Scheduling and Binding Algorithms for High-Level Synthesis Pierre G. Paulin Bm, PO. Box 35 11, Sm. “C” Ottawa, Canada KlY 4H7 John P. Knight Carleton Univ., Dept. of Electronics, Ottawa, Canada KlS 5B6 Abstract - New algorithms for high-level synthesis are presented. The first performs scheduling under hardware resource constraints and improves on commonly used list scheduling techniques by making use of a global priority function. A new design-space exploration technique, which combines this algorithm with an existing one based on time constraints, is also presented. A second algorithm is used for register and bus allocation to satisfy two criteria: the minimization of interconnect costs as well as the final register (bus) cost. A clique partitioning approach is used where the clique graph is pruned using interconnect affinities between register (bus) pairs. Examples from current literature were chosen to illustrate the algorithms and to compare them with four existing systems. 1. Introduction As logic and RTL-level synthesis tools gain a stable foothold in industry, the automatic synthesis of a digital system from a behavioral description - high-level synthesis - is the next step on the ladder of the design automation hierarchy. A tutorial on the subject is given in [McPC88]. The interest in high level synthesis is a natural consequence of the shift of IC designers’ involvement away from device-level considerations and towards architectural ones. In this paper, we will present algorithms that solve two difficult tasks in high-level synthesis, namely scheduling under resource constraints and register/bus allocation to minimize interconnect costs. These algorithms, originally implemented in the HAL system [Pau186], [Pau187], can also be integrated into specialized or general purpose high-level synthesis systems. 2. Scheduling under Resource Constraints In the context of high-level synthesis, scheduling [McPC88] consists of determining a propagation delay for every operation of the input behavioral description and then assigning each one to a specific control-step (a c-step is often equivalent to a single state of an FSM). One commonly used approach is a list scheduling (LS) technique where a hardware constraint is specified and the algorithm attempts to minimize the total execution time by using a local priority function to defer operations when resource conflicts occur. I’ennission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. A different approach, force-directed scheduling (FDS) was presented in [Pau187] and reimplemented by other groups in academia [Clou87], [StokSS] and industry [Fuhr88]. In this approach, a global time constraint is specified and the algorithm attempts to minimize the resources required to meet that constraint. This formulation of constraints is useful for DSP applications where system throughput is fixed and area must be minimized. The main strength of the algorithm was the use of a global measure of concurrency to guide the scheduling. As its name implies, the force-directed list scheduling (FDLS) algorithm presented here combines the characteristics and strengths of both force-directed and list scheduling. Like the former, it uses a global measure of concurrency throughout the scheduling process. Furthermore. it can be used when a predefined number of functional units of any type is specified. In the next subsection, we will give a quick review of the main concepts of the FDS algorithm (refer to [Paul871 or [Paul891 for details) while focusing on the common elements of the new FDLS algorithm presented further. 2.1 A review of Force Directed Scheduling The intent of the force-directed scheduling algorithm is to reduce the number of functional units, registers and buses required, by balancing the concurrency of the operations assigned to them, but without lengthening the total execution time. This is achieved using the three step algorithm summarized below. Determination of time frames: The first step consists of determining the time frames of each operation by evaluating the ASAP (as soon as possible) and ALAP schedules. This determines the possible time frames for each operation, as depicted in Fig. 2.1 for the differential equation (DiffEq) example of [Pau187]. The width of the box containing a particular operation represents the probability that the operation will be eventually placed in a given time slot. Uniform probabilities are assumed. Creation of Distribution Graphs: The next step is to take the sum of the probabilities of each type of operation for each c-step of the CDFG. The resulting distribution graphs (DGs) indicate the concurrency of similar operations. For each DC the distribution in c-step i is given by: DC(i) = c Prob(Opn, i) Opn type (1) where the sum is taken over all operations of a given type. Using Fig. 2.1, we can calculate the values of the multiplication DC. This yields: DC(l) = 2.833, DG(2) = 2.333, DG(3) = 0.833 and DG(4) = 0. Force calculation: The final step is to calculare the force associated with every feasible c-step assignment of each operation. This is done by temporarily reducing the 26th ACM/IEEE Design Automation Conference@ Paper 2.1 0 1989 ACM O-89791 -31 O-8/89/0006/0001 $1.50 1operation’s time frame to the selected c-step. The force associated with the reduction of an initial time frame (bounded by c-steps t and b) to a new time frame (bounded by c-steps nt and
View Full Document
Unlocking...