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.

Intel x86 Processors – CISC or RISC? Or both??

The argument between CISC architecture and RISC architecture is longstanding. For compiler designers, RISC is a little burden since the same C code will translate to nearly five times more lines of RISC assembly code compared to x86 assembly code. But from pure academic point of view, it is easy to see that RISC wins the argument because of several of its advantages. RISC instruction set is very small, for which it is easy to optimize the hardware. Simple instructions running in a single clock cycle is a typical characteristic of RISC that permits aggressive pipelined parallelism. RISC invests more area on registers (using a technique called register windowing), allowing easy out-of-order execution. OOO and pipelining are possible in CISC, but a little clumsy.

One reason that RISC cannot win despite all these advantages is Intel. Microsoft too is one of the major reasons because during the PC revolution, Win 95 had no support for RISC processors. But Intel with its CISC based x86 based architecture blocked all the avenues in general purpose computing for RISC processors. RISC has a good presence in embedded processing however, because of its low power, high real-time, small area advantages.

Two years ago I tried to investigate why Intel did not change its x86 core to a RISC. The findings were astounding, but then I did not have time to write it down in a blog like this. Better late than never. After the success with CISC based CPUs, in 1990 Intel entered the RISC zone with the introduction of i960. The i960 architecture however mainly targeted the embedded systems domain and not the general purpose computer understandably due to the lack of software support.

In general computing domain, Intel Pentium employed two staged pipeline for its IA-32 instructions. The presence of variable length instructions obligated an inherent sequential execution because every execution cycle involved identifying the length of the instruction. As a result, new instruction can begin anywhere with the set of instructions that the processor fetches. As the world was moving towards parallel programming, the only advantage that CISC enjoyed was the software support which might die down soon.

Sometimes when you think that you know where things are heading, there will be a ground breaking invention that would change the entire scenario. One such seminal invental in the form of the introduction of high performance substrate (HPS) by the famous microarchitecture guru, Yale Patt. Although I am tempted to explain HPS in detail, I would rather consider it to be out of the scope of this blogpost. A very simple (not necessarily accurate) description would be that Patt succeeded in converting the CISC instruction to multiple RISC-like instructions or micro-ops.

Intel demonstrated its fast finger by implementing this in its P6 architecture. As any successful, innovative company, Intel is always good at adapting to the new wave. It did it by jumping from its memory business to microprocessor back in eighties and now it did it again by using HPS. Intel’s first IA-32-to-micro-op decoder featured in Pentium Pro. P6 architecture contained three parallel decoders to simultaneously decode the CISC instructions to micro-ops resulting in a deeply pipelined execution (see figure). Sometimes this instruction decoding hardware can become extremely complex. But as the feature size reduced at very fast rate, Intel did not face any significant performance issue with this approach.

Now we are into the post-RISC era, where processors have the advantages of both RISC and CISC architecture. The gap between RISC and CISC has blurred significantly, thanks to the scale of integration possible today and the increased importance of parallelism. Trying to jot down the difference between the two is no longer relevant. Intel’s Pentium Core 2 Duo processor can execute more than one CISC instruction per clock cycle due to increased processing speed. This speed advantage would enable CISC instructions to be pipelined. On the other hand, RISC instructions are also becoming complex (CISC-like) to take advantage of increased processing speed. RISC processors also use complicated hardware for superscalar execution. So at present, classifying a processor as RISC or CISC is almost impossible, because their instructions sets all look similar.

Intel remained in the CISC even when the whole world went towards RISC and it enjoyed the advantage of software support. When the situation started favoring RISC in the advent of parallel processing, Intel used micro-op convertors to exploit the pipelining advantages of RISC. The current Intel processors have a highly advanced micro-op generator and an intricate hardware to execute complex instructions in a single cycle – a powerful CISC-RISC combination.

Connection Machines – Prelude to Parallel Processing

The computer architecture entered into a new phase with the stored program concept and programmable and general purpose computing architecture. The credit for this development goes to John Von Neumann, Grace Hopper, and Howard Aiken. Later it was relatively easy to build microprocessors and computers like ENIAC, since the general computing architecture was well established.

However there was a problem with this primordial architecture. Unlike human intelligence, it was massively relying on a single powerful processor that operated on the stored program in a sequential order. The first computer to depart from this view and behave more similar to human brain was Connection Machine(CM).

In early eighties, Danny Hillis a graduate student in MIT Artificial Intelligence Lab designed a highly parallel supercomputer that incorporated 65,536 processors. This design was commercially manufactured by Thinking Machines Corporation(TMC) created by Danny Hillis under the name CM-1. Thousands of processors which formed a part of CM-1 were extremely simple one bit processor connected together in a complex 20-dimensional hypercube. The routing mechanism between several processors in CM-1 was designed by Nobel Laureate Richard Feynman himself. In 1985, CM-1 was a dream SIMD machine for labs working on artificial intelligence(AI). But it had some practical problems. First it was too expensive a machinery to be purchased by budding AI labs. Second it did not have a FORTRAN compiler, which was the famous programming language among scientists at that time. Third it did not have floating point processing mechanism, a must for scientific analysis. So CM-1, although was a parallel processing marvel, looked more immature to face the market. Realizing the mistakes done in the design of CM-1, Thinking Machine released CM-2 which had a floating point processor and FORTRAN compiler. But still it did not fly. Evidently Danny Hillis was making a machine for future that present had no use with.

In early nineties, Thinking Machine introduced CM-5, which featured in the control station of Steven Speilburg’s Jurassic Park. It is considered to be not only a technological marvel, but also a totally sexy supercomputer (see figure). Instead of simple processors, CM-5 had a cluster of powerful SPARC processors. They also came out of the hypercube concept and built their data network as a binary fat tree. CM-5 is a synchronized MIMD machine combined with some best aspects of SIMD. The system can support up to 16,384 SPARC processors. The processing nodes and data networks interacted through 1-micron standard cell CMOS network interfaces with clock synchronization. The raw bandwidth for each processing node was 40 MBPS. But in a fat tree as it goes up the level, the cumulative bandwidth may reach up to several GBPS (if all these remind you of Beowulf, you are not alone!). TMC guaranteed that CM-5 was completely free of fetch-deadlock problem that occurs between multiple processors (using this).

Although it looks like a great architecture, from pure technical standpoint it is evident that TMC has toned down its idea of a complete parallel machine, simply because in eighties it did not sell partly due to the lack of market readiness and partly due to some blows in design. Secondly the failure of earlier CM series took a toll on TMC’s strategy. When CM-5 was introduced, the future of the company was dependent on that supercomputer sale. Los Alamos National Laboratory bought one. Jurassic Park set bought one. I cannot think of any other major customer. If CM-5 had survived, it would have had to fight with the likes of Intel Paragon, and Beowulf cluster for market space.

After the cold war, DARPA has cut down its funding on high performance computing which fell as a final blow on Thinking Machines. One fine morning in 1994, TMC filed Chapter 11 bankruptcy protection. The Inc. gives an alternative explanation for the failure of Thinking Machine. It is a good insight, but I cannot buy in its opinion about Danny Hillis. Perhaps The Inc. should restrict itself to its primary aim of advising budding entrepreneurs and refrain from measuring scientific minds. Nobody can deny that Danny Hillis was a genius, but the problem was that he was an out of the world freak who could not become a good businessman. Currently he is working on an ambitious project to build a monumental, mechanical clock that would run for multi-millennium.

The way that Thinking Machine took, was certainly not the way to build a successful enterprise. But the initial architecture that they introduced in early eighties was truly a stroke of a genius that every computer architect must study and understand.