Cross entropy based module alocation for distributed systems

Författare

Niklas Widell
Christian Nyberg

Redaktör

Teofilo Gonzalez

Summary, in English

In the module allocation problem a collection of software modules are to be assigned to physical processing nodes, subject to execution and communication cost. The cost of an allocation is a function of the execution costs and the communication costs for any pair of modules allocated to distinct processors. The module allocation problem has been well studied and is known to be NP-complete except for certain communication configurations. To solve the problem, several heuristics have been proposed. This pa per discusses an alternative approach to solving the module allocation problem by applying a stochastic optimization method called the Cross Entropy (CE) Method. The CE Method is a state-of-the-art stochastic method for solving combinatorial and multi-extremal continuous optimization problems. The CE method uses a distribution with parame ter v to generate sample allocation. The generated samples are then used to update v according to sample quality. This process is repeated until the distribution converges to a pos sibly optimal allocation. The results in this paper indicate that the CE method can successfully be applied to the mod ule allocation problem and efficiently generate high qual ity solutions. Also, the CE method allows the use of non standard objective functions that are used to find allocations that have multiple conflicting objectives.

Avdelning/ar

Institutionen för elektro- och informationsteknik

Publiceringsår

2004

Språk

Engelska

Publikation/Tidskrift/Serie

Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA

Fulltext