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

Fifteenth annual acm symposium on parallelism in algorithms and architectures

作者： Naor, Moni Wieder, Udi Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9781581136616

We propose a new approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to processors. We demonstrate the power of these design rules by suggesting two new architectures, one for DHT (Distributed Hash Table) and the other for dynamic expander networks. The DHT network, which we call Distance Halving allows logarithmic routing and load, while preserving constant degrees. It offers an optimal tradeoff between the degree and the dilation in the sense that degree d guarantees a dilation of O(logdn). Another advantage over previous constructions is its relative simplicity. A major new contribution of this construction is a dynamic caching technique that maintains low load and storage even under the occurrence of hot spots. Our second construction builds a network that is guaranteed to be an expander. The resulting topologies are simple to maintain and implement. Their simplicity makes it easy to modify and add protocols. A small variation yields a DHT which is robust against random faults. Finally we show that, using our approach, it is possible to construct any family of constant degree graphs in a dynamic environment, though with worst parameters. Therefore we expect that more distributed data structures could be designed and implemented in a dynamic environment.

关键词： Telecommunication networks

来源：评论

学校读者我要写书评

暂无评论

The effect of communication costs in solid-state quantum computing architectures 03

The effect of communication costs in solid-state quantum com...

引用

Fifteenth annual acm symposium on parallelism in algorithms and architectures

作者： Copsey, Dean Oskin, Mark Metodiev, Tzvetan Chong, Frederic T. Chuang, Isaac Kubiatowicz, John University of Washington Seattle WA United States University of California at Davis Davis CA United States University of California Berkeley Berkeley CA United States

ISBN: (纸本)9781581136616

Quantum computation has become an intriguing technology with which to attack difficult problems and to enhance system security. Quantum algorithms, however, have been analyzed under idealized assumptions without important physical constraints in mind. In this paper, we analyze two key constraints: the short spatial distance of quantum interactions and the short temporal life of quantum data. In particular, quantum computations must make use of extremely robust error correction techniques to extend the life of quantum data. We present optimized spatial layouts of quantum error correction circuits for quantum bits embedded in silicon. We analyze the complexity of error correction under the constraint that interaction between these bits is near neighbor and data must be propagated via swap operations from one part of the circuit to another. We discover two interesting results from our quantum layouts. First, the recursive nature of quantum error correction circuits requires a additional communication technique more powerful than near-neighbor swaps - too much error accumulates if we attempt to swap over long distances. We show that quantum teleportation can be used to implement recursive structures. We also show that the reliability of the quantum swap operation is the limiting factor in solid-state quantum computation.

关键词： Fault tolerant computer systems

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel selection 03

引用

Proceedings of the fourteenth annual acm-SIAM symposium on Discrete algorithms

作者： Yijie Han University of Missouri at Kansas City Kansas City MO

We present an optimal parallel selection algorithm on the EREW PRAM. This algorithm runs in O(log n) time with n/log n processors. This complexity matches the known lower bound for parallel selection on the EREW PRAM ... 详细信息

ISBN: (纸本)9780898715385

关键词： selection EREW PRAM parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Two techniques for reconciling algorithm parallelism with memory constraints (extended abstract)

Two techniques for reconciling algorithm parallelism with me...

引用

fourteenth annual acm symposium on parallel algorithms and architectures

作者： Vishkin, Uzi University of Maryland College Park MD United States

The utility of algorithm parallelism for coping with increased processor to memory latencies using "latency hiding" is part of the folklore of parallel computing. Latency hiding techniques increase the traffic to memory and therefore may "hit another wall": limited bandwidth to memory. The current paper attempts to stimulate research in the following general direction: show that algorithm parallelism need not conflict with limited bandwidth. A general technique for using parallel algorithms to enhance serial implementation in the face of processor-memory latency problems is revisited. Two techniques for alleviating memory bandwidth constraints are presented. Both techniques can be incorporated in a compiler. There is often considerable parallelism in many of the algorithms which are known as useful serial algorithms. Interestingly enough, all the examples provided for the use of the two techniques come from such serial algorithms.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

A lightweight idempotent messaging protocol for faulty networks 02

A lightweight idempotent messaging protocol for faulty netwo...

引用

fourteenth annual acm symposium on parallel algorithms and architectures

作者： Brown, Jeremy Grossman, J.P. Knight, Tom A.I. Laboratory M.I.T. 200 Technology Square Cambridge MA 02141 United States

ISBN: (纸本)9781581135299

As parallel machines scale to one million nodes and beyond, it becomes increasingly difficult to build a reliable network that is able to guarantee packet delivery. Eventually large systems will need to employ fault-tolerant messaging protocols that afford correct execution in the presence of a lossy network. In this paper we present a lightweight protocol that preserves message idempotence and is easy to implement in hardware. We identify the requirements for a correct implementation of the protocol. Experiments are performed in simulation to determine implementation parameters that optimize performance. We find that an aggressive implementation on a fat tree network results in a slowdown of less than 2x compared to buffered wormhole routing on a fault-free network.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Optimal tiling for the RNA base pairing problem

Optimal tiling for the RNA base pairing problem

引用

fourteenth annual acm symposium on parallel algorithms and architectures

