Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

A Methodology for the Formal Analysis of Asynchronous Micropipelines

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1954))

Abstract

In this paper we present a process algebra approach for the integrated verification of correctness and performance in concurrent systems. The verification procedure is entirely performed within the Circal process algebra, without any recourse to other formalisms. Performance is characterised in terms of logical properties, which do not incorporate explicit time. Such properties are then interpreted in terms of degree of parallelism and allow the quantitative evaluation of the throughput of the system. The approach has been applied to two four-phase handshaking protocols, which are motivated by the implementation of the AMULET2 asynchronous RISC processor. Both correctness and performance properties are captured in the same verification framework and automatically proved using the Circal System.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. F. Bacelli et al.Synchronisation and Linearity-Algebra for Discrete Event Systems, Wiley, 1992.

    Google Scholar 

  2. A. Bailey, G. A. McCaskill and G. J. Milne. An Exercise in the Automatic Verification of Asynchronous Designs.Formal Methods in System Design, Vol. 4, No. 3, pp. 213–242, 1994.

    Article MATH  Google Scholar 

  3. T. Bolognesi, and E. Brinksma. Introduction to the ISO specification language LOTOS.Computer Networks and ISDN Systems, Vol. 14, No. 1, pp. 25–59, 1987.

    Article  Google Scholar 

  4. A. Cerone, D. A. Kearney and G. J. Milne. Integrating the Verification of Timing, Performance and Correctness Properties of Concurrent Systems. InProc. of the Int. Conference on Application of Concurrency to System Design,Aizu-Wakamatsu City, Japan, pp. 109–119, IEEE Comp. Soc. Press, 1998.

    Google Scholar 

  5. A. Cerone and G. J. Milne. Modelling a Subclass of CMOS Circuits using a Process Algebra. InProc. 6th Annual Australasian Conference on Parallel and Real-Time Systems (PART’99), Melbourne, Australia, pp. 386–397, Springer-Verlag, Berlin, 1999.

    Google Scholar 

  6. T. A. Chu, C. K. C. Leung and T. S. Wanuga. A Design Methodology for Concurrent VLSI Systems. InProc. of ICDD, pp. 407–410, 1985.

    Google Scholar 

  7. R. de Nicola and M. C. B. Hennessy. Testing Equivalence for Processes.Theoretical Computer Science, Vol. 34, No. 1/2, pp. 83–134, 1984.

    Article MATH MathSciNet  Google Scholar 

  8. S. Donatelli, J. Hillston and M. Ribaudo. Comparison of Performance Evaluation Process Algebra and Generalized Stochastic Petri Nets. InProc. of the 6th Int. Work. on Petri Nets and Performance Models, IEEE Comp. Soc. Press, 1995.

    Google Scholar 

  9. S. B.. Furber and P. Day. Four-Phase Micropipeline Latch Control Circuit.IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 4, No. 2, pp. 247–253, 1996.

    Article  Google Scholar 

  10. S. B. Furber and J. Lin. Dynamic Logic in Four-Phase Micropipelines. InProc. of the 2nd Int. Symp. on Adv. Research in Asynchronous Circuits and Systems, IEEE Comp. Soc. Press, 1996.

    Google Scholar 

  11. M. J. C. Gordon and T. F. Melham.Introduction to HOL, Cambridge University Press, 1993.

    Google Scholar 

  12. C. A. R. Hoare.Communication Sequential Processes, International Series in Computer Science, Prentice Hall, 1985.

    Google Scholar 

  13. G. J. Milne.Formal Specification and Verification of Digital Systems,McGraw-Hill, 1994.

    Google Scholar 

  14. R. Milner.Communication and Concurrency, International Series in Computer Science, Prentice Hall, 1989.

    Google Scholar 

  15. F. Moller. The Semantics of Circal, Technical Report HDV-3-89, University of Strathclyde, Department of Computer Science, Glasgow, UK, 1989.

    Google Scholar 

  16. A. W. Roscoe.The Theory and Practice of Concurrency, International Series in Computer Science, Prentice Hall, 1998.

    Google Scholar 

  17. I. E. Sutherland. Micropipelines.Com. of ACM, Vol. 32, No. 6, pp. 720–738, 1989.

    Article  Google Scholar 

  18. T. Williams. Analyzing and Improving the latency and throughput performance on self-timed pipelines and rings. InProc. of the IEEE Int. Symp. on Circuit and Systems, New York, IEEE Comp. Soc. Press, 1992.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Software Verification Research Centre, The University of Queensland, QLD 4072, Brisbane, Australia

    Antonio Cerone

  2. Advanced Computing Research Centre, University of South Australia, SA 5095, Adelaide, Australia

    George J. Milne

Authors
  1. Antonio Cerone

    You can also search for this author inPubMed Google Scholar

  2. George J. Milne

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Austin Research Laboratories, IBM Corporation, Mail Stop 9460, Building 904 11501 Burnet Road, 78758, Austin, Texas, USA

    Warren A. Hunt Jr.

  2. Computer Science Department, Indiana University, Lindley Hall, 150 W. Woodlawn Avenue, 47405-7104, Bloomington, Indiana, USA

    Steven D. Johnson

Rights and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cerone, A., Milne, G.J. (2000). A Methodology for the Formal Analysis of Asynchronous Micropipelines. In: Hunt, W.A., Johnson, S.D. (eds) Formal Methods in Computer-Aided Design. FMCAD 2000. Lecture Notes in Computer Science, vol 1954. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40922-X_16

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp