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

22nd acm symposium on parallelism in algorithms and architectures

作者： Leiserson, Charles E. Schardl, Tao B. MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)9781450300797

We have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. Our PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation PBFS achieves high work-efficiency by using a novel implementation of a multiset data structure, called a "bag," in place of the FIFO queue usually employed in serial breadth-first search algorithms For a variety of benchmark Input graphs whose diameters are significantly smaller than the number of vertices a condition met by many real-world graphs PBFS demonstrates good speedup with the number of processing cores. Since PBFS employs a nonconstant-time "reducer" a "hyper-object" feature of Cilk++ the work inherent in a PM execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation We provide a general method for analyzing nondeterministic programs that use reducers PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis In particular, we show that for a graph G = (V, E) with diameter D and bounded out-degree, this data-race-free version of PBFS algorithm runs in time O((V + E)/P + Dlg(3) (V/D)) on P processors, which means that it attains near-perfect linear speedup if P << (V + E)I Dlg(3) (V/D).

关键词： Breadth-first search Cilk graph algorithms hyperobjects multithreading nondeterminism parallel algorithms reducers work-stealing

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Performance Potential of an Easy-to-Program PRAM-On-Chip Prototype Versus State-of-the-Art Processor 09

Brief Announcement: Performance Potential of an Easy-to-Prog...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Caragea, George C. Saybasili, A. Beliz Wen, Xingzhi Vishkin, Uzi Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9781605586069

we compare the Paraleap FPCA computer, a 64-processor hardware prototype of the PRAM-driven XMT architecture, with an Intel Core 2 Duo processor and show that Paraleap outperforms the Intel processor by up to 13.89x in terms of cycle counts. The comparison favors the Intel design, since the silicon area of an ASIC implementation of the 64-processor XMT design is the same as that of a single core.

关键词： paraleap parallel algorithms xmt PRAM explicit multi-treading ease of programming on-chip parallel processor

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Low Depth Cache-Oblivious Sorting 09

Brief Announcement: Low Depth Cache-Oblivious Sorting

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Blelloch, Guy E. Gibbons, Phillip B. Simhadri, Harsha Vardhan Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781605586069

Cache-oblivious algorithms have the advantage of achieving good sequential cache complexity across all levels of a multi-level cache hierarchy, regardless of the specifies (cache size and cache line size) of each level. In this paper, we describe cache-oblivious sorting algorithms with optimal work, optimal cache complexity and polylogarithmic depth. Using known mappings, these lead to low cache complexities on shared-memory multiprocessors with a single level of private caches or a single shared cache. Moreover, the low cache complexities extend to shared-memory multiprocessors with common configurations of multi-level caches. The key factor in the low cache complexity on multiprocessors is the low depth of the algorithms we propose.

关键词： Cache-oblivious algorithms sorting parallel algorithms multiprocessors schedulers

来源：评论

学校读者我要写书评

暂无评论

Inherent Limitations on Disjoint-Access parallel Implementations of Transactional Memory (Preliminary Version) 09

Inherent Limitations on Disjoint-Access Parallel Implementat...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Attiya, Hagit Hillel, Eshcar Milani, Alessia Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781605586069

Transactional memory (TM) is a promising approach for designing concurrent data structures, and it is essential to develop better understanding of the formal properties that can be achieved by TM implementations. Two fundamental properties of TM implementations are disjoint-access parallelism, which is critical for their scalability, and the invisibility of read operations, which reduces memory contention. This paper proves an inherent tradeoff for implementations of transactional memories: they cannot be both disjoint-access parallel and have read-only transactions that are invisible and always terminate successfully. In fact, a lower bound of Omega(t) is proved on the number of writes needed in order to implement a read-only transaction of t items, which successfully terminates in a disjoint-access parallel TM implementation. The results assume strict serializability and thus hold under the assumption of opacity. It is shown how to extend the results to hold also for weaker consistency conditions, serializability and snapshot isolation.

关键词： Transactional memory disjoint-access parallelism partial snapshots lower bound impossibility result

来源：评论

学校读者我要写书评

暂无评论

parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks 09

Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Mu...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Buluc, Aydin Fineman, Jeremy T. Frigo, Matteo Gilbert, John R. Leiserson, Charles E. Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

ISBN: (纸本)9781605586069

This paper introduces a storage format for sparse matrices, called compressed sparse blocks (CSB), which allows both Ax and A(x)(inverted perpendicular) to be computed efficiently in parallel, where A is an n x n sparse matrix with nnz >= n nonzeros and x is a dense n-vector. Our algorithms use Theta(nnz) work (serial running time) and Theta(root nlgn) span (critical-path length), yielding a parallelism of Theta(nnz/root nlgn), which is amply high for virtually any large matrix. The storage requirement for CSB is esssentially the same as that for the more-standard compressed-sparse-rows (CSR) format, for which computing Ax in parallel is easy but A(x)(inverted perpendicular) is difficult. Benchmark results indicate that on one processor, the CSB algorithms for Ax and A(x)(inverted perpendicular) run just as fast as the CSR algorithm for Ax, but the CSB algorithms also scale up linearly with processors until limited by off-chip memory bandwidth.

关键词： Compressed sparse blocks compressed sparse columns compressed sparse rows matrix transpose matrix-vector multiplication multithreaded algorithm parallelism span sparse matrix storage format work

来源：评论

学校读者我要写书评

暂无评论

SPAA'09 - Proceedings of the 21st annual symposium on parallelism in algorithms and architectures

SPAA'09 - Proceedings of the 21st Annual Symposium on Parall...

引用

21st annual symposium on parallelism in algorithms and architectures, SPAA'09

ISBN: (纸本)9781605586069

The proceedings contain 43 papers. The topics discussed include: speed scaling of processes with arbitrary speedup curves on a multiprocessor;the bell is ringing in speed-scaled multiprocessor scheduling;mapping filtering streaming applications with communication costs;scheduling to minimize staleness and stretch in real-time data warehouses;parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design;selfishness in transactional memory;at-most-once semantics in asynchronous shared memory;memory models: a case for rethinking parallel languages and hardware;the life and times of a ZooKeeper;Cassandra - a structured storage system on a P2P network;Pregel: a system for large-scale graph processing;towards transactional memory semantics for C++;on avoiding spare aborts in transactional memory;inherent limitations on disjoint-access parallel implementations of transactional memory;reducers and other Cilk++ hyperobjects;and beyond nested parallelism: tight bounds on work-stealing overheads for parallel futures.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Field-Split parallel Architecture for High Performance Multi-Match Packet Classification Using FPGAs 09

Field-Split Parallel Architecture for High Performance Multi...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Jiang, Weirong Prasanna, Viktor K. Univ So Calif Ming Hsieh Dept Elect Engn Los Angeles CA 90089 USA

ISBN: (纸本)9781605586069

Multi-match packet classification is a critical function in network intrusion detection systems (NIDS), where all matching rules for a packet need to be reported. Most of the previous work is based on ternary content addressable memories (TCAMs) which are expensive and are not scalable with respect to clock rate, power consumption, and circuit area. This paper studies the characteristics of real-life Snort NIDS rule sets, and proposes a novel SRAM-based architecture. The proposed architecture is called field-split parallel bit vector (FSBV) where some header fields of a packet are further split into bit-level subfields. Unlike previous multi-match packet classification algorithms which suffer from memory explosion, the memory requirement of FSBV is linear in the number of rules. FPGA technology is exploited to provide high throughput and to support dynamic updates. Implementation results show that our architecture can store on a single Xilinx Virtex-5 FPGA the full set of packet header rules extracted from the latest Snort NIDS and sustains 100 Gbps throughput for minimum size (40 bytes) packets. The design achieves 1.25x improvement in throughput while the power consumption is approximately one fourth that of the state-of-the-art solutions.

关键词： FPGA multi-match packet classification NIDS SRAM

来源：评论

学校读者我要写书评

暂无评论

Beyond Nested parallelism: Tight Bounds on Work-Stealing Overheads for parallel Futures 09

