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.

Multicore Processor Simulator

Back in 2005, I was listening to the recorded voice of Intel President Paul Otellini saying this in Intel Developers Forum. When he described the future direction of Intel, this is what he said:

We are designing all of our future development to multicore designs. We believe this is a key inflection point for the industry.

Followed by the diminishing returns from the Instruction-led Parallelism in a uniprocessor, the world of computer architecture decided that multicore processor and chip multiprocessor is the direction of the future.

I knew the importance of multicore processors even before they became famous in the general purpose computing. Part of my undergraduation research thesis involved implementing digital beamforming in quad-core SHARC processor. Now it is apparent that multicore processors are here to stay and whether you like it or not parallel programming is the future way of computing. Web programs are already running in parallel managed by the web application servers. Embedded systems programming are rapidly moving towards introducing parallelism wherever performance matters. There still are two issues that make parallel programming difficult. One is the availability of debugging tools, especially the rather unique bugs like Heisenbugs. The firms are moving towards developing debuggers to reveal the heisenbugs and ease the programming. Although the multicore developers and compiler designers are coming up with parallel programming debugger extensions to solve this problem, it is clear, present and painful at this stage.

Second issue with multicore processor is the lack of simulators for multicore processors. SimpleScalar is certainly a excellent processor simulator. But simulating a Chip MultiProcessor (CMP) with hundreds of core is still an open problem for the computer architecture community. Recently Monchiero et al of Hewlett-Packard Laboratories have come up with an idea to simulate shared-memory CMP of large size, published in the recent SIGARCH transaction.

The best part of this paper is the simplicity of the underlying idea. The idea is to translate the thread-level parallelism of the software to core-level parallelism in the simulated CMP. First step is to use the existing full system simulator to separate instruction streams belonging to different threads. Then the instructions flow of each thread is mapped to different cores of the targeted CMP. And then the final step is simulating the synchronization between the different cores. The simulator explained in this paper can be used to simulate any multithreaded application in a conventional system simulator and extend the evaluation to any homogenous multicore processor. I believe this framework is going to be used in many CMP-simulators in future.

UPDATED ON 02/02/2010: This might be a viable multicore processor simulator.