Accession Number:

ADA149812

Title:

Parallel Processing of Encoded Bit Strings.

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s):

Report Date:

1984-11-01

Pagination or Media Count:

26.0

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.

Subject Categories:

  • Numerical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE