<p>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 <a href="https://cstheory.stackexchange.com/questions/46610/improving-boolean-circuits-w-r-t-a-probability-distribution">this question</a>)</p>
<p>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.</p>
<p>Another problem is that, as you also already realised, the hardware world is <em>extremely secretive</em>. Almost nothing of interest is easily accessible. Anything you find in the open literature (excluding patents) is &gt; 20 years old. To give but one example: Nvidia does not publish the assembly language of their GPUs.</p>
<p>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 <em>lingua franca</em> in hardware) to a high standard (or a similar and more modern language like Chisel). &quot;High standard&quot; 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.</p>
<hr />
<p>In hardware design you are solving a multi-objective optimisation problem:</p>
<ul>
<li>Minimise the number of transistors used (in software that is reasonably close to program size, and, obviously, to circuit complexity)</li>
<li>Minimise the power consumption (this has no real correspondence to stuff we quantify in software)</li>
<li>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).</li>
</ul>
<p>Those objectives force hard trade-offs.</p>
<hr />
<p>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.</p>
<hr />
<p>Regarding verification: it's sort of the same as software verification, but</p>
<ul>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
</ul>

CC BY-SA 4.0
2024-10-20T16:09:45.303Z
Does Verilog have some advantage compared with VHDL?
Lamine
CC BY-SA 4.0
2024-10-20T16:25:25.953Z
@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
Martin Berger
CC BY-SA 4.0
2024-10-21T10:12:58.963Z
@MartinBerger https://www.reddit.com/r/FPGA/comments/onyb59/tools_for_verilog/ by tooling are you referring to how verilog program gets converted to netlist and the program behaviour can be simulated. Is this a correct analogy - the said conversion is akin to how a program is converted to assembly/machine code?
Ramit
CC BY-SA 4.0
2024-10-21T10:53:30.177Z
@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](https://www.cadence.com/en_US/home/tools/system-design-and-verification/formal-and-static-verification.html). Processor verification is *very* costly.
Martin Berger
CC BY-SA 4.0
2024-10-21T10:57:58.610Z
@MartinBerger thanks Martin for entertaining my naive questions! I need to get familiar with this ecosystem. There is a long way to go.
Ramit
CC BY-SA 4.0
2024-10-21T11:01:15.967Z
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.
Martin Berger
CC BY-SA 4.0
2024-10-21T11:04:03.470Z
There are various courses, like [https://www.cerc.utexas.edu/~jaa/verification/](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.
Martin Berger
CC BY-SA 4.0
2024-10-20T15:07:27.080Z
2024-10-20T17:57:29.077Z
2024-10-20T17:57:29.077Z
Martin Berger
<p>I have joined the hardware industry in the capacity of a formal verification engineer although my background is more of a theoretical logician.</p>
<p>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 ).</p>
<p>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 -&gt; <strong>sub-routine oracles</strong> like the adder, multiplier circuits, <strong>clock</strong>, also perhaps <strong>physical size of the die</strong> to be designed.</p>
<p>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 <strong>pseudo-code</strong> to converting it to <strong>hardware implementation</strong> of it would be very welcome. Thanks.</p>

<big-picture><se.software-engineering><ar.hardware-architecture>
Concepts that go into converting an Algorithm to a hardware implementation of it
Ramit
# Concepts that go into converting an Algorithm to a hardware implementation of it

(Asked by: username_0 on 2024-10-20)

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.

**Tags:** big-picture, se.software-engineering, ar.hardware-architecture


---

## 1 answers

### Answer by username_1 on 2024-10-20. Score: 6

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](https://cstheory.stackexchange.com/questions/46610/improving-boolean-circuits-w-r-t-a-probability-distribution))

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.

> **Comments:**
> **username_2**: Does Verilog have some advantage compared with VHDL?  
> **username_1**: @username_2 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  
> **username_0**: @MartinBerger https://www.reddit.com/r/FPGA/comments/onyb59/tools_for_verilog/ by tooling are you referring to how verilog program gets converted to netlist and the program behaviour can be simulated. Is this a correct analogy - the said conversion is akin to how a program is converted to assembly/machine code?  
> **username_1**: @username_0 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](https://www.cadence.com/en_US/home/tools/system-design-and-verification/formal-and-static-verification.html). Processor verification is *very* costly.  
> **username_0**: @MartinBerger thanks Martin for entertaining my naive questions! I need to get familiar with this ecosystem. There is a long way to go.  
> **username_1**: 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.  
> **username_1**: There are various courses, like [https://www.cerc.utexas.edu/~jaa/verification/](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.  

---

