An evolutionary method for automatic wire routing

An Evolutionary Method for Automatic Wire Routing J. Tanomaru, K. Oka Dept. of Information Science, Faculty of Engineering, The University of Tokushima, 2-1 Minami-Josanjima, Tokushima 770, Japan phone: +81-886-567488; fax: +81-886-554424; e-mail: [email protected] Abstract - This paper introduces an Automatic Wire Routing (AWR) algorithm based on evolutionary principles. In the proposed algorithm (dubbed EWRA, where "E" stands for evolutionary), populations of wiring networks evolve through the action of stochastic operators conceived from the heuristics of manual wire-routing. In each wiring configuration (individual of the population), all nets are routed and temporary intersections are allowed. The objective of evolution is to improve wiring quality in the sense of eliminating unwanted net intersections and simplifying paths in order to reduce manufacturing costs and increase reliability. Although the populations approach and the use of stochastic operators for simulating evolution resemble conventional genetic algorithms (GAS) operation, the AWR problem requires much more advanced representation and sophisticated operators whose action takes place at the wiring level, and not at the string level. Results showing the effectiveness of the proposed algorithm in a serial implementation are presented. Furthermore, in order to reduce computation time, parallel implementation of the proposed AWR algorithm is discussed for an ideal multicomputer architecture and for a realistic binary-tree multicomputer, in which the algorithm is currently being implemented. Preliminary results indicate that the proposed EWRA is feasible for AWR applications and suggest that efficient implementations can be obtained by using massively parallel processing. minals distnbuted through a wiring space. Although in this paper all the discussion will be for the single-layer case (two-dimensional wiring space), extension to the multilayer case is immediate. As the number of terminals to be connected and the wiring space increase, the search space increases in a non-polynomial fashion. In a common representation of the search space, the wiring space is viewed as a rectangular grid with mesh size A = w + c, where w is the minimum width of a net and c is the minimum clearance between nets. This representation is illustrated in Fig. 1, where two possible configurations are presented for nets connecting the terminals A-A', B-B', and C-C' on a single-layer grid. In Fig. l(a), the terminals C and C' cannot be connected. A possible wiring solution is presented in Fig. l(b), where it becomes clear that the order in which connections are made affects crucially the final results. INTRODUCTION Automatic wire-routing (AWR) can be viewed as a complex search task with various practical applications in the circuitry and IC industry, since the AWR problem can be mapped into the wire-routing of either printed circuit boards or IC masks [ 11. AWR demands extensive computations, and current algorithms being used in industry are still inefficient and can hardly accomplish between 80% and 90% of wiring rate after several workstation hours, leaving the remaining of the job to be done by human experts, in a very slow and costly process[2]. Under engineering viewpoint, AWR belongs to the class of optimization problems with very large search spaces, where one is more interested in finding feasible solutions in practical time than trying to find the absolute optimal solution. For such problems, evolutionary and genetic algorithms (GAS), which are iterative search algorithms modeled after the mechanics of natural evolution and natural genetics, have been successfully applied [3-41. With this motivation, this paper proposes a new AWR algorithm based on evolutionary principles, dubbed EWRA, in which populations of wiring networks evolve through the action of stochastic operators conceived from the heuristics of manual wire-routing. Although the populations approach and the use of stochastic operators for simulating evolution resemble conventional genetic algorithms (GAS)operation, the AWR problem requires much more advanced representation and operators. Results showing the effectiveness of the proposed algorithm in a serial implementation are presented. Furthermore, in order to reduce computation time, parallel implementation of the proposed AWR algorithm is discussed for an ideal multicomputer architecture and for a realistic binary-tree multicomputer available at our laboratory, in which the algorithm is currently being implemented. AUTOMATICWIRE ROUTING (AWR) The automatic wire-routing (AM) problem essentially consists of fmding non-intersecting connection paths (nets) between pairs of ter0-7803-1328-3/94$03.000 1994IEEE (b) Fig. 1. Example of a single-layer 8x7 grid with three nets. In (a), the terminals C-C' cannot be connected, while (b) shows a possible solution. The black cells represent obstructions. A classic AWR method is the Lee's maze running algorithm [5-6]. In this algorithm, a circular wave is expanded from one of the terminals to be connected and increasing indices (labels) are associated to each grid cell of the wave front, in such a way that each index represents the city-block distance of the corresponding cell to the source terminal. When a wave front reaches the target terminal, a net is generated by backtracking cells with adjacent indices from the destination to the source terminal. An example of application of this algorithm is illustrated in Fig. 2, where the black cells represent forbidden regions occupied by obstructions or already routed nets. In the example, the wave expanded from the terminal A reaches the terminal A' in ten steps, indicating that the minimum path connecting A and A' passes through ten grid cells. Clearly, the grid representation excludes paths other than horizontal and vertical ones. There are a number of alter1117 native procedures for increasing the search efficiency, like generating waves simultaneously from each terminal until collision occurs. prove the quality of the wiring. The basic features of the proposed algorithm are given below. a) Net variety generation: During the initialization phase, various possible paths (nets) are generated for each pair of terminals. b) Population approach: A candidate solution for the AWR problem is a set of one possible net for each pair of terminals to be connected. With n possible paths for each pair of terminals, a population of n candidate solutions (chromosomes) is obtained. c) Evolutionary operators: A new population of candidate solutions is obtained from the previous population through the application of stochastic operators which reproduce high-performance nets, cross and combine them with other nets, and perform heuristic operations in order to eliminate short-circuits (net crosses), contour obstacles, and improve wiring quality. EVOLUTIONARY Am Fig. 2. By using the Lee algorithm, the shortest distance separating A and A' can be easily determined. For the illustrated case, there are three shortest paths. Different backtrack procedures generate different nets. Though the maze-running algorithm is simple, guarantees that a path is found if one exists, and can be easily extended to the multilayer case, the method alone is not enough for AWR purposes, since the sequence in which wiring is performed has dramatic consequences on the final wiring result. One way of coping with such a problem is the rip-up procedure: nets are generated in any sequence; when an impasse occurs, that is, there is no physical path connecting two terminals, one of the previously routed nets is ripped up and re-routing takes place [7-81. The net to be ripped up is usually selected using random choice and, although high wiring rate can be eventually achieved, the method is inefficient and very time-consuming. This paper proposes an evolutionary AWR algorithm in which temporary net intersections are allowed and there is no need of rip-ups. ALGORITHM(EWRA) An initial population of n=5 candidate solutions for a wiring problem consisting of m=6 nets is shown in Fig. 3. Such nets may be generated independently of each other, in an unconstrained fashion. The net population can be analyzed in two ways: a) horizontally, each band (row) of the net array corresponds to a subpopulation of n possible nets for a given pair of terminals; b) vertically, each band (column) corresponds to a wiring configuration of m nets. In GA terminology, the net array can be thought of as a population of n chromosomes (each vertical band, combined into a single grid), each of them with m coded features. -!db/"L91pP EVOLUTIONARY APPROACH The last two decades have seen the emergence of the genetic algorithms (GAS), search procedures based on evolutionary principles. Differently from conventional optimization techniques based on hillclimbing procedures, GAS perform blind search from a population of candidate-solutions and employ stochastic and heuristic operators which modify and combine solutions to improve the population in the sense of maximizing some objective function. In CA jargon, the candidate-solutions are dubbed chromosomes, which in practice are represented by binary strings of coded parameters [3-41. Having chosen a representation for the search space in the form of strings over some finite (in practice, binary) alphabet, a typical GA search consists of the following steps: Choose an initial population of candidate-solutions. Step 1. Evaluate each individual of the population. Step 2. WHILE (there isn't a satisfactory solution) REPEAT Step 3. Generate new population through genetic operators. Evaluate each individual of the population. Step4. END. Some of the basic ideas behind GAS, such as the population-oriented approach and use of stochastic operators to generate new candidate-solutions from old ones, also served as motivation for the algorithm proposed here. However, while conventional GA operators usually operate by copying strings and changing parts, the AWR problem requires much more complex search space representation and advanced operators. BASICSOF THEAm ALGORITHM Generally there are a number of possible paths connecting any two terminals in a grid. With a global perspective, the shortest path is not always the best choice for wiring, since such a policy does not take into account the other terminals still to be connected. In the proposed AWR algorithm, at first various possible paths are generated for each pair of terminals, and then candidate solutions for the AWR problem suffer iterative action of evolutionary operators in such a way-to im1118 WIRING I, i WIRING! WIRING: WIRING: WIRING 2,3,4; 5 Fig. 3. Example of a net array with n = 5 candidate solutions (each vertical band) for a wiring problem with m = 4 nets. The wiring quality of a net can be evaluated accordingly to the following function: q[ne+(t)lb c, -[a ndnetj(t)) +p d(net$t)) +y nb(ne+(t))+ 6 n,,(ne+(t))] (1) where i = 1.2, ...,n and j = 1, 2, ...,m correspond to the horizontal and vertical indices of the population array, respectively, t is the population index (or generation), n,, d, nb, and n, stand for the number of crosses (path intersections), the length, number of bends and number of via-holes (forthe multilayer case) of a given net, a,p, y. 6 > 0 are penalty parameters, and c, is a positive value chosen in order to keep the quality index always positive. Accordingly, the wiring quality of a configuration with m nets can be defied analogously to (l), but considering the total number of crosses, total length, and so forth. Selection ofthe Initial Population For the initial population, in order to generate different paths for the same pair of terminals, several heuristic procedures can be adopted. For example, after expanding the wave in Fig. 2, it is easy to define different backtrack procedure which lead to different nets, and not only the shortest path. Altematively. false obstructions can be inserted on the grid, or nets can be forced to bend at certain positions. With the initial population and net quality function as defined in (I), the next population results from the application of several operators as described below. Net Reproduction Operator Touches may arise naturally during normal wiring procedure or may result from the application of the path exchange operator. The touch clearing operator simply stretches one of the touching nets, eliminating short circuits in the wiring space when physically possible. For each pair of touching nets, selection of the net to be stretched may be based on a stochastic procedure (coin flip) biased in order to favor low costly nets. An example of the action of the touch clearing operator is presented in Fig. 7. Net Reproduction is an operation which takes place horizontally in the population array, that is, in a subpopulation of nets for the same terminals. Each net in a horizontal band is evaluated according to (l), and is given a number of copies proportional to its quality relatively to the other nets in the subpopulation, in the same way that selection operates in traditional GAS. The procedure is repeated n times for each horizontal subpopulation, resulting in a transient population of the same size as the original one. In practice, at first the relative wiring oualitv is computed for each net in a horizontal subpopulation, and then selection takes place in such a way to reward nets of high relative quality with large number of copies in the following transient population. Generalized Net Crossover Operator Following reproduction, each of the horizontal bands of the transient population is shuffled obeying to a given probability distribution, in a procedure corresponding to generalized crossover. Crossover produces new candidate-solutions by combining nets of different wiring configurations. A possible transient population resulting from the action of reproduction and generalized crossover on the population of Fig. 3 is shown in Fig. 4. Fig. 5. Example of poor wiring of 4 nets with 3 path intersections. Fig. 6. Result of the action of the path-exchange operator on nets 3 and 4, generating two new touch-points. WIRING; WIRING; WIRING; WIRING: WIRING 1',2',3',4:5' Q net 1 Fig. 4. Possible transient net population resulting from the application of the net reproduction and generalized crossover operators to the net population shown in Fig. 3. ROUTING-ORIENTED OPERATORS Once the net reproduction and crossover are finished, each of the n vertical band of the resulting array constitutes a potential wiring configuration. However, much likely the simple combination of the individual nets in a vertical band of the array will result in a poor wiring configuration, with net intersections and longer-than-necessary, complex paths. For example, a poor net configuration in which there are two pairs of short-circuited nets is shown in Fig. 5. In order to improve the global wiring configuration and eliminate occasional net intersections, several heuristic operators were devised. Fig. 7. The touch-clearing operator on nets 3 and 4 eliminates shortcircuits. Net Contour Operator Path Exchange Operator In situations with an odd number of crosses, the path exchange operator alone is not enough for eliminating all the intersections. In those cases, the net contour operator can be used to deform one of the involved nets in such a way to contour the others in a safe path, eliminating intersections, as shown in Fig. 8. Selection of the net to be deformed may be based on flipping a biased coin which favors low costly nets. The action of this operator consists on exchanging parts between intersecting nets in order to reduce the number of net crosses. Like other operators in this paper, this is a complex operator whose action takes place at the net level, and not at string level as in conventional GAS. An example of the effects of the path exchange operator is given in Fig. 6 for two intersecting nets of the configuration shown in Fig. 5. The operator action changes the intersections into "touch points", which are easier to deal with. However, as can be concluded from Figs. 5 and 6, when the number of intersections is an odd number the path exchange operator alone is not enough to eliminate all the intersections. Net Self-Improvement Operator The function of this operator is to try to simplify complex paths, shortening nets and finding shortcuts whenever possible, in order to reduce manufacturing costs and increase reliability. Unlike other operators, the net self-improvement operator acts in a single net. The mechanism for this operator consists of at first drawing a few parallel lines that divide the region occupied by a single net into subregions, and then trying to find orthogonal short paths connecting the lines, as shown in the example in Fig. 9. TouchClearing Operator This operator deals with net touches, defined as the grid cells in which two or more nets touch each other without actual intersections. 1119 I tion, with no intersections, 100% of routing rate and no unnecessary bends. This is a remarkable fact, since for usual evolutionary methods, a population of only n=10 individuals is very small even for the small grid size considered. Q net 1 I I Fig. 8. The contour operator can be used to deform net 2, eliminating the intersection with net 1. I ; ; Q net 1 Fig. 10. Best wiring configuration at the 51-rst generation. All net intersections were already eliminated, but paths can be further simplified. I I 1 net 2 nZj I I Fig. 11. Optimal wiring configuration attained at the 617-th generation. Comparing with Fig. 10,a great deal of path simplification has taken place. net 4 Fig. 9. The net self-improvement operators acts by first tracing a few parallel lines, as in (a), and then trying to find shortcuts joining the lines, resulting in simpler nets, as shown in (b). SERIAL COMPUTERIMPLEMENTATION EWRA was implemented in a workstation environment, and preliminary results are here reported. Likewise normal GAS, the procedure consists of generating successive populations of wiring configurations. until a member of the population satisfies the problem constraints. The target is to obtain 100% of the nets connected, without any undesirable intersections. Furthermore, the total length of the nets and the total number of bends and via-holes between grid layers should be minimized to reduce manufacturing costs and increase wiring reliability. In order to evaluate the quality of a wiring configuration consisting of a vertical band of lhe population, another quality coefficient was defined upon (I). 111 practice, each vertical band (wiring configuration) was evaluated only after a new population was generated, that is, after the action of the operators was finished. Comparatively high values were chosen for the a coefficients, in such a way to penalize strongly occasional net intersections. Some experimental results are shown in Figs. 10 to 13, for a single-layer 32x32 grid with m=lX pairs of terminals to be wired. A population of size n = 10was chosen, and the parameters c = 1800, a=20,PI,y=2, and 64 were selected for the evaluating the wiring quality factor. The best wiring configuration obtained at the 51-rst generation is shown in Fig. IO. Although no net intersections are present, the nets still present unnecessary bends which result in high costs. The best configuration the 617-th generation is shown in Fig. 1 1, and virtually corresponds to [lieoptimal wire-routing configura1120 ,VI t K*--i j 1- 7m.- om A nm "40 -~ ---A~ om "ro ,.""xn" In> 1 ,R? Fig. 13. Variation of the best and average wiring quality of the population of wiring configurations. The best value reached peak in a few generations. The variation of number of net intersections is plotted in Fig. 12 for the best and the average of each generation. It is seen that as early as at the 51-rst generation it was possible to obtain full routing without net intersections. The spikes in Fig. 12 can be explained by the fact that the EWRA occasionally introduces net crosses while searching for better configurations, in a process analogous to escaping from local minima. Finally, in Fig. 13 the wiring quality of the best and average of the population of wiring configurations is plotted for each generation. The best value reached peak very early, whereas the average value showed oscillation near peak, corresponding to situations of near zero net crosses and a few path variations. (rows and columns of the net population array) is illustrated in the idealized parallel computer architecture of Fig. 14. PARALLEL IMPLEMENTATION The proposed EWRA performs a very exploitative search through an extremely large search space. The complexity inherent to the AWR problem, the sophisticated representation of the search space required by EWRA. and the evolutionary operations all contribute to high computational costs even for small-sized problems. Practical problems usually involve multilayer grids with many thousand cells per grid and hundreds of pairs of terminals to be linked, increasing the number of rows in the net population as the one shown in Fig. 3. Furthermore, having a high number of columns in the net population is also desirable, since this is equivalent to having more individuals (or chromosomes) in a population, which evidently increases the chances of successful search. Due to the nature of the AWR problem and the large execution time, the idea of using parallel processing to improve efficiency comes naturally. In fact, several papers have appeared in which nets are wired in parallel. For instance, in [8-91, a master processor keeps an up-to-date database with the nets already wired and assign the remaining nets to slave processors, each one executing a maze-running search. The slave processors send their nets to the master in a firstcome-first-serve basis, and only nets which do not result in intersections with already-wired nets are registered in the database, which is then sent back to all the slave processors to direct their wiring process. At the end, if there is any net not wired yet. one of the wired nets is selected for deletion (rip-up), and re-wiring takes place. A different approach was adopted in [2]. where a massively parallel SIMD computer was especially developed for wire-routing. In this case, the routing procedure consisted of routing each net iteratively, allowing intermediary states with intersecting nets, and using a few rules to minimize the number of intersections. On the other hand, EWRA features the same "implicit parallelism" which characterizes GAS, in which a large number of possible solutions and parts of solutions for a problem are searched simultaneously. Additionally, explicit parallelism has also been used for GAS, and the common strategy is to divide a large population of individuals into subpopulations which are assigned to slave processors for genetic manipulation [lo]. Better-fitted individuals are allowed to immigrate to join other subpopulations and are also passed to a master processor, which coordinates major issues. A different approach is suggested below for implementing the EWRA in parallel computers. The following discussion considers a customized ideal architecture for EWRA and a realistic implementation in a general purpose MIMD parallel computer of our laboratory. W Fig. 14. Parallel architecture idealized for the proposed EWRA, consisting of I MP (master processor), n WEPs (wiring evaluation processors), m NSPs (net selection processors) and a number of SPs ( slave processors). The central part of the network represented in Fig. 14 is composed by m NSPs (net selection processors) and n WEPs (wiring evaluation processors). It results that, if such a configuration is employed to apply the EWRA to a problem consisting of m nets with a population consisting of n wiring configurations, at least m+n processors are required only for NSPs and WEPs. Additionally, a master processor (MP) for task administration and a number of slave processors (SPs) for minor tasks were included in the network. In the idealized processor network, the layer of NSPs and the WEPs layer are "full-connected". This is explained by two reasons: a) before accomplishing net reproduction for each generation, each NSP must receive the corresponding net from each of the WEPs; and b) each NSP selects and sends one net of its subpopulation to each WEP, performing net reproduction and generalized crossover. The role of each kind of processor is described below. a) Net Selection Processors: each NSP is responsible for a subpopulation of nets connecting a set of terminals (usually two termnals). In simple temis, the j-th NSP performs the following actions: BEGIN IF (First-Generation) THEN ( Ideal Architecture for EWRA An idea of how to apply parallel processing can be easily derived from the net population array represented in Fig. 3. Recall that in this representation each row is associated with a single set of terminals to be connected, that is, each row represents a subpopulation of possible nets for the same terminals. Further, each net must be evaluated according to (I), forming the basis for action of the net reproduction and generalized crossover operators. Therefore, assigning different processors to each pair of terminals to be connected seems to be helpful, since in this way great part of the reproduction and crossover actions can take place in parallel, and unnecessary processors comniunication is avoided. On the other hand, each column of the net population array stands for a possible wiring configuration (combination of one net for each pair of terminals to be connected). The routing-oriented operators must be applied to the nets of each wiring configuration in order to eliminate occasional intersections and simplify paths. Such a task is time-consuming, but takes place independently of what happens in other wiring configurations. Consequently, assigning a processor for each wiring configuration arises as a natural approach to exploit parallelism in the EWRA. This idea of having processors corresponding to each pair of terminals and others to each wiring configuration FOR i := 1 Ton DO Generate one net and send it to the i-th WEP; First-Generation = FALSE i ELSE { FOR i: = 1 TO 11DO 1 Receive the corresponding j-th net from the i-th WEP, as well as information necessary to compute the net's wiring quality as defined in (1); Evaluate the wiring quality of the net; ) FOR i: = 1 Ton DO { 1 Select one net according to its relative wiring quality as in (2); Send the resulting net to the i-th WEP; 1 END Note that both net reproduction and generalized crossover are implemented by the NSPs, avoiding unnecessary processor communi1121 cation. The SPs may be used to speed up the task of evaluating the wiring quality of each net, as illustrated in Fig. 14. b) Wiring Evaluation Processors: each WEP is responsible for a separate wiring configuration. The i-th WEP performs the following actions: BEGIN FOR j: = 1 Tom DO Receive one net from the j-th NSP; Apply the routing-oriented operators in order to increase wiring quality; Evaluate the wiring configuration; FORj:=lTOmDO Send the j-th net to the j-th NSP; END In the WEPs' case, the SPs can be used to distribute the time-consuming routing-oriented operations. The master processor (MP) should receive the results of the evaluation of each wiring configuration and perform global administrative operations. Realistic Architecture: Binary-Tree Multicomputer Implementation The approach described above demands a especially-designed parallel computer, which is out of our current plans. Instead, currently the proposed EWRA is being implemented in the CORAL68K, a 63-processor multicomputer designed at our laboratory [ 111. The CORAL68K is a MIMD machine in which 63 processors are organized in a binary tree structure, as shown in Fig. 15. Each processor is m independent computer with a Motorola 68000microprocessor as CPU, system ROM (16kB) and 512kB of RAM. There is no common memory shared by the processors, making CORAL68K a true multicomputer. The processors are numbered from 1 to 63, in such a way that the root is assigned #I and the others are numbered sequentially in each layer from left to right, as indicated in Fig. 15. crossover (performed by the NSP in the proposed EWRA) and routing-oriented operations take place sequentially and not simultaneously. In other words, if the architecture of Fig. 14 is used, the WEPs would be idle while net selection was taking place inside the NSPs and, conversely, while routing-oriented operations were occurring inside the WEPs, all the NSPs would do nothing but wait. This approach alone reduces the minimum number of required processes from a minimum of m+n to max(m, n). b) In order to cope with the limited number of processors, instead of assigning a single pair of terminals to be connected or a single wiring configuration to each processor, each processor hands a bundle of both wiring terminal pairs and wiring configurations. This is equivalent to make each processor responsible for several rows and columns of the net population array as illustrated in Fig. 3. The parallel implementation of the proposed EWRA is currently under way and results shall be reported in the final version of this paper. 8. CONCLUDING REMARKS In this paper, evolutionary techniques which conceptually resemble genetic algorithms manipulation were applied to the AWR problem, and an evolutionary wire-routing algorithm (EWRA) was proposed. Wiring configurations with all the nets routed are generated, and heuristic operators are used to eliminate net intersections and increase wiring quality at each generation. The general mechanism of EWRA resembles conventional GAS, but rather more complex representations and operators are required. The effectiveness of the proposed EWRA for wire-routing applications was shown by some results of a serial implementation. Parallel implementation was also discussed for a special-purpose architecture and for a binary-tree parallel computer, in which EWRA is currently being implemented. Preliminary results suggest that very efficient EWRA implementations can be obtained by using massively parallel computers. Further results shall be reported in the final version of this paper. Although the proposed routing-oriented operators are able to solve most problems in routing, they still fail in some difficult problems, particularly when the wiring space is severely limited. This happens because the proposed operators are short-sighted and do not foresee the consequences of their actions. Currently, advanced operators which consider more than two nets for their action are under study, as well as biasing procedures for generalized crossover. REFERENCES Fig. 15. Structure of the CORAL68K parallel computer system. As illustrated in Fig. 15, the root processor (#I) is linked directly to a host computer (a UNIX workstation) which plays the role of user display and software development environment. All the CORAL68K processors run exactly the same program, which is compiled in the host and loaded simultaneously into all the 63 processors. Individualized operation is made possible through the use of individual parameters such as the processor number, level, and so on, which are unique to each processor. EWRA Implementation in the CORAM8K The binary structure of CORAL68K makes construction and design easy, but seriously limit processors communication. Furthermore, if the approach presented in the previous section is strictly followed, the 63 processors would not be enough to cope with any problem of practical interest. In order to run a parallel version of EWRA in the CORAL68K, the following approach is pro- posed: a) Each processor plays double roles as both a NSP and a WEP. This is possible because the operations of the net reproduction and Geyer, J. M. "Connection Routing Algorithm for Printed Circuit Boards," IEEE Trans. on Circuit Theory, Vol. CT-18, pp. 95-100, 1971. Kawamura, K., M, Ishii, and H. Shiraishi. "Massively Parallel Routing System," Denshi Tokyo, No. 31, pp. 90-95, 1992. Holland, J. H. Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, MI, 1975. Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989. Ohtsuki, T. "Maze-Running and Line-Search Algorithms," in T. Ohtsuki (Ed.), Layout Design and Ver$cation, pp. 99-13 1, Elsevier Science Publishers, 1986. Hoel, J. H. "Some Variations of Lee's Algorithm," IEEE Trans. on Computers, Vol. C-25, pp. 19-24, 1976. Dees Jr., W. A. and R. J. Smith 11, "Performance of Interconnection Rip-up and Reroute Strategies," Proc. 18th Design Automalion Conf., pp. 382-390, 198 1. Y. Takahashi and S. Sasaki. "Parallel Automated Wire Routing with a Number of Competing Processors," Proc. ACM Int. Conf.on Supercomputing, pp. 310-317, 1990. Takahashi, Y., T. Suzue, and S. Kashimoto. "Parallel MazeRunning and Line Search Algorithm for LSI CAD on BinaryTree Multiprocessor," Proc. World Conf. on Information Processinn and Communication, Seoul. DD.128- 136. 1989. [IO] Pettey, C-B., M. R. Leuze, and J. J. dikfenstette. "A Parallel Genetic Algorithm," in J. J. Grefenstette (Ed.), Proc. ICGA'87, Lawrence Erlbaum Associates, Hillsdale, NJ, pp.155-161, 1987. [11] Takahashi, Y., T. Endoh, and K. Matsuo. "Development and Evaluation of the CORAMSK Binary Tree Parallel Computer," Trans. of the Society of Inf. Processing, Vol. 30, pp. 46-57, 1989 (in Japanese). 1122