Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles
As one of the most important routing problems in the complex network within a very-large-scale integration (VLSI) circuit, bus routing has become much more challenging when witnessing the advanced technology node enters the deep nanometer era because all bus bits need to be routed with the same rout...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/8843271 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832560013973913600 |
|---|---|
| author | Ziran Zhu Zhipeng Huang Jianli Chen Longkun Guo |
| author_facet | Ziran Zhu Zhipeng Huang Jianli Chen Longkun Guo |
| author_sort | Ziran Zhu |
| collection | DOAJ |
| description | As one of the most important routing problems in the complex network within a very-large-scale integration (VLSI) circuit, bus routing has become much more challenging when witnessing the advanced technology node enters the deep nanometer era because all bus bits need to be routed with the same routing topology in the context. In particular, the nonuniform routing track configuration and obstacles bring the largest difficulty for maintaining the same topology for all bus bits. In this paper, we first present a track handling technique to unify the nonuniform routing track configuration with obstacles. Then, we formulate the topology-aware single bus routing as an unsplittable flow problem (UFP), which is integrated into a negotiation-based global routing to determine the desired routing regions for each bus. A topology-aware track assignment is also presented to allocate the tracks to each segment of buses under the guidance of the global routing result. Finally, a detailed routing scheme is proposed to connect the segments of each bus. We evaluate our routing result with the benchmark suite of the 2018 CAD Contest. Compared with the top-3 state-of-the-art methods, experimental results show that our proposed algorithm achieves the best overall score regarding specified time limitations. |
| format | Article |
| id | doaj-art-fda3d6c3ef0740a8b24d5a042463e127 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-fda3d6c3ef0740a8b24d5a042463e1272025-02-03T01:28:43ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/88432718843271Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and ObstaclesZiran Zhu0Zhipeng Huang1Jianli Chen2Longkun Guo3National ASIC System Engineering Research Center, Southeast University, Nanjing, ChinaCenter for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou, ChinaState Key Laboratory of ASIC and System, Fudan University, Shanghai, ChinaShandong Key Laboratory of Computer Networks, School of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan, ChinaAs one of the most important routing problems in the complex network within a very-large-scale integration (VLSI) circuit, bus routing has become much more challenging when witnessing the advanced technology node enters the deep nanometer era because all bus bits need to be routed with the same routing topology in the context. In particular, the nonuniform routing track configuration and obstacles bring the largest difficulty for maintaining the same topology for all bus bits. In this paper, we first present a track handling technique to unify the nonuniform routing track configuration with obstacles. Then, we formulate the topology-aware single bus routing as an unsplittable flow problem (UFP), which is integrated into a negotiation-based global routing to determine the desired routing regions for each bus. A topology-aware track assignment is also presented to allocate the tracks to each segment of buses under the guidance of the global routing result. Finally, a detailed routing scheme is proposed to connect the segments of each bus. We evaluate our routing result with the benchmark suite of the 2018 CAD Contest. Compared with the top-3 state-of-the-art methods, experimental results show that our proposed algorithm achieves the best overall score regarding specified time limitations.http://dx.doi.org/10.1155/2021/8843271 |
| spellingShingle | Ziran Zhu Zhipeng Huang Jianli Chen Longkun Guo Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles Complexity |
| title | Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles |
| title_full | Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles |
| title_fullStr | Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles |
| title_full_unstemmed | Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles |
| title_short | Topology-Aware Bus Routing in Complex Networks of Very-Large-Scale Integration with Nonuniform Track Configurations and Obstacles |
| title_sort | topology aware bus routing in complex networks of very large scale integration with nonuniform track configurations and obstacles |
| url | http://dx.doi.org/10.1155/2021/8843271 |
| work_keys_str_mv | AT ziranzhu topologyawarebusroutingincomplexnetworksofverylargescaleintegrationwithnonuniformtrackconfigurationsandobstacles AT zhipenghuang topologyawarebusroutingincomplexnetworksofverylargescaleintegrationwithnonuniformtrackconfigurationsandobstacles AT jianlichen topologyawarebusroutingincomplexnetworksofverylargescaleintegrationwithnonuniformtrackconfigurationsandobstacles AT longkunguo topologyawarebusroutingincomplexnetworksofverylargescaleintegrationwithnonuniformtrackconfigurationsandobstacles |