Compiler Support for Exploiting Coarse-Grained Pipelined Parallelism

ABSTRACT

The emergence of grid and a new class of data-driven applications is making a new form of parallelism desirable, which we refer to as coarse-grained pipelined parallelism. This paper reports on a compilation system developed to exploit this form of parallelism. We use a dialect of Java that exposes both pipelined and data parallelism to the compiler. Our compiler is responsible for selecting a set of candidate filter boundaries, determining the volume of communication required if a particular boundary is chosen, performing the decomposition, and generating code. We have developed a one-pass algorithm for determining the required communication between consecutive filters. We have developed a cost model for estimating the execution time for a given decomposition, and a dynamic programming algorithm for performing the decomposition. Detailed evaluation of our current compiler using four data-driven applications demonstrate the feasibility of our approach.

REFERENCES

• 1: Vikram Adve , Vinh Vi Lam , Brian Ensink, Language and Compiler Support for Adaptive Distributed Applications, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.238-246, August 2001, Snow Bird, Utah, United States
• 2: Vikram Adve , John Mellor-Crummey, Using integer sets for data-parallel program analysis and optimization, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.186-198, June 17-19, 1998, Montreal, Quebec, Canada
• 3: [3] Asmara Afework, Michael D. Beynon, Fabian Bustamante, Angelo Demarzo, Renato Ferreira, Robert Miller, Mark Silberman, Joel Saltz, Alan Sussman, and Hubert Tsang. Digital dynamic telepathology - the Virtual Microscope. In Proceedings of the 1998 AMIA Annual Fall Symposium. American Medical Informatics Association, November 1998.
• 4: [4] T. Arbogast, S. Bryant, C. Dawson, and M. F. Wheeler. Parssim: The parallel subsurface simulator, single phase. http://www.ticam.utexas.edu/~arbogast/parssim.
• 5: [5] D. Arnold, H. Casanova, and J. Dongarra. Innovation of the netsolve grid computing system. Concurrency Practice and Experience, 2002.
• 6: Adam Beguelin , Jack J. Dongarra , George Al Geist , Robert Manchek , Keith Moore, HeNCE: a heterogenous network computing environment, Scientific Programming, v.3 n.1, p.49-60, Spring 1994
• 7: Francine Berman , Andrew Chien , Keith Cooper , Jack Dongarra , Ian Foster , Dennis Gannon , Lennart Johnsson , Ken Kennedy , Carl Kesselman , John Mellor-Crumme , Dan Reed , Linda Torczon , Rich Wolski, The GrADS Project: Software Support for High-Level Grid Application Development, International Journal of High Performance Computing Applications, v.15 n.4, p.327-344, November 2001 [doi>10.1177/109434200101500401]
• 8: Francine Berman , Richard Wolski , Henri Casanova , Walfredo Cirne , Holly Dail , Marcio Faerman , Silvia Figueira , Jim Hayes , Graziano Obertelli , Jennifer Schopf , Gary Shao , Shava Smallen , Neil Spring , Alan Su , Dmitrii Zagorodnov, Adaptive Computing on the Grid Using AppLeS, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.369-382, April 2003 [doi>10.1109/TPDS.2003.1195409]
• 9: Michael D. Beynon , Tahsin Kurc , Umit Catalyurek , Chialin Chang , Alan Sussman , Joel Saltz, Distributed processing of very large datasets with DataCutter, Parallel Computing, v.27 n.11, p.1457-1478, October 2001 [doi>10.1016/S0167-8191(01)00099-0]
• 10: [10] Michael D. Beynon, Tahsin Kurc, Umit Catalyurek, Alan Sussman, and Joel Saltz. A component-based implementation of iso-surface rendering for visualizing large datasets. Technical Report CS-TR-4249 and UMIACS-TR-2001-34, University of Maryland, Department of Computer Science and UMIACS, May 2001.
• 11: Michael D. Beynon , Alan Sussman , Tahsin Kurc , Joel Saltz, Optimizing Execution of Component-based Applications using Group Instances, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.56, May 15-18, 2001
• 12: [12] Francois Bodin, Peter Beckman, Dennis Gannon, Srinivas Narayana, and Shelby X. Yang. Distributed pC++: Basic ideas for an object parallel language. Scientific Programming, 2(3), Fall 1993.
• 13: [13] Fabian E. Bustamante, Greg Eisenhauer, Karsten Schwan, and Patrick Widener. Active Streams and the Effects of Stream Specialization. In Poster in Proc. of Tenth International Symposium on High Performance Distributed Computing (HPDC-2001). IEEE Computer Society Press, August 2001.
• 14: [14] Srinivas Chippada, Clint N. Dawson, Monica L. Martínez, and Mary F. Wheeler. A Godunov-type finite volume method for the system of shallow water equations. Computer Methods in Applied Mechanics and Engineering (to appear), 1997. Also a TICAM Report 96-57, University of Texas, Austin, TX 78712.
• 15: Renato Ferreira , Bongki Moon , Jim Humphries , Alan Sussman , Joel Saltz , Robert Miller , Angelo Demarzo, The virtual microscope, University of Maryland at College Park, College Park, MD, 1997
• 16: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 17: [17] Ian Foster, Carl Kesselman, and Steven Tuecke. The Anatomy of Grid: Enabling Scalable Virtual Organizations. International Journal of Supercomputing Applications, 2001.
• 18: Dennis Gannon , Andrew Grimshaw, Object-based approaches, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 19: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 20: Andrew S. Grimshaw , William A. Wulf , James C. French , Alfred C. Weaver , Paul F. Reynolds, Jr., Legion: The Next Logical Step Toward a Nationwide Virtual Computer, University of Virginia, Charlottesville, VA, 1994
• 21: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 22: [22] High Performance Fortran Forum. Hpf language specification, version 2.0. Available from http://www.crpc.rice.edu/HPFF/versions/hpf2/files/hpf-v20.ps.gz, January 1997.
• 23: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 24: ACDS: Adapting Computational Data Streams for High Performance, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.641, May 01-05, 2000
• 25: [25] Ruoming Jin and Gagan Agrawal. A middleware for developing parallel data mining implementations. In Proceedings of the first SIAM conference on Data Mining, April 2001.
• 26: Sanjay M. Krishamurthy, A brief survey of papers on scheduling for pipelined processors, ACM SIGPLAN Notices, v.25 n.7, p.97-106, July 1990 [doi>10.1145/382076.382650]
• 27: [27] Land Satellite Thematic Mapper (TM). http://edcwww.cr.usgs.gov/nsdi/html/landsat_tm/landsat_tm.
• 28: Miron Livny , Rajesh Raman, High-throughput resource management, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 29: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 30: [30] Richard A. Luettich, Johannes J. Westerink, and Norman W. Scheffner. ADCIRC: An advanced three-dimensional circulation model for shelves, coasts, and estuaries. Technical Report 1, Department of the Army, U.S. Army Corps of Engineers, Washington, D.C. 20314-1000, December 1991.
• 31: Kwan-Liu Ma , Z. C. Zheng, 3D visualization of unsteady 2D airplane wake vortices, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 32: [32] The Moderate Resolution Imaging Spectrometer. http://ltpwww.gsfc.nasa.gov/MODIS/MODIS.html.
• 33: [33] NASA Goddard Distributed Active Archive Center (DAAC). Advanced Very High Resolution Radiometer Global Area Coverage (AVHRR GAC) data. http://daac.gsfc.nasa.gov/CAMPAIGN_DOCS/ LAND_BIO/origins.html.
• 34: [34] Grid Physics Network. GriPhyN. http://www.griphyn.org.
• 35: [35] Ron Oldfield. Summary of existing and developing data grids. White paper, Remote Data Access Group, Global Grid Forum, available from http://www.sdsc.edu/GridForum/RemoteData/Papers/papers.html.
• 36: [36] G. Patnaik, K. Kailasnath, and E.S. Oran. Effect of gravity on flame instabilities in premixed gases. AIAA Journal, 29(12):2141-8, Dec 1991.
• 37: Beth Plale , Karsten Schwan, dQUOB: Managing Large Data Flows Using Dynamic Embedded Queries, Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing, p.263, August 01-04, 2000
• 38: [38] Teragrid project partners. The TeraGrid: A Primer, September 2002. Available at www.teragrid.org.
• 39: Umakishore Ramachandran , Rishiyur S. Nikhil , Nissim Harel , James M. Rehg , Kathleen Knobe, Space-time memory: a parallel programming abstraction for interactive multimedia applications, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.183-192, May 04-06, 1999, Atlanta, Georgia, United States
• 40: [40] T. Tanaka. Configurations of the solar wind flow and magnetic field around the planets with no magnetic field: calculation by a new MHD. Jounal of Geophysical Research, 98(A10):17251-62, Oct 1993.
• 41: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 42: Randolph Y. Wang , Arvind Krishnamurthy , Richard P. Martin , Thomas E. Anderson , David E. Culler, Modeling communication pipeline latency, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.22-32, June 22-26, 1998, Madison, Wisconsin, United States
• 43: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]
• 44: Mau-Tsuen Yang , Rangachar Kasturi , Anand Sivasubramaniam, Automatic Scheduler for Real-Time Vision Applications, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.30, April 23-27, 2001
• 45: [45] K. Yelick, L. Semenzato, G. Pike, C. Miyamoto, B. Libit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, P. Colella, and A. Aiken. Titanium: A high-performance Java dialect. Concurrency Practice and Experience, 9(11), November 1998.