Parallel Algorithms for Multi-Indexed Recurrence Relations With Applications to DPCM Image Compression
Abdou S. Youssef
Parallel solution of 1-indexed recurrence relations has received much attention, but no effort has been made to design parallel algorithms for multi-indexed recurrence relations, where the recurrence is in more than one index. Multi-indexed relations arise in JPEG-standard DPCM compression of images, which is an increasingly important area due to the explosion of imagery applications such as multimedia and medical imaging. In this paper we design and analyze novel parallel algorithms for solving multi-indexed recurrence relations of arbitrary order. To that end, we develop three techniques: index sequencing, index decoupling, and dimension shifting. Index sequencing leads to a parallel algorithm of O(n log n) time on n processors, where the input size is n2. Index decoupling applies in limited situations, one of which is a commonly used special case of DPCM, and leads to a parallel algorithm of O(log n) time for n x n images on n x n processors. Dimension shifting is a universal technique for multi-indexed relations, and involves reducing the number of indices to 1 while clustering the terms of the relation into vectors. This is accomplished by means of special vector operators that we define and study. Our parallel algorithm for doing the dimension shifting and for solving the resulting 1-indexed recurrence relation takes O(log2 N) time on meshes of partitionable buses or hypercubes, where N is the data input-output size.
Parallel Algorithms for Multi-Indexed Recurrence Relations With Applications to DPCM Image Compression, - 6115, National Institute of Standards and Technology, Gaithersburg, MD
(Accessed February 22, 2024)