考慮任務(wù)不確定性的片上網(wǎng)絡(luò)魯棒性應(yīng)用映射問題研究

王新玉; 李治瑩; 邵帥; 虞志剛

doi:10.11999/JEIT180600

考慮任務(wù)不確定性的片上網(wǎng)絡(luò)魯棒性應(yīng)用映射問題研究

doi: 10.11999/JEIT180600

1.
東北財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院 ??大連 ??116025
2.
中國電子科學(xué)研究院 ??北京 ??100041

基金項目: 教育部人文社會科學(xué)研究一般項目(18YJC630185)，國家自然科學(xué)基金(61402086, 71501032, 71602021)

詳細信息

作者簡介:
王新玉：女，1985年生，博士，副教授，研究方向為并行分布式計算、智能優(yōu)化等

李治瑩：女，1997年生，本科生，研究方向為智能優(yōu)化算法等

邵帥：男，1994年生，碩士生，研究方向為應(yīng)用映射算法等

虞志剛：男，1988年生，博士，研究方向為片上網(wǎng)絡(luò)路由器設(shè)計等

通訊作者:
王新玉　Distribute_2008@163.com

中圖分類號: TP391
計量
- 文章訪問數(shù): 2008
- HTML全文瀏覽量: 766
- PDF下載量: 40
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-06-20
- 修回日期: 2019-01-09
- 網(wǎng)絡(luò)出版日期: 2019-01-25
- 刊出日期: 2019-05-01

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

1.
School of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116025, China
2.
China Academy of Electronics and Information Technology, Beijing 100041, China

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)

摘要

摘要:
標(biāo)準應(yīng)用映射問題中，每個任務(wù)的通信量是確定值，而實際應(yīng)用中任務(wù)通信具有突發(fā)性和時變特征，因此將任務(wù)通信量建模為不確定值具有現(xiàn)實意義。該文利用區(qū)間流法對任務(wù)不確定性進行描述，基于保守因子對魯棒性應(yīng)用映射問題建模，提出了求解問題的改進禁忌搜索算法(Tabu-RAM)，通過5個Benchmark案例對本文模型和算法進行了驗證。實驗結(jié)果表明Tabu-RAM能夠求解傳統(tǒng)應(yīng)用映射問題，且優(yōu)于現(xiàn)有文獻中給出的算法。此外，與傳統(tǒng)禁忌搜索算法相比，Tabu-RAM算法在求解魯棒性應(yīng)用映射問題時具有更好的性能和穩(wěn)定性。
- 片上網(wǎng)絡(luò) /
- 應(yīng)用映射 /
- 不確定性 /
- 區(qū)間流 /
- 禁忌搜索
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.
- Network-on-chip /
- Application mapping /
- Uncertainty /
- Interval flow /
- Tabu search

HTML全文

圖 1 測試算例4映射到4×8Mesh網(wǎng)絡(luò)中10次結(jié)果比較

下載: 全尺寸圖片幻燈片

圖 2 測試算例5映射到6×6Mesh網(wǎng)絡(luò)中10次結(jié)果比較

下載: 全尺寸圖片幻燈片

表 1 核與路由器的映射對應(yīng)關(guān)系

核編號i	1	2	3	4	5	6	7	8	9	10
路由器編號	3	1	5	8	7	4	10	6	9	2

下載: 導(dǎo)出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　當(dāng)$b \le m$時，若${\rm{tabulist}}\left[ b \right]\left[ {{{{Y}}_a}} \right]$為真，代表禁止將核$b$放
置到路由器${{{Y}}_a}$上，bFlag = false；

當(dāng)$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)$交換被禁止；否
則，交換不被禁止，對應(yīng)的解作為候選解。

下載: 導(dǎo)出CSV

表 3 Tabu-RAM算法流程

　步驟1　根據(jù)3.3.3節(jié)生成初始解${{Y}}$，全局最優(yōu)解${{G}} = {{Y}}$，連續(xù)
未更新次數(shù)NIN=0；

　步驟2　對${{Y}}$進行Tabu搜索，迭代次數(shù)為n，根據(jù)需要更新${{Y}}$和
${{G}}$，若達到最大搜索時間，轉(zhuǎn)步驟5；

　步驟3　若${{G}}$未更新，NIN++；否則NIN=0；

　步驟4　若${\rm{NIN}} \ge {5}$，利用3.3.3中方法構(gòu)造解賦值給${{Y}}$，轉(zhuǎn)步驟
2；否則，直接轉(zhuǎn)步驟2；

　步驟5　迭代終止，返回${{G}}$。

下載: 導(dǎo)出CSV

表 4 確定應(yīng)用場景下本文算法與已有文獻中的算法

編號	測試用例	核數(shù)	映射Mesh結(jié)構(gòu)	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*

下載: 導(dǎo)出CSV

表 5 不確定應(yīng)用場景下不同算法比較

測試用例			本文Tabu-RAM算法			標(biāo)準Tabu算法			文獻[17]中MC算法
編號	名稱	$\theta $取值	最優(yōu)值	平均值	開銷差距(%)	最優(yōu)值	平均值	開銷差距(%)	最優(yōu)值
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

下載: 導(dǎo)出CSV

參考文獻(22)

李剛, 汪鵬君, 張躍軍, 等. 基于65 nm工藝的多端口可配置PUF電路設(shè)計[J]. 電子與信息學(xué)報, 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]. 計算機研究與發(fā)展, 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

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計