The depth of a circuit is the maximal length of a path from an input gate to the output gate of the circuit [Reference]

Question: What is the relation between the depth of a circuit and hardware implementation of the circuit. In fact, I want to ask this question, why the low depth of a circuit results in the circuit has a suitable hardware implementation?

Thanks for all suggestions

  • 1
    $\begingroup$ Depth corresponds to time. $\endgroup$ – Yuval Filmus Jan 8 '19 at 6:21
  • $\begingroup$ @YuvalFilmus Is it possible to ask you to introduce papers or books about relation between depth and hardware implementation. In other words, I need the reference of this claim "the lower depth the faster operation"? Thanks $\endgroup$ – Amin235 Jan 8 '19 at 7:06
  • $\begingroup$ I’m not aware of any, but it’s common sense. $\endgroup$ – Yuval Filmus Jan 8 '19 at 7:08

In the zeroth order sense, it is correct that the logic depth and the time to execute the logic would be the same. There are nuances to this because you need to do something with the result.

What logic is a medium to do work. In the simplest sense, you have a bounded function with inputs and outputs:

enter image description here

In most actual systems, you need a way to hold the data, which is why we have latches:

enter image description here

and with the latch, we introduce the clock. I will now give you two examples of where logical depth, in a system context, is not representative of speed.

The first assumption that made is "0"s and "1"s are things. Digital is a special case of analog; however, I personally never run anything at a "1" because it is inefficient for power. After you are above threshold, you lose transistor gain. If you are trying to have power performance, you might not make the same choices as for speed performance. You are doing the same electrical work at a high total cost.

The second assumption is that everything is clocked. In a system context, I often add logic to make things go faster. Asynchronous systems give you the average speed as a delay, instead of the worst case delay as a synchronous, clocked system.

Another assumption is that logic doesn't have physical space. Wires are costly even though that they do not add to calculation value. A good example of this is the S-Box used in AES. If you look at the "logic", I have often seen hardware implementations that use a lookup table. This is because it's easy. If you look at the gate depth alone, without the wires, it also would look to be fast. When I make the AES S-Box, the circuit implementation looks like:

enter image description here

This circuit has a much larger depth than the lookup table; however, it requires, less power, takes up less area, and is faster than the lookup table implementation even though the logic depth is deeper.

| cite | improve this answer | |
  • $\begingroup$ I appreciate you taking the time to answer my questions. $\endgroup$ – Amin235 Jan 8 '19 at 11:57
  • 1
    $\begingroup$ @Amin235 Just keep in mind that in a system context, things are hard. Hardware is hard. $\endgroup$ – b degnan Jan 8 '19 at 15:18
  • $\begingroup$ Thanks for your hint Prof.Degnan. I want to ask my question clearly. In fact, my question is related to proposing an efficient MDS matrix for diffusion layer of AES. Consider two Figures 8 and 10 in this paper. The implementation cost of Fig.8 is 67 XOR and its depth is 6. Moreover, the implementation cost of Fig.10 is 68 XOR and its depth is 5. Now, my question is that for you as a computer science researcher, which matrix is efficient for diffusion layer of a block cipher, fig.8 or Fig.10? (I am a math student in coding theory). $\endgroup$ – Amin235 Jan 8 '19 at 16:35
  • 1
    $\begingroup$ @Amin235 I'm not a CS but a semiconductor physicist. I would not say either of those are good implementations, and I find those depths to be meaningless. I would generate 8 over 10. The layout would be smaller and therefore faster. 10 has some long wires. $\endgroup$ – b degnan Jan 9 '19 at 0:38
  • $\begingroup$ OK, I got it. Thanks for your useful comment. $\endgroup$ – Amin235 Jan 9 '19 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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