1
\$\begingroup\$

Disclaimer: So this is obviously a silly question and I want to start by saying I don't want to discuss the financial costs of this, as I'm aware CPU cache is expensive. As this hasn't been made obvious enough, this is PURELY ACADEMIC - NOT FOR IMPLEMENTATION. Think "thought experiment"

I've been wondering if it would be possible to precompute all the work an ALU would do and store the results in a lookup table.

For this specific example, I've been looking at a subset of instructions the ALU is responsible for in a MIPS Architecture which is "AND, OR, add, sub, slt, NOR".

In this architecture, these operations would take 4 bits to encode which we'll call the control, as there are only 6 operations. In addition, we'd have to take two 32 bit values as input and return a 32 bit value as output along with 3 1 bit flags. (Details listed here)

At a really high level, we'd use the 4 bit control, along with the two 32 bit inputs to return the 32 bit result and the 3 1 bit flags. So couldn't each control act as an offset to our cache, and use the input values to index into our lookup? We could even squeeze out some more memory for operations that have the commutative property (1+2 = 2+1)

I'm aware this is goofy question but I was curious if anyone had any insight. Perhaps it could be faster? If not, maybe use less electricity or generate less heat? At the very least it's interesting.

\$\endgroup\$

closed as primarily opinion-based by Eugene Sh., uint128_t, ThreePhaseEel, Voltage Spike, nidhin Feb 23 '17 at 12:12

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Are you talking about a lookup table with a 68 bit address (32 + 32 + 4)? \$\endgroup\$ – Justin Feb 21 '17 at 19:00
  • 2
    \$\begingroup\$ It would make sense for a nybble wide ALU, but 32 wide is a lot of address lines. \$\endgroup\$ – Neil_UK Feb 21 '17 at 19:01
  • 1
    \$\begingroup\$ @MyOtherHead It was simply a thought experiment. \$\endgroup\$ – Greg Hilston Feb 21 '17 at 19:07
  • 2
    \$\begingroup\$ Like Neil says, it's a reasonably common technique when dealing with 4 or 8 bit wide inputs. At 32 bits it becomes infeasible, as shown in the existing answers. \$\endgroup\$ – The Photon Feb 21 '17 at 19:35
  • 1
    \$\begingroup\$ But it wouldn't be better. You're trading off time complexity for space complexity, and you can't just wish away one of them to make your chosen solution "better". \$\endgroup\$ – The Photon Feb 21 '17 at 19:42
9
\$\begingroup\$

A single 32-bit x 32-bit to 32-bit lookup table would require an untenable amount of space:

$$ 2^{32} \times 2^{32} \times 32 = 2^{69} \approx \mathrm{5.9\ quintillion\ bits} $$

This is flatly impossible to build. A single microchip can store perhaps 240 bits (~128 GB); you'd need over 500 million of these to store the full lookup table. (Halving the size by exploiting symmetries like a+b=b+a still leaves the size in the implausible range.)

If you want to consider the implications on heat/power and speed, though:

  • If we generously assume that each of the 500+ million microchips draws 1 mA at 3.3V, you're looking at a total power consumption of roughly 1.8 MW. (Yes, that's megawatts.)

  • If we assume that each of those chips is 2x2 cm and 0.5 cm thick (including the circuit board), and that they require no other support circuitry, the resulting device will be roughly a 10 meter cube. It takes light about 34 nanoseconds to cross 10 meters; even if we assume that it takes no time for one of these chips to look up a result, this would limit the speed of such a device to roughly 292 MHz.

\$\endgroup\$
  • 2
    \$\begingroup\$ The fact that you'd need over 500 million microchips should cover that. Work through the implications yourself. :) \$\endgroup\$ – duskwuff Feb 21 '17 at 19:06
  • 1
    \$\begingroup\$ I'm not sure how else to phrase this, it was purely a question that I wasn't trying to translate into a physical solution. Purely theoretical and academic. I don't understand how I am not making that clear. \$\endgroup\$ – Greg Hilston Feb 21 '17 at 19:09
  • 3
    \$\begingroup\$ You are asking a purely "practical" questions about speed and electrical consumption. Which cannot be answered in terms of existing technology. Putting together such a large-scale system would require novel engineering solutions which will alter any possible answer to these. \$\endgroup\$ – Eugene Sh. Feb 21 '17 at 19:11
  • 1
    \$\begingroup\$ As you ask about heat and power, an ALU is a tiny fraction of a 'microchip', let's say 1/2000th, and you'd need 500 million full microchips to implement the lookup table. I make that around 10^12 more costly in heat, power, area, probably money, and likely no quicker on account of the speed of light for the address lines to traverse this assembly of chips. \$\endgroup\$ – Neil_UK Feb 21 '17 at 19:16
  • 3
    \$\begingroup\$ @GregHilston The choice of register width actually makes a huge difference here, as the size of the lookup table increases exponentially with the register size. It's actually a reasonable question for an 8-bit ALU. \$\endgroup\$ – duskwuff Feb 21 '17 at 19:42
5
\$\begingroup\$

The bottom line is that a lookup table is made up of logic gates, and it always takes fewer gates to implement the kinds of ALU operations you're talking about directly rather than use a lookup table.

So, no matter how much technology advances, it never makes sense to use lookup tables over direct logic using the same technology.

FPGAs are a special case because of how they are used. In the first place, reconfigurability is their most important feature, and secondly, the tiny lookup tables that they use (typically 16×1 to 64×1) are very fast — faster than the interconnect logic and other details that contribute to their configurability.

\$\endgroup\$
  • \$\begingroup\$ I don't agree, a lookup table is mainly MEMORY and not logic gates \$\endgroup\$ – Claudio Avi Chami Feb 22 '17 at 3:56
  • \$\begingroup\$ @ClaudioAviChami: How do you think that memory is implemented at the lowest level? It's basically gates -- lots of them! Even a mask ROM has a large decoder and OR gates to combine the data from different words. \$\endgroup\$ – Dave Tweed Feb 22 '17 at 12:20
0
\$\begingroup\$

At 32-bit level, its not practical. But considerable excitement occurred in 1985, when 5-bit math was proposed for in-memory image processing.

By taking log(pixel_magnitude) and storing that, dynamic-range was good and actual edge-detection should occur.

We never built it. After all, who would want to perform 5-bit math in a memory?

\$\endgroup\$
-1
\$\begingroup\$

To add on the speed, to access the look up table it will take a clock cycle which would make execution fast but a lot of modern architectures like ARM and AVR execute instructions in a single cycle so the the trouble of all those required bits wouldn't gain you much. Additionally to create all the require bits, whether they are implemented as SRAM or DRAM you would ended having to use a pretty small technology node which would result in high leakage current and therefore high power consumption. Again if you were to implement your look up table in flash accessing flash is slow operation compared to what some CPU cores can run again negating the any speed gains

\$\endgroup\$
  • 2
    \$\begingroup\$ The limiting factor of speed is c, not the programming language, but 299792458 m/s. I've guesstimated the volume of the ALU to a whopping 32 000 m^3. A spherical ALU would have a radius of about 65 nanoseconds. The rest of the digital stuff of the computer would fit in the center, but I've completely forgotten about the cooling system, power supplies, bypass capacitors and nuclear reactors. \$\endgroup\$ – Oskar Skog Feb 21 '17 at 19:29

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