Back to search

University of North Texas

Practical Parallel Processing

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
University of North Texas
Year dc:date
1996

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Hua, 1954-
Contributors dc:contributor
  • Fisher, Paul S.
  • Jacob, Roy Thomas
  • Tate, Stephen B.
  • Mackey, H. J.

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Public
  • Copyright
  • Copyright is held by the author, unless otherwise noted. All rights reserved.
  • Zhang, Hua, 1954-
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
call-no: 379 N81d no.4376
local-cont-no: 1002726895-zhang
untcat: b2026644
ark: ark:/67531/metadc278769

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Hua, 1954-. Practical Parallel Processing. University of North Texas, 1996. https://digital.library.unt.edu/ark:/67531/metadc278769/