On area-efficient drawings of rectangular duals for VLSI floor-plan
On area-efficient drawings of rectangular duals for VLSI floor-plan
复制标题
VLSI 平面图的矩形对偶面积有效绘图
DOI：
10.1007/bf01582878
复制
发表时间：
1988
影响因子：
2.7
通讯作者：
I. Shirakawa
中科院分区：
文献类型：
--
作者：
K. Tani;S. Tsukiyama;S. Shinoda;I. Shirakawa
本文考虑一个矩形对偶及其面积有效作图问题，使得在每个面的面积和最小尺寸以及相邻两个面之间的邻接长度都受到约束的情况下，能在所有矩形对偶中面积最小的矩形对偶上作图。由于这个问题很难解决，我们解决这个问题，在一个穷举的方式，通过使用一个算法来枚举所有的长方形。为了使这种详尽的方法有效，我们提出了以下两个算法工作在上述约束条件下，一个算法找到一个面积有效的图纸一个给定的矩形对偶，和一个算法来估计一个下界绘制一个给定的矩形对偶所需的面积。我们也给出了一些实验结果来证明下界的有效性。的面积有效图可作为VLSI布图，它把的每个内表面看作一个放置块的区域。
In this paper, we consider a problem to seek a rectangular dualand its area-efficient drawing such thatcan be drawn in the smallest area among all rectangular duals under the constraints imposed not only on the area and the minimum dimension of each face but also on the length of abutment between two adjacent faces. Since the problem is hard to solve, we tackle this problem in an exhaustive manner by using an algorithm to enumerate all the rectangular duals. In order to make this exhaustive method efficient, we propose the following two algorithms working under the constraints stated above; an algorithm to find an area-efficient drawing of a given rectangular dual, and an algorithm to estimate a lower bound to the area required to draw a given rectangular dual. We also show some esperimental results to demonstrate the effectiveness of the lower bound. The area-efficient drawing ofcan be used as a VLSI floor-plan by regarding each inner face ofas an area for a block to be placed.