Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1954))
Included in the following conference series:
594Accesses
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
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
F. Bacelli et al.Synchronisation and Linearity-Algebra for Discrete Event Systems, Wiley, 1992.
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.
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.
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.
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.
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.
R. de Nicola and M. C. B. Hennessy. Testing Equivalence for Processes.Theoretical Computer Science, Vol. 34, No. 1/2, pp. 83–134, 1984.
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.
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.
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.
M. J. C. Gordon and T. F. Melham.Introduction to HOL, Cambridge University Press, 1993.
C. A. R. Hoare.Communication Sequential Processes, International Series in Computer Science, Prentice Hall, 1985.
G. J. Milne.Formal Specification and Verification of Digital Systems,McGraw-Hill, 1994.
R. Milner.Communication and Concurrency, International Series in Computer Science, Prentice Hall, 1989.
F. Moller. The Semantics of Circal, Technical Report HDV-3-89, University of Strathclyde, Department of Computer Science, Glasgow, UK, 1989.
A. W. Roscoe.The Theory and Practice of Concurrency, International Series in Computer Science, Prentice Hall, 1998.
I. E. Sutherland. Micropipelines.Com. of ACM, Vol. 32, No. 6, pp. 720–738, 1989.
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.
Author information
Authors and Affiliations
Software Verification Research Centre, The University of Queensland, QLD 4072, Brisbane, Australia
Antonio Cerone
Advanced Computing Research Centre, University of South Australia, SA 5095, Adelaide, Australia
George J. Milne
- Antonio Cerone
You can also search for this author inPubMed Google Scholar
- George J. Milne
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Austin Research Laboratories, IBM Corporation, Mail Stop 9460, Building 904 11501 Burnet Road, 78758, Austin, Texas, USA
Warren A. Hunt Jr.
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
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-41219-9
Online ISBN:978-3-540-40922-9
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative