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

47th annual IEEE/acm International symposium on Microarchitecture, MICRO 2014

The proceedings contain 53 papers. The topics discussed include: transparent hardware management of stacked DRAM as part of memory;unison cache: a scalable and effective die-stacked DRAM cache;locality-aware mapping of nested parallel patterns on GPUs;accelerating irregular algorithms on GPGPUs using fine-grain hardware worklists;exploring the design space of SPMD divergence management on data-parallel architectures;managing GPU concurrency in heterogeneous architectures;FIRM: fair and high-performance memory control for persistent memory systems;efficient memory virtualization: reducing dimensionality of nested page walks;Iso-X: a flexible architecture for hardware-managed isolated execution;cc-hunter: uncovering covert timing channels on shared processor hardware;a practical methodology for measuring the side-channel signal available to the attacker for instruction-level events;and calculating architectural vulnerability factors for spatial multi-bit transient faults.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Emulations between QSM, BSP and LogP: A framework for general-purpose parallel algorithm design

Emulations between QSM, BSP and LogP: A framework for genera...

引用

Proceedings of the 1999 10th annual acm-SIAM symposium on Discrete algorithms

作者： Ramachandran, Vijaya Grayson, Brian Dahlin, Michael Univ of Texas at Austin Austin United States

Bulk synchronous parallel (BSP), LogP, and Queuing shared memory (QSM) are general-purpose parallel models that seek to achieve the right balance of simplicity, accuracy and broad applicability in the modelling of parallel machines. These models are essentially interchangeable by giving work-preserving emulations with small slowdown between these models. Work-preserving emulations between the three models are discussed.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Integer Sort: Theory and Practice 24

Parallel Integer Sort: Theory and Practice

引用

29th acm SIGPLAN annual symposium on Principles and Practice of parallel Programming (PPoPP)

作者： Dong, Xiaojun Dhulipala, Laxman Gu, Yan Sun, Yihan UC Riverside Riverside CA 92521 USA Univ Maryland Baltimore MD USA

ISBN: (纸本)9798400704352

Integer sorting is a fundamental problem in computer science. This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid theoretical foundation for their widespread usage in practice and strong performance. In practice, we design a new integer sorting algorithm, DovetailSort, that is theoreticallyefficient and has good practical performance. In particular, DovetailSort overcomes a common challenge in existing parallel integer sorting algorithms, which is the difficulty of detecting and taking advantage of duplicate keys. The key insight in DovetailSort is to combine algorithmic ideas from both integer- and comparison-sorting algorithms. In our experiments, DovetailSort achieves competitive or better performance than existing state-of-the-art parallel integer and comparison sorting algorithms on various synthetic and real-world datasets.

关键词： Integer Sort Radix Sort parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Graph algorithms with Batch Updates in the Massively parallel Computation Model 32

Dynamic Graph Algorithms with Batch Updates in the Massively...

引用

32nd annual acm-SIAM symposium on Discrete algorithms (SODA)

作者： Nowicki, Krzysztof Onak, Krzysztof Univ Wroclaw Wroclaw Poland IBM Res Hawthorne NY USA

ISBN: (纸本)9781611976465

We study dynamic graph algorithms in the Massively parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can efficiently handle large batches of edge insertions and deletions. We show algorithms that require fewer rounds to update a solution to problems such as Minimum Spanning Forest, 2-Edge Connected Components, and Maximal Matching than would be required by their static counterparts to compute it from scratch. They work in the most restrictive memory regime, in which local memory per machine is strongly sublinear in the number of graph vertices. Improving on the size of the batch they can handle efficiently would improve on the round complexity of known static algorithms on sparse graphs. Our algorithms can process batches of updates of size Theta(S), for Minimum Spanning Forest and 2-Edge Connected Components, and Theta(S1-epsilon), for Maximal Matching, in O(1) rounds, where S is the local memory of a single machine.

关键词： Scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel algorithms in the Binary-Forking Model 20

Optimal Parallel Algorithms in the Binary-Forking Model

引用

32nd acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Blelloch, Guy E. Fineman, Jeremy T. Gu, Yan Sun, Yihan Carnegie Mellon Univ Pittsburgh PA 15213 USA Georgetown Univ Washington DC 20057 USA Univ Calif Riverside Riverside CA 92521 USA

ISBN: (纸本)9781450369350

