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

36th acm symposium on parallelism in algorithms and architectures (spaa)

作者： Sitchinava, Nodari Svenning, Rolf Univ Hawaii Manoa Honolulu HI 96822 USA Aarhus Univ Aarhus Denmark

ISBN: (纸本)9798400704161

We present a thorough investigation of the All Nearest Smaller Values (ANSV) problem from a practical perspective. the ANSV problem is defined as follows: given an array A consisting of n values, for each entry A(i) compute the largest index l < i and the smallest index r > i such that A(i) > A(l) and A(i) > A(r), i.e., the indices of the nearest smaller values to the left and to the right of A(i). the ANSV problem was solved by Berkman, Schieber, and Vishkin [J. algorithms, 1993] in the PRAM model. their solution in the CREW PRAM model, which we will refer to as the BSV algorithm, achieves optimal O(n) work and O(log n) span. Until now, the BSV algorithm has been perceived as too complicated for practical use, and we are not aware of any publicly available implementations. Instead, the best existing practical solution to the ANSV problem is the implementation by Shun and Zhao presented at DCC'13. they implemented a simpler O(n log n)-work algorithm with an additional heuristic first proposed by Blelloch and Shun at ALENEX'11. We refer to this implementation as the BSZ algorithm. In this paper, we implement the original BSV algorithm and demonstrate its practical efficiency. Despite its perceived complexity, our results show that its performance is comparable to the BSZ algorithm. We also present the first theoretical analysis of the heuristic implemented in the BSZ algorithm and show that it provides a tunable trade-off between optimal work and optimal span. In particular, we show that it achieves O(n(1 + log n/k)) work and O(k(1 + log n/k)) span, for any integer parameter 1 <= k <= n. thus, for k = theta(log n), the BSZ algorithm can be made to be work-optimal, albeit at the expense of increased span compared to BSV. Our discussion includes a detailed examination of different input types, particularly highlighting that for random inputs, the low expected distance between values and their nearest smaller values renders simple algorithms efficient. Finally, we analy

关键词： Algorithm analysis parallel algorithms external memory PRAM algorithm engineering all nearest smaller values problem ANSV

来源：评论

学校读者我要写书评

暂无评论

Checkpoints and Continuations Instead of Nested Transactions 08

Checkpoints and Continuations Instead of Nested Transactions

引用

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 a mechanism for partially aborting transactions through the use of data structure checkpoints and control-flow continuations. In particular, we show that boosted transactions [9] already have built-in restoration points and afford a simple, efficient implementation. Our mechanism is far simpler than previous work, which relied on complex nesting schemes to establish checkpoints. We demonstrate syntactic advantages and we quantify the overhead of checkpoints and explore several examples, illustrating the utility of partially aborting transactions. We additionally present a novel queue-based spin lock which allows threads to timeout and differ in priority. Unlike the known lock due to Craig [5], our lock is more efficient for priority schemes of few levels.

关键词： Concurrency parallel programming transactional memory boosting checkpoints continuations

来源：评论

学校读者我要写书评

暂无评论

Conflict-Free Coloring for Rectangle Ranges Using O(n^.382) Colors 07

