Multi-core Parallel Complex System Task Scheduling Method Based on Multi Label Constraint

Yingjie Wang; Kuanjiu Zhou; Mingchu Li

doi:10.6180/jase.201803_21(1).0008

Multi-core Parallel Complex System Task Scheduling Method Based on Multi Label Constraint

Computer Science and Information Engineering

Yingjie Wang This email address is being protected from spambots. You need JavaScript enabled to view it.^1,2, Kuanjiu Zhou¹ and Mingchu Li¹

¹Software School, Dalian University of Technology, Dalian 116621, P.R. China
²Information and Engineering College, Dalian University, Dalian 116622, P.R. China

Received: February 7, 2017
Accepted: August 5, 2017
Publication Date: March 1, 2018

Download Citation: ||https://doi.org/10.6180/jase.201803_21(1).0008

ABSTRACT

When scheduling the multi-core parallel complex system tasks by using the traditional MapReduce scheduling method, there is a problem that the task response time is high and the system throughput is reduced. For this kind of phenomenon, we proposed a multi core parallel complex system task scheduling method based on multi label constraint, which was a task scheduling model with multi label constraint graph based on shaping, realizing the parallel fusion of space and time of system task scheduling. The space parallel and the time parallel scheduling method were incorporated in the scheduling framework. Through the parallel node merging and allocation algorithm, the space parallel scheduling method of multi label constraint graph was improved, which implemented the efficient scheduling of multi core parallel complex system tasks. The experimental results show that the proposed method can improve the data parallel performance, which has high scheduling performance.

Keywords: Multi Label, Constraint, Multi-core Parallel System, Task, Scheduling

REFERENCES

