Browse Prior Art Database

Data Broadcasting In SIMD Computers

IP.com Disclosure Number: IPCOM000128552D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 14 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

David Nassimi: AUTHOR [+4]

Abstract

This paper considers the data broadcasting problem for SIMD computers. An efficient data broadcasting algorithm is developed. Its complexity is 0(q2n) on a q-dimensional nq PE mesh-connected computer, and 0(log2N) on N PE cube connected and perfect shuffle computers.

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Data Broadcasting In SIMD Computers

David Nassimi and Sartaj Sahni

Computer Science Department

136 Lind Hall. Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

Technical Report 79-17 June Data Broadcasting In SIMI) Computers

David Nassimi and Sartaj Sahni University of Minnesota'

Abstract:

This paper considers the data broadcasting problem for SIMD computers. An efficient data broadcasting algorithm is developed. Its complexity is 0(q2n) on a q-dimensional nq PE mesh- connected computer, and 0(log2N) on N PE cube connected and perfect shuffle computers.

Key words and phrases: data broadcasting,,SIMD computer, parallel algorithm, mesh- connected computer, cube connected computer, perfect shuffle computer, complexity. *This research was supported in part by NSF grant MCS 78-15455.

1. Introduction

A block diagram for an SIMI) (Single Instruction Stream, -Multiple -Data Stream) computer is given in Figure.l. As can be seen, an SIMI) computer consists of N processing elements (Hs): The PEs are indexed 0 through N-1 and may be referenced as PE(i). Each PE has some local memory. The PEs are synchronized and operate under the control of a single control program. ,PEs may be enabled or disableled so that the common instruction for any given time-unit is executed only on enabled PEs. The PEs are connected together via an interconnection net- work.Different interconnection networks lead to different SIMI) architectures. In this paper we shall consider the following three architectures: (i) Mesh Connected Computer (MCC) In this model the PEs may be thought of as logically arranged as in a q dimensional array

(Equation Omitted)

where ni is the size of the ith dimension. and

(Equation Omitted)

The PE at location A(i q-1,... i , 0) is connected to the PEs at location

(Equation Omitted)

provided they exist. Data may be transmitted from one l?E.to another only via this inter- connection pattern. (ii) Cube Connected Computers (CCC) Assume that

University of Minnesota Page 1 Dec 31, 1979

Page 2 of 14

Data Broadcasting In SIMD Computers

(Equation Omitted)

be the binary representation of

(Equation Omitted)

be the number whose binary representation is

(Equation Omitted)

where ib is the complement, of

(Equation Omitted)

. In the cube model, PE(i) is connected to

(Equation Omitted)

As in the mesh model data can be transmitted from one PE to another only via this interconnection pattern. (iii) Perfect Shuffle Computer (PSC) Let N, p, i and i(b) be as in the cube model. In the perfect shuffle model, PE(i) is connected to

(Equation Omitted)

These three connections will respectively be called

exchange,, shuffle and unshuffle. Once again, data transmission from PE to PE is possible only via the connection scheme. It should be noted that the MCC model requires 2q connections per PE, the CCC model requires log N (all logarithms in this paper are base 2) and the PSC model...