Minimizing Register Requirements under Resource-Constrained Rate-Optimal Software Pipelining

R. Govindarajan, Erik R. Altman, Guang R. Gao
govind@cs.mcgill.ca

Abstract

In this paper we address the following software pipelining problem: given a loop and a machine architecture with a fixed number of processor resources (e.g. function units), how can one construct a software-pipelined schedule which runs on the given architecture at the maximum possible iteration while minimizing the number of registers?

The main contributions of the paper are:

First, we demonstrate that such problem can be described by a simple mathematical formulation with precise optimization objectives under periodic linear scheduling framework. The mathematical formulation provides a clear picture which permits one to visualize the overall solution space (for rate-optimal schedules) under different sets of constraints.
Secondly, we show that a precise mathematical formulation and its solution does not make a signficant peformance difference! We evaluated the performance of our method agains three other leading contemporary heuristic methods: Huff's Slack Scheduling, Want, Eisenbeis, Jourdan and Su's FRLC, and Gasperoni and Schwiegelshohn's modified list scheduling. Experimental results show that the method described in this paper performed significantly better than these methods.

Talk Overheads (235588 bytes)