| Challenges for multicore programming |

In 1965, Gordon E. Moore, co­founder and chairman emeritus of Intel Corporation made an observation that “the number of transistors placed inexpensively on integrated circuit will double approximately every two years”. This simple observation led to Moore’s Law, which has held true till recent times. Around 2004, single CPU clock speed scale ups hit what is today know as the “power wall”, when further power consumption and clock speed improvements became impossible. The problem at 90nm of silicon was that transistor gates became too thin to prevent current from leaking out into the substrate. None of the new technologies after 2004 has re-enabled anything like the scaling in the 90s. From 2007 to 2011, maximum CPU clock speed (with Turbo Mode enabled) rose from 2.93GHz to 3.9GHz, an increase of 33%. From 1994 to 1998, CPU clock speeds rose by 300%. CPU manufactures hence were forced to shift towards increasing processor count per die. Most processors today have at least 4 cores, while the higher end machines commonly have 16 cores or more. This brought in the era of multicore computing. However, increasing the number of cores does not necessarily mean faster processing. The software written for the multi core computers of today must be able to utilize the additional processing power resident in the extra cores. Today’s software therefore has to be written for multicore computers, and sequential modes of computation in software must be replaced by parallel processing to harness the power of the additional cores. However, most software in the world, excluding specialized cases of high performance computing and ADA, has always been sequential in nature. The sudden influx of multicores meant a complete new paradigm of programming, and while a considerable work has been done in this regard, programming multicores still proves to be a difficult problem.

In order to understand the challenges of creating software for multicore platforms, one must first understand the platform itself. Multicore machines are shared memory systems with uniform memory access time, implying that each execution unit usually has access to the whole system memory. Input output operations and disk access is usually serialized, making disk accesses and general input output operations very expensive in terms of time and synchronization. As the name implies, multicores necessarily have more than one processor, today usually 4 or more processors, on the same die. Therefore any software that can express itself in terms of tasks that can run in parallel on separate cores with minimal synchronization or disk access will yield maximum performance benefit from multicore machines. Whether a software code is expressible in such a form is however dependant on its algorithm and structure, and while some algorithms are inherently suited for parallel programming, many are not. Many algorithms in the domain of image processing require little or no interaction between tasks that process subparts of the image, and such algorithms, usually referred to as embarrassingly parallel algorithms, can be easily expressed as parallel tasks. On the other hand, iterative algorithms that depend on the output of the previous run are remarkably difficult, and sometimes impossible to parallelize. It can thus be easily surmised that one of the main tasks of programming for multicores is expressing the algorithm of the program as a set of parallel tasks. Most algorithms also need some synchronization between tasks, and may need a final reduction step to create the final output. If multiple approaches to parallelization of an algorithm are found, Amdahl’s law can be used to select the best approach to parallelization. A very commonly used law in the world of multicore programming, Amdahl’s law attempts to quantify the speedup produced by parallelizing software for multicores. Amdahl’s law states that if you enhance a fraction f of a computation by a speedup S, the overall speedup is: Speedupenhanced (f, S) = 1 / ( (1-f) + (f/S) ).
While Amdahl’s law can estimate the speed up gained by parallelizing software, it does not guide the programmer about how to create a parallel algorithm or software for a given problem. When it is required to create a parallel, multicore enabled version of existing software, often the programmer has to understand, analyze and redesign the software in order to achieve maximum benefits. In the initial days of multicore based computing, several attempts were made alleviate the complexity of parallelization by using auto parallelizing compilers. Compiler-based auto-parallelization is a much studied area, yet has still not found wide-spread application. This is largely due to the poor exploitation of parallelism inherent in program logic (often referred to as application parallelism), subsequently resulting in performance levels far below those which a skilled expert programmer could achieve. Most of today’s approaches for parallel programming for multicores depend on the programmer’s ability to create and express an algorithm as a parallel program using the various languages or libraries available for multicore programming.
Multicore programming can be achieved using are various programming models and libraries. Thread based models utilize multiple threads to express parallelism. However, if number of threads in execution is explicitly created and managed by the programmer, then the scalability of the program for target hardware of the future with larger number of cores becomes an issue. For this reason, explicit creation and management of threads is discouraged in parallel programming. Today’s parallel programming models like OpenMP, Intel’s thread building blocks and Cilk utilize what is known as user guided parallelism. In this model, the programmer is responsible for identifying parallel tasks within his/her code, but he/she does not explicitly write threads to handle these parallel tasks. Rather, these parallel units are indicated to the compiler through either specific classes or language extensions, and then the compiler, along with other supplied indications, is responsible for management of number of threads. This model is intended to provide excellent opportunities for scale up for future multicores with larger number of cores. Compilers today also utilize instruction level parallelisms to boost performance further.
While application level parallelism yields best performance gains, sometimes it is very difficult to achieve for large legacy software systems. It is also possible to gain substantial performance gains by using parallel libraries and data structures. For many commonly used mathematical operations, parallel versions are readily available in the market. MATLAB from Mathworks sells a parallel version that enable users to rum matlab code in parallel. Image processing library Imaging toolkit (ITK) also has a parallel version. By using these libraries, it is possible to gain substantial performance gain when running on a multicore without any major changes at code or algorithm level. Enterprises often use these libraries for quick and targeted performance enhancements for legacy code. All major languages today also provide parallel concurrent data structures which are inherently faster and thread safe, and language extensions that utilize parallelism. .Net language extensions contain concurrent data structures, and LINQ is a language extension that utilizes parallelism.

Multicores are here to stay and industry trends point towards largely parallel hardware architecture in the future. This is evident by Intel’s Knights Corner and AMD’s Fusion like products. The future may even move towards hybrid computing on heterogeneous platforms utilizing the cloud, NVIDIA’s GPUs and other many core devices. It is an urgent challenge today to create parallel computing technologies for tomorrow’s performance needs. Informatics plays a key role in this evolution, and must rise up to meet the challenge of how to make multicore computing easy and simple and out of the domain of specialists into the mainstream software development world.

Sources: 1. The death of CPU scaling: From one core to many — and why we’re still stuck: http://www.extremetech.com/computing/116561-the-death-of-cpu-scaling-from-one-core-to-many-and-why-were-still-stuck 2. Parallel Programming with Microsoft .NET: http://msdn.microsoft.com/en-us/library/ff963542.aspx 3. Introduction to Parallel Computing: https://computing.llnl.gov/tutorials/parallel_comp/#WhyUse 4. Automatic parallelization: http://en.wikipedia.org/wiki/Automatic_parallelization 5. Parallel computing: http://en.wikipedia.org/wiki/Parallel_computing 6. Rules for Parallel Programming for Multicore: http://www.drdobbs.com/parallel/rules-for-parallel-programming-for-multi/201804248 7. Parallel Computing Toolbox: http://www.mathworks.in/products/parallel-computing/ 8. OpenMP: http://www.openmp.org/ 9. Insight Segmentation and Registration Toolkit (ITK): http://www.itk.org/