An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire le...An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire length model is implemented on multiprocessor,which enables the algorithm to approach feasibility of large scale problems.Timing driven model on multiprocessor and wire length model on distributed processors are also presented.The parallel algorithm greatly reduces the run time of routing.The experimental results show good speedups with no degradation of the routing quality.展开更多
A global routing algorithm with performance optimization under multi constraints is proposed,which studies RLC coupling noise,timing performance,and routability simultaneously at global routing level.The algorithm is...A global routing algorithm with performance optimization under multi constraints is proposed,which studies RLC coupling noise,timing performance,and routability simultaneously at global routing level.The algorithm is implemented and the global router is called CEE Gr.The CEE Gr is tested on MCNC benchmarks and the experimental results are promising.展开更多
This paper presents a high-quality very large scale integration （VLSI） global router in X-architecture, called XGRouter, that heavily relies on integer linear pro- gramming （ILP） techniques, partition strategy and...This paper presents a high-quality very large scale integration （VLSI） global router in X-architecture, called XGRouter, that heavily relies on integer linear pro- gramming （ILP） techniques, partition strategy and particle swarm optimization （PSO）. A new ILP formulation, which can achieve more uniform routing solution than other formu- lations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing re- gion is extended progressively from the most congested re- git）n. In the post-processing stage of XGRouter, maze rout- ing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global rout- ing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global touters, XGRouter has no overflow.展开更多
As technology advances, there is a considerable gap between the congestion model used in global routing and the routing resource consumption in detailed routing. The new factors contributing to congestion include loca...As technology advances, there is a considerable gap between the congestion model used in global routing and the routing resource consumption in detailed routing. The new factors contributing to congestion include local pin access paths, vias, and various design rules. In this paper, we propose a practical congestion model with measurement of the impact of design rules, and resources consumed by vias and local pin access paths. The model is compatible with path search algorithms commonly used in global routing. Validated by full-flow routing, this congestion model correlates better with real resource consumption situation in detailed routing, compared with previous work. It leads to better solution quality and shorter runtime of detailed routing when it is used in the layer assignment phase of global routing stage.展开更多
文摘An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire length model is implemented on multiprocessor,which enables the algorithm to approach feasibility of large scale problems.Timing driven model on multiprocessor and wire length model on distributed processors are also presented.The parallel algorithm greatly reduces the run time of routing.The experimental results show good speedups with no degradation of the routing quality.
文摘A global routing algorithm with performance optimization under multi constraints is proposed,which studies RLC coupling noise,timing performance,and routability simultaneously at global routing level.The algorithm is implemented and the global router is called CEE Gr.The CEE Gr is tested on MCNC benchmarks and the experimental results are promising.
文摘This paper presents a high-quality very large scale integration （VLSI） global router in X-architecture, called XGRouter, that heavily relies on integer linear pro- gramming （ILP） techniques, partition strategy and particle swarm optimization （PSO）. A new ILP formulation, which can achieve more uniform routing solution than other formu- lations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing re- gion is extended progressively from the most congested re- git）n. In the post-processing stage of XGRouter, maze rout- ing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global rout- ing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global touters, XGRouter has no overflow.
基金This work was supported by the National Natural Science Foundation of China under Grant No. 61274031. A preliminary version of the paper was published in the Proceedings of CAD/Graphics 2013.
文摘As technology advances, there is a considerable gap between the congestion model used in global routing and the routing resource consumption in detailed routing. The new factors contributing to congestion include local pin access paths, vias, and various design rules. In this paper, we propose a practical congestion model with measurement of the impact of design rules, and resources consumed by vias and local pin access paths. The model is compatible with path search algorithms commonly used in global routing. Validated by full-flow routing, this congestion model correlates better with real resource consumption situation in detailed routing, compared with previous work. It leads to better solution quality and shorter runtime of detailed routing when it is used in the layer assignment phase of global routing stage.
