|
 ABSTRACT
We need a programming model that combines the advantages of the synchronous and asynchronous parallel styles. Synchronous programs are determinate (thus easier to reason about) and avoid synchronization overheads. Asynchronous programs are more flexible and handle conditionals more efficiently.
Here we propose a programming model with the benefits of both styles. We allow asynchronous threads of control but restrict shared-memory accesses and other side effects so as to prevent the behavior of the program from depending on any accidents of execution order that can arise from the indeterminacy of the asynchronous process model.
These restrictions may be enforced either dynamically (at run time) or statically (at compile time). In this paper we concentrate on dynamic enforcement, and exhibit an implementation of a parallel dialect of Scheme based on these ideas. A single successful execution of a parallel program in this model constitutes a proof that the program is free of race conditions (for that particular set of input data).
We also speculate on a design for a programming language using static enforcement. The notion of distinctness is important to proofs of noninterference. An appropriately designed programming language must support such concepts as “all the elements of this array are distinct,” perhaps through its type system.
This parallel programming model does not support all styles of parallel programming, but we argue that it can support a large class of interesting algorithms with considerably greater efficiency (in some cases) than a strict SIMD approach and considerably greater safety (in all cases) than a full-blown MIMD approach.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
2
|
Abu-S~fah, Walid, and Malony, Allen D. Vectbr processlng on the Alliant FX/8 multlprocessor. In Hwang, Kai, Jacobs, Steven M., and Swartslander, Earl E., editors, Proc. 1986 International Conference on Parallel Processing. IEEE Computer Society (August 1986), 559-566.
|
| |
3
|
FX/FORTRAN Programmer's Handbook. Alliant Computer Systems Corporation (Acton, Massachusetts, May 1985).
|
| |
4
|
Draft Propoaed Revised American National Standard Programming Language Fortran, ANSI X3.9-198x, dxaft $8, Version 112 edition. American National Standards Institute, Inc. (Washington, D. C., 1989).
|
| |
5
|
Bouknight, W. J., Denenberg, Stewart A., McInty~e, David E., Randall, J. M., Sameh, Amed It., and Slotnick, Daniel L. The ILLIAC IV system. Proceedings o} the IEEE 60, 4 (April 1972).
|
 |
6
|
|
| |
7
|
Flanders, P. M., et al. Efficient high speed computing with the Distributed Array Processor. In High Speed Computer and Algorithm Organization. Academic Press (1977), 11a-127.
|
| |
8
|
Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
|
| |
9
|
Gifford, David K., Jouvelot, Pierre, Lucassen, John M., and Sheldon, Mark A. FX-87 Reference Manual. MIT/LCS/TR 407. MIT Laboratory for Computex Science (Cambridge, Massachusetts, September 1987).
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
Hiliis, W. Daniel. The Connection Machine. MIT Press (Cambridge, Massachusetts, 1985).
|
| |
14
|
|
| |
15
|
|
| |
16
|
APL\$60 User's Manual. International Business Machines Corporation (August 1968).
|
| |
17
|
|
| |
18
|
|
| |
19
|
Lamport, Leslie. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers C-28, 9 (September 1979), 690-691.
|
| |
20
|
Lamport, Leslie. Proving the correctness of multiprocess programs. IEEE Transactior~s on Software Engineering SE.3, 3 (March 1977), 125-143.
|
| |
21
|
|
| |
22
|
|
| |
23
|
|
| |
24
|
|
| |
25
|
Rose, John R., and Steele, Guy L., Jr. C*: An extended C language for data parallel programming. In Kartashev, Lana P., and Kartashev, Steven I., editors, Proc. Second International Conference on Supercomputing. Volume H. International Supercomputing Institute (Santa Clara, California, May 1987), 2-16.
|
| |
26
|
Schmidt, Gary E. The Butterfly parallel processor. In Kartashev, Lana P., and Kartashev, Steven I., editors, Proc. Second International Conference on Super. computing. Volume I. International Supereomputing Institute (Santa Clara, Callfotnia, May 1987), 362-365.
|
| |
27
|
|
| |
28
|
|
| |
29
|
Shaw, David Elliot. The NON-VON Supercomputer. Technical Report. Department of Computer Science, Columbia University (New York, August 1982).
|
| |
30
|
|
| |
31
|
|
| |
32
|
|
| |
33
|
|
| |
34
|
|
| |
35
|
Steele, Guy Lewis, Jr., and Sussman, Gerald Jay. The Revised Report on SCHEME: A Dialect o/~{SP. AI Memo 452. MIT Artificial Intelligence Laboratory (Cambridge, Massachusetts, January 1978).
|
| |
36
|
|
| |
37
|
Connection Machine Model CM-~ Technical Summary. Thinking Machines Corporation (Cambridge, Massachusetts, April 1987).
|
| |
38
|
|
| |
39
|
Who}ey, Skef, and Steele, Guy L., Jr. Connection Machine Lisp: A dialect of Common Lisp for data parallel programming. In Kartashev, Lan~ P., and Kartashev, Steven I., editors, Proc. Second International Conference on Supercomputing. Volume IIt. International Supercomputing Institute (Santa Clara, California) May 1987), 45-54.
|
| |
40
|
|
CITED BY 22
|
|
|
|
|
Özalp Babaoğlu , Lorenzo Alvisi , Alessandro Amoroso , Renzo Davoli , Luigi Alberto Giachini, Paralex: an environment for parallel programming in distributed systems, Proceedings of the 6th international conference on Supercomputing, p.178-187, July 19-24, 1992, Washington, D. C., United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.1