Optical Parallel Computing And Its Application In Image Processing And Computational Molecular Biology

Optical parallel computation has advantages of precise delay, high communication speed and bandwidth, high reliability and ability of processing large amount of data simultaneously. In this thesis, we study optical parallel computing and present algorithms for image processing and computational molecular biology on the optical bus computational model named LARPBS (Linear Array with a Reconfigurable Pipelined Optical Bus System). We first introduce the optical computational model LARPBS and the primitive operations and algorithms of matrixes multiplication, sorting on the model. In the area of image processing, we present fast LARPBS algorithms of Hough transform and Euclidean distance transform. In the area of computational molecular biology, we present LARPBS algorithms for longest common subsequence and sequences alignment.For an image with n×n pixels, our LARPBS Hough transform algorithm can be completed in 0(1) time using mn~2 processors and get the optimal speed and efficiency.For an image with n×n pixels, the first EDT algorithm on LARPBS can be completed in O(logn loglogo / logloglogn) time using n~2 processors, while our second EDT algorithm can compute the EDT in 0{ log n loglog n) time using 0(n~2/ loglog n) processors. Compared with the best parallel EDT algorithms on LARPBS reported so far, our algorithms have the lowest time-area cost and are more efficient. Our third algorithm can process EDT transform in O(nlogn / (c(n)-logd(n))) time with n-d(n)c(n) processors, where c(n), d(n) satisfy 1