REAL: a program for REgister ALlocation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

REAL: a program for REgister ALlocation

Full text

Pdf (467 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 24th ACM/IEEE Design Automation Conference table of contents

Miami Beach, Florida, United States

Pages: 210 - 215

Year of Publication: 1987

ISBN:0-8186-0781-5

Authors

F. J. Kurdahi	Department of Electrical Engineering-Systems, University of Southern California, Los Angeles, CA
A. C. Parker	Department of Electrical Engineering-Systems, University of Southern California, Los Angeles, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 31, Citation Count: 70

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/37888.37920 What is a DOI?

ABSTRACT

This paper describes the REAL REgister ALlocation program. REAL uses a track assignment algorithm taken from channel routing called the Left Edge algorithm. REAL is optimal for non-pipelined designs with no conditional branches. It is thought that REAL is also optimal for designs with conditional branches, pipelined or not. Experimental results are included in the report, which illustrate the optimal solutions found by REAL. REAL is part of the ADAM Advanced Design AutoMation system, and will be used to process designs output from MAHA and Sehwa.

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 , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	2	E. Girczyc and j. Knight. An Ada to Standard Cell Hardware Compiler Based on Graph Grammars and Scheduling. In Proceedings, 1984 International Con- {erence on Computer Design - IGCD, pages 726-729, October 1984.
	3	Louis J. Hafer , Alice C. Parker, Register-transfer level digital design automation: The allocation process, Proceedings of the 15th conference on Design automation, p.213-219, June 19-21, 1978, Las Vegas, Nevada, United States
	4	Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
	5	N. Park and A. C. Parker. Synthesis of Optimal Pipeline Clocking Schemes. Technical Report DISC/85-1, Dept. of EE-Systems, University of Southern California, January 1985.
	6	Nohbyung Park , Alice Parker, Sehwa: a program for synthesis of pipelines, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.454-460, July 1986, Las Vegas, Nevada, United States
	7	Alice C. Parker , Jorge T. Pizarro , Mitch Mlinar, MAHA: a program for datapath synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.461-466, July 1986, Las Vegas, Nevada, United States
	8	C.-J. Tseng and D.P. Siewiorek. Automated Synthesis of Data Paths in Digital Systems. {EEE Trans, on CAD, CAD-5(3):379-395, July 1986.

CITED BY 70

	Elof Frank , Thomas Lengauer, APPlaUSE: A&barbelow;rea and p&barbelow;erformance optimization in a u&barbelow;nified placement and s&barbelow;ynthesis e&barbelow;nvironment, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.662-667, November 05-09, 1995, San Jose, California, United States
	Tom Wilson , Gary Grewal , Ben Halley , Dilip Banerji, An integrated approach to retargetable code generation, Proceedings of the 7th international symposium on High-level synthesis, p.70-75, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
	Smita Bakshi , Daniel D. Gajski, A memory selection algorithm for high-performance pipelines, Proceedings of the conference on European design automation, p.124-129, September 18-22, 1995, Brighton, England
	Valentin Mureşan , Xiaojun Wang , Valentina Mureşan , Mircea Vlăduţiu, Greedy Tree Growing Heuristics on Block-Test Scheduling Under Power Constraints, Journal of Electronic Testing: Theory and Applications, v.20 n.1, p.61-78, February 2004
	Per Gunnar Kjeldsberg , Francky Catthoor , Einar J. Aas, Storage requirement estimation for data intensive applications with partially fixed execution ordering, Proceedings of the eighth international workshop on Hardware/software codesign, p.56-60, May 2000, San Diego, California, United States
	David J. Kolson , Alexandru Nicolau , Nikil Dutt , Ken Kennedy, Optimal register assignment to loops for embedded code generation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.251-279, April 1996
	Florin Balasa , Francky Catthoor , Hugo de Man, Exact evaluation of memory size for multi-dimensional signal processing systems, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.669-672, November 07-11, 1993, Santa Clara, California, United States
	Wei-Kai Cheng , Youn-Long Lin, Code generation of nested loops for DSP processors with heterogeneous registers and structural pipelining, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.231-256, July 1999
	Juanjo Noguera , Rosa M. Badia, HW/SW codesign techniques for dynamically reconfigurable architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.4, p.399-415, August 2002
	Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
	Nam-Sung Woo, A global, dynamic register allocation and binding for a data path synthesis system, Proceedings of the 27th ACM/IEEE conference on Design automation, p.505-510, June 24-27, 1990, Orlando, Florida, United States
	David J. Kolson , Alexandru Nicolau , Nikil Dutt , Ken Kennedy, Optimal register assignment to loops for embedded code generation, Proceedings of the 8th international symposium on System synthesis, p.42-47, September 13-15, 1995, Cannes, France
	M. Rim , R. Jain , R. De Leone, Optimal allocation and binding in high-level synthesis, Proceedings of the 29th ACM/IEEE conference on Design automation, p.120-123, June 08-12, 1992, Anaheim, California, United States
	Reinaldo A. Bergamaschi , Raul Camposano , Michael Payer, Data-path synthesis using path analysis, Proceedings of the 28th conference on ACM/IEEE design automation, p.591-596, June 17-22, 1991, San Francisco, California, United States
	M. Nourani , C. Papachristou, Move frame scheduling and mixed scheduling-allocation for the automated synthesis of digital systems, Proceedings of the 29th ACM/IEEE conference on Design automation, p.99-105, June 08-12, 1992, Anaheim, California, United States
	Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States
	Chu-Yi Huang , Yen-Shen Chen , Youn-Long Lin , Yu-Chin Hsu, Data path allocation based on bipartite weighted matching, Proceedings of the 27th ACM/IEEE conference on Design automation, p.499-504, June 24-27, 1990, Orlando, Florida, United States
	Alok Sharma , Rajiv Jain, InSyn: integrated scheduling for DSP applications, Proceedings of the 30th international conference on Design automation, p.349-354, June 14-18, 1993, Dallas, Texas, United States
	Kyumyung Choi , Steven P. Levitan, A flexible datapath allocation method for architectural synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.4, p.376-404, Oct. 1999
	Darko Kirovski , Miodrag Potkonjak, Engineering change: methodology and applications to behavioral and system synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.604-609, June 21-25, 1999, New Orleans, Louisiana, United States
	Ying Zhao , Sharad Malik, Exact memory size estimation for array computations without loop unrolling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.811-816, June 21-25, 1999, New Orleans, Louisiana, United States
	Youn-Long Lin, Recent developments in high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.1, p.2-21, Jan. 1997
	Ranga Vemuri , Srinivas Katkoori , Meenakshi Kaul , Jay Roy, An efficient register optimization algorithm for high-level synthesis from hierarchical behavioral specifications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.189-216, January 2002
	Douglas M. Grant , Peter B. Denyer, Memory, control and communications synthesis for scheduled algorithms, Proceedings of the 27th ACM/IEEE conference on Design automation, p.162-167, June 24-27, 1990, Orlando, Florida, United States
	Peter Grun , Florin Balasa , Nikil Dutt, Memory size estimation for multimedia applications, Proceedings of the 6th international workshop on Hardware/software codesign, p.145-149, March 15-18, 1998, Seattle, Washington, United States
	PerGunnar Kjeldsberg , Francky Catthoor , Einar J. Aas, Detection of partially simultaneously alive signals in storage requirement estimation for data intensive applications, Proceedings of the 38th conference on Design automation, p.365-370, June 2001, Las Vegas, Nevada, United States
	Peeter Ellervee , Miguel Miranda , Francky Catthoor , Ahmed Hemani, System-level data format exploration for dynamically allocated data structures, Proceedings of the 37th conference on Design automation, p.556-559, June 05-09, 2000, Los Angeles, California, United States
	P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001
	Steve C.-Y. Huang , Wayne H. Wolf, How datapath allocation affects controller delay, Proceedings of the 7th international symposium on High-level synthesis, p.158-163, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
	Clifford Liem , Trevor May , Pierre Paulin, Register assignment through resource classification for ASIP microcode generation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.397-402, November 06-10, 1994, San Jose, California, United States
	Tsung-Yi Wu , Youn-Long Lin, Register minimization beyond sharing among variables, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.164-169, June 12-16, 1995, San Francisco, California, United States
	D. Sreenivasa Rao , F. J. Kurdahi, Controller and datapath trade-offs in hierarchical RT-level synthesis, Proceedings of the 7th international symposium on High-level synthesis, p.152-157, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
	Raul Camposano, Behavioral synthesis, Proceedings of the 33rd annual conference on Design automation, p.33-34, June 03-07, 1996, Las Vegas, Nevada, United States
	J. Septién , D. Mozos , F. Tirado , R. Hermida , M. Fernández, Heuristics for branch-and-bound global allocation, Proceedings of the conference on European design automation, p.334-340, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	M. Pedram , J. Chang, Module assignment for low power, Proceedings of the conference on European design automation, p.376-381, September 1996, Geneva, Switzerland
	R. Anand , M. Jacome , G. de Veciana, Heuristic tradeoffs between latency and energy consumption in register assignment, Proceedings of the eighth international workshop on Hardware/software codesign, p.115-119, May 2000, San Diego, California, United States
	Miodrag Potkonjak , Sujit Dey , Kazutoshi Wakabayashi, Design-for-debugging of application specific designs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.295-301, November 05-09, 1995, San Jose, California, United States
	Taewhan Kim , C. L. Liu, Utilization of multiport memories in data path synthesis, Proceedings of the 30th international conference on Design automation, p.298-302, June 14-18, 1993, Dallas, Texas, United States
	J. Noguera , R. Badia, A HW/SW partitioning algorithm for dynamically reconfigurable architectures, Proceedings of the conference on Design, automation and test in Europe, p.729, March 2001, Munich, Germany
	P. G. Paulin , J. P. Knight, Scheduling and binding algorithms for high-level synthesis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.1-6, June 25-28, 1989, Las Vegas, Nevada, United States
	Vijay Raghavendra , Chidchanok Lursinsap, Automated micro-roll-back self-recovery synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.385-390, June 17-22, 1991, San Francisco, California, United States
	Nazanin Mansouri , Ranga Vemuri, Automated Correctness Condition Generation for Formal Verification ofSynthesized RTL Designs, Formal Methods in System Design, v.16 n.1, p.59-91, Jan 1,2000
	Per Gunnar Kjeldsberg , Francky Catthoor , Einar J. Aas, Automated data dependency size estimation with a partially fixed execution ordering, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	P. G. Kjeldsberg , F. Catthoor , E. J. Aas, Storage requirement estimation for optimized design of data intensive applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.2, p.133-158, April 2004
	Rami Beidas , Jianwen Zhu, Scalable interprocedural register allocation for high level synthesis, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Heinrich Krämer , Wolfgang Rosenstiel, System synthesis using behavioural descriptions, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	Hongwei Zhu , Ilie I. Luican , Florin Balasa, Memory size computation for multimedia processing applications, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Saeed Safari , Amir Hossein Jahangir , Hadi Esmaeilzadeh, A parameterized graph-based framework for high-level test synthesis, Integration, the VLSI Journal, v.39 n.4, p.363-381, July 2006
	Chaeryung Park , Taewhan Kim , C. L. Liu, Register Allocation—A Hierarchical Reduction Approach, Journal of VLSI Signal Processing Systems, v.19 n.3, p.269-285, Aug. 1998
	Taemin Kim , Xun Liu, Compatibility path based binding algorithm for interconnect reduction in high level synthesis, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Leipo Yan , Thambipillai Srikanthan , Niu Gang, Area and delay estimation for FPGA implementation of coarse-grained reconfigurable architectures, ACM SIGPLAN Notices, v.41 n.7, July 2006
	Yan Meng , Timothy Sherwood , Ryan Kastner, Leakage power reduction of embedded memories on FPGAs through location assignment, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	R. Leupers , K. Karuri , S. Kraemer , M. Pandey, A design flow for configurable embedded processors based on optimized instruction set extension synthesis, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Soheil Aminzadeh , Saeed Safari, Co-evolutionary high-level test synthesis, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	Shih-Hsu Huang , Chun-Hua Cheng , Yow-Tyng Nieh , Wei-Chieh Yu, Register binding for clock period minimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Q. Hu , A. Vandecappelle , P. G. Kjeldsberg , F. Catthoor , M. Palkovic, Fast memory footprint estimation based on maximal dependency vector calculation, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Philip Brisk , Ajay K. Verma , Paolo Ienne, Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Hyunok Oh , Soonhoi Ha, Memory-optimized software synthesis from dataflow program graphs with large size data samples, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.514-529, January 2003
	Florin Balasa , Hongwei Zhu , Ilie I. Luican, Computation of storage requirements for multi-dimensional signal processing applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.4, p.447-460, April 2007
	Nazanin Mansouri , Ranga Vemuri, Accounting for various register allocation schemes during post-synthesis verification of RTL designs, Proceedings of the conference on Design, automation and test in Europe, p.46-es, January 1999, Munich, Germany
	Shuqing Zhao , Daniel D. Gajski, Defining an Enhanced RTL Semantics, Proceedings of the conference on Design, Automation and Test in Europe, p.548-553, March 07-11, 2005
	F. Balasa , P. G. Kjeldsberg , A. Vandecappelle , M. Palkovic , Q. Hu , H. Zhu , F. Catthoor, Storage Estimation and Design Space Exploration Methodologies for the Memory Management of Signal Processing Applications, Journal of Signal Processing Systems, v.53 n.1-2, p.51-71, November 2008
	Per Gunnar Kjeldsberg , Francky Catthoor , Sven Verdoolaege , Martin Palkovic , Arnout Vandecappelle , Qubo Hu , Einar J. Aas, Guidance of Loop Ordering for Reduced Memory Usage in Signal Processing Applications, Journal of Signal Processing Systems, v.53 n.3, p.301-321, December 2008
	Ilie I. Luican , Hongwei Zhu , Florin Balasa, Computation of the minimum data storage and applications in memory management for multimedia signal processing, Integrated Computer-Aided Engineering, v.15 n.2, p.181-196, April 2008
	Eunjoo Choi , Changsik Shin , Taewhan Kim , Youngsoo Shin, Power-gating-aware high-level synthesis, Proceeding of the thirteenth international symposium on Low power electronics and design, August 11-13, 2008, Bangalore, India
	Keisuke Inoue , Mineo Kaneko , Tsuyoshi Iwagaki, Safe clocking for the setup and hold timing constraints in datapath synthesis, Proceedings of the 19th ACM Great Lakes symposium on VLSI, May 10-12, 2009, Boston Area, MA, USA
	Johan Ditmar , Steve McKeever , Alex Wilson, Area optimisation for field-programmable gate arrays in SystemC hardware compilation, International Journal of Reconfigurable Computing, v.2008 n.2, p.1-14, January 2008
	Feng Wang , Yuan Xie , Andres Takach, Variation-aware resource sharing and binding in behavioral synthesis, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Taemin Kim , Xun Liu, Better than optimum?: register reduction using idle pipelined functional units, Proceedings of the 19th ACM Great Lakes symposium on VLSI, May 10-12, 2009, Boston Area, MA, USA
	Keisuke Inoue , Mineo Kaneko , Tsuyoshi Iwagaki, Novel Register Sharing in Datapath for Structural Robustness against Delay Variation, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.4, p.1044-1053, April 2008