Improving the performance of an algorithm by using multiple single dimensional memory structures for index mapping

Abstract

Execution time of an algorithm is a critical factor in process optimization. Index mapping is a technique that is used to improve the efficiency of an algorithm by improving the arithmetic efficiency of the algorithm. Usually, multi-dimensional or single dimensional memory structures are used for implementing index mapping. We found that the usage of multi-dimensional or single dimensional memory structures for implementing the index mapping did not always improve the resultant efficiency of an algorithm. Furthermore, we observed that the usage of multi-dimensional or single dimensional memory structures lead to cause reduction of the performance of an algorithm. As a solution for this problem, we used multiple single dimensional memory structures with equal length for implementing the index mapping. We evaluated the proposed technique with an algorithm that is used to create bit reversal permutation, which is considered as a critical sub process of Fast Fourier Transformation process. Two, four, eight, and sixteen multiple array and vector implementations of the algorithm reported 44% - 21% and 28% - 16% less clocks per element (CPE) in relation to the relevant multi-dimensional version, respectively. Also, two, four, eight, and sixteen multiple array and vector implementations of the algorithm reported 4% - 48% and 3% - 61% less CPE in relation to the relevant single dimensional version, respectively.