In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and ordered set union, intersection and difference. In the binary-forking model, tasks can only fork into two child tasks, but can do so recursively and asynchronously. The tasks share memory, supporting reads, writes and test-and-sets. Costs are measured in terms of work (total number of instructions), and span (longest dependence chain). The binary-forking model is meant to capture both algorithm performance and algorithm-design considerations on many existing multithreaded languages, which are also asynchronous and rely on binary forks either explicitly or under the covers. In contrast to the widely studied PRAM model, it does not assume arbitrary-way forks nor synchronous operations, both of which are hard to implement in modern hardware. While optimal PRAM algorithms are known for the problems studied herein, it turns out that arbitrary-way forking and strict synchronization are powerful, if unrealistic, capabilities. Natural simulations of these PRAM algorithms in the binary-forking model (i.e., implementations in existing parallel languages) incur an Omega(logn) overhead in span. This paper explores techniques for designing optimal algorithms when limited to binary forking and assuming asynchrony. All algorithms described in this paper are the first algorithms with optimal work and span in the binary-forking model. Most of the algorithms are simple. Many are randomized.

关键词： list ranking RMQ list contraction tree contraction intersection binary forking set-set operation range minimum query semisort parallel computational model tree merging fork-join union difference sorting

来源：评论

学校读者我要写书评

暂无评论

Evaluating Graph Coloring on GPUs 11

Evaluating Graph Coloring on GPUs

引用

16th acm symposium on Principles and Practice of parallel Programming

作者： Grosset, A. V. Pascal Zhu, Peihong Liu, Shusen Venkatasubramanian, Suresh Hall, Mary Univ Utah Sch Comp Salt Lake City UT 84112 USA

ISBN: (纸本)9781450301190

This paper evaluates features of graph coloring algorithms implemented on graphics processing units (GPUs), comparing coloring heuristics and thread decompositions. As compared to prior work on graph coloring for other parallel architectures, we find that the large number of cores and relatively high global memory bandwidth of a GPU lead to different strategies for the parallel implementation. Specifically, we find that a simple uniform block partitioning is very effective on GPUs and our parallel coloring heuristics lead to the same or fewer colors than prior approaches for distributed-memory cluster architecture. Our algorithm resolves many coloring conflicts across partitioned blocks on the GPU by iterating through the coloring process, before returning to the CPU to resolve remaining conflicts. With this approach we get as few color (if not fewer) than the best sequential graph coloring algorithm and performance is close to the fastest sequential graph coloring algorithms which have poor color quality.

关键词： algorithms Performance Graph coloring parallel algorithm GPU CUDA

来源：评论

学校读者我要写书评

暂无评论

Can a shared-memory model serve as a bridging model for parallel computation?

引用

THEORY OF COMPUTING SYSTEMS 1999年第3期32卷 327-359页

作者： Gibbons, PB Matias, Y Ramachandran, V AT&T Bell Labs Lucent Technol Informat Sci Res Ctr Murray Hill NJ 07974 USA Univ Texas Dept Comp Sci Austin TX 78712 USA

There has been a great deal of interest recently in the development of general-purpose bridging models for parallel computation. Models such as the BSP and LogP have been proposed as more realistic alternatives to the widely used PRAM model. The BSP and LogP models imply a rather different style for designing algorithms when compared with the PRAM model. Indeed, while many consider data parallelism as a convenient style, and the shared-memory abstraction as an easy-to-use platform, the bandwidth limitations of current machines have diverted much attention to message-passing and distributed-memory models (such as the BSP and LogP) that account more properly for these limitations. In this paper we consider the question of whether a shared-memory model can serve as an effective bridging model for parallel computation. In particular, can a shared-memory model be as effective as, say, the BSP? As a candidate for a bridging model, we introduce the Queuing Shared-Memory (QSM) model, which accounts for limited communication bandwidth while still providing a simple shared-memory abstraction. We substantiate the ability of the QSM to serve as a bridging model by providing a simple work-preserving emulation of the QSM on both the ssp, and on a related model, the (d, x)-BSP. We present evidence that the features of the QSM are essential to its effectiveness as a bridging model. In addition, we describe scenarios in which the high-level QSM more accurately models certain machines than the more detailed ssp and LogP models. Finally, we present algorithmic results for the QSM, as well as general strategies for mapping algorithms designed for the ssp or PRAM models onto the QSM model. Our main conclusion is that shared-memory models can potentially serve as viable alternatives to existing message-passing, distributed-memory bridging models.

关键词： Message passing

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: An implementation report for parallel triangular decompositions

Brief announcement: An implementation report for parallel tr...

引用

SPAA 2006: 18th annual acm symposium on parallelism in algorithms and architectures

作者： Maza, Marc Moreno Xie, Yuzhen London Ont. Canada

ISBN: (纸本)1595934529

