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

A comparison of task pools for dynamic load balancing of irregular algorithms

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2004年第1期16卷 1-47页

作者： Korch, M Rauber, T Univ Bayreuth Lehrstuhl Angew Informat 2 Fac Math Phys & Comp Sci D-95440 Bayreuth Germany

Since a static work distribution does not allow for satisfactory speed-ups of parallel irregular algorithms, there is a need for a dynamic distribution of work and data that can be adapted to the runtime behavior of the algorithm. Task pools are data structures which can distribute tasks dynamically to different processors where each task specifies computations to be performed and provides the data for these computations. This paper discusses the characteristics of task-based algorithms and describes the implementation of selected types of task pools for shared-memory multiprocessors. Several task pools have been implemented in C with POSIX threads and in Java. The task pools differ in the data structures to store the tasks, the mechanism to achieve load balance, and the memory manager used to store the tasks. Runtime experiments have been performed on three different shared-memory systems using a synthetic algorithm, the hierarchical radiosity method, and a volume rendering algorithm. Copyright (C) 2004 John Wiley Sons, Ltd.

关键词： task pools dynamic task scheduling irregular algorithms hierarchical radiosity volume rendering performance evaluation threads

来源：评论

学校读者我要写书评

暂无评论

Task Pool Teams:: a hybrid programming environment for irregular algorithms on SMP clusters

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2006年第12期18卷 1575-1594页

作者： Hippold, Judith Ruenger, Gudula Tech Univ Chemnitz Dept Comp Sci D-09107 Chemnitz Germany

Clusters of symmetric multiprocessors (SMPs) are popular platforms for parallel programming since they provide large computational power for a reasonable price. For irregular application programs with dynamically changing computation and data access behavior, a flexible programming model is needed to achieve efficiency. In this paper we propose Task Pool Teams as, a hybrid parallel programming environment to realize irregular algorithms on clusters of SMPs. Task Pool Teams combine task pools on single cluster nodes by an explicit message passing layer. They offer load balance together with multi-threaded, asynchronous communication. Appropriate communication protocols and task pool implementations are provided and accessible by an easy-to-use application programmer interface. As application examples we present a branch and bound algorithm and the hierarchical radiosity algorithm. Copyright (c) 2006 John Wiley & Sons, Ltd.

关键词： irregular algorithms hybrid programming SMP clusters

来源：评论

学校读者我要写书评

暂无评论

Scaling Runtimes for irregular algorithms to Large-Scale NUMA Systems

引用

COMPUTER 2015年第8期48卷 35-44页

作者： Lenharth, Andrew Pingali, Keshav Univ Texas Austin Inst Computat Sci & Engn Austin TX 78712 USA Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

The Galois system can automatically parallelize irregular algorithms written in a serial programming model and execute them efficiently on nonuniform memory access (NUMA) machines. Experimental results for five comple... 详细信息

关键词： multi-threading parallel algorithms automatic irregular algorithm parallelization complex irregular algorithms large-scale NUMA systems nonuniform memory access machines runtime scaling serial programming model Computer architecture Computer graphics Galois fields irregular algorithms Large-scale systems Memory management Parallel programming Runtime Scalability Software engineering ADP Galois NUMA amorphous data-parallelism computer architecture graph analytics irregular algorithms irregular applications memory allocation nonuniform memory access parallel programming scalability software engineering

来源：评论

学校读者我要写书评

暂无评论

Ordered vs. Unordered: a Comparison of Parallelism and Work-efficiency in irregular algorithms 11

Ordered <i>vs</i>. Unordered: a Comparison of Parallelism an...

引用

16th ACM Symposium on Principles and Practice of Parallel Programming

作者： Hassaan, M. Amber Burtscher, Martin Pingali, Keshav Texas State Univ San Marcos Dept Comp Sci San Marcos TX USA Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)9781450301190

Outside of computational science, most problems are formulated in terms of irregular data structures such as graphs, trees and sets. Unfortunately, we understand relatively little about the structure of parallelism and locality in irregular algorithms. In this paper, we study several algorithms for four such problems: discrete-event simulation, single-source shortest path, breadth-first search, and minimal spanning trees. We show that these algorithms can be classified into two categories that we call unordered and ordered, and demonstrate experimentally that there is a trade-off between parallelism and work efficiency: unordered algorithms usually have more parallelism than their ordered counterparts for the same problem, but they may also perform more work. Nevertheless, our experimental results show that unordered algorithms typically lead to more scalable implementations, demonstrating that less work-efficient irregular algorithms may be better for parallel execution.

