Extended Abstracts of the 18th Symposium on Operation Research, Cologne, Germany, September 1-3, 1993.
The high-level synthesis task is to take a specification of the behavior required of a system and a set of constraints and goals to be satisfied, and to find a structure that implements the behavior while satisfying the goals and constraints. The main step of the high-level synthesis includes operation scheduling and hardware allocation. Since these two tasks are essential in high-level synthesis they have been studied extensively and a variety of algorithms have been published. The scheduling and allocation are closely interrelated. In order to have an optimal design, both tasks should be performed simultaneously. However, due to the time complexity, many systems perform them separately or introduce iteration loops between the two subtasks. Roughly speaking, operation scheduling determines the cost-speed tradeoffs of the design while allocation involves assigning the operations and values to hardware, i.e., providing storage, function units, and communication paths, and specifying their usage. We will first describe two transformational scheduling algorithms. Integer linear programming algorithm implicitly uses branch-and-bound techniques for selection of transformations. An example of a heuristic based transformational scheduling algorithm is Simulated annealing based algorithm. Next we describe two iterative/constructive scheduling algorithms which belong to the list scheduling algorithms. The first one is the Force directed algorithm; it uses force as a priority function. The second one, developed by author, named Global arc minimization algorithm, uses a complex priority function based on critical paths and operation's neighborhood.