Heuristics to optimize the speed-up of parallel programs

Abstract:

In this paper we propose methods to optimize the speed-up which 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) which compose the program are represented by weighted nodes, and the arcs of the graph represent the precedence order between tasks. Because this problem is in general NP-hard we propose and investigate several heuristic algorithms, and compare their performance. The approaches we present are: a neural network based algorithm (based on the random neural model of Gelenbe), an algorithm based on simulated annealing and a genetic algorithm based heuristic.

Año de publicación:

1996

Keywords:

Fuente:

scopus