Foreground memory management in data path synthesis

Abstract

The management of foreground memory is a main issue in data path synthesis. the storage of values in registers and register files not only determines the number of each of them but also has a major impact on the interconnect structure. Both the amount of multiplexing and interconnect are crucial factors to both the delay and area of a circuit. In this paper it is shown that when values are grouped into register files before being assigned to actual registers, significant savings (20 per cent) can be obtained in the number of local interconnections and the amount of global interconnect at the expense of only slightly more register area. These results can be enhanced by splitting the read and write phases of registers and even more by introducing serial (re)write operations for the same value. the value grouping is based on edge‐colouring algorithms that provide a sharp upper bound on the number of register groups needed. After value grouping, the registers are allocated for each register file separately. Algorithms for register allocation published up till now have only considered loop‐free data flow graphs. When these algorithms are applied to data flow graphs with loops, unnecessary register transfer operations can be introduced. In this paper a new algorithm is presented that performs a minimal register allocation eliminating all superfluous register transfer operations. Experiments on a benchmark set have shown that in all cases all register transfers could be eliminated at no increase in register cost. This paper provides a deeper insight to the computational complexity of some problems in the area of data path synthesis. It shows that the various subtasks can be solved exactly using polynomial time algorithms. Copyright © 1992 John Wiley & Sons, Ltd.