A functional formalization of on chip communications
Open Access
- 1 May 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 20 (3) , 241-258
Abstract
This paper presents a formal model and a systematic approach to the validation of communication architectures at a high level of abstraction. This model is described mathematically by a function, named GeNoC . The correctness of GeNoC is expressed as a theorem, which states that messages emitted on the architecture reach their expected destination without any modification of their content. The model identifies the key constituents common to all on chip communication architectures, and their essential properties from which the correctness theorem is deduced. Each constituent is represented by a function that has no explicit definition but is constrained to satisfy the essential properties. Thus, the validation of a particular architecture is reduced to the proof that its concrete definition satisfies the essential properties. In practice, the model has been defined in the logic of the ACL2 theorem proving system. We illustrate our approach on several architectures that constitute concrete instances of the generic GeNoC model. Some of these applications come from industrial designs, such as the AMBA AHB bus or the Octagon network from ST Microelectronics.Keywords
This publication has 12 references indexed in Scilit:
- A Generic Model for Formally Verifying NoC Communication Architectures: A Case Study2007
- Æthereal Network on Chip:Concepts, Architectures, and ImplementationsIEEE Design & Test of Computers, 2005
- Modeling layered distributed communication systemsFormal Aspects of Computing, 2005
- A Generic Network on Chip ModelLecture Notes in Computer Science, 2005
- Deadlock Prevention in the Æthereal ProtocolLecture Notes in Computer Science, 2005
- A Unified Fault-Tolerance Protocol2004
- Using formal techniques to debug the AMBA system-on-chip bus protocol2003
- An interconnect architecture for networking systems on chipsIEEE Micro, 2002
- A formal model of asynchronous communication and its use in mechanically verifying a biphase mark protocolFormal Aspects of Computing, 1994
- Symbolic Model Checking1993