Conflict-Free Coloring for Rectangle Ranges Using <i>O</i>(<...

引用

19th annual symposium on parallelism in algorithms and architectures

作者： Ajwani, Deepak Elbassioni, Khaled Govindarajan, Sathish Ray, Saurabh Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9781595936677

Given a set of points P subset of R-2, a conflict free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each non-empty axis-parallel rectangle T in the plane contains a point whose color is distinct from all other points in P boolean AND T. this notion has been the subject of recent interest, and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to bases stations (points), such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R-2 can be conflict-free colored with (O) over tilde (n(beta+epsilon)) colors in expected polynomial time, for any arbitrarily small epsilon > 0 and beta = 3-root 5/2 < 0.382. this improves upon the previously known bound of O(root n log log n/ log n).

关键词： Frequency assignment in wireless networks conflict-free coloring axis-parallel rectangles dominating sets monotone sequences

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: An implementation report for parallel triangular decompositions

Brief announcement: An implementation report for parallel tr...

引用

spaa 2006: 18th annual acm symposium on parallelism in algorithms and architectures

作者： Maza, Marc Moreno Xie, Yuzhen London Ont. Canada

ISBN: (纸本)1595934529

Since the discovery of Gröbner bases, the algorithmic advances in Commutative Algebra have made possible to tackle many classical problems in Algebraic Geometry that were previously out of reach. However, algorithmic progress is still desirable, for instance when solving symbolically a large system of algebraic non-linear equations. For such a system, in particular if its solution set consists of geometric components of different dimension (points, curves, surfaces, etc) it is necessary to combine Gröbner bases with decomposition techniques, such as triangular decompositions. Ideally, one would like each of the different components to be produced by an independent processor, or set of processors. In practice, the input polynomial system, which is hiding those components, requires some transformations in order to split the computations into sub-systems and, then, lead to the desired components. the efficiency of this approach depends on its ability to detect and exploit geometrical information during the solving process. Our work addresses two questions: How to discover geometrical information, at an early stage of the solving process, that would be favorable to parallel execution? How to ensure load balancing among the processors? We answer these questions in the context of triangular decompositions [2] which are a popular way of solving polynomial systems symbolically. these methods tend to split the input polynomial system into subsystems and, therefore, are natural candidate for parallel implementation. However, the only such method which has been parallelized so far is the Characteristic Set Method of Wu [5], as reported in [1, 6]. this approach suffers from several limitations. For instance, the solving of the second component cannot start before that of the first one is completed;this is a limitation in view of coarse-grain parallelization. In [4] an algorithm, called Triade, for TRIAngular DEcompositions, provides a good management of the intermediate computa

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

A work-optimal CGM algorithm for the LIS problem

A work-optimal CGM algorithm for the LIS problem

引用

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

作者： thierry, G. Jean-Frádáric, M. David, S. Lab. de Recherche en Info. d'Amiens Univ. de Picardie Jules Verne CURI 5 rue du Moulin Neuf 80000 Amiens France

this paper presents a work-optimal CGM algorithm that solves the Longest Increasing Subsequence Problem. It can be implemented in the CGM with P processors in O(N2/P) time and O(P) communication steps. It is the first... 详细信息

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Optimal schedules for data-parallel cycle-stealing in networks of workstations

Annual ACM Symposium on Parallel Algorithms and Architecture...

引用

annual acm symposium on parallel algorithms and architectures 2000年 22-29页

作者： Rosenberg, Arnold L. Univ of Massachusetts Amherst United States

We refine the model underlying our prior work on scheduling cycle-stealing opportunities in NOWs, obtaining a model wherein the scheduling guidelines of [16] produce optimal schedules for every such opportunity. Although computing optimal schedules usually requires the use of general (often inefficient) function-optimizing methods, we show how to compute optimal schedules efficiently for the broad class of opportunities whose durations come from a concave probability distribution. Even when no such efficient computation of an optimal schedule is available, our refined model always suggests a natural notion of approximately optimal schedule, which may be efficiently computable. We illustrate such efficient approximability via the important class of cycle-stealing opportunities whose durations come from a heavy-tailed distribution. Such opportunities do not admit any optimal schedule - nor even a natural notion of approximately optimal schedule - within the model of [5, 16]. Within our refined model, though, we derive computationally simple schedules for heavy-tailed opportunities, which can be `tuned' to have expected work-output that is arbitrarily close to optimal.

关键词： Computer workstations

来源：评论

学校读者我要写书评

暂无评论

Fast set operations using treaps 98

Fast set operations using treaps

引用

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

作者： Blelloch, G.E. Reid-Miller, M. Carnegie Mellon Univ Pittsburgh PA United States

ISBN: (纸本)9780897919890

We present parallel algorithms for union, intersection and difference on ordered sets using random balanced binary trees (treaps [26]). For two sets of size n and m (m ≤ n) the algorithms run in expected O(m lg(n/m)) work and O(lg n) depth (parallel time) on an EREW PRAM with scan operations (implying O(lg2 n) depth on a plain EREW PRAM). As with the sequential algorithms on treaps for insertion and deletion the main advantage of our algorithms are their simplicity. In fact our algorithms for set operations seem simpler than previous sequential algorithms with the same work bounds, and might therefore also be useful in a sequential context. To analyze the effectiveness of the algorithms we implemented both sequential and parallel versions of the algorithms and ran several experiments on them. Our parallel implementation uses the Cilk [5] shared memory runtime system on a 16 processor SGI Power Challenge and a 6 processor Sun Ultra Enterprise 3000. It shows reasonable speedup: 6.3 to 6.8 speedup on 8 processors of the SGI, and 4.1 to 4.4 speedup on 5 processors of the Sun.

关键词： 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

来源：评论

学校读者我要写书评

暂无评论

Scalable parallel computational geometry for coarse grained multicomputers

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1996年第3期6卷 379-400页

作者： Dehne, F Fabri, A RauChaplin, A CARLETON UNIV SCH COMP SCIOTTAWAON K1S 5B6CANADA INRIA F-06902 SOPHIA ANTIPOLISFRANCE

We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O(n/p) much greater than O(1) local memory and all processors are connected via some arbitrary interconnection network (e.g. mesh, hypercube, fat tree). We present O(T-sequential/p + T-s(n,p)) time scalable parallel algorithms for several computational geometry problems. T-s(n,p) refers to the time of a global sort operation. Our results are independent of the multicomputer's interconnection network. their time complexities become optimal when T-sequential/p dominates T-s(n,p) or when T-s(n,p) is optimal. this is the case for several standard architectures, including meshes and hypercubes, and a wide range of ratios n/p that include many of the currently available machine configurations. Our methods also have some important practical advantages: For interprocessor communication, they use only a small fixed number of one global routing operation, global sort, and all other programming is in the sequential domain. Furthermore, our algorithms use only a small number of very large messages, which greatly reduces the overhead for the communication protocol between processors. (Note however, that our time complexities account for the lengths of messages.) Experiments show that our methods are easy to implement and give good timing results.

关键词： computational geometry parallel algorithms scalability

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the 5th annual acm symposium on parallel algorithms and architectures, spaa 1993

Proceedings of the 5th Annual ACM Symposium on Parallel Algo...

引用

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

ISBN: (纸本)0897915992

the proceedings contain 47 papers. the topics discussed include: Fault-Tolerant Meshes with Small Degree;the verification of cache coherence protocols;fault diagnosis in a small constant number of parallel testing rounds;tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults;on Gazit and Miller�s parallel algorithm for planar separators: achieving greater efficiency through random sampling;parallel and output sensitive algorithms for combinatorial and linear algebra problems;efficient parallel shortest-paths in digraphs with a separator decomposition;components for computing and communications;highly efficient dictionary matching in parallel;optimal parallel two dimensional pattern matching;and parallel construction and query of suffix trees for two-dimensional matrices.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：