Parallel Processing of Encoded Bit Strings.
Abstract
Many operations on strings of length n can be speeded up by a factor of p using p processors. String operations can also be speeded up, even when a single processor is used, by compactly encoding the strings, e.g. using run length code. This paper shows how to combine these two approaches by using p processors to process compactly encoded strings. The author studies various representations of bit strings and parallel algorithms to process these representations using a multiprocessor system. Section 2 describes the parallel processing model used. Sections 3 and 4 discuss various compact representations of strings, and their conversions to each other. Section 5 presents algorithms to process run length coded strings. Section 6 briefly discusses the extension of this work to representations of two-dimensional objects. Additional keywords: message processing, computations, binary arithmetic, coding, coordinates, value.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1984
- Accession Number
- ADA149812
Entities
People
- A. Y. Wu
Organizations
- University of Maryland