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

Simple Concurrent Connected Components algorithms

ACM TRANSACTIONS ON PARALLEL COMPUTING 2022年第2期9卷 1–26页

作者： Liu, Sixue Cliff Tarjan, Robert Endre Carnegie Mellon Univ Pittsburgh PA 15213 USA Princeton Univ Princeton NJ 08540 USA

We study a class of simple algorithms for concurrently computing the connected components of an n-vertex, m-edge graph. Our algorithms are easy to implement in either the COMBINING CRCW pram or the MPC computing model. For two related algorithms in this class, we obtain Theta(lgn) step and Theta(m lgn) work bounds.(1) For two others, we obtain O(lg(2) n) step and O(m lg(2) n) work bounds, which are tight for one of them. All our algorithms are simpler than related algorithms in the literature. We also point out some gaps and errors in the analysis of previous algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.

关键词： Connected components pram algorithms simplicity

来源：评论

学校读者我要写书评

暂无评论

More Efficient Parallel Integer Sorting

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2022年第5期33卷 411-427页

作者： Han, Yijie He, Xin Univ Missouri Sch Comp & Engn Kansas City MO 64110 USA Univ Buffalo State Univ New York Dept Comp Sci & Engn 338 Davis Hall Buffalo NY 14260 USA

We present a more efficient CREW pram algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2, ... , n(1/2)} in O(log n)(3/2)/log log n) time and O(n(log n/ log log n)(1/2)) operations. It also sorts n integers in {0, 1, 2, ..., n - 1} in 0 ((log n)(3/2)/log log n) time and O (n(log n/log log n)1/2 log log log n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O (n(log n)(1/2)).

关键词： algorithms design of algorithms bucket sorting integer sorting pram algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and Efficient Parallel Coarsest Refinement

引用

FUNDAMENTA INFORMATICAE 2017年第2期150卷 211-220页

作者： Juneam, Nopadon Kantabutra, Sanpawat Chiang Mai Univ Fac Sci Dept Comp Sci Chiang Mai 50200 Thailand Chiang Mai Univ Fac Engn Dept Comp Engn Theory Computat Grp Chiang Mai 50200 Thailand Chiang Mai Univ Dept Comp Engn Theory Computat Grp Chiang Mai Thailand

The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X,Y of the set U such that X = {X-1, X-2,..., X-x} and Y = {Y-1, Y-2,...;Y-y } and determine a new partition Z = {Z(1), Z(2),..., Z(z)} such that each Z(c) epsilon Z is a common non-empty subset of some X-a epsilon X and some Y-b epsilon Y and Z is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O(t (n) + log n) parallel time using max{n/log n, p(n)} processors, where t(n) denotes the running time of a parallel stable sorting algorithm that uses p(n) processors on an EREW pram. This result depends on t(n) and p(n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW pram. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O(log n log (n/log n)) parallel time using n/log n processors on an EREW pram. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm.

关键词： pram algorithms parallel computation coarsest refinement partition refinement

来源：评论

学校读者我要写书评

暂无评论

Unified parallel encoding and decoding algorithms for Dandelion-like codes

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2010年第11期70卷 1119-1127页

作者： Caminiti, Saverio Petreschi, Rossella Univ Roma La Sapienza Dept Comp Sci I-00198 Rome Italy

The Dandelion-like codes are eight bijections between labeled trees and strings of node labels. The literature contains optimal sequential algorithms for these bijections, but no parallel algorithms have been reported. In this paper the first parallel encoding and decoding algorithms for Dandelion-like codes are presented. Namely, a unique encoding algorithm and a unique decoding algorithm, which when properly parameterized, can be used for all Dandelion-like codes, are designed. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW pram is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading. (c) 2010 Elsevier Inc. All rights reserved.

关键词： Bijective tree encoding Prufer code Dandelion-like codes pram algorithms

来源：评论

学校读者我要写书评

暂无评论

Is Teaching Parallel Algorithmic Thinking to High School Students Possible? One Teacher's Experience 10

Is Teaching Parallel Algorithmic Thinking to High School Stu...

引用

41st ACM Technical Symposium on Computer Science Education

作者： Torbert, Shane Tzur, Ron Vishkin, Uzi Ellison, David J. Fairfax Cty Publ Sch Thomas Jefferson High Sch Sci & Technol Fairfax Cty VA USA

ISBN: (纸本)9781605588858

All students at our high school are required to take at least one course in Computer Science prior to their junior year. They are also required to complete a year-long senior project associated with a specific in-house laboratory, one of which is the Computer Systems Lab. To prepare students for this experience the lab offers elective courses at the post-AP Computer Science level. Since the early 1990s one of these electives has focused on parallel computing. The course enrolls approximately 40 students each year for two semesters of instruction. The lead programming language is C and topics include a wide array of industry-standard and experimental tools. Since the 2007-2008 school year we have included a unit on parallel algorithmic thinking (PAT) using the Explicit Multi-Threading (XMT) system [11, 12]. We describe our experiences using this system after self-studying the approach from a publicly available tutorial. Overall, this article provides significant evidence regarding the unique teachability of the XMT PAT approach, and advocates using it broadly in Computer Science education.

关键词： Parallel Algorithmic Thinking High School XMT pram algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel analysis and decomposition of partially occluded strings

引用

PARALLEL COMPUTING 2000年第4期26卷 483-494页

作者： Iliopoulos, CS Reid, JF Kings Coll London Dept Comp Sci Algorithm Design Grp London WC2R 2LS England Curtin Univ Technol Sch Comp Bentley WA 6102 Australia Univ Padua Dipartimento Elettron & Informat I-35131 Padua Italy

This is a theoretical study of partially occluded one-dimensional images. Here, we consider ''valid" images composed from a given set of objects, where some objects appearing in the image may be partially obstructed by others. A CRCW pram algorithm is presented here for validating a one-dimensional image x of length n over a set of k objects of equal length in O(log logn) time with linear work, where k is a fixed integer. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

关键词： string algorithms pram algorithms pattern recognition

来源：评论

学校读者我要写书评

暂无评论

An optimal parallel algorithm to convert a regular expression into its Glushkov automaton

引用

THEORETICAL COMPUTER SCIENCE 1999年第1-2期215卷 69-87页

作者： Ziadi, D Champarnaud, JM Univ Rouen Lab Informat Rouen Fac Sci F-76821 Mt St Aignan France

The aim of this paper is to describe a CREW-pram optimal algorithm which converts a regular expression of size s into its Glushkov automaton in O(logs) time using O(s(2)/log s) processors. This algorithm makes use of the star-normal form of an expression as defined by Bruggemann-Klein (1993) and is based on the sequential algorithm due to Ziadi et al. (1997) which computes an original representation of Glushkov automaton in O(s) time. (C) 1999-Elsevier Science B.V. All rights reserved.

关键词： pram algorithms regular expressions finite automata

来源：评论

学校读者我要写书评

暂无评论

Parallel maximum independent set in convex bipartite graphs

引用

INFORMATION PROCESSING LETTERS 1996年第6期59卷 289-294页

作者： Czumaj, A Diks, K Przytycka, TM UNIV PADERBORN DEPT MATH & COMP SCID-33095 PADERBORNGERMANY UNIV WARSAW INST INFORMATPL-02097 WARSAWPOLAND UNIV MARYLAND DEPT COMP SCICOLLEGE PKMD 20742

A bipartite graph G = (V, W, E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any vertex nu is an element of V form an interval (i.e. a sequence consecutively numbered vertices). Such a graph can be represented in a compact form that requires O(n) space, where n = max{\V\, \W\}. Given a convex bipartite graph G in the compact form Dekel and Sahni designed an O(log(2)(n))-time, n-processor EREW pram algorithm to compute a maximum matching in G, We show that the matching produced by their algorithm can be used to construct optimally in parallel a maximum set of independent vertices. Our algorithm runs in O(log n) time with nl log n processors on an Arbitrary CRCW pram.

关键词： bipartite graphs convex graphs independent set pram algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel superprimitivity testing for square arrays

引用

Parallel Processing Letters 1996年第3期6卷 299-308页

作者： Iliopoulos, Costas S. Department of Computer Science King's College London Strand London United Kingdom

We present an optimal O(log log n) time algorithm on the CRCW pram which tests whether a square array, A, of size n × n, is superprimitive. If A is not superprimitive, the algorithm returns the quasiperiod, i.e.,... 详细信息

关键词： Complexity Parallel algorithms pram algorithms String algorithms

来源：评论

学校读者我要写书评

暂无评论

TOP-BOTTOM ROUTING AROUND A RECTANGLE IS AS EASY AS COMPUTING PREFIX MINIMA

引用

SIAM JOURNAL ON COMPUTING 1994年第3期23卷 449-465页

作者： BERKMAN, O JAJA, J KRISHNAMURTHY, S THURIMELLA, R VISHKIN, U UNIV MARYLAND INST ADV COMP STUDIESCOLL PKMD 20742 TEL AVIV UNIV IL-69978 TEL AVIVISRAEL UNIV MARYLAND DEPT ELECT ENGNCOLL PKMD 20742 UNIV DENVER DEPT MATH & COMP SCIDENVERCO 80208

A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers [1..s]. For an input of size n, it runs in O(log log log s) time and O(n) work (which is optimal). A faster algorithm is presented for the special case s = n;it runs in O(log* n) time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CRCW pram). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the OMEGA(log log n) time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348-355]. The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with s = n, thus giving an 0 (log* n) time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.

关键词： PARALLEL algorithms VLSI ROUTING PREFIX MINIMA pram algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：