Flexible allocation method in polytope model for designing of efficient methods of recursive two-dimensional image processing using gpu
A.V. Nikonorov, V.A. Fursov, P.Yu. Yakimov

Full text of article: Russian language.

This paper considers a GPU implementation of a two-dimensional infinite impulse-response filter. We propose the decomposition of an IIR filter into the form which is applicable in the polytope model. The presented flexible allocation approach makes it possible to efficiently implement the polytope model in a single GPU kernel. Some theoretical performance estimations of the proposed flexible allocation algorithm are given in the paper.

Key words:
image processing, polytope model, GPU, fixed allocation, flexible allocation, CUDA, 2-D IIR Filters.


  1. Soifer, V. Computer Image Processing, Part II: Methods and algorithms / V. Soifer. – VDM Verlag, 2009. – 584 p.
  2. Fursov, V. Stable IIR Filters Identification based on the Genetic Algorithms / V. Fursov, A. Nikonorov, P. Yakimov. ? 8th Open German-Russian Workshop “Pattern recognition and image understanding”, workshop proceedings, November 21-26, 2011. – P. 71-74
  3. Lengauer, C. Loop Parallelization in the Polytope Model / C. Lengauer. ? Proceedings of the 4th International Conference on Concurrency Theory, 1993. ? P. 398-416.
  4. Rajopadhye, S. Synthesizing systolic arrays from recurrence equations / S. Rajopadhye, R.M. Fujimoto // Parallel Computing, 14(2), June 1990. ? P. 163-189
  5. Baghdadi, S. Putting Automatic Polyhedral Compilation for GPGPU to Work / S. Baghdadi, A. Groblinger, A. Cohen. ? Proceedings of the 15th Workshop on Compilers for Parallel Computers, 2010.
  6. McCool, M. Structured Parallel Programming with Deterministic Patterns / M. McCool. ? HotPar’10, 2nd USENIX Workshop on Hot Topics in Parallelism, Berkeley, CA, June 2010. ? P. 14-15.
  7. Lamport, L. The parallel execution of DO loops / L. Lamport // ACM Communication. – 1974. – Vol. 17, issue 2. ? P. 83-93.
  8. NVIDIA, NVIDIA CUDA C Best Practices Guide // Santa Clara, 2012. – 75 p.
  9. DudgeonD.E. Multidimensional digital signal processing / D.E. Dudgeon, R.M. Mersereau. – Prentice-Hall, Inc., Englewood Cliffs, 1984. – 400 p.
    © 2009, IPSI RAS
    Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846 2) 332-56-22, Fax: +7 (846 2) 332-56-20