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

Proceedings of the 1998 10th annual acm symposium on parallel algorithms and architectures, SPAA

作者： Laing, A.K. Cypher, R. The Johns Hopkins Univ Baltimore MD United States

ISBN: (纸本)9780897919890

In this paper we consider the problem of deadlock-free routing in arbitrary parallel and distributed computers. We focus on asynchronous routing algorithms which continuously receive new packets to route and which do not discard packets that encounter congestion. Specifically, we examine what we call the deadlock-free routing (DFR) problem. The input to the DFR problem consists of an arbitrary network and an arbitrary set of paths in the network. The output consists of a routing algorithm, which is a list of the buffers used along each of the paths. The routing algorithm is required to be free from deadlock and the goal is to minimize the number of buffers required in any one node. We study the DFR problem by converting it into an equivalent problem which we call the flattest common supersequence (FCS) problem. The input to the FCS problem consists of a set of sequences and the output consists of a single sequence that contains all of the input sequences as (possibly non-contiguous) subsequences. The goal of the FCS problem is to minimize the maximum frequency of any symbol in the output sequence. We present three main results. First, we prove that the decision version of the FCS problem is NP-complete, and has no polynomial-time approximation scheme unless P = NP. Next, we propose and experimentally evaluate a range of heuristics for FCS. Our experimental results show that one of these heuristics performs very well over a wide range of inputs. Lastly, we prove that this heuristic is in fact optimal for certain restricted classes of inputs.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A constant time optimal parallel algorithm for two-dimensional pattern matching

引用

SIAM JOURNAL ON COMPUTING 1998年第3期27卷 668-681页

作者： Crochemore, M Gasieniec, L Hariharan, R Muthukrishnan, S Rytter, W Univ Marne La Vallee Inst Gaspard Monge F-93160 Noisy Le Grand France Univ Warsaw Inst Informat PL-02097 Warszawa Poland Max Planck Inst Informat Saarbrucken Germany NYU Courant Inst New York NY USA AT&T Bell Labs Murray Hill NJ 07974 USA

We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m(h) x m(w) in a text array of size n(h) x n(w) in the concurrent-read-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n(h) x n(w)) work, following preprocessing of the pattern. This improves the previous best bound of O(loglogm) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th annual acm symposium on parallel algorithms and architectures, acm, New York, 1993, pp. 79-85], following preprocessing of the pattern, where m = max {m(h),m(w)}. The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(loglogm) time and O(m(h) x m(w)) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

关键词： pattern matching PRAM two-dimensional witnesses duelling periodicity

来源：评论

学校读者我要写书评

暂无评论

Matching nuts and bolts in O(n log n) time

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1998年第3期11卷 347-372页

作者： Komlos, J Ma, Y Szemeredi, E Rutgers State Univ Dept Math Piscataway NJ 08855 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA MIT Cambridge MA 02139 USA Rutgers State Univ Dept Comp Sci Piscataway NJ 08855 USA Univ Gesamthsch Paderborn D-4790 Paderborn Germany

Given a set of n nuts of distinct widths and a set of n bolts such that each nut corresponds to a unique bolt of the same width, how should we match every nut with its corresponding bolt by comparing nuts with bolts? (No comparison is allowed between two nuts or two bolts.) The problem can be naturally viewed as a variant of the classic sorting problem as follows. Given two lists of n numbers each such that one list is a permutation of the other, how should we sort the lists by comparisons only between numbers in different lists? We give an O(n log n)-time deterministic algorithm for the problem. This is optimal up to a constant factor and answers an open question posed by Alon et al. [Proceedings of the 5th annual acm-SIAM symposium on Discrete algorithms, 1994, pp. 690-696]. Moreover, when copies of nuts and bolts are allowed, our algorithm runs in optimal O(log n) time on n processors in Valiant's parallel comparison tree model. Our algorithm is based on the AKS sorting algorithm with substantial modifications.

关键词： sorting matching selection parallel computation AKS sorting algorithm random graphs

来源：评论

学校读者我要写书评

暂无评论

Asynchronous shared memory search structures

引用

THEORY OF COMPUTING SYSTEMS 1998年第4期31卷 377-401页

作者： Adler, M Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Int Comp Sci Inst Berkeley CA 94704 USA

