Abstract for piper_tr132

Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR132

GENERALIZED PARALLEL PROGRAMMING WITH DIVIDE-AND-CONQUER: THE BEEBLEBROX SYSTEM

A. J. Piper and R. W. Prager

JULY 1993

Object-oriented programming has been widely proposed as a discipline suited to extracting parallelism from a program. However, object-oriented programming provides no more guarantee of efficient parallelism than procedural programming. The divide-and-conquer (D&C) algorithm does guarantee a measure of efficient parallelism as demonstrated by many researchers. We present a system that uses object-oriented techniques to encapsulate the D&C algorithm and which is much more flexible than our previous work. We go on to describe a stack-based evaluation algorithm that allows the nesting of D&C evaluations. We use this framework to implement a tree-based language model which gives good parallel performance. We then present some techniques for achieving better performance and which are universally applicable to D&C problems. Finally we analyse the performance in theoretical terms and show that a suitable implementation can achieve better speedup than N/log_2N.


(ftp:) piper_tr132.ps.Z (http:) piper_tr132.ps.Z
PDF (automatically generated from original PostScript document - may be badly aliased on screen):
  (ftp:) piper_tr132.pdf | (http:) piper_tr132.pdf

If you have difficulty viewing files that end '.gz', which are gzip compressed, then you may be able to find tools to uncompress them at the gzip web site.

If you have difficulty viewing files that are in PostScript, (ending '.ps' or '.ps.gz'), then you may be able to find tools to view them at the gsview web site.

We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.