An Efficient Graph-Coloring Algorithm for Processor Allocation
Автор: Mohammed Hasan Mahafzah
Журнал: International Journal of Information Technology and Computer Science(IJITCS) @ijitcs
Статья в выпуске: 7 Vol. 5, 2013 года.
Бесплатный доступ
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.
Distributed System, Graph Coloring, CPU Scheduling, Multiprocessor System, CPU Utilization, Fully Connected Graph, Processor Allocation
Короткий адрес: https://sciup.org/15011923
IDR: 15011923
Список литературы An Efficient Graph-Coloring Algorithm for Processor Allocation
- C.H. Lee, K.G. Shin, “Optimal task assignment in homogeneous networks”, IEEE Transactions on Parallel and Distributed Systems, 8 (1997), pp. 119–129.
- 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.
- 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.
- Harry F. Jordan, Gita Alaghband, “Fundamentals of Parallel Processing”, 2003, Pearson Education, Inc.
- http://www.nlsda.buaa.edu.cn/~kexn/benchmarks/graph-benchmarks.htm, “Maximum Independent Set (MIS) and Minimum Vertex Cover (MVC)”, 2006.
- Al-Jaber, Ahmad and Sharieh, Ahmad, “Algorithms Based on Weight Factors for Maximum Independent Set”, Dirasat, Volume 27, Number 1, 2000, PP.74-91.
- Beigel, Richard, “Finding Independent Sets in Sparse and GeneralGraphs”, 2006.http://www.cis.temple.edu.cn/~beigel/papers/mis-soda.htm,
- 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.
- 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.
