Optimizing the speed-up of parallel programs and load balancing in distributed systems

Abstract:

This paper proposes methods to optimize the speed-up that can be obtained for a parallel program in a distributed system by modelling the assignment of the tasks of a parallel program as a graph-partitioning problem. The tasks (set of instructions that must be executed sequentially) that comprise the program are represented by weighted nodes, and the arcs of the graph represent the precedence order between tasks. Became this problem is in general NP-hard, several heuristic algorithms are proposed, investigated, and compared. The approaches presented are: a neural-network-based algorithm (based on the random neural model of Gelenbe), an algorithm based on simulated annealing, a genetic-algorithm-based heuristic, and a heuristic based on Kernighan's algorithm.

Año de publicación:

1998

Keywords:

• Genetic Algorithms
• Parallel programs
• Combinatorial optimization
• neural network
• Distributed computing environment
• Task assignment

Fuente:

scopus