More Web Proxy on the site http://driver.im/

Article

Temporal floorplanning using the T-tree formulation

Authors:

Yao-Wen ChangAuthors Info & Claims

ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design

Pages 300 - 305

https://doi.org/10.1109/ICCAD.2004.1382590

Published: 07 November 2004 Publication History

Abstract

Improving logic capacity by time-sharing, dynamically reconfigurable FPGAs are employed to handle designs of high complexity and functionality. We model each task as a 3D-box and deal with the temporal floorplanning/placement problem for dynamically reconfigurable FPGA architectures. We present a tree-based data structure, called T-trees, to represent the spatial and temporal relations among tasks. Each node in a T-tree has at most three children which represent the dimensional relationship among tasks. For the T-tree, we develop an efficient packing method and derive the condition to ensure the satisfaction of precedence constraints which model the temporal ordering among tasks induced by the execution of dynamically reconfigurable FPGAs. Experimental results show that our tree-based formulation can achieve significantly better solution quality with less execution time than the most recent state-of-the-art work.

References

[1]

{1} C. Ababeii and K. Bazargan, "Non-Contiguous Linear Placement for Re-configurable Fabrics," Proc. RAW, Apr. 2004.

[2]

{2} S.N. Adya and I. L. Markov, "Fixed-Outline Floorplanning Through Better Local Search," Proc. ICCD, pp. 328-334, 2001.

Digital Library

[3]

{3} S.N. Adya and I. L. Markov, "Fixed-outlin Floorplanning: Enabling Hierarchical Design," IEEE Trans. on VLSI, vol. 11, no. 6, pp. 1120-1135, Dec. 2003.

Digital Library

[4]

{4} Atmel, "AT40K05102040AL_Complete," Atmel, Inc.

[5]

{5} K. Bazargan, R. Kastner, and M. Sarrafzadeh, "Fast Template Placement for Reconfigurable Computing Systems," IEEE Design & Test of Computers , vol. 17, no. 1, pp. 68-83, Mar. 2000.

Digital Library

[6]

{6} Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, "B^*-trees: A New Representation for Non-slicing Floocplan," Proc. DAC, pp. 458-462, June 2000.

Digital Library

[7]

{7} S. P. Fekete, E. Köhler, and J. Teich, "Optimal FPGA Module Placement with Temporal Precedence Constraints," Proc. DATE, pp. 658-665, Mar. 2001.

Digital Library

[8]

{8} P.-N. Guo, C.-K. Cheng, and T. Yoshimura, "An O-tree Representation of Non-slicing Floorplan and Its Application," Proc. DAC, pp. 268-273, June 1999.

Digital Library

[9]

{9} S. Hauck, "The Roles of FPGAs in Reprogrammable Systems," Proc. of the IEEE, vol. 86, no. 4, pp. 615-639, Apr. 1998.

[10]

{10} S. Hauck, Z. Li, and E.J. Schwabe, "Configuration Compression for the Xilinx XC6200 FPGA," Proc. FCCM, pp. 138-146, 1998.

Digital Library

[11]

{11} P. Hilton and J. Pederson, "Catalan Numbers, Their Generalization, and Their Uses," Math. Intelligencer 13, pp. 64-75, 1991.

[12]

{12} A. B. Kahng, "Classical Floorplanning Harmful?" Proc. of ACM/SIGDA ISPD, pp. 207-213, April 2000.

Digital Library

[13]

{13} S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671-680, May 1983.

[14]

{14} E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976.

[15]

{15} J. Teich, S. P. Fekete, and J. Schepers, "Compile-Time Optimization of Dynamic Hardware Reconfigurations," Proc PDPTA, pp. 1097-1103, June 1999.

Digital Library

[16]

{16} R. Tesser and W. Burleson, "Reconfigurable Computing for Digital Signal Processing: A Survey," Journal of VLSI Signal Processing, Vol. 28, no. 1, pp. 7-27, May/June 2001.

Digital Library

[17]

{17} Xilinx, "XAPP151 Virtex Series Configuration Architecture User Guide v1. 5," Xilinx, Inc., Sep. 2000.

[18]

{18} Xilinx "Virtex-II Pro Platform FPGA User Guide," Xilinx, Inc.

[19]

{19} P.-H. Yuh, C.-L. Yang, Y.-W. Chang, and H.-L. Chang, "Temporal Floorplanning using 3D-subTCG," Proc. ASP-DAC, pp. 725-730, Jan. 2004.

