tailieunhanh - Handbook of algorithms for physical design automation part 22

Handbook of Algorithms for Physical Design Automation part 22 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 192 Handbook of Algorithms for Physical Design Automation Transformation from Q-sequence to floorplan 1. Initialize the floorplan with block n. 2. For i n - 1 to 1 do Let I i be the Q-state of block i. 3. If I i contains R s 4. Add block i from the left of the chip pushing aside top mi blocks where mi is the number of R s in I i that are adjacent to the left boundary of the chip. 5. If I i contains B s 6. Add block i from the top of the chip pushing down leftmost mi blocks where mt is the number of B s in I i that are adjacent to the top boundary of the chip. FIGURE Transformation from Q-sequence to floorplan. Extended Q-Sequence The Q-sequence representation is extended 5 to allow empty room insertion to include the optimal packing in the solution space. It is proven that at most n - _V4n - 1J empty rooms are needed to represent any packing and the size of the solution space will become 26n 2n n if empty rooms are included. A new move to perturb a floorplan by making use of a parenthesis tree pair is introduced to improve the packing performance. A linear-time decoding algorithm to realize a floorplan from a Q-sequence is given in Figure and an example that illustrates the decoding steps is shown in Figure . New Move Based on Parenthesis Constraint Tree The R parenthesis tree of a Q-sequence is obtained by representing the corresponding RQ-sequence in the form of a tree such that each node represents a pair of parentheses corresponding to a room. We label the R corresponding to the open parenthesis of room i by R for i 1 . n. An example is shown in Figure . The B parenthesis tree can be constructed similarly from the BQ-sequence and the B s are also labeled from 1 to n accordingly. Parenthesis trees have the following properties 5 R 6 a 4 R 5 6 b 3 6 vB 4 B 5 c 2 B 3 B 6 4 5 d 1 R2 R3 6 4 5 e 1 2 3 6 4 5 f FIGURE Example of realizing a floorplan from its Q-sequence RRBB1RR2BB3BB4R5R6 showing a the floorplan after adding