In a typical VLSI/PCB design, some modules are pre-placed in advance, and the other modules are requested to be placed without overlap with these pre-placed modules. The presence of such obstacles introduces inconsistency to a coding scheme, called a sequence-pair which has been proposed for an obstacle free placement problem. We solve this difficulty by proposing a procedure, called "adaptation", which transforms inconsistent sequence-pair to a consistent one, with utmost consideration for minimizing the modification. It is shown that a simulated annealing is well organized to test only feasible placements with the adaptation procedure. Using the adaptation, an MCNC benchmark data, ami49 is packed with 20% of the modules being pre-placed. Further, a PCB example which includes 32 free modules and 4 pre-placed modules (connectors) is laid out successfully by our method with a conventional wiring estimation followed by a commercial router.
Paper Location
Citation
[1] H. Murata, K. Fujiyoshi, and M. Kaneko, "VLSI/PCB placement with obstacles based on sequence-pair," Proceedings of the 1997 international symposium on Physical design, ACM New York, NY, USA, 1997, p. 26–31.
Positive
- Strong formalization of the adaptation algorithm.
- Fair background section, covers the problems with the current state-of-the-art at the time of writing.
- Clear example of how the algorithm works presented.
- Times clearly shown and packing efficiency displayed in table format against competing packers
Negative
- Claims higher complexity of an algorithm in the main text, only to point out that current state-of-the-art is better in the footnotes. This is slightly disingenuous to the casual reader.
- Omits proof of its first lemma (likely due to space constraints) but fails to point out a place to obtain aforementioned proof.
- Uses "End of Proof" symbol in a place where the proof was omitted. Misleading.
- Poor use of "Dominated" terminology. A better term more befitting of the case is certainly available.
No comments:
Post a Comment