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

4.1 INTRODUCTION

For obvious reasons, there has been a continued interest in developing efficient solutions and/or heuristics to hard combinatorial optimization problems. Many such solutions are based on biological (such as cellular automata, neural networks, DNA, and molecular computing), evolutionary (e.g., genetic algorithms), and physical/natural phenomena (such as simulated annealing, Brownian motion, probablistic hill climbing on electronic potential well, stochastic processes), and so on. Some of these solution techniques are classified under the realm of a general paradigm called biocomputing, It also turns out that almost all of these approaches are inherently parallel in nature. Consequently, various parallel algorithms have been proposed for many real-world application problems including very large-scale integrated (VLSI) circuit design and layout, partitioning/load balancing, multiprocessor scheduling, to mention a few. Actual implementations of these solutions on parallel/distributed machine architectures yield significant speedup gains over sequential implementations.

Over the last two decades, simulations of complex systems have been identified as an important area to exploit the inherent parallelism present in application problems. To this end, a significant body of literature on parallel/distributed simulation has been proposed (see [4, 6, 11, 13]). There are two basic approaches to parallel simulation: conservative and optimistic. While conservative synchronization ...