### ### Multicore and Linux ### 1. The Multicore Revolution The Multicore Association, founded in 2005, is a member-funded, non-profit, industry consortium focused on the creation of open standard APIs, specifications, and guidelines that will allow system developers and programmers to adopt multicore technology into their applications more readily . 2. What is a Multicore/Multiprocessor System? Four alternatives; (i) Single Instruction – Single Data (e.g., standard unicore systems - quite rare now!) (ii) Single Instruction – Multiple Data (e.g., processor array, vector supercomputers) (iii) Multiple Instruction – Single Data (e.g., graphics cards) (iv) Multiple Data – Multiple Instruction (e.g., A multi-core CPU is an MIMD machine. Shared memory machines may be of the bus-based, extended, or hierarchical type. Distributed memory machines may have hypercube or mesh interconnection schemes) 3. Necessity of Multicore Systems The clock keeps a processor's parts working in unison, like rowers on a galley ship. Other things being equal, the more ticks you have per second, the more work will get done. But - physical issues aside - it's no longer worth the cost in terms of power consumed and heat dissipated. Intel calls the speed/power dillemma a ”fundamental theorem of multicore processors". Intel has reported that Underclocking a single core by 20 percent saves half the power while sacrificing just 13 percent of the ­performance. That means that if you divide the work between two cores running at an 80 percent clock rate, you get 73 percent better performance for the same power. 4. It's Going To Be A Multicore World In the second half of 2006 the best processors were dual-core processors. Since 2006 the development has gone on, so that the new processors get four or more independent microprocessors. Today, single-core processors are not used in new personal computers. But they remain popular in embedded systems. IBM Power7 processors are available in sixteen-core or thirty two-core configuration for servers. In October 2009, they announced a new chip TILE-Gx100 based on 40nm technology that features up to 100 cores at 1.5 GHz On 25 July 2011, TilePro processor was found by Facebook to be 3-times more energy-efficient than Intel's x86, based on Facebook's experiments on servers using TilePro processor and Intel's x86 In 2012 Tilera founder, Dr. Agarwal, is leading a new MIT effort dubbed The Angstrom Project. It is one of four DARPA-funded efforts aimed at building exascale supercomputers. The goal is to design a chip with 1,000 cores. Tilera Readies Processors With 100 Cores http://www.informationweek.com/news/hardware/processors/showArticle.jhtml?articleID=220900697&subSection=Processors http://arstechnica.com/old/content/2004/09/intel-future.ars 5. Programming Challenges I Multicore performance depends on the software algorithms. At best, possible gains are limited by the fraction of the software that can be parallelised to (Amdahl's Law). Gustafson's law says use a bigger problem - thus minimising the sequential proportion - it rescues parallel processing from Amdahl's law. It is based on the idea that if the problem size is allowed to grow along with P, the sequential fraction of the workload will not ultimately come to dominate. Amdahl assumes that data set size stays the same. In practice we tend to be more guided by Gustafson’s law. More cores/memory allow to process larger datasets Code locking "first step". One single lock per subsystem acquired by all code, but this limits scaling. Coarse grained data locking "lock data not code". More locks: object locks, hash table lock. Reference counters to handle object lifetime. Fine grained data locking (optional). Even more locks (multiple per object). Per bucket lock in a hash. Communication latency. For highly tuned parallel code often latency is the limiter. Time to bounce the lock/refcount cache line from core A to B Cost depends on distance. adds up with fine-grained locking. Solution is to localize data or do less locks Good news is that in the multi core future latencies are lower.Compared to traditional large MP systems. Multi-core has very fast communication inside the chip Modern interconnects are faster, lower latency Modern multi-core system of equivalent size is easier to program Lockless techniques are even more complex! A declarative language, like Mercury, does it better. 6. Programming Challenges II Locks which are too wid cause poor performance or too narrow cause data corruption and crashes. Kansas statute law early 20th century “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.” To ensure that parallel execution is safe, a task’s effects must not interfere with the execution of another task. (e.g., Modifying global variables or data on the heap, Calling a function in a shared library may invisibly modify data on the heap, Interacting with the operating system, for example writing to a file). A compiler can check for these effects. If all the effects in a task are known not to interfere with other tasks, and vice versa, then the task can be safely parallelised. Profile the program to find the expensive parts. Analyse the program to determine what parts can be run in parallel. Select only the parts that can be parallelised profitably. This may involve trial and error when done by hand. Continue introducing parallelism until either all processors are fully utilised, or there is no profitable parallelism left. e.g., The program’s call graph is a tree of strongly connected components (SCCs). Analyse each procedure of each SCC, looking for sequential code with two or more statements or independent expressions whose cost is greater than a configurable threshold. Most potential parallelisation sites include are not Independent. Therefore dependent parallelisation must be supported. Variables that represent dependencies can be automatically transformed into futures. When profiling is enabled, the compiler writes a bytecode representation of the program into the executable. The parallelisation tool uses this bytecode and the profiling data to generate a feedback file. Upon re-compilation the compiler can read the feedback file and can follow the parallelisation advice in it. The feedback system can be used for any optimisation, not just parallelisation. 7. Multicore World New Zealand (Part I) James Reinders (Director, Chief Software Evangelist. United States). Worked on ASCI Red (first teraflop system) for Intel in 1996 and Knight's Corner (first teraflop chip in 2010). Dr. Tim Cornwell (Senior Software Scientist, Astronomy and Space Science, Project Lead for ASKAP. Australia, "Legacy code will die”. Dr. Martin McKendry and Stephan Friedl Open Parallel / Cisco - “The Contribution of Multicore to Server Architecture” Mahmoud (AUT) talking about IBMs tools to deal with exascle data manipulation and traffic. “Middleware Parallelisation for Exascale Data Processing and Transport in SKA Telescope”. Mahmoud S. Mahmoud (PhD candidate, Institute for Radio Astronomy & Space Research, AUT. New Zealand) Dr. Zhiyi Huang (Senior Lecturer, University of Otago. New Zealand). “WATS: Workload-Aware Task Scheduling in Asymmetric Multicore Architectures” Artur Laksberg of Microsoft - “Asynchronous Programming in C++ using Parallel Pattern Library” John Goodacre, Director, Program Management, ARM Processor Division. United Kingdom, Dr. Tim Mattson (Senior Research Scientist, Khronos OpenCL Group. United States) 8. Multicore World New Zealand (Part II) In addition to the technical theme, there was a number of business-orientated presentations. There was a very strong theme of making New Zealand a world centre in high performance computing and parallel programming. The conference was, of course, sponsored by OpenParallel, and their lead agent, Nicolas Erdody, was on a number of panel sessions. Phil McCaw (Managing Partner, MOVAC and Chair, Angel Investors Association. New Zealand) John Houlker (Strategic Initiatives Manager. New Zealand, ) Dr. David Eyers (Lecturer. New Zealand) Jim Peek, Fusion-io Senior Strategy Director. United States 9. Developments in the Linux Kernel For Multicore Systems In a nutshell, GNU Linux is a symmetric multiprocessing system (SMP) operating system - it know how to manage a multiple processor with a single shared main memory. Linux used to use a "big kernel lock" to provide the concurrency control required by symmetric multiprocessing (SMP) systems, used whenever a thread entered kernel space, and is released when the thread returns to user space (a system call is the archetypal example). BKL threads in user space can run concurrently on any available processors or processor cores, but no more than one thread can run in kernel space. The Linux kernel had a big kernel lock until it was finally replaced by more fine-grained locking mechanisms by Arnd Bergmann in 2011. By 2.2 big kernel lock for most of kernel, interrupts own lock. 2.4 more fine grained locking, still several common global locks. 2.6 further BLK reductions, new subsystems (multi queue scheduler, multi flow networking) 2.6.35 included (thank you Google) Receive Packet Steering (RPS) and Receive Flow Steering (RFS) to spread the load of network handling across the CPUs available in the system. Network cards have improved the bandwidth to the point where it's hard for a single modern CPU to keep up. In 2.6.36 Tilera architecture support (Tile CPUs) was added. In 2.6.38 automatic process grouping was added, allowing processes with the same sessionID to be grouped on the same processor as a single scheduling entity.