高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

考虑任务不确定性的片上网络鲁棒性应用映射问题研究

王新玉 李治莹 邵帅 虞志刚

王新玉, 李治莹, 邵帅, 虞志刚. 考虑任务不确定性的片上网络鲁棒性应用映射问题研究[J]. 电子与信息学报, 2019, 41(5): 1152-1159. doi: 10.11999/JEIT180600
引用本文: 王新玉, 李治莹, 邵帅, 虞志刚. 考虑任务不确定性的片上网络鲁棒性应用映射问题研究[J]. 电子与信息学报, 2019, 41(5): 1152-1159. doi: 10.11999/JEIT180600
Xinyu WANG, Zhiying LI, Shuai SHAO, Zhigang YU. Robust Application Mapping for Networks-on-chip Considering Uncertainty of Tasks[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1152-1159. doi: 10.11999/JEIT180600
Citation: Xinyu WANG, Zhiying LI, Shuai SHAO, Zhigang YU. Robust Application Mapping for Networks-on-chip Considering Uncertainty of Tasks[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1152-1159. doi: 10.11999/JEIT180600

考虑任务不确定性的片上网络鲁棒性应用映射问题研究

doi: 10.11999/JEIT180600
基金项目: 教育部人文社会科学研究一般项目(18YJC630185),国家自然科学基金(61402086, 71501032, 71602021)
详细信息
    作者简介:

    王新玉:女,1985年生,博士,副教授,研究方向为并行分布式计算、智能优化等

    李治莹:女,1997年生,本科生,研究方向为智能优化算法等

    邵帅:男,1994年生,硕士生,研究方向为应用映射算法等

    虞志刚:男,1988年生,博士,研究方向为片上网络路由器设计等

    通讯作者:

    王新玉 Distribute_2008@163.com

  • 中图分类号: TP391

Robust Application Mapping for Networks-on-chip Considering Uncertainty of Tasks

Funds: The General Project of Humanities and Social Sciences Research of the Ministry of Education (18YJC630185), The National Natural Science Foundation of China (61402086, 71501032, 71602021)
  • 摘要:

    标准应用映射问题中,每个任务的通信量是确定值,而实际应用中任务通信具有突发性和时变特征,因此将任务通信量建模为不确定值具有现实意义。该文利用区间流法对任务不确定性进行描述,基于保守因子对鲁棒性应用映射问题建模,提出了求解问题的改进禁忌搜索算法(Tabu-RAM),通过5个Benchmark案例对本文模型和算法进行了验证。实验结果表明Tabu-RAM能够求解传统应用映射问题,且优于现有文献中给出的算法。此外,与传统禁忌搜索算法相比,Tabu-RAM算法在求解鲁棒性应用映射问题时具有更好的性能和稳定性。

  • 图  1  测试算例4映射到4×8Mesh网络中10次结果比较

    图  2  测试算例5映射到6×6Mesh网络中10次结果比较

    表  1  核与路由器的映射对应关系

    核编号i 1 2 3 4 5 6 7 8 9 10
    路由器编号 3 1 5 8 7 4 10 6 9 2
    下载: 导出CSV

    表  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

    表  4  确定应用场景下本文算法与已有文献中的算法

    编号 测试用例 核数 映射Mesh结构 CastNet[13] GA[14] PSO[15] 本文算法
    1 MPEG-4 12 4×4 3852 3567* 3567* 3567*
    2 VOPD 16 4×4 4135 4290 4119* 4119*
    3 MMS 25 5×5 689503 689713 - 688297*
    4 DVOPD 32 4×8 - - 9602 9570*
    5 DVOPD 32 6×6 9618 10006 - 9522*
    下载: 导出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/JEIT150968

    LI 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.20150682

    ZHANG 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)
计量
  • 文章访问数:  1980
  • HTML全文浏览量:  751
  • PDF下载量:  40
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-06-20
  • 修回日期:  2019-01-09
  • 网络出版日期:  2019-01-25
  • 刊出日期:  2019-05-01

目录

    /

    返回文章
    返回