We consider the speed-up
that can be obtained for a parallel program in a distributed system. The
modeling of parallel program in a distributed system. The modeling of
parallel programs by acyclic graphs allows the study of the problem of
distributed processing as a graph partitioning problem. Such a model consist
of nodes instructions that must be executed sequentially), and of arcs that
represent the precedence order between tasks. Thus, the problem turns out to
find the task graph partitioning which maximizes execution speed-up of the
parallel program. This problem is NP- complete. To optimize, we specially use
a method based on the brain behavior, the random neural model of Gelembe, and we compare it with other approximate
methods: an algorithm based on the simulated annealing optimization
heuristic, a heuristic using genetic algorithm and an algorithm based on Kernighan´s heuristic.
|