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

Previous Articles Next Articles

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)
(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

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

摘要： 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

CLC Number:

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.

References 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)

Knowledge

Abstract

Cite this article

share this article

References 16

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	WANG Zhao-yang (王朝阳), LI Hai-bin* (李海滨), WEI Guang-mei (韦广梅). A Research for Error Compensation Algorithm of Dual Range Pressure Sensor [J]. Journal of shanghai Jiaotong University (Science), 2015, 20(3): 370-373.
[2]	XU Qi,BIAN Zhan,CHEN Yan,JIN Zhihong. Scheduling Optimization of Port Tugboat Operation Considering Multi-Anchorage [J]. Journal of Shanghai Jiaotong University, 2014, 48(1): 132-139.