[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.265-279 (March 1998)
Reducing Register Pressure in Software Pipelining*

FermJISEn SJISEnchez, and Jordi Cortadella+
Department of Computer Architecture
Universitat PolitJISEcnica de Catalunya
+ Department of Software
Universitat PolitJISEcnica de Catalunya

Software pipelining is a widely used technique aimed at finding an instruction-level parallel schedule for loops. Reducing the execution time of each iteration often results in an increasing demand for resources to execute the loop instructions and to store variables. This paper presents a new technique to reduce the register requirements in schedules obtained by means of software pipelining approaches. The technique reschedules the instructions inside and across the schedule boundaries. This is done by means of retiming without modifying either the initiation interval of the given schedule or the number of required resources. A two-step approach is proposed for such reduction: 1) minimizing the number of schedule stages and 2) rescheduling instructions within a basic block. The proposed technique has polynomial complexity, and experiments show that it obtains optimal results in most cases, thus improving the schedules found by means of the best existing techniques.

Keywords: software pipeling, register pressure, register optimization, span reduction, incremental scheduling, retiming

Received May 3, 1997; revised November 11, 1997.
Communicated by Chau-Huang Huang.
* This work was supported by CYCYT TIC-95-0419.