Nothing Special   »   [go: up one dir, main page]

skip to main content
article
Free access

Effects of resource sharing on circuit delay: an assignment algorithm for clock period optimization

Published: 01 April 1998 Publication History

Abstract

This paper analyzes the effect of resource sharing and assignment on the clock period of the synthesized circuit. The assignment phase assigns or binds operations of the scheduled behavioral description to a set of allocated resources. We focus on control-flow intensive descriptions, characterized by the presence of mutually exclusive paths due to the presence of nested conditional branches and loops.
We show that clustering multiple operations in the same state of the schedule, possibly leading to chaining of functional units (FUs) in the RTL circuit, is an effective way to minimize the total number of clock cycles, and hence total execution time. We present an assignment algorithm that is particularly effective for such design styles by minimizing data chaining and hence the clock period of the circuit, thereby leading to further reduction in total execution time.
Existing resource sharing and assignment approaches for reducing the clock period of the resulting circuit either increase the resource allocation or use faster modules, both leading to leading to larger area requirements. In this paper we show that even when the type of available resource units and the number of resource units of each type is fixed, different assignments may lead to circuits with significant differences in clock period.
We provide a comprehensive analysis of how resource sharing and assignment introduces long paths in the circuit. Based on the analysis, we develop an assignment algorithm that uses a high-level delay estimator to asign operations to a fixed set of available resources so as to minimize the clock period of the resultant circuit, with no or minimal effect on the area of the circuit. Experimental results on several conditional-intensive designs demonstrate the effectiveness of the assignment algorithm.

References

