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

4.3 PREVIOUS AND RELATED WORK

Scheduling, load balancing, and partitioning, in parallel and distributed systems in general, and parallel simulation in particular, have long been identified as important optimization problems. Finding an optimal solution is found to be NP-hard [14] in all but very restricted cases. Thus research has focused on the development of heuristic algorithms to find suboptimal solutions. Biocomputing/evolutionary/natural techniques have been proposed to solve these problems elegantly by such methods as simulated annealing, genetic algorithms, neural networks, or stochastic processes.

Graph partitioning has been applied to various VLSI design problems [20]. Existing literature on partitioning and mapping problems is based on approaches like graph theoretic, queueing theoretic, mathematical programming, numeric and nonnumeric heuristics, and/or combined methods (see [2]). The partitioning problem can be defined as follows. Group the nodes of the system graph into clusters such that the sum of link weights external to the clusters is minimized and the execution load is distributed uniformly among the processors. We assume that the intercommunication cost (IMC) between each pair of processes is known, represented by the weight of an undirected edge connecting the two nodes,¹ and that the processor utilization is maximized. In the following, we give an overview of a few approaches to this problem proposed for parallel computing in general.

Bokhari [2] and Nicol ...