Scheduling and mapping
Authors:
Open Access
- 1 June 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 30 (6) , 139-150
Abstract
Recently, software pipelining methods based on an ILP (Integer Linear Programming) framework have been successfully applied to derive rate-optimal schedules for architectures involving clean pipelines - pipelines without structural hazards. The problem for architectures beyond such clean pipelines remains open. One challenge is how, under a unified ILP framework, to simultaneously represent resource constraints for unclean pipelines, and the assignment or mapping of operations from a loop to those pipelines. In this paper we provide a framework which does exactly this, and in addition constructs rate-optimal software pipelined schedules. The proposed formulation and a solution method have been implemented and tested on a set of 1006 loops taken from various scientific and integer benchmark suites. The formulation found a rate-optimal schedule for 75% of the loops, and required a median time of only 2 seconds per loop on a Sparc 10/30.Keywords
This publication has 12 references indexed in Scilit:
- Iterative modulo scheduling1994
- Minimizing register requirements under resource-constrained rate-optimal software pipelining1994
- Minimum register requirements for a modulo schedule1994
- Lifetime-sensitive modulo scheduling1993
- Compiling for the CydraThe Journal of Supercomputing, 1993
- Instruction-level parallel processing: History, overview, and perspectiveThe Journal of Supercomputing, 1993
- Software pipelining: an effective scheduling technique for VLIW machines1988
- Optimal loop parallelization1988
- A VLIW architecture for a trace scheduling compilerIEEE Transactions on Computers, 1988
- Scheduling Parallel ComputationsJournal of the ACM, 1968