Robust Application Mapping for Networks-on-chip Considering Uncertainty of Tasks
-
摘要:
标准应用映射问题中，每个任务的通信量是确定值，而实际应用中任务通信具有突发性和时变特征，因此将任务通信量建模为不确定值具有现实意义。该文利用区间流法对任务不确定性进行描述，基于保守因子对鲁棒性应用映射问题建模，提出了求解问题的改进禁忌搜索算法(Tabu-RAM)，通过5个Benchmark案例对本文模型和算法进行了验证。实验结果表明Tabu-RAM能够求解传统应用映射问题，且优于现有文献中给出的算法。此外，与传统禁忌搜索算法相比，Tabu-RAM算法在求解鲁棒性应用映射问题时具有更好的性能和稳定性。
Abstract:In the standard application mapping problem, it is assumed that the communicating traffic of a task is a fixed value. In the real applications, the communication traffic is uncertain due to the time-varying and bursty characters. Therefore, it has the practical significance modeling the task with communicating traffic uncertainty. Given the interval flow and a conservation factor, the robust application mapping problem is formulated by a min-max model, and then solved by a revised Tabu-based algorithm (Tabu-RAM) in this paper. The algorithm is verified under five benchmark instances. As the experimental results show, under the standard application scenarios, the Tabu-RAM performs better than other methods proposed in the literature. In addition, under the application scenarios with uncertain tasks, experimental results show that the Tabu-RAM performs better and more stable than the traditional tabu algorithm.
-
Key words:
- Network-on-chip /
- Application mapping /
- Uncertainty /
- Interval flow /
- Tabu search
-
表 2
${{swap}}\left( {{{Y}},a,b} \right)$ 计算过程步骤1 令aFlag=true, bFlag=true； 步骤2 易知$a \le m$，若${\rm{tabulist}}\left[ a \right]\left[ {{{{Y}}_b}} \right]$为真，代表禁止将核$a$放
置到路由器${{{Y}}_b}$上，aFlag = false；步骤3 当$b \le m$时，若${\rm{tabulist}}\left[ b \right]\left[ {{{{Y}}_a}} \right]$为真，代表禁止将核$b$放
置到路由器${{{Y}}_a}$上，bFlag = false；当$b > m$时，$b$是虚拟核，若存在某个${\rm{tabulist}}\left[ c\; \right]\left[ {{{{Y}}\!_a}} \right]$
$\left( {c \ge b} \right)$为真，禁止将路由器${{{Y}}\!_a}$置为空，bFlag = false；步骤4 若aFlag和bFlag均为false, ${\rm{swap}}\left( {{{Y}},a,b} \right)$交换被禁止；否
则，交换不被禁止，对应的解作为候选解。
下载: 导出CSV
表 3 Tabu-RAM算法流程
步骤1 根据3.3.3节生成初始解${{Y}}$，全局最优解${{G}} = {{Y}}$，连续
未更新次数NIN=0；步骤2 对${{Y}}$进行Tabu搜索，迭代次数为n，根据需要更新${{Y}}$和
${{G}}$，若达到最大搜索时间，转步骤5；步骤3 若${{G}}$未更新，NIN++；否则NIN=0； 步骤4 若${\rm{NIN}} \ge {5}$，利用3.3.3中方法构造解赋值给${{Y}}$，转步骤
2；否则，直接转步骤2；步骤5 迭代终止，返回${{G}}$。
下载: 导出CSV
表 5 不确定应用场景下不同算法比较
测试用例 本文Tabu-RAM算法 标准Tabu算法 文献[17]中MC算法 编号 名称 $\theta $取值 最优值 平均值 开销差距(%) 最优值 平均值 开销差距(%) 最优值 1 MPEG-4 4×4 Mesh 0 42328.00 42328.00 0 42328.00 43270.20 2.23 49962.00 0.2 77628.00 77628.00 0 77628.00 79150.96 1.96 86986.80 0.4 92888.00 92888.00 0 92888.00 96519.68 3.91 99176.40 0.6 98359.40 98359.40 0 98359.40 101965.82 3.67 118958.80 0.8 99924.60 99924.60 0 99924.60 106761.86 6.84 116436.80 1.0 99993.00 99993.00 0 99993.00 103121.00 3.13 113627.00 平均值 0 3.62 2 VOPD 4×4 Mesh 0 2147.00 2147.00 0 2147.00 2148.60 0.07 2444.00 0.2 4566.60 4567.00 0.01 4570.60 4573.00 0.05 5761.40 0.4 5530.60 5530.60 0 5530.60 5534.36 0.07 7168.00 0.6 5818.20 5818.20 0 5818.20 5820.40 0.04 7294.00 0.8 6004.40 6004.40 0 6004.40 6018.66 0.24 7765.80 1.0 6070.00 6070.00 0 6070.00 6092.90 0.38 7858.00 平均值 0 0.14 3 MMS 5×5 Mesh 0 411649.00 411750.50 0.02 412039.00 416316.10 1.04 622005.00 0.2 786490.40 786640.70 0.02 787536.40 820504.72 4.10 1254921.60 0.4 917007.00 917152.10 0.02 917396.00 940330.06 2.50 1421245.80 0.6 952629.00 952869.40 0.03 953018.00 982380.46 3.08 1379116.40 0.8 959803.40 960015.00 0.02 960168.80 980107.78 2.08 1436050.60 1.0 960575.00 960846.40 0.03 961210.00 995897.40 3.61 1558999.00 平均值 0.02 2.75 4 DVOPD 4×8 Mesh 0 5593.00 5606.80 0.25 5726.00 5871.70 2.54 11706.00 0.2 10277.00 10317.82 0.40 10315.00 11101.32 7.62 22954.40 0.4 12083.80 12126.82 0.36 12161.80 12493.80 2.73 25964.00 0.6 12974.40 13011.08 0.28 13145.40 13803.52 5.01 29696.00 0.8 13413.40 13452.02 0.29 13447.40 14197.74 5.58 32243.40 1.0 13527.00 13591.80 0.48 13845.00 14281.30 3.15 29641.00 平均值 0.34 4.44 5 DVOPD 6×6 Mesh 0 5565.00 5573.70 0.16 5710.00 5853.60 2.51 12535.00 0.2 10236.00 10273.40 0.37 10276.00 10985.50 6.90 24139.00 0.4 12024.40 12060.12 0.30 12167.40 12601.10 3.56 27665.80 0.6 12885.40 12905.66 0.16 12956.40 13489.16 4.11 29484.00 0.8 13292.00 13319.40 0.21 13366.60 13892.86 3.94 28463.20 1.0 13439.00 13493.30 0.40 13716.00 14250.20 3.89 31575.00 平均值 0.26 4.15
下载: 导出CSV
-
李刚, 汪鹏君, 张跃军, 等. 基于65 nm工艺的多端口可配置PUF电路设计[J]. 电子与信息学报, 2016, 38(6): 1541–1546. doi: 10.11999/JEIT150968LI Gang, WANG Pengjun, ZHANG Yuejun, et al. Design of multi-port configurable PUF circuit based on 65 nm technology[J]. Journal of Electronics &Information Technology, 2016, 38(6): 1541–1546. doi: 10.11999/JEIT150968 SU Nan, GU Huaxi, WANG Kun, et al. A highly efficient dynamic router for application-oriented network on chip[J]. The Journal of Supercomputing, 2018, 74(7): 2905–2915. doi: 10.1007/s11227-018-2334-5 ABDELFATTAH M S, BITAR A, and BETZ V. Design and applications for embedded networks-on-chip on FPGAs[J]. IEEE Transactions on Computers, 2017, 66(6): 1008–1021. doi: 10.1109/TC.2016.2621045 POPOOLA O and PRANGGONO B. On energy consumption of switch-centric data center networks[J]. The Journal of Supercomputing, 2018, 74(1): 334–369. doi: 10.1007/s11227-017-2132-5 HU Jingcao and MARCULESCU R. Energy- and performance-aware mapping for regular NoC architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(4): 551–562. doi: 10.1109/TCAD.2005.844106 CHOU C L and MARCULESCU R. Contention-aware application mapping for network-on-chip communication architectures[C]. Proceedings of 2008 IEEE International Conference on Computer Design, Lake Tahoe, USA, 2008: 164–169. doi: 10.1109/ICCD.2008.4751856. ZHANG Bixia, GU Huaxi, YANG Yintang, et al. Thermal and competition aware mapping for 3D network-on-chip[J]. IEICE Electronics Express, 2012, 9(19): 1510–1515. doi: 10.1587/elex.9.1510 CHENG C and CHEN Weimei. Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms[J]. The Journal of Supercomputing, 2016, 72(11): 4365–4378. doi: 10.1007/s11227-016-1746-3 张大坤, 宋国治, 林华洲, 等. 二次改进遗传算法与3D NoC低功耗映射[J]. 计算机研究与发展, 2016, 53(4): 921–931. doi: 10.7544/issn1000-1239.2016.20150682ZHANG Dakun, SONG Guozhi, LIN Huazhou, et al. Double improved genetic algorithm and low power task mapping in 3D networks-on-chip[J]. Journal of Computer Research and Development, 2016, 53(4): 921–931. doi: 10.7544/issn1000-1239.2016.20150682 WANG Xinyu, LIU Haikuo, and YU Zhigang. A novel heuristic algorithm for IP block mapping onto mesh-based networks-on-chip[J]. The Journal of Supercomputing, 2016, 72(5): 2035–2058. doi: 10.1007/s11227-016-1719-6 FANG Juan, YU Lu, LIU Sitong, et al. KL_GA: An application mapping algorithm for Mesh-of-Tree (MoT) architecture in network-on-chip design[J]. The Journal of Supercomputing, 2015, 71(11): 4056–4071. doi: 10.1007/s11227-015-1504-y RADU C, MAHBUB M S, and VINTAN L. Developing domain-knowledge evolutionary algorithms for network-on-chip application mapping[J]. Microprocessors and Microsystems, 2013, 37(1): 65–78. doi: 10.1016/j.micpro.2012.11.003 TOSUN S. New heuristic algorithms for energy aware application mapping and routing on mesh-based NoCs[J]. Journal of Systems Architecture, 2011, 57(1): 69–78. doi: 10.1016/j.sysarc.2010.10.001 TOSUN S, OZTURK O, OZKAN E, et al. Application mapping algorithms for mesh-based network-on-chip architectures[J]. The Journal of Supercomputing, 2015, 71(3): 995–1017. doi: 10.1007/s11227-014-1348-x SAHU P K, SHAH T, MANNA K, et al. Application mapping onto mesh-based network-on-chip using discrete particle swarm optimization[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014, 22(2): 300–312. doi: 10.1109/TVLSI.2013.2240708 SEPÚLVEDA M J, CHAU W J, GOGNIAT G, et al. A multi-objective adaptive immune algorithm for multi-application NoC mapping[J]. Analog Integrated Circuits and Signal Processing, 2012, 73(3): 851–860. doi: 10.1007/s10470-012-9869-9 ZHU Di, CHEN Lizhong, YUE Siyu, et al. Balancing on-chip network latency in multi-application mapping for chip-multiprocessors[C]. Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, USA, 2014: 872–881. ASSUNÇÃO L, NORONHA T F, SANTOS A C, et al. A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs[J]. Computers & Operations Research, 2017, 81: 51–66. doi: 10.1016/j.cor.2016.12.010 LÓPEZ J, POZO D, CONTRERAS J, et al. A multiobjective minimax regret robust VAr planning model[J]. IEEE Transactions on Power Systems, 2017, 32(3): 1761–1771. doi: 10.1109/TPWRS.2016.2613544 FEIZOLLAHI M J and FEYZOLLAHI H. Robust quadratic assignment problem with budgeted uncertain flows[J]. Operations Research Perspectives, 2015, 2: 114–123. doi: 10.1016/j.orp.2015.06.001 BENLIC U and HAO Jinkao. Memetic search for the quadratic assignment problem[J]. Expert Systems with Applications, 2015, 42(1): 584–595. doi: 10.1016/j.eswa.2014.08.011 DOKEROGLU T and MENGUSOGLU E. A self-adaptive and stagnation-aware breakout local search algorithm on the grid for the Steiner tree problem with revenue, budget and hop constraints[J]. Soft Computing, 2018, 22(12): 4133–4151. doi: 10.1007/s00500-017-2630-7 -
下载:
图(2) / 表(5)
计量
- 文章访问数: 1950
- HTML全文浏览量: 726
- PDF下载量: 40
- 被引次数: 0
