Scheduling for low power under resource and latency constraints

We extend the Force-Directed List Scheduling (FDLS) algorithm proposed by Paulin and Knight (1989). In any time step, if the number of ready operations exceeds the available functional resources, then some operations must be deferred. The concept of “force” introduced by Paulin and Knight captures the effect of deferring an operation on the schedule length: larger the force, lower the likelihood of schedule length increase due to the operation´s deferral. We develop a power cost function that captures the effect of an operation´s deferral on the total power consumption of the design. The novelty of the work lies in heuristically determining the “best” time-step for an operation such that the overall power consumption is minimized without sacrificing the design throughput. The power-delay cost function proposed at the operation-level facilitates such an exploration. Experimental results show power savings of up to 60% with an average power savings of 23% at datapath level, 3% at the controller level, and 14% at the design-level