Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Collective communication operations can dominate the cost of large-scale parallel algorithms. Image compositing in parallel scientific visualization is a reduction operation where this is the case. We present a new algorithm called Radix-k that in many cases performs better than existing compositing algorithms. It does so through a set of configurable parameters, the radices, that determine the number of communication partners in each message round. The algorithm embodies and unifies binary swap and direct-send, two of the best-known compositing methods, and enables numerous other configurations through appropriate choices of radices. While the algorithm is not tied to a particular computing architecture or network topology, the selection of radices allows Radix-k to take advantage of new supercomputer interconnect features such as multiporting. We show scalability across image size and system size, including both powers of two and nonpowers-of-two process counts.

REFERENCES

• 1: Argonne Leadership Computing Facility. 2009. http://www.alcf.anl.gov/.
• 2: J. Ahrens and J. Painter. Efficient sort-last rendering using compression-based image compositing. In Proc. Eurographics Parallel Graphics and Visualization Symposium 2008, Bristol, United Kingdom, 1998.
• 3: Mike Barnett , Lance Shuler , Satya Gupta , David G. Payne , Robert van de Geijn , Jerrell Watts, Building a high-performance collective communication library, Proceedings of the 1994 conference on Supercomputing, p.107-116, December 1994, Washington, D.C., United States
• 4: Mike Barnett , David G. Payne , Robert A. van de Geijn , Jerrell Watts, Broadcasting on meshes with wormhole routing, Journal of Parallel and Distributed Computing, v.35 n.2, p.111-122, June 15, 1996 [doi>10.1006/jpdc.1996.0074]
• 5: M. Bernaschi and G. Iannello. Collective communication operations: Experimental results vs. theory. Concurrency, 10(5):359--386, 1998.
• 6: Jehoshua Bruck , Ching-Tien Ho , Shlomo Kipnis , Derrick Weathersby, Efficient algorithms for all-to-all communications in multi-port message-passing systems, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181756]
• 7: X. Cavin, C. Mion, and A. Fibois. Cots cluster-based sort-last rendering: Performance evaluation and pipelined implementation. In Proc. IEEE Visualization 2005, pages 111--118, 2005.
• 8: Anthony Chan , William Gropp , Ewing Lusk, An efficient format for nearly constant-time access to arbitrary time intervals in large trace files, Scientific Programming, v.16 n.2-3, p.155-165, April 2008
• 9: Ernie Chan , Marcel Heimlich , Avi Purkayastha , Robert van de Geijn, Collective communication: theory, practice, and experience: Research Articles, Concurrency and Computation: Practice & Experience, v.19 n.13, p.1749-1783, September 2007 [doi>10.1002/cpe.v19:13]
• 10: Ernie Chan , Robert van de Geijn , William Gropp , Rajeev Thakur, Collective communication on architectures that support simultaneous communication over multiple links, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122975]
• 11: William M. Hsu, Segmented ray casting for data parallel volume rendering, Proceedings of the 1993 symposium on Parallel rendering, p.7-14, October 25-26, 1993, San Jose, California, United States [doi>10.1145/166181.166182]
• 12: Greg Humphreys , Mike Houston , Ren Ng , Randall Frank , Sean Ahern , Peter D. Kirchner , James T. Klosowski, Chromium: a stream-processing framework for interactive rendering on clusters, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 13: Sameer Kumar , Gabor Dozsa , Gheorghe Almasi , Philip Heidelberger , Dong Chen , Mark E. Giampapa , Michael Blocksome , Ahmad Faraj , Jeff Parker , Joseph Ratterman , Brian Smith , Charles J. Archer, The deep computing messaging framework: generalized scalable message passing on the blue gene/P supercomputer, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375544]
• 14: Sameer Kumar , Gabor Dozsa , Jeremy Berg , Bob Cernohous , Douglas Miller , Joseph Ratterman , Brian Smith , Philip Heidelberger, Architecture of the Component Collective Messaging Interface, Proceedings of the 15th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, September 07-10, 2008, Dublin, Ireland [doi>10.1007/978-3-540-87475-1_10]
• 15: Tong-Yee Lee , C. S. Raghavendra , John B. Nicholas, Image Composition Schemes for Sort-Last Polygon Rendering on 2D Mesh Multicomputers, IEEE Transactions on Visualization and Computer Graphics, v.2 n.3, p.202-217, September 1996 [doi>10.1109/2945.537304]
• 16: Kwan-Liu Ma , Victoria Interrante, Extracting feature lines from 3D unstructured grids, Proceedings of the 8th conference on Visualization '97, p.285-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 17: Kwan-Liu Ma , James S. Painter , Charles D. Hansen , Michael F. Krogh, Parallel Volume Rendering Using Binary-Swap Compositing, IEEE Computer Graphics and Applications, v.14 n.4, p.59-68, July 1994 [doi>10.1109/38.291532]
• 18: Steven Molnar , Michael Cox , David Ellsworth , Henry Fuchs, A Sorting Classification of Parallel Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.23-32, July 1994 [doi>10.1109/38.291528]
• 19: Kenneth Moreland , Brian Wylie , Constantine Pavlakos, Sort-last parallel rendering for viewing extremely large data sets on tile displays, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
• 20: Ulrich Neumann, Parallel volume-rendering algorithm performance on mesh-connected multicomputers, Proceedings of the 1993 symposium on Parallel rendering, p.97-104, October 25-26, 1993, San Jose, California, United States [doi>10.1145/166181.166196]
• 21: Ulrich Neumann, Communication Costs for Parallel Volume-Rendering Algorithms, IEEE Computer Graphics and Applications, v.14 n.4, p.49-58, July 1994 [doi>10.1109/38.291531]
• 22: J. Nonaka, K. Ono, and H. Miyachi. Theoretical and practical performance and scalability analyses of binary-swap image composition method on ibm blue gene/l. In Proc. 2008 International Workshop on Super Visualization (unpublished manuscript), Kos, Greece, 2008.
• 23: Thomas Porter , Tom Duff, Compositing digital images, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.253-259, January 1984
• 24: David Pugmire , Laura Monroe , Carolyn Connor Davenport , Andrew DuBois , David DuBois , Stephen Poole, NPU-Based Image Compositing in a Distributed Visualization System, IEEE Transactions on Visualization and Computer Graphics, v.13 n.4, p.798-809, July 2007 [doi>10.1109/TVCG.2007.1026]
• 25: R. Rabenseifner. New Optimized MPI Reduce Algorithm. 2004. http://www.hlrs.de/organization/par/services/models/mpi/myreduce.html.
• 26: R. Rabenseifner and J. L. Traff. More efficient reduction algorithms for non-power-of-two number of processors in message-passing parallel systems. In Proc. EuroPVM/MPI 2004, pages 36--46, Budapest, Hungary, 2004.
• 27: Aleksander Stompel , Kwan-Liu Ma , Eric B. Lum , James Ahrens , John Patchett, SLIC: Scheduled Linear Image Compositing for Parallel Volume Rendering, Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, p.6, October 20-21, 2003 [doi>10.1109/PVGS.2003.1249040]
• 28: Akira Takeuchi , Fumihiko Ino , Kenichi Hagihara, An improved binary-swap compositing for sort-last parallel rendering on distributed memory multiprocessors, Parallel Computing, v.29 n.11-12, p.1745-1762, November/December 2003 [doi>10.1016/j.parco.2003.05.015]
• 29: R. Thakur, R. Rabenseifner, and W. Gropp. Optimization of collective communication operations in mpich. International Journal of High Performance Computing Applications, 19:49--66, 2005.
• 30: J. L. Traff. An improved algorithm for (non-commutative) reduce-scatter with an application. In Proc. EuroPVM/MPI 2005, pages 129--137, Sorrento, Italy, 2005.
• 31: Jesper Larsson Träff , Andreas Ripke , Christian Siebert , Pavan Balaji , Rajeev Thakur , William Gropp, A Simple, Pipelined Algorithm for Large, Irregular All-gather Problems, Proceedings of the 15th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, September 07-10, 2008, Dublin, Ireland [doi>10.1007/978-3-540-87475-1_16]
• 32: Hongfeng Yu , Chaoli Wang , Kwan-Liu Ma, Massively parallel volume rendering using 2-3 swap image compositing, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Keywords:
communication, image compositing, parallel scientific visualization