Abstract

This dissertation describes a number of novel parallel algorithms for solving maze-routing problems and string matching problems on a proposed reconfigurable mesh architecture.

Section I reviews the field of reconfigurable parallel computing. This includes an introduction to a number of reconfigurable architectures proposed in the literature and a list of references to the current literature on algorithms in the field of reconfigurable computing.

Section II presents a number of time-efficient algorithms to solve the mazerouting problem. Maze-routing algorithms are used in VLSI routing and robot path planning. In that section, definitions for absolute shortest path (ASP), shortest duplex-path (SDP), shortest triplex-path (STP), and single shortest path (SSP) are given. Then, 0(1) algorithms are presented for: (i ) testing the existence of specific types of paths, (ii ) finding an ASP and a SDP. In addition, fast algorithms are presented for finding the STP and the SSP. The simulation results indicate that a large percentage of the shortest paths that exist between two randomly selected terminals fall into one of the categories studied in this section.

Section III presents a number of time-efficient algorithms to solve the exact string matching and approximate string matching problems. These problems received much attention over the years due to their importance on various areas such as, DNA sequencing, text comparison, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of information on the WWW, these problems deserve special attention and speed becomes a major issue. Given a text T of length n and a pattern P of length m, the first algorithm finds the exact matching between T and Pin 0(1) time. The second algorithm finds the approximate matching between T and Pin O(k) time, where k is the maximum distance between T and P. The third algorithm considers only the replacement operation in the calculation of the edit distance and finds the approximate matching between T and Pin 0(1) time.

Department(s)

Computer Science

Comments

The first Author is a Graduate Student

This report is substantially the text of the Ph.D. dissertation of the first author, completed December 1996.

Acknowledgements:

The author wishes to express his gratitude to his advisor, Dr. Fikret Ercal, for his patient guidance, discussion, friendship and continued support and advice throughout the research and the preparation of this dissertation.

The author also wishes to convey his sincere thanks to Dr. George W. Zobrist for his support and advice, Dr. Chung-You Ho, Dr. Jagdish K. Patel and Dr. Ralph W. Wilkerson for their instruction, advice, and also for serving on his committee.

Thanks are also due to the author's teachers and friends who encourage him and help him at various stages of his education, which, as a result, makes this work possible.

This work was supported in part by the Department of Computer Science and the Intelligent Systems Center of the University of Missouri-Rolla.

Report Number

CSc-96-08

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1996 University of Missouri - Rolla, All rights reserved

Publication Date

1996-12-01

Download

Share

 
COinS