Logic and madness

What do Bertrand Russell (philosopher, logician and mathematician), Gottlob Frege (the great logician), Georg Cantor (inventor of set theory), David Hilbert (inventor of Hilbert spaces), Kurt Gödel (guru of incompleteness theory), Ludwig Wittgenstein (god of 20th century philosophy), the Greek city of Athens, the Oresteian trilogy and a dog named Manga all have in common?

They all star in the 2009 graphic novel Logicomix: An Epic Search for Truth, written by Apostolos Doxiadis and Christos Papadimitriou, drawn by Alecos Papadatos and colored by Annie Di Donna. It’s a rip-roaring tale of passion and madness, mixing fiction and reality, with frequent breaches of the fourth wall, and all presented through bright and colorful art and word balloons. For anyone interested in Logic, Mathematics or Philosophy, it presents Russell’s maddening journey during his quest for establishing the foundations of mathematics through logical certainty. It was during this journey that Russell, along with Alfred North Whitehead, wrote their seminal three-volume work, Principia Mathematica.

I first read about the book in the New York Times’ Sunday Books Review way back in the fall of 2009, but was only able to read it during a recent vacation. The story is engaging and entertaining, with just enough provocation for those who are more theoretically inclined to continue learning about these pioneer logicians beyond the pages of the book itself. The art is very reminiscent of Hergé’s ligne claire drawing style. Highly recommended.

Non-determinism in HDLs

Digital logic can be modeled and simulated using an event-driven simulator in a hardware description language (HDL), such as Verilog or VHDL. When these models are used for synthesis into logic gates, the HDL code is necessarily restricted to a subset of the respective language, as required by the synthesis tool in use. There exist industry-established guidelines for writing synthesizable code, and every synthesis tool vendor can provide a good reference.

Unfortunately, one of the greatest challenges during integration and IP reuse of legacy Verilog code is the potential for non-deterministic behavior during execution. These issues typically arise when there is an execution race condition within the Verilog code. Although a wider discussion of the relative strengths of each language is beyond the scope of this essay, these race conditions are not possible in legacy VHDL code, due to the determinism inherently guaranteed by the language definition.

Unlike strongly-typed languages such as C or VHDL, the Verilog language was not standardized by the IEEE until after it had achieved widespread popularity. As a result, the language started off with a de facto standard as defined by the behavior of the Verilog-XL compiler/simulator (which is currently owned by Cadence). Unfortunately, flaws in this de facto language definition allowed users the latitude to create code that exhibited simulator-dependent behavior during execution.

One such example of non-deterministic behavior can occur when blocking assignments are used without care. In any HDL, there are two types of signal assignments: blocking and non-blocking. A blocking assignment is executed immediately, just as in any sequential programming language such as C. A non-blocking assignment is added to an event-queue and not executed until a subsequent iteration, in keeping with the semantics of the particular event-driven programming language being used. This behavior gets further complicated when time delays are added.

The following snippet of Verilog code (from Clifford Cummings, Nonblocking Assignments in Verilog Synthesis, Coding Styles That Kill!, SNUG-2000) illustrates an example of simulator-dependent behavior:

module fbosc1 (y1, y2, clk, rst);
    output y1, y2;
    input clk, rst;
    reg y1, y2;
    always @(posedge clk or posedge rst)
        if (rst)  y1 = 0; // reset
        else      y1 = y2;
    always @(posedge clk or posedge rst)
        if (rst)  y2 = 1; // preset
        else      y2 = y1;
endmodule // fbosc1

The Verilog standard does not require the two “always” blocks to be executed by the simulator in any particular order, and as a result, the final values of the variables y1 and y2 become dependent on the order in which the simulator decides to execute the blocks. Fortunately, this problem can be entirely avoided by using non-blocking statements instead, as shown below.

module fbosc2 (y1, y2, clk, rst);
    output y1, y2;
    input clk, rst;
    reg y1, y2;
    always @(posedge clk or posedge rst)
        if (rst)  y1 <= 0; // reset
        else      y1 <= y2;
    always @(posedge clk or posedge rst)
        if (rst)  y2 <= 1; // preset
        else      y2 <= y1;
