Scheduling tasks to multi-processor platform using constraint programming and tabu search

User Rating:  / 0
PoorBest 

Authors:

Xiaohong Kong, Henan Institute of Science & Technology, Xinxiang, China

Ruihua Li, Henan Institute of Science & Technology, Xinxiang, China

Yanqun Zhang, Henan Institute of Science & Technology, Xinxiang, China

Abstract:

Purpose. Multiple processors can be integrated together into a multi-core platform and deal with large-scale science problems because of its excess computation and extensive parallelization. This paper mainly aims at tasks scheduling problem on this platform with shared memory and communication channel.

Methodology. Generally, intensive-computation job is portioned into coarse-grain sub-tasks so that tasks are executed in parallel (simultaneously) to improve the computation performance. The proposed algorithm employs constraint programming to find a feasible solution and uses local search to impove the solution and speed up the process.

Findings. Sharing a variety of available resources, the multi-processors scheduling is a complex combinatory optimization problem and resource-constrainted problem. We investigate how to obtain a rational solution or sub-optimal solution in a short period. At the same time, tasks with different features are also investigated to find how the performances of applications are influenced in specific target platform.

Originality. When tasks are assigned to different processors, various resource constraints, including data storage, executing cost, tasks priority and communication cost among processors, must be considered. A hybrid algorithm based on Tabu search is studied to optimize the completion time of applicaitons satisfying these contraints.

Practical value. The algorithm is implemented in IBM ILOG CPLEX Optimization Studio environment and gives better results compared with other algorithms. The proposed algorithm is an effective strategy and the technique can improve search efficiency and solution performance for multiprocessor scheduling problem.

References/Список літератури

1. Davis, R.I. and Burns, A., 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys, Vol. 43, No. 4, pp. 1–44.

2. IBM Corporation, 2010. Cell Broadband Engine Programming Handbook, http://www-01.ibm.com/ chips/techlib/techlib.nsf/techdocs9F820A5FFA3ECE8C8725716A0062585F.

3. Benini, L., Lombardi, M., Milano, M. and Ruggiero, M., 2008. Optimal resource allocation and scheduling for the CELL BE platform. Annals of Operations Research, Vol. 184, No. 1, pp. 51–77.

4. Leila, I. and Driss, G., 2011. Performance Evaluation of Convolution on the Cell Broadband Engine Processor. IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No. 2, pp. 337–351.

5. Edis, E.B. and Oguz, C., 2012. Parallel machine scheduling with flexible resources. Computers & Industrial Engineering, Vol. 63, No. 2, pp. 433–447.

6. Heinz, S., Ku, W.Y. and Beck, J. C., 2013. Recent Improvements Using Constraint Integer Programming for Resource Allocation and Scheduling. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013.

7. IBM Corporation, 2011. IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual v12.4.

8. Canon, L.C. and Jeannot, E., 2009. Precise Evaluation of the Efficiency and the Robustness of Stochastic DAG Schedules. Research Report. Research Report RR-6895, INRIA.

9. Thevenin, S., Zufferey, N. and Widmer, M., 2013. Tabu search for a single machine scheduling problem with discretely controllable release dates. In: Slovenian Society Informatika, 12th International Symposium on Operational Research SOR’13 in Slovenia. Dolenjske Toplice, September 25–27, 2013. Slovenian Society Informatika – Section for Operational Research, Ljubljana, Slovenia.

Files:
04_2016_Xiaohong
Date 2016-09-26 Filesize 288.33 KB Download 475

Visitors

4298540
Today
This Month
All days
808
808
4298540

Guest Book

If you have questions, comments or suggestions, you can write them in our "Guest Book"

Registration data

ISSN (print) 2071-2227,
ISSN (online) 2223-2362.
Journal was registered by Ministry of Justice of Ukraine.
Registration number КВ No.17742-6592PR dated April 27, 2011.

Contacts

D.Yavornytskyi ave.,19, pavilion 3, room 24-а, Dnipro, 49005
Tel.: +38 (056) 746 32 79.
e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.
You are here: Home Archive by issue 2016 Contents No.4 2016 Information technologies, systems analysis and administration Scheduling tasks to multi-processor platform using constraint programming and tabu search