International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 5, No. 7, 8 Jun. 2013
Cover page and Table of Contents: PDF (size: 431KB)
An Efficient Graph-Coloring Algorithm for Processor Allocation
Full Text (PDF, 431KB), PP.43-48
Views: 0 Downloads: 0
Author(s)
Index Terms
Distributed System, Graph Coloring, CPU Scheduling, Multiprocessor System, CPU Utilization, Fully Connected Graph, Processor Allocation
Abstract
This paper develops an efficient exact graph-coloring algorithm based on Maximum Independent Set (MIS) for allocating processors in distributed systems. This technique represents the allocated processors in specific time in a fully connected graph and prevents each processor in multiprocessor system to be assigned to more than one process at a time. This research uses a sequential technique to distribute processes among processors. Moreover, the proposed method has been constructed by modifying the FMIS algorithm. The proposed algorithm has been programmed in Visual C++ and implemented on an Intel core i7. The experiments show that the proposed algorithm gets better performance in terms of CPU utilization, and minimum time for of graph coloring, comparing with the latest FMIS algorithm. The proposed algorithm can be developed to detect defected processor in the system.
Cite This Paper
Mohammed Hasan Mahafzah, "An Efficient Graph-Coloring Algorithm for Processor Allocation", International Journal of Information Technology and Computer Science(IJITCS), vol.5, no.7, pp.43-48, 2013. DOI:10.5815/ijitcs.2013.07.05
Reference
[1]C.H. Lee, K.G. Shin, “Optimal task assignment in homogeneous networks”, IEEE Transactions on Parallel and Distributed Systems, 8 (1997), pp. 119–129.
[2]T.P. Ajith, C.S.R. Murthy, “Optimal task allocation in distributed systems by graph matching and state space search”, Journal of Systems and Software, 46 (1999), pp. 59–75.
[3]Ernst, A., Hiang, H., Krishnamoorthy, M., “Mathematical programming approaches for solving task allocation problems”, International Proceedings of the 16th National Conference of Australian Society of Operations Research., 2001.
[4]Harry F. Jordan, Gita Alaghband, “Fundamentals of Parallel Processing”, 2003, Pearson Education, Inc.
[5]http://www.nlsda.buaa.edu.cn/~kexn/benchmarks/graph-benchmarks.htm, “Maximum Independent Set (MIS) and Minimum Vertex Cover (MVC)”, 2006.
[6]Al-Jaber, Ahmad and Sharieh, Ahmad, “Algorithms Based on Weight Factors for Maximum Independent Set”, Dirasat, Volume 27, Number 1, 2000, PP.74-91.
[7]Beigel, Richard, “Finding Independent Sets in Sparse and GeneralGraphs”, 2006.http://www.cis.temple.edu.cn/~beigel/papers/mis-soda.htm,
[8]Ahmad Sharieh, Wagdi Al-Rawagefeh, Mohammed H. Mahafzah, And Ayman Al-Dahamsheh, “An Algorithm for Finding Maximum Independent Set in a Graph,“ European Journal of Scientific Research (EJSR), UK, Volume 23, Number 4, 2008, PP. 586-596.
[9]Johnson, D.S., “Worst-case behavior of graph coloring algorithm”, Proceedings of the Fifth Southeastern Conference on Combinations, Graph Theory and Computing, Canada, 1974, PP. 513-528.