Beyond Nested Parallelism: Tight Bounds on Work-Stealing Ove...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Spoonhower, Daniel Blelloch, Guy E. Gibbons, Phillip B. Harper, Robert Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781605586069

Work stealing is a popular method of scheduling fine-grained parallel tasks. The performance of work stealing has been extensively studied, both theoretically and empirically, but primarily for the restricted class of nested-parallel (or fully strict) computations. we extend this prior work by considering a broader class of programs that also supports pipelined parallelism through the use of parallel futures. Though the overhead of work-stealing schedulers is often quantified in terms of the number of steals, we show that a broader metric, the number of deviations, is a better way to quantify work-stealing overhead for less restrictive forms of parallelism, including parallel futures. For such parallelism, we prove bounds on work-stealing overheads-scheduler time and cache misses-as a function of the number of deviations Deviations can occur, for example, when work is stolen or when a future is touched. We also show instances where deviations can occur independently of steals and touches. Next, we prove that, under work stealing, the expected number of deviations is O(Pd+td) in a P-processor execution of a computation with span d and t touches of futures. Moreover, this bound is existentially tight for any work-stealing scheduler that is parsimonious (those where processors steal only when their queues are empty);this class includes all prior work-stealing schedulers. We also present empirical measurements of the number of deviations incurred by a classic application of futures, Halstead's quicksort, using our parallel implementation of ML. Finally, we identify a family of applications that use futures and, in contrast to quicksort, incur significantly smaller overheads.

关键词： scheduling work stealing futures performance bounds

来源：评论

学校读者我要写书评

暂无评论

Communication-Optimal parallel and Sequential Cholesky Decomposition 09

Communication-Optimal Parallel and Sequential Cholesky Decom...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Ballard, Grey Demmel, James Holtz, Olga Schwartz, Oded Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)9781605586069

Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional (O(n(3))) matrix multiplication to Cholesky factorization, which is used for solving dense symmetric positive definite linear systems. Second, we compare the cost of various Cholesky decomposition implementations to this lower bound, and draw the following conclusions: (1) "Naive" sequential algorithms for Cholesky attain neither the bandwidth nor latency lower bounds. (2) The sequential blocked algorithm in LAPACK (with the right block size), as well as various recursive algorithms [AP00, GJ01, ACW01, ST04] and one based on work of Toledo [Tol97], can attain the bandwidth lower bound. (3) The LAPACK algorithm can also attain the latency bound if used with blocked data structures rather than column-wise or row-wise matrix data structures, though the Toledo algorithm cannot. (4) The recursive sequential algorithm due to [AP00], attains the bandwidth and latency lower bounds at every level of a multi-level memory hierarchy, in a "cache-oblivious" way. (5) The parallel implementation of Cholesky in the ScaLA-PACK library (again with the right block-size) attains both the bandwidth and latency lower bounds to within a poly-logarithmic factor. Combined with prior results in [DGHL08a, DGHL08b, DGX08] this gives a complete set;of communication-optimal algorithms for O(n(3)) implementations of three basic factorizations of dense linear algebra: LU with pivoting, QR and Cholesky. But it goes beyond this prior work on sequential LU and QR by optimizing communication for any number of levels of memo

关键词： communication avoiding Cholesky decomposition lower bound bandwidth latency algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Price of Heterogeneity in parallel Systems

引用

THEORY OF COMPUTING SYSTEMS 2009年第2期45卷 280-301页

作者： Godfrey, P. Brighten Karp, Richard M. Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA

Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system's performance as a function of its nodes' capacities C and workload W (such as the makespan of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity alpha when for any workload, cost cannot increase by more than a factor alpha if node capacities become arbitrarily more heterogeneous. The price of heterogeneity also upper bounds the "value of parallelism": the maximum benefit obtained by increasing parallelism at the expense of decreasing processor speed. We give constant or logarithmic bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that in many cases, increasing heterogeneity can never be much of a disadvantage.

关键词： Heterogeneity parallel systems Scheduling Makespan Precedence constrained scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：