FORCE-DIRECTED SCHEDULING IN AUTOMATIC DATA PATH SYNTHESIS P.G. PAULIN' - J.P. KNIGHT' l Dept. 5L40, Bell-Northern Research P.O.Box 3511, Stn C, Ottawa, ONT. KlY 4H7 ' Carleton University, Colonel By Dr, Ottawa, ONT. KlS 5B6 ABSTRACT The HAL system performs data path synthesis using a new scheduling algorithm that 1s part Of an interdependent scheduling and allocation scheme. This scheme uses an BStl- mate of the hardware allocation to guide and optimiza the scheduling subtask. The allocation information includes the number. type. speed and cost of hardware modules as well as the associated multiplexer and interconnect costs. The iterative force-directed scheduling algorithm attempts to balance the distribution of operations that make use Of the same hardware resources: . Every feasible control step assignment is evaluated at each iteration, for a11 operations. . The associated side-effects on all the predecessor and successor operations are taken Into account. . All the decisions are global. . The algorithm has O(n*) complexity. We review and compare existing scheduling techniques. Mod- erate and difficult examples are used to illustrate the ef- fectiveness of the approach. 1. INTRODUCTION In the automatic design of application specific integrated circuits. the alaorithmic deSCriDtiOn is common1 y datapath and a- synthe- sized Into a control path. Scheduling datapath operations into the best control steps is a task whose importance has been recognized in many systems It.2.3.4.51. According to Gajski [I], it is “perhaps the single most important step during the architecture synthe- SiS”, IroniCally, it is also the one that has received the least attention in current literature. (Notable exceptions are the papers presented by Alice Parker’s group at the Uni- versity of Southern California [2.3) and by Emil GirczyC Of the University of Alberta 141). operation scheduling determines the serial/parallel nature of the design and approximates cost-speed trade-offs t61. If the design Is subjected to a speed constraint, the sched- Ul ing algorithm will attempt to make sufficient operations run In parallel to meet the constraint. Conversely, if there is a limit on chip area. the scheduler can be asked to Serial iae operations to give the maximum speed consistent with the canstraint. The scheduling task is an important one as it affects four fundamental aspects of the subsequent synthesis process: i This research was funded in part by grants from the Na- tural Sciences and Engineering Research Council. Canada (NSERCC) and from Bell-Northern Research. Ottawa. Permission 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. . The number and type of PrOCeSSOM allocated . The timing constraints on these processors . The storage requirements . The data transfer requirements The HAL system is composed of three main modules that were described In 151. The InHAL module uses a novel force- directed scheduling algorithm that attempts to balance the distribution of operations that make use of the same hard- war-e resources. This algorithm also allows specific allo- catlon information. such as the propagation delay of a specific standard Cell, to be used when optimizing the scheduling process. The MidHAL module performs the hardware allocation while the final interconnection and optimization step is realized by the ExHAL module. We will first review existing scheduling techniques and com- pare them with the approach used in the HAL System. This will be followed bv a algorithm descriDtion Of the force-directed scheduling that is’the main emphasis of this pa- per. We will then demonstrate how processor allocation in- formation is integrated into the scheduling process. Finally, we present experlmental results for moderate and difficult problems taken from current literature. 2. LITERATURE SURVEY The simplest way to perform scheduling is to relegate the task to the user. This is the aDDrOaCh favored bv the SilC system [7] under the assumption that the user should explic- itly define the parallelism of the design. Independent scheduling/allocation schemes: The next simplest scheme is to schedule operations “as soon as possible” (ASAP) as is done in the Emerald/Facet system [Sl. This technique has proved useful in the Past for near- optimal microcode compaction (91. A refinement of this concept is ASAP scheduling with condi- tional postponement of operations. the MIMOLA (101, this occurs whenever the o$ration con~urre%~~?~ higher than the number of available processors. The recently published Flame1 system (17) uses the same idea. The Scheme used in Kung, Whltehouse and Kailath’s book on digital sig- nal processing (11) is similar, except that an operation is postponed when it blocks a later one with a lower “BE late as possible” (ALAP) level. Continuing along the scale of increasing complexity, we have the algorithms that USQ list scheduling. as described in [91. The behavioral synthesis of interfaces (BSI) system developed by Nestor [12). the SLICER system developped by Pangrle and Gajski t13) and the BUD-DAA system [I41 use this type of approach. In list scheduling. operations are sorted in topological or- der (top to bottom) by “sing the precedence relations dic- tated by data and control operations dependanGleS. The sorted are then iteratively. scheduled into control steps. The order in which they are placed into a control step is determined by a heuristic priority function