CAJ | 학술논문

针对水平约束图为星图的具有曼哈顿模型的通道布线，提出了一个依据图论模型的最优轨道高度布线算法。该算法根据通道上结点的水平约束图和垂直约束图特点，依次安排好每一个结点的布线轨道，进而通过通孔可以把所有的结点在2层轨道上布线完成。通过计算分析，该算法能够达到最优的布线高度。
침대수평약속도위성도적구유만합돈모형적통도포선，제출료일개의거도론모형적최우궤도고도포선산법。해산법근거통도상결점적수평약속도화수직약속도특점，의차안배호매일개결점적포선궤도，진이통과통공가이파소유적결점재2층궤도상포선완성。통과계산분석，해산법능구체도최우적포선고도。
For a channel in 2-layer Manhattan model with horizontal constraint graph be star, we aim at interconnecting the terminals of each net by wires such that the circuit elements and the interconnecting wires are embedded into two planar layers by the methods of graph theory. Furthermore, the width (number of tracks required for routing) of a channel should be minimized. The constraints of a channel routing problem can be represented by a horizontal constraint graph (HCG) and a vertical constraint graph (VCG). Consider the two constraints, we improve the upper bound, we show that our algorithm can be obtain the best width.