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

3.3 IMPLEMENTATION ISSUES

The structure of the taxonomy concerning implementation issues is shown in Fig. 3.8. A discussion of this taxonomy then follows.

Figure 3.8 Classification of hybrid metaheuristic (implementation issues).

3.3.1 Specific versus General-Purpose Computers

Application-specific computers differ from general-purpose ones in that they usually only solve a small range of problems, but often at much higher rates and lower cost. Their internal structure is tailored for a particular problem, and thus can achieve much higher efficiency and hardware utilization than a processor that must handle a wide range of tasks.

Recently, the advent of programmable logic devices has made it easier to build specific computers for metaheuristics such as simulated annealing [3] and genetic algorithms [59]. A general architecture acting as a template for designing a number of specific machines for different metaheuristics (SA, TS, etc) has been proposed in [2]. The processor is built with XILINX FPGAs and APT1X interconnexion chips. Experiments evaluating a simulated annealing algorithm to solve the TSP achieves a speedup of about 37 times over an IBM RS6000 workstation. To our knowledge, this approach has not yet been proposed for hybrid metaheuristics.

3.3.2 Sequential versus Parallel

Most of the proposed hybrid metaheuristics are sequential programs. Parallel implementations of hybrid ...