Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

doi:10.1007/s12204-019-2073-7

Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (3): 372-380.doi: 10.1007/s12204-019-2073-7

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

XIE Ying *(谢盈), WU Jinzhao (吴尽昭), CHEN Jianying (陈建英), CUI Mengtian (崔梦天)

(1. School of Computer Science and Technology, Southwest Minzu University, Chengdu 610041, China; 2. Guangxi Key Laboratory of Hybrid Computational and IC Design Analysis, Guangxi University for Nationalities, Nanning 530006, China; 3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China; 4. University of Chinese Academy of Sciences, Beijing 100049, China)

出版日期:2019-06-01 发布日期:2019-05-29
通讯作者: XIE Ying *(谢盈) E-mail:xieying33@163.com

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

XIE Ying *(谢盈), WU Jinzhao (吴尽昭), CHEN Jianying (陈建英), CUI Mengtian (崔梦天)

(1. School of Computer Science and Technology, Southwest Minzu University, Chengdu 610041, China; 2. Guangxi Key Laboratory of Hybrid Computational and IC Design Analysis, Guangxi University for Nationalities, Nanning 530006, China; 3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China; 4. University of Chinese Academy of Sciences, Beijing 100049, China)

Online:2019-06-01 Published:2019-05-29
Contact: XIE Ying *(谢盈) E-mail:xieying33@163.com

摘要/Abstract

摘要： It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system. A novel dynamic measurement method (DMM) was proposed to measure the task scheduling algorithm’s correctness and dependability. In a multi-processor system, task scheduling problem is represented by a combinatorial evaluation model, interactive Markov chain (IMC), and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic (aCSL). DMM derives a path by logging runtime scheduling actions and corresponding times. Through judging whether the derived path can be received by task scheduling IMC model, DMM analyses the correctness of algorithm. Through judging whether the actual values satisfy label function of the initial state, DMM analyses the dependability of algorithm. The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.

关键词: multi-processor, task scheduling algorithm, IMC, aCSL, dynamic measurement

Abstract: It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system. A novel dynamic measurement method (DMM) was proposed to measure the task scheduling algorithm’s correctness and dependability. In a multi-processor system, task scheduling problem is represented by a combinatorial evaluation model, interactive Markov chain (IMC), and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic (aCSL). DMM derives a path by logging runtime scheduling actions and corresponding times. Through judging whether the derived path can be received by task scheduling IMC model, DMM analyses the correctness of algorithm. Through judging whether the actual values satisfy label function of the initial state, DMM analyses the dependability of algorithm. The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.

Key words: multi-processor, task scheduling algorithm, IMC, aCSL, dynamic measurement

中图分类号:

TP 302

XIE Ying *(谢盈), WU Jinzhao (吴尽昭), CHEN Jianying (陈建英), CUI Mengtian (崔梦天). Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(3): 372-380.

参考文献 16

[1]	WOLF W, JERRAYA A A, MARTIN G. Multiprocessorsystem-on-chip (MPSoC) technology [J]. IEEETransactions on Computer-Aided Design of IntegratedCircuits and Systems, 2008, 27(10): 1701-1713.
[2]	TANG Q, BASTEN T, GEILEN M, et al. Task-FIFOco-scheduling of streaming applications on MPSoCswith predictable memory hierarchy [J]. ACM Transactionson Embedded Computing System, 2017, 16(2):49.
[3]	MOKRYANI G, SIANO P. Evaluating the integrationof wind power into distribution networks by usingMonte Carlo simulation [J]. International Journal ofElectrical Power & Energy Systems, 2013, 53(1): 244-255.
[4]	B′EARD B, BIDOIT M, FINKEL A, et al. Systemsand software verification: Model-checking techniquesand tools [M]. Berlin: Springer, 2013.
[5]	CLASSEN A, CORDY M, SCHOBBENS P Y, et al.Featured transition systems: Foundations for verifyingvariability-intensive systems and their applicationto LTL model checking [J]. IEEE Transactions on SoftwareEngineering, 2013, 39(8): 1069-1089.
[6]	RIEMENSCHNEIDER R A, SAIDI H, DUTERTREB. Using model checking to assess the dependabilityof agent-based systems [J]. IEEE Intelligent Systems,2004, 19(5): 62-70.
[7]	ZULIANI P, PLATZER A, CLARKE E M. Bayesianstatistical model checking with application to Stateflow/Simulink verification [J]. Formal Methods in SystemDesign, 2013, 43(2): 338-367.
[8]	MA D, YAN R J, HUANG K, et al. Performance estimationtechniques with MPSoC transaction-accuratemodels [J]. IEEE Transactions on Computer-AidedDesign of Integrated Circuits and Systems, 2013,32(12): 1920-1933.
[9]	SHENG W, GAO Y Y, XI L, et al. Schedulabilityanalysis for multicore global scheduling with modelchecking [C]//11th International Workshop on MicroprocessorTest and Verification. Austin, TX, USA:IEEE, 2010: 21-26.
[10]	XIONG Z G, YANG Y, ZENG M. Research on twophasegrid task scheduling based on Petri nets [J].Journal on Communications, 2009, 30(8): 69-77 (inChinese).
[11]	NEUHAUSSER M R, ZHANG L J. Time-boundedreachability probabilities in continuous-time Markovdecision processes [C]//7th International Conferenceon the Quantitative Evaluation of Systems. Williamsburg,VA, USA: IEEE, 2010: 209-218.
[12]	ANSELMI J, DUFOUR F, PRIETO-RUMEAUT. Computable approximations for continuous-timeMarkov decision processes on Borel spaces based onempirical measures [J]. Journal of Mathematical Analysisand Applications, 2016, 443(2): 1323-1361.
[13]	JAFARI A, KHAMESPANAH E, SIRJANI M, et al.PTRebeca: Modeling and analysis of distributed andasynchronous systems [J]. Scinece of Compter Programming,2016, 128: 22-50.
[14]	BANICESCU I, SRIVASTAVA S. Towards robustresource allocations via performance modeling withstochastic process algebra [C]// 18th InternationalConference on Computational Science and Engineering.Porto, Pottugal: IEEE, 2015: 270-277.
[15]	HERMANNS H, KRCAL J, KRETINSKY J. Compositionalverification and optimization of interactiveMarkov chains [C]//International Conference on ConcurrencyTheory. Buenos Aires, Argentina: Springer,2013.
[16]	DICK R P, RHODES D L, WOLF W. TGFF:task graphs for free [C]//6th International Workshopon Hardware/Software Codesign. Seattle, WA, USA:IEEE, 1998: 97-101.

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 16

相关文章 1

编辑推荐

Metrics

本文评价