> For the complete documentation index, see [llms.txt](https://dolorhunter.gitbook.io/w3notepad/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dolorhunter.gitbook.io/w3notepad/computerarchitecture/chep14.md). # 14.Multicore System ## How to improve performance * We have looked at * Pipelining * Pipeline optimization * To speed up: * Deeper pipelining * Make the clock run faster * Parallelism * It’s necessary for performance ## Why Multicore * Moore’s law * A law about transistors * Smaller means more transistors per die * And smaller means faster too * But: need to worry about power too… ![Multicore](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591767609/notepad/2020-06-10_133914_te81qa.webp) ## Power Wall * Power = capacitance \* voltage2 \* frequency * Reducing voltage helps (a lot) * Better cooling helps * The `power wall` * We can’t reduce voltage further * leakage power * We can’t remove more heat * limited by air ![Power Limits](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591767609/notepad/2020-06-10_133628_xnepbo.webp) ## Hyperthreading * `Hyperthreads` (Intel) * Illusion of multiple cores on a single core * Switch between hardware threads for stalls * Fine grained and coarse grained * | Multi-Core | Multi-Issue | HT | | | -------------- | ----------- | -- | - | | Programs | N | 1 | N | | Num. Pipelines | N | 1 | 1 | | Pipeline Width | 1 | N | N | * Hyperthreads * HT = Multi-Issue + extra PCs and registers - dependency logic * HT = MultiCore - redundant functional units + hazard avoidance * Hyperthreads (Intel) * Illusion of multiple cores on a single core * Easy to keep HT pipelines full + share functional units Hyperthreading ## Example: All of the above ![Intel CPU](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591767889/notepad/2020-06-10_134352_sqzejq.webp) * 8 multiprocessors * 4 core per multiprocessor * 2 HT per core * Dynamic multi-issue: 4 issue * Pipeline depth: 16 * Note: each processor may have multiple processing cores, so this is an example of a **multiprocessor, multicore, hyperthreaded** system ## Parallel Programming * Q: So lets just all use multicore from now on! * A: Software must be written as parallel program * `Multicore difficulties` * Partitioning work, balancing load * Coordination & synchronization * Communication overhead * How do you write parallel programs? * ... without knowing exact underlying architecture? ![Multicore difficulties](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591769268/notepad/2020-06-10_140238_tytujy.webp) ### Work Partitioning * Partition work so all cores have something to do ![Work Partitioning](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591768386/notepad/2020-06-10_134747_otuowk.webp) ### Load Balancing * Need to partition so all cores are actually working ![Load Balancing](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591768386/notepad/2020-06-10_134804_i9byre.webp) ## Amdahl’s Law * If tasks have a `serial part` and a `parallel part`… * Example: * step 1: divide input data into n pieces * step 2: do work on each piece * step 3: combine all results * Recall: `Amdahl’s Law` * As number of cores increases … * time to execute parallel part? `goes to zero` * time to execute serial part? `Remains the same` * `Serial part eventually dominates` ![Amdahl’s Law](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591768386/notepad/2020-06-10_134946_ioxwde.webp) ### Pitfall: Amdahl’s Law affected execution time = amount of improvement + execution time unaffected ``` T_improved = T_affected / improvement factor + T_unaffected ``` * Improving an aspect of a computer and expecting a proportional improvement in overall performance Example: multiply accounts for 80s out of 100s * How much improvement do we need in the multiply performance to get 5×overall improvement? ``` 20 = 80/n + 20 ``` ## Scaling Example * Workload: sum of 10 scalars, and 10 × 10 matrix sum * Speed up from 10 to 100 processors? * Single processor: Time * 10 processors * Time = * Speedup = * 100 processors * Time = * Speedup = * Assumes load can be balanced across processors * What if matrix size is 100 × 100? * Single processor: Time = (10 + 10000) × tadd * 10 processors * Time = * Speedup = * 100 processors * Time = * Speedup = * Assuming load balanced ## Scaling * Strong scaling vs. weak scaling * Strong scaling: scales with same problem size * Weak scaling: scales with increased problem size ## Synchronization ### Parallelism and Synchronization * How do I take advantage of multiple processors; `parallelism`? * How do I write (correct) parallel programs, `cache coherency and synchronization`? * What primitives do I need to implement correct parallel programs? ### Topics * Understand Cache Coherency * Synchronizing parallel programs * Atomic Instructions * HW support for synchronization * How to write parallel programs * Threads and processes * Critical sections, race conditions, and mutexes ### Parallelism and Synchronization 2 * `Cache Coherency Problem`: What happens when two or more processors cache shared data? * i.e. the view of memory held by two different processors is through their individual caches * As a result, processors can see different (`incoherent`) values to the same memory location * Each processor core has its own L1 cache ![Each processor core has its own L1 cache](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591769848/notepad/2020-06-10_141033_djje5m.webp) ### Shared Memory Multiprocessors * Shared Memory Multiprocessor (SMP) * Typical (today): 2 – 8 cores each * HW provides single physical address space for all processors * Assume uniform memory access (ignore NUMA) ![Shared Memory Multiprocessors](https://res.cloudinary.com/dfb5w2ccj/image/upload/v1591769847/notepad/2020-06-10_141205_jbwvd7.webp) ### Cache Coherency Problem ``` Thread A (on Core0) for(int i = 0, i < 5; i++){ x = x + 1; } Thread B (on Core1) for(int j = 0; j < 5; j++) { x = x + 1; } ``` * What will the value of x be after both loops finish? * Start: x = 0 ``` Thread A (on Core0) for(int i = 0, i < 5; i++) { LW $t0, addr(x) ADDIU $t0, $t0, 1 SW $t0, addr(x) } Thread B (on Core1) for(int j = 0; j < 5; j++) { LW $t0, addr(x) ADDIU $t0, $t0, 1 SW $t0, addr(x) } ``` * What will the value of x be after both loops finish? * a) 6 * b) 8 * c) 10 * d) All of the above * e) None of the above *注: 理想情况是 10. 实际上 6, 8, 10 都有可能.*