Martin Kochanski’s web site / Encryption / The FAP4 chip

 

Look-ahead carry and other improvements

Remember that the big problem in addition comes when you are doing a sum like this:

  2 1 0 5 8 6 3 4 7 2 2 9 7 7 1 6
+ 4 8 9 4 1 3 6 5 2 7 7 0 2 2 8 5
= 6 9 9 9 9 9 9 9 9 9 9 9 9 9 9 11
  6 9 9 9 9 9 9 9 9 9 9 9 9 9 10 1
  6 9 9 9 9 9 9 9 9 9 9 9 9 10 0 1
  6 9 9 9 9 9 9 9 9 9 9 9 10 0 0 1
  6 9 9 9 9 9 9 9 9 9 9 10 0 0 0 1
  6 9 9 9 9 9 9 9 9 9 10 0 0 0 0 1
  6 9 9 9 9 9 9 9 9 10 0 0 0 0 0 1
  6 9 9 9 9 9 9 9 10 0 0 0 0 0 0 1
  6 9 9 9 9 9 9 10 0 0 0 0 0 0 0 1
  6 9 9 9 9 9 10 0 0 0 0 0 0 0 0 1
  6 9 9 9 9 10 0 0 0 0 0 0 0 0 0 1
  6 9 9 9 10 0 0 0 0 0 0 0 0 0 0 1
  6 9 9 10 0 0 0 0 0 0 0 0 0 0 0 1
  6 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1
  6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 1
  7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

where I've used the red background to show an adder that's emitting a carry.  That carry digit has to propagate all the way from the rightmost adder to the leftmost one before we can get the true result, and having to allow for this is what slows everything down.

One option: knowing how long to wait

Most of the time, carries don't propagate very far.  The sum that I've shown you above is exceptional and it occurs, on average, only once every 1,000 million million times that you do an addition. 

Because most chips have a clock that ticks at a fixed rate (you start a calculation, wait long enough for it to be completed, then the clock ticks and you store the result and start the next calculation), we have to make the clock slow enough for even the rarest case and in practice most of the time between clock ticks is spent waiting for something that probably won't happen.

It is possible to redesign the chip get the chip so that it reports when a calculation is complete.  In essence, we arrange things so that each carry signal is no longer "Yes" or "No", but "Yes", "No", or "Don't know", with 9 (the awkward case) reporting "Don't know" until the adder has received "Yes" or "No" from its right-hand neighbour.  If you then have a circuit that checks if any of the adders is saying "Don't know", then you have a simple strategy: wait until there is no "Don't know", and then let the clock tick.  In the worst case (the 1 in 1,000,000,000,000,000 chance) this won't be any slower than the old method, but almost always it will be much faster.

This works.  The main trouble is that this revision makes all the circuitry much more complex and the irregular timing makes control more difficult.  As far as I was concerned, the increased complexity ruled out further investigation: chip space was short enough as it was.

Look-ahead carry

Look-ahead carry depends on the fact that a carry can only propagate through a sequence of adders if the sum of the digits in every one of those adders is 9.

First, we divide the adders into blocks of four.  This is a purely conceptual division and nothing really changes.  For 300 digits, this means 75 blocks.

Next, we look at a typical block somewhere in the middle and consider the circumstances under which it will pass a carry to the block on its left.  There are two.  Either the carry has originated within the block itself, or the carry came in from the right and has been passed through all the adders in the block becuse every one of them had a sum of 9.

To each block, we add a supervisor circuit.  Its job is to check whether every adder in the block has a sum of 9.  If it does, then the supervisor watches out for a carry coming in from the right.  If a carry does arrive, the supervisor instantly passes it out to the block on the left.

What does this achieve?  Its effect is that if carries have to be propagated over a long distance, they will go from supervisor to supervisor rather than trickling through every single adder.  Since each supervisor is responsible for four adders, the result is that the signal travels four times as fast.

Let's look again at the example.  I'll give the adders names from A to P so we can follow them more easily.

  A B C D E F G H I J K L M N O P
  2 1 0 5 8 6 3 4 7 2 2 9 7 7 1 6
+ 4 8 9 4 1 3 6 5 2 7 7 0 2 2 8 5
= 6 9 9 9 9 9 9 9 9 9 9 9 9 9 9 11
 
  • P is passing a carry to O.  The supervisors EFGH and IJKL have noticed that their adders have all 9s, so they are both on the alert.
  6 9 9 9 9 9 9 9 9 9 9 9 9 9 10 1
 
  • O has received the carry from P and is passing a carry to N as a result.
  6 9 9 9 9 9 9 9 9 9 9 9 9 10 0 1
 
  • N has received the carry from O and is passing a carry to M as a result.
  6 9 9 9 9 9 9 9 9 9 9 9 10 0 0 1
 
  • M has received the carry from N and is passing a carry to L and to the supervisor IJKL.
  6 9 9 9 9 9 9 9 9 9 9 10 0 0 0 1
 
  • L has received the carry from M and is passing a carry to K as a result.  IJKL has also seen this carry and is passing a carry to H and to EFGH.
  6 9 9 9 9 9 9 10 9 9 10 0 0 0 0 1
 
  • K has received the carry from L and is passing a carry to J as a result.  H has received the carry from IJKL and is passing a carry to G.  EFGH has received the carry from IJKL and is passing a carry to D.
  6 9 9 10 9 9 10 0 9 10 0 0 0 0 0 1
 
  • J has received the carry from K and is passing a carry to I as a result.  G has received the carry from H and is passing a carry to F.  D has received the carry from EFGH and is passing a carry to C.
  6 9 10 0 9 10 0 0 10 0 0 0 0 0 0 1
 
  • I has received the carry from J and is passing a carry to H and to EFGH, but this has no additional effect because IJKL has already done it some time ago.  F has received the carry from G and is passing a carry to E.  C has received the carry from D and is passing a carry to B.
  6 10 0 0 10 0 0 0 0 0 0 0 0 0 0 1
 
  • E has received the carry from F and is passing a carry to D, but this has no additional effect because EFGH has already done it some time ago.  B has received the carry from C and is passing a carry to A.
  7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 
  • A has received the carry from B.

If we define the time taken for an adder to pass on a carry to be one unit, then the look-ahead carry has meant that the worst-case addition can be completed in 10 time units instead of 16.

The benefit is more pronounced with larger numbers.  If we look at our 300-adder problem, and incorporate a team of 75 supervisor circuits each of which watches a block of four adders, the worst-case addition is improved from 300 time units to 81.

We can go further, because we now have a structure of 75 supervisors that have to pass carries between them.  Let's add a new level of supervision, 19 super-supervisors watching (mostly) four supervisors each.  That reduces the 81 to 31.  And those super-supervisors can be watched in their turn, by five higher-level ones, which cuts the amount of delay to 23 time units: not bad when you compare it to the original 300.

There are many choices that can be made about how many adders each supervisor should handle and how many layers of supervision there should be, and the best answer depends strongly on how many adders are involved and the technicalities of exactly how many nanoseconds it takes a signal to pass through a particular circuit.  As a rough guide, it should be possible to reduce the delay in a 1024-bit adder (remember, chips think in bits) from 1024 time units to 30 or so.

This is good but it still makes addition a lot slower than it would be if we didn't need to handle carries at all.