The physical limitations of uniprocessors and the real-time requirements of numerous practical applications have made parallel processing an essential technology in military, industry and scientific research. In this dissertation, we investigate parallelizations of three practical applications using three parallel machine models. The algorithms are:
Finitely inductive (FI) sequence processing is a pattern recognition technique used in many fields. We first propose four parallel FI algorithms on the EREW PRAM. The time complexity of the parallel factoring and following by bucket packing is O(sk^2 n/p), and they are optimal under some conditions. The parallel factoring and following by hashing requires O(sk^2 n/p) time when uniform hash functions are used and log(p) ≤ k n/p and pm ≈ n. Their speedup is proportional to the number processors used. For these results, s is the number of levels, k is the size of the antecedents and n is the length of the input sequence and p is the number of processors.
We also describe algorithms for raster/vector conversion based on the scan model to handle block-like connected components of arbitrary geometrical shapes with multi-level nested dough nuts for the IES (image exploitation system). Both the parallel raster-to-vector algorithm and parallel vector-to-raster algorithm require O(log(n2)) or O(log2(n2)) time (depending on the sorting algorithms used) for images of size n2 using p = n2 processors.
Not only is the DWT (discrete wavelet transforms) useful in data compression, but also has it potentials in signal processing, image processing, and graphics. Therefore, it is of great importance to investigate efficient parallelizations of the wavelet transforms. The time complexity of the parallel forward DWT on the parallel virtual machine with linear processor organization is O(((so+s1)mn)/p), where s0 and s1 are the lengths of the filters and p is the number of processors used. The time complexity of the inverse DWT is also O(((so+s1)mn)/p). If the processors are organized as a 2D array with PrawPcol processors, both the interleaved parallel DWT and IDWT have the time complexity of O(((so+s1)mn)/ProwPcol).
We have parallelized three applications and achieved optimality or best-possible performances for each of the three applications over each of the chosen machine models. Future research will involve continued examination of parallel architectures for implementation of practical problems.
| Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc278769 |
| Date | 08 1900 |
| Creators | Zhang, Hua, 1954- |
| Contributors | Fisher, Paul S., Jacob, Roy Thomas, Tate, Stephen B., Mackey, H. J. |
| Publisher | University of North Texas |
| Source Sets | University of North Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | xi, 152 leaves: ill., Text |
| Rights | Public, Copyright, Copyright is held by the author, unless otherwise noted. All rights reserved., Zhang, Hua, 1954- |
Page generated in 0.0016 seconds