endmodule // fbosc2

In fact, there are many published guidelines on good Verilog design practices, and these are largely followed by the design community nowadays. However, it is a significant shortcoming of a language when “best practices” are required to ensure deterministic behavior of the executed code.

This kind of behavior is avoided when using VHDL, which purposefully limits the scope of variables which can accept blocking assignments. Where Verilog uses the reg and wire transport types, VHDL uses only signal. According to the VHDL language definition, a signal can only accept non-blocking assignments, which in turn are handled via the event queue. However, blocking assignments can be made to the variable type, but by definition the scope of a variable is restricted to within a process block (a process block in VHDL is equivalent to an always block in Verilog). If it is desired that the value of a computed variable be made visible outside a process block, the value of the variable needs to first be assigned to a signal (whose scope by definition extends to the hierarchy above). As a result, the language definition preserves determinism by preventing the occurrence of race conditions created by careless use of blocking assignments.

As mentioned above, this post is not meant for passing judgement on the suitability of using either VHDL or Verilog for a particular purpose. Rather, it is intended as a warning and encouragement to heed established guidelines for achieving the best results. Nowadays, robust design methodologies require certain Verilog compiler flags and Lint options to be enabled in order to allow detection of such cases so they may be corrected before simulation. However, older code bases of unknown origin and questionable quality can still pose a potential source of problems and project delays. Seasoned industry veterans advocate the use of extensive simulation verification test suites in order to provide confidence, but a “deterministic by compilation” approach will always be preferred.

Copyright © 2008 – 2012 Waqas Akram. All Rights Reserved.

Blogger’s block?

No one ever gets talker’s block. No one wakes up in the morning, discovers he has nothing to say and sits quietly, for days or weeks, until the muse hits, until the moment is right, until all the craziness in his life has died down.

Why then, is writer’s block endemic?

From an interesting blog post, complete with bonus link to Ira Glass interview.

Journal publication

Today, my paper on Tunable Mismatch Shaping for Quadrature Bandpass Delta-Sigma Data Converters was published in the Journal of Signal Processing Systems, Volume 65, Number 2, pp 199-210, November 2011.

From the abstract:

This paper presents an architecture for quadrature bandpass mismatch shaping that allows the center frequency of the mismatch suppression band to be tunable over the entire Nyquist range. The approach is based on the previously reported complex-valued tree-based mismatch shaper, and extends this to allow tunable operation. The proposed design has been implemented using VHDL and synthesized to logic gates. The hardware complexity and mismatch shaping performance of the proposed architecture are compared to that of a reference architecture, which uses separate tunable mismatch shapers for each complex component path. Simulation results show consistent mismatch shaping performance across the entire tuning range.

A pre-publication version of the paper can be downloaded here (pdf).

Patently interesting

I’m a pretty big fan of Ira Glass and his radio program, This American Life, and I try to listen to every episode possible. My recent travels have hindered this, and I’m only now starting to catch up with some missed episodes from the summer. A recent episode titled When Patents Attack! really caught my ear.

Today, I was pleased to learn that my paper was selected for inclusion in a special issue of the Journal of Signal Processing Systems on the “Top Picks from the SiPS 2010”. The issue assembles extended versions of the top 7-10 selected papers from the 2010 IEEE Workshop on Signal Processing Systems (SiPS), which took place last year in October, 2010.

Co-authored with my doctoral adviser, Prof. Earl E. Swartzlander, Jr., the paper is titled Tunable Mismatch Shaping for Quadrature Bandpass Delta-Sigma Data Converters and presents a technique that allows the center frequency of the mismatch noise shaping transfer function through a quadrature bandpass delta-sigma DAC to be adjustable over the entire Nyquist range.

PhD defense success!

My PhD is officially complete. The final doctoral defense took place today and I can thankfully say that I passed with flying colors. The dissertation is titled Tunable Mismatch Shaping for Bandpass Delta-Sigma Data Converters. I’m looking forward to a long summer of rest, particularly after the intensity of the past several months.