Systematic methods for designing stride permutation interconnections
Järvinen, T. (2004)
Tampere University of Technology
2004
Tietotekniikan osasto - Department of Information Technology
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-200810021052
https://urn.fi/URN:NBN:fi:tty-200810021052
Tiivistelmä
This Thesis considers systematic methods for designing stride permutation interconnections, which are common in several digital signal processing algorithms. Managing such interconnections becomes important especially in parallel hardware implementations, which is the principal design problem considered in this Thesis.
In the first proposed method, the stride permutations are represented with permutation matrices, which are decomposed into smaller, more efficiently implementable matrices. The derived decompositions can be directly mapped onto networks consisting of multiplexers, registers and interconnection wirings. In order to estimate the complexity, the lower bound of the number of registers in stride permutations is derived, which is shown to be equal to the number of registers in the proposed networks. In addition, the multiplexing complexity is shown to be reduced compared to other existing approaches.
The second developed method is based on parallel memories which are in-place updated for the minimization of memory usage. This, unfortunately, complicates the control generation and interconnections. To overcome these drawbacks, two different approaches are developed resulting in a simplified control generator and switching network, respectively. Moreover, it is shown that resulting memory-based networks can be easily modified for the run-time configuration of sequence sizes and strides.
The systematic methods for designing stride permutation interconnections presented in this Thesis are shown to be competent compared to other existing approaches that are often design specific. The proposed methods are applicable to various designs since the sequence length, stride, and parallelism of computation are given as parameters having any power-of-two values. In addition, the methods are well suitable for automatic design generation.
In the first proposed method, the stride permutations are represented with permutation matrices, which are decomposed into smaller, more efficiently implementable matrices. The derived decompositions can be directly mapped onto networks consisting of multiplexers, registers and interconnection wirings. In order to estimate the complexity, the lower bound of the number of registers in stride permutations is derived, which is shown to be equal to the number of registers in the proposed networks. In addition, the multiplexing complexity is shown to be reduced compared to other existing approaches.
The second developed method is based on parallel memories which are in-place updated for the minimization of memory usage. This, unfortunately, complicates the control generation and interconnections. To overcome these drawbacks, two different approaches are developed resulting in a simplified control generator and switching network, respectively. Moreover, it is shown that resulting memory-based networks can be easily modified for the run-time configuration of sequence sizes and strides.
The systematic methods for designing stride permutation interconnections presented in this Thesis are shown to be competent compared to other existing approaches that are often design specific. The proposed methods are applicable to various designs since the sequence length, stride, and parallelism of computation are given as parameters having any power-of-two values. In addition, the methods are well suitable for automatic design generation.
Kokoelmat
- Väitöskirjat [4905]