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

3rd annual acm symposium on parallel algorithms and architectures - SPAA'91

作者： Kunde, M. Institut f. Informatik TU Munich Arcisstr. 21 D-8000 Munich 2 Germany

The problem of packet routing on an r-dimensional mesh-connected array or grid of processors with side-length n is studied. Each processor is able to store rf(n) packets, f(n) 1-1/r. The new class of balanced routing ... 详细信息

ISBN: (纸本)0897914384

The problem of packet routing on an r-dimensional mesh-connected array or grid of processors with side-length n is studied. Each processor is able to store rf(n) packets, f(n) < n^1-1/r. The new class of balanced routing problems is introduced which includes such fundamental problems as partial h - h routing. On 3-dimensional n × n × n grids (without wrap-arounds) partial permutation problems and so-called (1, f(n))-balanced problems can be solved by a deterministic routing algorithm needing only 3.333n + O(n/f(n)^1/2) steps which is asymptotically only 11.11 percent larger than the distance bound of 3n - 3 steps. The result is better than those of so far known randomized algorithms, routing data only with high probability. The new algorithm also beats previous deterministic routing algorithms. For arbitrary r, r > 3, permutation routing on r-dimensional cubes can be performed in asymptotically (2r - 3+l/r)n steps which again is faster than the running times of so far known algorithms, both randomized and deterministic ones. A further improvement leads to an algorithm with approximately (r + (r - 2)(I/r)^1/(r-2))n + O(n/f(n) ^1/(r-1)) transport steps. For a constant buffer size of O((r²/ϵ) ^r-1) packets, ϵ > 0, a number of (r+(r - 2)(l/r) ^1/(r-2)/ + ϵ)n steps can be achieved. The number of steps is reduced to the half if the algorithms are adapted to tori of processors, i.e. grids with wrap-around connections. Furthermore, algorithms for the general h - h routing problem are presented which also needs a smaller number of steps than previous algorithms. It is shown that these problems can be solved in O((h + r)n) instead of O(hrn) needed before. © 1991 acm.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

The Dataflow Abstract Machine Simulator Framework 51

The Dataflow Abstract Machine Simulator Framework

引用

acm/IEEE 51st annual International symposium on Computer Architecture (ISCA)

作者： Zhang, Nathan Lacouture, Rubens Sohn, Gina Mure, Paul Zhang, Qizheng Kjolstad, Fredrik Olukotun, Kunle Stanford Univ Stanford CA 94305 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9798350326598;9798350326581

The growing interest in novel dataflow architectures and streaming execution paradigms has created the need for a simulator optimized for modeling dataflow systems. To fill this need, we present three new techniques that make it feasible to simulate complex systems consisting of thousands of components. First, we introduce an interface based on Communicating Sequential Processes which allows users to simultaneously describe functional and timing characteristics. Second, we introduce a scalable point-to-point synchronization scheme that avoids global synchronization. Finally, we demonstrate a technique to exploit slack in the simulated system, such as FIFOs, to increase simulation parallelism. We implement these techniques in the Dataflow Abstract Machine (DAM), a parallel simulator framework for dataflow systems. We demonstrate the benefits of using DAM by highlighting three case studies using the framework. First, we use DAM directly as an exploration tool for streaming algorithms on dataflow hardware. We simulate two different implementations of the attention algorithm used in large language models, and use DAM to show that the second implementation only requires a constant amount of local memory. Second, we re-implement a simulator for a sparse tensor algebra accelerator, resulting in 57% less code and a simulation speedup of up to four orders of magnitude. Finally, we demonstrate a general technique for time-multiplexing real hardware to simulate multiple virtual copies of the hardware using DAM.

关键词： Dataflow Accelerators Modeling parallel Discrete Event Simulation

来源：评论

学校读者我要写书评

暂无评论

Scheduling Strategies for Optimistic parallel Execution of Irregular Programs 08

Scheduling Strategies for Optimistic Parallel Execution of I...

引用

20th acm symposium on parallelism in algorithms and architectures

作者： Kulkarni, Milind Carribault, Patrick Pingali, Keshav Ramanarayanan, Ganesh Walter, Bruce Bala, Kavita Chew, L. Paul Univ Texas Austin Austin TX 78712 USA Cornell Univ Ithaca NY USA

ISBN: (纸本)9781595939739

Recent application studies have shown that many irregular applications have a generalized data parallelism that manifests itself as iterative computations over worklists of different kinds. In general, there are complex dependencies between iterations. These dependencies cannot be elucidated statically because they depend on the inputs to the program;thus, optimistic parallel execution is the only tractable approach to parallelizing these applications. We have built a system called Galois that supports this style of parallel execution. Its main features are (i) set iterators for expressing worklist-based data parallelism, and (ii) a runtime system that performs optimistic parallelization of these iterators, detecting conflicts and rolling back computations as needed. Our work builds on the Galois system, and it addresses the problem of scheduling iterations of set iterators on multiple cores. The policy used by the base Galois system is to assign an iteration to a core whenever it needs work to do, but we show in this paper that this policy is not optimal for many applications. We also argue that OpenMP-style DO-ALL loop scheduling directives such as chunked and guided self-scheduling are too simplistic for irregular programs. These difficulties led us to develop a general scheduling framework for irregular problems;OpenMP-style scheduling strategies are special cases of this general approach. We also provide hooks into our framework, allowing the programmer to leverage application knowledge to further tune a schedule for a particular application. To evaluate this framework, we implemented it as an extension of the Galois system. We then tested the system using five real-world, irregular, data-parallel applications. Our results show that (i) the optimal scheduling policy can be different for different applications and often leverages application-specific knowledge and (ii) implementing these schedules in the Galois system is relatively straightforward.

关键词： Optimistic parallelism Irregular Programs Scheduling

来源：评论

学校读者我要写书评

暂无评论

Tight Competitive Ratios for parallel Disk Prefetching and Caching 08

Tight Competitive Ratios for Parallel Disk Prefetching and C...

引用

20th acm symposium on parallelism in algorithms and architectures

作者： Hon, Wing-Kai Shah, Rahul Varman, Peter J. Vitter, Jeffrey Scott Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Rice Univ Dept ECE Houston TX 77251 USA Purdue Univ Coll Sci W Lafayette IN 47907 USA

ISBN: (纸本)9781595939739

We consider the natural extension of the well-known single disk caching problem to the parallel disk I/O model (PDM) [17]. The main challenge is to achieve as much parallelism as possible and avoid I/O bottlenecks. We are given a fast memory (cache) of size M memory blocks along with a request sequence Sigma = (b(1),b(2), ... ,b(n)) where each block b(i) resides on one of D disks. In each parallel I/O step, at most one block from each disk can be fetched. The task is to serve Sigma in the minimum number of parallel I/Os. Thus, each I/O is analogous to a page fault. The difference here is that during each page fault, up to D blocks can be brought into memory, as long as all of the new blocks entering the memory reside on different disks. The problem has a long history [18, 12, 13, 26]. Note that this problem is non-trivial even if all requests in Sigma are unique. This restricted version is called read-once. Despite the progress in the offline version [13, 15] and read-once version [12], the general online problem still remained open. Here, we provide comprehensive results with a full general solution for the problem with asymptotically tight competitive ratios. To exploit parallelism, any parallel disk algorithm needs a certain amount of lookahead into future requests. To provide effective caching, an online algorithm must achieve o(D) competitive ratio. We show a lower bound that states, for lookahead L <= M, any online algorithm must be Omega(D)-competitive. For lookahead L greater than M(1 + 1/epsilon), where c is a constant, the tight upper bound of O(root MD/L) on competitive ratio is achieved by our algorithm SKEW. The previous algorithm tLRU [26] was O((MD/L)(2/3)) competitive and this was also shown to be tight [26] for an LRU-based strategy. We achieve the tight ratio using a fairly different strategy than LRU. We also show tight results for randomized algorithms against oblivious adversary and give an algorithm achieving better bounds in the resource augme

关键词： Online algorithms Competitive Analysis parallel Disk Model

来源：评论

学校读者我要写书评

暂无评论

Fault diagnosis in a small constant number of parallel testing rounds 93

Fault diagnosis in a small constant number of parallel testi...

引用

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

作者： Beigel, Richard Margulis, Grigorii Spielman, Daniel A. Yale University United States Russian Academy of Sciences Russia MIT Russia Yale Station Department of Computer Science P.O. Box 2158 New HavenCT06520-2158 United States Department of Mathematics Yale Station P.O. Box 2155 New HavenCT06520-2155 United States Department of Applied Mathematics Massachusetts Institute of Technology CambridgeMA02139 United States

ISBN: (纸本)0897915992

Consider a set of processors, V, that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can be used to test each other. We provide a parallel algorithm that determines which processors are good and which are faulty in 32 rounds of testing, provided that a strict majority of the processors are good. © 1993 acm.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

parallel rectilinear shortest paths with rectangular obstacles 90

Parallel rectilinear shortest paths with rectangular obstacl...

引用

SPAA '90 - proceedings of the 2nd annual acm symposium on parallel algorithms and architectures

作者： Atallah, Mikhail J. Chen, Danny Z. Purdue Univ West Lafayette IN United States

ISBN: (纸本)0897913701

Let P be a simple rectilinear convex polygon of size O(n) inside which lie n pairwise disjoint rectangular rectilinear obstacles. We provide parallel techniques for computing rectilinear shortest paths that avoid the set of obstacles in P. Specifically, we compute descriptions of shortest paths in O(log2 n) time, with O(n2/log2n) processors in the CREWPRAM model if source and destination are on the boundary of P, with O(n2/log n) processors if the source is an obstacle vertex and the destination a vertex of P, and with O(n2) processors if both source and destination are obstacle vertices. The descriptions we compute enable one processor to obtain the path length of any query pair of vertices in constant time, or O(n/log n) processors to retrieve the shortest path itself in logarithmic time. If the two query points are arbitrary rather than vertices, then one processor takes O(log n) time (instead of constant time) for finding the path length. A number of other related shortest paths problems are solved. The techniques we use involve a fast computation of separator staircases and, most importantly, a scheme for partitioning the obstacles' boundaries into families in a way that ensures that the resulting path length matrices have a monotonicity property that is apparently absent before applying our partitioning scheme.

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Efficient low-contention parallel algorithms 94

Efficient low-contention parallel algorithms

引用

proceedings of the 6th annual acm symposium on parallel algorithms and architectures

作者： Gibbons, Philip B. Matias, Yossi Ramachandran, Vijaya AT&T Bell Laboratories 600 Mountain Ave. Murray Hill NJ Dept. of Computer Sciences University of Texas Austin TX

ISBN: (纸本)9780897916714

The queue-read, queue-write (QRQW) PRAM model [GMR94] permits concurrent reading and writing, but at a cost proportional to the number of readers/writers to a memory location in a given step. The QRQW model reflects the contention properties of most parallel machines more accurately than either the well-studied CRCW or EREW models: the CRCW model does not adequately penalize algorithms with high contention to shared memory locations, while the EREW model is too strict in its insistence on zero contention at each step. Of primary practical and theoretical interest, then, is the design of fast and efficient QRQW algorithms for problems for which all previous algorithms either suffer from high contention, fail to be fast, or fail to be *** paper describes low-contention, fast, work-optimal QRQW PRAM algorithms for the fundamental problems of finding a random permutation, parallel hashing, load balancing, and sorting. There is no known fast, work-optimal EREW algorithm known for finding a random permutation or for parallel hashing. For load balancing, we improve upon the EREW result whenever the ratio of the maximum to the average load is not too large. We show that the logarithmic dependence of the QRQW running time on this ratio is inherent by providing a matching lower *** demonstrate the performance advantage of a QRQW random permutation algorithm, compared with the popular EREW algorithm, by implementing and running both algorithms on the MasPar ***, we extend the work-time framework for the design of parallel algorithms to account for contention, and relate it to the QRQW PRAM model. We use our QRQW load balancing algorithm, as well as the QRQW linear compaction algorithm in [GMR94], to provide automatic tools for processor allocation—an issue that needs to be handled when translating an algorithm from its work-time presentation into the explicit PRAM description.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel solutions of linear algebraic circuits

