Combinatorial Algorithms for Integrated Circuit Layout (Repost)

The layout of integrated circuits on chips and boards is a complex task. A major portion of the research in the area of design automation has been devoted to the development of efficient and easy-to-use systems that support circuit layout. There are two aspects of building a layout system that are difficult. One is the combinatorial aspect and the other is the systems aspect. The combinatorial aspect is that most of the optimization problems that have to be solved during integrated-circuit layout are intractable.
More specifically, they are usually NP- hard (a notion that will be defined rigorously in Section 2.2) or harder. This observation implies that finding the optimal solution for each given problem instance in reasonable time is out of the question. We have to find other ways of solving the problem adequately. The systems aspect deals with all problems that remain, once the combinatorial problems have been solved. Among those are the maintenance of the consistency in the design database in the presence of simultaneous changes of the same design object, the development of an ergonomic and robust human interface, and the appropriate guidance through a partially interactive design process.
Both aspects of complexity are equally important, and they strongly influ- ence each other. As an example, an efficient algorithm that optimally solves a combinatorial layout problem such as block placement obviates the necessity of providing designer guidance through an interactive process of iteratively im- proving a heuristically found placement. On the other hand, a certain model of the design process leads to specific combinatorial problems that do not have to be solved in other design scenarios. For instance, in highly interactive design systems, dynamic versions of combinatorial problems prevail.