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

proceedings of the fourteenth annual acm symposium on parallel algorithms and architectures

作者： C. E. R. Alves E. N. Cáceres F. Dehne FTCE - Universidade São São Paulo Brazil Universidade Federal de Mato Campo Grande Brazil Carleton University Ottawa Canada

ISBN: (纸本)9781581135299

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(\fracn^2p\log m) local computation, where $p$ is the number of processors, p^2 \leq m \leq 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.

关键词： BSP string editing parallel algorithms dynamic programming CGM

来源：评论

学校读者我要写书评

暂无评论

Thirteen annual acm symposium on parallel algorithms and architectures

Thirteen annual ACM symposium on parallel algorithms and arc...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

The proceedings contains 48 papers from Thirteen annual acm symposium on parallel algorithms and architectures. Topics discussed include: compact routing schemes;simple on-line algorithms for the maximum disjoint paths problem;competitive buffer management for shared-memory switches;attack propagation in networks;computational power of pipelined memory hierarchies;and a data tracking scheme for general networks.

关键词： Routers

来源：评论

学校读者我要写书评

暂无评论

Statistical scalability analysis of communication operations in distributed applications 01

Statistical scalability analysis of communication operations...

引用

8th acm SIGPLAN symposium on the Principles and Practice of parallel Computing

作者： Vetter, JS McCracken, MO Lawrence Livermore Natl Lab Ctr Appl Sci Comp Livermore CA 94551 USA

ISBN: (纸本)9781581133462

Current trends in high performance computing suggest that users will soon have widespread access to clusters of multiprocessors with hundreds, if not thousands, of processors. This unprecedented degree of parallelism will undoubtedly expose scalability limitations in existing applications, where scalability is the ability of a parallel algorithm on a parallel architecture to effectively utilize an increasing number of processors. Users will need precise and automated techniques for detecting the cause of limited scalability. This paper addresses this dilemma. First, we argue that users face numerous challenges in understanding application scalability: managing substantial amounts of experiment data, extracting useful trends from this data, and reconciling performance information with their application's design. second, we propose a solution to automate this data analysis problem by applying fundamental statistical techniques to scalability experiment data. Finally, we evaluate our operational prototype on several applications, and show that statistical techniques offer an effective strategy for assessing application scalability. In particular, we find that non-parametric correlation of the number of tasks to the ratio of the time for communication operations to overall communication time provides a reliable measure for identifying communication operations that scale poorly.

关键词： Scalability Experimental data statistical techniques Consumers Communication Research Automated recording parallel architectures Surgery Multiprocessor High Performance Computing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling best-effort and real-time pipelined applications on time-shared clusters 01

Scheduling best-effort and real-time pipelined applications ...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Zhang, Y. Sivasubramaniam, A. Dept. of Computer Sci./Engineering Pennsylvania State University University Park PA 16802 United States

ISBN: (纸本)9781581134094

Two important emerging trends are influencing the design, implementation and deployment of high performance parallel systems. The first is on the architectural end, where both economic and technological factors are compelling the use of off-the-shelf computing elements (workstations/PCs and networks) to put together high performance systems called clusters. The second is from the user community that is finding an increasing number of applications to benefit from such high performance systems. Apart from the scientific applications that have traditionally needed supercomputing power, a large number of graphics, visualization, database, web service and e-commerce applications have started using clusters because of their high processing and storage requirements. These applications have diverse characteristics and can place different Quality-of-Service (QoS) requirements on the underlying system (low response time, high throughput, high I/O demands, guaranteed response/throughput etc.). Further, clusters run ning such applications need to cater to potentially a large number of users (or other applications) in a time-shared manner. The underlying system needs to accommodate the requirements of each application, while ensuring that they do not interfere with each other. This paper focuses on the CPU resources of a cluster and investigates scheduling mechanisms to meet the responsiveness, throughput and guaranteed service requirements of different applications. Specifically, we propose and evaluate three different scheduling mechanisms. These mechanisms have been drawn from traditional solutions on parallel systems (gang scheduling and dynamic coscheduling), and have been extended to accommodate the new criteria under consideration. These mechanisms have been investigated using detailed simulation and workload models to show their pros and cons for different performance metrics.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Pursuit and evasion on a ring: An infinite hierarchy for parallel real—time systems 01

Pursuit and evasion on a ring: An infinite hierarchy for par...

引用

proceedings of the thirteenth annual acm symposium on parallel algorithms and architectures

作者： Stefan D. Bruda Selim G. Akl Department of Computing and Information Science Queen's University Kingston Ontario K7L 3N6 Canada

No abstract available.

ISBN: (纸本)9781581134094

No abstract available.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Optimal prefetching and caching for parallel I/O sytems 01

Optimal prefetching and caching for parallel I/O sytems

引用

proceedings of the thirteenth annual acm symposium on parallel algorithms and architectures

作者： Mahesh Kallahalla Peter J. Varman Hewlett-Packard Labs 1501 Page Mill Rd. Palo Alto CA Department of ECE Rice University Houston TX

ISBN: (纸本)9781581134094

We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for optimal parallel-disk scheduling. Traditional buffer management algorithms that minimize the number of I/O disk accesses, are substantially suboptimal in a parallel I/O system where multiple I/Os can proceed *** present a new algorithm SUPERVISOR for parallel-disk I/O scheduling. We show that in the off-line case, where apriori knowledge of all the requests is available, SUPERVISOR performs the minimum number of I/Os to service the given I/O requests. This is the first parallel I/O scheduling algorithm that is provably offline optimal. In the on-line case, we study SUPERVISOR in the context of global L-block lookahead, which gives the buffer management algorithm a lookahead consisting of L distinct requests. We show that the competitive ratio of SUPERVISOR, with global L-block lookahead, is Θ(M - L + D), when L ≤ M, and Θ(MD/L), when L > M, where the number of disks is D and buffer size is M.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Computing the arrangement of curve segments: Divide-and-conquer algorithms via sampling

