On File and Task Placements and Dynamic Load Balancing in Distributed Systems

Po-Jen  Chuang; Chi-Wei Cheng

doi:10.6180/jase.2002.5.4.07

On File and Task Placements and Dynamic Load Balancing in Distributed Systems

Po-Jen Chuang This email address is being protected from spambots. You need JavaScript enabled to view it.¹ and Chi-Wei Cheng¹

¹Department of Electrical Engineering Tamkang University Tamsui,Taiwan 251, R.O.C.

Received: July 24, 2001
Accepted: November 6, 2002
Publication Date: December 1, 2002

Download Citation: ||https://doi.org/10.6180/jase.2002.5.4.07

ABSTRACT

Two distributed system problems, the file and task placement problem and the dynamic load balancing problem, are investigated in this paper. To find the placement of files and tasks at sites with minimal total communication overhead, we propose using the Simulated Annealing approach and multiple objective functions. Experimental results show that our proposed approach depicts superior performance with much less complexity over the previously introduced Genetic Algorithm approach. Dynamic load balancing is employed to equalize processor loads in a distributed system. It allows excessive tasks at a heavily loaded processor to be migrated to another processor with a light load during execution. To effectively lift up the acceptance rates for such task migration requests, we propose an efficient new scheme that yields much improved acceptance rates, followed by reduced unnecessary request messages and communication overhead, when compared with the standard sender-initiated scheme and the fairly complicated GA-based approach.

Keywords: Distributed Systems, Dynamic Load Balancing, File and Task Placements, Genetic Algorithms, Objective Functions, Request Acceptance Rates, Sender-Initiated, Simulated Annealing

REFERENCES

[1] Corcoran, A. L. and Schoenefeld, D. A., “A Genetic Algorithm for File and Task Placement in a Distributed System,” Proc. 1st IEEE Conf. on Evolutionary Computation, pp. 340-344 (1994).
[2] Kirkpatrick, S., Gelatt, C. D., Jr. and Vecchi, M. P., “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680 (1983).
[3] Yip, P., “The Role of Regional Guidance: The Guided Evolutionary Simulated Annealing Approach,” Ph.D. Dissertation, Department of Electrical Engineering and Applied Physics, Case Western Reserve University, Cleveland, U.S.A. (1993).
[4] Shivaratri, N. G., Krueger, P. and Singhal, M., “Load Distributing for Locally Distributed Systems,” IEEE Computer, Vol. 25, pp. 33-44 (1992).
[5] Munetomo, M., Takai Y. and Sato, Y., “A Genetic Approach to Dynamic Load Balancing in a Distributed Computing System,” Proc. 6th Int'l Conf. on Genetic Algorithms, pp. 418-421 (1994).
[6] Bell, D. A., “Difficult Data Placement Problems,” Computer Journal, Vol. 27, pp. 315-320, (1984).
[7] Chang, C. C. and Shielke, “On the Complexity of the File Allocation Problem,” Proc. Conf. on Foundations of Data Organization (1985).
[8] Dowdy, L. W. and Foster, D. V., “Comparative Models of the File Assignment Problem,” ACM Computing Surveys, Vol. 14, (1982).
[9] Ceri S., Martella, G. and Pelagatti, G., “Optimal File Allocation for a Distributed Database on A Network of Minicomputers,” Proc. ICOD 1 Conf. (1980).
[10] Holland, J. H., Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, U.S.A. (1975).
[11] Srinivas, M. and Patnaik, L. M., “Genetic Algorithms: A Survey,” IEEE Computer, Vol. 27, pp. 17-26 (1994).
[12] Corana, A., Marchesi, M., Martini, C. and Ridella, S., “Minimizing Multimodal Functions of Continuous Variables with the Simulated Annealing Algorithm,” ACM Trans. on Mathematical Software, Vol. 13, pp. 262-280 (1987).
[13] Richardson, J. T., Palmer, M. R., G. E. Liepens G. E. and Hilliard, M., “Some Guidelines for Genetic Algorithms with Penalty Functions,” Proc. 3rd Intl. Conf. on Genetic Algorithms (1989).
[14] Whitley, D. and Kauth, J., “genitor: A Different Genetic Algorithm,” Proc. Rocky Mountain Conf. on Artificial Intelligence, pp. 118-30 (1988).
[15] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, U.S.A. (1989).
[16] Eager, D. L., Lazowska, E. D. and Zahorjan, J., “Adaptive Load Sharing in Homogeneous Distributed Systems,” IEEE Trans. on Software Engineering, Vol. 12, pp. 662-675 (1986).