HIERARCHICAL FLOORPLANNING FOR VLSI BUILDING BLOCK LAYOUT

VLSIビルディングブロックレイアウトのための階層化フロアプランニング

Ohmura Michiroh

Over the past three decades, the remarkable growth of the semiconductor industry has been continued, which started from the invention of the transistor, and now realizes an industry that is all-pervasive in its effect on modern life. Moore's law shows a resultant doubling of circuit complexity each year. With the increase of the demand to integrate the whole system into one VLSI chip, Application Specific Integrated Circuit (ASIC) has emerged since early 1980s. In addition to the reduction of the design period and the cost, designing the high performance ASIC with millions of gate circuits will require a new Computer Aided Design (CAD) method.

This dissertation discusses hierarchical floorplanning for VLSI building block layout, and proposes a new hierarchical floorplanning method combined with global routing and positioning.

In Chapter 1, the outline of the VLSI layout design is discussed as a background of hierarchical floorplanning. In particular, placement and floorplanning in the VLSI layout design are explained in detail.

In Chapter 2, hierarchical floorplanning is explained in detail. First, conventional hierarchical floorplanning methods are introduced. Then difficulties of these floorplanning methods are pointed out. Finally, a new hierarchical floorplanning method combined with global routing and positioning is proposed, and the outline of this method is mentioned.

In Chapter 3, some theoretical results concerning the proposed hierarchical floorplanning method are discussed. The first result is an initial placement method by the ideal distance, which is a newly introduced concept. The second result is overlap resolution in which relative positions of modules are preserved. This is formulated as an overlap resolution problem and proved to be NP - complete. A heuristic algorithm is also given. The third result is improvement of one dimensional module placement. This is formulated as the improvement problem and for this problem, an optimum algorithm and its proof are given.

The proposed hierarchical floorplanning consists of the initial floorplanning and the detailed floorplanning. In Chapter 4, algorithms of each phase in the initial floorplanning and the detailed floorplanning are explained with some experimental results, which verify the effectiveness of these algorithms.

In Chapter 5, a prototype system FLORA II, which is constructed based on the proposed hierarchical floorplanning method, is introduced, and some experimental results concerning the hierarchical floorplanning system FLORA II are given. Not only floorplans but also final layouts after global routing is compared with a conventional method.

Finally, the conclusions of this dissertation and the future research works are discussed in Chapter 6.

Electrical engineering [ 540 ]

eng

Copyright(c) by Author

広島大学