Digital Library

Cited By

Gupta RGill S(2024)A new representation in 3D VLSI floorplan: 3D O-TreeGenetic Programming and Evolvable Machines10.1007/s10710-024-09485-325:1Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10710-024-09485-3
Seyoum BBiondi AButtazzo G(2019)FLORAACM Transactions on Embedded Computing Systems10.1145/335820218:5s(1-20)Online publication date: 8-Oct-2019
https://dl.acm.org/doi/10.1145/3358202
Kang IQiao FPark DKane DYoung ECheng CGraham R(2018)Three-dimensional Floorplan Representations by Using Corner Links and Partial OrderACM Transactions on Design Automation of Electronic Systems10.1145/328917924:1(1-33)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3289179
Show More Cited By

Recommendations

Temporal floorplanning using 3D-subTCG
ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation Conference

Improving logic capacity by time-sharing, dynamically reconfigurable FPGAs are employed to handle designs of high complexity and functionality. In this paper, we use a novel topological floorplan representation, named 3D-subTCG (3-Dimensional sub-...
Temporal floorplanning using the three-dimensional transitive closure subGraph

Improving logic capacity by time-sharing, dynamically reconfigurable Field Gate Programmable Arrays (FPGAs) are employed to handle designs of high complexity and functionality. In this paper, we use a novel graph-based topological floorplan ...
Macro Block Based FPGA Floorplanning
VLSID '97: Proceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications

This paper describes the floorplanning for FPGA based designs. In order to perform placement for very large designs, the currently followed approach of placing flat netlists is extremely time consuming. Also, managing large data sets, as in flat netlist ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design

November 2004

913 pages

ISBN:0780387023

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 07 November 2004

Check for updates

Qualifiers

Article

Conference

ICCAD04

Sponsor:

SIGDA

ICCAD04: The International Conference on Computer-Aided Design 2004

November 7 - 11, 2004

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
153
Total Downloads

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

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gupta RGill S(2024)A new representation in 3D VLSI floorplan: 3D O-TreeGenetic Programming and Evolvable Machines10.1007/s10710-024-09485-325:1Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10710-024-09485-3
Seyoum BBiondi AButtazzo G(2019)FLORAACM Transactions on Embedded Computing Systems10.1145/335820218:5s(1-20)Online publication date: 8-Oct-2019
https://dl.acm.org/doi/10.1145/3358202
Kang IQiao FPark DKane DYoung ECheng CGraham R(2018)Three-dimensional Floorplan Representations by Using Corner Links and Partial OrderACM Transactions on Design Automation of Electronic Systems10.1145/328917924:1(1-33)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3289179
Fischbach RKnechtel JLienig JKoh CSze C(2013)Utilizing 2D and 3D rectilinear blocks for efficient IP reuse and floorplanning of 3D-integrated systemsProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451921(11-16)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451921
Srinivasan SKamakoti VBhattacharya A(2013)A Novel Algorithm for Fast Synthesis of DNA Probes on MicroarraysACM Journal on Emerging Technologies in Computing Systems10.1145/2422094.24220959:1(1-17)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1145/2422094.2422095
Vipin KFahmy S(2012)Architecture-Aware reconfiguration-centric floorplanning for partial reconfigurationProceedings of the 8th international conference on Reconfigurable Computing: architectures, tools and applications10.1007/978-3-642-28365-9_2(13-25)Online publication date: 19-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28365-9_2
Hsieh JChang YLee W(2011)An enhanced leakage-aware scheduler for dynamically reconfigurable FPGAsProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950944(661-667)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950944
Montone ASantambrogio MRedaelli FSciuto D(2011)Floorplacement for partial reconfigurable FPGA-based systemsInternational Journal of Reconfigurable Computing10.1155/2011/4836812011(1-12)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1155/2011/483681
Fischbach RLienig JKnechtel JAtienza DXie YAyala JStevens K(2011)Investigating modern layout representations for improved 3d design automationProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973076(337-342)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973076
Montone ASantambrogio MSciuto DMemik S(2010)Placement and Floorplanning in Dynamically Reconfigurable FPGAsACM Transactions on Reconfigurable Technology and Systems10.1145/1862648.18626543:4(1-34)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1145/1862648.1862654
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten