Article The new class of g-chain periodic sorters Share on Authors: Ronald I. Becker View Profile , David Nassimi View Profile , Yehoshua Perl View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 356–364https://doi.org/10.1145/165231.157378Online:01 August 1993Publication History 4citation147DownloadsMetricsTotal Citations4Total Downloads147Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Derives a simple lower bound for performing a 2/sup b/ permutation on an N-PE SIMD hypercube, proving that log N-b routing steps are needed even if one allows an arbitrary mapping of elements to processors. An algorithm for performing a 2/sup b/ permutation using exactly log N-b full-duplex routing steps that is slightly more efficient than previously known O(log N-b) algorithms, which perform the permutation as an Omega or Omega /sup -1/ mapping, is presented. The author has also identified a general class of parallel computations called +or-2/sup b/ descend, which includes Batcher's odd-even merge and many other algorithms. An efficient algorithm for performing any computation in this class in O(log N) steps on an N-PE SIMD hypercube is given. A related class of parallel computations called +or-2/sup b/ ascend is also defined. This class appears to be more difficult than +or-2/sup b/ descend. A simple O(log/sup 2/ N/log log) N algorithm for this class on a SIMD hypercube, requiring Theta (log log N) space per processor is developed.>

article Free Access Share on Parallel permutation and sorting algorithms and a new generalized connection network Authors: David Nassimi Department of Electrical Engineering and Computer Science, North-western University, Evanston, IL Department of Electrical Engineering and Computer Science, North-western University, Evanston, ILView Profile , Sartaj Sahni Department of Computer Science, 136 Lind Hall, University of Minnesota, Minneapolis, MN Department of Computer Science, 136 Lind Hall, University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims Journal of the ACMVolume 29Issue 3July 1982 pp 642–667https://doi.org/10.1145/322326.322329Published:01 July 1982Publication History 174citation937DownloadsMetricsTotal Citations174Total Downloads937Last 12 Months42Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A parallel algorithm to determine the switch settings for a Benes permutation network is developed. This algorithm can determine the switch settings for an N input/output Benes network in 0(log2N) time when a fully interconnected parallel computer with N processing elements is used. The algorithm runs in 0(N½) time on an N½× N½mesh-connected computer and 0(log4N) time on both a cube connected and a perfect shuffle computer with N processing elements. It runs in 0(k log3N) time on cube connected and perfect shuffle computers with N1+1/kprocessing elements.

In this correspondence we develop an algorithm to perform BPC permutations on a cube connected SIMD computer. The class of BPC permutations includes many of the frequently occurring permutations such as matrix transpose, vector reversal, bit shuffle, and perfect shuffle. Our algorithm is shown to be optimal in the sense that it uses the fewest possible number of unit routes to accomplish any BPC permutation.

Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two $n \times n$ matrices can be multiplied in $O(n/m + \log m)$ time when $n^2 m$, $1 \leqq m \leqq n$, processing elements (PEs) are available. When only $m^2 $, $1 \leqq m \leqq n$, PEs are available, two $n \times n$ matrices can be multiplied in $O(n^2/m + m(n/m)^{2.61} )$ time. It is shown that many graph problems can be solved efficiently using the matrix multiplication algorithms.

Considers the data broadcasting problem for single instruction stream, multiple data stream (SIMD) computers. Two versions of this problem, i.e., random access read (RAR) and random access write (RAW) are considered. Efficient data broadcasting algorithms are developed for both cases. For the case of a RAR, the complexity of the algorithm is O(q2n) on aq-dimensionalnqPE mesh-connected computer and 0(log2N) on anNPE cube-connected or perfect shuffle computer. For the case of a RAW, the complexity of the algorithm is 0(q2n+dqn) on aq-dimensional MCC and 0(log2N+dlogN) on anNPE cube-connected or perfect shuffle computer;dis the maximum number of data items written into any one PE.

A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for the N input utput self-routing network is O(log N). It is shown that the network is capable of performing a rich class of permutations. The self-routing scheme leads to efficient O(log N) parallel algorithms to perform the same class of permutations on cube connected and perfect shuffle computers.

A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for an N input/output self routing network is O(log N). This network is capable of performing a large class of permutations. If the switches are set externally, then all permutations can be performed.

An opUmal algorithm to route data in a mesh-connected parallel computer is presented This algorithm can be used to perform any data routing that can be specified by the permutation and complementing of the bits in a PE address Matrix transpose, bit reversal, vector reversal, and perfect shuffle are examples of data permutations that can be specified in this way The algorithm presented uses the minimum number of unit distance routing steps for every data permutation that can be specified as above K~EV WORDS ANY PrmASES parallel algorithm, mesh-connected computer, ILLIAC IV, permutation, complexity, data routing CR CATEGORIES 5 25, 5 31, 6 22

Let $G = (V,E)$ be an undirected graph in which no vertex has degree more than d. Let $|V| = n^q = 2^q $ . In this paper we present an $O(q^3 (q + d)n\log n)$ algorithm to find the connected components of G on a q-dimensional $n \times n \times \cdots \times n$ mesh-connected parallel computer. When $d = 2$, the connected components can be found in $O(q^4 n)$ time. We also show that the connected ones problem can be solved in $O(q^6 n)$ time.

An O(n) algorithm to sort n2elements on an Illiac IV-like n × n mesh-connected processor array is presented. This algorithm sorts the n2elements into row-major order and is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an O(n) algorithm to sort n2elements into snake-like row-major order. Extensions to the case of a j-dimensional processor array are discussed.