Affordable Access

Publisher Website

2-D SIMD algorithms for perfect shuffle networks

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
16
Issue
3
Identifiers
DOI: 10.1016/0743-7315(92)90036-m
Disciplines
  • Computer Science

Abstract

Abstract In this paper we study a set of basic algorithms for SIMD Perfect Shuffle networks. These algorithms were studied in the works of Schwartz ( ACM TOPLAS 2 (1980) , 484–521) and Nassimi and Sahni ( IEEE Trans. Comput. C 30, 2 (Feb. 1981) , 101–107), for the 1-D case, where the size of the problem N is the same as the number of processors P. For the 2-D case of N = L ∗ P, studied also by Gottlieb and Kruskal (Ultracomputer Note No. 11) and Kruskal (Ph.D. dissertation, Courant Institute, New York University, 1981), we improve the run time of several algorithms. In particular, the run time of Row Reduction and Parallel Prefix is improved from O(L ∗ P) to O( L + log P). An adaptive method for gathering global information is introduced, implying a fast algorithm for Smoothing (off-line load balancing). Optimal algorithms for Cartesian Product and for the Transpose operations are devised. Other problems, important variants of these problems, and lowerbounds can be found in the work of Ben-Asher, Egozi, Schuster (Hebrew University Tech. Rep. 88-14, Oct. 1988).

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

2D O(3) + 2D QG

Oct 04, 1993

Numerical Algorithms for Flows in the Nodes of 2D...

on Journal of Computational Physi... Jan 01, 1997

2D or not 2D?

on Nature Chemistry September 2014

2D or not 2D

on Current Opinion in Chemical Bi... Jan 01, 2001
More articles like this..