Browsing by Author "Chang, Shu-Hsin"

Now showing 1 - 2 of 2

Critical-Trunk Based Obstacle-Avoiding Rectilinear Steiner Tree Routings for Delay and Slack Optimization
(2009)
Lin, Yen-Hung
;
Chang, Shu-Hsin
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
Obstacle-avoiding rectilinear Steiner tree (OARST) construction is a fundamental problem associated with the trend toward IP-block-based System-on-Chip designs. The objective of previous studies on obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) has been to minimize the total wirelength of the constructed Steiner tree. Studies of performance-driven Steiner trees have demonstrated that the minimization of wirelength may worsen the performance of the Steiner tree. This work is the first to construct OARST while considering the Elmore delay. A critical-trunk-based tree growth mechanism is proposed. The critical trunks are constructed by extended single-source single-target maze routing called multi-source single-target maze routing. The unconnected pins are connected to critical trunks under the delay constraints of every sink. The proposed critical trunk can be applied to solve performance-driven and slack-driven OARST problems. Experimental results demonstrate that the proposed algorithms achieve an average 24.12% improvement in the maximum delay over OARSMT in performance-driven OARST problem and successfully solve 66.67% worst negative slack (WNS) violations in slack-driven OARST problem while running faster than previous OARSMT algorithms.
Critical-Trunk-Based Obstacle-Avoiding Rectilinear Steiner Tree Routings and Buffer Insertion for Delay and Slack Optimization
(2011-09-01)
Lin, Yen-Hung
;
Chang, Shu-Hsin
;
Li, Yih-Lang
;
交大名義發表
;
National Chiao Tung University
For modern designs, delay optimization significantly facilitates success in design closure owing to its more realistic metric than wirelength in routing. Obstacle-avoiding rectilinear Steiner tree (OARST) construction is an essential routing problem. With the trends toward Internet protocol-block-based system-on-chip designs, OARST with buffer insertion has been surveyed to diminish the delay of long wires. Previous works on performance-driven (PD) OARST without and with buffer insertion can only handle small circuits. This paper develops a novel routing algorithm in obstacle-avoiding spanning graph to construct OARST with optimized delay efficiently. The proposed multisource single-target maze routing is first employed to identify the critical trunks, and the critical-trunk-based tree growth mechanism connects the unconnected pins to critical trunks under delay constraints of every sink. We apply the proposed critical-trunk-based tree growth mechanism to solve PD and slack-driven (SD) OARST problems. The proposed algorithms are extended to consider buffer insertion during PD and SD OARST constructions. Experimental results demonstrate that the proposed algorithms achieve an average 25.84% improvement in the maximum delay over obstacle-avoiding rectilinear Steiner minimal tree in the PD OARST problem and successfully solve 66.67% worst negative slack violations in the SD OARST problem. Compared to the simultaneous routing and buffer insertion approach, the proposed buffer-aware (BA) algorithm generates satisfactory timing results with almost identical wire length (WL). Moreover, the proposed BA SD OARST algorithm utilizes less WL than the BA rectilinear Steiner tree construction does by 17.99% on average. The runtime comparison with previous works shows the efficiency and scalability of this paper.