1. Placement Problem of I/O Blocks with Constraints on Size and Shape in VLSI.
- Author
-
Fujii, Takashi, Kikuno, Tohru, and Yoshida, Noriyoshi
- Subjects
- *
ELECTRIC circuits , *INTEGRATED circuits , *ELECTRONIC circuits , *INFORMATION retrieval , *BLOCK designs , *ELECTRICAL engineering - Abstract
In the building block approach it is difficult to estimate the size of a circuit (a set of blocks) which can be implemented on a chip, based only on the areas of blocks and the chip area. Consequently, in the layout design by this approach, not only the area of each block, but also its shape and size must explicitly be taken into account. This paper discusses the placement of relatively small-sized blocks (I/O blocks) which realize the specified input-output function. The I/O block is assumed to have a rectangular shape, and some restriction is imposed on the edge lengths. In the placement of the I/O blocks, the given I/O blocks are converted into unit blocks with the standard sizes, and the placement is performed for the unit blocks. For the placement of unit blocks, the following results are obtained. For a set of unit blocks U and a set of rectangular regions I, the necessary and sufficient condition is derived for the existence of the placement of U on I. Then an algorithm is given which determines the placement for given U and I satisfying the condition in 0(∣U∣ + ∣I∣ log ∣I∣) time. [ABSTRACT FROM AUTHOR]
- Published
- 1988