Resource-constrained software pipelining

Author

Aiken, Alexander ; Nicolau, Alexandru ; Novack, Steven

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA

Volume

6

Issue

12

fYear

1995

fDate

12/1/1995 12:00:00 AM

Firstpage

1248

Lastpage

1270

Abstract

This paper presents a software pipelining algorithm for the automatic extraction of fine-grain parallelism in general loops. The algorithm accounts for machine resource constraints in a way that smoothly integrates the management of resource constraints with software pipelining. Furthermore, generality in the software pipelining algorithm is not sacrificed to handle resource constraints, and scheduling choices are made with truly global information. Proofs of correctness and the results of experiments with an implementation are also presented

Keywords

optimising compilers; parallel algorithms; pipeline processing; processor scheduling; automatic extraction; correctness; fine-grain parallelism; instruction scheduling; machine resource constraints; program optimization; resource constraints; resource-constrained software pipelining; scheduling choices; truly global information; Computer aided manufacturing; Computer science; Hardware; Job shop scheduling; Parallel processing; Pipeline processing; Processor scheduling; Scheduling algorithm; Software algorithms; VLIW;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.476167

Filename

476167