Title :
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
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)n3+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;
Conference_Titel :
Application Specific Array Processors, 1994. Proceedings. International Conference on
Conference_Location :
San Francisco, CA
Print_ISBN :
0-8186-6517-3
DOI :
10.1109/ASAP.1994.331805
