Discussion Of Parallel Algorithms Abha Moitrat 5. Sitharama Iyengar4: TR 86-759 June 1986 Department of Computer Science Cornell University Ithaca, NY 14853 t Department ofComputer Science, Cornell University, Ithaca, NY 14853 ? Department ofComputer Science, Louisiana State University, Baton Rouge, LA 70803. DISCUSSION OF PARALLEL ALGORITHMS Abha Moitra Department of Computer Science Upson Hall Cornell University Ithaca, New York 14853 Abstract S. Sitharama Iyengar Department of Computer Science Coates Hall Louisiana State University Baton Rouge, LA 70803 In recent years we have witnessed a tremendous surge in the availability of very fast and inexpensive hardware. However, our ability to des?gn fast and cheap hardware far outstrips our ability to utilize them effectively in solving large prob- lems fast. Hence there is a continuing interest in the study and development of parallel algorithms. In this paper we present a survey of deterministic parallel algorithms for a class of computational problems. Both graph-theoretic and non graph-theoretic problems are considered and the parallel algorithms presented are motivated by identifying some common paradigrns. -2 1. TABLE OF CONTENTS Introduction 1.1 Models of Parallel Computation 1.2 Techniques for Exploiting Parallelism in Algorithms 1.3 Computational Model Used 1.4 Paradigms for Organizing Parallel Computation 1.5 Paradigms for Improving Efficiency of Parallel Algorithms 1.6 Organization and Scope of the Paper 2. Parallel Connectivity Algorithms 2.1 Parallel Connected Components Algorithms 2.2 Parallel Biconnected Components Algorithms 3. Parallel Minimum Spanning Tree Algorithms 3.1 Parallel Sollin's Algorithm 3.2 Parallel Prim-Dijkstra Algorithm 3.3 Parallel Kruskal's Algorithm 3.4 Adaptive Parallel Algorithms 4. Other Parallel Graph Algorithms 4.1 Parallel Algorithms for Shortest-Path Problems 4.2 Parallel Matching Algorithms 4.3 Parallel Planarity Testing Algorithms 4.4 Parallel Maximal Independent Set Algorithms 4.5 Parallel Algorithms for Euler Circuits 4.6 Miscellaneous Parallel Graph Algorithms 5. Other Parallel Algorithms 5.1 Parallel Arithmetic Expression Evaluation Algorithms 5.2 Parallel Algorithms for Polynomial Evaluation 5.3 Parallel String Matching Algorithms 5.4 Parallel Tree Balancing Algorithms 5.5 Parallelism in Alpha-Beta Algorithms 3 4 6 7 7 9 11 13 13 21 24 24 20 34 35 36 36 38 39 40 41 42 43 43 45 46 47 51 58 61 6. Conclusions References -3- 1. Introduction In recent years we have witnessed a tremendous surge in the availability of very fast and inexpensive hardware. These have been made possible partly by the use of faster circuit technologies and smaller feature sizes, partly by novel architectural features such as pipelining, vector processing, cache memories, sys- tolic arrays, etc., and partly by using novel interconnections between processors and memories such as Hypercube, Omega network, Orthogonal Tree network and others. However, our ability to design fast and cheap hardware far outstrips our ability to utilize them effectively in solving large problems fast. This is due mainly to the fact that a large problem may not be easy to decompose into smaller problems which could be solved in parallel, on account of data dependen- cies between the subproblems. The intrinsic parallelism of a problem can be defined as the product of the time required by the fastest parallel algorithm for solving it, and the number of processors required by that algorithm, divided by the time required by the best sequential algorithm. For a problem with high internal data dependency, the intrinsic parallelism would be very low. Because of these data dependencies, processes which are solving related sub- problems would need to communicate with each other. This communication could be via shared memory (with or without concurrent access), via a data bus or via an interconnection network. Any specific scheme incurs an overhead in terms of time lost to contention and/or latency, and also to hardware costs which do not reduce dramatically with improved technology, like that of the underlying circuits. Further, a communication scheme which is good for one class of prob- lems may not be good for another class, which only adds to our difficulty in find- ing a parallel algorithm. Memory contention can slow down the execution of a parallel algorithm, if the various processing elements must access the same variable at the same time; some systems must be devised so that only one processor can access a given vari- able at any one time (for example, LOCK and UNLOCK on MIMI) machines). Also, if the number of logical processors is larger than the number of physical processors in the machine, some sort of scheduling must be done to determine where the extra processes will eventually be handled. The scheduling cost is the resource allocated to do this scheduling. For efficient scheduling, the extra logi- cal processes should be saved until a processor is available, and the internal state of the logical processes should be monitored. One factor which can vary greatly between machines and influences execu- tion speed is the cost of creating a new process. For example, if a single process created all the other processes, then the cost of constructing p processes is O(p). On the other hand, if new processes are created dynamically by other existing processes, then in the best case the construction cost of p processes is 0 (log p) if process creation corresponds to a binary tree configuration. Examination of the above factors suggests two paradigms which can help improve parallel algorithms. The first is to design an algorithm with a large grain size and a smaller number of processes (grain size refers to the amount of 4- processing done by an individual process). The second suggests that the optimal number of processes is a compromise between the gain provided by each process and the time lost to synchronization. 1.1 Models or Computation The design of parallel algorithms becomes an important issue as numerous parallel architectures are developed. In fact, a considerable number of very dif- ferent architectures for parallel computing are in existence - ranging from special purpose array processors, to tree machines, to loosely coupled networks of proces- sors. Since the design and performance of a parallel algorithm depends very much on the architecture of the parallel machine, it is necessary to keep the architec- ture in mind when designing parallel algorithms. There is however no universal method for designing parallel algorithms. One approach to constructing parallel algorithms is to recognise parallelism in the existing sequential algorithms. This approach has been studied by different researchers (Keller 1973, Lee et al. 1985, Moitra, Iyengar 1986, Nicolau 1985, Shrira et al. 1983, Strom, Yemini 1985). We will therefore first examine briefly some parallel machine models of computations that have been proposed. 1.1.1 SIMD Machine SIMI) (Single Instruction Multiple Data) machine consists of an array of identical processors. All processors simultaneously execute the same instruction supplied by the control unit possibly on different data items. The execution of the instructions is synchronous in the sense that each processor executing the instruction in parallel must be allowed to finish before the next instruction is taken up for execution. Different models are obtained depending on whether the two types of con- flicts are allowed or not. In SIMD-SM model reading and writing conflicts are not allowed; in SIMD-SM-R simultaneous reading (but not writing) is allowed. In SIMD-SM-I?W, simultaneous reading and writing is allowed; in case a number of processor are attempting to write to the same location different assumptions can be made about which process succeeds in writing. In the equality-conflict- resolution, simultaneous writing is permitted only when all processors attempt to store the same value. In priority-conflict-resolution, all the processors are linearly ordered according to some priority and the processor with the highest priority attempting to write succeeds. In arbitrary-conflict-resolution, any arbitrary pr? cessor attempting to write succeeds. 1.1.2 MIMD Machine MIMD stands for Multiple Instruction Multiple Data and have the following characteristics. They consist of processing elements (P?) which may be individu- ally indexed. Each FE is capable of performing the standard arithmetic and logi- cal operations. In addition each FE knows its index and has some local memory. -5- The PEs operate asynchronously under the control of individual instruction streams. Different PEs can execute different instructions at any time. During the computation PEs communicate results to each other. In many MIMI) models the time required to communicate data from PE to PE often dominates the overall complexity of the algorithm. Several interprocessor communication models for NIlMI) computers have been proposed in the literature. The communication overhead of an algorithm varies from one communication model to the other, however the shared memory model (SM) is a well studied model. This model has no communication delay. In a shared memory computer there is a large common memory that is shared by all PEs. It is assumed that any PE can access any word in common memory in 0(1) time. When two or more PEs read (write to) from the same location simultaneously, we say that a read (write) conflict has occurred. In the MIMD-TC model, the processors are attached tightly through a cen- tral switching mechanism to reach the global memory. Stone (1?8O) states that architectures based on the MIMD-TC model have a limited number of processors because of the cost involved in the switching process. An example of this archi- tecture is C.mmp which has sixteen processors. 1.1.3 Tree Machine The tree machine of Bentley, Kung (1?79) consists of 0(n) processors. These processors are of three types. Processor type 1 is capable of broadcasting data they receive and the processor type 2 can combine their inputs in an elementary way. Processor type 3 stores program and data of size 0(n). 1.1.4 Special Purpose Parallel Machines The advent of parallel processing (specifically `IS!) has led to the develop- ment of a number of special purpose parallel machines to support directory struc- tures. Leiserson (1?79), Bentley, Kung (1()79), Ottaman et al. (1()82) and Atallah, Kosaraju (1()85) proposed pipelined architectures based on a balanced binary tree. 0(n) PEs are used in order to support a search tree containing up to n elements. The machines vary in their wiring complexity and variety of of dictionary opera- tions that they support. Generally all of them can perform the basic dictionary operations in 0 (log n) time. The complexity of the dictionary operation varies on the input pipeline intervals. Atallah, Kosaraju (1?85) machine provide O(log n) performance with a pipeline interval of 0(1) for a wide range of dic- tionary operations (n is the actual number of elements stored in the 0(n) PEs machine). The above designs maintain the dictionary elements in some sorted order. Somani, Agarwal (1984) propose a binary tree machine with 0(n) PEs that does not require any sorted order for the dictionary elements. Their design supports all dictionary operations and provides an 0 (log n) time performance with constant pipeline interval. Tanaka et al. (1980) propose a pipelined architec- ture for maintaining search tree of n elements with only 0 (log n) PEs. Fisher (1984) developed an architecture based on the Trie structure. In this design the -6- number of PEs is proportional to the length of the maximum key and this scheme is advantageous when the dictionary keys are long. These pipelined archi- tectures achieve only an 0 (log n) throughput improvement over the serial bal- anced tree algorithms. When the number of records in the dictionary becomes greater than n these designs will not function i.e., the hardware is tailored to the maximal possible number of elements in the tables. While the 0(n) PEs architec- tures can handle efficiently operations beyond basic dictionary functions they have no advantage over the 0 (log n) designs when only the basic operations are considered. 1.2 Techniques For Exploiting Parailelism In Aigorithms In most sequential algorithms, some degree of parallelism exists; it is the task of the programmer to exploit it in the most efficient way. Since it is often the case that only one paralldization technique can be applied to an algorithm at a time, a careful examination of the algorithm must be made before a technique can be chosen. The speed up ratio, s, used for comparing the sequential alg? rithm with the parallel algorithm, is the time required for the sequential execu- tion divided by the time required for parallel execution. In the ideal case, 8 would be equal to the number of processors used in the parallel execution. Data partitioning is one technique which can be applied to many algorithms. Data can be partitioned in two ways : statically and dynamically. In static parti- tioning, the data to be processed is partitioned into p processes, where p is the number of processes. Each processor handles one group of data, and each proces- sor shares the same code. This type of partitioning is efficiently implemented on a SINID machine. Dynamic partitioning allows data to be subdivided between active processors, as in the tree machine. In some cases, computational partitioning can be performed on an algorithm. If several subprograms must be performed, and each of these subprograms is independent of the other subprograms, then each can be assigned its own proces- sor. These processors have their own code and execute independently, at their own speed. Moitra (1986) discusses a general technique for data and computation partitioning for obtaining distributed programs. If several processors must make changes on a certain variable, memory con- tention can be minimized through localization. To decrease the access to these shared variables, a copy of the variable is made in the memory local to a proces- sor. The processor uses this local variable to do its computations, then, if neces- sary, the global variable is updated at the end of the subprogram. It is possible, in some cases, to relax the control mechanism so that the parallel processor sys- tem is working asynchronously instead of synchronously. This method is called relaxation, and involves replacing explicit synchronization with implicit synchron- ization to provide more flexibility. Software pipeline is a software implementation of the pipeline machine dis- cussed earlier. Each processor behaves like a pipeline segment, with items being passed down the line from one process to another. An item is said to be con- sumed by process i when process i is finished with it; when an item is consumed -7- by process i, an item is produced for process i + 1. The output rate of the pipe- line is dependent on the time spent in the slowest segment of the pipe, since this forms a sort of bottleneck behind which other items must wait before they can be processed. It is therefore wise to divide the algorithm into a number of processes that require approximately the same execution time. Synchronization is done by software also, most often using shared variables. When a process has consumed an item, it may set a flag in the shared memory which the next process checks when it is free. If this flag is not set, meaning that the previous processes are not through with the item, the process continues checking the flag; essentially wait- ing until the item is available for processing. Synchronization cost can be said to be 0(1), since only two processes need to read or write into a given cell. To sum up, it can be said that the amount of parallelism which can be achieved is dependent on all the above factors, with emperical evidence indicating that the granularity of the processes and communication requirements are usually the most critical and time consuming for parallel algorithms. For excellent surveys see Kung (1980) for a discussion on the structure and characterization of parallel algorithms and Kuck (1976) where parallel processing of ordinary sequential programs is considered. 1.3 Computation Model Used Observation 1. The parallel architectures mentioned above have some inherent drawbacks, namely, the focus on a specific architecture does not provide insight into the logical structure of the algorithms. Further, it also makes the transfer of an algorithm to a different architecture difficult. Observation 2. Computational models for asynchronous parallelism are very abstract in nature (for example, Petri nets). This level of abstraction, while very powerful for structuring process interactions, oft?n hides the actual computation process of the algorithm and makes the analysis of execution difficult. Thus, there is a need for restricting ourselves to some specific but general model. Consequently, we will mainly use the SIMD-SM model (and its various submodels) for the purpose of this paper. This choice is a natural one since most parallel algorithms are indeed based on this model. 1.4 Faradigms For Organizing Computation The design of parallel algorithms involves choosing appropriate data struc- tures, allocating processors and finally the algorithm to do the computation. All these three aspects can be combined under the heading of compntation organiza- tion. Certain simple computation organizations are used frequently in the prob- lems solved in the literature and hence we will first identify these basic tech- niques in the form of paradigms. There are three paradigms that we will intr? duce for computation organization. -8- 1.4.1 Binary Tree Paradlgm Consider the problem of calculating a function F of n data items (d1,...,d?) If the function F is such that (d1,...,d?,?) can be calculated by combining the results F(d1,...,d?12) and F(d??12+ 1,...,d?) then we can organize the computation of F in the form of a binary tree. The data form the leaves of the binary tree and the computation proceeds in steps. The processors are assigned so that all the computation at a level can be done as one step (and the same processors are reassigned for the next step). For a problem of size n where n is a power of 2, the number of processors required for the entire computation is n /2 and if the processing at each step takes c units of time then the entire computation takes c*log n units of time. A simple illustration of this technique is the problem of computing the sum of n numbers which uses 0(n) processors and requires O(log n) time. In the above description notice that the computation proceeds from the leaves to the root and that the entire problem is solved when the processor at the root does its computation. Most of the problems that are solved using the binary tree method are of this form. However, the binary tree method is more general, Dekel, Sahni (1983a), and lends itself to problems in which a number of passes over the computation tree have to be made, each odd pass from leaves to the root and each even pass from the root to the leaves. A simple illustration of this idea is the partial sums problem where = dj, 1 < j < n is to be calculated. Notice that in the first pass of the computation tree not all the S1,s are computed, but the remaining Sj'5 can be computed by making the second pass from the root to the leaves. In the second pass, each vertex transmits to its children the sum of all the values to the left of this child. 1.4.2 Growing by Doubling In the binary tree method, the first pass can be visualized in another way. At each step a (active) processor doubles the number of elements for which it has calculated the function F. Hence `growth' is achieved by doubling at each step. There are other ways in which this type of doubling technique can be used even when there is no binary tree structure associated with the problem. A simple illustration is the problem of counting the number of elements in a linked list. This is done by associating a processor with each element of a list which main- tains a pointer to an element further down the list; and at each step will double the distance its pointer spans by setting its pointer to the value of the pointer belonging to the element pointed to on the previous iteration. 1.4.3 Spanning Tree ror Graphs A very important class of parallel algorithms present in the literature are graph theoretic. A large majority of graph-theoretic problems are solved sequen- tially by first finding a depth-first spanning tree. However, the construction of depth-first spanning tree seems to be inherently sequential and hence cannot be -s done efficiently in a parallel model. Consequently, most of the sequential algo- rithms based on depth.first spanning trees are rather different from their parallel counterparts. One way that graph theoretic problems relying on depth-first spanning tree are converted into efficient parallel algorithms is by making use of any spanning tree (Tarian, Vishkin, 1984). In general, an algorithm based on any arbitrary spanning tree is more complicated than the one based on depth-first spanning tree, but this is a price that must be paid to obtain efficient parallel algorithms. We now describe the spanning tree construction of Tarian, Vishkin (1984) which is based on the connectivity algorithm of Shiloach, Vishkin (1982). Each vertex v has a pointer field D [v] through which it points to another vertex or itself. The algorithm proceeds in a number of iterations. Initially, D [i] = i for i=1, .., n; i.e. all vertices are in component trees by themselves. At any itera- tion, the graph is always a forest of rooted trees plus self-loops that occur only in the roots, each one of these is called a D-tree. The algorithm proceeds by hooking one tree onto another, this has the effect of decreasing the number of trees as well as increasing the size of individual trees. For efficiency, each rooted tree is kept so that each vertex is connected directly to the root and since the process of hooking violates this condition the algorithm also performs path compression or shortctttting in which a vertex is brought closer to the root. The D-pointers are therefore changed by two kinds of steps Step 1. Shortcutting: D[i] = Step 2. Hooking: D[D[i]j = D[j], where D[i] is the root of aD-tree and j is a vertex in another D-tree and (i,j) is an edge in the graph. That is trees are hooked together. At this point simultaneous writing to the same location is used and it does not matter which one succeeds. The edges used in the hooking step correspond to the edges in the spanning tree. This algorithm runs in O(log n) time using O(n+ m) processors. 1.5 Paradigms for Improving E?ciency of Puallel Algorithms The efficiency of any parallel algorithm A is measured by defining what is known as the effective processor tttitization or EPU defined as EPU = complexityofthefastestsequentialalgorithmforproblem number of processors used in A * time complexity of A Note that 0 < EPU < 1 and that an EPU equal to 1 is the best possible and corresponds to maximum speed up possible. As an illustration, the EPU for the n 1 sum of n numbers algorithm in the previous section 15 n * log n log n In any parallel algorithm there is always a trade off between the number of processors and the computation time (within some limits). For instance, for any 10 algorithm a new version may be obtained by allocating the processing of a number of processors to a single processor, thereby reducing the number of pro- cessors required at the expense of computation time. But notice that for any such simple scheme the EPU remains constant. However, there are times where reallocation of the processing to the proces- sors can be done in such a way as to increase the EPU of the new version of the existing algorithm. We describe two such general techniques below. 1.5.1 Processor Reduction Without Increasing Time Complexity Consider the problem of finding the sum of n numbers discussed before. Suppose p < n /2 processors are available. Then to compute the lowest level sum would require at most r n /2p 1 time, the next higher level would require at most Fn/4p 1? and so on. The total time T required satisfies T < F--H?1+ r--H?1+ + 1 2p 4p p n n n --H 1 + + 1 + + + 1 + 2[log flip lon ni 1 1 --H(--H+ --H+ + 2[logn?1 --H g ?2 4 < c1*log n + n _ c2*--H p O(log n + p __ n Notice that we can obtain a running time of 0 (log n) if p --H log n That is we have reduced the number of processors required while keeping the same time complexity. This type of improvement can be made for a number of problems and we call it the processor reduction or PR paradigm. 1.5.2 Time Complexity Reduction Without Increasing The Number Or Processors Consider again the problem of finding the sum of n numbers. This problem, as we had indicated above can be solved recursively by adding the sum of two smaller list of numbers. This recursive structure was reflected in the algorithm of the previous section where the recursion was unraveled all the way down. We now show how the time complexity can be reduced by unraveling the recursion only part of the way down; and this will be done in such a way as to not increase the number of processors required. Let the recursion be unraveled until we are left with blocks of size r whose sum has to be computed. Now for each block we can allocate one processor to obtain the sum in time O(?). The number of such blocks is nlx and hence the computation time required is - 11 - T = O(r + log To minimize the time we require that ? = log to give us n = x*2:. So when n = x*2: we can compute the sum of n numbers in time O(log 2:) and the number of processors required is 2:. We call this technique the time reduction or TR paradigm and another example of its usage is a sorting algorithm in llirschberg (1()78). Notice that this technique allows us to decrease the time complexity as well as the number of processors required from that required in the algorithm of the previous section. Also, this technique yields a faster algorithm than the one by the PR paradigm, however this speed up is at the expense of the number of prc- cessors. However, for both of the algorithms in this section the product of the number of processors and the time complexity is the same; that is n using paradigm PR, number of processors * time complexity log n *log n = n using paradigm TR, number of processors * time complexity = log 2: *2: --H Z*2: = n Further, for both the algorithms obtained in this section the EPU = 1; the best possible that can be achieved theoretically. There are two different assumptions that can be made about the number of processors available. Under unbounded paralletism, arbitrarily many processors are assumed to be available. Under bounded parallelism, a limited number of pr? cessors, independent of the problem size, are assumed to be available. 1.6 Organization And Scope Of The Paper Section 2 present a survey of parallel algorithms for finding the connected and biconnected components of a graph. Section 3 discusses the various parallel algorithms for the minimum spanning tree problem. Section 4 discusses various other parallel graph algorithms for shortest path, maximum matching, planarity testing, maximal independent set etc. Section 5 considers parallel algorithms for various non-graph theoretic problems like arithmetic expression and polynomial evaluation, string matching, tree balancing and alpha-beta search. Finally, sec- tion 6 presents some conclusions. In our treatment of parallel algorithms, we have excluded discussIon on sort- ing and numerical algorithms as well as any algorithms for vLSI and systolic arrays. An extensive amount of literature exists for parallel sorting and numerical algorithms. For instance, Bitton et al. (1?84), Chen (I()75), Dekel et al. (1981), Gentleman (1978), Lakshmivarahan et al. (1984), Sameh (1977). Kuck (1977) deals with parallel machine organization and programming; while Kuhn, Padua (1981) contain a collection of papers dealing with parallel processor taxonomies, pipeline, dataflow and array processors, compilers for translating sequential pr? grams into parallel ones, operating systems for parallel computers etc. Lee et al. 12 (1()85) deal with implementation details required for restructuring various nonnu- merical programs for parallel processing. The parallel algorithms we discuss are all deterministic. even though numerous randomized algorithms exist in the literature. Randomization can often achieve better efficiency then deterministic algorithms. The study of random algorithms is of current research focus and a lot more work needs to be done in this area. In this paper we have attempted to give a survey of parallel algorithms for a class of computational problems. Undoubtedly, some algoritbm may have been overlooked, but any such omissions were unintentional. 2. Parallel Connectiyity Algorlthms 2.1 Parallel Connected Components Algorithms The various parallel algorithms for fmding the connected components of undirected graphs can be broadly classified according to two major criteria - the basic technique employed and the format of the input. The basic techniques used in these algorithms have been breadth-first search, transitive closure and vertex collapse. The most common form of the input is adjacency matrix. The popular- ity of the adjacency matrix form of input in general stems from the fact that it allows graph theoretic problems to be stated and solved in terms of matrix mani- pulation problems. This works very well for dense graphs, but for sparse graphs this may lead to inefficient algorithms and so quite often input in the form of adjacency lists is used. While most of the algorithms for finding connected com- ponents are very general, some of them are more suitable for sparse or dense graphs. As we shall see, this extra information about the sparsity of graph allows for more efficient allocation of processors. 2.1.1 Breadth-first Search Miomandi, Corneil (1975) have proposed a technique for finding the con- nected components of a dense graph based on a breadth-first search of the given graph. The search starts from a vertex and processors are assigned to edges emanating from that vertex. A vertex at a distance of i from the start vertex is searched before any vertex at a greater distance from the start vertex. After all the vertices at a distance i have been searched, the partial lists of all the new vertices at a distance i + 1 are joined together so that a new vertex at a dis- tance i + 1 can be picked efficiently for searching. When the average degree of each vertex in the graph is approximately greater than or equal to k, where k is the number of processors available, then the complexity of the resulting alg? rithm is near optimal and is T/k + L [log ki + 2n where T is the complexity of the optimal sequential breadth-first search algorithm and L is the distance of the vertex furthest away from the start vertex. 2.1.2 Transitive Closure The basic idea of connected component (sequential) algorithms based on transitive closure is as follows. If the input is in the form of adjacency matrix A then the transitive closure of A, call it B, can be obtained so that the element of B is 1 if and only if there is a path of length 0 or more from vertex i to vertex j in the given graph. The component number of any vertex i is then just the smallest j such that 6q = 1. The first parallel algorithm for finding the connected components based on transitive closure is due to Reghbati, Corneil (19.78). Their algorithm is essen- tially what is described above. On a SIMD-SM-R model the transitive closure of a n x n matrix can be obtained when n3 processors are available by squaring the matrix log n times which requires 0 (lo? n) time; finding the first nonzero entry - 14- for each row can be done in 0 (log n) time. Hence the complexity of the algo- rithm is 0 (lo? n) using n3 processors on an SIMI>-SM-R model. The other algorithms based on transitive closure improve upon the efficiency of the transitive closure step. In Chandra (1S76), the parallel matrix multiplica- tion algorithm is used thereby reducing the number of processors required from n3 to ?nlO?7/log ?1 In Kucera (i?82) a stronger model, SIMD-SM-RW model, is used. This allows n2 processors to find the minimum of a set of n elements in constant time and hence allows the transitive closure of a binary matrix and the connected components to be computed in 0 (log n) time using n4 processors. 2.1.3 Vertex Collapse The input format is again in the form of adjacency matrix. The basic idea is to combine adjacent vertices into `supervertices' which are then combined them- selves. This process is repeated ujitil no further collapses are possible; at which point each supervertex corresponds to a connected component. Some commonly used terminology is as follows. A tree-loop is a tree having directed edges with an additional edge from the root to one of its descendants. A club is a tree-loop in which all the vertices other than the root are the sons of the root. The first algorithm using the vertex collapse technique is due to Hirschberg (1976) and is presented below. The basic idea is to grow each connected com- ponent as a club with the root of the club being the vertex with minimal label in that club. Fig. 1 illustrates how this algorithm works. The algorithm proceeds by having each vertex identifying the smallest numbered vertex that it has seen so far which is in the same connected component (in Fig. 1 this relationship is indi- cated by solid arrows). Each iteration of the algorithm consists of three steps. In the first step, each vertex finds lowest-numbered (new) neighboring root. In the second step, each root is linked to the root of the lowest-numbered neighboring root. In the third step, path compression is done so as to construct clubs. I 8 5 7 4 a Iteration I Find lowest-numbered (new)neighboring root. Connect roots. Build new club. Smallest numbered vertex seen so for which is in the same connected component? Iteraflon 2 t% ? Find lOWest?numbered (new) ??Ihboring root. Connect roots. --H -- 8uild new club. FIG. 1. Vertex collapse. - 17 algorithm llirschberg; h?pttL Adjacency matrix A (n by nl OutpuL Vector D of length n such that D[xj is the smallest vertex y reachable from vertex x. begin 1. for all r do D[xJ=r; 2. for [log n 1 iterations do begin 3. for all x do C[zJ=min (D[y] A[x,yJ=1 and Dt?1#D[x1) if none then D[zj; 4. for all x do Ctxl=D[x]--H--Hmin (C[y] if none then D(]; 5. for all z do DfrJ=C[xJ; 6. for [log n 1 iterations do for all r do C(x]=C[C(xll; 7. for all x do Dfr]=min f ckj,D[ckl] ?; end; end; D[y]=z and CjyJ$x) Algorithm Hirschberg has time complexity 0 (lo? n) on n2 processors for a SIMD-SM-R model. Basically, both the path compression and finding the minimum requires 0 (log n) time. Also, since each iteration reduces the number of clubs corresponding to a connected component by a factor of 2 until a single club corresponds to a con- nected component, 0 (log n) iterations are sufficient for the algorithm. Hirschberg et al. (1079) improve upon the performance of the original llirschberg algorithm by recognizing that the number of processors required can be reduced without increasing the time complexity. The idea is very similar to what we outlined as the PR paradigm in 1.5.1 and amounts to having each pr? cessor assign values to log n elements instead of to one element and that each processor can find the minimum of log n values instead of finding the minimum of two values. Both of these changes can be accomplished without increasing the time complexity so the new algorithm has a complexity of 0 (lo? n) using n [n IF log n ?? processors on a SIMD-SM-R model. Chin et al. (1981, 1982) improve upon the algorithm of Hirschberg et al. This improvement is obtained by considering in any iteration only those vertices that are non-isolated supervertices. This implies that the number of active ver- tices is reduced by a factor of at least two after each iteration and therefore the same time bound 0 (lo? n) can still be achieved by using n [n /lo? ?1 processors on the SIMD-SM-R model. This reduction in the number of processors is essen- tially the PR paradigm. - 18 - Savage, Ja'Ja' (1?81) develop two parallel connected components algorithms that provide improved performances for dense and sparse graphs respectively. For an undirected graph G = (V;E) with ?Vj > 2, the diameter d of G is defmed to be d = max fd(v, w),2? V, W E V where d(v ,w) is the length of the shortest path from v to w if it exists, otherwise -00. The observation they made is that it is not necessary to run the Hirschberg algorithm for r log n 1 iterations; rather it should be run until two consecutive iterations produce the same result. In that case the running time of the algo- rithm can be made O(log n * min (log n,d/2) where d is the diameter of the graph. When d < 2 log n (i.e. for dense graphs), this algorithm is faster than the original. When the graph is dense this algorithm requires O(n3/log n) pro- cessors to obtain time complexity 0 (log n log d). When the graph is sparse, the number of processors required can be reduced by organizing the input in the form of adjacency list rather than adjacency matrix. Certain reorganization of the original llirschberg's algorithm then leads to an algorithm with time complexity 0 (log2 n) using 0 ( m + n log n) proces- sors where m is the number of edges in the graph. Nath, Maheshwari (1()82) consider the problem of finding the connected components on a weaker model, a model that does not permit simultaneous read- ing from the same memory location by different processors. Their algorithm is based on the one due to Hirschberg et al. (1970) but avoids read conflicts by organizing the intermediate data structure as a chain (which avoids read conflicts when children access nonroot parents) and by keeping multiple copies of data. This algorithm has complexity 0 (lo? n) with n2 processors on an SIMD-SM model. Shiloach, Vishkin (1082) consider a stronger model, S!MD-SM-RW, where simultaneous reads as well as writes are allowed. In the latter case one processor succeeds but which one is not known. This algorithm, SV, has complexity O(log n) using only n+ 2m processors where ? = m, and it is presented below. - 19 - algorlthm SV; input: Vertices are represented by the numbers 1,?.., n. The edges are represented by a vector E of length 2m in which each edge (i,j) appears twice once as the ordered pair and once as the ordered pair . Output: Vector Dg0 of length ?? ?o is the index of the last iteration. Du0[nJ is the representative vertex of the connected component containing vertex n. Processor allocation: If in, processor Pj is allocated to the ordered pair E[i--Hn] = (this proces- sor is denoted as Pj1, `2) 1. 2. 3. 4. 5. 6. begin if in then if Du [ii]=Du?i[ii] then if Du[i2]n then if D8 [i11=DutDu [ijjJ and Q[Du[i1Jj 0 do wait; for i=k to n by p do begin ri FIND[iJ; for j=1 to n do begin r2= FIND[jj; if ri $ r2 then begin 13. 14. 15. 16. `7. 18. end; a min fi,j); z= max lock( VminFr 1J); if ( W[i,j]< Vmin[r 1j) v (W[i,jJ= Vmin[r1] and W(a,z) < min fV?[r1J,V[r1jY) then begin Vj [r 1J=a; Vi.[rli=z; Vmin[r 1] W[i,j] end; unlock( V???[r1j); end; end; end; lock(over); over=over+ 1; unlock(over); - 2g - 3.2 Parallel Prirn-Dukstra Algorithm The minimum spanning tree algorithm was first developed by Prim (1957) and its computer implementation was given by Dijkstra (1959). The algorithm (we name it Prim-Dijkstra) works by starting with a forest consisting of n ise- lated vertices. Then a vertex is chosen arbitrarily from the forest to be the first vertex of the partial tree. Then, the tree is grown successively by bringing in the nearest neighbour from one of the isolated vertices. In other words, at an inter- mediate step an edge (t , v) is added to the current (partially formed) tree T if T u ((u,v)) is also a tree and (u,v) is the lightest weight edge with this pr? perty. This method is described in algorithm PRIM-DIJKSTRA. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. `3. 14. algorithm PRIM-DIJKSTRA; // this algorithm finds the minimal spanning tree for a given graph 1/ begin // initialization // T--H--H?; 7)v=0; NEAR [1]=0; ror i=2 to n do begin NEAl? ti]= 1; DIST[i]= W[1,iJ end; // iteration step 1/ while ITI0 do wait; k=1; ror i=j to n by p do ir(NEAR[ij $ 0) and (DIST[il < DISTIkI) then k=i; lock( Vmin); irDIST(kj < Vmin then begin m=k; Vmin= DISTIki; end; unlock( Vmin); lock( over); over=over+ 1; irover=p then begin T=Thf(m, NEAR[mj)?; Tw=Tw+ Vmin; NEAR !kI=0; over =0; end; unlock(over); while over >0 do wait; ror i=j to n by p do begin ir(NEAR[i] $ 0) and (W[i,mj ICP[E!ill do begin m=m+1; P[m]=STACK[topl; top=top- 1; end; top=top+ 1; STACK[topl=E!i]; end; while top>1 do begin m=m+ 1; P[m]=STACK[top]; top=top - 1; end; end; some pairs of matching parentheses and some parentheses whose matches are in other segments. The matching pairs within a segment can be identified by mak- ing one pass through the segment. For the remaining parentheses, their matches are found by performing a variant of binary search on a balanced binary tree that they construct. This parentheses matching algorithm is made use of as follows. In the origi- nal expression, parentheses are introduced so that all subexpressions become 51"'- ple expressions, where a simple expression is one in which all operators not enclosed by parentheses are of the same precedence. The parentheses matching algorithm is then applied to this expression. At this point the original problem of obtaining a tree form for the input expression has been reduced to finding the tree form of a number of simple expressions. This can be done in a - 45 straightforward manner and the result can then be combined to obtain the tree form of the original expression. Apart from the parentheses matching part, the remaining steps can all be done in 0(1) time using n processors and therefore in 0 (log n) time using n/log n processors. 5.2 Parallel Algorithins ror Polynomial Evaluation Polynomial evaluation is a fundamental and widely used operation and the problem of designing efficient parallel algorithms for it has received a ??eat deal of attention in recent years. A polynomial can be expressed in a variety of ways e.g. the Power form, the Root Product form, the Newton form and the Orthogo- nal form. For details on different representation, see Kronsjo (1S7S). Different representations lend themselves to different techniques for exploiting parallelism from the sequential polynomial evaluation algorithms. Munro, Patterson (1?73) developed optimal algorithms for polynomial evaluation which use large amount of parallelism. Their algorithm proceeds by defining a recursive evaluation procedure for the polynomial. They ignore all memory access problems and assume the existence of k identical arithmetic pro- cessors, each of which can perform any one of the binary operations of +, --H, * and I in unit time. A lower bound of 2n arithmetic operations has been shown to be required for the evaluation of a general n degree polynomial. When the degree of the polynomial exceeds k ?log ki then the Munro, Patterson algorithm is optimal within one time unit. Hyafil (1S78) presents a parallel evaluation algorithm of multivariate polyno- mials. Hyafil's algorithm shows that a polynomial P computed sequentially in n (+ ,--H, *? steps with a degree d can be computed in parallel time O((log d)(log n + log d)). The number of processors required for this algorithm is ?log d even when n and d are bounded polynomially, in terms of the number of indeterminates. Valiant, Skyum (i?81) present an improved version of the above algorithm for any multivariate polynomial. The time complexity is the same as that for Hyafil's algorithm but it uses only (nd)0(') processors. Another result that uses only a polynomial number of processors is the result of Csanky (1976) for evaluating the determinant. There are other types of parallel polynomial evaluation algorithms in the literature. Recently Bini, Pan (1985) developed parallel polynomial division algo- rithms by preserving the full efficiency of the best sequential algorithms. This algorithm divides two polynomials of integer coefficients of degree at most m and can be accelerated by a factor log m. They further show that all the known algorithms for polynomial division can be represented as algorithms for triangular Toeplitz matrix inversion. For improving the efficiency of the determinant and of the inverse of matrix see Pan, Galil (1985). Recent results on algebraic com- plexity of computing polynomial zeros is described in Pan (1985). - 46 - 5.3 Parallel String Matching Algorithins The string matching problem consists of finding all occurrences of a given pattern in a given text. Galil (1084) presents families of parallel algorithms for this problem. For the SIMD?SM-RW model (the only simultaneous writes allowed are when processors attempt to write 0 simultaneously), his algorithms can be summarized as follows. 2. 1. O(n/p) time complexity for any number of p < n/log n processors. 2. Constant time complexity for p < ? 1+ processors where E > 0. 3. Time complexity O(log n/log log n) for n processors. For the SIMD-SM-R model, he has an algorithm with 0 (n / p) time complexity using any number p < n lo? n processors. All his algorithms solve the problem under the assumption that both the pattern and the text is over a given alphabet of fixed size. He develops these fam- ilies of algorithms by first presenting a non-optimal (0 (log n) time with 0(n) processors) solution for the special case when the length of the text is twice the length of the pattern. Then he shows that the number of processors required can be reduced to O(n/log n) by using the four Russian trick (Aho et al. 1074). Finally, he shows how the restriction on the lengths of the pattern and text can be removed and still maintain optimality by appropriate assignment of proces- sors. The resulting algorithms can then be modified to obtain optimal algorithm for the SIMD-SM-R model with the performance described above. Vishkin (1085) also presents optimal parallel algorithm for this problem. His algorithm has time complexity O(n/p) for any number p < n/log n processors on a SIMD-SM-RW model. (In this paper, the smallest numbered processor attempting to write succeeds; but in a future paper they show that these results are valid when simultaneous writes are allowed only if the processors attempt to write the same value.) In contrast to Galil's algorithms, the symbols are not con- strained to be taken from an alphabet of fixed size. Briefly, his algorithm works as follows. 1. Analyze the pattern so as to compute the following table. The ith entry in the table will indicate either that the suffix starting at position i of the pat- tern is a prefix of the pattern or not (in the later case it provides a coun- terexample). This table allows us to infer for appropriate indices, j1 and j2 in the text that an occurrence of the pattern can not start at both j1 and j2. Therefore a sparse set of indices where an occurrence of the pattern may start can be obtained. 3. A character by character test is applied to the indices obtained in the previ- ous step to determine whether an occurrence of the pattern in fact occur at those locations. - 47. 5.4 Parallel Tree Balancing Algorithms The task of balancing a binary tree is to adjust the left and right pointers of the vertices in the tree so that the height of the tree is minimized. In Moitra, Iyengar (1986), an optimal parallel algorithm for obtaining route balanced binary trees is derived. (In a route balanced binary tree all the leaves at the highest level are located at the leftmost side of the tree.) In this section unless otherwise stated, a balanced tree will mean a route balanced binary tree. The balancing algorithm is systematically derived by starting from a recursive algorithm and transforming it first into an iterative algorithm and then into an optimal parallel algorithm. This parallel algorithm has time complexity 0(1) with n processors on a SIMD-SM model and can be described as follows. The algorithm has two parts; in the first part a parallel inorder traversal of the binary tree is performed and the result is stored in an array LINK. In the second part, a balanced tree is built from the array LINK. The parallel traversal can be done in constant time if additional information is stored with each vertex giving the number of vertices with values less than or equal to its own value. To describe the building up process, we introduce some terminology. Let 'th vertex refer to the jth vertex from the left on the ith level if it exists in a binary tree. Mso, let VALN() denote the number of vertices with data values less than or equal to data value of the vertex in a balanced tree of size N. It can be shown that VALN() = min (VAL2?4(),[VAL2??1()+ N-S+ 1]/2) where n=?log(N+ 1)1, VAL2?4() = 2?4+(j--H1)*2?4+1 and S=2?--H1-N This gives a method of determining which cell in the array LINK corresponds to the th vertex in the final balanced tree. To construct the balanced tree, a processor ?K is associated with LINK[KJ and it must do the following Cl. determine i, j such that VAL?()=K; that is its final position in the balanced tree. C2. if it has a left son then determine Ki such that VALN()=Ki C3. if it has a right son then determine K2 such that VALN()=K2 Computations C2 and C3 can be easily done in constant time once computation Cl has been done. For simplicity consider the computation Cl when N=2?-l. Note that if processor ?K is allocated to process the vertex with VAL equal to K then ?K may correspond to different indices , M=l, 2, .. depending on the size of the balanced tree. However, the values fl-i and j are invariant over the size of complete balanced binary tree as shown in Fig. 2. 4 2 6 I 3 5 7 (a) vertex with value 6 has j=2, n--Hi=2 8 12 1 3 5 7 9 11 13 15 (b) vertex with value 6 has j=2, n--Hi=2 FIG. 2. Vertex identification that is invariant over size of complete balanced binary tree. - 49 - So, if the values fl--Hi and j are permanently associated with each processor, then computation Cl can also be done in constant time. Building up the bal- anced tree is given in algorithm COM-BAL. 1. 2. 3. 4. 5. 6. 7. 8. 9. algorithm COM-BAL; // parallel growing algorithm for the construction of a balanced tree by /1 /1 simultaneously executing processes ?i, ?` ?N, one for each cell in the // 1/ array LINK, where N=2?--Hl /1 begin ror each `)K do in parallel /1 h, j associated with each ?K 1/ begin n=?log(N+ `)1; if odd (K) then I/leaves /1 begin LSON [LINK [Kl] null; RSON [LINK [KJJ=null; end; if even (K) then I/interior vertices // begin LSON (LINK [Kil LINK 1K-2? `?-`J; RSON (LINK [K]]=LINK (K+ 2n?I?11; end; end; end; For arbitrary binary trees, cell LINK [K] may correspond to different indices and with i$i' and j$j' as the size of the tree changes thereby making computation Cl expensive. The computation can however be reorganized so that a processor ?A' sets up links for LINK (hi where h =min fh',(h'+N--HS+lJ/2? This allows for a simpler calculation of indices . However, a direct imple mentation of this idea would require the use of 2??l processors where n =?log (N+ 1)1 for a tree of size N. To reduce the number of processors so that only N processors are required to grow a tree of size N further reorganiza- tion of the computation has to be done. All the details are presented in alg? rithm BAL. The result presented above can be extended to balance m-way trees as dis- cussed in Dekel et al. (1985). - 50 - 1. 2. 3. 4. 5. 6. 7. 8. 10. 11. 12 13. `4. `5. 16. `7. 18. 20. 21. 22. algorlthm BAL; // parallel growing algorithm for the construction of a balanced tree by // // executing simultaneously processes Pi? ?` ?N // begin for each ?K do in parallel begin n=?log(N+ `)1; i=n--Hh; S=2?--H1--HN; K=2?-' + (j--H1) *2fl-i+ 1; K' =(K+ N--HS+ 1)/2; if K' >K then K' =K; /1 K'=VALN() /1 If odd (K) and (K=K') then //leaves on the highest level // begin LSON [LINK [K' ]]=null; RSON (LINK 1K' 11 =null; end; if odd (K) and (K $ K') then // reorganization of computation II begin K=K+ S; K' =(K+ N-S+ 1)12; if K'>K then K'=K; end; If even (K) then begin K1--H2?4+ 1+ (2*j?2)*2?? I/set up left link /1 K1'=(K1+ N-S+ 1)/2 if K1' >K1 then K1'=K1 /1 K1'=VALN() // ifodd(K1) and(K1$Kl') //odd(K1)?K' on level n--H1// then LSON[LINK[K' j]=nu1? else LSON[LINK[K' ]]=LINK[K1' 1; K2--H2?4-'+ (2q??)*2n?I // set up right link II K2' =(K2+ N-S+ 1)/2 if K2' >K2 then K2'=K2 II K2'=VALN() 1/ if odd (K2) and (K2 $ K2') 1/ odd (K2) ? K' on level n--H1 // then RSON[LINK[K' J]=null else RsoN[LINK[K' j]=LINK[K2']; end; end; end; - 51 - 5.5 Parailelism In Alpha-Beta Algorithms Efficient search of trees is fundamental to many areas of study such as Artif- icial Intelligence, Operations Research and Computer Science at large. Most M problems, especially game playing programs use heuristic information to direct the search that is relevant to the goal. It has been well documented in Berliner (1978) that an important component of search trees in game playing is the speed at which the search is conducted. The focus of this section is to explore parallelism in alpha-beta search algorithm used extensively in game trees. We first present definition necessary for the for- mulation of alpha-beta search algorithm (Knuth, Moore 1975, Nilsson 1980, Sla- gle, Dixon 1969, Pearl 1982). Then we describe a technique developed by Finkel, Fishburn (1982) to exploit parallelism in alpha-beta search algorithm. 5.5.1 Definitions And Formulation Or Alpha-Beta Search Algorithm Decision and game trees have been extensively used in M problems such as chess playing programs. However since the size of decision or game tree encoun- tered in such problems is very large, it becomes physically impossible to com- pletely search a tree. Thus it becomes important to develop an efficient method for searching and/or pruning the tree; for more details see (Knuth, Moore 1975, Nilsson 1980, and Slagle, Dixon 1969). We restrict the word game to mean a two person, zero sum, perfect informa- tion The play strictly alternates between two players. Each player, on his move is allowed to choose a move from only a finite number of possible moves. The game is characterized by a set of positions and by a set rules for moving from one position to another. If from a given state or position P, a player is allowed to move to any of the possible ?i, ?` ?k positions, then in the corresponding game tree, one would find a connecting branch from vertex P to each of the P1, ?k vertices. There are two procedures for assigning a static value to the vertices of a decision or game tree. They can be described as follows 1) Minimax procedure 2) Negamax procedure In minimax procedure even level vertices (0, 2, 4, ..) (the root is at level 0) are called MAX vertices and odd level vertices (1, 3, ..) are called MIN vertices. Playerl moves from MAX vertices and player2 moves from MIN vertices. Note that this notation of naming the vertices and assigning each player to even or odd vertices is arbitrary and is chosen by convention. Having named the vertices, a static evaluation function is used to preassign a value to the terminal vertices. After assigning these values, the values for all other non-terminal vertices up to the root are calculated. The procedure used is as follows For each MAX vertex, the value assigned is the maximum value of it's sons. For each MIN vertex, the value assigned is the minimum value of it's sons. - 52 - This procedure is repeatedly used untll the value of the root vertex is calcu- lated. The thinking behind this procedure is that each player wants to maximize its own gain and minimize it's loss to the other player. In minimax procedure we always evaluate the game position from any one of the player's viewpoint. In the negamax procedure there is no differenciation between MAX and MIN vertices. It assigns a static value to a terminal vertex say I (p) from the point of view of a player whose turn it is to make a move. The value from the other player's point of view is --H1(p). If there are more than one possible moves, one needs to select the best move, which will result in the greatest possible gain when the game ends. Thus the value assigned to a non-terminal vertex is the maximum of negative of it's sons. Remember that the value assigned to a terminal vertex is from the point of view of player whose turn it is to make a move and that the players strictly alternate. Negamax approach is useful when it is undesirable to deal with two or more separate cases. 5.5.2 Pruning Strategy Having described the basic background material, let us now describe one of the possible pruning strategy. As remarked earlier the size of a decision or game tree is extremely large in most M applications, making pruning desirable. The basic thinking behind pruning is as follows : if we can somehow determine that a given vertex can never improve the value of it's parent, it is not necessary to con- tinue the search beyond that vertex. The subtree below that vertex can be cut- off, thus pruning the entire tree. It is obvious that the negamax procedure as described above is not efficient as it makes no attempt to use the information content of vertices processed ear- lier. Thus our line of thinking should necessarily include the use of that informa- tion to improve the basic negamax procedure. We illustrate this point by the example in Fig. 3 in which we use the information available from earlier vertices to prune the tree. In Fig. 3(a) the negamax procedure tells us that m = max ( 3 , -n where n = max (-2, .. Hence n > -2 and so whatever may be the value of n, we will always get rn = 3. Thus we need not search the vertex n and everything below vertex n. This gives shallow cutoffs. Following this argument for more than one level gives us deeper cutoffs. Consider the subtree below and inclusive of vertex k in Fig. 3(b) where k = max (-j, .. ? and j = max ( -2, .. ?. This gives us two possible cases, viz k > -j or k = Consider k > -j. This means that the value of k is not determined by ver- tex j but is determined by siblings to the right of vertex j. Thus subtree rooted at vertex j can be cutoff. Consider k = -j. Since j > -2 we get k < 2. Now n > -k and therefore -n < 2. Since m = max (3,-n) and -n < 2 we get m = 3 which is indepen- dent of value of n. Thus the subtree rooted at vertex n can be cutoff. 2 (a). Shallow cutoff. FIG. 3. Pruning of search tree. (b). Deeper cutoff. 5.5.3 De?mition OrAlpha-BetaBounds Previous examples illustrate that by using the information obtained from earlier vertices, we can prune the decision or game tree to a considerable extent. Using two bounds a and 4, we get the Alpha-Beta search algorithm as described by Knuth, Moore (1975). 1. 2. 3. 4. 5. 6. function alphabeta (p : position; a , 4: integer) : integer; var i, d : 1..MAXCHlLD; st'cc : array [1..MAXCHILDJ ofposition; begin determine thesuccessor position S'LCC(1], .., 8flCCtd]; if d = 0 then return (static?value (p)); for i = 1 to d do begin 7. a = max (a, - alphabeta(succtil,-Pra)J; 8. ifa > 4then return (a); end; 9. return (a); end; /1 terminal vertex // // cutoff /1 - 54 - lows a) c) We can thus summerize the characteristics of the function aiphabeta as fol- For a given position p and for values of a, ? with a < ? 1) if negamax(p) < a then aiphabeta (p,a,P) < a 2) if negamax(p) > p then alphabeta (p,a,P) > fi 3) if a < negamax(p) < p then aiphabeta (p ,a,fl) = negamax(p) The pair (a,P) is called the window for the search. The alpha-beta search algorithm is strongly serial in the sense that the ear- lier work is used in deciding cutoffs at the later stages. 5.5A Parallelization OrAlphmrBetaSearch Algorlthm Attempts aimed at a parallel version of alpha-beta include parallel "aspira- tion search" by Baudet (1()78), "mandatory-work-first" by Akl, Barnard, Doran (i?82), tree splitting algorithm by Finkel, Fishburn (1082) and Kumar, Kanal (1984). We now look more closely at the algorithm of Finkel, Fishburn. Finkel, Fishburn (1082) present a parallel version of alpha-beta search algo- rithm. This tree splitting algorithm speeds up the search of a large tree of poten- tial continuations by dynamically assigning subtree searches for parallel execu- tion. The root processor evaluates the root position. Each of the interior proces- sors evaluate the position assigned to it by generating successors, queuing them for parallel execution to it's slave processor. A processor tree is used in the execu- tion of this parallel algorithm. Thus a processor which is at the kth level in the processor tree corresponds to the position at level k in the lookahead tree used by the game playing expert system. The terminal processor evaluates it's position using a serial alpha-beta algorithm. Thus on completion of it's slaves evaluation (or at cutoff) the master can evaluate it's position. The masters inform their working slaves about the updated narrow window as it receives information from it's slaves. As is clear from the above discussion, there are two algorithins viz. the leaf algorithm and the interior algorithm. We now describe these algorithms in more detail. 5.5.5 The LeafAlgorithm We can describe the interaction of algorithm Leaf with its master either by remote procedure calls or by message passing/shared memory form. In the algo- rithm described below the master calls the function leafa? remotely (line ii) and interrupts the active slaves, to inform them of updated windows, by invoking the asynchronous procedure update (line 2). 5.5.0 TheInteriorAigorithm As we described earlier, the slaves report to the master. The creation and co-ordination of the slaves is done by the master. We now give this algorithm and discuss how it works. - 55 algorithmLeaf; 1. ?,fl: array (1..MAXDEPTHJ ?rinteger; II global arrays /1 2. asynchronous procedure update(newa,newfl: integer); // the asynchronous procedure update is called by my master to// // inform me ofnewwindow (new?, newfl) // 3. var tmp : integer; 4. k : 1..MAXDEPTH; 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. begin ror k = 1 to MAXDEPTHdo begin alki = max f?[kJ,netu??; Ptki = min (fl[k],newP); newCL tmp = newCL = - new?; newP =-tmp; 1/ update /1 end; end; runction leaf??p : position; ?,P: integer): integer; begin CL(11 = CL; P[11=P; return(alphabeta(p,1)); end; // update arrays CL and P /1 runction alphabeta(p : position; depth : integer): integer; var S'LCC : array [1. MAXCIlILD] ?rposition; // successors S'LCCflO : 1. MAXCIlILD; // whichsuccessors succlim : 1..MAXCHLD; // how many successors begin determine the successors S'LCC [1], .., 8'LCC [sttcclim]; irsncchm = 0then return (static?value(p)); ror S'LCCflO = 1 to s'tccllm do begin // evaluate each successor ?[depth + 1] = -P[depth]; P[depth + 11 = -a[depthj; a[depth] = max fa(depth], -alphabeta(succ [8ttccnol,depth+ 1)); ifaldepthl < P[depthl then return(?[depth]); acutoffhas occurred 1/ end; I/for s'Lccno return (a(depth]); end; II alphabeta // - 56- algorithm interior; 1. var g lot, g 1(3: integer; 1/ global variables // 2. q : integer; // variable used for the depth of tree // 3. asynchronous procedure update(newot,new(3: integer); /1 update is called asynchronously by my master to inform me of the /1 new window (newot, new(3) // begin 4. atomically do begin 5. glot = max (glot,newot); 6. giP = min (g1(3,new(3?; end; II of atomically do // 7. for all slaveid do slaveid.update(-g l(3,-g lot); end; II update/I 8. function interiorot?p : position; ot,(3: integer) : integer; g var sttce : array [l..MAXcIllLD1 of position; I/for denoting successors 10. snccno : l..MAXCmLD; I/the number of successors 11. attcclim : l..MAXCHILD; // limit on number of successors 12. tmp : array ?1..MAXCIllLD] of integer; 13. g : integer; begin 14. g lot = ot; g 1(3 = (3; 15. determine the successors sncc [11, .., 8'LCC ts?cc!im]; 16. if sttcclim = 0 then return(static?value(p)); 17. if depth(suec[11) < q 18. then g = interiorot(3 lS. else g = leafot(3; 20. parfor snccno = 1 to succijin do /1 parallel operation 1/ begin 21. slaveid = idle?lave(); 22. if glot < g1(3then begin 23. tmp !sttccno J.slaveid.g(succ [snccno 1,-g 1(3,-g lot); 24. if tmp[enccno] > glotthen begin 25. atomicaily do glot = max (tmp[succnol,glot); 26. for all slaveid do slaveid.update(-g 1(3,-g lot); end; end; end; 1/ of parfor /1 27. return(glot); end; 1/ interiorot(3 1/ - 57 - The interior algorithm generates all successors of the position to be evaluated (as indicated in line 15). If there are sufficient number of slaves avail- able, then each slave is assigned to evaluate one of the position. Otherwise a queue Is formed. Mthough there are several ways of forming the queue, the queue is implemented as a parallel for loop (starting at line 20). One of the following action is taken when one of the slave returns: 1) If the returned value causes the value of current a to increase, then all active slaves are informed of the updated value (line 26). 2) If a increases beyond p then a cutoff has occurred. Since a non-positive updated window is now sent to slaves (line 26) the slaves get terminated. The queue of waiting successors positions (line 22) is emptied. a update interrupt from the master, the new window is transmitted to slaves. 3) On the When all successors are evaluated, the final value is returned to its master (line 27). 5.5.7 Optimizations There are several ways in which this algorithm can be optimized. These can be listed as follows 1) Majority of the time, a master is waiting for messages from the slaves. Hence this waiting time can be used for subtree searches. However since slaves have further slaves below them to help, masters are slower than slaves. Hence only deep masters can use this optimizations. 2) One can group several higher level masters onto a single processor. 3) The root processor can send a special window (-a-1,a) instead of (-P,-a). The narrower window speeds up the search. Finkel, Fishburn (1S83) discuss some improved speed up bounds for parallel alpha-beta search. 6. CONCLUSIONS The design of parallel algorithms for various parallel computer architectures is motivated by factors such as speed and the need to solve complex problems of practical interest. With the continuing decrease in hardware cost, the objective is to trade the number of processors for a gain in computational speed. The advent of commercial multiprocessors has sparked off considerable interest in the study and development of parallel algorithms. An extensive study of parallel algorithms for useful computational problems calls for a systematic and thorough investiga- tion of research efforts spanning over a decade. The attempt we have made here is to illustrate and emphasize the following aspects 1. The need to systematize the study of parallel algorithms and the design pr(>? cess. 2. To survey the various techniques employed in exploiting the inherent paral- lelism in problems. 3. To unify parallel algorithms by means of well-defined paradigms. 4. To present a bird's eye-view of some of the current research efforts in the area of concurrent algorithms. These are expected to result in a better understanding of the working as well as the development of parallel algorithms. In view of the ongoing Fifth Genera- tion Computer Project and the increased use of high speed super computers, a detailed study of the techniques for the design of parallel algorithms becomes quite important. Due to the growing number of parallel computer architectures and the alg? ritlims developed on these for a large class of problems, it has become increas- ingly difficult for a user to select a particular parallel algorithm for any given application. In fact, we feel that such a choice is usually decided by factors such as ease of implementation of the algorithms and cost-effectiveness of the comput- ers. What best could be done under such circumstances is to identify some of the inherent features of the parallel algorithms which are invariant and base one's judgement on a critical analysis of these. The notions of time and space complexity carry forward from the sequential algorithmic domain and are indeed helpful in making an appropriate choice of a parallel algorithm. But it is often difficult to analyze the complexity of parallel algorithms on MIMI) machines because of the close interleaving and the indeter- minacy of communication and synchronization costs. Such asynchronicity has benefits in the form of the ease of design of parallel algorithms, usually from an efficient sequential version, and more generality. The synchronous models of parallel computation such as the SIMI) machines have come to be accepted as useful models because of their simple structures and amenability to formal analysis. In fact, the complexity classes with regard to parallel computation have been mostly for the synchronous models of computation. Still, it should be observed here that unlike in the case of sequential algorithms there is no `satis- factory' model of parallel computation. - 59 - A large number of results on developing efficient parallel algorithms have enriched the complexity classes and thrown open newer issues. The notion of P- completeness is a useful analogue of NP-completeness in the sense that just as deterministic polynomial time sequential algorithms are unlikely for NP-complete problems, polylog parallel time algorithms are unlikely for P-complete problems. The class NC (Nick's class) characterizes the problems having efficient parallel algorithms. Though it is known that NC is a subset of P, it is widely believed that the inclusion is proper. Problems such as depth-first search, unification etc., are examples of problems in P but not known to be in NC. Further they are not likely to be in NC, because they have been shown to be P-complete. The question is whether P-complete problems can be efficiently parallelized in some sense. Recently, Vitter, Simons (1986) have proposed some new complexity classes for parallel algorithms called PC and PC*. These classes of problems do not have a speedup comparable to those in NC. The speedup is usually by a constant factor or proportional to the number of processors used. Another important point to be observed is that, the parallel algorithms in the literature have been mostly on problems in P. This is understandable since for NP-hard algorithms we cannot devise a polynomial-time parallel algorithm with a polynomial number of proces- sors, unless P = NP. Browning (see Mead, Conway 1980) has proposed a tree machine with an exponential number of processors and using this he has developed polynomial-time algorithms for some NP-complete graph problems. It is to be borne in mind that quite a large number of useThl problems are NP- complete. Though we cannot expect to achieve a significant speedup by parallel algorithms for these problems, such a study has not been undertaken so far in a systematic way. It is possible to achieve some useful results in the speedup for these problems using polynomial number of processors. Research efforts are needed in this direction. We can view the paradigms discussed here at two different levels: (i) abstract level and (ii) concrete level (relatively). At the abstract level the para- digms for the design of parallel algorithms can be split up into three categories. 1. Parallelizing existing sequential algorithms, 2. Deriving by formal means a parallel algorithm from a sequential algorithm (this is a special case of (1) above and the emphasis here is on the derivation technique), and 3. By using elegant characterizations and identifying computationally efficient properties. Under this setting, almost all the NllN1SD algorithms fall in category (1). This includes the algorithms of Prim-Dijkstra and Kruskal for the minimum spanning tree problem. Aigorithms such as the parallel connected components, parallel biconnected components, maximum matching, maximal independent set fall into the category (3). Parallel algorithms for balancing trees of section 5 typify category (2). At the concrete level we discuss paradigms like the binary-tree method, growing by doubling and spanning trees for graphs. We also have substantiated these techniques with suitable examples. We would like to emphasize here that there is no universal method for designing -60 - parallel algorithms. Usually the trick lies in identifying the right formulation of the problem amenable to parallelization and the use of one or more of the tech- niques we have elucidated. -6i- Re?erences Aho, A., Hopcroft, J., and Uliman, J. (1974). "The Design and Analysis of Com- puter Algorithms." Addison-Wesley, Reading, Massachusetts. Aki, S.G., Barnard, D.T., and Doran, R.J. (1982). Design, analysis, and imple mentation of a parallel tree search algorithm. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-4, 192-203. Ariomandi, E., and Corneil, D.G. (1975). Parallel computations in graph theory. Proc. of the 16th Annu. Symp. on Foundations of Cornput. Sci., 13-18. Atallah, M.J. (1984). Parallel strong orientation of an undirected graph. InI. Process. Lett. 18, 37-39. Atallah, M.J., and Kosaraju, S.R. (1985). A generalized dictionary machine for VLSI. IEEE Trans. Comput. C-35 (2), 151-155. Atallah, M., and Vishkin, U. (1984). Finding Euler tours in parallel. J. of Comp. and Sys. Sci. 29 (3), 330337. Awerbuch, B., Israeli, A., and Shiloach, Y., (1984). Finding Euler circuits in loga- rithmic parallel time. Proc. of the 16th Annu. ACM Symp. Theory Cornput., 249-257. Awerbuch, B., and Shiloach, Y., (1983). New connectivity and MSF algorithms for Ultracomputer and PRAM. Proc. 1983 Int. Conf. on Parallel Process., Aug 1983, 175-179. Bar-On, I., and Vishkin, U. (1985). Optimal parallel generation of a computation tree form. ACM Trans. Program. Lang. Syst. 7(2), 34?357. Baudet, G.M. (1978). The design and analysis of algorithms for asynchronous multiprocessors. Ph.D. dissertation, Dept. of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania. Bentley, J.L. (1980). A parallel algorithm for constructing minimum spanning trees. J. Algorithrns 1 (1), 51-59. Bentley, J.L., and Kung, H.T. (1979). A tree machine for searching problems. Proc. of the 1979 Int. Conf. on Parallel Process., 25?26O. Berliner, H.J. (1978). A chronology of computer chess and its literature. Artf. Intell. 10 (2), 201-214. Bini, D., and Pan, V. (1985). Parallel polynomial division can be accelerated preserving full efficiency of the best sequential algorithms. Computer Sci- ence Dept., Tech. Rep. 85-3, State University of New York at Albany. Bitton, D., DeWitt, D.J., Hsaio, D.K., and Menon, J. (1984). A taxonomy of parallel sorting. ACAl Cornput. Surv. 16(3), 287-318. Chandra, A.K. (1976). Maximal parallelism in matrix multiplication. IBM Tech. Rep. RC 6193, Thomas J. Watson Research Center, Yorktown Heights, N.Y. Chen, 5. (1975). Speedups of iterative programs in multiprocessing systems. Ph.D. dissertation, Dept. of Computer Science, Univ. of Illinois at Urbana- Champaign. - 62 - Cheriton, D., and Tarjan, R.E. (1976). Finding minimum spanning trees. SlAM J. Cornput. 5(4), 72?742. Chin, F.Y., Lam, J., and Chen, I.-N. (1981). Optimal parallel algorithms for the connected component problem. Prcc. of the 1981 Int. Con!. on Parallel Pro- cess., 17O?175. Chin, F.Y., Lam, J., and Chen, I.-N. (1982). Efficient parallel algorithms for some graph problems. Commun. ACM ?5 (9), 65?665. Cook, S.A. (1981). Towards a complexity theory of synchronous parallel compu- tation. L `Enseignement Mathematique XYV11? 9?124. Csanky, L. (1976). Fast parallel inversion algorithms. SlAM J. on Comput. 5(4), 618-623. Dekel, E., and Sahni, 5. (1983a). Binary trees and parallel scheduling algorithms. lEEE Trans. Comput. C-32 (3), 307-315. Dekel, E., and Sahni, 5. (1983b). Parallel generation of postfix and tree forms. ACM Trans. Program. Lang. SysL 5(3), 30O?317. Dekel, E., and Sahni, 5. (1984). A parallel matching algorithm for convex bipar- tite graphs and applications to scheduling. J. of Parallel and Distributed Cornput. 1, 185-205. Dekel, E., Nassimi, D., and Sahni, 5. (1981). Parallel matrix and graph algo- rithms. SlAM J. Cornput. 10(4), 657-675. Dekel, E., Peng, 5., and Iyengar, 5.5. (1985). Optimal parallel algorithm for con- structing and maintaining a balanced rn-way search tree. Dept. Mathemati- cal Sciences, Tech. Rep. CS-209, Univ. of Texas at Dallas, Dallas, Texas. Deo, N., and Yoo, Y.B. (1981). Parallel algorithms for the minimum spanning tree problem. Proc. of the 1981 Int. Conf on Parallel Process., 18?189. Deo, N., Pang, C.Y. (1984). Shortest path algorithms; taxonomy and annotation. Networks 14 (2), 275-324. Dijkstra, E. (1959). A note on two problems in connexion with graphs. N?mer. Math. 1, 26?271. Eckstein, D.M. (1979a). Simultaneous memory access. Tech. Rep. 7?6, Dept. of Computer Science, Iowa State Univ. of Science and Technology, Ames, Iowa. Eckstein, D.M. (1979b). BFS and biconnectivity. Tech. Rep. 7?11, Dept. of Computer Science, Iowa State Univ. of Science and Technology, Ames, Iowa. Finkel, R.A., and Fishburn, J.P. (1982). Parallelism in alpha-beta search. Artf. Intell. 19, 89-106. Finkel, R.A., and Fishburn, J.P. (1983). Improved speedup bounds for parallel alpha-beta search. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5 (1), 8? 92. Fisher, A.L. (1984). Dictionary machines with a small number of processors. Proc. of the 11th Annu. ACM Conf Comput. Architecture, 15?156. Floyd, R.W. (1962). Algorithm 97: Shortest path. Commun. ACM 5(6), 362. Galil, Z. (1984). Optimal parallel algorithms for string matching. Proc. of the -63- 16th Annu. ACM Symp. Theory Cornput., 24?248. Gentleman, W.M. (1978). Some complexity results for matrix computations on parallel processors. J. Assoc. CornpuL Mach. 25 (1), 112-115. Ghosh, R.K. (1986). Parallel algorithms for connectivity problems in graph theory. J. Cornput. Math. 18, 19?218. Hirschberg, D.S. (1976). Parallel algorithms for the transitive closure and the connected component problems. Proc. of the 8th Annu. ACAl Symp. Theory Cornput., 55-57. Hirschberg, D.S. (1978). Fast parallel sorting algorithms. Commun. ACM 21 (8), 657-661. Hirschberg, D.S. (1982). Parallel graph algorithms without memory conflicts. Proc. of the 20th Atlerton Conj, 257-263. Hirschberg, D.S., Chandra, A.K., and Sarwate, D.V. (1979). Computing con- nected components on parallel computers. Commun. AC'?I 22(8), 461-464. Hirschberg, D.S., and Volper, D.J. (1983). A parallel solution for the minimum spanning tree problem. Proc. of the 17th Annu. Conf. Inf Sci. SysL, 68? 684. Horowitz, E., and Sahni, 5. (1976). "Fundamentals of Data Structures." Com- puter Science Press, Woodland Hills, Calif. Hyafil, L. (1978). On the parallel evaluation of the multivariate polynomials. Proc. 10th ACM Syrnp. on Theo. of Cornput., 19?195. Ja'Ja', J., and Simon, J. (1982). Parallel algorithms in graph theory: planarity testing. SMM J. Cornput. 11 (2), 31?328. Karp, R.M., and Wigderson, A. (1985). A fast parallel algorithm for the maximal independent set problem. J. Assoc. Cornput. Mach. 32(4), 762-773. Karp, R.M., Upfal, E., and Wigderson, A. (1985). Constructing a perfect match- ing is in random NC. Proc. of the lflh Annu. ACM Symp. Theory Comput., 22-32. Keller, R.M. (1973). Parallel program schemata and maximal parallelism I: fun- damental results. J. Assoc. Comput. Mach. 20, 51?537. Knuth, D.E., and Moore, R.W. (1975). An analysis of alpha-beta pruning. Artif. Intell. 6 (4), 293-326. Kozen, D., Vazirani, U.V., and Vazirani, V.V. (1985). NC algorithins for com- paribility graphs, interval graphs, and testing for unique perfect matching. Fifth Conf on Foundations of Software Tech. and Theoretical Comp. Sc. Kronsjo, L. (1979). "Algorithms: their complexity and efficiency." John Wiley and Sons Ltd. Kruskal, J.B. (1956). On the shortest subtree of a graph and the traveling sales- man problem. Proc. Arner. Math. Soc. 7 4?5O. Kucera, L. (1982). Parallel computation and conflicts in memory access. In!. Process. Lett. 1? (2), 9?96. Kuck, D.J. (1976). Parallel processing of ordinary programs. in Advances in - 64 - Cornp?ters, vol. 15, M. Rubinoff and M. Yovits, Eds. Academic Press, New York, 119-179. Kuck, D.J. (1977). ACM &rnpuL A survey of parallel machine organization and programming. Surv. 9, 29-59. Kuhn, R.ll., and Padua, D.A. (1981). "Tutorial on Parallel Processing." IEEE Computer Society Press, Catalog No. EH0182-6. Kumar, V., and Kanal L.N. (1984). Parallel branch and bound formulations for understanding and synthesising AND/OR TREE search. IEEE Trans. Pat- tern Anal. Mach. In tell. PAMI-6 (6), 76?778. Kung, H.T. (1980). The structure of parallel algorithms. in Advances in Corn- p?t. 19, M. Yovits, Ed. Academic Press, New York, 65-112. Kwan, S.C., and Ruzzo, W.L. (1984) Adaptive parallel algorithms for finding minimum spanning trees. Proc. 1984 Int. Conf on Parallel Process., 439- 443. Lakshmivarahan, 5., Dhall, S.K., and Miller, L.L. (1984). Parallel sorting algo- rithms. in Advances in Cornput. 23, M. Yovits, Ed. Academic Press, New York, 295-354. Lee, G., Kruskal, C.P., and Kuck D.J. (1985). An empirical study of automatic restructuring of nonnumerical programs for parallel processors. IEEE Trans. Cornput. C-34 (10), 927-933. Leiserson, C.E. (1979). Systolic priority queues. Tech. Rep. CMU-CS-79-115, Dept. of Computer Science, Carnegi?Meflon University, Pittsburgh, Pennsyl- vania. Levitt, K.N., and Kautz, W.T. (1972). Cellular arrays for the solution of graph problems. Commun. ACM 15(9), 789-801. Luby, M. (1985). A simple parallel algorithm for the maximal independent set problem. Proc. of the 17th Annu. ACM Symp. Theory Cornput., 1-10. Mateti, P., and Deo, N. (1981). Parallel algorithms for the single source shortest path problems. Tech. Rep. CS-81-078, Computer Science Dept., Washington State Univ., Pullman, Wash. Mead, C.A., and Conway, L.A. (1980). "Introduction to vLSI Systems." Addison-Wesley, Reading, Massachusetts. Moitra, A. (1986). Automatic construction of CSP programs from sequential non-deterministic programs. Sci. Comput. Prograrn. 5, 277-307. Moitra, A., and Iyengar, 5.5. (1986). Derivation of a parallel algorithm for balancing binary trees. IEEE Trans. Software Eng. SE-12 (3), 442-449. Mulmuley, K., Vazirani, U.V., and Vazirani, V.V. (1986). Matching is as easy as matrix inversion. To appear in Combinatorics. Munro, I., and Patterson, M. (1973). Optimal algorithms for polynomial evalua- tions. J. of Comp. and Sys. Sci. 7, 189-198. Nath, D., and Maheshwari, S.N. (1982). Parallel algoritlims for the connected components and minimal spanliillg tree problems. Inf. Process. Lett. 14(1), 7-11. 65 - Nicolau, A. (1985). Uniform parallelism exploitation in ordinary programs. Proc. of the 1985 IEEE Int. ConI. on Parallel Process., 614-618. Nilsson, N.J. (1980). "Principles of Artificial Intelligence." Tioga Publishing Co., Palo Alto, CA. Ottaman, T.A., Rosenberg, A.I., and Stockmeyer L.J. (1982). A dictionary machine for vLSI. JEEE Trans. Cornput. C-31 (9), 892-897. Paige, R.C., and Kruskal, C.P. (1985). Parallel algorithms for shortest path problems. Proc. of the 1985 IEEE Int. ConI. on Parallel Process., 1420. Pan, V. (1985). Complexity of computing polynomial zeros. Computer Science Dept., Tech. Rep. 85-27, State University of New York at Albany. Pan, V., and Galil, Z. (1985). Improving the efficiency of parallel algorithms for the evaluation of the determinant and of the inverse of a matrix. Computer Science Dept., Tech. Rep. 85-5, State University of New York at Albany. Pearl, J. (1982) The solution for the branching factor of alpha-beta pruning algo- rithm and its optimality. Cornrnun. ACM 25(8), 559-563. Preparata, F.P. (1973). New parallel-sorting schemes. IEEE Trans. Cornput C- 27(7), 669-673. Prim, R.C. (1957). Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389-1401. Quinn, M.J., and Deo, N. (1984). Parallel graph algorithms. ACA? Comput. Surv. 16 (3), 319-348. Rabin, M.O., and Vazirani, V.V. (1984). Maximum matchings in general graphs through randomization. Tech. Rep. 15-84, Center for Research in Comput- ing Technology, Harvard University, Cambridge, Mass. Reghbati (Ariomandi), E., and Corneil, D.G. (1978). Parallel computations in graph theory. SIAA?I J. Cornput. 2 (2), 230237. Reif, J.ll. (1985). Depth-first search is inherently sequential. Inf. Process. Lett. 20 (5), 229-234. Sameh, A.H. (1977). Numerical parallel algorithms - a survey. in Tutorial on Parallel Processing, R.H. Kuhn and D.A. Padua, Eds. IEEE Computer Society Press, pp. 412-427. Savage, C. (1977). Parallel algorithms for graph theoretic problems. Ph.D. dissertation, Mathematics Dept., University of Illinois, Urbana, Ill. Savage, C., and Ja'Ja', J. (1981). Fast, efficient parallel algorithms for some graph problems. SMAl J. Cornput. 10(4), 682-691. Shiloach, Y., and Vishkin, U. (1982). An O(log n) parallel connectivity algo- rithm. J. Algorithrns 3 (1), 57-67. Shrira, L., Francez, N., and Rodeh, M. (1983). Distributed k-selection : from a sequential to a distributed algorithm. Proc. of the Second Annu. ACM Symp. on Principles of Distributed Computing. ACM, New York, 1?153. Slagle, J.R., and Dixon, J.D. (1969). Experiments with Soe program that search game trees. J. Assoc. Cornput. Mach. 16 (2), 18?207. - 66 - Sollin, M. (1977). An algorithin attributed to Sollin. in Introduction to the Design and Analysis of Algorithrns, S.E. Goodman, and S.T. Hedetniemi, Eds. McGraw-Hill, New York, sect. 5.5. Somani, A.K., and Agarwal, V.K. (1984). An efficient `151 dictionary machine. Proc. of the 11th Annu. ACM Int. Symp. Cornput. Architecture, 142-150. Stone, 11.5. (1980). Parallel computers. in Introduction to Computer Architec- ture, H.S. Stone, Ed. Science Research Associates Chicago, II., chap. 8. Strom, R., and Yemini, 5. (1985). Synthesizing distributed and parallel programs through optimistic transformations. Proc. of the 1985 IEEE Int. Conf. on Parallel Process., 632-642. Tanaka, Y., Nozoka, Y., and Masuyama, A. (1980). Pipeline searching and sort- ing modules as components of data flow database computer. Proc. of IFIP, 427-432. Tarian, R.E. (1972). Depth first search and linear graph algorithms. SMM J. Cornput. 1 (2), 14?160. Tarjan, R.E., and Vishkin, U. (1984). Finding biconnected components and com- puting tree functions in logarithmic parallel time. Proc. of the 25th Annu. Symp. Foundations of Cornput. Sci., 12-20. Tsin, Y.H., and Chin, F.Y. (1984). Efficient p?allA algorithms for a class of graph theoretic problems. SMM J. Comput. 13 (3), 58O?5?9. Tutte, W.T. (1947). The factorization of linear graphs. J. London Math. Soc. 22, 107-111. Valiant, L.G. (1982). Parallel computation. Proc. of 7th IBM Symp. on Math. Foundations of Cornput. Sci. Valiant, L.G., and Skyum, 5. (1981). Fast parallel computation of polynomials using few processors. Lecture Notes in Computer Science, Edited by J. Gruska and M. Chytil, 118, Springer-Verlag, 132-139. Vishkin, U. (1983). Implementation of simultaneous memory address access in models that forbid it. J. Algorithrns 4(1), 45-50. Vishkin, U. (1985). Optimal parallel pattern matching in strings. Lecture Notes in Computer Science, Edited by W. Brauer, 194, Springer-Verlag, 497-508. Vitter, J.S., and Simons, R.S. (1986). New classes for parallel complexity : a study of unification and other complete problems for P. IEEE Trans. Corn- put. C-35 (5), 40?418. Wyllie, J.C. (1979). The complexity of parallel computations. Ph.D. dissertation, Dept. of Computer Science, Cornell Univ., Ithaca, NY. Yao, C.-C. (1975). An O( lE I log log V I) algorithm for finding minimum span- ning trees. Inf. Process. Lett. 4 (1), 21-23. Yoo, Y.B. (1983). Parallel processing for some network optimization problems. Ph.D. dissertation, Computer Science Dept., Washington State Univ., Pull- man, Wash. AcknowIed?ements We thank our graduate students S.V.N. Rao, Chandrasekhran, and Girish Kurathekar for th?ir contributions in this paper. Comments by Professors Kraft and Bastani helped in revising the paper.