courseware Force-Directed Scheduling Sune Fallgaard Nielsen

courseware Force-Directed Scheduling Sune Fallgaard Nielsen Informatics and Mathematical Modelling Technical University of Denmark Richard Petersens Plads, Building 321 DK2800 Lyngby, Denmark

Overview / Agenda Motivation Introduction Defining problem and model Solution Results Conclussion SoC-MOBINET courseware [M-1] High-Level Synthesis 2

Motivation The mapping from a behavioral model to a physical Register-Transfer level description is a NP-complete problem. Therefore an exhaustive comparison on all possible solutions is infeasible. An algorithm finding an efficient mapping is required. SoC-MOBINET courseware [M-1] High-Level Synthesis 3

Introduction The paper was written in 1989. The interest on High-Level Languages like VHDL is increasing at that time. Synthesis tools capable of generating a RTL realization from a behavioral model is needed. SoC-MOBINET courseware [M-1] High-Level Synthesis 4

Introduction Mathematical domain specification create a model of the physical problem specification synthesis create an alogorithm to solve the problem design implementation Transform the optimized model back to the physical domain implementation Physical domain SoC-MOBINET courseware [M-1] High-Level Synthesis 5

Introduction Mathematical domain specification create a model of the physical problem specification synthesis create an alogorithm to solve the problem design implementation Transform the optimized model back to the physical domain implementation Physical domain SoC-MOBINET courseware [M-1] High-Level Synthesis 6

Defining problem and model The problem: For a given function, find an optimal solution. An optimal solution can be constrainted by area-, power-, performance- or flexibility requirements depending on the application. The model: Scheduling : Determine for each operation the time at which it should be performed without violating any precedence contraints. SoC-MOBINET courseware [M-1] High-Level Synthesis 7

Solution Common Approach List Scheduling New Approach Force-Directed Scheduling Resources given Minimize delay resources SoC-MOBINET courseware Time contraints given Minimize required [M-1] High-Level Synthesis 8

Solution Common Approach List Scheduling New Approach Force-Directed Scheduling Resources given Minimize delay resources SoC-MOBINET courseware Time contraints given Minimize required [M-1] High-Level Synthesis 9

Force-Directed Scheduling The Force-Directed Scheduling approach reduces the amount of: Functional Units Registers Interconnect This is achieved by balancing the concurrency of operations to ensure a high utilization of each unit. SoC-MOBINET courseware [M-1] High-Level Synthesis 10

Force-Directed Scheduling The Force-Directed Scheduling algorithm consists of 3 steps: 1. Determine a time frame of each operation 2. Create a distribution graph 3. Calculate the force (a new metric) SoC-MOBINET courseware [M-1] High-Level Synthesis 11

Scheduling – An example Solve the differential equation y’’ 3zy’ 3y 0 This can be calculated using this iterative algorithm while(z a) repeat zl : z dz; ul : u – (3 · z · u · dz) – (3 · y · dz); yl : y (u · dz); z : zl; u : ul; y : yl; SoC-MOBINET courseware [M-1] High-Level Synthesis 12

Scheduling – An example Data-Flow and Control-Flow Graphs ASAP Scheduling ALAP Scheduling SoC-MOBINET courseware [M-1] High-Level Synthesis 13

Scheduling – An example Data-Flow and Control-Flow Graphs ASAP Scheduling ALAP Scheduling SoC-MOBINET courseware [M-1] High-Level Synthesis 14

Scheduling – An example Step 1 : Determine a time frame of each operation Error in Figure SoC-MOBINET courseware [M-1] High-Level Synthesis 15

Scheduling – An example Step 2 : Create a distribution graph DG(1) 2.833 DG(2) 2.333 SoC-MOBINET courseware [M-1] High-Level Synthesis DG(3) 0.833 DG(4) 0 16

Scheduling – An example Step 3 : Calculate the force (a new metric) A metric called force is introduced. The force is used to optimize the utilization of units. A high positive force value indicates a poor utilization. b DG (i ) Force ( j ) DG ( j ) i t (b t 1) SoC-MOBINET courseware [M-1] High-Level Synthesis 17

Scheduling – An example Step 3 : Calculate the force (a new metric) Free Fixed SoC-MOBINET courseware [M-1] High-Level Synthesis 18