关键词： irregular algorithms Amorphous Data-parallelism Parallel Breadth-first Search Single-Source Shortest Path Discrete-Event Simulation Minimal Spanning Tree Multicore processors Galois system algorithms Languages Performance

来源：评论

学校读者我要写书评

暂无评论

A Customizable Lightweight STM for irregular algorithms on GPU 36

A Customizable Lightweight STM for Irregular Algorithms on G...

引用

36th IEEE International Parallel and Distributed Processing Symposium (IEEE IPDPS)

作者： Manoochehri, Shayan Cristofaro, Patrick Goswami, Dhrubajyoti Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada

ISBN: (纸本)9781665497473

irregular algorithms are often encountered in highly data-centric application domains. These algorithms operate on irregular data structures such as sparse graphs with irregular access patterns, which may also modify the underlying topology unpredictably. high computational time and inherent data parallelism present in these algorithms motivate the use of GPI Js for speeding things up, however there are challenges for their efficient implementations due to: difficulty in protecting the shared data consistency in the presence of concurrent dynamic transactions;irregular access patterns due to unstructured data structures;and dynamic structural modifications of the underlying topology. One approach to overcome these challenges is to use Software 'transactional Memory (STM). However, overly complex design and implementations of contemporary STM-based approaches and lack of proper framework to employ them in conjunction with the irregular algorithms stalls their adoption by the programming community. To overcome some of these challenges, this research proposes a lightweight STM with a simple design (Lite GSTM), based on a lock stealing algorithm, and an associated extensible framework to hide the complexity of the STM from a programmer. The framework is extensible by allowing plug-ins of customized STMs designed for different needs of transactions. The use of the framework is elaborated with two use cases which employ completely different irregular algorithms, however, have some common features: the underlying data structure is a graph, and the graph is structurally modified (coarsened) unpredictably in the course of execution. The paper presents the performance comparisons of the STM-based implementations with respect to their sequential and non-STM based counterparts, which show promising results.

关键词： software transactional memory STM GPU irregular algorithms morph operations framework mininnun spanning tree coarsening graph partitioning

来源：评论

学校读者我要写书评

暂无评论

Toward a Microarchitecture for Efficient Execution of irregular Applications

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2020年第4期7卷 1–24页

作者： Leidel, John D. Wang, Xi Williams, Brody Chen, Yong Tact Comp Labs Box 43104 Lubbock TX 79409 USA Texas Tech Univ Box 43104 Lubbock TX 79409 USA

Given the increasing importance of efficient data-intensive computing, we find that modern processor designs are not well suited to the irregular memory access patterns often found in these algorithms. Applications and algorithms that do not exhibit spatial and temporal memory request locality induce high latency and low memory bandwidth due to the high cache miss rate. In response to the performance penalties inherently present in applications with irregular memory accesses, we introduce a GoblinCore-64 (GC64) architecture and a unique memory hierarchy that are explicitly designed to exploit memory performance from irregular memory access patterns. GC64 provides a pressure-driven hardware-managed concurrency control to minimize pipeline stalls and lower the latency of context switches. A novel memory coalescing model is also introduced to enhance the performance of memory systems via request aggregations. We have evaluated the performance benefits of our approach using a series of 24 benchmarks and the results show nearly 50% memory request reductions and a performance acceleration of up to 14.6x.

关键词： Data-intensive computing irregular algorithms thread concurrency context switching

来源：评论

学校读者我要写书评

暂无评论

Groute: An Asynchronous Multi-GPU Programming Model for irregular Computations 17

Groute: An Asynchronous Multi-GPU Programming Model for Irre...

引用

22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Ben-Nun, Tal Sutton, Michael Pai, Sreepathi Pingali, Keshav Hebrew Univ Jerusalem Jerusalem Israel Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781450344937

Nodes with multiple GPUs are becoming the platform of choice for high-performance computing. However, most applications are written using bulk-synchronous programming models, which may not be optimal for irregular algorithms that benefit from low-latency, asynchronous communication. This paper proposes constructs for asynchronous multi-GPU programming, and describes their implementation in a thin runtime environment called Groute. Groute also implements common collective operations and distributed work-lists, enabling the development of irregular applications without substantial programming effort. We demonstrate that this approach achieves state-of-the-art performance and exhibits strong scaling for a suite of irregular applications on 8-GPU and heterogeneous systems, yielding over 7x speedup for some algorithms.

