Streaming FFT on REDEFINE-v2: an application-architecture design space exploration

ABSTRACT

In this paper we explore an implementation of a high-throughput, streaming application on REDEFINE-v2, which is an enhancement of REDEFINE. REDEFINE is a polymorphic ASIC combining the flexibility of a programmable solution with the execution speed of an ASIC. In REDEFINE Compute Elements are arranged in an 8x8 grid connected via a Network on Chip (NoC) called RECONNECT, to realize the various macrofunctional blocks of an equivalent ASIC.

For a 1024-FFT we carry out an application-architecture design space exploration by examining the various characterizations of Compute Elements in terms of the size of the instruction store. We further study the impact by using application specific, vectorized FUs. By setting up different partitions of the FFT algorithm for persistent execution on REDEFINE-v2, we derive the benefits of setting up pipelined execution for higher performance. The impact of the REDEFINE-v2 micro-architecture for any arbitrary N-point FFT (N > 4096) FFT is also analyzed. We report the various algorithm-architecture tradeoffs in terms of area and execution speed with that of an ASIC implementation. In addition we compare the performance gain with respect to a GPP.

REFERENCES

• 1: Mythri Alle, Keshavan Varadarajan, , Alexander Fell, S. K. Nandy, and Ranjani Narayan. Compiling Techniques for Coarse Grained Runtime Reconfigurable Architectures. In ARC'09: Proceedings of the 5th IEEE International Workshop on Applied Reconfigurable Computing, July 2008.
• 2: Mythri Alle, Keshavan Varadarajan, Alexander Fell, Nimmy Joseph, C. Ramesh Reddy, Saptarsi Das, Prasenjit Biswas, Jugantor Chetia, S. K. Nandy, and Ranjani Narayan. REDEFINE: Runtime Reconfigurable Polymorphic ASIC. IEEE Transactions on Embedded Systems, Special Issue on Configuring Algorithms, Processes and Architecture, 2008.
• 3: Mythri Alle, Keshavan Varadarajan, Nimmy Joseph, C. Ramesh Reddy, Alexander Fell, S. K. Nandy, and Ranjani Narayan. Synthesis of Application Accelerators on Runtime Reconfigurable Hardware. In ASAP '08: Proceedings of the 19th IEEE International Conference on Application specific Systems, Architectures and Processors, July 2008.
• 4: James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of Computation, 19(90):297--301, 1965.
• 5: William J. Dally. Virtual-Channel Flow Control. IEEE Transactions on Parallel and Distributed Systems, 3(2):194--205, 1992.
• 6: Alexander Fell, Prasenjit Biswas, Jugantor Chetia, S. K. Nandy, and Ranjani Narayan. Generic Routing Rules and a Scalable Access Enhancement for the Network on Chip RECONNECT. In 22nd IEEE International SOC Conference, September 2009.
• 7: Yasuhiro Inagami and John F. Foley. The specification of a new Manchester Dataflow Machine. In ICS '89: Proceedings of the 3rd International Conference on Supercomputing, New York, NY, USA, 1989.
• 8: Nimmy Joseph, C. Ramesh Reddy, Keshavan Varadarajan, Mythri Alle, Alexander Fell, S. K. Nandy, and Ranjani Narayan. RECONNECT: A NoC for polymorphic ASICs using a Low Overhead Single Cycle Router. In ASAP '08: Proceedings of the 19th IEEE International Conference on Application specific Systems, Architectures and Processors, July 2008.
• 9: Amar Nath Satrawala, Keshavan Varadarajan, Mythri Alle, S. K. Nandy, and Ranjani Narayan. REDEFINE: Architecture of a SOC Fabric for Runtime Composition of Computation Structures. In FPL '07: Proceedings of the International Conference on Field Programmable Logic and Applications, August 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

General Terms:
Design

Keywords:
NOC, application synthesis, custom instruction extension, dataflow software pipeline, honeycomb, polymorphic asic, router, runtime reconfiguration