Question? Leave a message!




Introduction to Multicore Programming

Introduction to Multicore Programming
Dr.JakeFinlay Profile Pic
Dr.JakeFinlay,Germany,Teacher
Published Date:22-07-2017
Website URL
Comment
Introduction to Multicore Programming Marc Moreno Maza University of Western Ontario, London, Ontario (Canada) CS 3101 (Moreno Maza) Introduction to Multicore Programming CS 3101 1 / 38Plan 1 Multi-core Architecture Multi-core processor CPU Cache CPU Coherence 2 Concurrency Platforms An overview of Cilk++ Race Conditions and Cilkscreen MMM in Cilk++ (Moreno Maza) Introduction to Multicore Programming CS 3101 2 / 38Multi-core Architecture Plan 1 Multi-core Architecture Multi-core processor CPU Cache CPU Coherence 2 Concurrency Platforms An overview of Cilk++ Race Conditions and Cilkscreen MMM in Cilk++ (Moreno Maza) Introduction to Multicore Programming CS 3101 3 / 38Multi-core Architecture Multi-core processor (Moreno Maza) Introduction to Multicore Programming CS 3101 4 / 38Multi-core Architecture Multi-core processor (Moreno Maza) Introduction to Multicore Programming CS 3101 5 / 38Multi-core Architecture Multi-core processor (Moreno Maza) Introduction to Multicore Programming CS 3101 6 / 38Multi-core Architecture Multi-core processor Memory I/O Network … P P P Chip Multiprocessor (CMP) (Moreno Maza) Introduction to Multicore Programming CS 3101 7 / 38Multi-core Architecture Multi-core processor Multi-core processor A multi-core processor is an integrated circuit to which two or more individual processors (called cores in this sense) have been attached. In a many-core processor the number of cores is large enough that traditional multi-processor techniques are no longer ecient. Cores on a multi-core device can be coupled tightly or loosely: may share or may not share a cache, implement inter-core communications methods or message passing. Cores on a multi-core implement the same architecture features as single-core systems such as instruction pipeline parallelism (ILP), vector-processing, SIMD or multi-threading. Many applications do not realize yet large speedup factors: parallelizing algorithms and software is a major on-going research area. (Moreno Maza) Introduction to Multicore Programming CS 3101 8 / 38Multi-core Architecture CPU Cache CPU Cache (1/7) A CPU cache is an auxiliary memory which is smaller, faster memory than the main memory and which stores copies of of the main memory locations that are expectedly frequently used. Most modern desktop and server CPUs have at least three independent caches: the data cache, the instruction cache and the translation look-aside bu er. (Moreno Maza) Introduction to Multicore Programming CS 3101 9 / 38Multi-core Architecture CPU Cache CPU Cache (2/7) Each location in each memory (main or cache) has a datum (cache line) which ranges between 8 and 512 bytes in size, while a datum requested by a CPU instruction ranges between 1 and 16. a unique index (called address in the case of the main memory) In the cache, each location has also a tag (storing the address of the corresponding cached datum). (Moreno Maza) Introduction to Multicore Programming CS 3101 10 / 38Multi-core Architecture CPU Cache CPU Cache (3/7) When the CPU needs to read or write a location, it checks the cache: if it nds it there, we have a cache hit if not, we have a cache miss and (in most cases) the processor needs to create a new entry in the cache. Making room for a new entry requires a replacement policy: the Least Recently Used (LRU) discards the least recently used items rst; this requires to use age bits. (Moreno Maza) Introduction to Multicore Programming CS 3101 11 / 38Multi-core Architecture CPU Cache CPU Cache (4/7) Read latency (time to read a datum from the main memory) requires to keep the CPU busy with something else: out-of-order execution: attempt to execute independent instructions arising after the instruction that is waiting due to the cache miss hyper-threading (HT): allows an alternate thread to use the CPU (Moreno Maza) Introduction to Multicore Programming CS 3101 12 / 38Multi-core Architecture CPU Cache CPU Cache (5/7) Modifying data in the cache requires a write policy for updating the main memory - write-through cache: writes are immediately mirrored to main memory - write-back cache: the main memory is mirrored when that data is evicted from the cache The cache copy may become out-of-date or stale, if other processors modify the original entry in the main memory. (Moreno Maza) Introduction to Multicore Programming CS 3101 13 / 38Multi-core Architecture CPU Cache CPU Cache (6/7) The replacement policy decides where in the cache a copy of a particular entry of main memory will go: - fully associative: any entry in the cache can hold it - direct mapped: only one possible entry in the cache can hold it -N-way set associative: N possible entries can hold it (Moreno Maza) Introduction to Multicore Programming CS 3101 14 / 38Multi-core Architecture CPU Cache Cache Performance for SPEC CPU2000 by J.F. Cantin and M.D. Hill. The SPEC CPU2000 suite is a collection of 26 compute-intensive, non-trivial programs used to evaluate the performance of a computer's CPU, memory system, and compilers (http://www.spec.org/osg/cpu2000 ). (Moreno Maza) Introduction to Multicore Programming CS 3101 15 / 38Multi-core Architecture CPU Coherence Cache Coherence (1/6) x=3 Load x … x=3 PP P Figure: ProcessorP reads x=3 rst from the backing store (higher-level memory) 1 (Moreno Maza) Introduction to Multicore Programming CS 3101 16 / 38Multi-core Architecture CPU Coherence Cache Coherence (2/6) x=3 Load x … x=3 x=3 PP P Figure: Next, ProcessorP loads x=3 from the same memory 2 (Moreno Maza) Introduction to Multicore Programming CS 3101 17 / 38Multi-core Architecture CPU Coherence Cache Coherence (3/6) x=3 Load x … x=3 x=3 x=3 PP P Figure: ProcessorP loads x=3 from the same memory 4 (Moreno Maza) Introduction to Multicore Programming CS 3101 18 / 38Multi-core Architecture CPU Coherence Cache Coherence (4/6) x=3 Store Store … x=3 x=3 x=3 x=5 PP P Figure: ProcessorP issues a write x=5 2 (Moreno Maza) Introduction to Multicore Programming CS 3101 19 / 38Multi-core Architecture CPU Coherence Cache Coherence (5/6) x=3 Store Store … x=3 x=5 x=3 x=5 PP P Figure: ProcessorP writes x=5 in his local cache 2 (Moreno Maza) Introduction to Multicore Programming CS 3101 20 / 38