Algorithms for operation scheduling in VLSI circuit design

The problem of automatically obtaining the layout of a circuit starting with a purely behavioural specification has been receiving growing attention during the last few years. Several reasons explain this interest, but the main one is the great amount of computing power that can now be integrated in a single device. Modern microelectronic technology allows the realisation in a small area of a great number of functions, enabling the production of very large circuits, whose design cannot be managed properly by traditional tools. So the requirement for new CAD tools, able to assist the designer in the definition of the circuit and to perform complex optimisation tasks is becoming-more and more urgent. While the problems involved in layout definition, floor-planning and channel routing are well known and are solved in several commercially available tools, the automatic design of a VLSI architecture is a much newer matter. In the paper a new algorithm solving one of the main subproblems of the high level synthesis, the operation scheduling, is presented. It is based on a general and flexible probabilistic model, able to manage a wide set of different constraints and optimisation aspects. It is proved, using the main benchmarks available in the literature, that the algorithm gives results comparable with or better than, the best ones published, showing a low time complexity