5
$\begingroup$

I have joined the hardware industry in the capacity of a formal verification engineer although my background is more of a theoretical logician.

I have this open question for the theoretical computer scientists, to identify the resources that get utilised in trying to convert an algorithm to some hardware implementation of the said algorithm. This is analogous to the flavour of identifying complexity resources to an algorithm. I want the resources that would be needed to manoeuvred to get the algorithmic implementation to an algorithm like say matrix multiplication ( which is used a lot in modern processors ).

In my limited experience it seems access to specific fundamental resources like an adder circuit or a multiplier circuit is where the bottlenecks get to, and the verilog implementation of these algorithms deal with timing accesses to these resources through staging them across distinguishable logical segments. Thus in particular at least few resources that I think of in the context of my question would be -> sub-routine oracles like the adder, multiplier circuits, clock, also perhaps physical size of the die to be designed.

I understand this might be more of an electronics engineering question, but I am trying to bridge two different disciplines and am hoping there would be some experts with this understanding having experienced both aspects. Also it seems the hardware industry is very closed as opposed to the community of theorists or even software engineers. I feel a lacunae in my understanding that I am not able to fully articulate. I am hoping a discussion will clarify the nuances. Resources that point to step by step conversion from a matrix/floating point multiplication pseudo-code to converting it to hardware implementation of it would be very welcome. Thanks.

$\endgroup$

1 Answer 1

6
$\begingroup$

I was in the same position a couple of years ago, when I took the plunge from software and PL theory to hardware verification. I too looked here for help (see this question)

Unfortunately, there is no easy answer to this question. And the existing answers (like systolic arrays, stream processor architectures, dataflow programming languages, etc etc) probably won't make much sense to you at this point, because they are written up for an expert computer architecture audience.

Another problem is that, as you also already realised, the hardware world is extremely secretive. Almost nothing of interest is easily accessible. Anything you find in the open literature (excluding patents) is > 20 years old. To give but one example: Nvidia does not publish the assembly language of their GPUs.

What I wish I had done, and that is what I recommend to you to do first and before anything else, is to learn Verilog (the lingua franca in hardware) to a high standard (or a similar and more modern language like Chisel). "High standard" means: you complete a small processor core. That will be only a few hundred lines of Verilog / Chisel. But you must understand every line of your own code. There are plenty of (ok-ish) books, text, courses, YouTube videos on this subject. Once you understand how this world works, your question becomes straightforward to answer, and you will understand the existing answers.


In hardware design you are solving a multi-objective optimisation problem:

  • Minimise the number of transistors used (in software that is reasonably close to program size, and, obviously, to circuit complexity)
  • Minimise the power consumption (this has no real correspondence to stuff we quantify in software)
  • Maximise the achievable clock-speed. This is related to the length of the longest signal path, and is related to depth of circuits in circuit complexity). Speed of light restrictions play a major role in modern processor designs (IIRC electrons travel at 1/3 of the speed of light in silicon, you can calculate how far an electron can travel in a single clock cycle in a 4 Ghz processor).

Those objectives force hard trade-offs.


Languages like Verilog and Chisel are synchronous and parallel. To a good approximation, sequential behaviour does not exist in nature (and hence in processors), you can just create the illusion of sequential behaviour. Clocks and synchrony are there in parts to make processors more easy to design and understand.


Regarding verification: it's sort of the same as software verification, but

  • This is taken very seriously, because hardware is not agile: if a bug is detected only after tape-out, the company probably goes bankrupt. Certainly the verification engineer in charge of the part of the circuit that was buggy gets fired. The cost of verification is rigorously quantified, at least in terms of budget for verification engineers and their tooling.

  • Verification happens on simulated models of the actual processor. The simulated models are orders of magnitude slower than a real processor. That's why ultra-wasteful brute forcing like AFL don't scale and you need to be more clever.

$\endgroup$
7
  • $\begingroup$ Does Verilog have some advantage compared with VHDL? $\endgroup$
    – Lamine
    Commented Oct 20 at 16:09
  • 2
    $\begingroup$ @Lamine Only tooling. Most professional tooling are for (some vendor specific subset of) Verilog. In this world tooling is everything. If you verify a core that's given by 80M lines of code, you need serious tooling. Chances are that that tool prefers Verilog. As a language, Verilog is terrible. Chisel is much nicer, in my opinion, but tools are lacking $\endgroup$ Commented Oct 20 at 16:25
  • 1
    $\begingroup$ @Ramit The tooling ecosystem for hardware design and verification is huge. Compilation to netlist is one dimension. Simulation another. E.g. stuff like Jasper Gold from Cadence. Processor verification is very costly. $\endgroup$ Commented Oct 21 at 10:53
  • 1
    $\begingroup$ Going from a high-level description of a processor, say in Verilog, to, ultimately, transistors, is really a multi-level compilation step! Many of those steps follow techniques that you see in compilers that you know from software. One of the interesting facts about this is that semantics of the very bottom level is, ultimately quantum mechanics, and not fully accessible. $\endgroup$ Commented Oct 21 at 11:01
  • 2
    $\begingroup$ There are various courses, like https://www.cerc.utexas.edu/~jaa/verification/ on hardware verification online. But, as I suggested, I find them easier to understand if one already has a good grasp of how processors work and are specified in RTL languages like Verilog. $\endgroup$ Commented Oct 21 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.