Time optimal linear schedules for algorithms with uniform dependencies

Author

Shang, Weijia ; Fortes, Jose A B

Author_Institution

Center for Adv. Comput. Studies, Univ. of Southwestern Louisiana, Lafayette, LA, USA

Volume

40

Issue

6

fYear

1991

fDate

6/1/1991 12:00:00 AM

Firstpage

723

Lastpage

742

Abstract

The authors address the problem of identifying optimal linear schedules for uniform dependence algorithms so that their execution time is minimized. Procedures are proposed to solve this problem based on the mathematical solution of a nonlinear optimization problem. The complexity of these procedures is independent of the size of the algorithm. Actually, the complexity is exponential in the dimension of the index set of the algorithm, and for all practical purposes, very small due to the limited dimension of the index set of algorithms of practical interest. A particular class of algorithms for which the proposed solution is greatly simplified is considered, and the corresponding simpler organization procedure is provided

Keywords

computational complexity; optimisation; parallel algorithms; algorithms; complexity; mathematical solution; nonlinear optimization problem; time optimal linear schedules; uniform dependence algorithms; uniform dependencies; Algorithm design and analysis; Lattices; Multidimensional systems; Optimal scheduling; Optimizing compilers; Parallel processing; Processor scheduling; Scheduling algorithm; Systolic arrays; Vectors;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.90251

Filename

90251