Fast module mapping and placement for datapaths in FPGAs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast module mapping and placement for datapaths in FPGAs

Full text

Pdf (1.26 MB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays table of contents

Monterey, California, United States

Pages: 123 - 132

Year of Publication: 1998

ISBN:0-89791-978-5

Authors

Timothy J. Callahan	University of California at Berkeley
Philip Chong	University of California at Berkeley
André DeHon	University of California at Berkeley
John Wawrzynek	University of California at Berkeley

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 35, Citation Count: 19

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/275107.275132 What is a DOI?

ABSTRACT

By tailoring a compiler tree-parsing tool for datapath module mapping, we produce good quality results for datapath synthesis in very fast run time. Rather than flattening the design to gates, we preserve the datapath structure; this allows exploitation of specialized datapath features in FPGAs, retains regularity, and also results in a smaller problem size. To further achive high mapping speed, we formulate the problem as tree covering and solve it efficiently with a linear-time dynamic programming algorithm. In a novel extension to the tree-covering algorithm, we perform module placement simultaneously with the mapping, still in linear time. Integrating placement has the potential to increase the quality of the result since we can optimize total delay including routing delays. To our knowledge this is the first effort to leverage a grammar-based tree covering tool for datapath module mapping. Further, it is the first work to integrate simultaneous placement with module mapping in a way that preserves linear time complexity.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Mahadevan Ganapathi, Efficient tree pattern matching (extended abstract): an aid to code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.334-340, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318663]
	2	A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
	3	Saman P. Amarasinghe , Jennifer M. Anderson , Christopher S. Wilson , Shih-Wei Liao , Brian R. Murphy , Robert S. French , Monica S. Lam , Mary W. Hall, Multiprocessors from a Software Perspective, IEEE Micro, v.16 n.3, p.52-61, June 1996 [doi>10.1109/40.502406 ]
	4	K. Chaudhary , M. Pedram, A near optimal algorithm for technology mapping minimizing area under delay constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.492-498, June 08-12, 1992, Anaheim, California, United States
	5	DEHON, A. DPGA-Coupled Microprocessors: Commodity ICs for the Early 21st Century. In Proceedings IEEE Workshop on FPGAs for Custom Computing Machines (Cat. No. 94TH0611-4) (1994), IEEE Comput. Soc. Press, pp. 31-9. AN4754544.
	6	FRANCIS, R. Technology Mappingfi~r lamkup.Table Based Field- Programmable Gate Arrays. PhD thesis, University of Toronto, 1992.
	7	Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	8	J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
	9	K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
	10	Andreas Koch, Module compaction in FPGA-based regular datapaths, Proceedings of the 33rd annual conference on Design automation, p.471-476, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240608]
	11	Andreas Koch, Structured design implementation: a strategy for implementing regular datapaths on FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.151-157, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228392]
	12	LOU, J., SALEK, A. H., AND PEDRAM, M. AnExact Solution to Simultaneous Technology Mapping and Linear Placement Problem for Trees. In Prec. International Workshop on Logic Synthesis (May 1997), pp. 1--4.
	13	A. R. Naseer , M. Balakrishnan , Anshul Kumar, An Efficient Technique for Mapping RTL Structures onto FPGAs, Proceedings of the 4th International Workshop on Field-Programmable Logic and Applications: Field-Programmable Logic, Architectures, Synthesis and Applications, p.99-110, September 07-09, 1994
	14	NATIONAL SEMICONDUCTOR CORPORATION. NAPAi000 Data Sheet, 1996.
	15	TJiANG, S. Twig Reference Manual. Comp. Sci. Tech. Rep. 120, AT&T Bell Laboratories, January 1986.
	16	XILINX. The Programmable Logic Data Book. 1994.

CITED BY 19

	Hamid R. Ahmadifar , Farhad Mehdipour , Morteza S. Zamani , Mehdi Sedighi , Kazuaki Murakami, An incremental temporal partitioning method for real-time reconfigurable systems, Proceedings of the 5th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications, p.88-93, February 15-17, 2006, Madrid, Spain
	Russell Tessier, Fast placement approaches for FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.2, p.284-305, April 2002
	Kia Bazargan , Seda Ogrenci , Majid Sarrafzadeh, Integrating scheduling and physical design into a coherent compilation cycle for reconfigurable computing architectures, Proceedings of the 38th conference on Design automation, p.635-640, June 2001, Las Vegas, Nevada, United States
	John M. Emmert , Dinesh Bhatia, A methodology for fast FPGA floorplanning, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.47-56, February 21-23, 1999, Monterey, California, United States
	Yaska Sankar , Jonathan Rose, Trading quality for compile time: ultra-fast placement for FPGAs, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.157-166, February 21-23, 1999, Monterey, California, United States
	Daler N. Rakhmatov , Sarma B. K. Vrudhula , Thomas J. Brown , Ajay Nagarandal, Adaptive Multiuser Online Reconfigurable Engine, IEEE Design & Test, v.17 n.1, p.53-67, January 2000
	Kiarash Bazargan , Ryan Kastner , Majid Sarrafzadeh, Fast Template Placement for Reconfigurable Computing Systems, IEEE Design & Test, v.17 n.1, p.68-83, January 2000
	R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002
	Yuanqing Guo , Gerard J.M. Smit , Hajo Broersma , Paul M. Heysters, A graph covering algorithm for a coarse grain reconfigurable system, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Chen Chang , John Wawrzynek , Robert W. Brodersen, BEE2: A High-End Reconfigurable Computing System, IEEE Design & Test, v.22 n.2, p.114-125, March 2005
	Mihai Budiu , Seth Copen Goldstein, Fast compilation for pipelined reconfigurable fabrics, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.195-205, February 21-23, 1999, Monterey, California, United States
	Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000
	John M. Emmert , Sandeep Lodha , Dinesh K. Bhatia, On Using Tabu Search for Design Automation of VLSI Systems, Journal of Heuristics, v.9 n.1, p.75-90, January 2003
	Fred Ma , John P. Knight , Calvin Plett, Physical resource binding for a Coarse-Grain reconfigurable array using evolutionary algorithms, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.5, p.553-563, May 2005
	Camel Tanougast , Yves Berviller , Serge Weber , Philippe Brunet, A partitioning methodology that optimises the area on reconfigurable real-time embedded systems, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.494-501, January 2003
	A. Dreweke , M. Worlein , I. Fischer , D. Schell , Th. Meinl , M. Philippsen, Graph-Based Procedural Abstraction, Proceedings of the International Symposium on Code Generation and Optimization, p.259-270, March 11-14, 2007
	Philip Brisk , Adam Kaplan , Ryan Kastner , Majid Sarrafzadeh, Instruction generation and regularity extraction for reconfigurable processors, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France
	Marlene Wan , Hui Zhang , Varghese George , Martin Benes , Arthur Abnous , Vandana Prabhu , Jan Rabaey, Design Methodology of a Low-Energy Reconfigurable Single-Chip DSP System, Journal of VLSI Signal Processing Systems, v.28 n.1-2, p.47-61, May-June 2001
	Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002