[1] Chang, C. W., Chen, J. J., Kuo, T. W., et al. “Real-time Task Scheduling on Island-based Multi-core Platforms,” IEEE Transactions on Parallel &Distributed Systems, Vol. 26, No. 2, p. 1 (2014). doi: 10.1109/TPDS.2013. 2297308
[2] Bell, P. C. and Wong, P. W. H., “Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines,” Journal of Combinatorial Optimization, Vol. 29, No. 4, pp. 739749 (2015). doi: 10.1007/s10878-013-9618-8
[3] Meier, H. E. M., Döscher, R. and Faxén, T., “A Multiprocessor Coupled Ice-ocean Model for the BalticSea: Application to Salt Inflow,” Journal of Geophysical Research Oceans, Vol. 108, No. C8, pp. 343367 (2015). doi: 10.1029/2000JC000521
[4] Abdel All, M., Hassan, H. M., Hamdy, M., et al., “Design and Implementation of Application-specific Instruction-set Processor Design for High-throughput Multi-standard Wireless Orthogonal Frequency Division Multiplexing Baseband Processor,” Iet Circuits, Devices & Systems, Vol. 9, No. 3, pp. 191203 (2015). doi: 10.1049/iet-cds.2014.0046
[5] Ingham, M. D., Rasmussen, R. D., Bennett, M. B., et al., “Engineering Complex Embedded Systems with State Analysis and the Mission Data System,” Journal of Aerospace Computing Information & Communication, Vol. 2, No. 12, pp. 507536 (2015). doi: 10.2514/ 1.15265
[6] Lin, C. C., Chang, C. J., Syu, Y. C., et al., “An Energyefficient Task Scheduler for Multi-core Platforms with Per-core DVFS Based on Task Characteristics//Brazilian Conference on Intelligent Systems,” IEEE Computer Society, pp. 381390 (2014). doi: 10.1109/ICPP. 2014.47
[7] Chang, C. W., Chen, J. J., Kuo, T. W., et al., “Real-time Task Scheduling on Island-based Multi-core Platforms,” IEEE Transactions on Parallel &Distributed Systems, Vol. 26, No. 2, pp. 538550 (2015). doi: 10.1109/ TPDS.2013.2297308
[8] Meng, X. F. and Zhang, X. Y., “Parallel Task Scheduling Strategy with Multi-objective Constraints in P2P,” Computer Integrated Manufacturing Systems, Vol. 14, No. 4, pp. 761766 (2008).
[9] Xu, T., Li, P. and Sundareswaran, S., “Decoupling Capacitance Design Strategies for Power Delivery Networks with Power Gating,” ACM Transactions on Design Automation of Electronic Systems, Vol. 20, No. 3, pp. 130 (2015). doi: 10.1145/2700825
[10] Saifullah, A., Agrawal, K., Lu, C., et al., “Multi-core Real-time Scheduling for Generalized Parallel Task Models,” Real-Time Systems, Vol. 49, No. 4, pp. 217 226 (2013). doi: 10.1007/s11241-012-9166-9
[11] Porto, S. C. S. and Ribeiro, C. C., “A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Precedence Constraints,” International Journal of High Speed Computing, Vol. 7, No. 1, pp. 4571 (2012). doi: 10.1142/S012905339500004X
[12] Sheikh, H. F., Ahmad, I., Wang, Z., et al., “An Overview and Classification of Thermal-aware Scheduling Techniques for Multi-core Processing Systems,” Sustainable Computing Informatics & Systems, Vol. 2, No. 3, pp. 151169 (2012). doi: 10.1016/j.suscom. 2011.06.005
[13] Jahn, J., Pagani, S., Kobbe, S., et al., “Runtime Resource Allocation for SoftwarePipelines,”ACMTransactions on Parallel Computing, Vol. 2, No. 1, pp. 123 (2015). doi: 10.1145/2742347
[14] Min, C. and Eom, Y. I., “Dynamic Scheduling of Irregular Stream Programs toward Many-core Scalability,” IEEE Transactions on Parallel & Distributed Systems, Vol. 26, No. 6, pp. 15941607 (2015). doi: 10.1109/TPDS.2014.2325833
[15] Wang, Y., Li, K., Chen, H., et al., “Energy-aware Data Allocation and Task Scheduling on Heterogeneous Multiprocessor SystemswithTimeConstraints,” IEEE Transactions on Emerging Topics in Computing, Vol. 2, No. 2, pp. 134148 (2014). doi: 10.1109/TETC. 2014.2300632
[16] Zhang, X., Chen, L. and Wang, M., “Efficient Parallel Processing of Distance Join Queries Over Distributed Graphs,” Knowledge & Data Engineering IEEE Transactions on, Vol. 27, No. 3, pp. 740754 (2015). doi: 10.1109/TKDE.2014.2345383
[17] Wang, T., Ji, Z., Sun, Q., et al., “Interactive Multi-label Image Segmentation via Robust Multi-layer Graph Constraints,” IEEE Transactions on Multimedia, Vol. 18, No. 12, pp. 23582371 (2016). doi: 10.1109/TMM. 2016.2600441
[18] Diaz, L., Gonzalez, E., Villar, E., et al., “VIPPE, Parallel Simulation and Performance Analysis of Multicore Embedded Systems on Multi-core Platforms,” Design of Circuits and Integrated Circuits (DCIS), 2014 Conference on. IEEE, pp. 17 (2015). doi: 10. 1109/DCIS.2014.7035584
[19] Chang, C. W., Chen, J. J., Kuo, T. W., et al., “Real-time Task Scheduling on Island-based Multi-core Platforms,” Parallel &Distributed Systems IEEE Transactions on, Vol. 26, No. 2, pp. 538550 (2015). doi: 10.1109/ TPDS.2013.2297308
[20] Mingas, G. and Bouganis, C. S., “Population-based MCMC on Multi-core CPUs, GPUs and FPGAs,” IEEE Transactions on Computers, Vol. 65, No. 4, pp. 12831296 (2016). doi: 10.1109/TC.2015.2439256
[21] Mcintoshsmith, S., Price, J., Sessions, R. B., et al., “High Performance in Silico Virtual Drug Screening on Many-core Processors,” International Journal of High Performance Computing Applications, Vol. 29, No. 2, pp. 119134 (2015). doi: 10.1177/1094342014 528252
[22] Zhong, Z., Rychkov, V. and Lastovetsky, A., “Data Partitioning on Multicore and Multi-GPU Platforms Using Functional Performance Models,” IEEE Transactions on Computers, Vol. 64, No. 9, pp. 25062518 (2015). doi: 10.1109/TC.2014.2375202
[23] Li, Y., Métivier, L., Brossier, R., et al., “2D and 3D Frequency-domain Elastic Wave Modeling in Complex Media with a Parallel Iterative Solver,” Geophysics, Vol. 80, No. 3, pp. T101T118 (2015). doi: 10. 1190/geo2014-0480.1
[24] Olszewski, P., “Genetic Optimization and Experimental Verification of Complex Parallel Pumping Station with Centrifugal Pumps,” Applied Energy, Vol. 178, pp. 527539 (2016). doi: 10.1016/j.apenergy.2016.06.084
[25] Ingargiola, A., Lerner, E., Chung, S. Y., et al., “A Multispot Confocal Platform for High-throughput Freely Diffusing Single-molecule FRET Studies,” Biophysical Journal, Vol. 110, No. 3, pp. 194a195a (2016). doi: 10.1016/j.bpj.2015.11.1084