Data path synthesis

Abstract

This paper reviews all the phases in data path synthesis: register allocation, storage grouping, module allocation and interconnect allocation. In addition, a new phase for the storage value insertion is introduced. For each of these phases a formal problem description is given. Restrictions on the data path allocation phases are presented, which delimit the problems to cases which can be solved by polynomial algorithms. For the general cases, heuristics are provided which have appeared to be effective in the literature. Special data path architectures may require special algorithms to make use of their features. Throughout the paper archetectural constraints are described and effective algorithms for them derived. To construct an effective data path allocation system, a scheme has to be defined. The scheme determines which subproblems are solved in what order and which constraints are taken into account in each phase. The data flow graph and schedule and their match with the data path architecture have a major impact on the development of a scheme. This paper will point out the trade-offs that have to be made when developing such a scheme. This paper provides a reference to most of the data path allocation algorithms published in the scope of high-level synthesis. Most of the techniques are explained in considerable detail and various examples are given. The paper comments on the applicability of most of the algorithms for particular data path allocation problems. © 1994.