Annual ACM Symposium on Parallel Algorithms and Architecture...

引用

annual acm symposium on parallel algorithms and architectures 1999年 212-221页

作者： Ben-Asher, Yosi Haber, Gady Haifa Univ Haifa Israel

The problem of obtaining efficient solutions for parallel evaluation of linear algebraic circuits (LAC) is considered. The parallelism is obtained through matrix multiplications. A CREW PRAM algorithm is used, in which, during execution, propagates computed values into future matrix products, and uses a special scheduling of the matrix multiplications to reduce constant factors of the execution times.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Experiences with parallel N-body simulation 94

Experiences with parallel N-body simulation

引用

proceedings of the 6th annual acm symposium on parallel algorithms and architectures

作者： Liu, Pangfeng Bhatt, Sandeep N. DIMACS Rutgers University Piscataway NJ Bell Communications Research Morristown NJ

ISBN: (纸本)9780897916714

This paper describes our experiences developing high-performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the communication requirements are irregular and adaptive. Together with the need to balance the computational work-load among processors, these issues pose interesting challenges and tradeoffs for high-performance *** implementation was guided by the need to keep solutions simple and general. We use a technique for implicitly representing a dynamic global tree across multiple processors which substantially reduces the programming complexity as well as the performance overheads of distributed memory architectures. The contributions include methods to vectorize the computation and minimize communication time which are theoretically and experimentally *** code has been tested by varying the number and distribution of bodies on different configurations of the Connection Machine CM-5. The overall performance on instances with 10 million bodies is typically over 30% of the peak machine rate. Preliminary timings compare favorably with other approaches.

关键词： Memory architecture

来源：评论

学校读者我要写书评

暂无评论

On the benefit of supporting virtual channels in wormhole routers 96

On the benefit of supporting virtual channels in wormhole ro...

引用

proceedings of the 1996 8th annual acm symposium on parallel algorithms and architectures

作者： Cole, Richard J. Maggs, Bruce M. Sitaraman, Ramesh K. New York Univ New York NY United States

ISBN: (纸本)9780897918091

This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We show that in any network in which each physical channel can emulate up to Q virtual channels, it is possible to route any set of L-bit messages whose paths have congestion C and dilation D in (L+D)C(D log D)1/Q2O(log*(C/D)) bit steps. We also prove a nearly matching lower bound, i.e., for any values of C, D, Q, and L, where C, D≥Q+1 and L = (1+Ω(1))D, we show how to construct a network and a set of L-bit messages whose paths have congestion C and dilation D that require Ω(LCD1/Q) bit steps to route. These upper and lower bounds imply that increasing the queuing capacity Q of each physical channel can speed up a wormhole routing algorithm by a superlinear factor. The results can be translated to the scenario in which each physical channel can transmit B bits simultaneously, and can queue bits from B different messages. In this case, the bounds are (L+D)C(D log D)1/B2O(log* (C/D))/B and Ω(LCD1/B/B), respectively. We also present a simple randomized wormhole routing algorithm for the butterfly network. The algorithm routes a q-relation on the inputs and outputs of an n-input butterfly in O(LQ(q+log n)(log1/Q n) log log(qn)) bit-steps. We present a nearly-matching lower bound that holds for a broad class of algorithms.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：