A processor-time-minimal schedule for the standard tensor product algorithm

Author

Scheiman, Chris ; Cappello, Peter

Author_Institution

Dept. of Comput. Sci., California Univ., Santa Barbara, CA, USA

fYear

1994

fDate

22-24 Aug 1994

Firstpage

176

Lastpage

187

Abstract

The paper, using a directed acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n×n×n×n directed mesh. Its completion requires at least 4n-3 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the 4D mesh, such a schedule requires at least (2/3)n³+n/3 processors. This lower bound is shown to be exact by constructing a processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a 3-dimensional twisted torus

Keywords

computational complexity; directed graphs; graph theory; multiprocessing systems; parallel algorithms; scheduling; systolic arrays; tensors; 3D twisted torus; 4D mesh; directed acyclic graph; directed mesh; lower bound; precedence constrained multiprocessor schedules; processor-time-minimal; processor-time-minimal multiprocessor schedule; processor-time-minimal schedule; standard tensor product algorithm; systolic array; three dimensional twisted torus; time-minimal multiprocessor schedules; topology; Algorithm design and analysis; Computational modeling; Computer science; Costs; Processor scheduling; Q measurement; Scheduling algorithm; Systolic arrays; Tensile stress; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

Application Specific Array Processors, 1994. Proceedings. International Conference on

Conference_Location

San Francisco, CA

ISSN

1063-6862

Print_ISBN

0-8186-6517-3

Type

conf

DOI

10.1109/ASAP.1994.331805

Filename

331805