Data path allocation

A regular computation-intensive signal flow—as occurs in algebraic analysis, Altering, or format conversion— is combined with nested branches and multiple data-dependent loops. This explicit irregularity complicates not only the controller synthesis but also other synthesis tasks, Uke scheduling and data-path allocation. These tasks need to deal with control-flow hierarchy explicitly, which is an important aspect of our approach (see section 3). 

I. Park, K. O Brien, and A. A. Jerraya. An interactive data-path allocation algorithm. IFIP Workshop on Control Dominated Synthesis from a Register Transfer Level Description, Grenoble, Prance, 1992. 

Allocation, which assigns each operation to a piece of hardware. Allocation involves both the selection of the type and quantity of hardware modules from a library (often called module assignment) and the mapping of each operation to the selected hardware. Allocation is sometimes called data path synthesis or data path allocation. 

The EMUCS data path allocator uses an algorithm originally deflned by McFarland, but unpublished. It attempts to bind dataflow elements onto hardware elements in a step-by-step... 

L. Stok, Interconnect Optimisation During Data Path Allocation , Proc. ofEDAC SO, pages 141-145, March 1990. 

Chu-Yi Huang, Yen-Shen Chen, Youn-Long Lin, and Yu-Chin Hsu, Data Path Allocation Bas on Bipartite Weighted Matching , Proc. of the 27th DAC, pages 499- 04, June 1990. 

The University of Illinois synthesis system consists of three parts Chippe, Slicer, and Splicer. Chippe controls the S3mthesis process, Slicer is the scheduler, and Splicer is the data path allocator. Chippe was Brewer s thesis work, and Slicer / Splicer was Pangrle s thesis work, both at the University of Illinois at Urbana-Champaign. 

First, an ASAP schedule is constructed, assuming infinite resources, and one cycle per operation. Then optimizations are applied, moving operations to other control steps to reduce the maximum number of operations of each type in any one control step, and grouping operations into functional units so as to have a minimum number of functional units. Uien the scheduler traverses the control step schedule, passing the operations in each control step to the data path allocator. The data path allocator tries to bind those operations using heuristics if it fails, the scheduler tries to delay operations until later control steps, and if that also fails, the user is notified that the resource constraints should be increased. 

The Data Path Allocation tool (EMUCS) determines the number of registers, functional units, and interconnections needed to implement the behavior and assigns appropriate behavioral entities to them. A post-processing phase determines the bussing structure. 

Register-Transfer Level Synthesis includes two phases, control step scheduling and data path allocation and binding. 

Data path allocation can also make use of partitioning information. Since operations from different partitions cannot share hardware, a data path allocator can make use of the minimum hardware information that the control step allocator may take advantage of, but can also use the partitioning information to guide the mapping of data flow operators to hardware. 

Before discussing the specifics of the EMUCS data path allocator, several other data path allocators will be described briefly. McFarland [McFarlandSS] provides a tutorial on High-Level Synthesis in which he defines two classes of data path allocators iterative/constructive and global allocation. Iterative/constructive techniques bind one element at a time, while global allocation techniques find simultaneous solutions to a number of bindings at one time. Examples of each of these techniques are described below. 

---