A scheduling algorithm based on data availability for behavioral VLSI synthesis
Jong-Soo Kim · 1995
High-level synthesis of digital circuits concerns automatic translation of a behavioral description of a design to a structural design entity represented in terms of components and connections. One of the critical steps in high-level synthesis is to determine the particular scheduling algorithm that will provide the most efficient implementation. This dissertation presents a new scheduling algorithm which distributes the operations specified in the behavioral description into a set of states and generates a finite state machine control circuit. It minimizes the number of states required using data availability and dependency conditions extracted from the behavioral code. Behavioral code may contain nested loops, conditional branches and wait statements. The new scheduling algorithm presented is efficient because data availability conditions and conditional and wait statements break the behavioral code into manageable pieces which are analyzed independently. It satisfies arbitrary resource and chaining constraints, but it is not meant to perfectly optimize the schedule of operations between state transitions. If necessary, these descriptions may be optimized using existing algorithms, such as integer linear programming, after the proposed algorithm has identified the necessary states. The new algorithm is therefore more suitable to behavioral descriptions which can be scheduled into multiple states with relatively few operations. A comparison of the new versus the path-based algorithm shows that the new algorithm produces a schedule with fewer or equal number of states in less computation time.