An efficient load-balancing algorithm for image processing applications on multicore processors

ABSTRACT

The significance of load-balancing is rising with the increasing number of processing cores per chip. A fast load-balancer is sought to exploit fine grain parallelism possible with multicore processors. This paper focuses on load-balancing image processing applications where the amount of processing varies per pixel; such application domain includes high dynamic range imaging and fractal related applications. This paper formulates load-balancing, for such applications, as a curve fitting problem for statistically sampled work across the image. Such formulation allows for analytically determining an optimal load-balance partitioning, resulting in accurate, low-overhead load-balancing. Experiments using the proposed algorithm shows a remarkable performance of achieving around 90% of 'perfect' image partitioning for a complex fractal application.

REFERENCES

• 1: From a few cores to many: A tera-scale computing research overview. white paper, Intel, 2006. ftp://download.intel.com/research/platform/terascale/terascale_overview_paper.pdf.
• 2: F. R. Diard. Adaptive load balancing in a multi-processor graphics precessing system. US Patent 2006/0221087 A1, October 2006.
• 3: IBM. Cell Broadband Engine Architecture, October 2006. version 1.01.
• 4: Y.-J. Kim and B.-K. Kim. Load balancing algorithm for parallel vision processing for real-time navigation. In Proceedings of the 2000 IEEE/RSI International Conference on Intelligent Robots and Systems, 2000.
• 5: J. M. Squyres, A. Lumsdaine, and R. L. Stevenson. A toolkit for parallel image processing. In Parallel and Distributed Methods for Image Processing II, volume 3452 of Proc. SPIE, San Diego, USA, July 1998.
• 6: E. W. Weisstein. Mandelbrot set. From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/MandelbrotSet.html.
• 7: G. Wright, A. El-Mahdy, and I. Watson. Dynamic java threads on the JAMAICA single-chip multiprocessor. In V. Narayanan and M. I. Wolczko, editors, Java Microarchitectures, number 1-4020-7034-9, pages 207--229. Kluwer Academic Publishers, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.9 Applications

General Terms:
Algorithms, Performance

Keywords:
cell BE, curve fitting, fractals, load balancing, parallel computing, statistical sampling