Excerpt from Efficient and Correct Execution of Parallel Programs That Share Memory

In this paper, we consider an optimization problem that arises in the execution of parallel programs on shared memory multiple-instruction stream multiple-data stream (MIMD) computers. A program on such a machine consists of many program segments each executed sequentially by a single processor. The processors have access to shared memory, and can execute standard memory access operations on this shared memory. This memory is distributed among many separate memory modules. A network connects processors to memory modules. Delays on this network arc stochastic. Thus, operations issued by a processor to distinct memory modules may not be executed as memory requests on those modules in the order they were issued.

For performance reasons, we want to allow one operation to begin before a previous one in the same instruction Our analysis gives a method for determining which operations in a stream may be issued concurrently without changing the semantics of the execution We also consider code where blocks of operations have to be executed atomically. This introduces the necessity of locks. Wc use a conflict graph similar to that used to schedule transactions in distributed databases.

Our graph incorporates the order on operations given by the program text, enabling us to do without locks even when database conflict graphs would suggest that locks are necessary.

1. Introduction

Programs on shared memory M1MD computers, e.g. the NYU Uliracomputer |GGK] or the IBM RP3 machine (PBG). consist of many program segments each executed sequentially by a single processor. The memory locations accessed by these programs arc either locations in shared memory modules, ot local memory locations, which we call registers. An operation in a given processor follows one of four basic patterns:

(1) read from registers (in that processor) and write to registers,

(2) read from registers (in that processor) and write to a single location in a shared memory module,

(3) read a single location from a shared memory module and write to registers (in that processor),

(4) force a constant to either a register (in that processor) or a shared memory module location.

We call a register or a location in a memory module by the generic name variable Thus, an operation consists of a read of zero or more variables followed by a write to one or more variables.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully, any imperfections that remain are intentionally left to preserve the state of such historical works.