Alexander Aiken
David Gay
ABSTRACT
Many parallel programs are written in SPMD style i.e. by running the same sequential program on all processes. SPMD programs include synchronization, but it is easy to write incorrect synchronization patterns. We propose a system that verifies a program's synchronization pattern. We also propose language features to make the synchronization pattern more explicit and easily checked. We have implemented a prototype of our system for Split-C and successfully verified the synchronization structure of realistic programs.
- 1.J. Auslander, M. Philipose, C. Chambers, S. J. Eggers, and B. N. Bershad. Fast, Effective Dynamic Compilation. In Proceedings of the A CM SIGPLAN '96 Con- }erence on Programming Language Design and Implementation, pages 149-159, Philadelphia, Pennsylvania, May 1996. Google Scholar
Digital Library
- 2.D. (3allahan, K. Kennedy, and J. Subhlok. Analysis of Event Synchronization in a Parallel Programming Tool. In Proceedings of the Second A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 21-30, Seattle WA, March 1990. Google ScholarDigital Library
- 3.D. (3allahan and J. Subhlok. Static Analysis of Low- Level Synchronization. In Proceedings of the A CM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, pages 100-111, Madison, WI USA, {1} 1989. A(3M Press , New York, NY , USA. Published as SIGPLAN Notices, volume 24, number Google ScholarDigital Library
- 4.Gray Research Incorporated. The URA Y T3D Hardware Reference Manual, 1993.Google Scholar
- 5.D. E. (3uller, A. Dusseau, S. (3. Goldstein, A. Krishnamurthy, S. Lumetta, T. yon Eicken, and K. Yelick. Introduction to Sptit-U. University of California, Berkeley, 1993.Google Scholar
- 6.D. Gay. Barrier Inference. Technical Report U(3B//GSD-97-965, EECS Computer Science Division, University of California, Berkeley, July 1997. Google ScholarDigital Library
- 7.D. Gifford, P. Jouvelot, J. Lucassen, and M. Sheldon. FX-87 REFERENCE MANUAL. Technical Report MIT-LCS//MIT/L(3S/TR-407, Massachusetts Institute of Technology, Laboratory for Computer Science, September 1987'.Google Scholar
- 8.J. Gosling, B. Joy, and G. Steele. The Java Language Specification. The Java Series. Addison-Wesley, Readhag, MA, USA, June 1996. Google ScholarDigital Library
- 9.D. P. Helmbold and (3. E. McDowell. Computing Reachable States of Parallel Programs. Proceedings of the A CM/ONR Workshop on Parallel and Dis-. tributed Debugging, published in A CM SIGPLAN Notices, 26(12):76--84, December 1991. Google ScholarDigital Library
- 10.T. 3eremiassen and S. Eggers. Computing Per-Process Summary Side-Effect Information. In Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, number 757 in Lecture Notes in Computer Science, pages 175-191, New Haven, (3onnecticut, August 3-5, 1992. Springer- Verlag. Google ScholarDigital Library
- 11.T. E. Jeremiassen and S. 3. Eggers. Static Analysis of Barrier Synchronization in Explicitly Parallel Systems. In Proceedings of the IFIP WG 10.3 Working Conference on Parallel Architectures and Compilation Techniques, PACT '94, pages 171-180, Montreal, Quebec, August 24-26, 1994. North-Holland Publishing Co. Google ScholarDigital Library
- 12.N. D. Jones, (3. K. Gomard, and P. Sestoff. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993. Google ScholarDigital Library
- 13.A. Krishnamurthy, D. E. Culler, A. Dusseau, S. G. Goldstein, S. Lumetta, T. yon Eicken, and K. Yelick. Parallel Programming in Split-G. In Proceedings of the Supercomputing "93 Conference, pages 262-273, Portland, OR, November 1993. IEEE Computer Society Press. Google ScholarDigital Library
- 14.A. Krishnamur~hy and K. Yelick. Optimizing Parallel Programs with Explicit Synchronization. In ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 196--204, New York, NY, USA, June 1995. ACM Press. Google ScholarDigital Library
- 15.W. Landi and B. G. Ryder. A Safe Approximate A1- goriLhm for Iaterprocedural Poinier Aliasing. In A GM SIGPLAN '9~ Conyerence on Programming Language Design and Implementation, pages 235-248, June 1992. Google ScholarDigital Library
- 16.D. H. Lawrie, T. Layman, D. Baer, and J. :M. Randal. Glypnir- A Programming Language for Illiac IV. Communications of the A CM, 18(3):157-164, March 1975. Google ScholarDigital Library
- 17.C. E. Leiserson, Z. S. Abuhamdeh, D. C. Douglas, C. R. Feynman, M. N. Ganmukhi, 5. V. Hill, W. D. Hillls, B. C. Kuszmaul, M. A. SL Pierre, D. S. Wells, M. C. Wong, S. Yang, and R. Zak. The Network Architecture of the CM-5. In Symposium on Parallel and Distributed Algorithms "9,9,, June 1992. Google ScholarDigital Library
- 18.S. P. Masficola and B. G. Ryder. Non-concurrency Analysis. In Fourth A CM SIGPLAN Symposium on Princip}es and Practice of Parallel Programming, pages 129-138, New York, NY, USA, July 1993. AGM Press. Google ScholarDigital Library
- 19.C. E. McDowell. A Practical Algorithm for Static Analysis of Parallel Programs. Journal of Parallel and Distributed Gompu~ing, 6(3):515-536, {6} 1989. Google ScholarDigital Library
- 20.Message Passing Interface Forum. Document for a standard message-passing interface. Technical Report UT-CS-93-214, University of Tennessee, Knoxville, 1993. Google ScholarDigital Library
- 21.M. A. Nichols, H. J. Siegel, and H. G. Dietz. Data Management and Control-Flow Aspects of an SIMD/SPMD Parallel Language/Compiler. IEEE Transactions on Parallel and Distributed Systems, 4(2):222-234, February 1993. Google ScholarDigital Library
- 22.R. N. Taylor. A General-Purpose Algorithm for Analyzing Concurrent Programs. Communications of the ACM, 26(5):362-376, May 1983. Google ScholarDigital Library
- 23.Thinking Machines Corporation. G* Programming Guide, 1993.Google Scholar
- 24.L. Wang. ELP User's Manual Parallel Processing Laboratory, School of Electrical and Computer Engineering, Purdue UniversiLy, March 1996.Google Scholar
- 25.S. Cameron Woo, M. Ohaxa, E. Torrie, J. Pal Shin~h, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22rid Annual International Symposium on Computer Architecture, pages 24-36, Santa Margherita Ligure, I~aly, June 22-24, 1995. ACM SIGARCH and IEEE Computer Society TCGA. Google ScholarDigital Library
- 26.M. Young and R. N. Taylor. Combining Static Concurrency Analysis 'wi~h Symbolic Execution. In Proceedings Workshop on Software Testing, pages 10-18, 1986.Google Scholar
Index Terms
- Barrier inference
Recommendations
Distributed Hardwired Barrier Synchronization for Scalable Multiprocessor Clusters
Conventional multiprocessors mostly use centralized, memory-based barriers to synchronize concurrent processes created in multiple processors. These centralized barriers often become the bottleneck or hot spots in the shared memory. In this paper, we ...
Static Barrier MIMD
In this paper, we describe and analyze the performance of a new architectural construct - an efficient synchronization mechanism called "Static Barrier MIMD" or SBM. Unlike traditional barrier synchronization, the proposed barriers are designed to allow ...
Comments