Programming Metaphors

Most programming languages use the recipe/script/story metaphor. The computer follows the steps in the recipe to get the desired results.

Parallel programming adds more engineering work after the recipe/story/script is complete. You need to create an assembly line for the recipe. Instead of having one processor work on the steps itself, you need to split up the steps for each factory worker to perform one step. You can separate them with queues or synchronize them on mutexes. As you add or remove workers, you need to redo the assembly line for optimal efficiency.

Defining Cloud Computing

Cloud Computing views the whole group of machines as a single computational machine. It splits up work symmetrically and asymmetrically to the group. Often, cloud computing uses address space to perform computation, e.g. Google's Map-Reduce would use address space to help sort. This leverages the best hardware (routers) to do the information routing. It leaves the hardware optimized for storage (local hard disks).

In Cloud Computing, configuration is significant. You array the machines in a replacable manner. But the arrays are setup for speed, storage, and networking.

This could be a renaming and elaboration on grid computing which views computational cycles as a resource much like the electrical grid. Grid computing sells the grid resources. It doesn't configure the networking. Some grids like Seti@Home have significant network constraints which make it impossible to use for all but the smallest Map-Reduce problems. Cloud computing is free of the constraints of Seti@Home's node's bandwidth limitations.

Variably Long Instruction Word

With Intel pushing thousands of cores in the future, the predominant programming model may be Variably Long Instruction Words. The "instruction" would line up various "cores" together. As you start the functionality, the inputs are probably pretty small. As processing increases, the inputs are expanded to a very long data width. All the processing occurs in parallel and is slowly gathered together into the result.

This is what's used by carry-look-ahead addition if you look at the width of the number of gates used mid-computation.

It's been a month

I've been trying to figure out Montgomery Multiplication on the Via C7 processors. The texts available online haven't been too helpful.

I had quickly whipped up an integration of Via's sample code into openssl. I benchmarked it by running with openssl's s_client and s_server. My initial integration turned out to be slower than just using openssl.

The number of buffer copies to align the data was to blame. During the next half-week, I learned enough about Montgomery multiplication to be confident to try my hand at implementing a more streamlined version. The more streamlined version is faster with a 30% speed up.

I was using the binary method of modular exponentiation while openssl used the fixed window method. Both use Montgomery multiplication. Mine used the hardware one. OpenSSL used its software.

I'd have to spend more time to get my implementation tweaked to remove unnecessary memset(,0,) to clear memory and begin to use the fixed window method.

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.