Parallel Processing of Encoded Bit Strings

摘要

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.