Image compositing is the final stage in sort-last parallel rendering, where the images that were computed separately by parallel processes are blended together into one final image. All processes need to exchange their images quickly and efficiently.
Direct-send and binary swap are the usual algorithms for image compositing. Radix-k is our algorithm, which allows custom configuration of the number of compositing stages and the amount of communication concurrency in each stage. Examples of these algorithms are shown below. Further reading: Peterka, T., Goodell, D., Ross, R., Shen, H.-W., Thakur, R.: A Configurable Algorithm for Parallel Image-Compositing Applications. Proceedings of SC09, Portland OR, November 2009. pdf bibtex
The advantages of the Radix-k algorithm are listed below. Direct-send and binary swap are no longer treated as separate algorithms: rather, as two valid configurations out of many.
On the Intrepid Blue Gene/P supercomputer at Argonne National Laboratory, Radix-k outperforms binary swap by 40% across the board from 32 to 35,000 processes.
When optimizations such as bounding boxes and run-length encoding are added, Radix-k outperforms binary swap by up to 5X. 64-megapixel images were composited across 32,000 processes at an interactive rate of 12.5 frames per second. Further reading: Kendall, W., Peterka, T., Huang, J., Shen, H.-W., Ross, R.: Accelerating and Benchmarking Radix-k Image Compositing at Large Scale. Proceedings of EG PGV'10, Norrkoping, Sweden, May 2010. pdf bibtex