关键词： Multi-GPU Asynchronous Programming irregular algorithms

来源：评论

学校读者我要写书评

暂无评论

Data-driven versus Topology-driven irregular Computations on GPUs

Data-driven versus Topology-driven Irregular Computations on...

引用

IEEE 27th International Parallel and Distributed Processing Symposium (IPDPS)

作者： Nasre, Rupesh Burtscher, Martin Pingali, Keshav Univ Texas Austin Austin TX 78712 USA Texas State Univ San Marcos TX USA

ISBN: (纸本)9780769549712

irregular algorithms are algorithms with complex main data structures such as directed and undirected graphs, trees, etc. A useful abstraction for many irregular algorithms is its operator formulation in which the algorithm is viewed as the iterated application of an operator to certain nodes, called active nodes, in the graph. Each operator application, called an activity, usually touches only a small part of the overall graph, so non-overlapping activities can be performed in parallel. In topology-driven implementations, all nodes are assumed to be active so the operator is applied everywhere in the graph even if there is no work to do at some nodes. In contrast, in data-driven implementations the operator is applied only to nodes at which there might be work to do. Multicore implementations of irregular algorithms are usually data-driven because current multicores only support small numbers of threads and work-efficiency is important. Conversely, many irregular GPU implementations use a topology-driven approach because work inefficiency can be counterbalanced by the large number of GPU threads. In this paper, we study data-driven and topology-driven implementations of six important graph algorithms on GPUs. Our goal is to understand the tradeoffs between these implementations and how to optimize them. We find that data-driven versions are generally faster and scale better despite the cost of maintaining a worklist. However, topology-driven versions can be superior when certain algorithmic properties are exploited to optimize the implementation. These results led us to devise hybrid approaches that combine the two techniques and outperform both of them.

关键词： irregular algorithms data-driven topology-driven algorithmic properties GPGPU

来源：评论

学校读者我要写书评

暂无评论

Processor Allocation for Optimistic Parallelization of irregular Programs 1

引用

12th International Conference on Computational Science and Its Applications (ICCSA)

作者： Versaci, Francesco Pingali, Keshav Univ Padua TU Wien I-35100AOGJ Padua Italy Univ Texas Austin Austin TX USA

ISBN: (数字)9783642311253

ISBN: (纸本)9783642311246;9783642311253

Optimistic parallelization is a promising approach for the parallelization of irregular algorithms: potentially interfering tasks are launched dynamically, and the runtime system detects conflicts between concurrent activities, aborting and rolling back conflicting tasks. However, parallelism in irregular algorithms is very complex. In a regular algorithm like dense matrix multiplication, the amount of parallelism can usually be expressed as a function of the problem size, so it is reasonably straightforward to determine how many processors should be allocated to execute a regular algorithm of a certain size (this is called the processor allocation problem). In contrast, parallelism in irregular algorithms can be a function of input parameters, and the amount of parallelism can vary dramatically during the execution of the irregular algorithm. Therefore, the processor allocation problem for irregular algorithms is very difficult. In this paper, we describe the first systematic strategy for addressing this problem. Our approach is based on a construct called the conflict graph, which (i) provides insight into the amount of parallelism that can be extracted from an irregular algorithm, and (ii) can be used to address the processor allocation problem for irregular algorithms. We show that this problem is related to a generalization of the unfriendly seating problem and, by extending Turan's theorem, we obtain a worst-case class of problems for optimistic parallelization, which we use to derive a lower bound on the exploitable parallelism. Finally, using some theoretically derived properties and some experimental facts, we design a quick and stable control strategy for solving the processor allocation problem heuristically.

关键词： irregular algorithms Optimistic parallelization Automatic parallelization Amorphous data-parallelism Processor allocation Unfriendly seating Turan's theorem

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Processor Allocation for Optimistic Parallelization of irregular Programs 11

Brief Announcement: Processor Allocation for Optimistic Para...

引用

23rd Annual Symposium on Parallelism in algorithms and Architectures

作者： Versaci, Francesco Pingali, Keshav Univ Padua Dept Informat Engn I-35100 Padua Italy

ISBN: (纸本)9781450307437

关键词： irregular algorithms Optimistic parallelization Amorphous data-parallelism Processor allocation Turan's theorem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：