Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

4.7 SUMMARY

During the last decade, there has been a growing interest in optimization algorithms that rely on analogies to natural processes. The emergence of massively parallel computers mades these algorithms of practical interest. Perhaps the well-known algorithms in this class are genetic algorithms, stochastic learning systems, and simulated annealing.

In this chapter, we have identified various important optimization problems arising in conservative and optimistic parallel simulations, such as scheduling/load balancing/partitioning, rollback reduction, synchronization, and communication overhead minimization. We have discussed the application of simulated annealing with an adaptive schedule to the partitioning problem for conservative simulations, whereby each logical process is allowed to proceed if and only if it is certain that it will not receive any earlier event. The main objective is to develop a partitioning algorithm to find good (suboptimal) solutions based upon realistic estimates of computation and communication load. The results obtained clearly indicate that careful partitioning is important to the efficient implementation of conservative simulations.

Next, we considerd the time-warp paradigm, whereby each logical process proceeds with its computations without any constraints and where it is necessary to control the traffic flow and balance the computational load on differents LPs. The problem of load balancing in optimistic simulation is approached in two ways. ...