Wednesday, August 15, 2012

Laws and Verification

It’s Independence Day in India and I decided to use the freedom of applying some of the common laws to “Sid’dha-karana” aka Verification" :)

LAW means “a generalization that describes recurring facts or events in nature” and engineering is full of laws. Though laws are formulated for a particular aspect of engineering, most of these are widely applicable to parallel areas too. The idea here is to salute the heroes who articulated these postulates and derive conclusions applicable to our field of interest.

The Laws

In semiconductor industry the most widely referenced one is Moore’s Law formulated by Intel co-founder Gordon E. Moore, who described the trend in his paper (1965) later generalized as – The number of transistors on a chip will double approximately every two years.

Another common adage quite popular is Murphy’s Law named after Edward A Murphy based on his conclusion after experiments in 1949 stating "If there's more than one way to do a job, and one of those ways will result in disaster, then somebody will do it that way." The law is more generalized since then as – Anything that can go wrong, will go wrong.

Next set of laws form the basis for classical mechanics popularly known as Newton’s law of motion compiled by Sir Isaac Newton in 1687. The laws are –
First Law - Every object in a state of uniform motion tends to remain in that state of motion unless an external force is applied to it.
Second Law – The relationship between an object's mass m, its acceleration a, and the applied force F is F = ma. Acceleration and force are vectors and the direction of the force vector is the same as the direction of the acceleration vector.
Third Law – For every action there is an equal and opposite reaction.

Another law commonly discussed with reference to multiprocessing is Amdahl's law named after computer architect Gene Amdahl. It states that the performance improvement to be gained from using some faster mode of execution is limited by the fraction of the time the faster mode can be used.

Finally the law of Natural Selection formulated by Charles Darwin in support of the theory of evolution stating that, some individuals survive and reproduce more often than others, and as a consequence their heritable characteristics become more common over time.

Applying to Verification

Moore’s law – Amount of code to be verified doubles every 2 years.

Murphy’s law – Any code that isn’t verified will not work.

Based on the above two laws, we can further derive a conclusion that total Verification effort doubles every 2 years where effort = Engg time + Tools + Flows + CPU cycles.

Newton laws
First Law - Once the bug rate stabilizes, every code continues to be stable unless there is a change in external force. This force can be exerted by modifying constraints, introducing another methodology like assertions, formal etc.
Second Law - The improvement in rate of finding bugs is directly proportional to the net force applied and is inversely proportional to the total lines of code. This means, the effort, approach and outcome all depend on the F=ma relationship wherein, force is same as described in First law, m = lines of code and a is improvement in bug rate. In comparison to IPs, for large designs like SoCs, the effort is more while modifying the approach and the rate of finding bugs slows down for a given time.
Third Law - Every attempt to break the design results into more stable and mature design.

Amdahl’s law – When multiple verification techniques are applied, the overall gain (i.e. stability of code) is limited by the fraction of the time these techniques can be used e.g. CRV over directed, Formal over CRV, Manual tests vs auto generation of tests etc.

Law of Natural Selection – Change is inevitable and during the process of verification evolution, multiple approaches show up but only few find their footprint across design tape outs.

Drop in a comment with other laws you find applying to verification!
Happy Independence Day!!!