How languages influence design, and why we should care: a tale of C, Verilog, and trouble
Most of us don’t have the luxury to stop and reflect very often, especially about design language theory. In this writer’s case that is probably just as well, as my theoretical speculations tend to wander into quicksand with improbable regularity. But a recent conversation with Steve Teig, EDA industry luminary, currently president and CTO of stealth start-up Tabula, and someone whose speculations are very much worth following, set me to thinking on the subject.
Teig was talking about the relationship between the language in which an algorithm is coded, the target architecture, and the results. Much of his thinking he anchored in a very important distinction: between languages that describe algorithms and languages that describe implementations. (He uses other, more precise terms, but I think that captures the distinction adequately for our purposes here.) If you think about languages in these terms, it becomes clear that trying to describe an algorithm in an implementation language may limit the range of concepts you can capture and restrict the range of target implementation architectures you can serve well.
For example, contrast two programming languages, one obscure and one inescapable: APL and C. APL (see here, for instance) was created to express algorithms that had two key characteristics: their variables were often multidimensional arrays or lists, and their transformations could be defined as recursive processes. APL can express such algorithms with concise, precise elegance. I think—I’m not sure I ever really learned to read it. But an APL interpreter for any known computer had to be a masterpiece of coding skill. It had to be a self-contained environment that compensated for the differences between the sort of linear-algebra world in which the great turn-of-century mathematicians lived and the sort of resource-starved clockwork that passed for a computer in the 1970s.
C could not be more different. At the risk of offending anyone who learned programming after about 1975, C is extraordinarily implementation-specific for a text-based language. It is little more than a short-hand for PDP-11 assembly code. It is an indelible tribute to Gordon Bell that his instruction set architecture was so splendid that it could be used to adequately describe a wide range of sequential algorithms.
Writing a C compiler for the register-based, indexed-addressing, single-ALU machines that most microprocessors became—in their efforts to mimic the PDP-11 to greater or lesser extent—was not a great intellectual exercise. It was just work. But expressing an algorithm in C pretty much requires that the algorithm have been conceived to execute on such a machine in the first place. We don’t recognize this because we have become so used to C that we have forgotten that the domain of algorithms is actually much broader than that.
Conversely, getting a C program to execute efficiently on anything that doesn’t look very like a PDP-11 is an exercise in futility. The programming language has already eliminated much of the information we would need to efficiently use a memory-to-memory architecture, say, or a list processor, or—more to the point these days—a multiprocessing cluster. About all we can do in the latter case is ignore the code and go looking for data parallelism.
My point isn’t to poke fun at C, but to draw a parallel. The same distinction exists in hardware description languages. Verilog and VHDL are hardware description languages—but descriptions of a particular set of hardware. They have virtually no way of describing an algorithm except as an implementation in these particular structures. Start with a system of linear differential equations or a collection of matrix algebra, and there is no reasonable way to describe them. You can only—after huge leaps of domain-constraining assumptions—describe datapaths that might implement such algorithms.
So what? Today, just as the programming folks are running into a brick wall trying to parallelize C programs, hardware architects are running into a brick wall trying to capture design specifications and reduce them to synthesizable code. We can do the job just fine if the algorithm happens to be an instance of something RTL code naturally describes—that is, a data path or a synchronous state machine. Otherwise, we are in for a difficult, manual translation process with no guarantee of a positive result.
And just as many programmers tend to think of algorithms in terms of C programs, many architects and designers tend to think of algorithms in terms of a sequence of synchronous registers separated by clouds of asynchronous logic. We’ve forgotten—if we ever knew—that such structures are one set of constructs that was once particularly useful to the computer industry, not a general description of the class of all algorithms. And that is severely hampering our attempts to elevate design to a level of abstraction above RTL. The problem is too hard because the implementation language is too specific, or perhaps because it is specific to the wrong constructs. It’s an interesting view of the issue.
nikhil commented:
Rodney commented:
For example, a Sudoku puzzle solver written in Python (a slow interpretive language) is relatively easy to write using sets and lists. Doing the same thing in C++ doesn''t alter the set manipulations in algorithms, but it does require a comparatively slow process of manually creating the required set and list objects.
Testing a RADAR processing algorithm in MATLAB/Octave using the native matrix operations facilitates implementing the mathematically derived functions, but practical implementation is done in languages such as C/C++ or Verilog/VHDL that are slower to code but ultimately provide superior system throughput.
What can make a difference is the target processor. Algorithms designed for a vector processor such as a Cray can be substantially different than algorithms designed for serial processors. An algorithm designed for an FPGA with scads of MACs can be substantially different, and 100 times faster, than an algorithm designed for a serial processor.
nikhil commented:
ron commented:
Basic Personality commented:
A Problematic Language commented:
Dick Selwood commented:
ron commented:
Policebox commented:
DaveW commented:
