SALSA: a new approach to high-level synthesis
Ganesh Krishnamoorthy · 1992
High-level synthesis takes a behavioral specification of a digital system expressed in a hardware description language plus a set of constraints and automatically generates a register-transfer level design that implements the behavior. The two most important tasks in synthesis are: scheduling and allocation. Scheduling determines when an operator in the behavioral specification will execute. Allocation maps operators in the behavior to functional units, values to registers, and data transfers to interconnections between resources. This dissertation describes a new approach to synthesis that generates designs that satisfy behavioral constraints while using minimum hardware resources. This approach uses constraint satisfaction algorithms to generate an initial schedule that meets ordering and timing constraints. The initial schedule is then improved using simulated annealing. A new representation for synthesis has been developed that allows efficient exploration for low-cost schedules while satisfying constraints. This representation also includes allocation information and allows new allocation trade-offs which are not possible in the classical representation. Once a low-cost schedule is found allocation is completed in a two step process. A constructive algorithm based on greedy heuristics is used to generate an initial allocation. The initial allocation is improved through an iterative improvement technique similar to simulated annealing. This approach has been successful in generating very high quality designs.