A Parallel Programming Model with Sequential Semantics
Creators: name: Thornley, John
Publisher: name: California Institute of Technology
Year: 1996

description: Parallel programming is more difficult than sequential programming in part because of the complexity of reasoning, testing, and debugging in the context of concurrency. In this thesis, we present and investigate a parallel programming model that provides direct control of parallelism in a notation with sequential semantics. Our model consists of a standard sequential imperative programming notation extended with the following three pragmas: (1) The parallelizable sequence of statements pragma indicates that a sequence of statements can be executed as parallel threads; (2) The parallelizable for-loop statement pragma indicates that the iterations of a for-loop statement can be executed as parallel threads; (3) The single- assignment type pragma indicates that variables of a given type are assigned at most once and that ordinary assignment and evaluation operations can be used as implicit communication and synchronization operations between parallel threads. In our model, a parallel program is simply an equivalent sequential program with added pragmas. The placement of the pragmas is subject to a small set of restrictions that ensure the equivalence of the parallel and sequential semantics. We prove that if standard sequential execution of a program (by ignoring the pragmas) satisfies a given specification and the pragmas are used correctly, parallel execution of the program (as directed by the pragmas) is guaranteed to satisfy the same specification. Our model allows parallel programs to be developed using sequential reasoning, testing, and debugging techniques, prior to parallel execution for performance. Since parallelism is specified directly, sophisticated analysis and compilation techniques are not required to extract parallelism from programs. However, it is important that parallel performance issues such as granularity, load balancing, and locality be considered throughout algorithm and program development. We describe a series of programming experiments performed on up to 32 processors of a shared-memory multiprocessor system. These experiments indicate that for a wide range of problems: (1) Our model can express sophisticated parallel algorithms with significantly less complication than traditional explicit parallel programming models; (2) Parallel programs in our model execute as efficiently as sequential programs on one processor and deliver good speedups on multiple processors; (3) Program development with our model is less difficult than with traditional explicit parallel programming models because reasoning, testing, and debugging are performed using sequential methods. We believe that our model provides the basis of the method of choice for a large number of moderate-scale, medium-grained parallel programming applications.
description: © 1996 John Thornley, California Institute of Technology. 

Submitted May 20th, 1996. 

Many thanks to my academic advisor, Mani Chandy, for his support, guidance, and assistance in so many ways over the previous six years. I feel very fortunate to have been advised by such a gracious and insightful academic and such an all-around nice guy. Thanks also to the other members of my examining committee, Mary Hall, Carl Kesselman, Peter Schröder, and Eric Van de Velde, for their time spent reading this thesis and for their suggest ions regarding this work. Thanks to the graduate students who have been part of our research group during my stay at Caltech, Berna Massingill, Paul Sivilotti, Adam Ritkin, Peter Hofstee, Rustan Leino, Eve Schooler, Ulla Binau, Svetlana Kryukova, Rajit Manohar, and Peter Carlin, for their help with my research and for their friendship. Particular thanks to Paul for helping me
with all those "interesting little questions" (equivalence, nondeterminacy, time travel, and invisible cameras) and to Berna, Adam, and Rajit for assistance and proofreading above and
beyond the call of duty. Thanks also to Diane Goodfellow for her administrative support and for keeping us well fed. Much of this research has been influenced by two parallel programming projects at Caltech: the PCN project led by Steve Taylor and Mani Chandy at Caltech and by Ian Foster at Argonne National Labs, and the CC++ project led by Carl Kesselman and Mani Chandy at Caltech. Thanks to those individuals and their groups. Special thanks to Steve for introducing me to parallel programming with PCN during my first year at Caltech. Thanks to t he Ada 95 team at Silicon Graphics, in particular Tom Quiggle and Wes Embry, for providing me with software, computer time, and technical support for my parallel programming performance experiments. Getting my hands on a 36-processor shared memory multiprocesoor was a dream come true for me. (We computer scientists have very tame dreams!) Thanks to my teachers and academic colleagues in the Department of Computer Science at the University of Auckland, New Zealand for providing me with so many opportunities and for encouraging me to embark upon this adventure. Thanks also to the students that I taught at the University of Auckland for shaping my perspective on computer science and for making that phase of my life so interesting and so much fun. Thanks again to Professor Graham Hill and his team in the Department of Surgery at
the University of Auckland for their compassion and skill. Thanks to Dr. Stephen Petit, Dr. Charles Bernstein, and Lucy Artinian for making me believe that bad times don't have to last forever. Thanks to Cecilia for being my special friend and for providing me with a safe haven
away from Caltech for t he past five years. Thanks to my mother, Margaret, my father, Basil, and my brother, Robert, for their unconditional love and support throughout all of my life and education. Without them, I
really could not have done this! Finally and somewhat vaguely, thanks to the California Institute of Technology for the uncountably many thins that have made these last six years so fascinating and unforgettable. This research was supported in part by Air Force Office of Scientific Research grant AFOSR-91-0070 and by the NSF under Cooperative Agreement No. CCR-9120008.
description: Submitted - postscript.pdf
Submitted - postscript.ps