|Verification Futures 2018 (click here to see full programme)
|Pradeep Kumar Nalla, Senior Test and Verification Engineer, Test and Verification Solutions Ltd
|Efficient Formal Verification of Liveness and Freedom from Deadlock
|As far as verification of hardware systems are concerned, two types of properties are prevalent. Verification properties may be classified as safety vs liveness. Safety properties assert that something bad never happens. Whereas, liveness properties assert that something good will eventually happen.
Liveness properties are crucial to the variety of design types – for example, systems containing arbiters (where we check for requests are eventually acknowledged), critical FSMs (Finite State Machines) (a desirable state is eventually reached), transaction queuing (FIFOs/Queues) (data is eventually drained), clock gating to save dynamic power consumption (design should eventually not become busy) and LRU (Least Recently Used) cache replacement algorithms in cache blocks (every entry has a path to LRU).
Safety properties typically contain finite length counterexample depicting a failure condition, whereas liveness properties contain an infinite-length counterexample (a prefix followed by a lasso-shaped suffix), typically known as livelock. Wherever there is a scope for liveness verification, underlying there exists scope for verification of freedom from deadlock as well, as it is a weak form of liveness, i.e. absence of livelock can guarantee the absence of deadlocks, however livelock detected in a design may not be a deadlock. Liveness verification is more challenging and known to be significantly less scalable in practice despite the variety of algorithms available to solve them.
In this paper, we will discuss the strategies for efficient treating of liveness and freedom from deadlock using formal verification, especially to go beyond bug hunting to achieve full proof/exhaustive verification to establish the correctness of the design.
These strategies include:
Bounded liveness vs unbounded liveness verification. The bounded liveness verification is much more scalable than unbounded version since it does not entail the overhead of state repetition logic and for finite designs it is complete given an adequately large time bound. If we observe a proof or unreachable condition, then it is also valid for unbounded version.
Constrain the model using high impact input conditions in order to bring down the complexity, which is an under-approximation. If we observe a failure condition then it is also valid on original problem.
Auto identification of deadlock sources using external interfaces or FSM design specifications and their conversion to safety properties.
Finally, tuning the knobs of design configuration (parameterization) to a lowest complex configuration such that proving the design with this configuration is still complete and can be treated as design robust confidence measure.
This talk will cover:
|Pradeep Kumar Nalla has 10 years of industry experience in the VLSI field and is currently a Senior Test and Verification Engineer at Test and Verification Solutions Ltd. Prior to joining T&VS he worked at IBM Server Processors group for ~6 years as part of the EDA-India Verification tools team, involved in development and support for the formal verification tool SixthSense. Before joining IBM he was with Atrenta India where he developed and supported the tool Sequential Equivalence Checking for Power optimisation. Pradeep obtained his Ph.D. (Efficient distributed bounded property checking) from the University of Tuebingen, Germany in 2008. He holds five US patents with seven filed and one under evaluation. He has co-authored 20 papers in various international conferences and workshops.