| 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
|
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.
|
李刚, 汪鹏君, 张跃军, 等. 基于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
|
Figures(2) / Tables(5)
DownLoad:
