检索结果-内蒙古大学图书馆

18th acm sigplan symposium on principles and practice of parallel programming

作者： Shun, Julian Blelloch, Guy E. Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450319225

there has been significant recent interest in parallel frameworks for processing graphs due to their applicability in studying social networks, the Web graph, networks in biology, and unstructured meshes in scientific simulation. Due to the desire to process large graphs, these systems have emphasized the ability to run on distributed memory machines. Today, however, a single multicore server can support more than a terabyte of memory, which can fit graphs with tens or even hundreds of billions of edges. Furthermore, for graph algorithms, shared-memory multicores are generally significantly more efficient on a per core, per dollar, and per joule basis than distributed memory systems, and shared-memory algorithms tend to be simpler than their distributed counterparts. In this paper, we present a lightweight graph processing framework that is specific for shared-memory parallel/multicore machines, which makes graph traversal algorithms easy to write. the framework has two very simple routines, one for mapping over edges and one for mapping over vertices. Our routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), our routines automatically adapt to the density of vertex sets. We implement several algorithms in this framework, including BFS, graph radii estimation, graph connectivity, betweenness centrality, PageRank and single-source shortest paths. Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly optimized code. Furthermore, they get good speedups on a 40-core machine and are significantly more efficient than previously reported results using graph frameworks on machines with many more cores.

关键词： Algorithms Performance Shared Memory Graph Algorithms parallel programming

来源：评论

学校读者我要写书评

暂无评论

Ownership Passing: Efficient Distributed Memory programming on Multi-core Systems 13

Ownership Passing: Efficient Distributed Memory Programming ...

引用

18th acm sigplan symposium on principles and practice of parallel programming

作者： Friedley, Andrew Hoefler, Torsten Bronevetsky, Greg Lumsdaine, Andrew Ma, Ching-Chen Indiana Univ Bloomington IN 47405 USA ETH Zurich Switzerland Lawrence Livermore Natl Lab Livermore CA USA Rose Hulman Inst Technol Terre Haute IN 47803 USA

ISBN: (纸本)9781450319225

the number of cores in multi- and many-core high-performance processors is steadily increasing. MPI, the de-facto standard for programming high-performance computing systems offers a distributed memory programming model. MPI's semantics force a copy from one process' send buffer to another process' receive buffer. this makes it difficult to achieve the same performance on modern hardware than shared memory programs which are arguably harder to maintain and debug. We propose generalizing MPI's communication model to include ownership passing, which make it possible to fully leverage the shared memory hardware of multi-and many-core CPUs to stream communicated data concurrently with the receiver's computations on it. the benefits and simplicity of message passing are retained by extending MPI with calls to send (pass) ownership of memory regions, instead of their contents, between processes. Ownership passing is achieved with a hybrid MPI implementation that runs MPI processes as threads and is mostly transparent to the user. We propose an API and a static analysis technique to transform legacy MPI codes automatically and transparently to the programmer, demonstrating that this scheme is easy to use in practice. Using the ownership passing technique, we see up to 51% communication speedups over a standard message passing implementation on state-of-the art multicore systems. Our analysis and interface will lay the groundwork for future development of MPI-aware optimizing compilers and multi-core specific optimizations, which will be key for success in current and next-generation computing platforms.

关键词： Ownership Passing Distributed Memory Shared Memory Message Passing Multi-core

来源：评论

学校读者我要写书评

暂无评论

Barrier elision for production parallel programs 2015

Barrier elision for production parallel programs

引用

20th acm sigplan symposium on principles and practice of parallel programming, PPoPP 2015

作者： Chabbi, Milind Lavrijsen, Wim De Jong, Wibe Sen, Koushik Mellor-Crummey, John Iancu, Costin Rice University United States Lawrence Berkeley National Laboratory United States UC Berkeley United States

ISBN: (纸本)9781450332057

