VLSI/PCB placement with obstacles based on sequence pair

In a typical very large scale integration/printed circuit board (VLSI/PCB) design, some modules are preplaced in advance, and the other modules are requested to be placed without overlap with each other and with these preplaced modules. The presence of such obstacles introduces inconsistency to a coding scheme, called sequence pair, which has been proposed for an obstacle free placement problem. We solve this difficulty by proposing a procedure called "adaptation" which transforms an inconsistent sequence pair to a consistent one with the utmost consideration for minimizing the modification. It is shown that a simulated annealing is well organized so that it tests only feasible placements by the adaptation procedure. As a design example, a Microelectronics Center of North Carolina (MCNC) benchmark data "ami49" is packed with treating ten modules among 49 modules as preplaced ones. Further, a PCB example which includes 32 free modules and four preplaced modules (connectors) is laid out successfully by our method with a conventional wiring estimation followed by a commercial router.