LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAICN vt<\.O.S»S3-SS15> GOf Z CENTRAL CIRCULATION AND BOOKSTACKS The person borrowing this material is re- sponsible for its renewal or return before the Latest Date stamped below. You may be charged a minimum fee of $75.00 for each non-returned or lost item. Theft, mutilation, or defacement of library materials can be causes for student disciplinary action. All materials owned by the University of Illinois Library are the property of the State of Illinois and are protected by Article 16B of Illinois Criminal law and Procedure. TO RENEW, CALL (217) 333-8400. University of Illinois Library at Urbana-Champaign Jul a ± l\}\)) JUL 1 I 21)01 When renewing by phone, write new clue date below previous due date. L162 Digitized by the Internet Archive in 2013 http://archive.org/details/fastheuristictec558stev ^ yuiucDcs-R-72-558 yyuMi FAST HEURISTIC TECHNIQUES FOR PLACING AND WIRING PRINTED CIRCUIT BOARDS *y James Edward Stevens, Jr. October 1972 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS UIUCDCS-R-72-558 FAST HEURISTIC TECHNIQUES FOR PLACING AND WIRING PRINTED CIRCUIT BOARDS BY James Edward Stevens, Jr October 1972 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 ^Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign and supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the U.S. Army Research Office-Durham under Contract No. DAHC0^-72-C-0001. ABSTRACT A comparison of existing placement techniques is presented. Large realistic printed circuit board problems are introduced and used to make comparisons. The value of different placements is measured by the total wire length generated as well as by the results of actually routing the connections on the board. A new wire routing algorithm called Channel Routing, is proposed. The Channel touting algorithm is faster than existing routing techniques and can handle very large circuit board problems. The results of imple- menting the basic Channel Routing algorithms are presented. These results are also used to compare the effectiveness of the different placement algorithms. Ill ACKNOWLEDGEMENT I am indebted to Professor D. L. Slotnick for his support and encouragement and to Dr. Akihiro Hashimoto for his valuable advice. The typing was done by Frieda Anderson and the drafting by Fred Hancock. Credit is also due Linda Zapf for programming the placement algorithms. I am grateful to the Center for Advanced Computation and the Department of Computer Science at the University of Illinois for their support of this dissertation. IV TABLE OF CONTENTS Page ACKNOWLEDGMENT ±±± LIST OF TABLES vi LIST OF FIGURES vii 1. INTRODUCTION 1 2. THE ILLIAC IV DESIGN PROBLEM . . 3 3. GENERAL DESIGN AUTOMATION DISCUSSION 10 3.1 Measurement Techniques , . . . 10 3.2 The Assignment Problem 11 3«3 The Interconnection Problem 12 4. PLACEMENT l4 4.1 Preliminaries 14 4.1.1 Connection Specification 14 4.1.2 Wire Length for One Package 15 4.2 Serial Placement Techniques 16 4.2.1 General Description 16 4.2.2 The Serial Placement Program 21 4.2.3 Serial Placement Results 22 4.3 Iterative Placement Techniques 27 4.3.1 General Description 27 4.3.2 The Pairwise Interchange Program 31 4.3-3 Pairwise Interchange Results 34 4.3.4 Implementation of Steinberg's Algorithm .... 35 4.3.5 Steinberg's Placement Results 40 4.4 Comparison of Results 4l 5. ROUTING 43 5.1 Review 43 5.1.1 Lee's Algorithm 43 5.1.2 Line Routing 46 5.1.3 Cellular Wiring 47 5.1.4 Two- Layer Routing 48 5.2 Channel Routing 50 5.2.1 Objectives 50 5.2.2 Spaces and Channels 51 5.2.3 Space Assignment 53 5.2.4 Channel Assignment 59 5.2.5 Final Positioning 62 5.2.6 Proof of Optimum Channel Assignment 65 5.2.7 Results 70 5.2.8 Possible Improvements 72 V Page 6. CONCLUSIONS 7^ 6.1 Placement 7I4. 6.2 Channel Routing 75 APPENDIX A 77 APPENDIX B 104 LIST OF REFERENCES 117 VI LIST OF TABLES Table Page 1. Serial Placement Results 2k 2. Wire Routing of Serial Placements 25 3. Correlations 26 k. Pairwise Interchange Results . . 35 5. Steinberg's Algorithm Results Ui 6. Comparison of Results J42 7. Channel Routing Results 71 VI 1 LIST OF FIGURES Figure Page 1. ILLIAC IV CU Board 1+ 2. A Chained Connection 5 3. An Integrated Circuit Package 7 k. Package Spacing 8 5. An Edge Connector Group . 9 6. Minimum Spanning Tree versus Steiner Tree 13 7« Package Selection 18 8. Candidate Positions 20 • 9. An Unconnected Set 28 10. Board Positions of an Unconnected Set 30 11. Lee's Algorithm U3 12. Space Arrangement 52 13. A Generalized Connection 5^- ik. Data Format of a Horizontal Wire Segment 56 15. Wiring to a Package Pin 58 16. Channel Assignment 60 17. Conflict Elimination 61 18. Final Horizontal Positioning 63 19. Final Vertical Positioning 65 20. A Directed Graph 66 21. A Generalized Path 69 1. INTRODUCTION Since its beginning in 1955* automated design of digital electronic equipment has "become a formidable area of study. A large body of information has been published in the open literature [ 3] > including a recently published book, [ 11] , which deals solely with the current tech- niques for the automated design of computer hardware. Design automation has been incorporated into every level of manufacturing, from register level computer descriptions to the diagnostic testing of the finished product. This dissertation, however, is restricted to the problem of automated printed circuit board design, which involves the placement of components on the board and the routing of wires to interconnect them. Optimal solutions to the placement problem can be found only for boards containing no more than 20 components [5,6]. In the case of wire routing, optimal solutions can be obtained [20] for individual wires but not for an entire board. Modern printed circuit boards present large placement and wiring problems with up to 200 components being intercon- nected on one board. Therefore, hueristic procedures are used for find- ing reasonable, sub-optimal placements and wire routings for these boards. Comparing these hueristic procedures to determine the most effective tech- niques is extremely difficult, and to date, no realistic comparison of published algorithms has been made. Steinberg's 3*+ component problem [ 16] has been widely used for comparing placement algorithms [11,19], but it is too small to be considered realistic today. The only comparison of wire routing algorithms is made in terms of the computer time required to route similar sized problems. One primary purpose of this disserta- tion is to begin a realistic comparison of hueristic design automation algorithms by publishing some large printed circuit board problems. ILLIAC IV is a large parallel processing computer designed by the University of Illinois and built by Burroughs Corporation [1,2]. A unique situation therefore exists in which a public institution has access to the detailed design specification of a large modern computer. Such information is usually subject to industrial proprietary classification. Proper application of this information, particularly to the area of design automation should benefit the academic community as well as in- dustry. The printed circuit board design problems found in the ILLIAC IV control unit are large, obviously realistic problems. Widespread use of these design specifications as test problems should produce significant new information about the placement and routing of printed circuit boards. Chapter 5 proposes a new algorithm [27] for wire routing which is designed for interconnecting integrated circuit packages. The new routing algorithm combines the best properties of some existing tech- niques, reviewed in Section 5.1, to achieve faster speed and greater flexibility. The implementation of the basic algorithm is discussed in detail and results are presented for the wiring of ILLIAC IV sample pro- blems. The wire routing program is also used to compare the results from various placement algorithms. 2. THE ILLIAC IV DESIGN PROBLEM The Control Unit (CU) of the ILLIAC IV computer is composed of many large multilayer printed circuit boards. Each hoard can contain up to 165 integrated circuit packages arranged in eleven rows of fifteen packages each (Fig. 1). The integrated circuit packages employed are sixteen pins dual inline packages. The integrated circuits use high speed emitter coupled logic (ECL) technology with gate times in the range of two to four nanoseconds. The placement and wiring of the ILLIAC IV CU hoards represents a large collection of design automation problems . This set of problems was first solved by the Burroughs Corporation along with the University of Illinois. The high speed which was sought for the ILLIAC IV CU dictated a number of very strict wiring rules. First of all, a multilayer board was required so that ground planes would surround each signal layer in order to insure proper transmission line effects. The use of transmission line technology also restricted the manner in which connections could be made. Each connection was required to proceed from the source through each load until the final one where it was to be terminated by the proper resistance. Each pin to be connected could have only two wires connected to it so the connection had to be chained (Fig. 2). In addition, there was a minimum limit placed on the length of each connection in order to eliminate unwanted reflections. In certain special cases further res- trictions were imposed. For the sake of timing the lengths of two wires were sometimes required to be identical which resulted in laying out portions of some boards completely by hand. IIIZD 10 CD CD 9 CD CD □ 8 CD □ o □ 7CD CD □ □ □ 6CD CD cd □ □ □ 5CZJ CD □ □ □ □ □ 4 CD □ □ □ □ □ □ □ 3CD □ □ □ □ □ □ CD cd 2CD □ □ □ □ □ □ □ □ CD ICD CD 1 2 3 □ 4 5 □ 6 □ CD 7 8 9 10 □ CD CH CD II 12 13 14 15 t'"ii inn inn inn inn inn him in inn niii I in I inn Figure 1. ILLIAC IV CU Board 1 CO i-i- D CHAINED CONNECTION TOTAL WIRE LENGTH =15 Figure 2. A Chained Connection. For the purposes of this dissertation the CU board design problem will be somewhat simplified. What is desired is a set of large realistic design problems which are to be solved using a set of widely known and accepted wiring rules. The first step in simplifying the design problem is to consider only the signal connections to be made on each board. The specification of the wiring for each board is presented in the form of a netlist . By removing the power and ground connections from each netlist, specifications can be presented which determine only the signal connections to be made. Simplified netlists for five CU boards are listed in Appendix A. A second step in simplifying the design problems is to specify a less restrictive set of wiring rules. The following set of rules was chosen to provide the greatest ease in. comparing different place- ment and routing techniques: 1. No upper or lower limit is imposed on the length of any one connection. 2. No limit exists on the distance that two adjacent wires may run in parallel. 3- All wire segments are vertical or horizontal. (Manhattan geometry. ) k. No limit is placed on the number of wires which can meet at one point. 5. A two-sided board can be used for wiring. 6. Potential positions for packages as well as positions of edge connectors are fixed on the board. 7. Plated through communicating holes (Vias) can be specified by the design process and are not limited in number. Such a simplified set of wiring rules is intended only to help in compar- ing the effectiveness and speed of a wide range of placement and routing algorithms. In order to be useful, design algorithms should be capable of handling more difficult problems. The detailed specification of the CU board has also been sim- plified somewhat. The positions reserved for pulldown and terminating registers have been eliminated and the position of edge connectors has been slightly rearranged. The results of this dissertation are based on the following specifications: 1. Eleven rows of fifteen package positions (Fig. l). 2. Package pins numbered from lower left in a counterclock- wise fashion (Fig. 3)» 3- Minimum wire spacing is 50 mils. k. Packages are .75 inches apart in the vertical direction and .5 inches apart horizontally. (Fig. h.) (The package spacing is retained from the original specification as an arbitrary reference.) 5. Edge connectors are arranged in fifteen groups of sixteen pins each. Each group is directly below a column of packages and the pins are numbered as shown in Figure 5- (Note that each group of edge pins can be treated as a package position for the purposes of placement and wiring. Once again the aim of this simplified specification is to make the CU board design problems easy to work with so that comparison of different algorithms can be facilitated. 16 n n n n 0.1 n r-i n n uuuuuuuu 1 8 16 PIN DUAL INLINE PACKAGE Figure 3. An Integrated Circuit Package 7 CHANNELS 9 CHANNELS i i i i i i 1 1 1 1 1 ii 1 1 i 1 1 it 1 1 1 1 1 1 5 CHANNELS ► - 14 CHANNELS JT - .75 Li CHANNEL ARRANGEMENT Figure k. Package Spacing. 16 15 14 13 12 11 10 9 lt2T3t4?5T6 • 7 t ft t 50 mils Figure ^. An Edge Connector Group. 10 3. GENERAL. DESIGN AUTOMATION DISCUSSION 3.1 Measurement Techniques The overall objective of a design automation system is to manufacture a piece of equipment with a given performance in the short- est possible time and for the lowest possible cost. Since decreasing the production time usually requires an increase in cost, some tradeoff must be made between these goals. The objective of each stage of the design process is also some minimization of time and cost. For the functions of placing and wiring printed circuit boards the amount of time can usually be measured directly, whereas the costs involved are quite complex. In order to minimize production costs it has been tra- ditionally assumed that placement algorithms should strive toward mini- mizing the total wire length and the routing algorithm should strive toward minimizing the amount of area consumed in wiring. These mea- surements will be used throughout this paper to compare the effective- ness of various techniques. However, consideration will be given to the possibility of determining more meaningful measurements. In order to minimize costs, a placement algorithm should pro- duce a placement which can be wired efficiently under a given set of wiring rules. The ease of routing a board is typically dependent on the number of crossovers and the amount of congestion in a given area as well as on the total amount of wire that must be routed. It is generally assumed that decreasing the total wire length will decrease the number of crossovers and the amount of congestion in specific areas. This may 11 "be true., but at the same time it is obvious that there are other ways of more directly improving the wireability of a board which, for instance, might take into account the amount of congestion in a given area. In Chapter k of this dissertation there is a quantitative evaluation of the factors contributing to the wireability of a board. 3.2 The Assignment problem The simple assignment problem can be demonstrated in terms of assigning modules to positions, where a specific cost can be determined for the assignment of a particular module to a particular position inde- pendent of the positions of other modules. If the objective is to mini- mize the cost, this can be accomplished by minimizing the sum of all individual costs, C. ., of assigning module i to position j , where each module can be assigned to one and only one position. Munkres [ h] has formulated a solution to this problem which is practical for up to 200 modules. Placing a package on a printed circuit board, however, does not have a fixed cost (in wire-length) that is independent of the position of other packages. The placement problem cannot therefore be formalized as a simple assignment problem. The placement problem can be formalized as a quadratic assignment problem, but there are no known solutions to the quadratic assignment problem that are practical. The most obvious solution is to simply enumerate all possible assignments and determine which has the lowest cost (total wire-length). Such a solution requires ni assignments and cost evaluations and could be used only for the smallest 12 problems. Branch and bound techniques reduce the number of operations required and can be used for small n (15 - 20) as shown by Lawler [5] and Gilmore [6]. The computation time for these techniques increases exponentially as the number of packages increases. As a result , the placement problem for large printed circuit boards has been approached by heuristic algorithms. Measurement of the comparative effectiveness of heuristic techniques is very difficult since optimum solution are usually unknown and since large realistic problems are not publicly available. Therefore, the thrust of the placement por- tion of this dissertation is the comparison of existing heuristic algo- rithms. 3. 3 The Interconnection Problem When several points on a printed circuit board are to be made electrically common, the interconnection which connects them is called a net . The manner in which a net is formed is often determined by the wiring rules of the board. The wiring rules adopted in Chapter 2 do not place any restrictions on the manner in which nets can be connected. Each net is therefore connected in such a way as to minimize the amount of wire used. The minimum spanning tree algorithm of Prim [7] is used to determine how each net is connected. This algorithm assumes that each connection must be made from one node on the net to another node on the net (Fig. 6a). If additional nodes are allowed to be added the result is a Steiner [9] tree which will always have a wire length less than or equal to that of the minimum spanning tree (Fig. 6b). However, Steiner trees are much more 13 difficult to find than minimum spanning trees [10] and they place considerable restrictions on the actual wire routing. Also, when Manhattan geometry is used, the difference between the wire length of a Steiner tree and that of the corresponding minimum spanning tree tends to be very small. OB D (a) MINIMUM SPANNING TREE TOTAL WIRE LENGTH = 14 < I 3 2 B 1 , IF* • c 2 * at > 2 1 i ► (b) STEINER TREE TOTAL WIRE LENGTH s 12 *PSUED0- NODES Figure 6. Minimum Spanning Tree Versus Steiner Tree, 14 4. PLACEMENT 4. 1 Preliminaries 4.1.1 Connection Specification In order to generate a placement it is necessary to obtain a complete specification of the interconnections to be made between com- ponents. This specification usually takes the form of a list of signal nets. The elements in this list contain the name of the component, the pin on that component to be connected, a source/load indication and the name of the signal net. When the list follows the format of each source being immediately followed by all of its loads the signal name is not needed to determine which nodes (list elements) are on the same net. This format will be used for specifying the signal nets for the ILLIAC IV CU boards ( see Appendix A) . To facilitate the use of interconnection information a program was written to read the net list and generate cross reference tables con- taining all the needed information. All of the placement programs re- ferred to in this paper work directly from these tables. The first table, COMPS, contains one entry for each pin of each component to be placed on the board. This table is stored as an array with one dimension being the component number and the other being the pin number on that component. Each entry in this table has one of four meanings, depending on its initial character. 15 1. The component and pin number to which this pin connects. Component names begin with an "A". 2. The edge connector pin of the board to which this connects. Edge connector pin names begin with a "P". 3. The number of the net to which this pin connects. Net numbers begin with a blank. k. No connection is made to this pin. No connection is indicated by a "*". U.1.2 Wire Length for One Package Often times during the course of a placement algorithm it is useful to know the contribution made to the total wire length by the connections from only one package. Such information allows a computer program to determine whether moving one component to a new position will increase or decrease the total wire length. When such a component is connected to one or more nets it is very difficult to determine exactly how much wire is contributed by that component. The only way to find out how much wire is used is to measure the entire wire length of the net with the component being moved first in one position and then in the other. This measurement gives the change in the wire length of the net due to the moving of one component but it does not tell how much wire that component adds to the net in each position. The contribution made to the total wire length by the connections from only one package will not be measured. In each case the total wire length of the connections from one package will 16 be measured including the entire length of each net. Whereas such a measurement is not useful in itself, the difference in two of these measurements gives the exact change in the total wire length that results from moving one component to a new position. k.2 Serial Placement Techniques U.2.1 General Description Serial placement algorithms assign packages to positions on a printed circuit board in only one pass. One package at a time is chosen and placed in a final positions, until all of the packages have been placed. Ihis process can be broken down into two distinct subprocesses. The first is the selection process which chooses the next package to be placed and the second is the positioning process which assigns the chosen package to a position on the board. These two subprocesses are quite independent and several methods have been described for performing each of them [11]. The obvious advantage of using a serial placement algorithm is the speed of execution, with the number of operations performed being directly proport- ional to the number of units being placed. The obvious disadvantage of the serial techniques is that once a unit is placed, it can not be moved to compensate for further developments. Because of this rigidity in the serial methods, along with their speed, they are often used simply to generate initial placements for other placement algorithms. The order in which units are to be placed is determined by maximizing some objective function. This function is dependent on the number of connections that each package has. One of the simplest such 17 functions is the pair linking method [ lk] which proceeds in the following manner. At any given time in the serial placement process, some packages have been placed on the board and some are available to be placed (Fig. 7). The pair linking method finds the package not already placed which has the greatest number of connections to one package which has been placed. Thus, the most strongly linked pair between the unplaced and placed packages has been found and the unplaced member of the pair is assigned to be the next package placed. At this time the selected package can be assigned to a final position on the board or it can simply be entered into the set of placed packages so that the entire order of placement can be determined. The process can be broken into two separate routines, the first one orders the packages and the second one positions them on the board. Different ordering and positioning algorithms can then be intermixed conveniently. The cluster development [ lUl selection method uses a more com- plex objective function than the pair linking method. In cluster devel- opment, the next package to be placed is the one among the unplaced pack- ages which has the greatest number of connections to already placed pack- ages. Counting the number of connections to other units presents a slight problem for both the cluster development method and the pair linking method. The problem is to determine how many wires are needed to connect a package to a net. In Figure 6a, nodes A, B, C, D and E are all con- nected on one net. Whereas nodes, A, C and E are connected to the net by only one wire, node D is connected by two wires and node B is connected by three wires. At the time that one package is being placed, some of 18 J^ PLACED NOT PLACED Figure 7« Package Selection. the packages which are connected to it by nets may not he placed so that complete formation of the net is impossible. One solution to this pro- blem is to form as much of the net as possible, for instance, to create a minimum spanning tree for the nodes which correspond to the already placed packages of the net. This approach will not be perfectly accurate so a less time consuming approximation should be acceptable. Such an alter- native is to connect the package being placed only to the nearest node of the net in each case. The motivation behind cluster development is to choose the package with the greatest number of connections to packages already fixed in position so that the chosen package can be placed with the greatest accuracy. A further criterion for choosing a package might be to minimize the number of new connections to unplaced units which it generates [15]« 19 The idea here is to create the fewest possible restrictions on the future placement of packages. The realization of this idea is to choose the package which has the greatest difference between connections to already placed packages and connections to unplaced packages. The second half of each serial placement algorithm is a routine which assigns each package to a final position on the board. The objective in placing each unit is to minimize the amount of wire that is added when connecting that unit. Only those wires which connect to already placed components may be considered. The most obvious and also the most time- consuming method for finding the best position for one package is to try it in every available position. The amount of wire used to connect the package at each position is measured, and the position which requires the lowest amount of wire is chosen as the final position. In order to de- crease the amount of time involved several simplifications can be made. Rather than trying each unit in every available position a sub- set consisting of the most likely positions can be tried. Since the edge connectors on an ILLIAC IV CU board are all on one edge (Fig. l), the placement of packages will begin at that edge and grow away from it. In this case a subset consisting of the first available position in each column of package positions (open boxes in Fig. 8) could be used. This selection limits the number of positions tried for each package to fifteen. A much more flexible set of candidates can be conveniently generated in- volving a slightly larger subset. This larger subset is made up of the positions which "outline" the previously placed packages (all boxes in 20 ''ig. 8). Although it can be shown that the optimum position for a pack- age may not be contained in the "outline, " this method is much faster than trying all available positions. Figure 8. Candidate Positions, 21 U.2.2 The Serial Placement Program One serial method was programmed and used to produce placements which could he compared to those generated hy other techniques. The se- lection and positioning rules employed in the program were chosen mainly for their ease of implementation and speed of execution. No attempt was made to find the "best" serial placement method. The intention here was to implement a reasonable technique to be used as the basis for some mean- ingful comparisons. The placement method which is described in detail below, will be referred to simply as the Serial Placement method for the remainder of this dissertation. The selection rule employed chooses the package with the great- est number of connections to the already placed packages. Initially, the only packages placed on the board are the edge connectors which interface with the backplane. Therefore, the first package chosen for placement is the one which has the greatest number of connections to connector pins. Implementing such a scheme is quite straightforward. Step 1. Initialize c Each package is assigned a value c. which indicates how many connections it has to connector pins. Step 2. Select one package for positioning. Find the maximum c i and select the corresponding package. Step 3. Update c. For each package connected to the most recently selected package c. = c. + ti where n is the number of times it is connected. Step k. If all packages have not been selected yet, return to Step 2. 22 In the algorithm above, Step 3 is very important. The most recently chosen package may be connected to a net (a connection involving more than two packages). When this occurs, each package on the net will have its c value increased by one. Each package on a net is therefore con- sidered to be directly connected to every other package on that net rather than just being connected to the net. Each time a new package is indicated as the next to be placed it is tried in several of the available positions to determine which one will require the least amount of wire to connect it. In order to save time, the new package is not experimentally connected at every available board position. Only those positions adjacent to already placed packages or to board connector pins are investigated as depicted in Figure 8. The measurement which is made at each position is simply the Manhattan dis- tance for each point-to-point connection plus the distance to the nearest node of a net. In many cases the package to which a connection should be made has not yet been placed. In such instances the connection is com- pletely ignored, and for this reason the proper formation of nets could not be employed, so the above simplification was used. U.2-3 Serial Placement Results The Serial Placement program was used to place 20 different ILLIAC IV CU boards (Table l). These 20 boards constitute a representat- ive subset of the entire set of 6k different CU boards. This subset was chosen on the basis of total wire length and number of packages. The pro- gram was run on a Burroughs 6500 computer which has a five megahertz basic Table 1. Serial Placement Results 23 Board Name Number of Total Wire Placement Vertical Horizontal Packages Length Time (sec) Overflow Overflow FIRDB 52 725 19 1 FDS 63 1102 18 IWSCTL 83 1159 2U FDQA 93 1230 25 FIRCB 102 1292 27 FORC 96 1313 28 IIAA 118 13^0 3^ FWLDF 102 13^6 22 ATPOT 101 1U29 27 1+ MTMCTL 111+ 1U60 25 MPCTL 99 1527 29 TXFER 97 1608 22 5 ICTLA 110 1637 26 MDSPLY 75 1736 20 16 32 ATP05 112 1851 U6 1+3 FBUSY 119 2058 28 2k 3 ATP25 13^ 2126 1+1 TCRFLD 136 2318 30 16 9 ILTCL lUl 2Ul6 37 37 IICR1 121 3306 38 1+2 78 2k clock speed. The placement times shown in Table 1 give the processor time used. The Channel Routing program described in Chapter 5 was used to route the boards placed by the Serial Placement Program. The routing results are intended to measure the wireability of the placements and to determine whether wire length measurement can be used to predict wire- ability. The last two columns of Table 1 indicate the success of wiring the boards when the original package spacing for ILLIAC IV is used. This spacing shown in Figure k allows a total of 19 channels for each package row and 16 channels for each column. The edge connector pins are located 1.7 inches from the first row of packages allowing 33 horizontal channels in that area. The number of overflows in Table 1 is the number of addi- tional channels needed after final positioning to completely wire the board. In Table 2 additional routing information is given. The last two columns of Table 2 indicate the minimum number of channels which must be available in each row or column of packages for complete wiring using the Channel Router. The wireability measure is intended to indicate the total amount of successful wiring as well as the distribution of wiring density over the board. Table 3 is the correlation matrix of several of the variables present in Tables 1 and 2. All of these variables are shown to be related by the fact that all correlations are positive with most of them above .5. A few of these results are considered significant. The high correlation (.88) between the number of connector pins used and the number of vertical channels required may be helpful in partitioning logic onto boards. Such 25 Table 2. Wire Routing of Serial Placements Board Connector Total No. of Total No. of Vertical Horizontal Name Pins Used Vertical Channels Horizontal . Channels Wireability Wireability FIRDB 57 121 116 13 20 FDS 156 201 112 16 18 IWSCTL 173 181 128 15 17 FDQA 91 171 lk8 13 17 FIRCB 1U6 185 1^2 13 15 FORC Sk 172 lU6 16 18 IIAA 90 163 169 15 17 FWLDF 1U9 187 131 Ik 15 ATP07 156 207 137 15 21 MTMCTL 135 176 137 Ik 15 MPCTL 15H 195 158 16 18 TXFER 22U 222 U+5 16 21 ICTLA 17< 221 165 16 18 MDSPLY 223 257 15U 20 26 ATP05 178 250 2lU 30 19 FBUSY 220 265 18U 18 21 ATP25 170 232 215 16 18 TCRFLD 196 230 205 19 22 ILTCL 211 278 192 22 18 lie 221 283 303 21 32 26 Table 3. Correlations 1 2 3 1+ 5 6 7 1.00 ,4o • 73 .56 .67 .36 .04 .1+0 1.00 •69 .88 .48 .53 .50 •73 .69 1.00 .86 • 93 • 59 .66 1. Number of Packages 2. Connector Pins Used 3- Total Wire Length 4. Total No. of Vertical Channels .% .88 .86 1.00 .71 .72 .89 5. Total No. of Horizontal Channels .67 .48 .93 -71 1-00 .62 .64 6. Vertical Wireability .36 .53 -59 -72 .62 1.00 .42 7. Horizontal Wireability .04 .50 .66 .89 .64 .42 1.00 27 a measure should help predict the difficulty of wiring the boards in a given partition. The total wire length correlates highly with the number of vertical (.86) and horizontal (-93) channels required. However, total wire length does not predict wireability consistently. k. 3 Iterative Placement Techniques ^••3-l General Description All iterative placement techniques begin with a complete place- ment of a board. These initial placements can be generated manually or by random selection or by another placement algorithm. Each step in the iterative technique changes the positions of a subset of the packages so that the total wire length of the board is decreased. Thus, after any iteration, the board is completely placed and the process may be termin- ated. The algorithm continues until some stopping criterion is met. Most times these methods are stopped when no further decrease in the wire length is being made. The advantage of iterative schemes is that they produce better placements than the serial methods. Even though some iterative techniques are very simple to program they all tend to require large amounts of processing time. An exhaustive pairwise interchange is the simplest iterative scheme. Biach iteration consists of interchanging two packages on the board and determining whether that interchange results in a decrease in the total wire length. If no change occurs or if the total wire length is increased, the packages are returned to their previous positions. An exhaustive pairwise interchange systematically attempts every possible interchange between two packages on the board. The exhaustive pairwise 28 interchange can be repeated until none of the interchanges result in a decrease in the total wire length. A local minimum has then been reached. An exhaustive three-way interchange is a similar technique which tries all possible interchanges of three units in each iteration. It has been shown however, that the results of the three-way interchange are not signifi- cantly better than those of the pairwise interchange [29J. Steinberg's algorithm [ 16] considers a large subset of all the packages during each iteration using an optimal procedure for reposition- ing that subset. The basic subset used in Steinberg's algorithm is an unconnected set of packages. An unconnected set (Fig. 9) is made up of packages, such that no package in the set is connected to any other pack- age in the set. Therefore, the positioning of any one package of an un- connected set is completely independent of the positioning of the other °v □- UNCONNECTED SET REMAINING ELEMENTS Figure 9- An Unconnected Set, 29 packages of the set. The placement of an unconnected set of units in the available board positions (Fig. 10) created by their removal is therefore a simple assignment problem for which an optimal solution can be easily found [ k] . The positioning of the unconnected set of units will always either decrease or not change the total wire length of the board. There are many unconnected sets that can be formed from any given set of packages. The process for constructing an unconnected set starts by choosing a package at random and proceeds by adding to the set only those packages which are not connected to members of the set. This process is continued until a set of the desired size has been formed or until no more packages can be added to the set. An unconnected set which can not be added to, is known as a maximal unconnected set. '!he size of the unconnected set to be used will be largely determined by the com- puting power available for solving the assignment problem. It is always preferable to use maximal unconnected sets when possible to ensure the greatest flexibility in the assignment. Rutman [17] suggested an improvement to Steinberg's algorithm to produce better placements and to speed up the convergence of the algo- rithm. After some predetermined number of Steinberg iterations Rutman inserts an interchange step which decreases the length of the longest wires, ''hen Steinberg's algorithm is applied for a few more iterations. Rutman 's interchange seems to help keep Steinberg's algorithm from stop- ping at a local minimum. 30 □ □ □ □ 1 1 □ □ Figure 10. Board Positions of an Unconnected Set. 31 Another iterative placement method employs a relaxation prin- ciple. After an initial placement is established a measurement is made for each package which determines how strongly it is connected to other packages. This measurement represents the degree to which one package wants to be close to another. Each of these measurements can in turn be represented by a force which acts to move a package closer to the pack- ages it connects to. An equilibrium position which balances the forces on each package is then computed for all packages. The new placement is then formed by moving all packages to the position closest to their equilibrium positions with the constraint that no two packages may occupy the same position. Other relaxation methods are quite similar to this description and are beginning to appear in the literature [11]. One difficultly in implementing a relaxation algorithm is the problem of representing net connection so that they realistically influence position- ing during each iteration. k . 3 . 2 The I'airwise Interchange Program The pairwise interchange program exhaustively attempts all possible interchanges of two packages. The change in the total wire length of the board that results from each interchange is determined, and only those interchanges which decrease the total wire length are actually made. If any interchanges are performed during this process then the board positions will be different at the end than they were to begin with. Further improvement may be possible by simply trying all possible interchanges on this new board placement. Continued 32 iteration through all possible pairwise interchanges may or may not continue to improve the total wire length of the board. As soon as one iteration fails to produce an improvement a local optimum has been reached which has the property that no interchange of any two packages will result in a reduced total wire length for the board. This local optimum is not unique. Its configuration depends on the initial place- ment of the board. Implementing the Pairwise Interchange method is quite straight forward; however, some care must be employed to keep the execution time from becoming unreasonable. When considering the interchange of two packages, it is not practical to measure the entire wire length of the board before and after the interchange. Only the change in the total wire length is important. If all of the connections to the two packages in question are point-to-point connections this calculation becomes trivial. The difference in total wire length is simply the change of length of each connection. Frequently, however, a package will be con- nected to a net which is a single connection of more than two points on the board. The amount of wire needed to connect a package to a net can not be determined without reconstructing the entire net each time this information is needed. Since the structure of the net may be changed significantly by moving one package the change in total wire length will only be correct if it is determined by taking the difference of the entire length of each net for the two package positions. The difference 33 in total wire length measured in this manner will he the same as when the total wire length is computed for each position and then the difference taken. The results will therefore he the same while a great increase in speed will he achieved. Trie algorithmic description of the pairwise interchange pro- gram is given below, where P(l) represents the I th package, and N is the number of packages. Step 1. Initialize. Set initial positions of packages on the board. Set 1 to 1 and J to 2. Set IND to 0. Step 2. Measure the wire length of the connections to P(l) and P(J). Step 3- Interchange P(l) and P(J). Step It. Measure the wire length of the connections to P(l) and P(J) in their new positions and determine the total change in wire length (&to) . Step 5, Cf AW is positive, interchange P(l) and P(J) returning them to rial positions. Otherwise set IND to 1. gtcp . ' ] • Otherwise if J N set J 1-0 1 and I to I + 1 and go to Step 2. Otherwise set J to ,l + 1 and go to Step 2. Step 7. Cf END then done. Otherwise go to Step 1. 3^ t+. 3 - 3 Pairwise Interchange Results Since the iterative placement programs required large amounts of computer time, a set of only five boards was chosen to compare them. The complete net lists for these five hoards are given in Appendix A. Each of the iterative placements used the Serial Placement results as initial placements. Also, the iterative placement interchanges were restricted to the hoard positions filled by the Serial Placement program. Each iteration of the Pairwise Interchange program attempts all possible pairwise interchanges of packages on the board. These iterations are repeated until one produces no improvement in the wire length indi- cating a locally optimal solution. The Pairwise Interchange Results in Table h include this final iteration. The execution time for each iter- ation of a given board placement remains about the same, decreasing slightly as the number of interchanges decrease. The execution times given in Table k are the processor times for execution on a Burroughs 6500 computer and can be directly compared to the Serial Placement times. k.3-h Implementation of Steinberg's Algorithm Steinberg's placement algorithm [ 16] was the most difficult of the three methods to implement; therefore, it was implemented in its most simplified form. The algorithm consists first of finding a set of pack- ages such that a member of the set does not connect to any other member of the set. Since the members of such a set are independent, they can be interchanged by a simple procedure which will insure that the total wire length of the board will be improved or at worst stay the same. Repeated application of this procedure to different sets of packages will continue to decrease the total wire length until some local optimum is reached. 35 Table k. Pairwise Interchange Results Board No. of No. of Inter- Execution Starting Final Improve- Name Iterations Changes Time (Min. ) Wire Wire ment Length Length FIRDB 2 Ik 2k 725 700 3-% FDQA. 1+ 57 Qk 1230 1085 12 % ATP07 3 ^5 55 1U29 1320 1.% FLD 3 in 67 2318 22U3 3 1o IICR1 k iua 136 3306 281+5 lh i 36 A set of packages which have no connections to other packages within the set is called an unconnected set and- is illustrated in Figure 9. Such a set can be easily formed in the following manner: Step 1. Initialize. Mark all packages to be unconnected. Step 2. Select one package at random. If it is marked connected repeat Step 2. Step 3« Mark the selected package and all packages it connects to, as connected. Enter the selected component in the unconnected set. Step ^4. When the required number of packages are in the unconnected set or when all of the packages have been marked unconnected, stop. Otherwise return to Step 2. When an unconnected set is formed such that no other package can be added to the set, it is called a maximal unconnected set. The above descrip- tion represents the implementation which was employed; therefore, the unconnected sets are formed in a random manner. The size of the uncon- nected sets is kept as large as possible and often times maximal uncon- nected sets are used. Since the elements of an unconnected set are by definition not directly connected to one another, the positioning of each member of an unconnected set is completely independent of the positioning of the other members. Therefore, the problem of optimally placing an unconnected set of packages with respect to minimum wire length reduces to a simple linear assignement problem which can be quickly solved by Munkres Algorithm [ U] . 37 There is one small problem which must be handled properly. In setting up the assignment problem a measurement must be made of the amount of wire needed to connect a package in each of the available positions. As was the case in the Pairwise Interchange method, each time a net is encoun- tered during this measurement, the entire net must be reconstructed and the entire net wire length must be added. Each entry, C. ., of matrix C is therefore the wire length used in connecting package i in position j . The difference, c. . - c , gives the exact change in wire length for 1J IK. moving package i from position j to position k. The following algorithmic description of Munkres method is given by Rutman [17] in his implementation of Steinberg's algorithm. Preliminaries In the matrix [C], no lines are covered and no zeros are starred or primed. Consider row 1 of the matrix. Find the smallest element in row 1, and call it h, Subtract h from each element of row 1. In the process of subtracting h, some element (or elements) of row 1 become zero. Whenever an element becomes zero and if there is no starred zero in the row and none in its column, star the zero and cover the column containing the zero. If there is no zero star in its column but there is one in its row, add the matrix coordinates of the zero to the zero 38 A list (unless the zero A list is already full). Do the same for each row of the matrix.* If N columns are covered, the starred zeros form the desired result, and the problem is finished. If less than N columns are covered, go to Step 1. Step 1 Take the coordinates of a zero from the zero list, popping up the zero A list. If the zero is covered, push the coordinates of the zero into the top of the zero B list and take another zero from the zero A list. Continue until a non-covered zero is found or until the zero A list is depleted. If the zero A list is depleted and flag F is set search the matrix for an uncovered zero. If the zero A list is depleted and flag F is reset, go to Step 3- Assume an uncovered zero is found. Prime the zero, then consider the row containing it. If there is no starred zero in this row, go at once to Step 2. If there is a starred zero in the row, cover the row and uncover the column of the starred zero. Look for any uncovered zeros in this new uncovered column. If any exist, add their coordinates to the top of the zero A list (if the zero A list overflows, set flag F). Then go to beginning of Step 1. ¥r Note that at this time the zero A list (if sufficiently large) will contain the coordinates of every uncovered zero if any exist. If there are too many zeros for the zero list to hold, flag F will be set. Otherwise, flag F is reset. 39 Step 2 There is a sequence of alternating starred and primed zeros, constructed as follows: Let Z denote the uncovered (there is only one). Let Z* denote the 0* in Z ' s column (if any). Let Z denote the in Z ' s row (if Z exists, its column is not covered since Z„ is in its column and Z is not covered, so its row must be covered. Hence there is a In this row (see Step l). Let Z Q denote the in Z ' s column (if any). Similarly, continue until the sequence stops at a which has no in its column (Munkres proves such a exists and the sequence is unique)). Now unstar each starred zero of the sequence, and star each primed zero of the sequence. Erase all primes (that is, remove the zero prime coordinates from vector C ). Uncover every row and cover every column containing a . If N columns are covered, the starred zeros form the desired result and the algorithm is finished. Otherwise, empty the zero B list into the bottom of the zero A list and go to Step 1. Step 3 - Let h denote the smallest uncovered element of the matrix; it will be positive. Add h to each twice-covered element. Subtract h from each uncovered element. In the process of subtracting h, add the coordinates of any new zeros to the zero A list. Return to S bep 1 without altering any stars, primes, or covered lines. ko U.3.5 Steinberg's Placement Results The Steinberg Placement program was tested on the same problems as the Pairwise Placement program (^«3»3)- The results of the Steinberg placements are presented in Table 5« Each iteration involves choosing and repositioning one unconnected set. The program was stopped when 50 consecutive iterations produced a decrease in wire length of less than 10 units. For each placement except that of board IICR1 it appeared that no further improvement would be made in the wire length. The placement of IICR1 had improved by 15 units in each of the last two sets of 25 iter- ations and would probably continue to improve slightly. It was termina- ted after one hour of processor time for monetary reasons. The Steinberg Placement program was run on a Burroughs 67OO computer which is a faster modified version of a 6500. The execution times for Steinberg results can not be directly compared to other placement execution times. The basic clock speed of the 6500 and 67OO are the same but the 67OO is faster on some operations. The conclusion indicated is that the Steinberg Placement program is faster than the Pairwise Placement program, but not twice as fast. 1+1 Table 5. Steinberg's Algorithm Results Board No. of Size of No. of B67OO Execution Starting Final Wire Improve - Name Iterations Unconnected Inter- Time (Min. ) Wire Length Length ment Set Changes FIRDB 100 Max ( 8-1?) k 8 725 702 3 % FDQA 150 Max (15-20) 23 29 1230 1122 9 35 ATPOY 150 Max (25-30) 32 U9 li+29 1320 7-5;; TCKFLD 150 30 32 33 2318 2181 5.5* IICR1 150 Max (25-30) 75 62 3306 2733 17 % U.1+ Comparison of Results The results of applying the Channel Routing program to the Pairwise and Steinberg placements are presented in Table 6. These results are used to measure the effectiveness of applying iterative placement algorithms to serial initial placements. The only clear conclusion is that the change in wire length does not effectively predict the change in wireability as defined in Section U.2.3. Both the Pairwise and Steinberg program produce improvements in wireability in some cases but in most cases no change in wireability occurs. Generally, not enough im- provement is made to justify the computer time involved in the iterative techniques used in this study. k2 m P H w K £h O d O m •H M cd I VD H ■s >> H p nj •H -P H d ■H o cQ SI CCi •H U M o •H w is >5 p •H H H CO •H O ^ •H cd P ^ m •H > S H cd -P £ sd o o H N Cm ■H m M CD o > ffi O H > cd o O H •H > o 0) u •H £2 ,d H p CO M P d O CD H J P d CD S t3 0) O o ,d cfl P H CD PL, s TJ 5h CD 03 £ O 53 pq S o CVJ VD O CAJ c~ CO H H CM r-H on CM CAJ H O CM o o o o o o LT\ O CM o LT\ CM o O CO CO t- D— t- CM H o CD CD W W H •H rO H ■H cd & SJ cd *g ■H M ■H •H M M •H CD U •H CD cd P CD cd TO Fh CO CO Fn PQ Q H fa O O o M M E OBJECT Figure 13 . A Generalized Connection. 55 In fact, as long as all wire segments remain in the spaces they are ori- ginally assigned to, no connection will ever he more than 2V + 2H longer than its minimum. (Where V is the vertical distance between rows of pack- ages and H is the horizontal distance between columns of packages.) The channel routing program Appendix B) stores the description of each wire segment in one word of memory. All of the horizontal wire segments are stored in one array and all the vertical wire segments in another. Each array row in one of these two-dimensional arrays corres- ponds to a space on the printed circuit board. Channel assignment with- in spaces is therefore concerned with only one array row at a time which allows for efficient partitioning to backup storage in a multiprogramming environment. The description of a horizontal wire segment is detailed in Figure Ik. Although h'J bits are indicated as being divided into eight fields, some of the fields are larger than necessary so that a reduced word size may be possible. The channel field is used to indicate which channel this wire segment is assigned to within its space. A channel field of six bits restricts the size of spaces to being less than 6U channels wide. The one bit indicator field, I, is initially set to zero and is changed to one when this wire segment is assigned to a channel. 56 CHANNEL I LEFT POINTER RIGHT POINTER LEFT LEFT OFFSET RIGHT RIGHT OFFSET 46 41 40 39 3130 22 21 17 16 1110 65 Figure 1^. Data Format of a Horizontal Wire Segment The left pointer field contains a pointer to the vertical wire segment which connects (through a via) to the left end of this wire segment. Actually, the left pointer contains an index to a word of storage within the array row indicated by the left field. A left pointer field of nine bits allows a maximum of 512 wire segments to be assigned to each space. The right pointer field has the same purpose as the left pointer field, except that it refers to the right end point of the wire segment. The left field indicates the vertical space to which the left end point of this wire segment is restricted. A left field of five bits corresponds to a maximum of 32 vertical spaces being defined. The left offset field indicates the exact position of the left end point within the space indicated by the left field. The left offset field is changed after ver- tical channel assignment to indicate the channel to which the vertical wire segment that connects to the left end point is assigned. Therefore, the size of the left offset field is made consistent with the size of the channel field in reflecting the maximum number of channels per space. Combining the contents of the left field and the left offset field yields 57 one eleven-bit quantity which monetonically sequences the end points of all horizontal wire segments from right to left across the printed cir- cuit board. Finally, the right field and the right offset field have the same purpose as the left and left offset fields respectively, except that they refer to the right end point of the wire segment. Vertical wire segment information is also stored in words of memory which are divided into fields as inficated in Figure lk. The above explanation can be applied to the use of vertical wire segment fields by substituting the words, bottom and top, for the words, left and right, respectively and interchanging the words, vertical and horizontal. When space assignment is complete all wire segments needed to completely wire the board will be represented by words of storage in the horizontal and vertical wire segment arrays. The final vertical wire segment on each end of a general connection, (segments A and E of Figure 13) do not require any storage however, because they do not need to be considered during channel assignments and can be easily specified later. Figure 15 shows that these short final vertical wire segments do not take up any vertical channel space, and since no two pins have the same hori- zontal coordinate within a horizontal space, these final wire segments can not conflict with one another. Specifying that the end point of a horizontal wire segment is to be connected to a pin, (done by setting the pointer field to all l's) and knowing the horizontal coordinate of that end point is all that is required to completely describe the vertical wire segment needed to complete that connection. 58 4 VERTICAL CHANNEL • • • 1 j! i i i • • • • i • • • • i i HORIZONTAL SPACE BOUNDARY Figure 15. Wiring to a Package Pin. 59 5-2. h Channel Assignment After space assignment is completed each space will contain a set of wire segments. These wire segments are represented as a set of intervals having an upper bound and a lower "bound (Fig. 16). The object of channel assignment is to position all wire segments so that no two overlap and to use the fewest possible number of channels. The first step in the procedure is to search the list of intervals for the element which has the greatest upper bound. This element is assigned to the first channel and eliminated from the list. The list is then searched for the interval which has the greatest upper bound which is less than the lower bound of the previously chosen interval. This element is also assigned to the first channel and eliminated from the list. The search is repeat- ed until none of the remaining elements have an upper bound which is less than the previous lower bound, at which time the entire process is repeat- ed for the next channel. When all of the intervals have been eliminated from the list the channel assignment is complete. This algorithm always uses the minimum possible number of channels to finalize the positions of all of the wire segments in a given space. The proof of minimality will be given in Section 5.2.6. When the channel assignments are being made, precautions must be taken to ensure that the wire segments which must be joined to form a connection have end points which coincide. At the conclusion of the space assignment stage, many conflicts may exist since all wire segments are assumed to travel down the center of the space. Assume that two hori- zontal wire segments (l and 2) have the same end point (Fig. 17a). If 6o ±5 8 10 SET OF INTERVALS ±5 ..8 10 INTERVALS ASSIGNED TO FOUR CHANNELS 15 8 10 ALTERNATE MINIMAL SOLUTION Figure 16. Channel Assignment. 61 vertical wire segment 3 is to connect to 2 and vertical wire segment k is to connect to 1 then the two connections are sharing one via hole. Chan- nel assignment is now performed on all vertical wire segments. Since the upper bound of wire k is not less than the lower bound of wire 3; these two wire segments may not be assigned to the same channel. For this reason there can no longer be a via conflict between connections Ik and 23, but wire 1 may be in conflict with wire 2 (Fig. 1Tb). If such a conflict exists then wire 1 and wire 2 can not be placed in the same channel when horizontal channel assignment is performed. When all channel assignment is complete there is no conflict between connection 1^ and connection 23 (Fig. 17c). Other combinations of conflicting wire segments can be form- ed, but the channel assignment proceeds in such a way as to always elim- inate wire overlap and via conflicts. (a) AFTER SPACE ASSIGNMENT (b) AFTER VERTICAL ASSIGNMENT (c) AFTER HORIZONTAL ASSIGNMENT Figure 17. Conflict Elimination. 62 5-2.5 Final Positioning After channel assignment has been completed in each space, the number of channels needed for complete wiring is determined for each space. In some cases the number of channels needed may surpass the number of channels originally allocated to a given space. Although the availability of wiring area is restricted by the physical layout of packages on the board, the space boundaries are not tied to physical positions as explain- ed in 5.2.2. Figure l8a shows a typical initial positioning of space boundaries. The channel assignment (Fig. l8b) appears to overflow space B which would cause incomplete wiring. However, by moving the boundary between space A and space B upward one channel it becomes possible to fit all wires without overflow (Fig. l8c). Once channel assignment has been completed a simple algorithm can be applied to optimally position the horizontal space boundaries. The objective of this procedure is to minimize the number of channels which will not fit within the physical limitations over the entire hori- zontal side of the board. This algorithm consists merely of locating each boundary between spaces to its upward most possible position (i.e., farthest from the edge connectors on the board). A space boundary can be moved upward until it encounters either an already fixed space boundary or a physical limitation (either a row of pins or the edge of the board). Starting from the uppermost boundary of the space the channels assigned to that space are given their final positions working downward until either the set of channels for that space is exhausted, or the lower phy- sical boundary for that space is encountered, at which time the remaining 63 SPACE A 3 CHANNELS SPACE A ■ SPACE 8 (a) INITIAL SPACE POSITIONING 3 CHANNELS SPACE B - (b) CHANNEL ASSIGNMENT SPACE A •• ••!!•• SPACE B • • i • • A 1 • (c) FINAL POSITIONING Figure 18. Final Horizontal Positioning. 6k channels are entered in an overflow list. In either case a downward boundary is set for the space which may serve as the upward boundary for the next space. This procedure will minimize the number of channels which will be entered in the overflow list. The final positioning of channels requires an update to the positions of the horizontal wire segments within each channel. Also, an update must be made to the endpoints of vertical wire segments which con- nect to the horizontal wire segments that are moved. These updates are quite easily made. Also, it can be easily verified that these adjust- ments due to final positioning will not create conflicts and will not effect the optimality of the original channel assignments that were made. The same algorithm can be applied to the final positioning of vertical channels since vertical space boundaries are also free to move within physical limitations. However, in the case of final vertical posi- tioning, changes may be caused in horizontal wire segments which will effect horizontal channel assignment. In Figure 19 the movement of wire segment A causes wire segment B to change orientation and therefore con- flict with wire segment C. Such a change in wire segment orientation can cause a change in the channel assignments. In Figure 19a, wire segments B and C do not conflict, and could be assigned to the same channel, whereas, in Figure 19b, wire segments B and C can not be assigned to the same channel. A straight forward solution to this problem has been adopted. Vertical channel assignment and final positioning are performed before horizontal channel assignment begins. Final horizontal positioning and adjustments then completes the wire routing process . 65 VERTICAL SPACE VERTICAL SPACE B C_ • • • •*•!• / (a) INITIAL WIRE POSITION CHANNEL CONFLICT (b) MOVEMENT OF A VERTICAL WIRE WITHIN A SPACE Figure 19. Final Vertical Positioning. 5.2.6 Proof of Optimum Channel A s signment The set of wire segments assigned to a given space can be repre- sented as a set of intervals as previously stated (Fig. 16). This set of intervals can be represented by a directed graph (Fig. 20). The nodes of the graph represent wire segments and an arrow is directed from one node to another if and only if the lower bound of the first wire is greater than the upper bound of the other wire. Assigning wire segments to chan- nels corresponds to covering the directed graph which represents the set of wire segments with a set of directed paths. A directed path is com- posed of a set of nodes which are connected by arrows such that all arrows point in the direction of the path (dark arrows in Figure 20). Selecting a path corresponds to assigning the wire segments represented by the nodes 66 Figure 20. A Directed Graph. 67 on the path to one channel without overlap. A path cover of a graph is a collection of paths which includes each node of the graph exactly once. Two nodes in a directed graph are said to be incomparable if no path exists which includes both nodes. The greatest number of mutually in- comparable nodes which can be found in the directed graph must therefore be equal to the minimum number of paths which can be used to cover the graph. This property was first proven by Dilworth and the corresponding theorem bears his name. The largest collection of mutually incomparable nodes is referred to as a maximal incomparable set and in general several distinct incomparable sets from one graph may be maximal. To show that the channel assignment algorithm is optimal it must be shown that the number of channels used is equal to the minimum number of paths which can cover the corresponding directed graph. First of all a method of constructing paths must be found which corresponds to the method used to assign wire segments to channels. Such a path can be formed by choosing the node with the greatest upper bound then choosing the arrow eminating from that node which leads to the node with the great- est upper bound. The path is complete when a node is reached which has no outgoing arrows. The first step in the proof is to show that such a path which will be called a max chain contains exactly one member from each maximal incomparable set of the graph. By definition no path can contain more than one element of a maximal comparable set of nodes. Assume on the other hand that a max chain can be found which contains no members of a given maximal incomparable set. If this assumption leads to a contradiction then the first step is demonstrated. Since none of the nodes (N , ..., N ) are in a given maximal incomparable set (M , . . . , M ) they must all be comparable with a member of that set (Fig. 2.1). There is a node N. which is the highest node with an incoming arrow which leads from a member IYL of M. The next preceding node N. must have an outgoing arrow which leads to a member M of M. From the com- parisons described above it follows that the lower bound of IVL is greater than the upper bound of N . and the upper bound of M is greater than the lower bound of M, • Therefore the upper bound of M is greater than the upper bound of N . . This proves that N is not a max chain since the arrow from N. to M was not chosen. Therefore every max chain contains exactly one member from each maximal incomparable set. Eliminating the nodes along a max chain from the directed graph reduces the size of each max- imal incomparable set by one, reducing the number of paths required to cover the graph by one. Therefore the number of max chains needed to cover the graph which is equal to the number of channels used is always the minimum. This algorithm assumes that each wire segment is an indivisible entity. The question arises as to whether fewer channels would be re- quired if a wire segment could be split into independent subsections con- nected by perpendicular wire segments. To show that such a modification would not improve the number of channels required a proof will be given that the size of the maximal incomparable sets is not decreased. Assume that a wire segment which is a member of a given maximal incomparable set can be broken into several nodes so that none are incomparable with the maximal incomparable nodes. The lower bound of any of these nodes would 69 M Figure 21. A Generalized Path. TO be equal to the upper bound of the following node to preserve continuity. Figure 11 can again be used to show that a contradiction is generated. Node M is shown comparable with node M (L(M, ) > U(N.) > U(M )). There- fore such a division of one wire segment can not reduce the number of channels required to place a set of wire segments. 5.2.7 Results The Channel Routing program (Appendix B) was run on 20 ILLIAC IV CU boards placed by the Serial Placement program U.2.3- The results of routing within the package spacing shown in Figure k are given in Table 7- The density of wiring is presented as the percent of board area used. This figure can be calculated accurately only for those boards which are com- pletely wired. The amount of board space available is considered to be the total area up to the farthest package row from the connector pins which has any packages in it. This is a reasonable choice, since the Channel Routing program never routes any wires outside this area. The wiring density for boards which are not completely wired has a different meaning. This figure gives the density that would be attained if the package spacing s could be increased to allow complete wiring. The speed of the Channel Routing program is its most important assests. Many improvements of the type mentioned in Section 5*2.8 can be made without raising the running time above even one minute. The channel assignment routine which is the basis of the program takes only two or three seconds to finalize the wiring. Most of the program time is spent setting up the wire segment storage. This includes reading the wire list 71 Table 7. Channel Routing Results Board Name Total Vertical Horizontal Routing Percent of Wire Length Overflow Overflow Time (sec) Board Area Used FIRDB 725 1 8 19* FDS 1102 11 30 IWSCTL 1159 11 28 FDQA 1230 10 23 FIRCB 1292 12 25 FORC 1313 12 25 IIAA 13^0 12 21 FWLDF 13U6 10 26 ATP07 1^29 k 13 29* MTMCTL 1U60 11 25 MPCTL 1527 Ik 29 TXFER 1608 5 12 31* ICTLA 1637 12 26 MDSPLY 1736 16 32 13 36* ATP05 1851 ^3 17 21* FBUSY 2058 21+ 3 15 32* ATP25 2126 17 3U TCRFLD 2318 16 9 15 33* ILTCL 2U16 37 17 3*+* IICR1 3306 k2 78 20 35* These percentages are calculated by increasing the board dimensions to those necessary for 100 percent wiring. 72 and performing the space assignment. Also, the data structure of the program is well suited to a small core, multiprogramming computer. The channel assignment routine is basically interested in one array row at a time which keeps data storage requirements in core below 1000 words. The entire program requires about 5000 words of resident core to run on a Burroughs 67 00 computer. 5.2.8 Possible Improvements Two alternatives exist for improving vertical space assignment. One is to run the entire routing program once, simply to determine which vertical spaces use too many channels. This information can then be used to allocate space better on a second routing attempt. Another possibility is to perform vertical channel assignment is still in progress. This can be easily done because vertical wire segments can initially end only at the center of horizontal spaces. A simple count kept at each end point position will reflect the number of channels required so far. A combina- tion of both of these improvements might be better still. Changes in the final positioning routine may produce the most dramatic improvements. Final positioning allows space boundaries to be moved within certain physical limits. An improvement would be to allow wire segments to actually cross the space boundary as long as no conflicts are created. Rather than having wire segments cross space boundaries, the identical result can be attained by allowing space boundaries which are not straight lines. Preliminary study of routing data indicates that such a modification may increase wiring densities by five percent. More soph- isticated final positioning algorithms can be developed and should be investigated. 73 In the event of wiring failures a follow-up technique should he considered which takes advantage of the special properties of the channel routing method. The storage organization and the high speed of the chan- nel routing program should make failure elimination possible without ex- tensive use of maze running algorithms. One possibility is to change a number of space assignments so as to reduce localized overcrowding and then return to the original channel assignment routine. 6. CONCLUSIONS 6. 1 Placement Several basic placement algorithms were compared in Chapter k. During the course of implementing these algorithms some factors were found to greatly influence the results. The pairwise interchange method and Steinberg's algorithm were initially programmed with approximated wire length measurements. No significant improvements were made in the initial serial placements. After these two programs were changed so that all wire-lengths were exactly measured, they were able to make consider- able improvements on the initial placements. Also, it was found, as suggested by Garside and Nicholson [29], that systematic pairwise inter- change converges faster than random pairwise interchange. These con- . elusions are not intended as comparisons of alternative implementations. The factors involved are important because it was found that the algorithms simply would not work unless they were handled as indicated. The results presented in Chapter h support several interesting conclusions. The total wire length of a board must be augmented by other measures to clearly indicate the ease of wiring that board. Connections which leave the board (edge connector pins) significantly influence the wireability of the board. The most important measure however, is the dis- tribution of wiring density. These results indicate that assignment of edge connector pins is very important and better results can be obtained by allowing the placement program to assign the pin positions. Also, an effort should be made to incorporate information from a routing attempt into a placement improvement program. Such an effort is becoming prac- tical with the introduction of fast wire routing techniques like the channel routing algorithm of Chapter 5» 75 The comparison of serial and iterative placement techniques presented in Table 6 yields several conclusions. The serial placement method has a distinct time advantage and may produce completely wireable placements. In such cases, no further improvement should he sought. Iterative placement algorithms can produce improvements in -wire length and wireability when needed without using an unreasonable amount of time. The iterative placement results of Chapter k were obtained with the pos- sible placement positions restricted to those used for serial placement. If an iterative placement algorithm were allowed to reposition components to any position on the board, even better results should be attainable. Further comparisons using sophisticated versions of existing placement algorithms will provide important qualitative and quantitative conclusions. 6.2 Channel Routing The channel routing algorithm described in Chapter 5 performs the complete wire routing function. All connections which can be made by this algorithm within the given board area are completely specified with- out conflicts. The results of implementing this basic algorithm and test- ing it on ILLIAC IV design problems are very favorable. The speed of execution for such large problems is the main advantage of the channel routing approach. The major disadvantage is that this algorithm is de- pendent on the availability of unlimited via holes whose positions are not fixed. An implementation of the basic channel routing algorithm is capable of completely wiring large printed circuit boards with wiring densities of 20 to 30 percent. Wiring failures begin to occur on boards 76 requiring densities greater than 30 percent. These results are signifi- cant "because several improvements can be made in the basic algorithm. More sophisticated space assignment and final positioning routines can be implemented. Also a second pass algorithm could be developed to route as many failed connections as possible using more complicated paths than the channel routing algorithm presently considers. The speed and flexi- bility of the basic algorithm will make improvements possible without unreasonable costs in terms of computer time. 77 APPENDIX A The following pages contain the signal net listings of five ILLIAC IV CU hoards. Several simplifications of the original net lists have "been made, including the elimination of all power and ground con- nections and a consolidation of the clock buffer circuitry so that it appears as a single movable package. Also, the labeling of edge con- nector pins has been organized to facilitate distance measurements for placement programs and edge pin wiring for routing programs. The edge connectors should be considered to be divided as shown in Figure 1 with the groups being labeled P001 through P015. Within each group there are exactly sixteen pins which are spaced 50 mils apart and are numbered as shown in Figure 5> so each group can be treated the same as a package. Actually each edge connector group has 32 pins with sixteen appearing on each side. In the signal netlists which follow, no distinction will be made between corresponding edge connector pins on opposite sides of the board. Therefore, one edge connector pin name may appear more than once in the netlist. However, no edge connector pin is used more than once, so each occurrence should be treated as a separate pin. The netlists are listed in columns so that the first entry of the second column follows the final entry of the first column and so forth. Each entry is composed of l) a name where A indicates a package and P indicates a connector pin group, 2) a pin number and 3) a source (s) or load (L) indicator. Each signal net is composed of one source and one or more loads which immediately follow the source. The following rules should be helpful in checking that the data is properly copied. 78 1. Packages are named starting with AOOO sequentially through the highest numbered package. No sequence numbers are skipped. 2. A package name with sequence number N will not appear in a given entry unless all package names with sequence numbers less than N have appeared in previous entries. 3- Edge connector pin groups are named P001 through P015 inclusive, and no sequence number greater than 15 will follow a "P". k. Pin numbers (the second element of each entry) must be between 001 and 016 inclusive. 5. Each netlist must begin with a source (an entry with an S as its third element) and every source (s) must be followed by at least one load (L). 6. Each column after the first page has 50 entries (^9 on first page) . Netlist Highest Numbered Length of Package Netlist ATP07 A100 960 FDQA A092 861 FIRDB A051 hQk IICR1 A120 1233 TCRFLD A135 995 ATP07 79 AOOO 005 s A027 013 L A044 004 s A021 009 L AOOl 008 L A029 oo4 S A042 014 L A021 016 L A002 005 S A027 oi4 L A045 007 s A048 Oil L A003 008 L A030 007 S A042 016 L A019 007 S AOOO 002 S A027 016 L A045 oo4 S AOOO Oil L AOOl Oil L A030 oo4 n A042 001 L AOOO 016 L A002 002 S A027 001 L A020 005 S A024 014 L A003 Oil L A031 007 S A017 Oil L A020 008 L A004 002 S A032 008 L A010 005 S A0l8 009 L A005 001 L A031 oo4 S A007 Oil L A021 014 L A006 002 S A032 009 L A004 007 S A049 013 L A007 001 L A033 007 S A008 012 L A022 007 S A008 013 L A032 Oil L A008 014 L A023 013 L A009 002 S A033 oo4 S A011 001 L AOOO 009 L A003 OlU L A032 012 L A011 Oil L A024 013 L A010 013 L A03U 007 S A046 013 L A018 008 L A011 008 L A032 013 L A006 007 S ao49 Oil 1 A012 002 S A034 oo4 S A025 016 L A050 007 s A013 oi4 L A032 oi4 L A010 009 L A051 Oil L A002 01 4 L A035 007 S A010 oi4 L A052 Oil L A010 Oil L A032 016 L A008 Oil L A050 005 s A011 013 L A035 oo4 S A011 009 L A051 013 L A0l4 002 S A032 001 L A011 016 L A052 013 L A015 001 L A036 007 S A046 Oil L A050 004 S A016 002 S A037 00S L A009 007 S A053 Oil L A017 001 L A036 oo4 S A002 Oil L A054 Oil L A018 013 L A037 009 L A002 016 L A050 002 S A019 002 S A038 007 S A025 014 L A053 013 L AOOl 014 L A037 Oil L A010 008 L A054 013 L A020 013 L A038 oo4 S A008 009 L P003 015 s A021 008 L A037 012 L A011 oi4 L A055 Oil L A022 002 S A039 007 S A047 013 L A055 007 s A023 oi4 L A037 013 L A012 007 S poo4 002 L AOOO Ol4 L A039 oo4 S A013 013 L A055 00S S A020 Oil L A037 oi4 L A002 009 L A050 001 L A021 013 L A040 007 S A025 013 L A050 009 L A024 002 S A037 016 L A008 008 L A020 002 S A017 008 L A040 oo4 S A047 Oil L A017 013 L A025 002 S A037 001 L A014 007 S A010 002 S A007 008 L A04l 007 S A018 012 L A007 013 L A026 007 S A042 00S L A018 014 L A018 002 S A027 008 L A04l oo4 S A021 001 L A015 008 L A026 004 S A042 009 L A021 Oil L A008 002 S A027 009 L A043 007 S A048 013 L A005 008 L A028 007 S A042 Oil L A016 007 S A021 005 s A027 011 L A043 00 4 S A024 016 L A015 Oil L A028 004 S A042 012 L A020 009 L A011 005 s A027 012 L A044 007 S A020 014 L A005 Oil L A029 007 S A042 013 L A018 Oil L A021 002 S 80 A015 013 L A001 005 s P007 003 s A069 Oil L A011 002 S A038 Oil L A062 0.12 L AO68 OOl* s A005 013 L A038 0.16 L A063 0.12 L A069 013 L pool* 015 S A001 007 S P007 ooi* S A070 005 S A056 009 L A036 Oil L A06U 001 L A071 Oil L A056 01U L A036 O.I6 L P005 Oil S A070 ooi* S A056 00U S A023 002 S A065 002 L A071 013 L A057 011 L A030 Oil L A0l*2 002 S ■, A072 005 s A058 Oil L A030 016 L AOl+6 016 L A073 Oil L A056 002 S A023 ooi* S AOl+6 ooi* s A072 OOU s A057 013 L A029 Oil L P010 Oil L A073 013 L A058 013 L A029 016 L A0l*2 005 S pool* 015 s AO56 007 S P009 016 S A0U6 008 L A067 012 L A059 011 L A0l*8 009 L A0l*6 005 S AO67 Oil* l A060 Oil L A0U8 Oil* L P010 016 L A069 012 L A056 005 S AOU7 009 L A032 002 S A069 Oil* L A059 013 L AOU7 Oil* L A0l*7 016 L A071 012 L A060 013 L A0l*6 009 L A0l*7 ooi* S A071 Oil* l A06l 001 S A0U6 01U L P01.1 003 L A073 012 L A056 008 L A0l*9 009 L A032 005 s A073 Oil* l A06l 002 S A0U9 Oil* L AOl+7 008 L A071+ 013 s A050 008 L P011 006 S AOl+7 005 S P003 003 L A06.1 003 S A0U8 012 L P010 015 L A051 007 s A056 013 L AOU7 012 L A037 002 S POOl* OOl* L A06l ooi* S A0l*6 012 L A0l*8 016 L A051 008 S A050 0.13 L A0l*9 0.12 L A0l*8 OOl* S AO7I* Oil L A007 005 S P013 003 S P010 Oil* L A075 013 s A0U5 Oil L A028 Oil L A037 005 s A003 OOl* l A0U5 016 L A028 016 L A0l*8 008 L A053 007 s A007 007 S P009 012 S A0l*8 005 s AO66 009 L AOl*l+ oil L A026 Oil L P011 OOl* l pool* 007 L AOl*l* 016 L A026 016 L A027 002 S A053 008 S A003 005 S A023 0.12 L A0l*9 016 L A075 Oil L AOl+3 Oil L A00.1 009 L A0l*9 ooi* s A075 016 S A0l*3 016 L A017 009 L P011 007 L P002 015 L A003 007 S P013 001* S A027 005 s A053 002 S AOl+1 Oil L A033 Oil L AOl+9 008 L AO66 016 L AOl*l 016 L A033 012 L A0l*9 005 s P003 015 L A013 002 S P009 007 S P0.11 003 L A053 001 S A035 011 L A031 Oil L A018 007 S A075 Oil* L A035 016 L A031 016 L P009 016 L A076 013 s A013 ooi* S A013 012 L A018 005 s P003 007 L AO3I* Oil L A003 009 L P009 Oil L A051* 007 s AO3I* 016 L A007 009 L A008 005 s A068 009 L A017 005 S A015 005 S P008 012 L P003 016 L AOl*0 Oil L POOS Oil L AO66 005 s A051+ 008 s AOl*0 016 L A015 007 S AO67 Oil L A076 0.11 L A017 007 S P008 0.16 L AO06 ooi* s A076 016 S A039 Oil L A005 007 S A067 013 L P002 Oil L A039 016 L P009 015 L AO68 005 S A05l* 002 S 81 A068 016 L AO66 001 L POlU 003 s A091 012 L P003 012 L A080 002 S AO89 Oil L A092 012 L A05 1 + 001 S A08l 012 L POlU 00U S A093 012 L A076 OlU L P009 015 L A090 Oil L A09U 012 L A07U 016 S A082 007 S POlU 008 S A095 012 L P002 012 L AO68 008 L A091 Oil L POlU 016 S A051 002 S A082 005 s P013 015 s AO88 OlU L A070 016 L AO83 OlU L A092 Oil 1 AO89 OlU L A051 001 S P011 002 L POlU 007 S A090 OlU L AO7U OlU L A082 00U S A093 Oil L A091 OlU 1 A077 013 s AO68 001 L POlU 003 s A092 OlU L P003 003 L A082 002 S A09U Oil L A093 OlU L A052 007 S A083 012 L P013 016 S A09U OlU L A072 009 L P007 OOU L A095 Oil L A095 OlU L A052 008 S A08U 007 S poio 007 S P009 00U S A077 Oil L A070 008 L A080 009 L AO78 009 L A077 016 S A08U 005 S P013 Oil S A06U Oil L P002 016 L AO85 OlU L AO88 013 L A079 012 L A052 002 S P007 007 L poio 003 s A065 Oil L A072 016 L A08U 00U S A080 OlU L poo8 003 s A052 001 S A070 001 L P013 015 s A062 009 L A077 OlU L A08U 002 S AO89 013 L A062 OlU L P005 015 s A085 012 L POIO 00U S A063 009 L A070 Oil L P007 008 L A082 009 L A063 OlU L A072 Oil L A086 007 S P013 012 S P008 008 S P006 002 S A072 008 L A090 013 L AO78 OlU L AO66 Oil L AO-36 005 s poio 003 s A06U 016 L AO68 Oil L AO87 OlU L A082 OlU L A079 OlU L A062 007 S P007 Oil L P013 016 S A065 OlU L A051 012 L AO86 00U S A091 013 L P007 012 S A078 005 s A072 001 L POIO 008 S A062 008 L A053 012 L AO86 002 S A08U 009 L P008 007 S A079 005 S AO87 012 L POlU 00U S A080 008 L A053 OlU L P007 008 L A092 013 L A078 013 L A06U 005 s POOU 016 S POIO Oil S P005 012 S A05U 012 L AO66 007 L A08U OlU L A080 013 L AO65 005 S AO68 007 L P013 007 s A079 013 L A05U OlU L A070 007 L A093 013 L P007 016 S A062 002 S A072 007 L poio 007 S A082 008 L A0S1 OlU L P008 00U S AO86 009 L A06U OlU L A063 007 S AO87 Oil L P013 Oil S P005 003 s A052 012 L AO87 013 L A09U 013 L A082 013 L A063 002 S AO85 Oil L POIO 012 S A065 016 L A052 OlU L A085 013 L AO86 OlU L poio 015 s A080 007 S AO83 Oil L P013 008 S A08U 008 L A066 008 L A083 013 L A095 013 L P007 015 s A080 005 S A08l Oil L POlU Oil S A08U 013 L A08l OlU L A08l 013 L AO88 012 L A062 016 L P011 008 L poiU 007 S AO89 012 L P007 015 s A080 00U S AO88 Oil L A090 012 L AO86 008 L 82 A063 oo8 L P008 007 S P011 016 s A009 Oll+ L P005 007 s AO78 001 L A039 008 L A090 007 S A086 013 L A06k 013 L AOl*0 013 L A03 1 * 009 L AO63 016 L A079 001 L AOll* 009. L A035 009 L P009 003 S A065 013 L P0.12 007 S A009 008 L AO78 008 L POlU 012 S A036 013 L A091 005 S P006 Oil S AO88 009 L AO38 008 L A031 Oil* L A079 011 L AO89 009 L A016 0.12 L A033 Oil* L P007 Oil S A090 009 L P012 003 S A012 01.1 L A06k 009 L A091 009 L A036 008 L A012 Oil* L P006 007 S A092 009 L A038 0.13 L -A091 007 S A065 009 L A093 009 L A0l6 009 L A031 009 L P007 003 S AO9I+ 009 L P012 0.15 S A033 009 L A062 Oil L A095 009 L A029 013 L A012 008 L P008 003 S P012 015 S A030 008 L A092 005 s A088 008 L AO^l* 013 L A019 012 L A039 Oil* l A078 016 L A0l*5 008 L P011 015 S AOl*0 Oil* L P005 011 S AOOl* 012 L A029 008 L AOll* 0.1.1 L A089 008 L P011 Oil S A030 0.13 L AOll* Oil* L A079 016 L AOl+U 008 L A019 009 L A092 007 S P007 012 S A0U5 013 L P012 0.11 S A039 009 L A090 008 L AOOU 009 L A026 013 L AOl*0 009 L A06k 012 L P012 0.11 S A028 008 L AOll* 008 L P005 00l* S A0l*l 013 L A022 012 L A093 005 S A091 008 L A0l*3 008 L P011 001* S A036 Oil* l A065 012 L A006 012 L A026 008 L AO38 Oil* l POll* Oil S P011 012 S A028 013 L A016 0.11 L A092 008 L AOlj-1 008 L A022 009 L A0.16 Oil* l P008 ooi* S A0U3 013 L AO88 005 S A093 007 S A093 008 L A006 009 L AOl+U 01** L A036 009 L A062 013 L P012 012 S A0U5 OlU L AO38 009 L P007 0.16 S A03U 0.13 L AOOl* Oil L A016 008 L A091* 008 L A035 008 L AOOl* Oil* L A091+ 005 S AO63 011 L A009 012 L AO88 007 S A029 Oil* l P005 003 S P011 015 s AOl*l* 009 L A030 Oil* l A095 008 L A03U 008 L A0l*5 009 L A019 0.11 L A063 013 L A035 013 L AOOl* 008 L A019 Oil* l P008 015 S A009 009 L A089 005 S A091* 007 S A078 Oil L P011 007 S AOUl Oil* L A029 009 L P006 015 S A031 013 L A0U3 OlU L A030 009 L A079 008 L A033 008 L A006 Oil L A019 008 L P007 007 S A012 012 L A006 Oil* L A095 005 s A06k 007 L P0.11 0.11 S A089 007 S A026 Oil* L P006 003 S A031 008 L AOUl 009 L A028 Oil* L A065 007 L A033 0.13 L AOi+3 009 L A022 0.11 L P008 Oil S A012 009 L A006 008 L A022 Oil* l AO78 012 L P0.12 016 S A090 005 s A095 007 S A06h 008 L A039 013 L A03U oil* L A026 009 L A079 009 L AOl*0 008 L A035 Oil* L A028 009 L A065 008 L AOll* 012 L A009 Oil L A022 008 L 83 A067 005 s A097 016 s A075 006 L A090 001 L poo6 016 L pooU Oil L A075 001 S A091 001 L AO67 00U S ao6o 002 S A075 003 L A092 001 L P006 015 L A068 01U L A076 007 S A093 001 L AO69 005 S ao6o 001 S AO76 006 L A09U 001 L P006 012 L A097 01U L AO76 001 S A095 001 L A069 00U S A098 013 S AO76 003 L poo 5 008 S P006 Oil L P003 016 L A096 007 S A06U 002 L A071 005 S A057 007 S AO96 006 L A065 001 L poo6 008 L A070 012 L A096 001 S POOU 012 S A071 00U S A057 008 S AO96 003 L A050 Oil L poo6 007 L A098 Oil L A098 007 S A050 016 L A073 005 S A098 016 S A09S 006 L A056 Oil L P006 00U L P003 Oil L A098 001 S A056 016 L AO73 00U S A057 002 S AO98 003 L poo6 006 L A070 OlU L A097 007 S A081 00U S A057 001 S A097 006 L A059 012 L A098 OlU L A097 001 S AO81 005 S A099 013 S A097 003 L A059 01U L P005 016 L A099 007 S A083 00U S A058 007 S A099 006 L ao6o 012 L A072 012 L A099 001 S A083 005 S A058 008 S A099 003 L A060 01U L A099 Oil L P013 00U S A085 00U S A099 016 b A080 Oil L A057 012 L P005 007 L A088 016 L A085 005 S A058 002 S P013 012 S A057 01U L A072 oiU L AOSO 016 L A087 00U S A058 001 S A0S9 016 L A058 012 L A099 OlU L POlU 008 S A087 005 S P005 002 S A082 Oil L A058 01U L ao66 013 L A090 016 L A096 013 S AO68 013 L P013 007 S P005 015 L A070 013 L A082 016 L A059 007 S A072 013 L A091 016 L AO66 012 L POOU 003 S POlU 012 S A059 008 S A100 016 L AOSU Oil L A096 Oil L pooU 007 S A092 016 L A096 016 S A100 01U L P013 008 S P006 003 L A100 002 S A08U 016 L A059 002 S A06l 016 L A093 016 L AO66 OlU L AO7U 007 S POlU 015 s A059 001 S AO7U 006 L A036 Oil L A096 01U L A07U 001 S A09U 016 L A097 013 S AO7U 003 L P013 003 s pooU 008 L A077 007 S AO86 016 L A060 007 S A077 006 L A095 016 L A068 012 L A077 001 S P015 003 s A060 008 S A077 003 L AO88 001 L A097 Oil L A075 007 S AO89 001 L Qk FDQA P005 ooi+ S A020 03.1+ L AOl+0 0.12 1 A002 Oil L AOOO 012 L A021 Oll+ L AOUO 013 L A010 Oil L A001 012 L A022 Oll+ L AOl+1 012 L A036 005 s A002 012 L A023 Oll+ L AOl+1 013. L A002 013 L A003 012 L P006 ooi+ S A033 003 s A0.10 013 L A001+ 012 L A02U 012 L A0H2 012 L AOl+0 007 S A005 012 L A025 012 L AOl+2 013 L A018 Oil L A006 012 L A026 012 L A033 001+ S A026 0.11 L A007 012 L A027 012 L A035 012 L AOUO 005 s P005 003 S A028 012 L A035 013 L A018 0.13 L AOOO OlU L A029 012 L A033 005 S A026 013 L A001 OlU L A030 012 L A0U3 012 L A036 001+ S A002 OlU L A031 012 L A0U3 0.13 L A003 Oil L A003 OlU L P005 016 S A033 006 S A011 Oil L AOOlf OlU L A021+ 011+ L A038 012 1 A036 002 S A005 OlU L A025 QXk L AO38 013 L A003 013 L A006 OlU L A026 011+ L A01+1+ Oll+ L A011 013 L A007 OlU L A027 Oll+ L A033 007 S AOl+0 001+ S P005 015 S A028 01k L A036 012 L A0.19 Oil L A008 012 L A029 Oll+ L A036 013 L A027 0.11 L A009 012 L A030 Oll+ L A037 012 L AOl+0 002 S A010 012 L A031 011+ L A037 013 L A019 0.13 L A011 012 L pooU 003 s A033 008 S A027 013 L A012 012 L A032 016 L AOl+5 012 L A037 007 S A013 012 L pooi+ 007 s AOl+5 0.13 L A001+ Oil L AOlU 012 L A032 Oll+ L A035 007 S A012 Oil L A015 012 L A032 002 S AOOO Oil L A037 005 s P005 007 S A033 016 L A008 Oil L A001+ 013 L A008 OlU L A031+ 001 S A035 005 s A012 013 L A009 OlU L A035 Oil L AOOO 013 L AOl+1 007 S A010 OlU L A035 0.11+ L A008 013 L A020 Oil L A011 OlU L A036 009 L A039 007 S A028 Oil L A012 0ll+ L A036 011+ L A0.16 Oil L AOl+1 005 s A013 OlU L A037 Oil L A021+ Oil L A020 013 L AOll+ Oll+ L A037 011+ L A039 005 s A028 013 L A015 Oll+ L AO38 009 L A016 013 L A037 001+ S P006 007 S A038 Oll+ L A021+ 013 L A005 Oil L A016 012 L A031+ 002 S A035 001+ S A013 Oil L A017 012 L A039 Oil L A001 Oil L A037 002 S A018 012 L A039 Oll+ L A009 Oil L A005 013 L A019 012 L AOl+0 009 L A035 002 S A013 013 L A020 012 L AOUO Oll+ L A00.1 013 L AOl+1 00l+ S A021 012 L AOUl Oil L A009 013 L A021 Oil L A022 012 L AOl+1 Oll+ L A039 001+ S A029 Oil L A023 012 L AOl+2 009 L A0.17 Oil L AOl+1 002 S P006 008 S AOl+2 Oll+ L A025 Oil 1 A02.1 013 L A016 OlU L A033 001 S A039 002 S A029 013 L A017 OlU L A039 012 L A017 013 L A038 007 S A018 OlU L A039 013 L A025 013 L A006 Oil L A019 0ll+ L A033 002 S A036 007 S . A011+ Oil L 85 A038 005 s A055 013 L AO66 OlU L A077 016 s A006 013 1 P008 015 s AO67 009 L A0U8 OlU L AOlU 013 L AO3U 0.13 L AO67 OlU L A052 OlU L A0U2 007 S AO3U 009 S A0U7 001 S A072 00U s A022 Oil L A0U5 009 L AO68 012 L AO78 Oil L A030 Oil L AOU5 OlU L A069 012 L A078 013 s A0U2 005 S AO3U 008 S A070 012 L A0U9 012 L A022 013 L AOU3 009 L A071 012 L A053 012 L A030 013 L A0U3 OlU L A0U7 002 S A072 001 S A038 00U S A03U 007 S A068 009 L AO78 OlU L A007 Oil L AOUU 016 L AO68 OlU L AO78 016 S A015 Oil L A0U6 008 S A069 009 L A0U9 OlU L A038 002 S A056 012 L A069 OlU L A053 OlU L A007 013 L A057 012 L A070 009 L A073 008 S A015 013 L A058 012 L A070 OlU L A079 Oil L A0U2 00U S A059 012 L A071 009 L A079 013 s A023 Oil L A0U6 007 S A071 OlU L A050 012 L A031 Oil L A056 009 L P001 Oil S A05U 012 L A0U2 002 S A056 OlU L A072 OlU L A073 005 s A023 013 L A057 009 L A073 OlU L A079 OlU L A031 013 L A057 OlU L P002 007 S A079 016 S AOUU 00U S A058 009 L A07U 012 L A075 008 L A0U6 Oil L A058 OlU L P002 Oil S A050 OlU L AOU7 Oil L A059 009 L A07U 008 L A05U OlU L AOUU 002 S A059 OlU L A07U 005 s A075 007 s A0U6 013 L A0U6 001 S A0U3 Oil L AOUU 009 L AOU7 013 L A060 012 L A0U3 016 L A073 00U S AOU3 007 S A06l 012 L A0U5 Oil L A080 Oil L A0U8 Oil L A062 012 L A0U5 016 L aoSo 013 s A0U9 Oil L A063 012 L A075 00U S A051 012 L AOU3 005 S A0U6 002 S P007 OOU L A055 012 L A0U8 013 L A060 009 L A076 007 s A073 001 S AOU9 013 L A060 OlU L P007 007 L A080 OlU L A0U3 OOU S A06l 009 L A076 00U S A080 016 S A050 Oil L A06l OlU L P007 003 L A051 OlU L A051 Oil L A062 009 L aoUU 007 S A055 OlU L AOi+3 002 S A062 OlU L AOUU 001 L A081 005 s A050 013 L A063 009 L AO7U 002 S A056 008 L A051 013 L A063 OlU L AOUU 008 L A056 016 L A0U5 007 S A0U7 008 S A07U 00U S A06U 008 L A052 Oil L A06U 012 L A077 Oil L A06U 016 L A053 011 L A065 012 L A077 013 s A082 005 s AOl+5 005 S AO66 012 L A0U6 012 L A057 008 L A052 013 L A067 012 L A0U6 OlU L A057 016 L A053 013 L A0U7 007 s A0U8 012 L A065 008 L A0U5 00U S A06U 009 L A052 012 L A065 016 L AO5U Oil L A06U OlU L AOU7 012 L A083 005 s A055 Oil L • A065 009 L AOU7 OlU L A058 008 L AOU5 002 S A065 OlU L A072 005 s A058 016 L AO5U 013 L AO66 009 L A077 OlU L AO66 008 L 86 A066 016 L A065 005 s AO68 007 S A071 00^ S A08^ 005 S P002 00U L P013 Oil L P0.15 Oil L A059 008 L A065 007 S A068 00U S A071 002 S A059 016 L P002 007 L P013 OO^- L P015 007 L AO67 008 L A065 00U S AO68 002 S A089 005 S AO67 016 L P002 003 L P013 003 L A056 Oil L AO85 005 S A065 002 S A06l 005 S A056 013 L A060 008 L POOl 015 L POlU 00^ L A06k Oil L A060 016 L A058 005 S A06l 007 S A06k 013 L AO68 008 L P003 00U L P0.1U 008 L A089 00U S AO68 016 L A058 007 S A06.1 001+ S A057 Oil L AO86 005 S P003 007 L P013 016 L A057 013 L AO61 008 L A058 00U S A06l 002 S A065 Oil L AO61 016 L P003 003 L P013 012 L A065 013 L AO69 008 L A058 002 S A069 005 S A090 005 S AO69 016 L P002 015 L POl^ 003 L A058 Oil L AO87 005 S AO66 005 S A069 007 S A058 013 L AO62 008 L P003 007 L POlU 007 L AO66 Oil L A062 016 L AO66 007 S A069 00U S AO66 013 L A070 008 L P003 008 L P013 015 L A090 00S s AO70 016 L AO66 ool+ S A069 002 S A059 Oil L A088 005 S P003 003 L PO.13 0.15 L A059 013 L AO63 008 L AO66 002 S A062 005 S A067 Oil L AO63 016 L P002 OI6 L POlU 015 L A067 013 L A071 008 L A059 005 S A062 007 S A091 005 S AO71 016 L POO 3 015 L P015 003 L A060 Oil L AO56 005 S A059 007 S A062 001+ S A060 013 L pool 008 L P003 016 L POlU 012 L AO68 Oil L AO56 007 S A059 00U S A062 002 S AO68 013 L POOl Oil L P003 015 L P011+ Oil L A091 001+ S A056 ool+ S A059 002 S A070 005 s A06l Oil L pool 007 L P003 012 L POlU 016 L A06l 013 L A056 002 S AO67 005 S A070 007 S A069 Oil L pool 003 L P002 015 L P015 003 L A069 013 L A06k 005 S AO67 007 S A070 00U S A092 005 S pool 007 L P002 012 L POlU 015 L A062 Oil L A06^ 007 S AO67 OOik S A070 002 S A062 013 L POOl 012 L P003 Oil L POlU Oil L A070 Oil L A06i+ 00U S A067 002 S AO63 005 S A070 013 L POOl 003 L P002 Oil L P015 Oil L A092 00J+ S A06k 002 S A060 005 S A063 007 S A063 Oil L POOl 001+ L P013 008 L P015 015 L A063 013 L A057 005 S A060 007 S A063 00U S A071 Oil L P002 003 L P013 Oil L P015 008 L A071 013 L A057 007 S A060 00U S A063 002 S AOOO 007 S P002 008 L P013 007 L P015 00l+ L A08l 002 L A057 OOU S A060 002 S A071 005 s AOOO 002 S POOl 016 L P013 003 L P015 012 L A082 007 L A057 002 S AO68 005 S A07.1 007 S A008 007 s POOl 015 L po.13 007 L P015 016 L AO83 007 L 87 A008 002 s A019 007 s A022 002 s A08U 008 L A08i+ 007 L A085 01)+ L A091 016 L A072 012 L A016 007 S A019 002 S A030 007 S A052 007 S AO85 007 L AO86 OlU L A092 009 L AO85 008 L A016 002 S A027 007 S A030 002 S AO86 008 L AO86 007 L AO87 Olt L A092 016 L AO87 008 L A02U 007 S A027 002 S A007 007 S AO88 008 L AO87 007 L A088 01U L AO89 012 L AOi+8 001 S A024 002 S A001+ 007 S AO77 002 S A075 013 L AO88 007 L AO81 001 L AO89 OlU L AOl+8 002 S A001 007 S AOOU 002 S A015 007 S A08l Oil L A08l 009 L A082 001 L A090 012 L A082 Oil L A001 002 S A012 007 S A015 002 S AO83 Oil L A082 009 L AO83 001 L A090 01*+ L A081+ Oil L A009 007 S A012 002 S A023 007 S A072 013 L AO83 009 L AOSU 001 L A091 012 L A052 002 S A009 002 S A020 007 S A023 002 S A0S5 Oil L A08U 009 L AO85 001 L A091 OlU L AO86 Oil L A017 007 S A020 002 S A031 007 S AO87 Oil L AO85 009 L AO86 001 L A092 012 L AO88 Oil L A017 002 S A028 007 S A031 002 S A0U9 008 S A086 009 L AO87 001 L A092 OlU L AO76 Oil L A025 007 S A028 002 S P006 016 S A0U9 007 S AO87 009 L A088 001 L A035 008 L A08l 013 L A025 002 S A005 007 S A039 003 L A082 013 L AO88 009 L AO89 008 L P005 008 S AO83 013 L A002 007 S A005 002 S A035 001 L A08U 013 L A08l 012 L AO89 001 L A039 001 L A072 016 L A002 002 S A013 007 S P006 012 S A053 007 S A082 012 L A090 008 L A036 Oil L AO85 013 L A010 007 S A013 002 S AOl+0 Oil L AO86 013 L AO83 012 L A090 001 L P005 Oil S AO87 013 L A010 002 S A021 007 S A036 001 L A088 013 L A08^ 012 L A091 008 L AOUO 001 L A0i+9 001 S A018 007 S A021 002 S P006 015 S A075 001 L AO85 012 L A091 001 L A037 008 L AO76 008 L A018 002 S A029 007 S AOUl 008 L AOi+9 002 S AO86 012 L A092 008 L P005 012 S A08l 016 L A026 007 S A029 002 S A037 001 L A082 016 L AO87 012 L A092 001 L A04l 001 L AO83 016 L A026 002 S A006 007 S P006 Oil S A08U 016 L A0S8 012 L AO89 009 L A038 Oil L A073 009 L A003 007 S A006 002 S A042 Oil L A053 002 S A08l OlU L AO89 016 L P006 003 S AO85 016 L A003 002 S AOlk 007 S A038 001 L AO86 016 L A082 OlU L A090 009 L A0i+2 001 L AO87 016 L A011 007 S AOlU 002 S AOl+8 007 S AO88 016 L A0S3 OlU L A090 016 L A08l 008 L A050 008 S A011 002 S A022 007 S A082 008 L AO76 001 L A081+ Oll+ L A091 009 L AO83 008 L A050 007 S 88 A08l AO82 AO83 A08U AO73 A05 i + A035 AO86 AO87 AO88 A050 A075 AO76 A050 A090 A073 A05U A091 A092 A051 AO76 AO76 A051 AO89 A090 A073 A055 A091 A092 A051 AO75 AO76 AO76 A051 A090 AO7I+ A055 A091 A092 AO77 AO77 AO77 AO77 AO78 AO78 AO78 AO78 A079 002 L 002 L 002 L 002 L 012 L 007 S 002 L 002 L 002 L 002 L 001 s 014- L 016 L 002 S 007 L 007 L 013 L 002 S 007 L 007 L 008 S 0.12 L 013 L 007 S Oil L Oil L 016 L 007 S Oil L Oil L 001 S 016 L 009 L OlU L 002 S 013 013 Oll+ 002 013 013 007 006 001 s 003 L 007 S 006 L 001 S 003 L 007 S L L L S L L S L A079 A079 A079 A080 A080 A080 A080 P008 A03U P008 A03U 006 L 001 S 003 L 007 S 006 L 001 S 003 L Oil S Oil L 007 S OlU L FIRDB pooU 003 s A012 013 L A011 Oil L AO^if 007 L A000 016 L A013 00*+ S A016 005 S A0U5 008 L pooU 007 S AO.1.1 012 L A017 007 L A0^5 013 L AOOO OlU L P011 Oil S A018 007 L A028 00^ S AOOO 002 S AOlU 009 L A019 007 L P013 007 L A001 OI6 L AOl^ 008 S A016 007 S A006 001 S A002 008 S A006 012 L A020 007 L A028 Oll+ L A003 009 L POll 007 S A021 007 L A027 008 L A003 016 L AOlU 012 L A016 008 S AOl+6 007 L AOOI4 001 L A011+ 005 S A022 007 L A006 002 S AOOif 009 L A006 OlU L A023 007 L A028 Oil L A005 009 L POll 003 S A02^ 007 L A016 001+ S A005 OlU L AOlU 013 L A025 007 L A0k6 008 L A003 00^ S AOl^ OOU S A026 007 L A032 008 L A006 Oil 1 A007 012 L A016 009 S A033 008 L A007 Oil L P010 015 S poiU 007 L A038 008 L A003 005 S AOlU 016 L aoo6 007 S AOUO 008 L A006 013 L AOlU 001 S aoi6 Oil L A023 009 L A007 013 L A007 Ollj- L A027 007 L A025 009 L A005 001+ S P009 015 S A028 005 S A026 009 L A008 Oil L A015 009 L A029 007 1 A016 001 S A009 Oil L A015 008 S A030 007 L A027 009 L A005 005 S A008 012 L A031 007 L A029 008 L A008 013 L P009 016 S A032 007 L A030 008 L A009 013 L A015 012 L A033 007 L A031 008 L AOOU 00i+ S A015 005 S A028 007 S A017 009 L A010 Oil L A008 OlU L A017 008 L A016 002 S AOOU 005 S P009 Oil S aoi8 008 L A018 009 L A010 013 L A015 013 L A019 008 L A019 009 L A001 001 S A015 001+ S A020 008 L A020 009 L A003 012 L A009 012 L A021 008 L A021 009 L A003 013 L P009 012 S A028 001 S A03^ 008 L A005 012 L A015 016 L A03U 007 L A035 008 L A005 013 L A015 001 S A035 007 L A036 008 L A001 002 S A009 011+ L A036 007 L A037 008 L A001+ 012 L P007 003 S A037 007 L A016 016 S AOOU 013 L A002 016 L A038 007 L A039 008 L P007 007 s A002 002 S A039 007 L A022 009 L A002 Oil L A010 012 L aoUo 007 L A02U 009 L A011 002 S A002 005 S A028 008 S A042 008 L A003 008 L A013 013 L A022 008 L A0i+3 008 L AOOU Oil L A012 Oil L A023 008 L AOUU 008 L A005 008 L A012 00U S A02U 008 L AOi+5 009 L A012 007 S A013 012 L A025 008 L A0U5 OI6 L A003 001 L A012 012 L A026 008 L A007 008 S AOOU OlU L P006 015 S A028 002 S AO^l 008 L A005 001 L A012 008 L AO^l 007 L P006 Oil L P007 00U S P009 003 S A0l42 007 L A007 007 S A002 012 L A011 008 L A028 009 S A016 OlU L P006 016 S P008 015 S A0^3 007 L A0U7 005 S 90 A027 Oil L A030 Oil L A04l 012 L P007 004 L A029 009 L A031 Oil L A042 012 L A009 008 s A0U7 007 S A032 Oil L A0U9 002 S A050 014 L A046 009 L A033 Oil L A038 012 L A009 007 s A030 009 L A017 012 L A039 0.12 L A050 0.11 L A031 009 L A048 008 S A040 012 L A051 005 s A032 009 L A018 012 L A044 Oil L A029 0.14 L A033 009 L A019 012 L A0U5 001 L A030 014 L A017 Oil L A020 012 L A0U9 009 S A032 014 L A0U7 001 S A021 012 L P009 004 L A051 007 s A038 009 L A04l Oil L A008 001 S A027 016 L A039 009 L A042 Oil L AOl+9 014 L A046 oi4 l A040 009 L A048 009 S A008 002 S A031 014 L A023 Oil L A038 Oil L A0U9 Oil L A033 014 L A02U 0.11 L A039 Oil L A050 005 S A0.17 016 L A025 011 L A040 Oil L A046 013 L A020 016 L A026 Oil L A022 012 L A029 013 L A034 014 L A0U7 008 S A023 012 L A017 014 L A036 0.14 L A018 Oil L A024 012 L A018 014 L A051 001 s A019 Oil L A025 012 L A019 014 L A018 016 L A020 Oil L A026 012 L A020 014 L A019 016 L A021 Oil L A008 008 S A021 014 L A021 016 L A034 009 L P009 016 L A050 007 S A035 014 L A035 009 L AOOS 007 S A027 014 L A037 0.14 L A036 009 L A048 Oil L A030 013 L A051 008 S A037 009 L A049 005 S A031 013 L A038 014 L AOU7 002 S A027 013 L A032 013 L A039 014 L A04l 009 L A030 0.12 L A033 013 L A040 014 L A042 009 L A031 012 L A050 001 S A022 016 L A0U3 009 L A032 012 L A023 014 L A026 016 L ao44 009 L A033 0.12 L A04l 013 L A04.1 014 L AOl+7 009 S A017 013 L A042 013 L A042 014 L A022 Oil L A0U9 007 S A050 008 S A051 002 S AOl+7 004 S A046 012 L A034 013 L A023 016 L P011 008 L A029 012 L A035 013 L A024 016 L A007 001 S A022 013 L A036 013 L A025 016 L AOl+7 Ol4 L A023 013 L A037 0.13 L A051 004 S A007 002 S A024 013 L A043 0.12 L P006 007 L A047 Oil L A025 0.13 L A044 012 L A009 001 S AOl+8 005 S A026 013 L A045 Oil L A051 014 L A046 Oil L A049 001 S AO^-5 014 L A009 002 S A029 011 L A018 013 L A050 009 S A051 Oil L A034 Oil L A019 013 L A038 0.13 L A048 004 S A035 011 L A020 013 L A039 013 L A017 001 L A036 Oil L A021 013 L ao4o 013 L A019 001 L A037 011 L A034 012 L A022 014 L A020 001 L A0U3 Oil L A035 012 L A02^ 014 L A036 016 L A0U5 012 L A036 012 L A025 014 L A037 016 L ao48 007 S A037 012 L A026 014 L A039 016 L A027 012 L A049 008 S A050 oo4 s A040 016 L 91 A0U8 A027 A0k6 A029 A030 A031 A032 A033 AOi+8 A018 A021 A03U A035 AO38 AOi+8 P010 AOIO AOl+8 P008 AOll P006 A012 P008 AOll A037 P015 A036 POOl A031 POlO A030 P012 A033 P009 A032 POlO A029 P013 AOUO P012 A0^2 P002 AOl+1 P006 A038 P013 AOk6 P013 A039 P013 001 001 016 016 016 016 0.16 016 002 001 L 001 L 016 L 016 L 016 016 007 007 OlU 016 009 01.1 009 007 001 002 00*1 002 008 002 016 002 Oil 002 007 002 00*+ 002 003 002 007 002 016 002 012 002 015 002 Oil 002 1 11 il| L S L S L S L S L S L S L S L S L S L S L S L S L S L S L S L S L S L S L A035 P003 A03^ P003 A013 P002 AOl+3 A013 AOi+U A013 AOl+5 POOl A022 P011 A021+ P009 A025 P008 A026 P007 A023 POlO A021 P004 A020 P005 A027 P015 A019 P006 A018 P007 A017 P008 002 S 003 L 002 S 015 L 001 S 015 L 00^ S 016 00^ OlU 002 007 002 OOU 002 015 002 008 002 003 002 003 002 00U 002 Oil 002 005 002 015 002 008 002 003 L S L S L S L S L S L S L S L S L S L S L S L S L S L 92 IICRI pooU 015 s A021 OlU L A005 01^ L A038 016 L AOOO 013 L P013 003 s A006 Oll+ L AO^ll 009 L POO** Oil S A022 008 L A007 01U L AOUl 016 L A001 013 L A023 008 L A028 002 S A0U3 009 L P002 007 S P013 00^ S A008 0.1U L AOl+3 016 L A002 013 L A022 OlU L A009 01U L A037 009 L P002 Oil S A023 oii+ L A029 01^ L A037 016 L A003 013 L P013 oi6 S A030 Oll+ L P009 016 S' P001 003 s A02U 008 L A010 01U L A03 1 *- 008 L AOOU 013 L A011 008 L POOU 003 S A038 007 S P001 00^ S A025 007 S A031 016 L AOl+5 Oil L A005 013 L A015 009 L POOU 007 S A0k6 Oil L POOU Oil S A015 016 L A031 oaA L A038 005 s A006 013 L A017 009 L A031 002 S A0U5 013 L P003 Oil S A017 oi6 L A032 016 L A0k6 013 L A007 013 L A019 009 L POOU 015 S A038 00U S PO05 015 s A019 016 L A025 Oil L AOl+7 Oil L A008 013 L A021 009 L A032 001 S A0U8 Oil L P005 012 S A021 oi6 L A033 012 L A038 002 S A009 013 L A025 008 S A033 013 L AOl+7 013 L P005 007 s A023 009 L A03^t- 012 L A0U8 O.I3 L A010 013 L A023 016 L A032 002 S AOi+1 00U S P013 012 S A026 009 L A035 012 L A0if9 Oil L A011 013 L A013 Oil L A035 013 L A050 Oil L POlU 008 S A011 009 L A032 003 S AOUl 002 S A012 01** L P005 008 S A036 012 L A0U9 013 L A013 012 L A027 013 L A036 013 L A050 013 L P015 Oil S A027 001 S A037 012 L AOUl 007 S AOlU 008 L AOlU 009 L A037 013 L A051 Oil L A015 008 L AOlU 016 L A032 00l+ S A052 Oil L P015 007 s A016 009 L AO38 012 L AOUl 005 S AOlU OlU L A016 016 L AO38 013 L A051 013 L A015 Oik L A018 009 L A032 005 S A052 013 L POlU 003 s A018 016 L A039 012 L AOl+3 OOU S A016 008 L A020 009 L A039 013 L A053 Oil L A017 008 L A020 016 L AOUO 012 L A05^ Oil L POlit 003 s A027 002 S AO^O 0.13 L AOl+3 002 S A016 OlU L A022 009 L A032 006 S A053 013 L A017 OlU L A022 016 L AOUl 012 L A05U 013 L P013 015 S A012 009 L AOUl 013 L A0U3 007 S A018 008 L A012 016 L A032 007 S A055 Oil L A019 008 L A02^ 009 L A0U2 012 L A056 Oil L P013 015 S P007 012 S A0^2 013 L AOl+3 005 S A018 Oik L A028 013 L A032 008 S A055 013 L A019 OlU L A028 001 S A0U3 012 L A056 013 L poi^ 007 s AOOO oiU L A0U3 013 L A037 007 S A020 008 L A00.1 OlU L P008 003 S A057 Oil L A021 008 L A002 oxU L AO^-U 016 L A058 Oil L P013 012 S A003 OlU L AOkk 001 S A037 005 s A020 OlU L AOO^ 01^ L A038 009 L A057 013 L 93 A058 013 L P010 008 s A063 Oil L AO66 OlU L A03T ooU s A063 013 L AOUU 005 s A067 OlU L A059 Oil L aoUU 00U S A0U2 009 L AO68 OlU L A060 Oil L AOUO 009 L A0U2 016 1 A069 OlU L A03T 002 S AOUO 016 L A033 009 L A070 OlU L A059 013 L A035 009 L A033 016 L A071 OlU L A060 013 L P008 007 S P008 008 S A092 008 S A03U 007 S AOUU 013 L AOUU 012 L A072 OlU L A061 Oil L AOUO OOU S A0U2 00!+ S A073 OlU L AO3U 005 S AO77 Oil L AO85 Oil L A07U OlU L A06l 013 L AO78 Oil L AO86 Oil L A075 OlU L A062 007 S AOUO 002 S A0U2 002 S AO76 OlU L A039 Oil L A077 013 L AO85 013 L poo6 007 S A039 OlU L AO78 013 L AO86 013 L A092 Oil L A036 Oil 1 AOUO 007 S A0U2 007 S AOUU 008 S A036 OlU L A079 Oil L AO87 Oil 1 A039 009 L A0U2 Oil L A080 Oil L AO88 Oil L A039 016 L A0U2 OlU L AOUO 005 S A0U2 005 s A036 009 L A033 Oil L A079 013 L AO87 013 L A036 016 L A033 OlU L A080 013 L AO88 013 L P008 Oil S A062 008 S A035 007 S A033 007 S AOUU 009 L AOUO Oil L A08l Oil L A089 Oil L A039 00U S AOUO OlU L A082 Oil L A090 Oil L A093 Oil L A035 Oil L A035 005 S A033 005 s A09U Oil L A035 OlU L A08.1 013 L AO89 013 L A039 002 S A038 Oil L A082 013 L A090 013 L A093 013 L A038 OlU L A035 00U S A033 00U S A09U 013 L AOUl Oil L A083 Oil L A091 Oil L A039 007 s AOUl OlU L A08U Oil L A033 002 S A095 Oil L A062 009 s A035 002 S A091 013 L A096 Oil L A0U3 Oil L AO83 013 L A092 001 S A039 005 s AOU3 OlU L A08U 013 L A06U 001 L A095 013 L A037 Oil L P009 015 S A065 001 L AO96 013 L A037 OlU L A035 016 L A066 001 L A036 007 s AO3U Oil L A063 007 S A067 001 L A097 Oil L A063 001 S A06U 009 L AO68 001 L AO98 Oil L A06U 012 L A065 009 L A069 001 L A036 005 s A065 012 L AO66 009 L A070 001 L A097 013 L A066 012 L A067 009 L A071 001 L A098 013 L A067 012 L A068 009 L A092 002 S A036 00U S AO68 012 L AO69 009 L A072 001 L A099 Oil L A069 012 L AO70 009 L A073 001 L A036 002 S A070 012 L AO71 009 L A07U 001 L A099 013 L A071 012 L AO63 008 S A075 001 L A03U 002 S A063 002 S AO72 009 L AO76 001 L P009 012 L A072 012 L AO73 009 L P006 00U S A03U 00U S A073 012 L A07U 009 L A092 013 L P010 OlU L AO7U 012 L AO75 009 L A092 007 S A100 005 S A075 012 L AO76 009 L A06U OlU L A101 007 L AO76 012 L P010 Oil S A065 OlU L A102 005 S 9h A101 008 1 A109 Oil L AOi+5 002 S A056 008 S A103 005 S A110 Oil L P001 Oil L P011 Oil L A101 009 L Alll Oil L A052 008 S A056 007 S A101+ 005 S A112 Oil L P010 007 L POOU 007 L A101 Oil L Allh 002 S A052 007 S A056 001 S A105 005 S A113 Oil L P005 00^ L POll 0.12 L A101 012 1 A115 Oil L A052 001 S A056 002 S A106 005 S P007 Oil S P010 Oil L POOU 003 L A10.1 013 L A028 Oil L A052 002 S AOkQ 008 S A107 007 S A028 007 S P005 003 L P008 015 L A101 Oll+ L AOOO 001 L A0k6 008 S AOi+8 007 S P003 012 S A001 001 L P009 Oil L POOl 0.11 L A108 013 L A002 001 1 A0U6 007 S A057 008 S P015 Oil S A003 001 L P001 016 L P012 Oil L AOOO Ol6 L AOO^ 001 L A053 008 S A057 007 S A109 009 L A005 001 L P011 015 L P006 016 L P015 008 S A006 001 L A053 007 S A057 00.1 S A001 016 L A007 001 1 P005 Oil L P012 0.12 L A109 016 L A028 008 S A053 001 S A057 002 S P010 016 S A008 001 L P011 Oil L P006 015 L A002 016 L A009 001 L A053 002 S A048 001 S ALIO 009 L A029 001 L P006 007 L P008 012 L P015 015 S A030 001 L A0h6 001 S A0h8 002 S A003 016 L A010 001 L P009 007 1 POOl 012 L ALIO 016 L A050 008 S AOl+6 002 S A058 008 s P015 015 S POOU OlU L POOl 015 L POll 007 L AOO^ 016 L A050 007 S A054 008 S A058 007 s All! 009 L P002 012 L P011 003 L P006 003 1 P009 003 S A06l 008 S A05U 007 S A058 001 s A005 016 1 P011 010 L pooU 00U L POll 008 L ALU 016 1 A06l 007 S A054 001 S A058 002 S P003 007 S P006 003 L P011 006 L P006 012 L A006 016 L A06l 001 S A05U 002 S A0^9 008 S A112 009 L P0.11 003 L pooU 008 L P007 004 L P003 008 S A061 002 S AOl+7 008 S ao^9 007 s A007 016 L P006 002 L P009 007 L P003 015 L A1.12 016 L AOi+5 008 S A0U7 007 S A059 008 S P003 00U S P008 015 L POOl 008 L P012 015 L A008 016 L A0^5 007 S A055 008 S A059 007 S All 3 009 L P001 012 L P0.11 016 1 P006 006 L P002 016 S A051 008 S A055 007 S A059 001 S A009 016 L P010 003 L P005 016 L P0.12 008 L A113 OI6 L A051 007 S A055 001 S A059 002 S P012 016 S P005 003 L P011 015 L P006 0.1.1 L A010 016 L A051 001 S A055 002 S A0U9 001 S poiU oo4 S P010 00U L P006 008 L P007 003 L A030 016 L A051 002 S A0U7 001 S A0U9 002 S P012 003 S P001+ 016 L P008 016 L P003 016 L A111+ 013 L A0U5 001 S A0U7 002 S A060 008 S Allh 00.1 S P008 003 L POOl 007 L P012 007 L 95 A060 007 s A06U 008 L A070 Oil L A119 008 S P006 015 L A100 Oil L AlOk 008 L P015 016 L A060 001 S A077 001 S A080 007 S A119 005 S P012 003 L A109 OlU L A020 Oil L P015 012 L A060 002 S A065 Oil L A070 008 L A083 008 S P006 Oil L A100 013 L AlOU Oil L A075 Oil L All6 00U S A117 012 L A080 00.1 S A106 013 L P015 00U L A077 002 S A118 016 L A119 Oil L A117 008 S AOlU 013 L A112 011+ L A083 007 S POlU 016 L A065 008 L A071 Oil L A012 013 L A117 005 S A100 016 L A10U 013 L A075 008 L P013 016 L AO78 008 S A080 002 S A106 016 L A117 00U S A117 013 L A020 013 L AO83 001 S P011 002 L A110 012 L A071 008 L P012 007 L A117 001 S AO66 Oil L A10U 016 L AO83 002 S poio 015 L A102 008 L A08l 008 S P012 Oil L A118 008 S AO78 007 S A116 009 L A062 001 S P015 003 L A016 Oil L A113 012 L A109 013 L A118 005 S AO66 008 L A072 Oil L A110 013 L P015 003 L A102 Oil L A105 008 L Alll 013 L A118 00U S A078 001 S A08l 007 S A112 013 L P003 00U L A117 016 L A022 Oil L A062 002 S A118 001 S A110 OlU L A072 008 L A113 013 L P003 003 L AO67 Oil L A105 Oil L A115 013 L A116 008 S A102 013 L A08l 001 S P011 00U S P002 OOU L AO78 002 S A116 012 L A062 013 L A116 005 S A016 013 L A113 OlU L POO 5 007 S P002 003 L A067 008 L A073 Oil L A027 Oil L A116 001 S A102 016 L A105 013 L A027 007 S poio 015 L A079 008 S A08l 002 S A011+ 012 L A119 007 S A118 009 L A022 013 L A016 012 L P015 016 L Alll 012 L A073 008 L A018 012 L P012 OOU S AO68 Oil L A105 016 L A020 012 L AllU Oil L A103 008 L A119 001 S A027 008 S A082 008 S A079 007 S P015 008 L A022 012 L A116 013 L A018 Oil L A119 00U S A012 012 L A115 012 L AO68 008 L P015 012 L A02U 012 L A074 Oil L A103 Oil L A08U 008 S A026 007 S A106 008 L A079 001 S A116 016 L A029 008 L A082 007 S A118 012 L A119 013 L A015 007 S A012 Oil L Alll OlU L A076 Oil L AOOO 008 L AO7U 008 L A069 011 L A107 008 L A015 002 S A106 Oil L A103 013 L A084 007 S A001 008 L A077 008 S A079 002 S A02U Oil L A017 007 S A109 012 L A018 013 L AO76 008 L A002 008 L A06U Oil L A069 008 L A107 Oil L A017 002 S A100 008 L A103 016 L A08U 001 S A003 008 L A117 009 L A080 008 S P009 016 L A019 007 S A077 007 S A118 013 L A084 002 S AOOU 008 L A011+ Oil L A112 012 L P009 015 L A019 002 S 96 A005 008 L A009 005 s A073 007 s A053 012 L A021 007 S A08l OlU L P013 007 L A053 OlU L A006 008 L A010 005 S A076 00.5 s A110 00U S A021 002 S A08U 012 L P008 016 L A0U6 OlU L A00T 008 L A08U OlU L A076 007 s A05U 012 L A023 007 S A030 005 S P013 003 L A05U OlU L A008 008 L A083 012 L A075 005 s Alll 005 S A023 002 S A083 OlU L P010 007 L A0U7 012 L A009 008 L A07U 005 s A075 007 s A055 012 L A011 005 S P010 003 L poiU 007 L A055 OlU L A010 008 L A07U 007 s A012 005 s Alll OOU S A013 005 S P013 007 L A090 012 L A0U7 OlU L A030 008 L A06U 005 s AOlU 005 s A056 012 L P009 Oil S P005 Oil L A085 012 L A056 OlU L A120 Oil L A06U 007 s AOlU 00U S A112 005 S A120 007 S P015 007 L AO85 OlU L A0U8 012 L AOOO 009 L A065 005 s A0l6 005 s A057 012 L A001 009 L P005 015 L AO86 012 L A057 OlU L A002 009 L A065 007 s A016 00U S A112 OOU S A003 009 L POlU 012 L A086 OlU L A0U8 OlU L AOOU 009 L AO66 005 s A018 005 s A058 012 L A005 009 1 P008 OOU L A087 012 L A058 OlU L A006 009 L A066 007 s A018 00U S A113 005 S A007 009 L POlU 015 L A087 OlU L A0U9 012 L A120 008 S A067 005 s A020 005 s A059 012 L A008 009 L P005 002 L A088 012 L A059 OlU L A009 009 L A067 007 s A020 00U S A113 OOU S A029 009 L P015 OOU L A088 OlU L A0U9 OlU L A030 009 L A068 005 S A022 005 s A060 012 L A010 009 L P007 012 L AO89 012 L A060 OlU L A029 005 S AO68 007 s A022 00U S A090 008 S A082 012 L POlU Oil L AO89 OlU L A029 Oil L AOOO 005 S A069 005 s A02U 005 s A07U Ol6 L A077 012 L P007 016 L A091 012 L A090 007 s A001 005 S A069 007 s A012 OOU S A07U 013 L A077 OlU L POlU Oil L A090 OlU L A085 008 S A002 005 S A070 005 s A115 005 s AOOO Oil L A078 012 L P008 012 L A050 012 L A06U 016 L A003 005 S A070 007 s A06l 012 L A085 007 S A078 OlU L P013 Oil L A06l OlU L A06U 013 L AOOU 005 S A071 005 s A109 005 s A085 001 S A079 012 L P009 OOU L A0U5 012 L A001 Oil L A005 005 s A071 007 s A051 012 L A065 016 L A079 OlU L P013 008 L A051 OlU L A085 002 S A006 005 s A072 005 s A109 00U s A065 013 L A080 012 L P008 008 L A0U5 OlU L A086 008 S A007 005 s A072 007 s A052 012 L A002 Oil L A080 OlU L P013 Oil L A052 OlU L A066 Ol6 L A008 005 s A073 005 s A110 005 s AO86 007 s A08l 012 L P009 008 L A0U6 012 L A066 013 L 97 A086 001 S AOOU 012 L A003 012 L A005 012 L A06T 016 l A006 012 L A086 002 S A007 012 L A067 013 L A120 002 S A087 008 S A008 012 L A00U Oil L A009 012 L A068 016 L A029 012 L A087 007 s A030 012 L A068 013 L A010 012 L AO87 001 S P009 00U S A005 Oil L A120 013 L AO69 016 L P003 012 S A087 002 S A108 Oil L A069 013 L A108 007 s AO88 008 S A011 01 U L A006 Oil L A101 002 S A070 016 L P008 OOU L A088 007 s A098 008 S A070 013 L A106 012 L A088 001 S AO98 007 s A007 Oil L A106 009 L A071 016 L P010 012 L AO88 002 S A093 008 S A071 013 L A100 012 L AO89 008 S A093 007 s A008 Oil L A100 009 L A072 016 L P007 007 L A089 007 s A093 001 S A072 013 L A100 001 L AO89 001 S A093 002 S A009 Oil L A100 OlU L A073 016 L P007 008 L AO89 002 S A09 1 * 008 S A073 013 L A102 012 L A091 008 S A09^ 007 s A010 Oil L A102 009 L A076 016 L P007 007 L A091 007 s A09*+ 001 S A076 013 L A102 001 L A090 001 S A09U 002 S A030 Oil L A102 OlU L A075 016 L P007 003 L A090 002 S A095 008 S A075 013 L A103 012 L A120 001 S A095 007 s AOOO 012 L A103 009 L A001 012 L P007 015 L A002 012 L A095 001 S A003 Oil L A103 001 L A095 A103 P007 A096 AlOk A096 AlOh P008 A096 AlO^ A096 AlOh P007 A097 A105 A097 A105 P009 A097 A105 A097 A105 P009 A099 A107 A099 A107 P009 A098 A106 A098 A106 P008 P013 A011 P013 A013 A025 A013 A011 POOU A025 P0lU A012 A026 POlU A026 A098 POlU A030 002 Oil* Oil 008 012 007 009 Oil 001 001 002 OlU 016 008 012 007 009 012 001 001 002 Olfc 003 008 012 007 009 008 001 001 002 OlU 007 L OOl* S 001 008 01U 001 013 016 012 013 015 008 008 016 Oil 012 012 013 P012 A115 POli+ A029 POlU A029 A115 P011 A062 P002 A109 P002 A109 P002 A110 P002 A110 P001 Alll P001 Alll P003 A112 P003 A112 P001 A113 P001 A113 Allk A109 A110 Alll A112 All It A113 A115 P002 A015 A093 P003 A015 A093 P002 A017 A09 i * P002 A017 A09 1 * P001 015 008 008 013 004 016 009 007 Oil 015 008 015 001 Oil 008 008 001 008 008 003 001 016 008 008 001 016 008 015 001 007 007 007 007 007 008 007 007 016 Oil 012 003 013 01U 012 Oil 012 008 013 01U 007 s L S L S L L S L S L S L S L S L S L S L S L S L S L S L S L L L L L L L S L L S L L S L L S L L S 98 A019 Oil L A095 012 L P001 OOU S A019 013 L A095 OlU L P003 015 S A021 Oil L A096 012 L P003 Oil S A021 013 L A096 OlU L P002 007 S A023 Oil L A097 012 L P002 OOU S A023 013 L A097 OlU L P002 003 S A011 Oil L A099 012 L P003 007 S A098 Oil* l A013 009 L A108 001 S A015 012 L A017 012 L A019 012 L A021 012 L A108 002 S A023 012 L A026 012 L A013 008 L A011 012 L TCRFLD 99 pooi+ 003 s A017 013 L P001+ 008 L P001 012 L AOOO 016 L A018 013 L A032 002 S A016 007 S pooU 007 s A003 007 s POO 3 006 L A036 013 L AOOO OlU L A019 Oil L A023 007 S A033 009 L A001 001 S A020 Oil L A032 013 L A033 001 S A002 Oil L A003 005 s A031 012 L P001+ 012 L A001 002 S A019 013 L A031 00l+ 3 A036 007 S A002 016 L A020 013 L POOU 00l+ L P001 012 L A001 003 S A002 007 s A032 007 S AOlo 002 S A003 Oil L A021 Oil L P003 006 L A036 012 L A001 ooU S A022 Oil L A023 001 S A033 016 L A003 016 L A002 005 s A006 Oll+ L A037 008 S A001 005 S A021 013 L A023 002 S POOU 016 L AOOU Oil L A022 013 L A032 012 L AO38 002 S A001 006 S POlU OOU s A031 013 L P001 008 L AOOU 016 L A007 OlU L A033 005 S A 32 5 008 S A001 007 S AOOU 00*+ S POOU 015 L A037 012 L A005 Oil L A023 Oil L A03U 002 S A025 007 3 A001 008 S A02U Oil L P003 010 L A037 009 L A005 016 L AOOU 002 S A021+ 007 s AO38 013 L A006 002 S A023 013 L AO3I+ 013 L A037 001 S POll+ 008 L A024 013 L A033 012 L P001+ Oil L P0ll+ 003 s A005 ooU S A006 013 L A038 007 s A007 Oil L A025 Oil L A033 001+ S P001 008 L P015 015 S A026 Oil L POOU 015 L A025 001 3 A008 009 L A005 002 5 A03U 007 3 A037 013 L P010 016 S A025 013 L POO 3 010 L A025 002 S A009 Oil L A026 013 L A021+ 002 S AOjT olS l poio 015 s A003 ooi+ S A03U 012 L AO38 012 L A010 Oil L A027 Oil L A033 013 L A039 008 s POIO Oil S A028 Oil L A006 012 L P005 003 L A011 Oil L A003 002 S A031 008 S AOl+0 002 S P012 003 S A027 013 L P005 00l+ L P001 OlU L A012 013 L A028 013 L A035 002 3 A026 008 S P013 003 S A002 00l+ S P001 006 L A039 012 L A013 009 L A029 Oil L A015 008 3 A026 007 s P013 003 S A030 Oil L A006 Oil L AOl+0 013 L AOll+ 009 L A002 002 S A015 007 S A039 009 L P012 007 S A029 013 L A031 009 L A039 001 3 AOlU 016 L A030 013 L A035 013 L P001+ Oil L A00*+ 007 S A007 007 S A031 001 S AOl+0 007 S A015 Oil L AOOU 001 L P001+ 007 L P001 Oll+ L A016 Oil L AOOU 012 L A035 007 3 A026 001 S A001+ 005 S A005 001 L P001 006 L A039 013 L A015 013 L A005 012 L A015 002 S A026 002 S A016 013 L A003 001 L A031 016 L AOl+0 012 L A005 007 S A003 012 L A035 012 L A039 016 L A017 Oil L A002 001 L A033 008 S AOl+1 008 S A018 Oil L A002 012 L P005 003 L POO 5 007 L A005 005 S A031 005 S A036 002 S AOl+2 002 S 100 P003 008 L A0U6 012 L P006 003 L A021 007 s A017 008 s AOl+7 008 S A052 007 S A057 009 L A04l 012 L P006 007 L P002 008 L A058 013 L A017 007 s A0U8 002 S A020 001 S A057 001 S AOUl 009 L P002 OOU L A051 013 L ' P006 007 L A0U2 013 L A028 008 S A020 002 S AO58 007 S AOUl 001 S A0U7 012 L A052 012 L POO 3 002 L P005 008 L A028 007 S A051 016 L A021 001 S A0^2 007 S A0U8 013 1 A053 008 S A057 013 L P003 008 L AOi+7 009 L P005 Oil L A021 002 S A017 001 S A0U7 001 S A05^ 002 S A057 016 L AOUl 013 L P005 015 L P002 012 L A058 012 L A017 002 S A0U8 007 S A029 008 S A059 008 S AOUl 016 L P002 OOU L A053 012 L P006 008 L A0U2 012 L A028 001 S A029 007 S A060 002 S A0U3 008 S A0U7 013 1 A053 009 L poo 3 OOU L P005 007 L A028 002 S AO^ 013 L A022 008 S AOl+U 002 S A0U8 012 L A053 001 S A059 012 L P003 OlU L AOi+7 016 L P005 015 L A022 007 S A018 008 S AO^-9 008 S A05 1 + 007 S A060 013 L A0U3 012 L P006 OOU L P002 012 L A059 009 L aoi8 007 S A050 002 S A029 001 S A059 001 S AOUU 013 L P002 006 L A053 013 L P006 003 L AOi+3 009 L A019 008 S A029 002 S A060 007 S A0U3 001 S AOU9 012 L A053 016 1 P003 OOU L P005 Oil L A006 009 L A05 ] + 012 L A022 001 S AOkk 007 S A019 007 S A055 008 S A059 013 L poo 3 0l4 1 A0U9 009 L P005 012 L A022 002 S A018 001 s A050 013 L A056 002 S A060 012 L A0U3 013 L A0U9 001 S P002 01^ L A059 016 L A018 002 S P006 002 L A030 008 S P013 015 s AO^U 012 L A050 007 S A055 012 L A007 016 L A0U3 016 L P002 006 L A030 007 S A009 007 S AOl+5 008 S A019 001 S A056 013 L A023 012 L P005 008 L AOU9 013 L A055 009 L A061 007 S A0^6 002 S A006 008 L A055 001 S A023 OlU L P002 002 L A019 002 S P006 Oil L A010 007 S A027 008 S AOl+9 016 L A056 007 S A02U 012 L AOl+5 012 L A050 012 L P002 OlU L A062 007 S A027 007 S A051 008 S A030 001 S A02U OlU L A0U5 009 L P006 006 L A055 013 L A063 007 S AOl+6 013 L A052 002 S A030 002 S A015 012 1 A0U5 001 S P002 008 L A056 012 L A06k 007 S P005 016 L A020 008 S A055 016 L A015 OlU L aoU6 007 S A051 012 L A057 008 S AO65 007 s P002 002 L A020 007 S P006 015 1 A016 012 L A027 001 S A052 013 L A058 002 S A066 007 S AOi+5 013 L A051 009 L F003 002 L A016 Ol4 L A027 002 S A006 007 L A021 008 S A067 007 S A0U5 016 L A051 001 S A057 012 L A025 012 L 101 A068 007 S P010 00U s P013 015 s A090 012 L A025 OlU L A06l 016 L A082 016 L A092 002 S A069 007 S poio 007 s P013 016 S A073 Oil L A026 012 L A010 016 L AO83 016 L P007 006 S A070 007 S P015 003 s P013 Oil' S A093 016 L A026 OlU L A062 016 L A08U 016 1 A093 OlU S A071 007 S POIO 003 s P013 00U S A092 OlU L A017 012 L A063 016 L AO85 016 L AO92 008 S A072 007 s POIO 015 s P012 00U S A07U Oil L A017 OlU L A06U 009 L AO86 016 L P007 008 S A073 007 S P006 016 S P012 003 S A093 010 L A018 012 L A065 016 L AO87 016 L A093 012 S A07U 007 S POIO Oil S AO88 001 S AO92 012 L A018 OlU L AO66 016 L A077 012 L A09U 002 S A011 007 S P011 007 S A008 Oil L A011 013 L A027 012 L A067 016 L A089 007 S P007 012 S A012 007 S P011 010 S AO76 013 L A095 016 L A027 OlU L AO68 016 L AOlU Oil L A095 OlU S A013 007 S P015 00U S AOlU 013 L A09U OlU L A028 012 L A069 016 L A007 008 L A09U 008 S A075 007 S P011 Oil S A089 008 S A012 Oil L A028 OlU L A070 016 L AO78 013 L P007 OlU S A076 007 s P011 003 s A080 013 L A095 010 L A019 012 L A070 009 L A08l 013 L A095 012 S A077 007 S P011 013 s A082 013 L AO9U 012 L A019 OlU L A072 016 L AO83 013 L AO96 002 S A078 007 S P011 015 s A089 009 S A013 013 L A020 012 L A073 OlU L A08U 013 L P007 010 S A079 007 S P011 012 S A085 013 L A097 016 L A020 OlU L AO7U OlU L AO86 013 L A097 OlU S ao8o 007 S POIO 012 S AO87 013 L AO96 OlU L A029 012 L A011 016 L POlU 00U S A096 008 S A08l 007 S P011 006 S AO89 Oil L A075 Oil L A029 OlU L A012 016 L POIO OlU S P007 016 S A082 007 s P013 008 S AO66 Oil L A097 010 L A030 012 L A013 016 L P011 007 S A097 012 S A083 007 S P011 008 S A067 Oil L AO96 012 L A030 OlU L A075 016 L P011 016 S AO98 002 S A08U 007 S P012 008 S AO68 Oil L A076 Oil L A021 012 L AO76 016 L P015 003 s poo8 oou s A085 007 S P013 Oil S A069 Oil L A099 016 L A021 OlU L A077 016 L P011 015 s A099 OlU S ao86 007 S P013 012 S A070 012 L A098 OlU L A022 012 L AO78 016 L P011 002 S A098 008 S A087 007 S POlU 016 S A071 Oil L A077 Oil L A022 OlU L A079 016 L A090 008 S P009 002 S P012 007 S P013 007 s A072 Oil L A099 010 L A088 016 L A080 016 L P007 00U S A099 012 S P010 008 S P013 00U s A091 010 L A098 012 L A009 016 L A08l 016 L A091 012 S A100 002 S 102 A078 Oil L A008 00^ S P015 016 L AO85 009 L P008 006 S A080 Oil L A059 00U S AO86 009 L A101 016 L A08l Oil L P015 012 L AO87 009 L A101 OlU S A082 012 L A088 00U S P012 015 S A100 OlU L AO83 Oil L A009 012 L AO88 009 L A100 008 S A08U Oil L A010 012 L A088 008 S A0T9 on L A085 Oil L A011 012 L A102 Oil L P008 016 S A086 Oil L A012 01 U L A102 013 L A101 010 L AO87 Oil L A013 008 L A103 002 S A101 012 S POlU 012 S AOlU 008 L A009 008 L A100 012 L A008 013 1 AOlU 01^ L P007 006 S P013 008 S A039 00U S P012 Oil S Alo4 016 L A080 012 L POlU 015 L A088 013 L AlOk OlU S P012 015 S AO^l 005 S P015 016 S A103 01^ L A08l 012 L P011 003 L A008 008 L A103 008 S P01J+ 007 s AO^l OOU S A008 005 s A06l 008 L A082 Oil L P011 00^ L A007 001 L P007 008 S P013 016 S A0U3 005 s A102 007 S AlO^ 010 L AO83 012 L POlU Oil L A009 009 L AlO^ 012 S P013 012 S A0U3 00^ S A06l 009 L A103 012 L A08U 012 L POlU 012 L A010 009 L A105 002 S P013 007 s A0U5 005 s A062 009 L A010 008 L AO85 012 L POlU 008 L AO63 009 L P007 004 S P012 Oil S A0^5 OOU S A06U Oil L A106 016 L A086 012 L POlU 007 L A065 009 L A106 01k s P012 012 S A0U7 005 s AO66 009 L A105 Ollj- L AO87 012 L P015 007 L A102 008 S A105 008 S A089 00U S A0^7 OOU S A067 009 L A062 008 L A008 001 L P015 007 L AO68 009 L P007 010 S A089 001 S A0^9 005 s A069 009 L A106 010 L AO67 012 L P015 012 L A070 009 L A106 012 S A068 012 L A0U9 00U s A071 001 L A105 012 L AO69 012 L P015 015 L A072 009 L A107 002 S A070 Oil L A051 005 s A073 009 L A063 008 L A071 012 L P015 Oil L A07U 009 L P007 oii s A072 012 L A051 00U S A102 009 S A108 016 L A073 012 L P015 008 L A011 009 L A108 oik S A07U 012 L A053 005 s A012 009 L A107 OlU L A089 002 S POl^ 015 L A013 012 L A107 008 S A011 OlU L A053 00U S A075 009 L A06U 012 L A012 012 L POlU 016 L AO76 009 L P007 016 S A013 CflA L A055 005 s A077 009 L A108 010 L A075 012 L POlU Oil L AO78 009 L A108 012 S AO76 012 L A055 00U S A079 009 L A107 012 L A077 012 L P015 OOU L A102 001 S A109 002 S AO78 012 L A057 005 s A080 009 L AO65 008 L A079 012 L P015 008 L A08l 009 L P007 012 S POlU 003 s A057 00U S A082 009 L A110 016 L A066 012 L P015 Oil L AO83 009 L A110 Oli+ S AO89 013 L A059 005 S A08k 009 L A109 01k L 103 M09 oo8 s POOS OlU s A126 012 s AOlU 005 s A066 008 L A118 010 L A125 012 L A077 013 L P008 002 S A118 012 S A127 002 S AOlU 00U s A110 010 L A117 012 L A080 008 L A079 013 L A110 012 S A119 002 S P008 01U S P012 016 S A109 012 L A011 008 L A128 016 L A088 012 L Alll 002 S P009 006 S A128 OlU S A088 005 s AO67 008 L A120 016 L A127 OlU L A135 Oil L P008 006 S A120 OlU S A127 008 S A135 013 L A112 016 L A119 01U L A08l 008 L A135 007 s A112 OlU S A119 008 S P009 002 S A009 001 L Alll OlU L A012 008 L A128 010 L A06l 001 L Alll 008 S P009 012 S A128 012 S A010 001 L A068 008 L A120 010 L A127 012 L A062 001 L P008 008 S A120 012 S A129 002 S A063 001 L A112 010 L AII9 012 L A082 008 L A06U 008 L A112 012 S A121 002 S P009 006 S A065 001 L Alll 012 L A013 Oil L A130 016 L AO66 001 L A113 002 S P009 008 S A130 OlU S A135 008 S AO69 008 L A122 016 L A129 OlU L AO67 001 L P008 OOU S A122 OlU S A129 008 S A068 001 L AllU 016 L A121 OlU L AO83 008 L AO69 001 L AllU OlU S A121 008 S P009 008 S A070 001 L A113 OlU L A075 008 L A130 010 L A071 008 L A113 008 S P009 00U S A130 012 S A072 001 L A070 008 L A122 010 L A129 012 L A073 013 L P008 012 S A122 012 S A131 002 S A07U 013 L AllU 010 L A121 012 L A08U 008 L A135 009 S AllU 012 S A123 002 S P009 012 S A011 001 L A113 012 L AO76 008 L A132 016 L A012 001 L A115 002 S P009 OlU S A132 OlU S A013 001 L A071 016 L A12U 016 L A131 OlU L A075 001 L P008 002 S A12U 01U S A131 008 S A076 001 L A116 016 L A123 01*+ L A085 008 L A077 001 L Aii6 01 U S A123 008 S P009 OlU S AO78 001 L A115 01U L A077 008 L A132 010 L A079 001 L A115 008 S P009 016 S A132 012 S A135 001 S A072 008 L A12U 010 L A131 012 L A080 001 L P009 00U S A12U 012 S A133 002 S A08l 001 L A116 010 L A123 012 L AO86 008 L A082 001 L A116 012 S A125 002 S P009 010 S AO83 001 L A115 012 L AO78 008 L A13U 016 L A08U 001 L A117 002 S P009 010 S A13U OlU S AO85 001 L A073 008 L A126 016 L A133 OlU L AO86 001 L P008 012 S A126 OlU S A133 008 S AO87 001 L A118 016 L A125 OlU L AO87 008 L A118 OlU S A125 008 S P009 016 S A117 01 U L A079 008 L A13U 010 L A117 008 S P008 016 S A13U 012 S A07U 008 L A126 010 L A133 012 L 10U APPENDIX B SEGIN % % ThE c-< ftV)VJ ^L S3JTIM3 PROS*** WHICH FOLLOWS WAS DEVELOPED At THE * UNIVERSITY nr ILLIN0T5 ?¥ jTM STEVENS. THE DESIGN IT THIS pRO- I r,RAv4 IS THE SJbjEcT Or ChAsTER rl v/E Or THE dhD THESIS ENTITLED * HJERlSTTe TECH^Ep'JES r3 p T „,r AUTOMATED DESIGN Or PRINTED CIRCUIT * PDAPDS. RRTEFLY HE ALGORITHM PROCEEDS BY DIVIDING EACH CONNECTION % INTO THPrE wlRE SEGMENTS, T WO HORIZONTAL AND ONE VErTT^, THESE * wIRE SEGMENTS ARE THEM ASSIGNED TO SPACES ON THE 3-OARn ^hICH Are % IMPLEMENTED AS TWO ARRAYS* */ERT< FOR VERTICAL WTRES AMD HDR 3 FOR % Ml9T7 r lMTflL WIRES. T-lZ 3R13RAM ASSUHFS THAT THE BOARD TS COMPOSED * Or ELEVEN ROWS OF FlFTEEv \*> ^IV OIL IC PACKAGES, THf SPACING X =l E T W E r N * D w S AMD C 3 L J M \! S Or ? A C < * G E S TS DEPENDANT ON THE VARIABLES % US Av,"> H<, FlNAj. 3 OSlTlONS O r THE WIRE SEGMENTS IS DETERMINED 3Y ?! THE CHANw£L ASSIGNMENT ALGORITHM, t % e-ACH HORIZONTAL WIRE SEGMENT IS REPRESENTED As 3ME 17 3I T * WORD WITH THF FDLL'L^wINS r T r lDS, VERTICAL WIRE SEGMENTS AR? f REPRESENTED WITH THE SA*E TV 3 " 3F WORD ONLY THE END P^TNTS ARE * CALLED T-i 3 AND 90TTDM, % t^ITS USAGE % t TO 5 OFFSET OF RIGHT E^D POINT WITHIN SPACE J! i TO 10 VERTICAL SPACE OF RIGHT END P^INT II TO l.S OUTSET Or L- rT ^D °0INT vITHEN SPACE 17 TO 21 VERTICAL SPASE 3F LEET END PBTNT ?? TO 30 POINTER TO VERTICAL WIRE SEGMENT CONNECTED TO ThE RIGHT EN) O r THTS WIRE 5E" M ENT 31 TO 39 POINTER TO VERTICAL HIRE SEGMENT CONNECTED TO THE LEFT END Of THIS WIRE SEGMENT 105 O TAG n I MDT CATE TTUAL f» D S T T I OMISG OF THIS WlR? SES o! to H*V :, »H :, » r I : 'ST , ,LAST,o?EU5 c ",0LJM3# CH«M^»EU#3FST» ! ?UlM,3j,<,RL,lv,IT,jJ#SPrc» L?T9,T3TR,^3T^,TEM9| T M TF SS P FT RST9* L' S T ? » ^T • LT » RT 3rp , LTOFF» RTPTR # I.TPTR J a|_P4e />3^y Hn9S[0lil#3t?553>H5PTRtOll1J» tfrorst on a. n?55i»y/s 3 T9[T« 15) i 4L°4e apPa* t »0' B r9t23»3f?5Sl»HspTRt0l231» Vf : ?T3rOM«,'):?55' , »*/ :,:, T?tOll4l| r 1 P M A T f«T(ai3),CHE:^<(X?» : 'IS/),Mr«(X2»lSl5J# WT^T (?i 5 ),r 7F ^t ( »3^T VTE^ EPPOP-.O #"TDES NOT PHTNT TO", IS), CMrMT(i6,« chammtls j s e o i m s°a:e » , i 5 / ) j L * 3FL *EyTV,NExTH,EPP3P»E;)jT» LA3EL ETF*M3REI LAPEL PTtE»pITO> LAPEL EPP0P1J alpha fil^amEi FOP^AT :»R9rMTf A6)J R?AnfCa*D*»CA*DFMT»FTlYME)J FILL WTPLT^T WITH r I LNAWE$"P"[ Al 15161 J WPlTEe>PTvjT,CAPOrMT»rTLN ftw E)l vshi =( v*i c9) oiv 2» V D Hl t(v°l =7 ) 01 V ? I H JI L S S i/5 3 H[J]] TMEM BF^IN j:=RT»=RTTt=Jl4-n i.T:=LFT:=jt; RTPTR1=RPTR» s\/S D H[ J]J L'TPTPt =L p TRt =511) pTTOFFJ=RTO t 'F: = V?Hj IF LASTo 5TR 3 Them 3EGTN LETOEFt s \/S + J 7-LAST°l T92lsli END ELSE LETO r E»r\/S + LAST!>| IF FIRSTP GTP 9 ThEN BEGIN LT0FE«rrVS4 lHFTRSTPj TBI »»1J 107 END ELSE ESjD else 3 E G J V JtrPTts^ITIeJll lT:=LFT|=Jl > RT°TR| rR»TRl=511 J i_TPTf?t=L»TR»=VS?T^[J]; LTTFFisL/TaFFIsVSHJ IP L A S Tp STR 3 T4F.N ?:"IN RTTHTf !sVS*18-L«ST'l M?l = U ENS EL"*E RTTnrf : s y/s*LAST»-i ) Tf ETRST 3 -,TR 3 THEN 3E5IN ?T3Fr: B V5*16*FnST»l F*1 1=1 I r vn else: RT->rr; = »/s*fiR5T3-l| END» IF Jl GTR J? THEN GENERAL C^N^ECMOW BCSTM THf VERTICAL HTRE SET 3s4 r v*T rHR EACH CONNECTION IS A 5 S I GNE") T ^ T-tc VrRTTCAL S » ft C E W -< T T -« H«S HE TEW'ST ^1 RE SEGMENTS ALREADY 4SSTJVJE') TD IT A VJ3 LIES ?ET^ECN THE C"ILJ M NS OF THE Tdl t>AC<»GES *ETNG ClMNECTEO, PTf, l «?55l 108 if \/5PT9rTV3] lss his then hegtn H T 5 j = ^ s 3 T ? r I \i ■) ] ) HT3P»=IN9I EN9J J« =RITj =3TG?; 9TT3"n=V5H) If L* I >T3>B THEN gr-fvi th?« = h E^O ELSE RPT^tsVSPMt j]| l T?«=511 » 3T»=,il ; LT«=jl if ri : ?st 3 >s then 3 =: 3 1 m *T0FT: s vS*J 5- r HSTPj THii=i j em:> else: =?T3rrj S y/SfrnsT 3 -u LTDFrisVSHJ LTPT^JsVS'T^t J]» "?TPTRIa51IJ E-MOl I r Jl LSS J? THEN PEStV THE VERTICAL rfTRE SESxENT rn=? EACH CONVECTION is ASSlGNEf) T3 THr VroricAL SPACE „H j ; H HftS THE F r w , ST WIRE SEGMENTS *L«*DY ASSTSNED T:) IT AN5 LIES BETWEEN THE COLONS OE THE T Mn PACKAGES 109 ^ r i Ms C>V^JEr TEO. ^ I 3 I = 2551 r?^ IVO IsJWl STE. 3 1 umtil J2 90 IF YS^T^IMD] !.:S. 913 THEN 9 E G T N 9 T G I = V 5 ' T 5 [ I \J D ] I =< T 5° I =IN?> CVDJ jt =LfTt=aiG»i RTT»=J2I JF L.AST»>* THEM 3E3lV ^IT3rr t= k/S + l6-'.«STP> 7321=11 rMD ELSE RTT3r-ri-VS*i.4ST :> -!; L.FT3FT|*VSH| ^o T ^ I =5 1 1 t L B T*lstfS*T*[J1J *TI =J> If rj^ST?>? HTM 3E S I M LTDTFl =VSf 1 7-F!?sT?| TM I =11 rvJn ELSE LTgrF|«v$*|rMST»J RT3Pri«VSHI 9TPTRI s^/S^T^t J] l LTPT^I»51 II FMD? If T1>I? THrs ■ran I le^Tt «2«I2*T92I i d t«n' t = ?*r 1 *m i 110 TrjP3Ffis ns^ T t> T R j e H a P T R T T 1 => 1 1 9PT°« =H»PTR.r I "II TNT ELSE o e r, T M I » =Ta=>: =?xI2 + T32| TTPDrrjr msh; PTTOFFje HSHJ TPT'JrWPPT^f I U 3°TPt=H3pTR[33r i; F VOl TF Tl = T? TME\J ? DTH pIVc I vi Sfl ME ?Tm *%•, M3 v/ F R T I c A L wIrE'IS USED. PEr,n I r J 1 > J ? THEM p T 5 I m RTT0TF»=RT3FFJ RPTR t zRTPTR J EvO ELSE RFGIM LFTt=LTJ LrTDFFisLTDFFJ L 3 TRt=LTPTR; EVf)J STORE w^PD FDR H D =? I 7HNJTA L D VJ L v . 9 0T 4 dIVS I vi SAuE PIN R^w. HT9»tT3B # ^p3TR[TD B n»« RITDET I L s TRf 39 * 8« 91 S Ill LFTfffTM *>:5:$] j RTTM0I4I5JI HopT?rTn33l=H?3T^[Tl3 ,, *i; GT T3 MDREI FMn f «; T ORST w???S FDR GT VJ~ ^ A i. ClviMECTTCI^. MDRBfI#HP3T?[I])ts^TTDFr »LPMr 39:8:91 R«» D T9r30«9«9l5LF'Tf31i4i5HL r T0eTrt0«'F RBPM[39:8:9]?r 3 T'?[30i«:9i n3Tr?1««t'5H^3T0 r fri6:5:*]&ri :s cmj4:5]» t'SPTRtJ3l«tfS»T9fjH1l r, H T1 viURF) EDFI f^D S»«CF assigvjuEmt H^TTFf P^TMT#NpM»r3^ I : rO S^Fo 1 u ^J T I |_ 1" DO VSPT^rM, FT* Ii»D STfo 1 JMTIL ?3 01 ^pTR(Tj)) q f. r, t nj c^a^vjtl asstgymfmt CMAVM£|.I»SJ F1P 3EST T-»EN 3EGIM 3EST!=vr^rsr<,J].no»ini 9J«=J| E^OI T r ?ESTsO TWEM 9EGn CHAVJ«jr L , sC ^ ftw ^ ?L + n 3"! TO MEXTVJ EM9J Jr »T0 MEO 51 1 M~N TT 134P(S3AS»»M].M0I51*X A -O •nRP[S3A;,=TR].[30t9l=3j THFM 113 TE *0*Pf 5*AS,»m. C16I61 GEO CHS^NEL THEN HT.^3[SPftC,3T : ?5i=H"'^ : >[ ,; P ft C,PTRUCH6MNELr5»5tf] rLSE KHFVER5AL HAS TCCUREQ. H r IR?[SPAC»PT51j=HlR 3 [«;PAC»PTR.UTE^P[3O:30j9l RTE^ : »r3D:39J9UTEv , r 1 6 f $ ] + nr5l5i6]»C4AsjMELr 1 M5 «6] else T r -)DRPrSPAC# ! »T^3.[?ll5]s'< AMD nn^prsPAr* 3 !'!. 1 39t9i = 3j then T r 43RPrS94C>»T5»1.t 5 1 6 1 SFQ CH*NNEL THEN H19 :, r«;PAC,Pr ; ?3t=HT^ :> [SPflC,PTRHCHAVJNELrl6t5t61 else rofv^s^. h*s iccu^o, HT^PrSPAr»PTV1t=m : ) : '[^PAr,PT^UTE^P[39t30!9l *TEvis»r33!39t9HrFVPr!M «10f5]&TrviPfi0l?l t 5 1 UDj« 3 i = r"»". r 5t 61 + 1 H 1 6: 5»6)»,:HMNELr St5:6] ELSE q E r, t vj E R 9 R I ^TTEcPHYT'r^r^NH-IR'lSPAC » P t «? J » < ) I S3 TO r i j T | ENDI EO; RITE » WRTTf(PRT\|T,C-irHT»:HAN\lEL»*)/ ENOf CHA N\|EL» s1 J FIR <«=n step 1 JMTlt ?3 DO Pi r r t m ■ ]f MP=T9T <)sD then *P6lN CHammEL'«OJ r3 to Rim V" : )TS[<»qj1i=\/: ; 'T^r<,3j1HlrAniO»l]rS»»C»?Mj.r30l9l«9J THEM' T r 43*PrS»A%*TRj.[1 6 »6l SE9 CHANNEL THEN H?RPt'S = AC.?T : ?]:=-nRPrSPAC»PTR3S,CHANNELr5«5»M "~ LS ^ ?R"VERSAL -IAS '1CCU9E0, H 1 R p [ 5 p A C » p T * J : = H 1 R s f s P ft C » P T R 1& T E M P [ 3 9 | 3 J 9 1 ITrM3r3 9l39»9HTE"Pr21 C 1 « 5 J R T E M P f 1 * 3» 1 I 5 J ROJ^I'TSM'.f I6lf )-«l)r5|5l6]l.CHAM¥EUl*l5lS] ELSE T^ H^ 3 rS- 5 A%PTP3.t?lt5l = < AMD M3RPTSPA:* or 3 ] . [39j 9irPJ THEV tf M3*Prs»Ac,?TRj.t 5r ft i ge* channel then M1RP[SPAC.PT^]t=H-|^P[SPflCPTRUCHftNNELtl6i5r61 rLS? rR-V^RSAL -IAS TCCUREO. H1RPfSPflC.PTR]»rmR3 r spAC*PTRuTEwp[39!30|9i STE^?r33:39»9UTE w Pr?lH0t5nTrMPri0l?li5j RCDJ^^t=TEv«'.r5:6l + l>t16:5l6]^CHAVNELr 5 t 5 l 6 ] ELSE G3 TO ERR3RJ t>T "=VE'.TSr<. : 'J].r39|9]; SPflCt=VERTStK»9J3.r?ii5]| TrM?:EH3RPrSPAC,PTR]| Ir ( k vnD ?)-^ THEN Tr CHANNEL GTR 19 NEm SFAlLJR?. HAS OCCLIREO. CHaNVEL«=15 else ir channel gtr 5 then 115 yrATL'J 1 ?" HAS OCCURE'). CM/JMMFLlsCHAMVEL* 4 ri$r CHAMMri.:si rr r h a v» nj p: l & t 9 1 9 t h~m F l M S F rr C H A M \J f. '_ 5 T 3 it T -< E M Et,5F cham^EL: s1 J RFc;T t =0* flP 1 1 s 5 T E p 1 JMIlL H 3 p T 9 r < 1 - 1 50 PrSTM » TT Tnf [_rrT "IT TuBEST THfN 3EGIM 3est tr-n^r <» ji.ria iiui 9JleJ) EMDl TT arsT=0 THEY IF HPPMfO/O T^fm 9 E 1 1 ^ r^a^/MELt = -^* > J VJ ^.>♦1 * 31 TO njfxTHj EN1J ^1 : ?pr<»9J]:=H0^ :> r<' : 'JHlfoOtOJlHC^'VNJELt 116 r t * % errori I RITOI a 1 1 « t = H 1 R? f < , 3 J J . r 2 1 11 11 1 RESTisOj 9E=>i$TTI3N THE r ^ D 31IMT Or THE |/E^TIC.H rfIRE SEr.uENT *HICH r^MMTfTs td this (jnr s r s m e ^ t n cdrespind to this c h « m m e i a s m s m < wSMT. VI REVERSAL? 3F \l T .JTz^i ^IRE SERVIENTS At?E POSSIBLE i> T 3 l s H [) 9 P r < » 3 J 1 . [ 3 D l 9 1 J If 3 T? VJE3 51 1 HEM T r VE^TSr5 B .*Ct»T9],'rl.9l5]«.K HC' v r TTSiS = -C» = TTj£sv'c : ?T?r$r£c,?'R]R*>-jANJME'i-.[5jTt'Sj ^ '- ^ ^ T r VE'TSrS=»*C# 3 T93.r21 ! 5 ] r K THEM V r RTSrS3A;,3T. : ?]!=^E : ?T^rSPAC»3TR]?CHANJMELCl^»5l61 ELSE 63 n E 9 R 3 R 1 i PTs:=M3^Pr <, 3J] , [ 3?j91| SPflCt=H3R 3 r <» q J] ,f 21 t 5 3 * IE *TR ME3 5! 1 THE V T r l'ERT5[SPftC» 3 T9],rl9t5]s< THEM VERTSrS3A:#3T^UsV/ERT?r?PAC»PTR]&CHAMMEL[5i 5t5] Ei.SE T^ VTRTSrS'ACf =»T ^ 1 . r 2 1 :5]sK them ■ Vr?TSrSPA;,3T : ?]trVERTSrSPAc»PTR]RCHAMVELtlDl5l6] ELSr 3EGIM ^ITE(PRlMT>i9rvH>VE;?TsrS B AC,3TRJ,OJ G3 T3 E3JT) FVDI WRITE f PRIMT»C-«FMT»CH4MSEL»*)I EOUTl EMI. 117 LIST OF REFERENCES 1. G. H. Barnes, R. M. Brown, M. Kato, D. J. Kuck, D. L. Slotnick and R. A. Stokes, "The ILLIAC IV Computer," IEEE Transactions on Computers, C-17, No. 8, (1968), 7^6. 2. D. L. Slotnick, "The Fastest Computer," Scientific American, Vol. 22U, No. 2, (February 1971), 76-87. 3- M. A. Breuer, "General survey of design automation of digital computers," Proc. IEEE, 5k, No. 12, (December 1966), I708-I72I. h. J. Munkres, "Algorithms for the assignment and transportation problems," J. SIAM, 5, (1957), 32-38. 5« E. L. Lawler, "The quadratic assignment problem," Management Science 9, (1963), 586-599- 6. P. C. Gilmore, "Optimal and suboptimal algorithms for the quadratic assignment problem," J. SIAM, 10, No. 2, (June 1962), 305-313- 7- R- C. Prim, "Shortest connection networks and some generalizations," Bell Sys. Tech. J., 36, (November 1957), 1389-1^01. 8. H. Loberman and A. Weinberger, "Formal procedures for connecting terminals with a minimum total wire length," J. ACM h, (October 1957), U28-U37. 9- R- Courant and H. Robbins, What is Mathematics ?, Oxford University Press, New York, I9I+I. 10. M. Hanan, "On Steiner's problem with rectilinear distance," J. SIAM, lk, (1966), 255-265. 11. M. Hanan and J. M. Kurtzberg, Placement techniques, Design Automation of Digital Systems : Theory and Techniques , M. Breuer, ed. , Prentice- Hall, New York, 1972. 12. J. M. Kurtzberg, "Backboard wiring algorithms for the placement and connection order problems," Burroughs Report TR 60-Uo, June 28, i960. 13- J. M. Kurtzberg, "On approximation methods for the assignment problem," J. ACM, 9, No. h, (October 1962), U19-U39- lk. J. M. Kurtzberg, "Algorithms for backplane formation," in Micro- electronics in Large Systems, Spartan Books, 1965, 51-76. 15- R. L. Gamblin, M. Q. Jacobs and C. J. Tunis, "Automatic packaging of miniaturized circuits," in Advances in Electronic Circuit Packaging, Vol. 2, G. A. Walker, ed. , New York: Plenum, 1962, 219-232. 118 16. L. Steinberg, "The backboard wiring problem: A placement algorithm," SIAM Review, 3 No. 1, (January 1961), 37-50. 17. R. A. Rutman, "An algorithm for placement of interconnected elements based on minimum wire length," Proc. 196k SJCC, U77-U9I. 18. F. S. Hillier and M. M. Conners, "Quadratic assignment problem algorithms and the location of indivisible location, " Management Science, 13, No. 1, (September 1966), H2-57- 19. G. W. Graves and A. B. Winston, "An algorithm for the quadratic assignment problem," Management Science, 17_, No. 7, (March 1970); ^53-^71. 20. C. Y. Lee, "An algorithm for path connections and its applications," IRE Transactions on Electronic Computers, (September 1961), 3^+6-365« 21. D. W. Hightower, "A solution to line-routing problems on the continuous plane," Proc. 1969 Design Automation Workshop, 1-2^-. 22. K. Mikami and K. Tabuchi, "A computer program for optimal routing of printed circuit conductors," Proceedings of the IFIP Congress, 2, 1968, 11+75. 23' R- B. Hitchcock, "Cellular wiring and the cellular modeling technique, technique," Proc. 1969 Design Automation Workshop, 25-^-1- 2k. S. Heiss, "A path connection algorithm for multilayer boards," Proc. 1968 Design Automation Workshop. 25. S. Ackers, Routing techniques, Design Automation of Digital Systems : Theory and Techniques , M. Breuer, ed. , Prentice-Hall, New York, 1972. 26. S. E. Lass, "Automated printed circuit routing with a stepping aperture," Comm. of ACM, 12, No. 5, (May 1969) , 262-265- 27. A. Hashimoto and J. E. Stevens, Jr., "Wire routing by optimizing channel assignment within large apertures," Proc. 1971 Design Automation Workshop. 28. A. Hashimoto and J. E. Stevens, Jr., "Path cover of acyclic graphs," ILLIAC IV Document No. 239, December 2k, 1970. 29- R. G. Garside and T. A. Nicholson, "Permutation procedure for the backboard wiring problem," Proc. IEE London, (January 1968), 27-30. 30. L. C Abel, "On the automated layout of multi-layer planar wiring and a related graph coloring problem," Coordinated Science Laboratory Report R-5^6, University of Illinois at Urbana-Champaign, January 1972. UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA R&D (Security elmaalflemtltm of till; body of ab arrmct mnd Indamtng annotation must bo antatad whan tha overall report la clmaalflad) ORIGINATING ACTIVITY (Corporal* author) I J,. REPORT SECURITV C U A »SI F . C A T I OK Center for Advanced Computation Univeristy of Illinois at Urbana- Champaign Urbana, Illinois 61801 UNCLASSIFIED 2b. CROUP 3. REPORT TITLE Fast Heuristic Techniques for Placing and Wiring Printed Circuit Boards 4- DESCRIPTIVE MOTH (Typo of ta po tt and rnelualwa datma) Doctoral Dissertation B authorisi (Flrat mm, mlddla Initial, Imat nam*) James E. Stevens, Jr. S. REPORT DATE October 1972 la. TOTAL NO. OF PAGE* JL2S. 7b. NO. OF REFI 3Q_ •a. CONTRACT OR GRANT NO. DAHC04 72 -C -0001 b. PROJECT NO. ARPA Order No. 1899 «a. ORIGINATOR'S REPORT NUMBERISI CAC Document No. 58 ah. OTHER REPORT NOISt (Any othar numbora that may ba aaalfned Oil a raport) 10 DISTRIBUTION STATEMENT Copies may be requested from the address given in (l) above, II. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY U.S. Army Research Office-Durham Duke Station, Durham, North Carolina IS. ABSTRACT A comparison of existing placement techiques is presented. Large realistic printed circuit board problems are introduced and used to make comparisons. The value of different placements is measured by the total wire length generated as well as by the results of actually routing the connections on the board. A new wire routing algorithm called Channel Routing, is proposed. The Channel Routing algorithm is faster than existing routing techniques and can handle very large circuit board problems. The results of implementing the basic Channel Routing algorithms are presented. These results are also used to compare the effect- iveness of the different placement algorithms. DD 'JT..1473 IINf!T.ARSTFTF.n Security Classifi cation UNCLASSIFIED Security Classification KEY WORDS KOLI WT Fast Heuristic Techniques Printed Circuit Boards ILLIAC IV Design Problem Design Automation Placement Routing TTHrf!T.ARSTTiTttD Security Classification BIBLIOGRAPHIC DATA SHEET 1. Report No. UIUCDCS-R-72-558 3. Recipient's Accession No. 4. Title and Subtitle Fast Heuristic Techniques for Placing and Wiring Printed Circuit Boards 5- Report Date October 1972 7. Author(s) James Edward Stevens, Jr. 8. Performing Organization Rept. No. 9. Performing Organization Name and Address Center for Advanced Computation University of Illinois at Urb ana -Champaign Urbana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. DAHCO^ 72-C-OOOl 12. Sponsoring Organization Name and Address U. S. Army Research Office - Durham Duke Station Durham, North Carolina 13. Type of Report & Period Covered Doctoral Dissertation 14. 15. Supplementary Notes None 16. Abstracts A comparison of existing placement techniques is presented. Large realistic printed circuit board problems are introduced and used to make comparisons. The value of different placements is measured by the total wire length generated as well as by the results of actually routing the connections on the board. A new wire routing algorithm called Channel Routing, is proposed. The Channel Routing algorithm is faster than existing routing techniques and can handle very large circuit board problems. The results of implementing the basic Channel Routing algorithms are presented. These results are also used to compare the effectiveness of the different placement algorithms. 17. Key Words and Document Analysis. 17o. Descriptors Fast Heuristic Techniques Printed Circuit Boards ILLIAC IV Design Problem Design Automation Placement Routing 17b. Id( in il i< 1 ■, Open-Knded Terms 17c. < OSA II Field/Group I ulability Statemi m Copie:; may be obtained from the address in (9) above. Distribution unlimited. 19. Security Class (This Report) UNCI ASSIFIHD 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 128 22. Pri ^C »M NTIS-U ( 10-701 USCOMM-DC 40329-P71 fc 6