Title :
Optimization of computation time for systolic arrays
Author :
Wong, Yiwan ; Delosme, Jean-Marc
Author_Institution :
Yale Univ., New Haven, CT, USA
fDate :
2/1/1992 12:00:00 AM
Abstract :
This work deals with the general case of processors with multiple, possibly pipelined, functional units that operate concurrently and presents a method for the minimization of the actual computation time nsys×tsys. The selection of a linear scheduling function, which minimizes nsys×tsys is formulated as a combinatorial optimization problem, which is shown to have a bounded search space. An efficient branch-and-bound method for the solution of that problem is proposed and applied to several examples
Keywords :
minimisation; multiprocessor interconnection networks; parallel algorithms; systolic arrays; bounded search space; branch-and-bound method; combinatorial optimization problem; computation time minimization; concurrency; linear scheduling function; multiple functional units; pipelined functional units; systolic arrays; Algorithm design and analysis; Computed tomography; Concurrent computing; Costs; Hardware; Parallel architectures; Processor scheduling; Scheduling algorithm; Systolic arrays; Time measurement;
Journal_Title :
Computers, IEEE Transactions on
