research-article

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

Authors:

Alexander Fell,

Mythri Alle,

Keshavan Varadarajan,

Ranjani NarayanAuthors Info & Claims

CASES '09: Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems

Pages 127 - 136

https://doi.org/10.1145/1629395.1629414

Published: 11 October 2009 Publication History

Get Access

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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[5]

William J. Dally. Virtual-Channel Flow Control. IEEE Transactions on Parallel and Distributed Systems, 3(2):194--205, 1992.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

Cited By

View all

Mahadurkar MMerchant FMaity AVatwani KMunje IGopalan NNandy SNarayan R(2014)Co-exploration of NLA kernels and specification of Compute Elements in distributed memory CGRAs2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV)10.1109/SAMOS.2014.6893215(225-232)Online publication date: Jul-2014
https://doi.org/10.1109/SAMOS.2014.6893215
Madhu KDas SC MS NNandy SNarayan R(2014)Synthesis of Instruction Extensions on HyperCell, a reconfigurable datapath2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV)10.1109/SAMOS.2014.6893214(215-224)Online publication date: Jul-2014
https://doi.org/10.1109/SAMOS.2014.6893214
Krishnamoorthy RVaradarajan KGarga GAlle MNandy SNarayan RFujita MKathail VTatge RBarua R(2010)Towards minimizing execution delays on dynamically reconfigurable processorsProceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1878921.1878935(77-86)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878921.1878935
Show More Cited By

Index Terms

Streaming FFT on REDEFINE-v2: an application-architecture design space exploration
1. Computer systems organization
  1. Architectures
    1. Other architectures

Recommendations

REDEFINE: Runtime reconfigurable polymorphic ASIC

Emerging embedded applications are based on evolving standards (e.g., MPEG2/4, H.264/265, IEEE802.11a/b/g/n). Since most of these applications run on handheld devices, there is an increasing need for a single chip solution that can dynamically ...
A dynamically reconfigurable communication architecture for multicore embedded systems

To deal with the communication bottleneck of multiprocessor systems, several communication architectures have been proposed in the last decade. Yet, none of them has demonstrated the performance of the direct connections between two communicating units. ...
Executing large algorithms on low-capacity FPGAs using flowpath partitioning and runtime reconfiguration

This paper describes a new method of executing a software program on an FPGA for embedded systems. Rather than combine reconfigurable logic with a microprocessor core, this method uses a new technique to compile Java programs directly to special-purpose ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CASES '09: Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems

October 2009

298 pages

ISBN:9781605586267

DOI:10.1145/1629395

Program Chairs:
Joerg Henkel
Karlsruhe University (TH), Germany
,
Sri Parameswaran
University of New South Wales, Australia

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWeek '09

Sponsor:

ESWeek '09: Fifth Embedded Systems Week

October 11 - 16, 2009

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
236
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mahadurkar MMerchant FMaity AVatwani KMunje IGopalan NNandy SNarayan R(2014)Co-exploration of NLA kernels and specification of Compute Elements in distributed memory CGRAs2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV)10.1109/SAMOS.2014.6893215(225-232)Online publication date: Jul-2014
https://doi.org/10.1109/SAMOS.2014.6893215
Madhu KDas SC MS NNandy SNarayan R(2014)Synthesis of Instruction Extensions on HyperCell, a reconfigurable datapath2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV)10.1109/SAMOS.2014.6893214(215-224)Online publication date: Jul-2014
https://doi.org/10.1109/SAMOS.2014.6893214
Krishnamoorthy RVaradarajan KGarga GAlle MNandy SNarayan RFujita MKathail VTatge RBarua R(2010)Towards minimizing execution delays on dynamically reconfigurable processorsProceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1878921.1878935(77-86)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878921.1878935
Biswas PUdupa PMondal RVaradarajan KAlle MNandy SNarayan R(2010)Accelerating Numerical Linear Algebra Kernels on a Scalable Run Time Reconfigurable PlatformProceedings of the 2010 IEEE Annual Symposium on VLSI10.1109/ISVLSI.2010.65(161-166)Online publication date: 5-Jul-2010
https://dl.acm.org/doi/10.1109/ISVLSI.2010.65
Biswas PVaradarajan KAlle MNandy SNarayan R(2010)Design space exploration of systolic realization of QR factorization on a runtime reconfigurable platform2010 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation10.1109/ICSAMOS.2010.5642058(265-272)Online publication date: Jul-2010
https://doi.org/10.1109/ICSAMOS.2010.5642058

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

REDEFINE: Runtime reconfigurable polymorphic ASIC

A dynamically reconfigurable communication architecture for multicore embedded systems

Executing large algorithms on low-capacity FPGAs using flowpath partitioning and runtime reconfiguration