Browse Prior Art Database

SINID Algorithms For 2-D Arrays In Shuffle Networks

IP.com Disclosure Number: IPCOM000128197D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 19 page(s) / 55K

Publishing Venue

Software Patent Institute

Related People

Yosi Ben-Asher: AUTHOR [+5]

Abstract

and the Model , 2. Sort ... 3. The Raw-Reduction Operation 3.1. 2-D Multiple-Broadcast operation 4. Parallel Prefix by Raws .............. 5. The Transpose Operation ............ 5.1. Transpose Rows to Columns T, 5.2. Transpose Columns to Rows TAT 6. Packing and Unpacking ......... 6.1. One-Dimensional Packing 6.2. 2-D Packing ...................... 6.3. 2-D Unpacking .................. 6.4. 2-D Backing lower bound .... '7. The Smoothing Operation ...... 7.1. Simple Smoothing Algorithm 7.2. The Support Algorithm 7.3. Simulation Results ..... 7.4. The Dup Operation .... 7.5. Dup - Smoothing ....... 8. Cartesian Product ......... 8.1. Cartesian Product by Groups 9. Discussion and Summary ....... 10. Acknowledgements

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SINID Algorithms For 2-D Arrays In Shuffle Networks

by Yosi Ben-Asher David Egoai Assaf Schuster

Ultracomputer Note #147 February, 1988 The work of the first author was done while under partial support of IBM under grant No. N00039-84-R-0605(Q) . The work of the second author was supported under National Science Foundation grant No. DCR-8413359 while employed at the Courant Institute. Current Address for the first and third author's: Hebrew University, Department of Mathematics and Com-puter Science, Jerusalem, Israel.

Table of Contents

1. Introduction and the Model , 2. Sort ...

3. The Raw-Reduction Operation

3.1. 2-D Multiple-Broadcast operation

4. Parallel Prefix by Raws .............. 5. The Transpose Operation ............ 5.1. Transpose Rows
to Columns T, 5.2. Transpose Columns to Rows TAT 6. Packing and Unpacking ......... 6.1.
One-Dimensional Packing 6.2. 2-D Packing ...................... 6.3. 2-D Unpacking .................. 6.4.
2-D Backing lower bound .... '7. The Smoothing Operation ...... 7.1. Simple Smoothing Algorithm
7.2. The Support Algorithm 7.3. Simulation Results ..... 7.4. The Dup Operation .... 7.5. Dup -
Smoothing ....... 8. Cartesian Product ......... 8.1. Cartesian Product by Groups 9. Discussion and
Summary .......

10. Acknowledgements

11.References .......................... Ultracomputer Note 147 6 Page i

ABSTRACT

This paper studies a set of 2-D basic algorithms for SIMD perfect shuffle networks. Those algorithms where studied in [1] and [SN], but for the 1-D case, where the size of the problem N is the same as the number of proces-sors P. For the 2-D case of N=L*P, we improve some algorithms to be "2-D efficient", by improving their running time from

(Equation Omitted)

as N exceeds P. We give nontrivial algorithms for the follow-ing operations: Row-Reduction, Parallel-Prefix, Transpose, Packing, Smoothing and Cartesian-Product.

This paper studies a set of 2-D basic algorithms for SIMD perfect shuffle networks. Those algorithms where studied in [1] and [SN], but for the 1-D case, where the size of the problem N is the same as the number of proces-sors P. For the 2-D case of N=L*P, we improve some algorithms to be "2-D efficient", by improving their running time from

New York University Page 1 Dec 31, 1988

Page 2 of 19

SINID Algorithms For 2-D Arrays In Shuffle Networks

(Equation Omitted)

as N exceeds P. We give nontrivial algorithms for the follow-ing operations: Row-Reduction, Parallel-Prefix, Transpose, Packing, Smoothing and Cartesian-Product.

1. Introduction and the Model

Schwartz [1] introduced the idea of a parallel processor based on the shuffle connections [2]; reviewed various basic of SIMD algorithms for such an ensemble of processors, and analyzed their asymptotic time complexities. However, these algorithms are designed for the 1-D case, where N, the size of the problem is restricted to be P, the number of proces-sors.,/ In reallit...