September 2 – 6 , 1991, Dagstuhl Seminar 9136

Theory and Practice of Physical Design of VLSI Systems


T. Lengauer, R. Möhring, B. Preas

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 20


The Workshop on the Theory and Practice of Physical Design of VLSI Systems intended to bring together practitioners and theoreticians that work in this important field of design automation. Physical design has experienced impressive development within the last decade. Driven by the explosive growth in the technology for manufacturing integrated circuits, combinatorial methods have been developed that aim at structuring and optimizing the process of physical design. Early on, it has become apparent that sophisticated mathematical techniques would have to be developed and applied in order to handle the range of complexity of the relevant optimization problems. Thus, activities have been spawned in a wide range of communities spanning the entire spectrum from theory to practice.

Driven by the demands of industrial applications, there has been a lot of research aimed at quick but (hopefully) effective solutions to the immediate design problems. Typically, such research involves the development of robust models that capture the characteristics of the application domain and the application of universal and well understood heuristic techniques of optimization. The validation of the research is done by benchmarking or similar experimental evidence of how well the approach fits the application.

Driven by the activities in the practical research communities, more mathematically oriented researchers that are more distant to the application have conducted research on the algorithmic engines that might be at the core of several families of optimization problems in physical design automation (placement, routing, compaction, cell generation etc.).

This workshop intended to enhance the communication between these two research communities. This is important such that practitioners become aware of the new optimization technology at hand and that theoreticians choose models and investigate questions that are relevant to practical applications. To our knowledge, this was the first workshop that was specifically aimed at bringing together theory and practice of physical design.

The lively and sometimes heated discussions and exchanges of ideas during the workshop gave evidence for the fact that both communities have to tell each other a lot and that there is need of more exchange between them. The list of talks shows that a wide range of subjects and methods was covered. The list of attendees reflects the pluralistic character of the workshop. It was apparent that many attendees got substantially new impulses to motivate and critically evaluate their future research.

The excellent surroundings of the workshop at Schloß Dagstuhl provided an atmosphere that was conducive to frank personal interaction. The organizers wish to thank all those who helped make this workshop an interesting and successful research experience.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.