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.
XIE Ying *(谢盈), WU Jinzhao (吴尽昭), CHEN Jianying (陈建英), CUI Mengtian (崔梦天)
. Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System[J]. Journal of Shanghai Jiaotong University(Science), 2019
, 24(3)
: 372
-380
.
DOI: 10.1007/s12204-019-2073-7
[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.
