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

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

作者： Cypher, Robert Konstantinidou, Smaragda IBM Almaden Research Center San Jose CA

ISBN: (纸本)0897915992

This paper considers the problem of creating message-passing protocols for parallel computers. It is assumed that the processors are connected by a network that provides guaranteed delivery of every message, provided that each message delivered by the network is removed by the receiving processor unconditionally and in finite time. Two models of message-passing are considered, namely a selective model in which the receiver specifies the source of the message, and a nonselective model in which the receiver accepts messages from all sources. We consider only space-efficient protocols in which each processor has storage for a constant number of messages and message headers. We present three main results. First, we give a protocol for the selective model that performs a constant amount of communication per send or receive posted by the application. Second, we prove that no such efficient protocol exists for the nonselective model. Third, we present a protocol for the nonselective model that performs a logarithmic amount of communication per send or receive posted by the application. © 1993 acm.

关键词： Message passing

来源：评论

学校读者我要写书评

暂无评论

DREADLOCKS: Efficient Deadlock Detection 08

DREADLOCKS: Efficient Deadlock Detection

引用

20th acm symposium on parallelism in algorithms and architectures

作者： Koskinen, Eric Herlihy, Maurice Brown Univ Dept Comp Sci Providence RI 02912 USA

ISBN: (纸本)9781595939739

We present Dreadlocks. an efficient new shared-memory spin lock that actively detects deadlocks. Instead of spinning on a Boolean value, each thread spins on the lock owner's per-thread digest, a compact representation of a portion of the lock's waits-for graph. Digests can be implemented either as bit vectors (for small numbers of threads) or as Bloom filters (for larger numbers of threads). Updates to digests are propagated dynamically as locks are acquired and released. Dreadlocks can be applied to any spin lock algorithm that allows threads to time out. Experimental results show that Dreadlocks outperform timeouts under many circumstances, and almost never do worse.

关键词： Concurrency parallel programming deadlock deadlock detection bloom filters transactional memory

来源：评论

学校读者我要写书评

暂无评论

Scheduling Threads for Constructive Cache Sharing on CMPs 07

Scheduling Threads for Constructive Cache Sharing on CMPs

引用

19th annual symposium on parallelism in algorithms and architectures

作者： Chen, Shimin Gibbons, Phillip B. Kozuch, Michael Liaskovitis, Vasileios Ailamaki, Anastassia Blelloch, Guy E. Falsafi, Babak Fix, Limor Hardavellas, Nikos Mowry, Todd C. Wilkerson, Chris Intel Res Pittsburgh Pittsburgh PA USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Intel Microproc Res Lab Pittsburgh PA USA

ISBN: (纸本)9781595936677

In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which concurrently scheduled threads share a largely overlapping working set. In this paper, we compare the performance of two state-of-the-art schedulers proposed for fine-grained multithreaded programs: parallel Depth First (PDF), which is specifically designed for constructive cache sharing, and Work Stealing (WS), which is a more traditional design. Our experimental results indicate that PDF scheduling yields a 1.3-1.6X performance improvement relative to WS for several fine-grain parallel benchmarks on projected future CMP configurations;we also repert several issues that may limit the advantage of PDF in certain applications. These results also indicate that PDF more effectively utilizes off-chip bandwidth, making it possible to trade-off on-chip cache for a larger number of cores. Moreover, we find that task granularity plays a key role in cache performance. Therefore;we present an automatic approach for selecting effective grain sizes, based on a new working set profiling algorithm that is an order of magnitude faster than previous approaches. This is the first paper demonstrating the effectiveness of PDF on real benchmarks;providing a direct comparison between PDF and WS;revealing the limiting factors for PDF in practice, and presenting an approach for overcoming these factors.

关键词： Chip Multiprocessors Scheduling algorithms Constructive Cache Sharing parallel Depth First Work Stealing Thread Granularity Working Set Profiling

来源：评论

学校读者我要写书评

暂无评论

Optimal trade-offs between size and slowdown for universal parallel networks

Optimal trade-offs between size and slowdown for universal p...

引用

proceedings of the 7th annual acm symposium on parallel algorithms and architectures, SPAA'95

作者： Meyer auf der Heide, Friedhelm Storch, Martin Wanka, Rolf Univ of Paderborn Paderborn Germany

