## Friday, August 28, 2009

### Synergy among processors

A simple question. Jack is a cobbler, working in DumbCobbler Inc. He stitches on an average 20 shoes per day. DumbCobbler Inc has got some new orders and so they hire 9 new cobblers to work with Jack. Do the math. How much shoe can DumbCobbler make in a day? If the answer is 200,...

Wrong. Actually they are making 225 shoes a day. Where does the extra 25 shoes come from, if all the cobblers are equally qualified and in isolation they can make only 20 shoes per day. The extra 25 is the result of synergy. So as a team of talented people work together, some kind of a team thing develops among them and even without much process improvement they make more in a given time. Where there is synergy, whole is greater than the mathematical sum of the parts.

Now let me change the problem a little bit. I have a processor, say MIPS 32 bit processor. I have an image processing problem and the processor takes 6 seconds to run the algorithm that solves the problem. Now I am putting two processors, both MIPS 32-bit, in a multicore environment. The same algorithm has to be run. How much time would it take now? If the answer is 3 seconds, ...

Wrong again. The answer probably would be somewhere between 4-5 seconds. It depends on two factors. One is whether the algorithm can be made parallel. Some algorithms are inherently sequential. For example, adding numbers in an array (am I sure?). The second factor is how skillful the programmer is in recognizing the parallelism present in the algorithm. For example, adding numbers in an array can be done in parallel, since you can divide and conquer. But even in a completely parallel implementation the lower bound remain intact. That is, if one processor takes up 6 units of time, two processors can at the best take 3 units of time to finish the job. A little more perhaps for synchronization, but not any less, unlike humans.

So will the processors ever get synergy? If we assume processors to be dumb compared to humans, would robots with AI have synergy? For this I have to be explained how synergy works in terms of a cerebral model. Has any psychologist tried it? No idea; I don't follow medical discoveries.

But here is an interesting fact. In IBM's Cell multicore processor architecture, there are a set of RISC processors called SPE, which stands for Synergistic Processing Element. They are SIMD processor suited for vector processing (as with any SIMD processor). It does not do out of order execution, because it has 128 registers. Register renaming can be done liberally which obviates OOO. Instead of cache, SPE uses something called "Local store". Just like cache it is inside the chip. SPEs act together when a set of SPEs are chained together for stream processing. This property is of great use in a GPU which requires fast video processing. More on Cell architecture some other time.

Probably since these processors are chained together, they have that prefix, "Synergistic". It still does not produce the effect of whole being larger than the sum of the parts. That's something that we have to wait for a long time.

#### 2 comments:

1. Actually, I've already seen synergy in an embedded system we were using. We have two tasks that handle large data sets and constantly exchange data with each other. They were written to be segregated and communicate over shared memory, but can be mapped to the same physical CPU. However, when we switched from a single CPU to a multi-CPU version, with the two tasks now on separate processsors, we observed a speed-up of more than double. Why? In a word, cache. With a single CPU constantly switching between the two tasks, each task was flushing the other one's cached data, forcing the CPU to reload from main memory. With 2 CPUs, each task had a separate CPU cache so they were able to really fly. This speed-up is much more than the overhead of interprocessor communication.

2. The thing you just explained above - is that synergy among processors? Lets get back to the human example. Consider that a person is shaping a piece of wood in a lathe and tailoring at the same time. First he would shape the wood for, say 1 hour. Then he stops, remove the lathe machine from the table and places a sewing machine. This takes 15 minutes. Then he starts tailoring for the next one hour and decides to go back to lathe.

Now if I employ two people and two tables (an expense in resource), then I can save that 15 minutes in terms of productivity. But that's not my synergy. That's just a process improvement. This analogy is similar to the N CPUs sharing a cache and performing N tasks in parallel.
Synergy is much more than that.