Efficiency of Parallelisation

As shown in Section 5.3.2, the genetic algorithm provides a large scope for distributes memory parallelism (see also Fig. 2).

The following table gives the speedup $S_p$ and the efficiency $E_p$ as defined in Section 5.1.1 for three different network sizes of the genetic Encoder/Decoder problem using three different population sizes. The ENC/DEC problem was chosen because the number of training patterns $t$ is equal to the number of input nodes $n$, which results in a computation/communication ratio $r$ of order $O(n)$. For all other problems, $r$ is of order $O(2^n)$ which would soon lead to efficiencies of nearly $100\%$ and make comparisons difficult for greater network sizes.

The simulations were executed in parallel on 4, 8 and 12 processors ( encpar) and the optained performance was compared to the sequential version encseq on a single transputer.

${\bf E}_p$,${\bf S}_p$		8-3-8 ENC/DEC			16-4-16 ENC/DEC			32-5-32 ENC/DEC
pop.		100	1000	10000	100	1000	10000	100	1000	10000
	$S_4$	3.22	3.61	3.56	3.88	3.88	3.83	3.90	3.99	3.93
4	$E_4$	81%	90%	89%	97%	97%	96%	98%	100%	98%
	$S_8$	2.61	5.91	6.00	5.30	7.05	7.21	6.88	7.76	7.66
8	$E_8$	33%	74%	75%	66%	88%	90%	86%	97%	96%
	$S_12$	2.72	6.29	7.68	6.12	9.69	9.69	9.75	10.92	11.13
12	$E_12$	23%	52%	64%	51%	81%	81%	81%	91%	93%

The efficiency increases with the problem size, due to larger training sets an therefore longer error calculations. It also increases with larger population sizes which reduce the relative impact of the overhead involved for setting up the connections. Higher numbers of processes reduce efficiency, which can be explained by Amdahl's Law (Section 5.1.2) and by the fact, that the overhead for routing information between the master and the slaves increases with the number of transputers in the network. This explains the very high efficiency of the 4 transputer networks, because they require no routing at all.