EMUCS Allocation

In the case of the Workbench, three tools are involved in the synthesis process CSTEP is used to create a control step schedule, EMUCS allocates hardware and binds the data flow objects to that hardware according to the schedule produced by CSTEP, and Busser is used to choose busses for the data path produced by EMUCS. The specific use of partitioning information by these three tools is described in the CSTEP and EMUCS chapters. 

FU allocation is based on an EMUCS-like algorithm [5]. Micro-scheduling uses an ASAP algorithm. Component placement and connection allocation make use of improved constructive approaches similar to those used in APOLLON [6]. The originality of the approach is that all of these algorithms are implemented in order to allow mixed manual and automatic design. With the exception of micro-scheduling, they all use a constructive approach. At each step, a new element is allocated or placed. The four steps may be sequenced automatically or performed step by step. Each step may be executed automatically, interactively, or manually. 

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... 

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. 

Furthermore, if two or more ISPS or VT processes call a common child, that child will be part of both processes. If only one process is synthesized at a time, as is done in the current version of EMUCS, this should present no major problems, but if a tool were to attempt to synthesize the entire VT (i.e., all processes) at the same time, different allocation structures would have to be maintained for the common children for each process. Since maintaining multiple allocation structures might be difficult, one solution to this problem might be to define a Duplicate Vtbody transformation, which would allow each process to have its own copy of the common children. Another solution, using the existing transformations, would be to simply make the common children into a separate process. 

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. 

Register allocation In the EMUCS initiation phase, the VT is searched for regvals that will have to be bound to registers. 

As is the case for scheduling, partitioning does not have a large effect on the data path allocation for this design. This is a result of EMUCS inability to bind objects of different bitwidths to the same module. In the Kalman Filter, the addressing carriers are 4 bits, while the data carriers are 16 bits, so address and data operators will not share hardware. For this case, this restriction to the way that EMUCS can bind exactly reflects the partitions produced by APARTY. 

This machine has shown how input costs can be varied in EMUCS to allow for a design space exploration and to allow particular technologies to be targeted in the data path allocation phase. 

The BTL310 partitions can be run through the data path allocation and bus choosing tools. Module counts for a data path design by EMUCS and Busser using default cost values are shown in Table 8-6. 

Control Step Scheduling and Data Path Allocation. Control step scheduling (CSTEP) and data path allocation (EMUCS) are the last of the major phases of the Workbench shown in Figure 9-1. The control step sequencing and data path allocation tools synthesize modules to perform the operations and transfer and store the values it finds in the VT. They assign all the operators in the VT to control steps and bind individual values and operators in the VT to specific modules in the synthesized structure. Only the EMUCS data path allocation tool has been integrated into the CORAL system. 

---