This paper presents a new object oriented framework DAMPVM/DAC which is implemented on top of DAMPVM and provides automatic partitioning of irregular divide-and-conquer (DAC) applications at runtime. The processes are then mapped dynamically to processors taking into account their speeds and even loads by other user processes. The paper presents the programming interface (API) of the framework, available tuning mechanisms, internal solutions with respect to automatic partitioning and mapping to processors. Finally, specific parameters, optimization techniques and simulation results are shown for a variety of irregular divide-and-conquer applications. The applications include αβ search, recursive Fibonacci, ([UNKNOWN]), finding twin prime numbers in parallel and previously implemented and now carefully analyzed and tuned adaptive quadrature integration and image recognition.Various DAC parameters were tuned for specific applications including costs of computing vectors/subtrees, maximum partitioning levels etc. Moreover, the overhead of DAMPVM/DAC compared to sequential implementations is shown for all the implemented applications.
Get full access to this article
View all access options for this article.
References
1.
Baldeschwieler, J., Blumofe, R., and Brewer, E. 1996. ATLAS: An infrastructure for global computing . In: Proceedings of the Seventh ACM SIGOPS European Workshop on System Support for Worldwide Applications, Connemara, Ireland.
2.
Blumofe, R., Joerg, C., Kuszmaul, B., Leiserson, C., Randall, K., and Zhou, Y. 1995. Cilk: An efficient multithreaded runtime system . In: Proceedings of the 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 207-216 .
3.
Bricker, A., Litzkow, M., and Livny, M. 1991. Condor Technical Summary. Technical report, Computer Sciences Department, University of Wisconsin-Madison.
Brockington, M.G. and Schaeffer, J. 1996. The APHID parallel alpha-beta search algorithm . In: Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96).
6.
Buyya, R., ed. 1999. High Performance Cluster Computing, Programming and Applications. Prentice Hall .
7.
Casas, J., Clark, D., Konuru, R., Otto, S., Prouty, R., and Walpole, J. 1995. MPVM: A Migration Transparent Version of PVM. Technical report, Department of Computer Science and Engineering, Oregon Graduate Institute of Science & Technology.
8.
Chanchio, K. and Sun, X. 1996. MpPVM: A software system for non-dedicated heterogeneous computing . In: Proceedings of the International Conference on Parallel Processing, volume 3, pp. 215-222 .
9.
Chi-Chung, H. and Chanson, S. 1999. Hydrodynamic load balancing . IEEE Transactions on Parallel and Distributed Systems, 10: 1118-1137 .
10.
Cortes, A., Ripoll, A., Senar, M., and Luque, E. 1999. Performance comparison of dynamic load-balancing strategies for distributed computing . In: Proceedings of the Thirty-second Annual Hawaii International Conference on System Sciences.
11.
Coulouris, G., Dollimore, J., and Kindberg, T. 2001. Distributed Systems - Concepts and Design. Addison-Wesley .
12.
Czarnul, P. 2002. Dynamic process partitioning and migration for irregular applications . In: Proceedings of International Conference on Parallel Computing in Electrical Engineering PARELEC '2002, pp. 123-130 , http://www.parelec.org.
13.
Czarnul, P. and Krawczyk, H. 1999. Dynamic assignment with process migration in distributed environments . In: Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science, 1697: 509-516 .
14.
Czarnul, P., Tomko, K., and Krawczyk, H.: 2001a. Dynamic partitioning of the divide-and-conquer scheme with migration in PVM environment . In: Recent Advances in Parallel Virtual Machine and Message Passing Interface. 8th European PVM/MPI Users' Group Meeting, Santorini/Thera, Greece, September 23-26, Lecture Notes in Computer Science, 2131: 174-182 .
15.
Czarnul, P., Tomko, K., and Krawczyk, H. 2001b. A heuristic dynamic load balancing algorithm for meshes . In: Parallel and Distributed Computing and Systems, Proceedings of the IASTED International Conference, Anaheim, CA, U.S.A., pp. 166-171 .
16.
Czarnul, P., Venkatasubramanian, S., Sarris, C.D., Hung, S.H., Chun, D., Tomko, K., Davidson, E.S., Katehi, L.P.B., and Perlman, B. 2001c. Locality enhancement and parallelization of an FDTD simulation . In: Proceedings of the 2001 DoD/HPCMO Users Conference, U.S.A. http://www.hpcmo.hpc.mil/Htdocs/UGC/UGC01/.
17.
Dan, P., Dongsheng, W., Youhui, Z., and Meiming, S. 1999. Quasi-asynchronous migration: A novel migration protocol for PVM tasks . Operating Systems Review, 33: 5-14 .
18.
Decker, T., Monien, B., and Preis, R. 2000. Towards optimal load balancing topologies . In: Proceedings of the 6th EuroPar Conference, Lecture Notes in Computer Science, 1900: 277-287 .
Fabero, J.C., Martin, I., Bautista, A., and Molina, S. 1996. Dynamic load balancing in a heterogeneous environment under PVM . In: IEEE Proceedings of PDP '96, Braga, Portugal, pp. 414-419 .
Geist, A., Beguelin, A., Dongarra, J., Jiang, W., Mancheck, R., and Sunderam, V. 1994. PVM Parallel Virtual Machine. A Users Guide and Tutorial for Networked Parallel Computing. MIT Press, Cambridge . http://www.epm.ornl.gov/pvm/.
Horowitz, E. and Zorat, A. 1983. Divide-and-conquer for parallel processing . IEEE Transactions on Computers, C-32: 582-585 .
27.
Iskra, K., Hendrikse, Z., van Albada, G., Overeinder, B., and Sloot, P. 2000. Performance measurements on Dynamite/DPVM . In: Proceedings of Euro PVM/MPI 2000, Lecture Notes in Computer Science, 1908: 27-38 .
28.
Lin, F.C.H. and Keller, R.M. 1987. The gradient model load balancing method . IEEE Transactions on Software Engineering, SE-13: 32-38 .
29.
Lo, V., Rajopadhye, S., Telle, J., and Zhong, X. 1996. Parallel divide and conquer on meshes . IEEE Transactions on Parallel and Distributed Systems, 7: 1049-1057 .
Ou, C.W. and Ranka, S. 1997. Parallel incremental graph partitioning . IEEE Transactions on Parallel and Distributed Systems, 8: 884-896 .
35.
Piper, A. and Prager, R. 1993. Generalized Parallel Programming with Divide-and-Conquer: The Beeblebrox System. Technical Report CUED/F-INFENG/TR132, Cambridge University Engeneering Department ftp://svr-ftp.eng.cam.ac.uk/pub/reports/piper_tr132.ps.Z.
36.
Prechelt, L. and Hänßgen, S. 2002. Efficient parallel execution of irregular recursive programs . IEEE Transactions on Parallel and Distributed Systems, 13: 167-178 .
37.
Sarris, C.D., Tomko, K., Czarnul, P., Hung, S.H., Robertson, R.L., Chun, D., Davidson, E.S., and Katehi, L.P.B. 2001. Multiresolution time domain modeling for large scale wireless communication problems . In: Proceedings of the 2001 IEEE AP-S International Symposium on Antennas and Propagation, volume 3, pp. 557-560 .
38.
Schloegel, K., Karypis, G., and Kumar, V. 2000. Graph partitioning for high performance scientific simulations. In: CRPC Parallel Computing Handbook. Morgan Kaufmann , http://citeseer.nj.nec.com/schloege100graph.html.
39.
Shu, W. 1994. Adaptive dynamic process scheduling on distributed memory parallel computers . Scientific Programming, 3: 341-352 .
40.
Shu, W. and Wu, M.Y. 1996. Runtime incremental parallel scheduling (RIPS) on distributed memory computers . IEEE Transactions on Parallel and Distributed Systems, 7: 637-649 .
41.
Silvestre, J.P., and Romke, T. 1997. Programming Frames for the Efficient Use of Parallel Systems. Technical Report TR-183-97, Paderborn Center for Parallel Computing.
42.
Tan, C.P., Wong, W.F., and Yuen, C.K. 1999. tmPVM - Task Migratable PVM . In: Proceedings of the 2nd Merged Symposium IPPS/SPDP, pp. 196-202 .
43.
van Nieuwpoort, R.V., Kielmann, T., and Bal, H.E. 2000. Satin: Efficient parallel divide-and-conquer in Java . In: Euro-Par 2000 Parallel Processing, Proceedings of the 6th International Euro-Par Conference, Lecture Notes in Computer Science, 1900: 690-699 .
44.
Watts, J. and Taylor, S. 1998. A practical approach to dynamic load balancing . IEEE Transactions on Parallel and Distributed Systems, 9: 235-248 .
45.
Wilkinson, B. and Allen, M. 1999. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall .
46.
Willebeek-LeMair, M. and Reeves, A. 1993. Strategies for dynamic load balancing on highly parallel computers . IEEE Transactions on Parallel and Distributed Systems, 4: 979-993 .
47.
Wu, I. 1991. Efficient parallel divide-and-conquer for a class of interconnection Topologies . In: Proceedings of the 2nd International Symposium on Algorithms, Lecture Notes in Computer Science, 557: 229-240 .
48.
Wu, M.Y. 1997. On runtime parallel scheduling for processor load balancing . IEEE Transactions on Parallel and Distributed Systems, 8: 173-186 .
49.
Xu, C., Monien, B., Luling, R., and Lau, F.C.M. 1995. An analytical comparison of nearest neighbor algorithms for load balancing in parallel computers . In: Proceedings of the 9th International Parallel Processing Symposium (IPPS '95), IEEE Computer Society Press, pp. 472-479 .
