i-manager Publications

A new greedy algorithm for multi-processor scheduling with gang scheduling

Sarath B. Siyambalapitiya*, M. Sandirigama**

* Research Student, Department of Statistics and Computer Science, University of Peradeniya, Sri Lanka.

** Head, Department of Computer Engineering, University of Peradeniya, Sri Lanka.

Periodicity:July - September'2010
DOI : https://doi.org/10.26634/jse.5.1.1202

Abstract

In this study, we propose some greedy algorithms for the multi-processor job scheduling problem. A given list of jobs are arranged according to the time duration for processing. Depending on the job processing times, some jobs are divided into multi-threads while others remain as single thread jobs. Multi-thread jobs are processed based on the concept of gang scheduling. A lower bound for the total processing time is computed. The results of the proposed algorithm is presented using a percentage gap from the optimal solution using this lower bound.

Keywords

Multi-processor,Greedy,Gang scheduling

How to Cite this Article?

Sarath B. Siyambalapitiya and M. Sandirigama (2010). A New Greedy Algorithm for multi-processor scheduling with gang scheduling. i-manager’s Journal on Software Engineering, 5(1),7-12. https://doi.org/10.26634/jse.5.1.1202

References

[1]. Feitelson, D.G. et.al. (2004). Parallel Job Scheduling- A Status Report, Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, Vol.3834, pp. 1-16.

[2]. Goes, L.F.B., and Martins, C.A.P.S. (2004). Proposal and Development of a Reconfigurable Gang Scheduling Algorithm, Master thesis, PUC Minas, May 2004.

[3]. Karatza, H.D. (2006). Scheduling Gangs in a Distributed System, International Journal of Simulation Systems, Science Technology, Vol 7, No.1, pp 15-22.

[4]. Rajagopalan, M. et.al. (2007). Thread Scheduling for Multi-Core Platforms, Proceedings of USENIX Workshopon Hot Topics in Operating Systems, San Diego, California.

[5]. Siyambalapitiya, R., and Sandirigama M. (2010). Efficient Greedy Algorithm for Multi-Processor Scheduling, i-manager’s Journal on Software Engineering, Vol. 4, No. 4, April-June. pp. 50-54.

[6]. Weinberg, J. (2006). Job Scheduling on Parallel Systems, Ph.D. Research Examination, University of California, San Diego.

[7]. Wiseman, Y., and Feitelson, D.G. (2001). Paired Gang Scheduling, Jerusalem Parallel & Distributed Processing Symp., Jerusalem, Israel, November.

	North Americas,UK, Middle East,Europe		India	Rest of world
	USD	EUR	INR	USD-ROW
Pdf	35	35	200	20
Online	35	35	200	15
Pdf & Online	35	35	400	25

A new greedy algorithm for multi-processor scheduling with gang scheduling

Abstract

Keywords

How to Cite this Article?

References

If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Options for accessing this content: