A high-quality global routing algorithm based on hybrid topology optimization and heuristic search for data processing in MEC
A high-quality global routing algorithm based on hybrid topology optimization and heuristic search for data processing in MEC
复制标题
基于混合拓扑优化和启发式搜索的 MEC 数据处理高质量全局路由算法
DOI：
10.1007/s11227-021-04147-y
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Guolong Chen
中科院分区：
文献类型：
--
作者：
Saijuan Xu;Ling Wei;Genggeng Liu;Yeh-Cheng Chen;Guolong Chen
随着物联网的发展，实时决策逐渐成为物联网移动的边缘计算环境的重要特征之一。因此，在物联网MEC环境下的集成电路（IC）设计中，低延迟是重要的优化目标之一。在众多的路由竞争中，线长、溢出和运行时间是主要的评价标准，因此如何降低线长、溢出和运行时间成为一个重大的挑战。然而，现有的工作缺乏优秀的优化能力，线长，溢出，和运行时，或只考虑了一些优化目标。因此，本文以线长、溢出和运行时间为优化目标，提出了一种MEC环境下高质量的IC设计全局布线算法，包括以下有效策略：（1）Prim算法与分治法相结合的混合拓扑优化策略;（2）考虑网络拥塞和线长的启发式搜索算法。由于使用快速拓扑表（FLUTE）算法来构建每个网络的拓扑结构，存在太多的Steiner点。为此，我们使用Prim算法和分治法来构造拓扑结构，从而避免了冗余Steiner点的问题。此外，我们提出了一种基于区间划分的拥塞区域识别方法，以确定网络的区域和顺序，以撕裂和重路由（R&R）。此外，在R&R阶段，采用一种同时考虑网络拥塞和线长的启发式搜索算法对总线长进行优化。实验结果表明，所提策略在总溢出、总线长和运行时间方面均实现了有效优化，能够更好地满足物联网MEC环境下数据处理IC设计的低延迟需求。
With the development of Internet of Things (IoT), real-time decision making has gradually become one of the important characteristics in mobile edge computing (MEC) environment of IoT. Therefore, in the Integrated Circuit (IC) design of MEC environment for IoT, low delay is one of the important optimization objectives. In the many routing competitions, wirelength, overflow, and runtime are the main evaluation standards, so how to reduce wirelength, overflow, and runtime has become a major challenge. However, the existing work lacks the excellent optimization ability in wirelength, overflow, and runtime, or only considers some of the optimization objectives. Therefore, we consider the wirelength, overflow, and runtime as the optimization objectives and propose a high-quality global routing algorithm of IC design in MEC environment, including the following effective strategies: (1) A hybrid topology optimization strategy combining Prim algorithm and divide-and-conquer method, (2) a heuristic search algorithm considering the congestion and the wirelength of nets. Due to the use of the Fast Lookup Table (FLUTE) algorithm to construct the topology of each net, there are too many Steiner points. For this reason, we used Prim algorithm and divide-and-conquer method to construct the topology, and thus it can avoid the problem of redundant Steiner points. In addition, we propose a congestion area identification method based on interval division to determine the area and order of nets to rip-up and reroute (R&R). Furthermore, a heuristic search algorithm that considers both the congestion and the wirelength of nets is used to optimize the total wirelength in the R&R stage. In terms of the total overflow, the total wirelength and the runtime, the experimental results show that the proposed strategies have achieved effective optimization, which can better satisfy the demand of low delay of IC design for data processing in MEC environments of IoT.
登录
查看更多内容
DOI：
--
发表时间：
2018-12
期刊：
ArXiv
影响因子：
--
作者：
Md. Redowan Mahmud;R. Buyya
通讯作者：
Md. Redowan Mahmud;R. Buyya
基于多策略优化离散差分进化的X架构Steiner最小树算法
DOI：
10.7717/peerj-cs.473
发表时间：
2021
期刊：
PeerJ. Computer science
影响因子：
--
作者：
Liu G;Yang L;Xu S;Li Z;Chen YC;Chen CH
通讯作者：
Chen CH
基于粒子群优化的多层避障X-Architecture Steiner最小树构建
影响因子：
11.8
作者：
Xing Huang;Wenzhong Guo;Yuzhen Niu;Guolong Chen
通讯作者：
Guolong Chen
DOI：
10.1109/tcad.2008.927733
发表时间：
2008-09
影响因子：
2.9
作者：
Tsung-Hsien Lee;Ting-Chi Wang
通讯作者：
Tsung-Hsien Lee;Ting-Chi Wang
影响因子：
7.2
作者：
Pieper TM
通讯作者：
Pieper TM