An improved evolutlonary approach for the cluster allocation problem

Abstract

In a distributed system, consisting of a set of interconnected local area networks, users migrate to different machines, users invoke different programs and users and programs need distinct data files to satisfy their expectations. Consequently optimal allocation of parallel program tasks can increase system performance as results of traffic cost reducti9n between clusters2• The problem of allocating a program in a particular system node can be divided into two subproblems: i) allocate the program in a cluster such that traffic costs are minimized and ii) within a particular cluster choose the node following sorne load balancing criteria [5]. To solve subproblem i), in 1992 U. M. Borghoff [2] proposed the Individual Program Execution Location Algorithm IPELA, where essentially giving a distribution of data files the best allocation for program execution, minimizing the expected intercluster traffic, is searched. The algorithm uses diverse input data such us the cost for starting a program at sorne node [10], thedependencies between program and data files [1], separated read and write access costs [9], the impact of l/O activities on the communication costs [8] and the allocation of program and data files [3]. . As the number of possible allocations induce high complexity and the model could not be solved too optimality Borghoff reduced the number of combinations by limiting the number of data file replicas and looking for those combinations where the relevant file sets's allocation is varied. This approach reduced complexity. Nevertheless running ¡PELA implied evaluation of each solution in a large problem space.