In this paper, we address the question how efficiently a single constant-degree processor network can simulate the computation of any constant-degree processor network. We show the following lower bound trade-off: If M is an arbitrary constant-degree processor network of size m that can simulate all constant-degree processor networks of size n with slowdown s, then m·s = Ω(n log m). Our trade-off holds for a very general model of simulations. It covers all previously considered models and all known techniques for simulations among networks. For m ≥ n, this improves a previous lower bound by a factor of log log n, proved for a weaker simulation model. For m < n, this is the first non-trivial lower bound for this problem. In this case, this lower bound is asymptotically tight.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

SPAA'11 - proceedings of the 23rd annual symposium on parallelism in algorithms and architectures

SPAA'11 - Proceedings of the 23rd Annual Symposium on Parall...

引用

23rd acm symposium on parallelism in algorithms and architectures, SPAA'11

ISBN: (纸本)9781450307437

The proceedings contain 50 papers. The topics discussed include: graph expansion and communication costs of fast matrix multiplication;near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs;linear-work greedy parallel approximate set cover and variants;optimizing hybrid transactional memory: the importance of nonspeculative operations;parallelism and data movement characterization of contemporary application classes;work-stealing for mixed-mode parallelism by deterministic team-building;full reversal routing as a linear dynamical system;reclaiming the energy of a schedule, models and algorithms;a tight runtime bound for synchronous gathering of autonomous robots with limited visibility;convergence of local communication chain strategies via linear transformations: or how to trade locality for speed;and convergence to equilibrium of logit dynamics for strategic games.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Conflict-free access of arrays in a parallel processor 89

Conflict-free access of arrays in a parallel processor

引用

1st annual acm symposium on parallel algorithms and architectures, SPAA 1989

作者： Lee, D.-L. Wang, Y.H. Department of Computer Science York University North YorkONM3J1P3 Canada

ISBN: (纸本)089791323X

Let T be a collection of data templates of an N × N matrix, T = {row, column, forward diagonal, backward diagonal}. In the context of parallel processing, the question of whether it is possible or not for a parallel processor with N processing elements, N memory modules, and an interconnection network to allow parallel, conflict-free access to any instance of any data templates in T for N = 2n and any n > 1 has been open for a long time. The problem essentially concerns whether there exists any valid skewing scheme that can be realized in terms of interconnection networks. In this paper we will answer this open question by presenting a valid skewing scheme and a simple interconnection network that efficiently implements the skewing scheme in question. © 1989 acm.

关键词： Interconnection networks (circuit switching)

来源：评论

学校读者我要写书评

暂无评论

parallelism in Dynamic Well-Spaced Point Sets 11

Parallelism in Dynamic Well-Spaced Point Sets

引用

23rd annual symposium on parallelism in algorithms and architectures

作者： Acar, Umut A. Cotter, Andrew Hudson, Benoit Tuerkoglu, Duru Max Planck Inst Software Syst Kaiserslautern Germany

ISBN: (纸本)9781450307437

parallel algorithms and dynamic algorithms possess an interesting duality property: compared to sequential algorithms, parallel algorithms improve run-time while preserving work, while dynamic algorithms improve work but typically offer no parallelism.. Although they are often considered separately, parallel and dynamic algorithms employ similar design techniques. They both identify parts of the computation that are independent of each other. This suggests that dynamic algorithms could be parallelized to improve work efficiency while preserving fast parallel run-time. In this paper, we parallelize a dynamic algorithm for well-spaced point sets, an important problem related to mesh refinement in computational geometry. Our parallel dynamic algorithm computes a well-spaced superset of a dynamically changing set of points, allowing arbitrary dynamic modifications to the input set. On an EREW PRAM, our algorithm processes batches of k modifications such as insertions and deletions in O(k log Delta) total work and in O(log Delta) parallel time using k processors, where Delta is the geometric spread of the data, while ensuring that the output is always within a constant factor of the optimal size. EREW PRAM model is quite different from actual hardware such as modern multiprocessors. We therefore describe techniques for implementing our algorithm on modern multi-core computers and provide a prototype implementation. Our empirical evaluation shows that our algorithm can be practical, yielding a large degree of parallelism and good speedups.

