The design in Figure 1 is a coarse-grained pipeline. This is evident by noting that when a module completes a task as described in Section 3.2, it immediately awaits more input to repeat processing. Because of this pipelining, GA operations do not have to be suspended while other GA operations run, which happens in a sequential software implementation. Thus a significant speedup over software is realized.
Parallelization of HGA modules is also possible. For example, multiple selection modules can be inserted, all of which feed into a single CMM (Figure 2). To extend the parallelization, the selection-crossover-fitness pipeline could be replicated to form several parallel pipelines by replicating the highlighted portion (dotted box) of Figure 2. In this case, the duty of writing new members to memory and maintaining records of the HGA's state (see Section 3.2, Item 6) would have to be shifted from the FM to a new module called the memory writer. This would be necessary because parallel fitness modules would have difficulty maintaining these values among themselves.
Figure 2: Example of parallel selection modules.
The highest degree of parallelism of the HGA involves banks of an arbitrary number of selection, crossover/mutation and fitness modules. Connectivity is complete in the sense that each selection module is connected to each CMM and each CMM is connected to each FM. This configuration would maximize the utilization of each module but also complicates the communication between modules.
The pipelined and parallel configurations presented in this section can be combined in myriad ways, each with different degrees of communication complexity and overall efficiency. To simplify the design process, only the configurations in Figures 1 and 2 were created, analyzed and simulated (Sections 4.1 and 4.2). Also, due to area constraints on the FPGAs, only the configuration in Figure 1 was implemented in a prototype (Section 4.4).
Last modified 11 August 1999.