T HE U NI VE R SI TY O F M ICH I GA N COLLEGE OF LITERATURE, SCIENCE., AND THE ARTS Computer and Communication Sciences LDepartment COMPARISON OF GENETIC ALGORITHMS AND GRADIENT-BASED OPTIMIZERS ON PARALLEL PROCESSORS: EFFICIENCY OF USE OF PROCESSING CAPACITY Albert D. Bethke November 1976 Logic of Computers Group Technical Report No. 197 with assistance from: National Aeronautics and Space Administration Grant No. NSG-1176 Langly Research Center Hampton, Virginia

<C-l 25 9 -' rl

ABSTRACT Parallel computers such as the ILLIAC IV [3], CDC STAR, and C.mmp [12] are in limited use today. The use of microprocessors promises to make parallel processor computers' very practical in the near future. In this paper, we will explore the question of performing function optimization on a parallel processor computer. In particular, we will compare Holland's reproductive plans [6], [8] (suitably modified for parallel execution) with more standard (gradient based) function, optimizers (again, modified for parallelism) [2], [9]. We will first consider an elementary reproductive plan and later a more sophisticated reproductive plan. Since reproductive plans are based on models from population genetics, we may reasonably expect reproductive plans to be well suited to parallel implementation. Indeed., recasting the elementary plan into a parallel form is rather straightforward. The more sophisticated plan poses some problems however. Gradient based optimizers are easily put into parallel form, but less efficiently utilize a multi-processor than the reproductive plans.

Table of Contents Elementary Reproductive Plan.1.......... Efficiency Analysis....................... 6 Sophisticated Reproductive Plan................. 9 Efficiency Analysis.17 Standard (Gradient based) Function Optimizers..........21 Summary.24 Refe.rences............................ 25 Explanation of Figures......................26

Elementary Reprod uctive Plan The elementary reproductive plan has the following form: generate initial (random) population repeat until desired stopping criterion: compute selection probabilities generate new population (using crossover and mutation) Each of the steps above may be done in a?rallel fashion, but each step must be completed before the next step can be started. In the following assume that there are N individuals in the population denoted by A(l), A(2),...,A(N). The objective function will be denoted by f. Associated with each individual are two numbers. First, VALUE(I) will be the function value for the point represented by A(I). That is, VALUE(I) = f(A(I)). (The "fitness" of an individual is simply tile function value for that individual, but all fitnesses are shifted to ensure that they are positive: fitness(I) = VALUE(I) - FMIN + 1.0, where FMIN is the smallest function value encountered so far.) Second, the selection probabilities are kept in an array PROB. PROB(I) is the probability of selecting individual A(I) to participate in an application of the crossover operator while generating a new population. Lipton [11] suggests an ALGOL-like notation for describing parallel algorithms. In the same spirit, we will use PARFOR index:= initial STEP increment UNTIL final DO <statement> to indicate a repetition of <statement> for the specified values of the index variable with parallel execution for different index values and arbitrary interleaving of these executions. 1

2 So, to generate the initial population: PARFOR I:= 1 UNTIL N DO A(I):= random point in domain of f; To compute the selection probabilities we must do the following: PARFOR I:= 1 UNTIL N DO TEMPl(I):= TEMP2(I):= VALUE(I):=f(A(I)); compute SUM = VALUE(1) + VALUE(2) +... + VALUE(N) and find new FMIN; PARFOR I:= 1 UNTIL N DO PROB(I):= (VALUE(I) - FMIN + 1.0)/(SUM - N*(FMIN - 1.0)) We may compute the sum of the function values and find the minimum function value in the same loop: M:= N; WHILE M > 1 DO BEGIN PARFOR I:= 1 UNTIL FLOOR(M/2) DO BEGIN TEMP1 (I):= TEMP1 (2*I-1) + TEMP1i(2*I); IF TEMP2(2*I-1) < TEMP2(2*I) THEN TEMP2(I):= TEMP2(2*I-1) ELSE TEMP2(I):= TEMP2(2*I); END; IF M is odd THEN BEGIN TEMP1 (CEiLING(M/2)):= TEMP1 (M); TEMP2 (CEILING(M/2)):= TEMP2 (M) END;

3 M:= CEILING(M/2) END; SUM TEMPl(1); FMIN:= TEMP2(1l); The parallelism is rather limited here. The PARFOR loops will be able to utilize only half as many processors each time through the WHILE loop. And there is the special case when M is odd plus the need to halve M each time. This can be improved somewhat if N is a power of two. In that case, we need not check for M being odd or find FLOOR(M/2) or CEILING (M/2). Alternatively, K let K = rlog2(N)J, L = 2, so N < L < 2N. And, after generating the initial population, set TEMP1(J) = 0 and TEMP2(J) = VALUE(1), for N < J < L. These values will remain unchanged until the reproductive plan terminates. This also eliminates the need to test for odd values of M, since we can begin with M:= L which is a power of two. In fact, if we have L/2 processors, each of them can execute the same program. Processor J's program: FOR COUNT:= 1 UNTIL K DO BEGIN sum and compare block TEMP1(J): TEMP1 (2*J-1) + TEMP1(2*J); IF TEMP2(2*J-l) < TEMP2(2*J) THEN TEMP2(J):= TEMP2(2*J-1) ELSE TEMP2(J):= TEMP2(2*J); END sum and compare block; This assumes that the processors work synchronously.

4 To generate the new population: PARFOR I I= UNTIL N DO BEGIN: PARENTi:= SELECT; PARENT2:=SELECT; NEW(I):=CROSS-OVER(PARENT1,, PARENT2); mutate NEW(I) -END; SELECT is a procedure which chooses an individual from the current population at random based-on the selection probabilities computed earlier. CROSS-OVER is a procedure which performs a cross-over on 2 individuals to produce a new individual. PARENT1 and PARENT2 must be local to the PARFOR loop - or better yet, there should be one PARENT1 and one PARENT2 associated with each processor. These two values could be kept in registers (rather than keeping them in storage) since they are only needed for a very short time. In addition, each processor should have its ~own random number seed. This seed might be kept in a register also since. the random number generator is heavily used by this reproductive plan. Finally, to replace the old population by the new population: PARFOR I I= UNTIL N DO A(I):=NEW(I); Notice that if we have N processors, they can all exec ute exactly the same program (synchronously). It is therefore very well suited for execution on a singl-e-instruction-stream-multiple-data-stream computer. This program

5 one after the other, and disable the processors which should not execute that part. Using fewer than N processors poses no problems except the obvious scheduling problem of associating the proper index variable values (in a PARFOR loop) with the proper processor. If we use an "asynchronous multiprocessor", then the processors will have to be artificially synchronized and we may proceed only as rapidly as the slowest processor allows us. However, since each processor executes the s-ame code, using the same arrays at the same time, we woilct not expect any significant differences in execution times.

Efficiency Analysis The bottleneck for this algorithm is computing the sum of the function values and mi nimum function value in order to find the select-ion probabilities. Even with N processors, the summation cannot be done in one step. The best that can be done-is to add the values in pairs following a binary tree to obtain the final result in lgN steps.. But the computational sequence to find this sum (and the minimum value at the same time) is very short and simple. Let the time required for one processor to execute the block labeled "sum and compare block" above for only one value of COUNT be C Let the time required to ex ecute the S'. remainder of the program (excluding initialization) be CR Notice, C~ includes the final step'in computing selection probabilities (PROB(I) VALUE(J)/SUM)., the time required to generate a new individual, and the time to place that individual into the population. So CR ~> C R S. Using N processors, the computation time for one generation is [log2NJ * C + CR Using only 1 processor., one generation requires (N-1)C S + NCR units of time. And with 1 < P < N processors we have [1] + rlog2P] - l)CS +PFiCR as the computation time per generation. To carry this one 5LUp ]YUFLIMEr, if N/P = m where 0 < m < N and m is an integer, then the computation time per generation is

7 Experience with reproductive plans [4]., [5], [6] suggests that larger populations lead to better long term performance at the expense of the short term performance. So the population size must be chosen accordingly. For sequential machines, populations larger than a few hundre d individuals generally lead to unacceptably slow optimization. For N < 200, and with C ~< CR (say C5 1 O. the computation time per generation using P S R S~~~~ CR) processors is well approximated by For larger populations, this approximation is not as good unless the ratio CR/CS is increased also. See figures 6-10. Define the "speed-up (coefficient)" for P processors to be the ratio of the execut ion times using only 1 processor and using P processors. Then S [ R N S~ ~ ~~~~~~~S the P processors). Notice this is just - So N EP P [N N never exceeds 1 and'is minimal for P =N- 1. For P=N -1, 1N sn rcsosweePde ntdvd scerywseu sic oepoesr eanil urn ato ahPRO op e

8 Pherefore, the processor-sare kept busy nearly all the time. The elementary reproductive plan lends itself well to parallel implementation. Using more than N processors would reduce the computation time even fnore. The loop which does the summation and finds the minimum of the function values for the current population could be sped up by having 2 or 3 or even more processors executing the program for processor J. The addition of TEMPl (2*J-1) + TEMPl (2*J) and the comparison of the TEMP2 values can be done concurrently. Some of the sections of the rest of the program can be similarly sped up by using more than N processors. PAREN'T1 and PARENT2 can be chosen simultaneously for example. And the code for SELECT and CROSSOVER and MUTATE undoubtably can be implemented with reasonable efficiency using a small number of processors. So usihg 2N or 3N or maybe inN, for small m, processors should reduce the computation. time per generation by almost m over the time required with only N processors.. Synchronizing the processors would be more difficult and there might be some not yet discovered bottlenecks which would reduce the efficiency of using more than N processors. in.-any case, if N is 50, 100, or 200, 2N or 3N processors may not be available.

Sophisticated Reproductive Plan The plan we will consider was developed by deJong [6] and performs much better than the simple reproductive plan. The form of this sophisticated plan is: generate initial (random) population repeat until desired stopping criterion: compute selection probabilities generate new individuals incorporate new idividuals into population Here we do not replace the entire population at once, but only G < N individuals each generation. Other differences between the elementary and sophisticated plans incl ude forcing each-individual to have very nearly the expected number of offspring (based on selection probabilities), and to apply crossover with a probability less than 1 (the elementary plan always applied crossover in generating new individuals)., These and other differences will become more apparent as the sophisticated plan is put into parallel form. The initial population may be generated as before. The selection probabilities are computed in the same way as for the elementary plan with one exception - in the same loop that sums the function values and find's the minimum value, we also find the index of the best individual. (The best individual is saved from one generation to the next to ensure that the optimizer does not. "regress".)

10 PARFOR I 1 UNTIL N DO BEGIN TEMPI1(I) TEMP 2(I) VALUE 1 f(A(I) BEST (I) I END M N; WHILE M > 1 DO BEGIN PARFOR I 1 UNTIL FLOOR(M/2) DO BEGIN TEMP1(I) TEMP1(2*I-1) + TEMP1.(2*I); IF TEMP2(2*I-1) < TEMP2(2*I) THEN TEMP2(I) TEMP2(2*I.-1) ELSE TEMP2(I) TEMP2(2*I); IF VALUE(BEST(2*1-1)) > VALUE(BEST(2*1)) THEN BEST(I) BEST(2*I-1) ELSE BEST(I) BEST(2*I) END IF M is odd THEN BEGIN TEMP1(CEILING(M/2)) TEMP1(M); TEMP2(CEILING(M/2)) TEMP2(M); BEST(CEILING(M/2)) BEST(M) END;

SUM:=TEMPi1(1); FMIN:=TEMP2(l); BEST-INDEX BEST(l); save best string if desired; PARFOR I:=1 UNTIL N DO PROB(I):=VALUE(I)/SUM; Again, the parallelism can be improved greatly by using some dummy variables. Let K og2NJ, L = 2,so N <L <2N After generating the initial population, set TEMPI(J) = 0, TEMP2(J)= VALUE(1), BEST(J) ='J, for N < J < L. These values will not be changed by the reproductive plan. With L/2 processors the WHILE loop above can be effectively carried out if-each processor follows this program: FOR COUNT:= 1 TO K DO BEGIN TEMP1(J): TEMP1(2*J-1) + TEMP1(2*J); IF T.EMP2(2*J-l) < T'EMP2(2*J) THEN TEMP2(J):=TEMP2(2*J-1) ELSE TEMP.2(J):=TEMP2(2*J); IF VALUE (BEST(2*J-1)) > VALUE(BEST(2*J)) THEN BEST(J):=BEST(2*J-l.) ELSE BEST(J):=BEST(2*J) END;

1 2 To generate G new individuals to be incorporated into the population later, requires the following sort of structure. PARFOR NEW 1 UNTI L G DO IF random value < crossover probability THEN BEGIN UNTIL successful selection BEGI N PARENTI:=SELECT; test and decrement PARENTl's offspring counter END UNTIL successful. selection BEG IN PARENT2:=SELECT; lb1 PARENTI / PARENT2 THEN~ test and decrement PARENT21s offspring Count er END NEW(I) CROSS-OVER(PARENT1., PARENT2); END ELSE no crossover BEG IN UNTIL successful selection BEGIN

13 NEW(I) A(PARENT1) ~END; mutate NEW(I); The test and decrement operation must be a single indivisible operation such that if more than one processor attempts to modify the same counter all but one will be "locked out" until the first processor completcP.s the test and decrement. The test portion of the test and decrement operation tells whether the counter is positive or not. If the counter is positive, then that individual has not yet had its expected number of offspring and may be selected successfully as a "parent". The indivisibility of the test and decrement op'eration ensures that the same individual cannot be simultaneously selected by several processors and have its counter decremented to a very negative value (and have more than the expected number of offspring). Of course, the same individual can be selected in very rapid succession by several processors and could be involved in several crossover operations at the same time if the number of expected offspring allowed that. Incorporating the new individuals into the population is done in one of two ways. If G < N/2, then C individuals from the current population are replaced by the new individuals. If G > N/2, then N-C individuals are chosen from the current population to be retained in the next generation. DeJong' s work [6] suggests C should be about N/lO, so the first method is almost always the method to be used. DeJong also found that the performance of this reproductive plan is improved if, for each new

14 The number of such candidates was called the crowding factor (CF),. So the replacement process may be done in this way: PARFOR I:= I UNTIL G DO BEGIN PARFOR. J:= I 1 UNTIL CF DO BEG IN ch10oose ce individual from the current population.? ran'dom (Cuniform distribution) call this -i4ndivi dual Ax (J)3; find Hamiing distance between A(R(J)) and NEW W() lID.m'J(J); find miniirimi of HiD(l) ), HD(2),...,HD(CF), call it H D (LEST "'...C H; A(, BEST.i, A'"CH-L Nif,,(I) END, The replacement opera'tion A(BES'STM.ATCH): NEW(I) presents us with the difficulty Ji: v sec-;al processors may simultaneously replace the same individual with >'(-vera-.. new individuals causing some of the new individuals to be lost"'he solution is to mark each individual as to whether or not it has been replaced yet and then "test and set" this flag when replacing a ind kividua!i This can be accomplished with the same test and decrement instruction needed earlier. When an individual is selected for replacement whic h is marked as already replaced, then another individual'must be chosen. Thus, the program becomes:

PARFOR I 1 UNTIL G DO BEGIN UNTIL REPLACEMENT-F.LAG(BESTJAATCH) =not replaced* DO BEGIN PARFOR J I= UNTIL CF DO BEGIN UNTIL REPLACEMENL-FLAG(R(,J)) =not replaced DO R (J):=RANDOM (l,N); HD(J): Hamming distance between A(R(J)) and NEW(I); END; BEST-vIATCH:= index corresponding to minimum of HD(l)., HD(2),...,HD(CF); END; A(BESTJAATCH:=NEW(I); END; At this point, the more sophisticated reproductive plan has been adapted for parallel implementation. We should mention that the sophisticated plan uses a generalized crossover operator so that the number of crossover points may be greater than one. This should have very little effect on the parallel implementation of the algorithm except that all *Notice, the test that A(BESTJAATCH),has not already been replaced must be done using the "test and set" (or possibly a "test and decrement") operation for the reason-stated above. On-the other hand, the test to

16 small number- 1 or 2 or 3. So this may not represent much of. a savings.)

This sophisticated reproductive plan presents some real difficulties to parallel implementation. In the simple pian, it was natural to associate one processor with each of the new individuals to be generated during one generation. We may do that for the sophisticated plan, but here we face the problem of avoiding "collisions" in choosing parents and again when incorporating the new individuals into the population. If we were using G processors - one for each new individual - and a collision occured while selecting which individuals will be replaced, then G-l processors would be idle while another replacement choice was made by one processor. This would be rather inefficient, unless it were infrequent. If there were only a few processors, such collisions would be less costly (indeed, with only 1 processor efficiency is 100%). There may be some effective way of avoiding these collisions,, or some better form of this algorithm for parallel implementation, but we have not found one. * As the algorithm stands, one can rather easily estimate the expected number of collisions., which is independent of the number of processors."* Assume that m individuals have already been chosen to be replaced. Then *We considered the possibility of having one processor dedicated to choosing parents and coordinating.replacements, but such a processor could not keep up with the other processors. Also, using a multiple of G processors one could choose several candidates for replacement at once, but then finding a distinct subset of G of these is the original problem agaain.

1.8 the probability of choosing an unchosen individual on the next attempt is Simply N-rn m N So the expected numrber of trials befor e a successful selection is (since this is a Bernoulli sequence) N m N-rn Thus, the expected -Iumbe r oftil required to choose C distinct individuals from tW. rppd ~t -i -q.ni " i s C G-1' G - I m=0 m= 0 kNC k N,- WC-2 __k W N N(JJJ —G Lfl( 21NC )22(N-GC If N =10 C, tchen W N I.0 J-0537 N 1.OS C So we would lexpec about 5% o*, the trials to result in collisions.'We have not. estimnatedI.. he vari-,-ne in the number of collisions, but it seems reasonable to be..ieve Ithat iftost generations will not involve collisions in choosing whic.h indiviiJduals are to be replaced. The same analysis applies to selection of pareftiCs to generate the C new'individuals. Here

19 acceptable parent (one with a positive offspring counter) after having chosen m previously is still -i N-rn m N since the total number of allowed offspring is N and the remaining number is N-rn. Therefore, the computation time per generation is roughly T - +[lo2P - l)C5 + C~ + CR where C~ and C are the time required to choose one individual as a R parent (or for replacement) and the time required to do -everything else to generate new individuals and incorporate them into the population. In particular: T (N-1)C + WC + GC 1 S Ct' R TG J~. + [lgGI - I)C5 C~ CR So if C ~> C and N < 1000, then R 5' Now this makes T W C+GC I. G t R -G. G And E So, gain th rerdciepaGtlzstepoesr ut el u th ppoimton se nthsdeiato aent ogodastos o

20 the simpler plan. Further investigation is needed to really discover how efficient the sophisticated reproductive plan is. There is some parallelism possible within the code which generates a new individual and also in the code to place that individual into the population. So using 2G or 3G processors might be relatively efficient, but we have not investigated this possibility.

Standard (Gradient based) Function Optimizers Standard function optimizers all have one thing in common. They must estimate the gradient of the function at each sample point. In order to do this., either a procedure must be provided to generate an array of partial derivatives (based on algebraic derivatives of the function), or else the optimizer must sample the function at nearby points along each dimension of the domain. The first method is hard to evaluate since it depends very strongly on the form of the objective function. The second method is much easier to deal with, and also more general, so we assume that D (the dimensionality of the domain of the objective function), or possibly 2D, function evaluations are made at points near the current sample point in order to get the gradient information required for choosing the next sample point. This suggests that usin g D processors would allow the partial derivatives to all be estimated in parallel in very short time. Indeed, those optimizers, which do a large amount of matrix manipulations (using the Hessian) can do the matrix operations in parallel as well if there are D processors. Matrix operations are generally not 100% efficient in using parallel processing [7], [10]. In many cases, the bottleneck is a summation which must be computed. Matrix multiplication using D processors and 2 DxD matrices requires about 2 D ([log2DI + 1) 3 2 computation steps (there are D multiplications and D summations of D

22 Notice, finding the magnitude of the gradient is limited by this same summation bottleneck. Function optimizers which use a one-dimensional search to generate the next sample point can make use of parallel processing to speed up that search. Instead of Jsing a binary or golden section search, use a P-ary search. Find function values at P evenly spaced points. Compare these to determine which.interval to continue searching. The comparison step is the bottleneck he'e. It reqt-ires [log2P] steps to make this P-way comparison. Al,se sped-up due to using P-ary search rather than binary or Fibonacc': search is only a'iogarithmic improvement [2], [9]. Using D processors and neglecti:.g the comparison bottleneck, the speed-up is approx.immate.y D \ O R' X j e 2 So l':l.0 o D'I 2D. Thus S 0'log2D]og 0 2 D DD This is badly sub-optimal for large D. Moreover, the standard optimizer's rate of convergence decreases rapidly as D becomes large. So parallel implementation does not seem to be the solution to getting good performance on func'tions of a large number of variables using gradient-based optimizers. Another obvious approach to parallel implementation of the standard type of optimizer is to use P processors each of which runs the function optimizer independently of the other processors~ For a unimodal function,

23' the speed-up is essentially zero. The only improvement is that the.starting point closest to the optimum is probably better than if only one starting point had been chosen. For multimodal functions, this allows a crude global search to be made at the same time as the local search is performed. Commonly, one would run his favorite gradient-based optimizer several times, startin apoints spread throughout the domain. So the speed-up is almost perfect: S ~P P and B Il P using P processors on a multi-modal function. This must be taken-with a grain of salt, however, since standard optimizers are not very well suited to multi-modal functions.

In short, the simple genetic plan seems very well suited to parallel implementation. The sophisticated reproductive plan makes less efficient use of parallel processors, but it is still reasonably efficient for P < G (where G is likely to be on the order of 10). The standard, gradient-based function optimizer is less suited to parallel implementa-~ tion than either reproductive plan, but it may be advantageous to use parallel processing on multi-modal functions.

References 1. Arjomandi, E. "A Study of Parallelism in Graph Theory". Doctoral Thesis, Dept. of Computer Science, Univ. of Toronto. Also Technical Report No. 86, Dept. of Computer Science, Univ. of Toronto. Dec., 1975. 2. Avriel, M. and D. J. Wilde. "Optimal Search for a Maximum with Sequences of Simultaneous Function Evaluations". Management Science, 12, 1966, p. 722-731. 3. Barnes, G.'H., R. M. Brownm, M. Kato, D. J. Kuck, D. L. Slotnik, R. A. Stoker. "The Illiac IV Computer". IEEE Trans. on Comp. 17, 1968, p. 746-757. 4. Bethke, A.' D., B. P. Zeigler, D. M. Strauss. "Convergence Properties of Simple Genetic Algorithms". Technical Report No. 159, Logic of Computers Group, Univ. of Michigan. July, 1974. 5. Bosworth, J. L., N. Foo, B. P. Zeigler. "Comparison of Genetic Algorithms with Conjugate Gradient Methods". Technical Report No. 00312-1-T, Logic of Computers Group, Univ. of Michigan. 6. DeJong, K. A. "Analysis of the Behavior of a class of Genetic Adaptive Systems". Doctoral Thesis, Dept. of Computer and Communication Sciences, Univ. of Michigan, 1975. Also, Technical Report No. 185, Logic of Computers Group, Univ. of Michigan. 7. Heller, D. "A Survey of Parallel Algorithms in Numerical Linear Algebra". Technical Report, Dept. of Computer Science, CarnegieMellon Univ. 1976. 8. Holland, J. H. Adaptation in Natural and Artificial Systems. Univ. of Michigan Press, 1975. 9. Karp, R. M., W. L. Miranker. "Parallel Minimax Search for a Maximum". Journal of Combinatorial Theory, 4, 1968, 19-35. 10. Kung, H. T. "Synchronized and Asynchronous Parallel Algorithms for Multiprocessors". Technical Report, Dept. of Computer Science, Carnegie-Mellon Univ. 1976. Also to appear in New Directions and Recent Results in Algorithms and Complexity, edited by J. F. Traub, Academic Press, 1976. 11. Lipton, R. J. "Reduction: A Method of Proving Properties of Parallel Programs". CACM, 18, 1975, p. 717-721. 12. Wulf, W. A. and C. G. Bell. "C.mmp - A Multi-Mini-Processor". Proc. AFIPS 1972 FJCC. Vol. 41 Part II, AFIPS Press, 1972, p. 765-777. 25

Explanation of Figures. Figures 1-5 show how good the approximation N P P is for various values of N. This approximation is compared to P P where T = (-l)C + NC whee T1 ( S R and T~ =[ij + rlogN] I iC5 + [.cR using the ratio CR Figures 6410 compare the approximation T P Pi Rwith T =(i~ [1og2N + F1CR CR. for the same values of N and - = 10 also. CS

EFFICIENCY OF SIMPLE REPRODUCTIVE PLAN POPULATION SIZE= 10 0 0'-4 0i 0 1:0 02o 04006 0 lo100 0~~~~NME FPOESR

EFF IC IENCY OF S IMPLE R EPRODUCT IVE PLRN POPULAT ION SIZFE = 100 0 z LUJ LLJ 9000o 20.v00 40.100 60.00G 80.00 100.00 NUMBER OF PROCESSORS

EFF I CIENCY OF S IMPLE REPRODUCT IVE PLAN POPULAT ION S IZE = 1000 0 co LLI. U0 FC'J 0'b~~oo 200. 00 400.00 600.00 800.00 1 000.lb00 NUMBER OF PROCESSORS

EFFICIENCY~ OF SIMPLE HEPHODUCTIVE" PLRN POPULRTION SIZE = 10-000, 0> 0l C> 0l 0> 0k C0 0a LU Cl4 (Jo C) LL> Cl LU 0~'O.00 200.00 LAooOO 0 600.00 800.00o 1000.00 NUMBER- OF PROCESSORS. (XO1)'

EFF I CIENCY OF S IMPLE REPRODUCT IVE PLAN POPULAT ION S IZE I 100000 L)J I b.o-20. 0.0 0*0 80601000 0~~~~~UBRO RCSOS( -

COMPUTATION TIME OF SIMPLE`REPRODUCTIVE PLAN POPULATION. SIZE = 10 Lii C) Iz 10 20 60 00 0~~~~UBR FPOESR

COMPUTATION TIME OF SIMPLE REPRODUCTIVE PLA~N POPULATION SIZE = 10 (0 z: C) 0.400 20.,00'WOO1 80.00 80000 So.0 NUMBER OF PROCESSORS

COMPUTAT ION, TIME OF SIMPLE REPRODUCTIVE, PLAN POPULATION SIZE =1000 000 0 a60-0 o 0 lwo'a~ ~ UBROFPOESR

C.OMPUTATION TIME OF ~SIMPLE REPRODUCTIVE PLAN POPULATION SIZE= 10000' M~~~~~ up~~~~~~~~~~~~~ 0U0.0 0 0,0 01*010,0 wd~~~~NM F RCSOS(I

UNIVERSITY OF MICHIGAN 11111111111111111111111111111111111 I111 3 9015 02523 0254 COMPUTATION TIME OF SIMPLE REPRODUCTIVE PLAN POPULRT I ON SIZE = 100000.~ Xa amf-. NUMBER OF PROCESSORS (X10-2) FIGUI9E1O