[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

Efficient Algorithms for Interface Timing Verification

Published: 01 April 1998 Publication History

Abstract

This paper presents algorithms for computing separations between events that are constrained to obey prespecified relationships in their relative time of occurrence. The algorithms are useful for interface timing verification, where event separations are checked against timing requirements. The first algorithm computes separations when only linear and max constraints exist. The algorithm must converge to correct maximum separation values in a finite number of steps, or report an inconsistence of the constraints, irrespective of the existence of infinite constraint bounds or infinite event separations. It is conjectured to run in O(V E + V^2 log V) time, where V is the number of events, and E is the number of relationships between them. The other algorithms extend the first, and compute event separations in the NP-complete version of the problem where min constraints exist. Experiments demonstrate the algorithms are efficient in practice.

References

[1]
1. T. Amon, H. Hulgaard, S.M. Burns, and G. Borriello, "An algorithm for exact bounds on the time separation of events in concurrent systems," in Proceedings of IEEE International Conference on Computer Design , pp. 166-173, 1993.
[2]
2. G. Borriello and R. Katz, "Synthesis and optimization of interface transducer logic," in Proceedings of IEEE International Conference on Computer-Aided Design , 1987.
[3]
3. J.A. Brzozowski, T. Gahlinger, and F. Mavaddat, "Consistency and satisfiability of waveform timing specification," Networks , pp. 91-107, Jan. 1991.
[4]
4. T. Burks and K. Sakallah, "Min-max linear programming and the timing analysis of digital circuits," in Proceedings of IEEE International Conference on Computer-Aided Design , pp. 152-155, 1993.
[5]
5. P. Chou, E.A. Walkup, and G. Borriello, "Scheduling for reactive real-time systems," IEEE MICRO , Vol. 14, No. 4, pp. 37-47, Aug. 1994.
[6]
6. T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms . McGraw-Hill, 1990.
[7]
7. A.J. Daga and W.P. Birmingham, "VITCh: A methodology for the timing verification of board-level circuits," in Proceedings of TAU Workshop , 1993.
[8]
8. T. Gahlinger, "Coherence and satisfiability of waveform timing specification," Ph.D. thesis, University of Waterloo, May 1990.
[9]
9. Integrated Device Technology, Inc., Logic Data Book , 1990.
[10]
10. Intel Corporation, Microsystem Components Handbook , 1986.
[11]
11. Intel Corporation, Microprocessors , 1990.
[12]
12. Intel Corporation, Memory , 1990.
[13]
13. D. Ku and G. de Micheli, "Relative scheduling under timing constraints," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , Vol. 11, No. 6, pp. 696-717, June 1992.
[14]
14. L. Lavagno and A. Sangiovanni-Vincentelli, "Linear programming for optimum hazard elimination in asynchronous circuits," in Proceedings of IEEE International Conference on Computer Design , 1992.
[15]
15. Y.-Z. Liao and C.K. Wong, "An algorithm to compact a VLSI symbolic layout with mixed constraints," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , Vol. CAD-2, No. 2, pp. 62-69, April 1983.
[16]
16. K. McMillan and D. Dill, "Algorithms for interface timing verification," in Proceedings of IEEE International Conference on Computer Design , pp. 48-51, 1992.
[17]
17. C. Myers and T.H.Y. Meng, "Synthesis of timed asynchronous circuits," in Proceedings of IEEE International Conference on Computer Design , pp. 279-284, 1992.
[18]
18. K.A. Sakallah, T.N. Mudge, and O.A. Olukotun, "Timing verification and optimal clocking of synchronous digital circuits," in Proceedings of IEEE International Conference on Computer-Aided Design , 1990.
[19]
19. P. Vanbekbergen, G. Goossens, and H. de Man, "Specification and analysis of timing constraints in signal transition graphs," in Proceedings of the European Conference on Design Automation , pp. 302-306, 1992.
[20]
20. E.A. Walkup, "Optimization of linear max-plus systems with application to timing analysis," Ph.D. thesis, University of Washington, 1995.
[21]
21. E.A. Walkup and G. Borriello, "Interface timing verification with application to synthesis," in Proceedings of Design Automation Conference , pp. 106-112, 1994.
[22]
22. W.H. Wolf and A.E. Dunlop, "Symbolic layout and compaction" in B.T. Preas and M.J. Lorenzetti (Eds.), Physical Design Automation of VLSI Systems , Benjamin-Cummings, Chap. 6, pp. 211-281, 1988.
[23]
23. Ti-Yen Yen and W. Wolf, "Performance estimation for real-time distributed embedded systems," in Proceedings of IEEE International Conference on Computer Design , pp. 64-69, 1995.

Cited By

View all
  • (2009)Scenario-based timing verification of multiprocessor embedded applicationsACM Transactions on Design Automation of Electronic Systems10.1145/1529255.152925914:3(1-58)Online publication date: 4-Jun-2009
  • (2006)Reasoning about synchronization in GALS systemsFormal Methods in System Design10.1007/s10703-006-7841-y28:2(153-169)Online publication date: 1-Mar-2006
  • (2005)Min-Max Inequalities and the Timing Verification Problem with Max and Linear ConstraintsDiscrete Event Dynamic Systems10.1007/s10626-004-6209-y15:2(119-143)Online publication date: 1-Jun-2005

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Formal Methods in System Design
Formal Methods in System Design  Volume 12, Issue 3
April 1, 1998
65 pages
ISSN:0925-9856
Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 1998

Author Tags

  1. linear and max constraints
  2. microprocessor bus
  3. timing verification

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2009)Scenario-based timing verification of multiprocessor embedded applicationsACM Transactions on Design Automation of Electronic Systems10.1145/1529255.152925914:3(1-58)Online publication date: 4-Jun-2009
  • (2006)Reasoning about synchronization in GALS systemsFormal Methods in System Design10.1007/s10703-006-7841-y28:2(153-169)Online publication date: 1-Mar-2006
  • (2005)Min-Max Inequalities and the Timing Verification Problem with Max and Linear ConstraintsDiscrete Event Dynamic Systems10.1007/s10626-004-6209-y15:2(119-143)Online publication date: 1-Jun-2005

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media