Evaluation Order and Parallelism

The change between ripple and carry-look-ahead is the evaluation order. By using more flexible evaluation order, we can try to parallelize.

The easiest way may be to give control over the evaluation order into the run-time environment. In automated test runs, the evaluation order can be changed to ferret out common coding errors. Production runs would change evaluation order to extract the most speed out of the system.

Carry-lookahead Addition

Carry look ahead addition optimizes the addition circuits. Without carry look ahead addition, ripple adders would be used. Ripple adders take three bits of input a_i, b_i and c_i.

The first two are the addends and the third is the carry bit from the prior adder. The result bit (r_i) is a_i xor b_i xor c_i. The xor operation can be decomposed to x and not y or y and not x. The carry bit (c_i+1) is a_i and b_i or b_i and c_i or c_i and a_i. From the software developer point of view, these subscripts make it easy to "code" this as a for-loop.

The key here is that the ripple adder requires that the carry bit be rippled through the adder. This takes time for the signal to go through all the gates.

The carry look ahead adder uses boolean algebra to create all the carry bits in parallel by using more gates. This allows you to xor a, b, and c together. To generate the carry bits, each bit position can be show to generate a carry bit or propagate a carry bit. The carry bit for any position is c_i = g_i-1 + p_i-1*c_i-1. You can expand this recurrence into an expression that you can then evaluate in roughly O(log n) since logic gates can take two inputs and have the associative and commutative property.

Parallelism here requires significant gate resources. The simple ripple adder has a straight forward software implementation. The carry look ahead adder doesn't. The latter is faster. Is it worth the software complexity if we always had to code things like the carry look ahead adder?

Eager vs. Lazy Evaulation

Programming languages can be categorized into eager or lazy evaluation. Most languages are in the eager evaluation.

But we can do somethings in C++ and Java to create lazy evaluation by constructing objects that store parameters for later evaluation.

class BigInteger;
class IntermediateSum {
  const BigInteger &a, &b;
};

class BigInteger {
  IntermediateSum operator+(const BigInteger &b) { 
    return new Intermediate(*this, b); 
  }
  BigInteger& operator=(const IntermediateSum &i) {
    /* now add */
  }
};

The sum isn't evaluated until it hits the assignment. This lazy evaluation shows precisely when you can start evaluation and when you really need it.

Expressing Parallelism

Knuth's matrix multiplier doesn't express parallelism itself. It relies on the large register sizes and the hardware's parallel sets of gates to do the hard work. Software developers can't depend on the hardware development to have parallel implementations for their particular application.

Moreover, the gap between typical software code and parallel hardware is large. Languages for hardware design like VHDL and ladder diagrams won't cut it for the next web site. These languages help set down the millions transistors which all contribute their piece of binary logic. They're running their electrons all the time, unlike software programs which go line-by-line, instrucion-by-instruction, or opcode-by-opcode.

The efforts from the CPU designers have kept this problem at bay for a long while. Things like caches, speculative execution, branch prediction have all helped software keep the illusion of a single instruction stream. Development of reduced instruction set computers (RISC) forced some of the problems of branches onto the assembler.

But now, the hardware parts can't continue to increase clock speeds. They can only deliver the basic Moore's law of increasing the number of transistors on a chip.

Broad Word Computing

Knuth presents bit-flipping tricks as broad word computing. For me, bit-flipping is something that languages try to hide from programmers. But Knuth begins to code single-instruction-multiple-data (SIMD) using bitwise operators. He shows a few lines which will average two vectors, x and y, each with 8, 8-bit integers (Video 37m45s).

l = 0x0101010101010101;

t = ((x^y) & ~l) >> 1;
z = (x&y) + t;

Then, Knuth used bitwise operators to multiply a 4x4 binary matrix. He had to use the full 64-bits to do it. Larger matricies require even wider words. An 8x8 matrix would require 8^3-bit registers. Yet, the number of instructions remain the same!

The computational effort is being moved from the software instructions into additional memory space and circuitry.

Welcome

Commonly used programming languages aren't quite up to the task of writing easily parallelizable software. As a programmer, I don't want to spend time breaking up tasks into threads and processes, debugging the inevitable locking errors, and then redesigning when there's an order of magnitude more processing cores available.

My thoughts on parallel computing have ranged from how to tweak programming languages, field-programmable gate arrays (FPGAs), general purpose graphics processing units (GPGPU), multicore, multithreaded, to Knuth's broad word, formerly platologic, computing (Look under Computer Musings for a video lecture at Stanford).

General Purpose Graphics Processing Unit (GPGPU)

Both ATI and nVidia have started opening their graphics processing units (GPUs) up to general purpose computation. The pipeline of pixel and vertex shaders have lots of transistors designed for 32-bit float matrix multiplication. In graphics, it's easy to parallelize and multiple computing units were etched into silicon to make the GPU faster.

ATI's effort, Close-to-Metal, is used by Folding@Home to be able to accelerate certain computations. I wanted to take a closer look, but their SourceForge project is temporarily shutdown.

Compute Unified Device Architecture (CUDA) is nVidia's project. I took a quick look at their documentation and didn't focus too heavily on the implementation details.

In assorted online discussions, the key limitation to the GPGPU processing is the bandwidth between main memory and the GPU. Without the ability to execute many branches or adequate integer processing, the data and code that gets stuck in GPU memory can't easily get out.

As a programmer, I'll optimize the data flow between the CPU and GPU for only things that I think might make payoff. I'll be spending the time redesigning those parts of the program that benefit from the GPU's speed at processing 32-bit floats.

Wouldn't it just be better if some lower-level software could help? Maybe the compiler or virtual machine, like Java or VMWare, could help without forcing me to redesign my program.