Large scientific code bases are often composed of several layers of runtime libraries, implemented in multiple programming languages. In such situation, programmers often choose conservative synchronization patterns leading to suboptimal performance. In this paper, we present context-sensitive dynamic optimizations that elide barriers redundant during the program execution. In our technique, we perform data race detection alongside the program to identify redundant barriers in their calling contexts;after an initial learning, we start eliding all future instances of barriers occurring in the same calling context. We present an automatic on-the-fly optimization and a multi-pass guided optimization. We apply our techniques to NWChem - a 6 million line computational chemistry code written in C/C++/Fortran that uses several runtime libraries such as Global Arrays, ComEx, DMAPP, and MPI. Our technique elides a surprisingly high fraction of barriers (as many as 63%) in production runs. this redundancy elimination translates to application speedups as high as 14% on 2048 cores. Our techniques also provided valuable insight about the application behavior, later used by NWChem developers. Overall, we demonstrate the value of holistic context-sensitive analyses that consider the domain science in conjunction with the associated runtime software stack. Copyright 2015 acm.

关键词： Computational chemistry

来源：评论

学校读者我要写书评

暂无评论

TileSpGEMM: A Tiled Algorithm for parallel Sparse General Matrix-Matrix Multiplication on GPUs 22

TileSpGEMM: A Tiled Algorithm for Parallel Sparse General Ma...

引用

27th acm sigplan symposium on principles and practice of parallel programming (PPoPP)

作者： Niu, Yuyao Lu, Zhengyang Ji, Haonan Song, Shuhui Jin, Zhou Liu, Weifeng China Univ Petr Super Sci Software Lab Beijing Peoples R China

ISBN: (纸本)9781450392044

Sparse general matrix-matrix multiplication (SpGEMM) is one of the most fundamental building blocks in sparse linear solvers, graph processing frameworks and machine learning applications. the existing parallel approaches for shared memory SpGEMM mostly use the row-row style with possibly good parallelism. However, because of the irregularity in sparsity structures, the existing row-row methods often suffer from three problems: (1) load imbalance, (2) high global space complexity and unsatisfactory data locality, and (3) sparse accumulator selection. We in this paper propose a tiled parallel SpGEMM algorithm named TileSpGEMM. Our algorithm sparsifies the tiled method in dense general matrix-matrix multiplication (GEMM), and saves each non-empty tile in a sparse form. Its first advantage is that the basic working unit is now a fixed-size sparse tile containing a small number of nonzeros, but not a row possibly very long. thus the load imbalance issue can be naturally alleviated. Secondly, the temporary space needed for each tile is small and can always be in on-chip scratchpad memory. thus there is no need to allocate an off-chip space for a large amount of intermediate products, and the data locality can be much better. thirdly, because the computations are restricted within a single tile, it is relatively easier to select a fast sparse accumulator for a sparse tile. Our experimental results on two newest NVIDIA GPUs show that our TileSpGEMM outperforms four state-of-the-art SpGEMM methods cuSPARSE, bhSPARSE, NSPARSE and spECK in 139, 138, 127 and 94 out of all 142 square matrices executing no less than one billion flops for an SpGEMM operation, and delivers up to 2.78x, 145.35x, 97.86x and 3.70x speedups, respectively.

关键词： Sparse matrix SpGEMM tiled algorithm GPU

来源：评论

学校读者我要写书评

暂无评论

Provably Fast and Space-Efficient parallel Biconnectivity 23

Provably Fast and Space-Efficient Parallel Biconnectivity

引用

28th acm sigplan Annual symposium on principles and practice of parallel programming, PPoPP 2023

作者： Dong, Xiaojun Wang, Letong Gu, Yan Sun, Yihan UC Riverside

ISBN: (纸本)9798400700156

Computing biconnected components (BCC) of a graph is a fundamental graph problem. the canonical parallel BCC algorithm is the Tarjan-Vishkin algorithm, which has O(n + m) optimal work and polylogarithmic span on a graph with n vertices and m edges. However, Tarjan-Vishkin is not widely used in practice. We believe the reason is the space-inefficiency (it uses O(m) extra space). In practice, existing parallel implementations are based on breath-first search (BFS). Since BFS has span proportional to the diameter of the graph, existing parallel BCC implementations suffer from poor performance on large-diameter graphs and can be slower than the sequential algorithm on many real-world graphs. We propose the first p arallel b iconnectivity algorithm (FAST-BCC) that has optimal work, polylogarithmic span, and is space-efficient. Our algorithm creates a skeleton graph based on any spanning tree of the input graph. then we use the connectivity information of the skeleton to compute the biconnectivity of the original input. We carefully analyze the correctness of our algorithm, which is highly non-trivial. We implemented FAST-BCC and compared it with existing implementations, including GBBS, Slota and Madduri's algorithm, and the sequential Hopcroft-Tarjan algorithm. We tested them on a 96-core machine on 27 graphs with varying edge distributions. FAST-BCC is the fastest on all graphs. On average (geometric means), FAST-BCC is 3.1× faster than the best existing baseline on each graph. © 2023 Owner/Author.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Scheduling parallel Programs by Work Stealing with Private Deques 13

