Permuting streaming data using RAMs

ABSTRACT

This article presents a method for constructing hardware structures that perform a fixed permutation on streaming data. The method applies to permutations that can be represented as linear mappings on the bit-level representation of the data locations. This subclass includes many important permutations such as stride permutations (corner turn, perfect shuffle, etc.), the bit reversal, the Hadamard reordering, and the Gray code reordering.

The datapath for performing the streaming permutation consists of several independent banks of memory and two interconnection networks. These structures are built for a given streaming width (i.e., number of inputs and outputs per cycle) and operate at full throughput for this streaming width.

We provide an algorithm that completely specifies the datapath and control logic given the desired permutation and streaming width. Further, we provide lower bounds on the achievable cost of a solution and show that for an important subclass of permutations our solution is optimal.

We apply our algorithm to derive datapaths for several important permutations, including a detailed example that carefully illustrates each aspect of the design process. Lastly, we compare our permutation structures to those of Järvinen et al. [2004], which are specialized for stride permutations.

REFERENCES

• 1: Astola, J., and Akopian, D. 1999. Architecure-oriented regular algorithms for discrete sine and cosine transforms. IEEE Trans. Sig. Proc. 47, 4, 1109--1124.
• 2: Beauchamp, K. G. 1984. Applications of Walsh and Related Functions. Academic Press, Orlando, FL.
• 3: Benes, V. E. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, Orlando, FL.
• 4: Bernstein, D. S. 2005. Matrix Mathematics. Princeton University Press, Princeton, NJ.
• 5: G. Bilardi, Merging and Sorting Networks with the Topology of the Omega Network, IEEE Transactions on Computers, v.38 n.10, p.1396-1403, October 1989 [doi>10.1109/12.35835]
• 6: Bürgisser, P., Clausen, M., and Shokrollahi, M. A. 1997. Algebraic Complexity Theory. Springer-Verlag, Berlin, Germany.
• 7: Duhamel, P. 1990. A connection between bit reversal and matrix transposition: Hardware and software consequences. IEEE Trans. Acous., Speech, Signal Proc. 38, 11, 1893--1418.
• 8: Gorman, S. F., and Wills, J. M. 1995. Partial column FFT pipelines. IEEE Trans. Circ. Syst. II: Analog Digital Signal Proc. 42, 6, 414--423.
• 9: Tuomas Jarvinen , Perttu Salmela , Harri Sorokin , Jarmo Takala, Stride Permutation Networks for Array Processors, Proceedings of the Application-Specific Systems, Architectures and Processors, 15th IEEE International Conference, p.376-386, September 27-29, 2004 [doi>10.1109/ASAP.2004.37]
• 10: T. Lang, Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network, IEEE Transactions on Computers, v.25 n.5, p.496-503, May 1976 [doi>10.1109/TC.1976.1674637]
• 11: D. H. Lawrie, Access and Alignment of Data in an Array Processor, IEEE Transactions on Computers, v.24 n.12, p.1145-1155, December 1975 [doi>10.1109/T-C.1975.224157]
• 12: Kyungsook Yoon Lee, On the Rearrangeability of 2(Iog2N) -1 Stage Permutation Networks, IEEE Transactions on Computers, v.34 n.5, p.412-425, May 1985 [doi>10.1109/TC.1985.1676581]
• 13: Peter A. Milder , Franz Franchetti , James C. Hoe , Markus Püschel, Formal datapath representation and manipulation for implementing DSP transforms, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391572]
• 14: Milder, P. A., Hoe, J. C., and Püschel, M. 2009. Automatic generation of streaming datapaths for arbitrary fixed permutations. In Proceedings of Design, Automation and Test in Europe.
• 15: Grace Nordin , Peter A. Milder , James C. Hoe , Markus Püschel, Automatic generation of customized discrete fourier transform IPs, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065703]
• 16: Parhi, K. K. 1992. Systematic synthesis of DSP data format converters using life-time analysis and forward-backward register allocation. IEEE Trans. Circ. Syst. II: Analog Digital Signal Proc. 39, 7, 423--440.
• 17: D. S. , Jr. Parker, Notes on Shuffle/Exchange-Type Switching Networks, IEEE Transactions on Computers, v.29 n.3, p.213-222, March 1980 [doi>10.1109/TC.1980.1675553]
• 18: M. C. , III Pease, The Indirect Binary n-Cube Microprocessor Array, IEEE Transactions on Computers, v.26 n.5, p.458-473, May 1977 [doi>10.1109/TC.1977.1674863]
• 19: Püschel, M., and Moura, J. M. F. 2008. Algebraic signal processing theory: Cooley-Tukey type algorithms for DCTs and DSTs. IEEE Trans. Signal Proc. 56, 4, 1502--1521.
• 20: Takala, J. H., Järvinen, T. S., and Sorokin, H. T. 2003. Conflict-free parallel memory access scheme for FFT processors. In Proceedings of the 2003 International Symposium on Circuits and Systems.
• 21: Charles Van Loan, Computational frameworks for the fast Fourier transform, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 22: Viterbi, A. J. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13, 2, 260--269.
• 23: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Permutation, RAM, connection network, data reordering, linear bit mapping, matrix transposition, streaming datapath, stride permutation, switch