Computing the arrangement of curve segments: Divide-and-conq...

引用

11th annual acm-SIAM symposium on Discrete algorithms

作者： Amato, Nancy M. Goodrich, Michael T. Ramos, Edgar A. Texas A&M Univ College Station United States

We describe two deterministic algorithms for constructing the arrangement determined by a set of (algebraic) curve segments in the plane. They both use a divide-and-conquer approach based on derandomized geometric sampling and achieve the optimal running time O(n log n+k), where n is the number of segments and k is the number of intersections. The first algorithm, a simplified version of one presented in [1], generates a structure of size O(n log log n+k) and its parallel implementation runs in time O(log2 n). The second algorithm is better in that the decomposition of the arrangement constructed has optimal size O(n+k) and it has a parallel implementation in the EREW PRAM model that runs in time O(log3/2 n). The improvements in the second algorithm are achieved by means of an approach that adds some degree of globality to the divide-and-conquer approach based on random sampling. The approach extends previous work by Dehne et al., Deng and Zhu and Kuehn, that use small separators for planar graphs in the design of randomized geometric algorithms for coarse grained multicomputers. The approach simplifies other previous geometric algorithms, and also has the potential of providing efficient deterministic algorithms for the external memory model.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for data placement on parallel disks

Approximation algorithms for data placement on parallel disk...

引用

11th annual acm/SIAM symposium on Discrete algorithms

作者： Golubchik, L Khanna, S Khuller, S Thurimella, R Zhu, A Univ Maryland Dept Comp Sci College Pk MD 20742 USA

ISBN: (纸本)0898714532

We study an optimization problem that arises in the context of data placement in multimedia storage systems. We are given a collection of M multimedia data objects that need to be assigned to a storage system consisting of N disks d(1),d(2)...,d(N). We are also given sets U-1,U-2,...,U-M such that U-i is the set of clients requesting the ith data object. Each disk d(j) is characterized by two parameters, namely, its storage capacity C-j which indicates the maximum number of data objects that may be assigned to it, and a load capacity L-j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data objects on disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system. We study this data placement problem for two natural classes of storage systems, namely, homogeneous and uniform ratio. Our first main result is a tight upper and lower bound on the number of items that can always be packed for any input instance to homogeneous as well as uniform ratio storage systems. We show that an algorithm given in [11] for data placement, achieves this bound. Our second main result is a polynomial time approximation scheme for the data placement problem in homogeneous and uniform ratio storage systems, answering an open question of [11]. Finally, we also study the problem from an empirical perspective.

关键词： Multimedia systems

来源：评论

学校读者我要写书评

暂无评论

Multithreaded algorithms for the Fast Fourier Transform

Annual ACM Symposium on Parallel Algorithms and Architecture...

引用

annual acm symposium on parallel algorithms and architectures 2000年 176-185页

作者： Thulasiraman, Parimala Theobald, Kevin B. Khokhar, Ashfaq A. Gao, Guang R. Univ of Delaware Newark DE United States

In this paper we present fine-grained multithreaded algorithms and implementations for the Fast Fourier Transform (FFT) problem. The FFT problem has been formulated using two distinct approaches based on the dataflow concepts. The first approach, referred to as the receiver-initiated algorithm, realizes the FFT iterations as a parent-child relationship while fully exploiting the underlying parallelism. The second approach, referred to as the sender-initiated algorithm, follows a data-flow model based on the producer-consumer style of programming and can be adopted to different architectural parameters for achieving high performance. The implementations of the proposed algorithms have been carried out on the EARTH (Efficient Architecture for Running THreads) platform. For both the algorithms, we analyze the ratio of remote vs local threads and study its impact on the experimental results. Our implementation results show that for certain block sizes on fixed problem size and machine size, the receiver-initiated approach performs better than the sender-initiated approach. For large number of processors, both the algorithms perform well, yielding execution times of only 10 msec for an input of 16 K data points on a 64 processor machine, assuming each processor running at 140 MHz clock speed.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

A no-busy-wait balanced tree parallel algorithmic paradigm 00

A no-busy-wait balanced tree parallel algorithmic paradigm

引用

proceedings of the twelfth annual acm symposium on parallel algorithms and architectures

作者： Uzi Vishkin University of Maryland

ISBN: (纸本)9781581131857

Suppose that a parallel algorithm can include any number of parallel threads. Each thread can proceed without ever having to busy wait to another thread. A thread can proceed till its termination, but no new threads can be formed. What kind of problems can such restrictive algorithms solve and still be competitive in the total number of operations they perform with the fastest serial algorithm for the same problem?Intrigued by this informal question, we considered one of the most elementary parallel algorithmic paradigms, that of balanced binary trees. The main contribution of this paper is a new balanced (not necessarily binary) tree no-busy-wait paradigm for parallel algorithms; applications of the basic paradigm to two problems are presented: building heaps, and executing parallel tree contraction (assuming a preparatory stage); the latter is known to be applicable to evaluating a family of general arithmetic *** putting things in context, we also discuss our “PRAM-on-chip” vision (actually a small update to it), presented at SPAA98.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：