Article

Free access

Definition and solution of the memory packing problem for field-programmable systems

Authors:

David Karchmer,

Jonathan RoseAuthors Info & Claims

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Pages 20 - 26

Published: 06 November 1994 Publication History

PDF eReader

Abstract

This paper defines a new optimization problem that arises in the use of a Field-Programmable System (FPS). An FPS consists of a set of Field-Programmable Gate Arrays and memories, and is used both for emulation of ASICs and computation. In both cases the application circuits will include a set of memories which may not match the number and aspect ratio of the physical memories available on the FPS. This can often require that the physical memories be time-multiplexed to implement the required memories, in a circuit we call a memory organizer.

We give a precise definition of the packing optimization problem and present an algorithm for its solution. The algorithm has been implemented in a CAD tool that automatically produces a memory organizer circuit ready for synthesis by a commercial FPGA tool set.

References

[1]

J. Arnold, D. Buell, and E. Davis, "Splash 2," in ~lh. Annual A CM Symposium on Parallel Algorithms and Architectures, pp. 316-322, 1992.

Digital Library

Google Scholar

[2]

P. Bertin, D. Roncin, and J. Vuillemin, "Programmable Active Memories: A Performance Assessment," in Research on Integrated Systems: Proceedings of the 1993 Symposium, MIT Press, 1993.

Digital Library

Google Scholar

[3]

S. Walters, "Computer-aided prototyping for ASIC-Based systems," IEEE Design and Test of Computers, pp. 4-10, June 1991.

Digital Library

Google Scholar

[4]

R. Tessier, J. Babb, M. Dahl, S. Hanono, and A. Agarwal, "The virtual wires emulation system: A gate-efficient asic prototyping environment," in FPGA 9~, February 1994.

Google Scholar

[5]

D. Galloway, D. Karchmer, P. Chow, D. Lewis, and J. Rose, "The Transmogrifier: The University of Toronto Field-Programmable System," Tech. Rep. 306, CSRI, University of Toronto, 1994.

Google Scholar

[6]

D. Karchmer, "A Field-Programmable System with Reconfigurable Memory," Master's thesis, University of Toronto, June 1994.

Google Scholar

[7]

Xilinx Inc., San Jose, CA, XACT Development System, October 1992.

Google Scholar

[8]

Aptix Corporation, San Jose, CA, Aptix System Data Book, November 1993.

Google Scholar

[9]

T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout. John Wiley L; Sons, 1990.

Digital Library

Google Scholar

[10]

M. Garey and R. Graham, "Worst-case analysis of memory allocation algorithms," in 4th. Annual ACM Symposium on Theory of Computing, 1972.

Digital Library

Google Scholar

Cited By

View all

Vasiljevic JChow PBetz VConstantinides G(2014)MPackProceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays10.1145/2554688.2554761(233-236)Online publication date: 26-Feb-2014
https://dl.acm.org/doi/10.1145/2554688.2554761
Ditmar JMcKeever SWilson A(2008)Area optimisation for field-programmable gate arrays in SystemC hardware compilationInternational Journal of Reconfigurable Computing10.1155/2008/6743402008(1-14)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1155/2008/674340
Hsu TWang TFix L(2008)A generalized network flow based algorithm for power-aware FPGA memory mappingProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391479(30-33)Online publication date: 8-Jun-2008
https://dl.acm.org/doi/10.1145/1391469.1391479
Show More Cited By

Index Terms

Definition and solution of the memory packing problem for field-programmable systems
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
      1. Datapath optimization
    2. Logic synthesis
      1. Circuit optimization

Recommendations

Reconfigurable Processing With Field Programmable Gate Arrays
ASAP '96: Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors

In-system-programmable, SRAM-based Field Programmable Gate Arrays (FPGAs) can be used to create processors and coprocessors whose internal architecture as well as interconnections can be reconfigured to match the needs of a given application. Exploiting ...
Field Programmable Gate Array (FPGA) and Their Applications
Field Programmable Compressor Trees: Acceleration of Multi-Input Addition on FPGAs

Multi-input addition occurs in a variety of arithmetically intensive signal processing applications. The DSP blocks embedded in high-performance FPGAs perform fixed bitwidth parallel multiplication and Multiply-ACcumulate (MAC) operations. In theory, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Upcoming Conference

ICCAD '24

Sponsor:
sigda

IEEE/ACM International Conference on Computer-Aided Design

October 27 - 31, 2024

New York , NY , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)13

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vasiljevic JChow PBetz VConstantinides G(2014)MPackProceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays10.1145/2554688.2554761(233-236)Online publication date: 26-Feb-2014
https://dl.acm.org/doi/10.1145/2554688.2554761
Ditmar JMcKeever SWilson A(2008)Area optimisation for field-programmable gate arrays in SystemC hardware compilationInternational Journal of Reconfigurable Computing10.1155/2008/6743402008(1-14)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1155/2008/674340
Hsu TWang TFix L(2008)A generalized network flow based algorithm for power-aware FPGA memory mappingProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391479(30-33)Online publication date: 8-Jun-2008
https://dl.acm.org/doi/10.1145/1391469.1391479
Ouaiss IVemuri R(2001)Hierarchical memory mapping during synthesis in FPGA-based reconfigurable computersProceedings of the conference on Design, automation and test in Europe10.5555/367072.367841(650-657)Online publication date: 13-Mar-2001
https://dl.acm.org/doi/10.5555/367072.367841
Jha PDutt N(2000)High-level library mapping for memoriesACM Transactions on Design Automation of Electronic Systems10.1145/348019.3482975:3(566-603)Online publication date: 1-Jul-2000
https://dl.acm.org/doi/10.1145/348019.348297
Panda PWhite JSentovich E(1999)Memory bank customization and assignment in behavioral synthesisProceedings of the 1999 IEEE/ACM international conference on Computer-aided design10.5555/339492.340063(477-481)Online publication date: 7-Nov-1999
https://dl.acm.org/doi/10.5555/339492.340063
Jha PDutt N(1997)Library Mapping for MemoriesProceedings of the 1997 European conference on Design and Test10.5555/787260.787680Online publication date: 17-Mar-1997
https://dl.acm.org/doi/10.5555/787260.787680
Panda PDutt NNicolau AOtten RYasuura H(1997)Exploiting off-chip memory access modes in high-level synthesisProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266503(333-340)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266503
Panda PDutt NNicolau AVahid FCatthoor F(1997)Architectural exploration and optimization of local memory in embedded systemsProceedings of the 10th international symposium on System synthesis10.5555/261693.261720(90-97)Online publication date: 17-Sep-1997
https://dl.acm.org/doi/10.5555/261693.261720
Schmit HThomas DRudell R(1995)Address generation for memories containing multiple arraysProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225102(510-514)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225102
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Reconfigurable Processing With Field Programmable Gate Arrays

Field Programmable Gate Array (FPGA) and Their Applications

Field Programmable Compressor Trees: Acceleration of Multi-Input Addition on FPGAs