[公告] 博士論文研究計畫口試: 歐家欣(2014/04/10)

[ARDS]

清華大學資訊工程學系博士研究計劃口試

題 目: Application of the Bit-Parallel Approach to Solve String Matching and Subcircuit Extraction Problems

學 生: 歐家欣

指導教授: 李家同教授

口試委員: 李家同教授、唐傳義教授、王炳豐教授、盧錦隆教授

時 間: 103 年 04 月 10 日 (星期四) 14:00 - 16:00

地 點: 資電館 550 會議室

論文摘要:

In this proposal, we focus on applying bit-parallel approaches to solve three problems: (1) Bit-vectors with involving special properties problems. (2) Subcircuit extraction problem. (3) Nearest neighbor string matching problem.

(1) Bit-vectors with involving special properties problems:
Suppose that we are given a vector consisting of only 1’s and 0’s and we are interested in finding some special properties of this vector. For instance, we like to determine whether all of the bits from location s to location e in the vector are all 1’s or whether there exists a 1 from location s to location e. In more complicated cases, we are given two bit vectors and we like to investigate the mutual properties between the two vectors. For instance, we want to find all locations i in vector B such that there exists a k in vector A , k i, such that A(k)=1 and in vector B, locations from k to i all assume value 1. These problems all involve “for-all” or “there-exists” notations and can of course be solved by sequential programs. In this proposal, we are interested in bit-parallel process to solve these problems. That is, we are interested in solving the problem effi
ciently by using "bitwise-and", "bitwise-or" and other bitwise logical operations. A sequence of logical operations can be expressed as a logical formula. This proposal proposes a systematical method to find such logical formulas to solve problems involving bit vectors with “for-all” and “there-exists” notations. Five logical prototype problems, named “single-for-all” (1’s), “single-there-exists”, “multiple- for-all”, “multiple-there-exists” and “multiple-there-exists-and-for-all”, are defined in this proposal. For each problem, we shall show that there exists a corresponding logical formula which can be computed using bit-parallel operations in O(n/w) time, where w is the word size of the machine. We consider four variants for these five problems, and show that their logical formulas can be obtained using those of the five prototype problems.

(2) Subcircuit extraction problem:
Given two circuits, a smaller pattern circuit S and a larger main circuit T, the subcircuit extraction problem is to find all subcircuits T’ in T which are identical to S. In our proposal, our algorithm is not only to find out all subcircuits T’ which are exactly the same as S, but also to find out T’s which are subcircuits of S. It is an important topic in many areas of VLSI circuit design. In this proposal, we propose an algorithm to solve the problem. Our approach transforms both main and pattern circuits into weighted directed graph consisting of positive weights on edges and then uses a set of filtering rules to rule out subcircuits which cannot be candidates. These filtering techniques can all be implemented by bit-parallel mechanism. Experimental results show that our algorithm is efficient. If a pattern circuit consists of 50 transistors and the text circuit cons
ists of 10000 transistors, we can solve the subcircuit extraction problem less than 1 second.

(3) Nearest neighbor string matching problem:
The nearest neighbor string matching problem is defined as follows: Given a text string T = t1t2…tn and a pattern string P = p1p2…pm, find all substrings of T whose edit distances with P are the smallest. To be more precise, we are looking for all positions i of T such that there exists a suffix of t1t2…ti whose edit distance with P is the smallest. Such suffixes are called nearest neighbors of P in T. The nearest neighbor string matching problem has useful applications in bioinformatics. The nearest neighbor string matching problem can be straightforwardly solved by Seller’s Algorithm and more sophistically, by Myers algorithm which is used to solve the approximate string matching problem. Myers algorithm has good performance in practice. However, Heikki Hyyro and Gozalo Navarro proposed a filtering algorithm based on Myers which has better performance on smaller error
bound k and larger alphabet sizes. In our proposal, we present a bit-parallel algorithm which combines Myers algorithm and the modified Heikki Hyyro and Gozalo Navarro (HN) algorithm. The HN Algorithm uses a filtering algorithm which needs to do a preprocessing based on the error bound k. Hence, it is not suitable to be used to solve the nearest neighbor string matching problem which has no error bound k. In this proposal, we present a modification of HN algorithm which avoids the error bound k. At the beginning, we use Myers algorithm to find the temporary nearest neighbor distance. Once we found the temporary nearest neighbor distance is suitable to work on HN algorithm, we obtained the filtering algorithm which is based on HN algorithm.

--
[;32m※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw>
[;32m◆ From: ards @ r717b.cs.nthu.edu.tw [m