Scheduling – An example Step 3 : Calculate the force (a new metric) With the operation x’ in control-step 1. 2 DG (i ) Force (1) DG (1) 2 i 1 2.833 2.333 2.833 0.25 2 DG(1) 2.833 DG(2) 2.333 SoC-MOBINET courseware [M-1] High-Level Synthesis DG(3) 0.833 Poor utilization DG(4) 0 19

Scheduling – An example Step 3 : Calculate the force (a new metric) With the operation x’ in control-step 2. (x’’ must be in control-step 3) Force(2) DG (2) 2 i 1 DG (i ) DG (3) 2 3 i 2 DG (i ) 2 2.833 2.333 0.833 2.333 2.333 0.as 833 1 Direct forceIndirect (calculated before) force (on x’’ in control-step 3) 2 2 DG(1) 2.833 DG(2) 2.333 SoC-MOBINET courseware [M-1] High-Level Synthesis DG(3) 0.833 Good utilization DG(4) 0 20

Scheduling – An example By repeatedly assigning operations to various control-steps and calculating the force associated with the choice several force values will be available. The Force-directed scheduling algorithm chooses the assignment with the lowest force value, which also balances the concurrency of operations most efficiently. SoC-MOBINET courseware [M-1] High-Level Synthesis 21

Force-Directed Scheduling The Force-Directed Scheduling approach reduces the amount of: Functional Units Registers Interconnect By introducing Registers and Interconnect as storage operations, the force is calcuted for these as well. The 3 steps of the algorithm are carried out for these operations also. SoC-MOBINET courseware [M-1] High-Level Synthesis 22

Force-Directed Scheduling SoC-MOBINET courseware [M-1] High-Level Synthesis 23

Force-Directed Scheduling Introducing Registers and Interconnect as operations. Since the Registers and Interconnect area consumption is reduced in solution b, it might be optimal. SoC-MOBINET courseware [M-1] High-Level Synthesis 24

Force-Directed List Scheduling List Scheduling Force Directed Scheduling Resources given Minimize delay resources Time contraints given Minimize required If the problem is the other way around, ie. if the resources are given a Force-Directed List Scheduling algorithm can be applied. SoC-MOBINET courseware [M-1] High-Level Synthesis 25

Force-Directed List Scheduling The Force-Directed List Scheduling utilizes the strengths of the: Force-Directed Scheduling and List Scheduling Force-Directed List Scheduling is similar to List Scheduling except force is the priority function, not mobility. SoC-MOBINET courseware [M-1] High-Level Synthesis 26

Force-Directed List Scheduling List Scheduling Force-Directed List Scheduling Mobility is a poor metric Force is a better metric We have 1 adder and 1 multiplier SoC-MOBINET courseware [M-1] High-Level Synthesis 27

Results Test Application : Fifth-order Elliptic Wave Filter Many optimal depending on the application One result, ASAPresults, is not optimal. xp is a pipelined multiplier SoC-MOBINET courseware [M-1] High-Level Synthesis 28

Results – The Design Space The Force-Directed List Scheduling gives better means for exploring the design space. It offers many results and depending on the application the designer can choose to use more or less resources and see what implications it will have on the delay. SoC-MOBINET courseware [M-1] High-Level Synthesis 29

One more optimization The Force-Directed List Scheduling is implemented in a system called HAL. HAL also uses techniques called register merging and multiplexer merging. These techniques minimizes the cost on registers and interconnections. SoC-MOBINET courseware [M-1] High-Level Synthesis 30

Results Comparison on various syntesis tools normalized to HAL86 Test Application : Differential Equation Non-pipelined Multiplier Pipelined Multiplier SoC-MOBINET courseware [M-1] High-Level Synthesis 31

Results Physical unit and interconnection requirements Test Application : Wave Filter SoC-MOBINET courseware [M-1] High-Level Synthesis 32

Conclussions The Force-Directed Scheduling and Force-Directed List Scheduling algorithms allows the designer to explore the design space. By taking into account the cost of interconnection, registers and multiplexers a more precise algorithm is realized. The HAL system, using these algorithms, shows promising results compared to other systems. SoC-MOBINET courseware [M-1] High-Level Synthesis 33