Optimizing Reduction Computations In a Distributed Environment

ABSTRACT

We investigate runtime strategies for data-intensive applications that invovle generalized reductions on large, distributed datasets.Our set of strategies includes replicated filter state, partitioned filter state, and hybrid options between these two extremes.We evaluate these strategies using emulators of three real applications, different query and output sizes, and a number of configurations.We consider execution in a homogeneous cluster and in a distributed environment where only a subset of nodes hst the data.Our results show replicating the filter state scales well and outperforms other schemes, if sufficient memory is available and sufficient computation is involved to offset the cost of global merge step.In other cases, hybrid is usually the best.Moreover, in almost all cases, the performance of the hybrid strategy is quite close to the best strategy. Thus, we believe that hybrid is an attractive approach when the relative performance of different schemes cannot be predicted.

REFERENCES

• 1: [1] A. Afework, M. D. Beynon, F. Bustamante, A. Demarzo, R. Ferreira, R. Miller, M. Silberman, J. Saltz, A. Sussman, and H. Tsang. Digital dynamic telepathology - the Virtual Microscope. In Proceedings of the 1998 AMIA Annual Fall Symposium. American Medical Informatics Association, Nov. 1998.
• 2: [2] G. Agrawal, R. Jin, and X. Li. Middleware and compiler support for scalable data mining. In Proceedings of Languages and Compilers for Parallel Computing (LCPC), 2001.
• 3: Bill Allcock , Ian Foster , Veronika Nefedova , Ann Chervenak , Ewa Deelman , Carl Kesselman , Jason Lee , Alex Sim , Arie Shoshani , Bob Drach , Dean Williams, High-performance remote access to climate simulation data: a challenge problem for data grid technologies, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.46-46, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582080]
• 4: 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]
• 5: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• 6: Randy Butler , Von Welch , Douglas Engert , Ian Foster , Steven Tuecke , John Volmer , Carl Kesselman, A National-Scale Authentication Infrastructure, Computer, v.33 n.12, p.60-66, December 2000 [doi>10.1109/2.889094]
• 7: [7] U. Catalyurek, M. D. Beynon, C. Chang, T. Kurc, A. Sussman, and J. Saltz. The virtual microscope. IEEE Transactions on Information Technology in Biomedicine, 2003. To appear.
• 8: [8] Common Component Architecture Forum. http://www.cca-forum.org.
• 9: [9] C. Chang. Cost models for query processing strategies in the active data repository. Technical Report CS-TR-4060 and UMIACS-TR-99-54, University of Maryland, Department of Computer Science and UMIACS, Sept. 1999.
• 10: [10] C. Chang, T. Kurc, A. Sussman, U. Catalyurek, and J. Saltz. A hypergraph-based workload partitioning strategy for parallel data aggregation. In Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Mar. 2001.
• 11: Optimizing Retrieval and Processing of Multi-Dimensional Scientific Datasets, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.405, May 01-05, 2000
• 12: Chialin Chang , Bongki Moon , Anurag Acharya , Carter Shock , Alan Sussman , Joel H. Saltz, Titan: A High-Performance Remote Sensing Database, Proceedings of the Thirteenth International Conference on Data Engineering, p.375-384, April 07-11, 1997
• 13: [13] A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke. The Data Grid: Towards an architecture for the distributed management and analysis of large scientific datasets. Journal of Network and Computer Applications: Special Issue on Network-Based Storage Services, 23(3):187-200, July 2000.
• 14: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.462-478, Sept. 1994 [doi>10.1006/jpdc.1994.1104]
• 15: Christos Faloutsos , Pravin Bhagwat, Declustering using fractals, Proceedings of the second international conference on Parallel and distributed information systems, p.18-25, January 1993, San Diego, California, United States
• 16: [16] R. Ferreira, T. Kurc, M. Beynon, C. Chang, A. Sussman, and J. Saltz. Object-relational queries into multi-dimensional databases with the Active Data Repository. Parallel Processing Letters, 9(2):173-195, 1999.
• 17: [17] R. Ferreira, B. Moon, J. Humphries, A. Sussman, J. Saltz, R. Miller, and A. Demarzo. The Virtual Microscope. In Proceedings of the 1997 AMIA Annual Fall Symposium, pages 449-453. American Medical Informatics Association, Hanley and Belfus, Inc., Oct. 1997.
• 18: [18] I. Foster and C. Kesselman. Globus: A metacomputing infrastructure toolkit. International Journal of Supercomputer Applications and High Performance Computing, 11(2):115-128, 1997.
• 19: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 20: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 21: [21] Global Grid Forum. http://www.gridforum.org.
• 22: Andrew Grimshaw , Adam Ferrari , Frederick Knabe , Marty Humphrey, Wide-Area Computing: Resource Sharing on a Large Scale, Computer, v.32 n.5, p.29-37, May 1999 [doi>10.1109/2.762790]
• 23: Hwansoo Han , Chau-Wen Tseng, Improving Compiler and Run-Time Support for Irregular Reductions Using Local Writes, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.181-196, August 07-09, 1998
• 24: [24] R. Jin and G. Agrawal. A middleware for developing parallel data mining implementations. In Proceedings of the first SIAM conference on Data Mining, Apr. 2001.
• 25: Tahsin Kurc , Ümit Çatalyürek , Chialin Chang , Alan Sussman , Joel Saltz, Visualization of Large Data Sets with the Active Data Repository, IEEE Computer Graphics and Applications, v.21 n.4, p.24-33, July 2001 [doi>10.1109/38.933521]
• 26: Tahsin Kurc , Chialin Chang , Renato Ferreira , Alan Sussman , Joel Saltz, Querying very large multi-dimensional datasets in ADR, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.12-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331544]
• 27: [27] T. M. Kurc, A. Sussman, and J. Saltz. Coupling multiple simulations via a high performance customizable database system. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Mar. 1999.
• 28: [28] F. Lee, T. Kurc, G. Agrawal, U. Catalyurek, R. Ferreira, and J. Saltz. Optimizing reduction computations in a distributed environment. Technical Report OSU-CISRC-4/02-TR20, Department of Computer and Information Sciences, The Ohio State University, April 2003.
• 29: Ron Oldfield , David Kotz, Armada: A Parallel File System for Computational Grids, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.194, May 15-18, 2001
• 30: 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
• 31: Ambuj Shatdal , Jeffrey F. Naughton, Adaptive parallel aggregation algorithms, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.104-114, May 22-25, 1995, San Jose, California, United States
• 32: [32] SRB: The Storage Resource Broker. http://www.npaci.edu/DICE/SRB/index.html.
• 33: [33] The TeraGrid: A Primer, September 2002. Available at www.teragrid.org.
• 34: Mustafa Uysal , Tahsin M. Kurç , Alan Sussman , Joel H. Saltz, A Performance Prediction Framework for Data Intensive Applications on Large Scale Parallel Machines, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.243-258, May 28-30, 1998
• 35: Hao Yu , Lawrence Rauchwerger, Adaptive reduction parallelization techniques, Proceedings of the 14th international conference on Supercomputing, p.66-77, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335238]