Data Sequencing for Minimum-transition Transmission
Rajeev Murgai, Masahiro Fujita, Sriram C. Krishnan · 1997
Given a set of data words or messages to be transmitted over a bus such that the sequence (order) in which they are transmitted is irrelevant, we address the problem of determining the optimum sequence that minimizes the total number of transitions on the bus. Since busses take up significant fraction of chip-area, the bus capacitances are often considerable; then the bus power may account for as much as 40% of the total power consumed on the chip (Designer 1995). Thus exploiting the freedom to resequence the data words can lead to substantial power savings. This problem arises during the flushing of a cache and transmission of packets over a channel. We also show how some power minimization problems in scheduling during high-level synthesis, in instruction-sequencing for embedded applications, and in die testing can be cast as the data ordering problem. We prove that the data ordering problem is NP-complete. Nevertheless, we propose two polynomial-time algorithms to approximate the optimum solution to within a constant factor. The first algorithm gives a solution to within a factor of 2 from the optimum, and the second within a factor of 1.5, but at an additional cost that is a function of the word-size. Experimental results confirm that resequencing data using the proposed algorithms leads to significant reduction (by 36%) in switching activity and hence power savings.