language: en

Two Computer Systems Paradoxes: Serialize-to-Parallelize, and Queuing Concurrent-Writes

Rimon Orni and Uzi Vishkin
September 17, 1995

Abstract We present and examine the following Serialize-to-Parallelize Paradox: suppose a programmer has a parallel algorithm in mind; the programmer must serialize the algorithm, and is actually trained to suppress its parallelism, while writing code; later, however, compilation and runtime techniques are used to reverse the results of this serialization effort and extract as much parallelism as possible. This work actually provides examples where parallel or parallel-style code enables extracting more parallelism than standard serial code. The "arbitrary concurrent-write" convention is useful in parallel algorithms and programs and appears to be not too difficult to implement in hardware for serial machines. Still, typically concurrent-writes to the same memory location in a program are implemented by queuing the write operations, thus requiring time linear in the number of writes. We call this the Queuing Concurrent-Writes Paradox. Assuming that providing useful, easy-to-program programming paradigms to improve the overall effectiveness of computer systems is of interest, this work is a modest example for applying such software-driven considerations to computer architecture issues. This work may be the first to relate parallel algorithms and parallel programming with the technology of instruction level parallelism.

1 Introduction