Cross entropy based module alocation for distributed systems

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

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.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Communication Systems
  • Electrical Engineering, Electronic Engineering, Information Engineering
Original languageEnglish
Title of host publicationProceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA
EditorsTeofilo Gonzalez
PublisherACTA Press
ISBN (Print)0-88986-421-7
Publication statusPublished - 2004
Publication categoryResearch
Peer-reviewedYes

Total downloads

No data available