作者： Almeida, Francisco Andonov, Rumen Gonzales, Daniel D.E.I.O.C. La Laguna Spain INRIA Rennes France

Dynamic programming is an important combinatorial optimization technique that has been widely used in various fields such as control theory, operations research, computational biology and computer science. Many authors have described parallel dynamic programming algorithms for the family of multistage problems. More scarce is the literature for the more general class of problems where dependences appear between non-consecutive stages. Among the important problems falling in this class is the RNA base pairing problem. In this study we propose a new parallel scheme for a large class of recurrences with triangular iteration space and nonuniform dependences that includes the RNA base pairing problem. We derive two different instances of this scheme that correspond to an horizontal and a vertical traverse of the iteration domain. We develop and extend the tiling approach for this particular class. We formulate and analytically solve the optimization problem determining the tile size that minimizes the total execution time of the tiled program on a distributed memory parallel machine. Our analyze is based on the BSP model, which assures the portability of the obtained results. The computational experiments carried out on the CRAY T3E behave according to the predictions of our theoretical model.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel dynamic programming for solving the string editing problem on a CGM/BSP

Parallel dynamic programming for solving the string editing ...

引用

fourteenth annual acm symposium on parallel algorithms and architectures

作者： Alves, C.E.R. Cáceres, E.N. Dehne, F. FTCE Universidade São Judas Tadeu São Paulo SP Brazil Universidade Federal de Mato Grosso do Sul Campo Grande MS Brazil School of Computer Science Carleton University Ottawa Ont. K1S 5B6 Canada

In this paper we present a coarse-grained parallel algorithm for solving the string edit distance problem for a string A and all substrings of a string C. Our method is based on a novel CGM/BSP parallel dynamic programming technique for computing all highest scoring paths in a weighted grid graph. The algorithm requires log p rounds/supersteps and O(p/n2 log m) local computation, where p is the number of processors, p2 ≤ m ≤ n. To our knowledge, this is the first efficient CGM/BSP algorithm for the alignment of all substrings of C with A. Furthermore, the CGM/BSP parallel dynamic programming technique presented is of interest in its own right and we expect it to lead to other parallel dynamic programming methods for the CGM/BSP.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploiting flexibly assignable work to improve load balance 02

Exploiting flexibly assignable work to improve load balance

引用

fourteenth annual acm symposium on parallel algorithms and architectures

作者： Pinar, Ali Hendrickson, Bruce NERSC Lawrence Berkeley National Lab. Berkeley CA 94720 United States Parallel Computing Sciences Dept. Sandia National Laboratories Albuquerque NM 87185-1110 United States

ISBN: (纸本)9781581135299

In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with log WT and |P| probe calls, where WT and |P|, respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem, and formulate it as a linearly constrained optimization problem, i.e., min Ax∞, s.t. Bx = d. To avoid solving an intractable ∞-norm optimization problem, we show that in this case minimizing the 2-norm is sufficient to minimize the ∞-norm, which reduces the problem to the well-studied linearly-constrained least squares problem. The continuous version of the problem has the advantage of being easily amenable to parallelization.

关键词： algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel scheduling problems in next generation wireless networks 02

Parallel scheduling problems in next generation wireless net...

引用

fourteenth annual acm symposium on parallel algorithms and architectures

作者： Becchetti, L. Diggavi, S. Leonardi, S. Marchetti-Spaccamela, A. Muthukrishnan, S. Nandagopal, T. Vitaletti, A. Universita di Roma La Sapienza Rome Italy AT and T Shannon Labs Florham Park NJ United States University of Illinois Urbana-Champaign IL United States

ISBN: (纸本)9781581135299

Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform on experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.

关键词： Wireless telecommunication systems

来源：评论

学校读者我要写书评

暂无评论

On a scheme for parallel sorting on heterogeneous clusters

引用

FUTURE GENERATION COMPUTER SYSTEMS 2002年第3期18卷 353-372页

作者： Cérin, C Gaudiot, JL Univ So Calif Los Angeles CA 90089 USA Univ Picardie Jules Verne Laria F-80000 Amiens France

We discuss parallel sorting algorithms and their implementations suitable for cluster architectures in order to optimize cluster resources. We focus on the time spent in computation and the load balancing properties when processors are running at different speeds, i.e. correlated by a multiplicative constant factor (our weak definition of heterogeneous platform). One scheme is under study: parallel sorting by sampling (either regular sampling technique introduced by Shi and Schaeffer [J. parallel Distrib. Comput. 14 (4) (1992) 361] or the over-partitioning scheme introduced by Li and Seveik [parallel sorting by over-partitioning, in: Proceedings of the Sixth annual symposium on parallel algorithms and architectures, acm Press, New York, June 1994]). What is important in the paper is mainly the load balance factor and not necessary the execution time. It is clear that improved load balance leads to improved execution titre. The results presented in the paper demonstrate that load balancing for the case of computers with heterogeneous processing capacity is more challenging than for the homogeneous case. The survey, through the sorting case study, allow us to identify some algorithmic issues and software challenges to master heterogeneous cluster platforms in order to better utilize theta: data decomposition techniques, scheduling and load balancing methods. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： performance evaluation and modeling of parallel integer sorting algorithms sorting by regular sampling and by over-partitioning data distribution load balancing strategies BSP programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：