A Graph Heuristic Approach for the Data Path Allocation Problem

Abstract

The current escalation in usage and complexity of modern digital systems, and the emergence of Very-Large Scale Integration (VLSI) has led to a huge design productivity gap in the chip design industry. It is well established that the annual growth of the number of transistors on a chip surpasses that of transistors handled by a fi xed-sized design team. This gap, represented by \Moore's law of engineers", raises the necessity for more efficient approaches to automatically design these advanced frameworks. This paper aims to reduce the design productivity gap by presenting a new algorithm to optimize chip design automation in terms of runtime and solution quality. More speci cally, this automation process known as high-level synthesis (HLS), targets the datapath allocation problem in VLSI design. In this context, datapath allocation represents one of the major steps in HLS along with scheduling and partitioning. To optimize this allocation problem, a variation of the Fiduccia-Mattheyses (FM) algorithm is presented. The algorithm starts with a schedule as input and partitions it into available hardware resources using a modifi ed version of the Fiduccia-Mattheyses algorithm to t the datapath allocation problem. The algorithm is tested on various benchmarks and favorable results are reported. The results show that the algorithm performs well while generating sub-optimal solutions.