We study the problem of storing an ordered E;et On an asynchronous shared memory parallel computer. We examine the case where we want to perform successor (least upper bound) queries efficiently on the set members that are stored. We also examine the case where processors insert and delete members of the set. Due to asynchrony, we require processors to perform queries and to maintain the structure independently. Although several such structures have been proposed, the analysis of these structures has been very limited. We here ut;e the recently proposed QRQW PRAM model to provide upper and lower bounds on the performance of such data structures. In the asynchronous QRQW PRAM, the problem of processors concurrently and independently searching a shared data structure is very similar to the problem of routing packets through a network. Using this as a guide, we introduce the Search-Butterfly, a search structure that combines the efficient packet routing properties of the butterfly graph with the efficient search structure properties of the B-Tree. We analyze the behavior of the Search-Butterfly when the following operations are performed: arbitrary searches, random searches,and random searches, insertions, and deletions. We also provide lower bounds that show that the results are within a factor of O (log n) of optimal where n is the number of keys;in the structure. When the searches are random, the results are within a constant factor of optimal. Many of the proofs are derived from closely related results for packet routing. Others are of independent interest, most notably a method of adding queues to any network belonging to a large class of queuing networks with non-Markovian routing in a manner that allows us to bound the delay experienced by packets in the augmented network.

关键词： COMPUTER storage devices parallel computers ASYNCHRONOUS circuits

来源：评论

学校读者我要写书评

暂无评论

Minimizing stall time in single and parallel disk systems 98

Minimizing stall time in single and parallel disk systems

引用

Proceedings of the 1998 30th annual acm symposium on Theory of Computing

作者： Albers, Susanne Garg, Naveen Leonardi, Stefano Max-Planck-Inst fuer Informatik Saarbruecken Germany

ISBN: (纸本)9780897919623

We study integrated prefetching and caching problems following the work of Cao et. al. and Kimbrel and Karlin. Cao et. al. and Kimbrel and Karlin gave approximation algorithms for minimizing the total elapsed time in single and parallel disk settings. The total elapsed time is the sum of the processor stall times and the length of the request sequence to be served. We show that an optimum prefetching/caching schedule for a single disk problem can be computed in polynomial time, thereby settling an open question by Kimbrel and Karlin. For the parallel disk problem we give an approximation algorithm for minimizing stall time. Stall time is an important and harder to approximate measure for this problem. All of our algorithms are based on a new approach which involves formulating the prefetching/caching problems as integer programs.

关键词： Magnetic disk storage

来源：评论

学校读者我要写书评

暂无评论

Clustering and reassignment-based mapping strategy for message-passing architectures 1

Clustering and reassignment-based mapping strategy for messa...

引用

1st Merged International parallel Processing symposium/symposium on parallel and Distributed Processing (IPPS/SPDP 1998)

作者： Senar, MA Ripoll, A Cortes, A Luque, E Univ Autonoma Barcelona Dept Informat Unitat Arquitect Ordinadors & Sistemes Operatius Bellaterra 08193 Barcelona Spain

ISBN: (纸本)0818684038

A fundamental issue affecting the performance of a parallel program is the assignment of tasks to processors in order to get the minimum completion rime. In this paper, we present a compilation-time two-stage mapping strategy (denoted as CREMA) used for mapping arbitrary programs (modeled as TIG graphs) onto message-passing parallel systems with any architecture. In contrast to most of the other approaches found in the literature, CREMA is not tied to any particular architecture or any specific algorithm. The first stage is based on task clustering and task reassignment algorithms that contract the original task graph. The second stage takes the contracted graph and tries to successfully match the physical properties of the target system. It has been evaluated for a wide range of bath regular and irregular graphs that correspond to some well-known real applications. The results show that CREMA provides a good trade-off between mapping quality and computational complexity.

关键词： mapping problem task allocation task assignment graph partitioning clustering Heuristics

来源：评论

学校读者我要写书评

暂无评论

Sorting in linear time?

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1998年第1期57卷 74-93页

