Scheduling tasks to multi-processor platform using constraint programming and tabu search
/ 0
- Details
- Category: Information technologies, systems analysis and administration
- Last Updated on 02 October 2016
- Published on 02 October 2016
- Hits: 3637
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.
 04_2016_Xiaohong
|
|
 2016-09-26  288.33 KB  824 |
|
Archive