Since the discovery of Gröbner bases, the algorithmic advances in Commutative Algebra have made possible to tackle many classical problems in Algebraic Geometry that were previously out of reach. However, algorithmic progress is still desirable, for instance when solving symbolically a large system of algebraic non-linear equations. For such a system, in particular if its solution set consists of geometric components of different dimension (points, curves, surfaces, etc) it is necessary to combine Gröbner bases with decomposition techniques, such as triangular decompositions. Ideally, one would like each of the different components to be produced by an independent processor, or set of processors. In practice, the input polynomial system, which is hiding those components, requires some transformations in order to split the computations into sub-systems and, then, lead to the desired components. The efficiency of this approach depends on its ability to detect and exploit geometrical information during the solving process. Our work addresses two questions: How to discover geometrical information, at an early stage of the solving process, that would be favorable to parallel execution? How to ensure load balancing among the processors? We answer these questions in the context of triangular decompositions [2] which are a popular way of solving polynomial systems symbolically. These methods tend to split the input polynomial system into subsystems and, therefore, are natural candidate for parallel implementation. However, the only such method which has been parallelized so far is the Characteristic Set Method of Wu [5], as reported in [1, 6]. This approach suffers from several limitations. For instance, the solving of the second component cannot start before that of the first one is completed;this is a limitation in view of coarse-grain parallelization. In [4] an algorithm, called Triade, for TRIAngular DEcompositions, provides a good management of the intermediate computa

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

parallel construction and query of suffix trees for two-dimensional matrices 93

Parallel construction and query of suffix trees for two-dime...

引用

5th annual acm symposium on parallel algorithms and architectures, SPAA 1993

作者： Giancarlo, Raffaele Grossi, Roberto AT and T Bell Laboratories Murray HillNJ07974 United States University of Palermo Italy Dipartimento di Informatica Università di Pisa Pisa56125 Italy Dipartimento di Sistemi e Informatica Università di Firenze Firenze50134 Italy

ISBN: (纸本)0897915992

We give efficient CRCW PRAM algorithms for the construction of two data structures, the Lsuffix Tree of a square matrix and the Nested Suffix Tree of a general matrix. The Lsuffix tree, introduced by Giancarlo [11], represents all square submatrices of a square matrix. The nested suffix tree, introduced here, represents all rectangular submatrices of a given general matrix. Both data structures can be seen as a generalization to matrices of the suffix tree of a string [18]. We remark that the problem of building a tree data structure representing all rectangular submatrices of a given matrix has been shown to be computationally harder than the problem of building a tree data structure representing only the square submatrices of a given matrix [10]. Thus, our attention for the important special case of square submatrices is justified. Once those two data structures are available, we can answer quickly and in parallel, a wide variety of queries that have many important applications in low-level image processing [20], visual databases [12] and two-dimensional data compression [16, 21, 22]. All matrices in this abstract have entries defined over an ordered alphabet E. © 1993 acm.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Near Optimal parallel algorithms for Dynamic DFS in Undirected Graphs 17

Near Optimal Parallel Algorithms for Dynamic DFS in Undirect...

引用

29th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Khan, Shahbaz IIT Kanpur Dept CSE Kanpur 208016 Uttar Pradesh India

ISBN: (纸本)9781450345934

Depth first search (DFS) tree is a fundamental data structure for solving various graph problems. The classical algorithm [37] for building a DFS tree requires O(m + n) time for a given undirected graph G having n vertices and m edges. Recently, Baswana et al. [5] presented a simple algorithm for updating the DFS tree of an undirected graph after an edge/vertex update in (O) over tilde (n)(1) time. However, their algorithm is strictly sequential. We present an algorithm achieving similar bounds that can be easily adopted to the parallel environment. In the parallel environment, a DFS tree can be computed from scratch using O(m) processors in expected (O) over tilde (1) time [2] on an EREW PRAM, whereas the best deterministic algorithm takes (O) over tilde (root n) time [2, 17] on a CRCW PRAM. Our algorithm can be used to develop optimal time (upto poly log n factors) deterministic parallel algorithms for maintaining fully dynamic DFS and fault tolerant DFS of an undirected graph. (1) parallel Fully Dynamic DFS: Given any arbitrary online sequence of vertex or edge updates, we can maintain a DFS tree of an undirected graph in (O) over tilde (1) time per update using m processors on an EREW PRAM. (2) parallel Fault tolerant DFS: An undirected graph can be preprocessed to build a data structure of size O(m), such that for any set of k updates (where k is constant) in the graph, a DFS tree of the updated graph can be computed in (O) over tilde (1) time using n processors on an EREW PRAM. For constant k, this is also work optimal (upto poly log n factors). Moreover, our fully dynamic DFS algorithm provides, in a seamless manner, nearly optimal (upto poly log n factors) algorithms for maintaining a DFS tree in the semi-streaming environment and a restricted distributed model. These are the first parallel, semi-streaming and distributed algorithms for maintaining a DFS tree in the dynamic setting.

关键词： parallel dynamic DFS graph algorithm streaming distributed

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：