作者： Andersson, A Hagerup, T Nilsson, S Raman, R Goethe Univ Frankfurt Fachbereich Informat D-60054 Frankfurt Germany Lund Univ Dept Comp Sci S-22100 Lund Sweden Aalto Univ Dept Comp Sci FIN-02150 Espoo Finland Kings Coll London Dept Comp Sci London WC2R 2LS England Max Planck Inst Informat Saarbrucken Germany

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 ... 2(w)-1 in O(n log log n) time for arbitrary w greater than or equal to log n, a significant improvement over the bound of O(n root log n) achieved by the fusion trees of Fredman and Willard. Provided that w greater than or equal to (log n)(2+epsilon) for some fixed epsilon> 0. the sorting can even be accomplished in linear expected time with a randomized algorithm. Both of our algorithms parallelize without loss on a unit-cost PRAM with a word length of w bits. The first one yields an algorithm that uses O(log n) time and O(n log log n) operations on a deterministic CRCW PRAM. The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w greater than or equal to (log n)(2+epsilon) for some fixed epsilon > 0. Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting of multiple-precision integers represented in several words. (C) 1998 Academic Press.

关键词： parallel list ranking Algorithm Bounds Machines Pram parallel random access machine model concurrency theory randomized algorithms deterministic Bound algorithms machinery Greater than or equal to machine word length sorting programs

来源：评论

学校读者我要写书评

暂无评论

Aggressive dynamic execution of multimedia kernel traces 1

Aggressive dynamic execution of multimedia kernel traces

引用

1st Merged International parallel Processing symposium/symposium on parallel and Distributed Processing (IPPS/SPDP 1998)

作者： Bishop, B Owens, R Irwin, MJ Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA

ISBN: (纸本)0818684038

There has been relatively little analytical work on processor optimizations for multimedia applications. With the introduction of MMX by Intel, it is clear that this is an area of increasing importance. Building on previous work [4, 5, 6, 7, 13, 14], we propose optimizations for multimedia architectures that support independent parallel execution of instructions within dynamically assembled traces, resulting in dramatic performance improvements. Specifically, we propose simplified instruction scheduling and register renaming algorithms due to constraints on trace formation. In addition, we suggest specific instruction pool and trace cache parameters. We constructed a simulator in order to measure the benefits of these processor optimizations for multimedia applications. The simulated machine, which could fetch/decode 2 instructions per cycle, performed better than a superscalar machine that could fetch/decode 8 instructions per cycle. Execution rates as high as 7.3 instructions per cycle were achieved for the benchmarks simulated, assuming 16 instructions per trace.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

parallel tree building on a range of shared address space multiprocessors: algorithms and application performance 1

Parallel tree building on a range of shared address space mu...

引用

1st Merged International parallel Processing symposium/symposium on parallel and Distributed Processing (IPPS/SPDP 1998)

作者： Shan, HZ Singh, JP Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

ISBN: (纸本)0818684038

irregular particle-based applications that use trees, far example hierarchical N-body applications, are important consumers of multiprocessor cycles, and are argued to benefit greatly in programming ease from a coherent shared address space programming model. As more and more supercomputing platforms that can support different programming models become available to users, from tightly-coupled hardware-coherent machines to clusters of workstations or SMPs, to truly deliver on its ease of programing advantages to application users it is important that the shared address space model nor only perform and scale well in the rightly-coupled case but also port well in performance across the range of platforms (as the message passing model can). For tree-based N-body applications, this is currently not true: While the actual computation of interactions ports well, the parallel tree building phase can become a severe bottleneck on coherent shared address space platforms, in particular an platforms with less aggressive, commodity-oriented communication architectures (even though it rakes less than 3 percent of the time in most sequential executions). We therefore investigate the performance of five parallel tree building methods in the context of a complete galaxy simulation on four very different platforms that support this programming model: an SGI Origin2000 (an aggressive hardware cache-coherent machine with physically distributed memory), an SGI Challenge bits-based shared memory multiprocessor art Intel Paragon running a shared virtual memory protocol in software at page granularity, and a Wisconsin Typhoon-zero in which the granularity of coherence can be varied using hardware support but the protocol runs in software (in the last case using both a page-based and a fine-grained protocol). We find that the algorithms used successfully and widely distributed so far for the first two platforms cause overall application performance to be very poor on the latter two commodit

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

A framework for simple sorting algorithms on parallel disk systems (extended abstract) 98

A framework for simple sorting algorithms on parallel disk s...

引用

Proceedings of the tenth annual acm symposium on parallel algorithms and architectures

作者： Sanguthevar Rajasekaran Dept. of CISE University of Florida Gainesville FL

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：