关键词： parallel batch dynamic updates multithreading voronoi diagrams well-spaced point sets self-adjusting computation mesh refinement

来源：评论

学校读者我要写书评

暂无评论

Efficient automatic simulation of parallel computation on networks of workstations

引用

DISCRETE APPLIED MATHEMATICS 2006年第10期154卷 1500-1509页

作者： Kaklamanis, Christos Krizanc, Danny Montangero, Manuela Persiano, Giuseppe Univ Modena & Reggio Emilia Dipartimento Ingn Informaz I-41100 Modena Italy Univ Patras Inst Comp Technol GR-26500 Patras Greece Univ Patras Dept Comp Engn & Informat GR-26500 Patras Greece Wesleyan Univ Dept Math & Comp Sci Middletown CT 06459 USA Univ Salerno Dipartimento Informat & Applicaz I-84081 Baronissi Italy

Andrews et al. [Automatic method for hiding latency in high bandwidth networks, in: proceedings of the acm symposium on Theory of Computing, 1996, pp. 257-265;Improved methods for hiding latency in high bandwidth networks, in: proceedings of the Eighth annual acm symposium on parallel algorithms and architectures, 1996, pp. 52-61] introduced a number of techniques for automatically hiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identical in computational power to those of the guest network being simulated. They further assume that the links of the host are able to pipeline messages, i.e., they are able to deliver P packets in time O(P + d) where d is the delay on the link. In this paper we examine the effect of eliminating one or both of these assumptions. In particular, we provide an efficient simulation of a linear array of homogeneous processors connected by unit-delay links on a linear array of heterogeneous processors connected by links with arbitrary delay. We show that the slowdown achieved by our simulation is optimal. We then consider the case of simulating cliques by cliques;i.e., a clique of heterogeneous processors with arbitrary delay links is used to simulate a clique of homogeneous processors with unit delay links. We reduce the slowdown from the obvious bound of the maximum delay link to the average of the link delays. In the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining. The main motivation of our results (as was the case with Andrews et al.) is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a network of workstations (NOW). In such a setting it is unlikely that the links provided by the NOW will support pipelining and it is quite probab

关键词： parallel computation distributed computation automatic simulation

来源：评论

学校读者我要写书评

暂无评论

Space-efficient representations of shared data for parallel computers 90

Space-efficient representations of shared data for parallel ...

引用

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

作者： Herley, Kieran T. Cornell Univ Itaca NY United States

ISBN: (纸本)0897913701

The problem of representing a set U = {u1, ..., um} of read-write variables on an n-node distributed memory parallel computer is considered. It is shown that U can be represented among the n nodes of a variant of the mesh-of-trees using O((m/n)polylog(m/n)) storage per node such that any n-tuple of variables may be accessed in O(log n(log log n)2) time in the worst case for m polynomial in n.

关键词： Computer systems, Digital

来源：评论

学校读者我要写书评

暂无评论

Fast parallel matching in expander graphs 93

Fast parallel matching in expander graphs

引用

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

作者： Kelson, Pierre Univ. of British Columbia Vancouver B.C. Canada

Let iT be a bipartite graph with bipartition (A, B) where \A\-n and every subset X of A with at most a n elements has at least b\X\ neighbors (o 1). We consider the problem of computing a matching from a given subset... 详细信息

ISBN: (纸本)0897915992

Let iT be a bipartite graph with bipartition (A, B) where \A\-n and every subset X of A with at most a n elements has at least b\X\ neighbors (o < 1,6 > 1). We consider the problem of computing a matching from a given subset X A of size at most a n into B. By Hall's theorem such a matching does indeed exist. We propose two algorithms for this problem. The first algorithm is in NC for b > d' for a constant e > 0;here d denotes the maximum degree of a vertex in A. The second algorithm uses randomization and computes a matching for X provided b = Q(diogd). It terminates in 0(log n) steps for constant d and in polylog(n) time for d = O(polylog(n)) (with high probability). This algorithm is a local algorithm in the sense that the vertices in the graph establish the matching themselves in an online fashion. Both algorithms have applications to local and global routing in communication networks. In particular our results improve a construction of a self-routing nonblocking network by Arora, Leighton, and Maggs. © 1993 acm.

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：