Fast parallel routing and computation on interconnection networks
David S. L. Wei · ScholarlyCommons (University of Pennsylvania) · 1991
Both parallel processing and artificial intelligence play important roles in computer science. The application of parallel processing in artificial intelligence is one of the possible approaches to realize an efficient and intelligent computer. This is a two-part thesis. The first part of this thesis investigates routing problems, which are central to parallel processing, for a class of interconnection networks called leveled networks, while the second part of the thesis makes use of these results to develop efficient parallel algorithms for some communication intensive artificial intelligence problems. Specifically, we look at the parsing problem for natural language grammars which is a fundamental problem in artificial intelligence. Our work goes beyond theoretical study on routing and parallel algorithms in that we also develop implementations of the algorithms on an actual parallel machine, viz., the Connection Machine (CM). This allows us to verify experimentally the performance predicted by theoretical analysis. To date, much of the work on routing has virtually centered on constant degree networks with logarithmic (or even larger) diameter. In order to achieve faster communication, we initiate the study of routing on some non-constant degree networks with sublogarithmic diameter. We also give a universal randomized optimal routing algorithm for a large class of interconnection networks, viz., leveled networks. These leveled networks can be of logarithmic, or sublogarithmic diameter. Further, we present algorithms for emulating PRAMs, an ideal shared memory model, on leveled networks. The emulation is optimal. We also study parallel parsing algorithms. In particular, we consider tree adjoining grammars (TAGs). We give a parallel parsing algorithm on a 5-dimensional systolic array, which achieves optimal speed-up with respect to the best known sequential one. We also present an efficient algorithm for general TAGs on the CM. This implemented algorithm parallelizes the parsing in terms of the grammar size unlike previous parallel parsing algorithms which parallelize the parsing in terms of the input sentence. The former is highly desirable for the natural language processing because of the huge grammar size.