next up previous
Next: Comparing the systems Up: Optimization Previous: efficient code

parallel code

Another method of speeding the replication process is to parallelize. We have seen this happen opportunistically in the case of ``hyper-parasites'' which steal CPUs from parasites, and in that way can simultaneously produce more than one daughter.

However, an enhancement was made to the instruction set in which ``split'' and ``join'' instructions were added, allowing a process to split into a multi-threaded process, and then optionally to join all the threads back into a single thread [38]. A seed organism was created in which an initially single threaded process splits into two threads just before entering the loop that copies bytes. The two processors then divide up the work of copying bytes, such that one processor copies the first half of the code, while the other copies the second half. After exiting the loop, the two threads join into one.

Through evolution, these algorithms have increased their parallelism to as many as thirty-two processors. The thirty-two processor algorithm eliminated the loop. Each processor simply copies two bytes. Sixteen processor organisms have been found with sixty byte algorithms. Since sixteen does not divide evenly into sixty, the division of the work is more complicated, and the solutions involve some overlap of the data copied by adjacent processors.



Thomas S.Ray
Mon Jul 15 15:51:28 JST 1996