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

1Software School, Dalian University of Technology, Dalian 116621, P.R. China
2Information 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  


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


  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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


42nd percentile
Powered by  Scopus

SCImago Journal & Country Rank

Enter your name and email below to receive latest published articles in Journal of Applied Science and Engineering.