Scheduling Parallel Programs by Work Stealing with Private D...

引用

18th acm sigplan symposium on principles and practice of parallel programming

作者： Acar, Umut A. Chargueraud, Arthur Rainey, Mike Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Paris 11 CNRS LRI Orsay France

ISBN: (纸本)9781450319225

Work stealing has proven to be an effective method for scheduling parallel programs on multicore computers. To achieve high performance, work stealing distributes tasks between concurrent queues, called deques, which are assigned to each processor. Each processor operates on its deque locally except when performing load balancing via steals. Unfortunately, concurrent deques suffer from two limitations: 1) local deque operations require expensive memory fences in modern weak-memory architectures, 2) they can be very difficult to extend to support various optimizations and flexible forms of task distribution strategies needed many applications, e. g., those that do not fit nicely into the divide-and-conquer, nested data parallel paradigm. For these reasons, there has been a lot recent interest in implementations of work stealing with non-concurrent deques, where deques remain entirely private to each processor and load balancing is performed via message passing. Private deques eliminate the need for memory fences from local operations and enable the design and implementation of efficient techniques for reducing task-creation overheads and improving task distribution. these advantages, however, come at the cost of communication. It is not known whether work stealing with private deques enjoys the theoretical guarantees of concurrent deques and whether they can be effective in practice. In this paper, we propose two work-stealing algorithms with private deques and prove that the algorithms guarantee similar theoretical bounds as work stealing with concurrent deques. For the analysis, we use a probabilistic model and consider a new parameter, the branching depth of the computation. We present an implementation of the algorithm as a C++ library and show that it compares well to Cilk on a range of benchmarks. Since our approach relies on private deques, it enables implementing flexible task creation and distribution strategies. As a specific example, we show how to impleme

关键词： work stealing nested parallelism dynamic load balancing

来源：评论

学校读者我要写书评

暂无评论

An ownership policy and deadlock detector for promises 21

An ownership policy and deadlock detector for promises

引用

26th acm sigplan symposium on principles and practice of parallel programming, PPoPP 2021

作者： Voss, Caleb Sarkar, Vivek Georgia Institute of Technology United States

ISBN: (纸本)9781450382946

Task-parallel programs often enjoy deadlock freedom under certain restrictions, such as the use of structured join operations, as in Cilk and X10, or the use of asynchronous task futures together with deadlock-avoiding policies such as Known Joins or Transitive Joins. However, the promise, a popular synchronization primitive for parallel tasks, does not enjoy deadlock-freedom guarantees. Promises can exhibit deadlock-like bugs;however, the concept of a deadlock is not currently well-defined for promises. To address these challenges, we propose an ownership semantics in which each promise is associated to the task which currently intends to fulfill it. Ownership immediately enables the identification of bugs in which a task fails to fulfill a promise for which it is responsible. Ownership further enables the discussion of deadlock cycles among tasks and promises and allows us to introduce a robust definition of deadlock-like bugs for promises. Cycle detection in this context is non-trivial because it is concurrent with changes in promise ownership. We provide a lock-free algorithm for precise runtime deadlock detection. We show how to obtain the memory consistency criteria required for the correctness of our algorithm under TSO and the Java and C++ memory models. An evaluation compares the execution time and memory usage overheads of our detection algorithm on benchmark programs relative to an unverified baseline. Our detector exhibits a 12% (1.12×) geometric mean time overhead and a 6% (1.06×) geometric mean memory overhead, which are smaller overheads than in past approaches to deadlock cycle detection. © 2021 acm.

关键词： parallel programming

来源：评论

