Data path binding

The processor synthesizer, which will be presented in the remaining of this chapter, consists of scheduling, data path binding and controller synthesis. Its output is a set of connected Register Transfer Level (RTL) modules which may be... 

In this chapter, we will present the processor synthesis part of THEDA. The general design consideration is described in Section 2. The target architecture is described in Section 3. Scheduling is described in Section 4. Constructive and iterative refined approaches to the data path binding problem are described in Section 5. Finally, we conclude with a summary. 

To synthesize a processor, we have to address a number of inter-dependent tasks including function unit selection, scheduling, data path binding and controller syn-... 

We have described an approach for processor synthesis. We divide the problem into three interdependent subtasks, namely, operation scheduling, data path binding and controller synthesis. The first subtask includes both time-constrained and resource-... 

The data path binding problem is divided into two phases data path construction and data path refinement. A branch-and-bound search algorithm is used to construct the initial data path based on a set of observations. During the data path refinement phase, we rip up a mixture of variables, data transfers and operations and relocate them. The refinement is augmented with a randomized selection process to prevent itself from being trapped in a local optimal. 

Binding - assigning operations to functional units, assigning values to storage units and interconnecting these components to cover the entire data path. 

Overview of the project, including scheduling and data path synthesis, module binding, controller allocation, floorplanning, and layout. 

Nam-Sung Woo, A Global, Dynamic Register Allocation and Binding for a Data Path Synthesis System , Proc. of the 27th DAC, pages 505-510, Jiuie 1990. 

Data path synthesis, including register allocation and binding, and three code segment examples. 

The ExHAL module then binds the operations to specific functional units and completes the data path. First, the operations are bound to specific functional units using a greedy algorithm, attempting to minimize the interconnect by minimizing the number of different sources and destinations... 

Scheduling, Data Path Synthesis, Controller Design, and Module Binding... 

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

Olympus overview, HardwareC, transformation, data path synthesis, scheduling, logic synthesis, and module binding. 

The University of California at Berkeley s HYPER system is aimed at synthesizing real-time applications, and includes transformations, scheduling, data path synthesis, module binding, and controller design. 

Uses a set of small transformations, including multiplexor reduction, allocation of assignment operations, and data path partitioning, plus several translation steps, which perform the module binding. 

The user can modify a data path by adding and/or deleting functional units and interconnection. At any time, the user can invoke the procedure fixit. which repairs the operator binding and interconnection, so that the original behavior is preserved. 

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. 

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

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. 

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. 

Two of the EMUCS design phases involve binding data-flow objects to data path modules. Before considering the specifics of the prebinding and automatic binding phases, it is important to understand how the binding is accomplished. 

EMUCS uses a prebinding phase to bind special operators. Three types of special operators are recognized by EMUCS control, memory, and message operators. In addition, the user may hand choose any other operators or regvals that he wants bound to particular modules. This allows the user to partially (or fully) specify the data path if he so chooses. 

Figure 6-8 demonstrates how a next binding is chosen. The figure shows a control step schedule and a graphical depiction of the scheduled VT. Assume the partial data path of Figure 6-6, and the costs defined previously, as well as the additional costs listed below. 

The choosing and binding process is repeated until all operators and regvals have been bound to data path modules. 

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. 

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. 

---