{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T15:41:03Z","timestamp":1751384463093,"version":"3.38.0"},"reference-count":49,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2003,2,1]],"date-time":"2003-02-01T00:00:00Z","timestamp":1044057600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2003,2]]},"abstract":"<jats:p> 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 \u03b1\u03b2 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. <\/jats:p>","DOI":"10.1177\/1094342003017001007","type":"journal-article","created":{"date-parts":[[2003,6,25]],"date-time":"2003-06-25T22:04:01Z","timestamp":1056578641000},"page":"77-93","source":"Crossref","is-referenced-by-count":12,"title":["Programming, Tuning and Automatic Parallelization of Irregular                Divide-and-Conquer Applications in DAMPVM\/DAC"],"prefix":"10.1177","volume":"17","author":[{"given":"Pawel","family":"Czarnul","sequence":"first","affiliation":[{"name":"GDANSK UNIVERSITY OF TECHNOLOGY, POLAND"}]}],"member":"179","published-online":{"date-parts":[[2003,2,1]]},"reference":[{"unstructured":"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.","key":"atypb1"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb2","DOI":"10.1145\/209937.209958"},{"unstructured":"Bricker, A., Litzkow, M., and Livny, M. 1991. Condor Technical Summary. Technical report, Computer Sciences Department, University of Wisconsin-Madison.","key":"atypb3"},{"unstructured":"Brockington, M. 1998. Asynchronous Parallel Game-Tree Search. PhD thesis, Department of Computing Science, University of Alberta, Edmonton, Canada. www.cs.ualberta.ca\/~games\/articles\/mgb_thesis.ps.gz.","key":"atypb4"},{"unstructured":"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).","key":"atypb5"},{"unstructured":"Buyya, R., ed. 1999. High Performance Cluster Computing, Programming and Applications. Prentice Hall .","key":"atypb6"},{"unstructured":"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.","key":"atypb7"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb8","DOI":"10.1109\/ICPP.1996.538578"},{"doi-asserted-by":"publisher","key":"atypb9","DOI":"10.1109\/71.809572"},{"unstructured":"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.","key":"atypb10"},{"unstructured":"Coulouris, G., Dollimore, J., and Kindberg, T. 2001. Distributed Systems - Concepts and Design. Addison-Wesley .","key":"atypb11"},{"doi-asserted-by":"crossref","unstructured":"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.","key":"atypb12","DOI":"10.1109\/PCEE.2002.1115218"},{"doi-asserted-by":"publisher","key":"atypb13","DOI":"10.1007\/3-540-48158-3_63"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb14","DOI":"10.1007\/3-540-45417-9_26"},{"unstructured":"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 .","key":"atypb15"},{"unstructured":"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\/.","key":"atypb16"},{"doi-asserted-by":"publisher","key":"atypb17","DOI":"10.1145\/311094.311100"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb18","DOI":"10.1007\/3-540-44520-X_37"},{"unstructured":"Erlebach, T. 1995. APRIL 1.0 User Manual, Automatic Parallelization of Divide and Conquer Algorithms. Technische Universitat Munchen, Germany , http:\/\/www.mayr.informatik.tu-muenchen.de\/personen\/erlebach\/aperitif.html.","key":"atypb19"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb20","DOI":"10.1109\/EMPDP.1996.500614"},{"doi-asserted-by":"crossref","unstructured":"Feldmann, R., Mysliwietz, P., and Monien, B. 1994. Studying overheads in massively parallel MIN\/MAX-tree evaluation . In: Proceedings of the 6th ACM Symposium on Parallel Algorithms and Architectures (SPAA '94), pp. 94-103 , http:\/\/www.uni-paderborn.de\/fachbereich\/AG\/monien\/PUBLICATIONS\/POSTSCRIPTS\/FMM_Studying_Overheads_1994.ps.Z.","key":"atypb21","DOI":"10.1145\/181014.192325"},{"doi-asserted-by":"crossref","unstructured":"Gatlin, K.S. and Carter, L. 1999. Architecture-cognizant divide and conquer algorithms. In: SuperComputing '99.","key":"atypb22","DOI":"10.1145\/331532.331557"},{"unstructured":"Geist, A. 1997. Advanced Tutorial on PVM 3.4 New Features and Capabilities, http:\/\/www.csm.ornl.gov\/pvm\/EuroPVM97\/.","key":"atypb23"},{"doi-asserted-by":"crossref","unstructured":"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\/.","key":"atypb24","DOI":"10.7551\/mitpress\/5712.001.0001"},{"unstructured":"Gropp, W. and Lusk, E. 2001. User's Guide for MPICH, a Portable Implementation of MPIVersion 1.2.2. http:\/\/www-unix.mcs.anl.gov\/mpi\/mpich\/.","key":"atypb25"},{"doi-asserted-by":"publisher","key":"atypb26","DOI":"10.1109\/TC.1983.1676280"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb27","DOI":"10.1007\/3-540-45255-9_8"},{"doi-asserted-by":"publisher","key":"atypb28","DOI":"10.1109\/TSE.1987.232563"},{"doi-asserted-by":"publisher","key":"atypb29","DOI":"10.1109\/71.539736"},{"doi-asserted-by":"crossref","unstructured":"Loidl, H. and Hammond, K. 1995. On the granularity of divide-and-conquer parallelism . In: Proceedings of GlaFP, WICS, Ullapool, Scotland, Springer-Verlag. http:\/\/www.dcs.gla.ac.uk\/~hwloidl\/publications\/GlaFp95.ps.gz.","key":"atypb30","DOI":"10.14236\/ewic\/FP1995.13"},{"unstructured":"Luling, R., Monien, B., and Ramme, F. 1992. A study on dynamic load balancing algorithms. Technical Report TR-001-92, Paderborn Center for Parallel Computing, www.uni-paderborn.de\/fachbereich\/AG\/monien\/PUBLICATIONS\/POSTSCRIPTS\/LMR_Dyn_Load_Balancing_92.ps.Z.","key":"atypb31"},{"doi-asserted-by":"publisher","key":"atypb32","DOI":"10.1007\/BF00129780"},{"unstructured":"Oak Ridge National Laboratory, U.S.A. 1997 PVM Documentation: Listing of new features found in PVM 3.4 and past PVM versions http:\/\/www.epm.ornl.gov\/pvm\/changes.html#pvm3.4.0.","key":"atypb33"},{"doi-asserted-by":"publisher","key":"atypb34","DOI":"10.1109\/71.605773"},{"unstructured":"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.","key":"atypb35"},{"doi-asserted-by":"publisher","key":"atypb36","DOI":"10.1109\/71.983944"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb37","DOI":"10.1109\/APS.2001.960158"},{"unstructured":"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.","key":"atypb38"},{"doi-asserted-by":"publisher","key":"atypb39","DOI":"10.1155\/1994\/856294"},{"doi-asserted-by":"publisher","key":"atypb40","DOI":"10.1109\/71.506702"},{"unstructured":"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.","key":"atypb41"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb42","DOI":"10.1109\/IPPS.1999.760460"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb43","DOI":"10.1007\/3-540-44520-X_96"},{"doi-asserted-by":"publisher","key":"atypb44","DOI":"10.1109\/71.674316"},{"unstructured":"Wilkinson, B. and Allen, M. 1999. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall .","key":"atypb45"},{"doi-asserted-by":"publisher","key":"atypb46","DOI":"10.1109\/71.243526"},{"doi-asserted-by":"crossref","unstructured":"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 .","key":"atypb47","DOI":"10.1007\/3-540-54945-5_67"},{"doi-asserted-by":"publisher","key":"atypb48","DOI":"10.1109\/71.577261"},{"unstructured":"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 .","key":"atypb49"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342003017001007","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342003017001007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T16:08:18Z","timestamp":1740931698000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342003017001007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,2]]}},"alternative-id":["10.1177\/1094342003017001007"],"URL":"https:\/\/doi.org\/10.1177\/1094342003017001007","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}