学校读者我要写书评

暂无评论

Energy-optimal configuration selection for manycore chips with variation

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2017年第5期31卷 451-466页

作者： Langer, Akhil Totoni, Ehsan Palekar, Udatta Kale, Laxmikant V. Intel Fed 1906 Fox Dr Champaign IL 61820 USA Univ Illinois Coll Business Urbana IL 61801 USA Univ Illinois Dept Comp Sci 1304 W Springfield Ave Urbana IL 61801 USA

Operating chips at high energy efficiency is one of the major challenges for modern large-scale supercomputers. Low-voltage operation of transistors increases the energy efficiency but leads to frequency and power variation across cores on the same chip. Finding energy-optimal configurations for such chips is a hard problem. In this work, we study how integer linear programming techniques can be used to obtain energy-efficient configurations of chips that have heterogeneous cores. Our proposed methodologies give optimal configurations as compared with competent but sub-optimal heuristics while having negligible timing overhead. the proposed ParSearch method gives up to 13.2% and 7% savings in energy while causing only 2% increase in execution time of two HPC applications: miniMD and Jacobi, respectively. Our results show that integer linear programming can be a very powerful online method to obtain energy-optimal configurations.

关键词： energy power optimization multicore chips low-voltage computing near-threshold voltage computing process variation heterogeneity integer programming quadratic integer programming

来源：评论

学校读者我要写书评

暂无评论

Accurate data redistribution cost estimation in software distributed shared memory systems 01

Accurate data redistribution cost estimation in software dis...

引用

8th acm sigplan symposium on principles and practice of parallel programming

作者： Morris III, D.G. Lowenthal, D.K. Hewlett-Packard Company 19447 Pruneridge Avenue Cupertino CA 95014 United States

ISBN: (纸本)9781581133462

Distributing data is one of the key problems in implementing efficient distributed-memory parallel programs. the problem becomes more difficult in programs where data redistribution between computational phases is considered. the global data distribution problem is to find the optimal distribution in multi-phase parallel programs. Solving this problem requires accurate knowledge of data redistribution cost. We are investigating this problem in the context of a software distributed shared memory (SDSM) system, in which obtaining accurate redistribution cost estimates is difficult. this is because SDSM communication is implicit: It depends on access patterns, page locations, and the SDSM consistency protocol. We have developed integrated compile- and run-time analysis for SDSM systems to determine accurate redistribution cost estimates with low overhead. Our resulting system, SUIF-Adapt, can efficiently and accurately estimate execution time, including redistribution, to within 5% of the actual time in all of our test cases and is often much closer. these precise costs enable SUIF-Adapt to find efficient global data distributions in multiple-phase programs.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

DAPPLE: A pipelined data parallel approach for training large models 21

DAPPLE: A pipelined data parallel approach for training larg...

引用

26th acm sigplan symposium on principles and practice of parallel programming, PPoPP 2021

作者： Fan, Shiqing Rong, Yi Meng, Chen Cao, Zongyan Wang, Siyu Zheng, Zhen Wu, Chuan Long, Guoping Yang, Jun Xia, Lixue Diao, Lansong Liu, Xiaoyong Lin, Wei Alibaba Group China

ISBN: (纸本)9781450382946

It is a challenging task to train large DNN models on sophisticated GPU platforms with diversified interconnect capabilities. Recently, pipelined training has been proposed as an effective approach for improving device utilization. However, there are still several tricky issues to address: improving computing efficiency while ensuring convergence, and reducing memory usage without incurring additional computing costs. We propose DAPPLE, a synchronous training framework which combines data parallelism and pipeline parallelism for large DNN models. It features a novel parallelization strategy planner to solve the partition and placement problems, and explores the optimal hybrid strategies of data and pipeline parallelism. We also propose a new runtime scheduling algorithm to reduce device memory usage, which is orthogonal to re-computation approach and does not come at the expense of training throughput. Experiments show that DAPPLE planner consistently outperforms strategies generated by PipeDream's planner by up to 3.23× speedup under synchronous training scenarios, and DAPPLE runtime outperforms GPipe by 1.6× speedup of training throughput and saves 12% of memory consumption at the same time. © 2021 acm.

关键词： Scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：