[1]
AVRA, L. 1991. Allocation and assignment in high-level synthesis for self-testable data paths. In Proceedings of the IEEE International Test Conference. 463-472.
[2]
BERGAMASCHI, R. A., CAMPOSANO, R., AND PAYER, M. 1991. Data-path synthesis using path analysis. In Proceedings of the 28th ACM/IEEE Conference on Design Automation (DAC '91, San Francisco, CA, June 17-21, 1991). ACM Press, New York, NY, 591-596.
[3]
BHATTACHARYA, S. 1995. Hardware synthesis and analysis of control-intensive designs from high level specifications. Ph.D. Dissertation. Duke University, Durham, NC.
[4]
BHATTACHARYA, S., BRGLEZ, F., AND DEY, S. 1993. Transformations and resynthesis for testability of RT-level control-data path specifications. IEEE Trans. Very Large Scale Integr. Syst. 1, 3 (Sept.), 304-318.
[5]
BHATTACHARYA, S., BRGLEZ, F., AND DEY, S. 1996. Fast true delay estimation during high level synthesis. IEEE Trans. CAD 15, 9 (Sept.), 1088-1105.
[6]
BHATTACHARYA, S., DEY, S., AND BRGLEZ, F. 1994. Clock period optimization during resource sharing and assignment. In Proceedings of the 31st Annual Conference on Design Automation (DAC'94, San Diego, CA, June 6-10, 1994). ACM Press, New York, NY, 195-200.
[7]
BHATTACHARYA, S., DEY, S., AND BRGLEZ, F. 1994. Performance analysis and optimization of schedules for conditional and loop-intensive specifications. In Proceedings of the 31st Annual Conference on Design Automation (DAC'94, San Diego, CA, June 6-10, 1994). ACM Press, New York, NY, 491-496.
[8]
CLSI USERS GUIDE 1991.
[9]
DEY, S., RAGHUNATHAN, A., JHA, N. K., AND WAKABAYASHI, K. 1996. Controller re-specification to minimize switching activity in controller/data path circuits. Tech. Rep. 96-C007-4-5016-1. NEC C&C Research Labs, Princeton, NJ.
[10]
GAREY, M. AND JOHNSON, D. 1979. Computers and Intractability. W. H. Freeman & Co., New York, NY.
[11]
GREGORY, B., MACMILLEN, D., AND FOGG, D. 1992. ISIS: A system for performance driven resource sharing. In Proceedings of the 29th ACM/IEEE Conference on Design Automation (DAC '92, Anaheim, CA, June 8-12). IEEE Computer Society Press, Los Alamitos, CA, 285-290.
[12]
HINTZ, K. AND TABAK, D. 1992. MicrocontroUers: Architecture, Implementation, and Programming. McGraw-Hill, Inc., New York, NY.
[13]
HUANG, S. C.-Y. AND WOLF, W. H. 1994. How datapath allocation affects controller delay. In Proceedings of the International Symposium on System Synthesis. 158-163.
[14]
HUANG, S. C.-Y. AND WOLF, W. H. 1994. Performance-driven synthesis in controller-datapath systems. IEEE Trans. Very Large Scale Integr. Syst. 2, 1 (Mar.), 68-80.
[15]
JAIN, R., MLINAR, M., AND PARKER, A. 1988. Area-time model for synthesis of non-pipelined designs. In Proceedings of the International Conference on Computer-Aided Design (ICCAD '88, Santa Clara, CA, Nov.). 48-51.
[16]
KIM, T., LIU, J., AND LIU, C. 1991. A scheduling algorithm for conditional resource sharing. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14). IEEE Computer Society Press, Los Alamitos, CA.
[17]
KOZMINSKI, K., Ed. 1992. OASIS Users Guide. MCNC, Research Triangle Park, NC.
[18]
PAULIN, P. G. AND KNIGHT, J. P. 1989. Force-directed scheduling for the beavioral synthesis of ASICs. IEEE Trans. CAD 8, 6 (June), 661-679.
[19]
PERRY, D. 1989. VHDL. McGraw-Hill, Inc., New York, NY.
[20]
RAMACHANDRAN, C., KURDAHI, F. J., GAJSKI, D. D., Wv, A. C.-H., AND CHAIYAKUL, V. 1992. Accurate layout area and delay modeling for system level design. In Proceedings of the 1992 IEEE/ACM International Conference on Computer-Aided Design (ICCAD '92, Santa Clara, CA, Nov. 8-12). IEEE Computer Society Press, Los Alamitos, CA, 355-361.
[21]
RAMACHANDRAN, L. AND GAJSKI, D. 1991. An algorithm for component selection in performance optimized scheduling. In Proceedings of the IEEE International Conference on Computer- Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14). IEEE Computer Society Press, Los Alamitos, CA, 92-95.
[22]
RUNDENSTEINER, E. A. AND GAJSKI, D. D. 1992. Functional synthesis using area and delay optimization. In Proceedings of the 29th ACM/IEEE Conference on Design Automation (DAC '92, Anaheim, CA, June 8-12). IEEE Computer Society Press, Los Alamitos, CA, 291-296.
[23]
SENTOVICH, E., SINGH, K., MOON, C., SAVOJ, H., BRAYTON, R., AND SANGIOVANNI-VINCENTELLI, A. 1992. Sequential circuit design using synthesis and optimization. In Proceedings of the ICCD. 328-333.
[24]
STOK, L. 1992. False loops through resource sharing. In Proceedings of the 1992 IEEE/ACM International Conference on Computer-Aided Design (ICCAD '92, Santa Clara, CA, Nov. 8-12). IEEE Computer Society Press, Los Alamitos, CA, 345-348.
[25]
TANENBAUM, A. S. 1988. Computer Networks. Prentice-Hall, Inc., Upper Saddle River, NJ.
[26]
TSENG, C. AND SIEWIOREK, D 1986. Automated synthesis of data paths on digital systems. IEEE Trans. CAD 5, 3 (July), 379-395.
[27]
WAKABAYASHI, K. AND YOSHIMURA, T. 1989. A resource sharing and control synthesis method for conditional branches. In Proceedings of the International Conference on Computer-Aided Design (ICCAD). 62-65.
[28]
Woo, N.-S. 1990. A global, dynamic register allocation and binding for a data path synthesis system. In Proceedings of the ACM/IEEE Conference on Design Automation (DAC '90, Orlando, FL, June 24-28). ACM Press, New York, NY, 505-510.
[29]
YANG, S. 1991. Logic synthesis and optimization benchmarks, user guide version 3.0. In Proceedings of the International Workshop on Logic Synthesis. MCNC, Research Triangle Park, NC.

Cited By

View all
  • (2006)Register transfer level power optimization with emphasis on glitch analysis and reductionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.77563218:8(1114-1131)Online publication date: 1-Nov-2006
  • (2005)Applying Resource Sharing Algorithms to ADL-driven Automatic ASIP ImplementationProceedings of the 2005 International Conference on Computer Design10.1109/ICCD.2005.25(193-199)Online publication date: 2-Oct-2005

Index Terms

  1. Effects of resource sharing on circuit delay: an assignment algorithm for clock period optimization

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Design Automation of Electronic Systems
      ACM Transactions on Design Automation of Electronic Systems  Volume 3, Issue 2
      April 1998
      199 pages
      ISSN:1084-4309
      EISSN:1557-7309
      DOI:10.1145/290833
      • Editor:
      • C. L. Liu
      Issue’s Table of Contents

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Journal Family

      Publication History

      Published: 01 April 1998
      Published in TODAES Volume 3, Issue 2

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. clock period
      2. high-level synthesis
      3. resorce sharing

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)32
      • Downloads (Last 6 weeks)4
      Reflects downloads up to 13 Nov 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2006)Register transfer level power optimization with emphasis on glitch analysis and reductionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.77563218:8(1114-1131)Online publication date: 1-Nov-2006
      • (2005)Applying Resource Sharing Algorithms to ADL-driven Automatic ASIP ImplementationProceedings of the 2005 International Conference on Computer Design10.1109/ICCD.2005.25(193-199)Online publication date: 2-Oct-2005

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Get Access

      Login options

      Full Access

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media