Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Cross entropy based module alocation for distributed systems

Widell, Niklas LU and Nyberg, Christian LU (2004)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA
editor
Gonzalez, Teofilo
publisher
ACTA Press
ISBN
0-88986-421-7
language
English
LU publication?
yes
id
f59ecaaa-ac29-4e29-94f4-06afd765157a (old id 532408)
date added to LUP
2016-04-04 11:20:21
date last changed
2020-01-08 15:01:57
@inproceedings{f59ecaaa-ac29-4e29-94f4-06afd765157a,
  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.}},
  author       = {{Widell, Niklas and Nyberg, Christian}},
  booktitle    = {{Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA}},
  editor       = {{Gonzalez, Teofilo}},
  isbn         = {{0-88986-421-7}},
  language     = {{eng}},
  publisher    = {{ACTA Press}},
  title        = {{Cross entropy based module alocation for distributed systems}},
  url          = {{https://lup.lub.lu.se/search/files/5750457/625308.pdf}},
  year         = {{2004}},
}