Multiprocessor Architecture

35 flashcards · Computer Science · by Athena Papkouf

1. Instruction-level parallelism

   Multiple instructions executing concurrently on the same core Limited by control and data dependences

2. Task-level parallelism

   Multiple threads of the same app executing concurrently on different cores, exploiting parallelism Limited by the algorithm and sync. overheads

3. Data-level parallelism

   One instruction operating concurrently on different data Limited by irregular data access patterns & memory BW

4. Amdhal's law

5. Models of Communication for synchronisation

   1.Shared address space 2.Message passing 3.Data parallel

6. Shared Address Space

   Threads communicate by reading/writing to shared vars Shared variables are like a big bulletin board  Any thread can read or write Communication is unstructured, implicit in loads and stores  Arguably easier to program, but harder to scale

7. Non-uniform Memory Access (NUMA)

   All processors can access any memory location, but... cost of memory access is different for different processors (more scalable) High bandwidth & low latency access to local memory BW scales with # of nodes if most accesses are local

8. Message Passing

   Different address spaces  Communicate explicitly via sending/receiving messages  Synchronization is implicit in the messages  Arguably harder to program, but easier to scale

9. Data Parallel

   Structure computation as a big “map” over a collection  Severely limits communication between iterations of the map (goal: preserve independent processing of iterations)

10. Single Writer, Multiple Reader (SWMR) Invariant

    Either the last writer or any reader has a valid copy

11. MSI Protocol State Diagram

12. Total directory storage per L2 bank

    # of L1 tags * bits/entry

13. reducing true sharing

    Partition the data structures and merge later privatise results

14. reducing false sharing

    move data in different cache blocks by padding

15. Loop unrolling

    Perform multiple loop iterations in one Reduce loop overhead

16. Loop fusion

    Combine two back-to-back loops with exactly the same iteration pattern to reduce loop overhead

17. Loop fission

    Split a big loop into smaller loops to improve L1 data and instruction cache miss rate

18. Desirable Lock Characteristics (5)

    ◆ Low latency ◆ Processors should be able to acquire free locks quickly ◆ Low traffic ◆ Waiting for lock should generate little/no traffic ◆ A busy lock should be handed off between processors with as little traffic as possible ◆ Scalability ◆ Latency/traffic should scale reasonably with number of processors ◆ Low storage cost ◆ Fairness ◆ Avoid starvation or substantial unfairness ◆ Ideal: processors should acquire lock in order they request access

19. Simple TS Lock Performance Characteristics (5)

    ◆ Low latency (under low contention) ◆ High coherence traffic ◆ Poor scaling ◆ Low storage cost (one int) ◆ No provisions for fairness

20. TTS Lock Performance Characteristics

    ◆ Slightly higher latency than TS in uncontended case ◆ Generates much less interconnect traffic ◆ More scalable (due to less traffic) ◆ Storage cost unchanged (one int) ◆ Still no provisions for fairness

21. TS w/ Exp. Back-off Characteristics

    ◆ Same uncontended latency as TS ◆ Generates less traffic than TS ◆ Improves scalability (due to less traffic) ◆ Storage cost unchanged ◆ Exponential back-off can cause severe unfairness ◆ Newer requesters back off for shorter intervals

22. Busy Waiting

    threads spinning while waiting

23. Blocking Synchronization

    ◆ Preempt the running thread (suspend) ◆ OS schedules another thread to run ◆ The other thread can run and make progress preferable if: Scheduling overhead is larger than expected wait time Scheduling overhead is in the order of microseconds While a few spinning iterations is in the order of nanoseconds Processor’s resources not needed for other tasks

24. Coarse-grained Locking

    ◆ Simple implementation ◆ Lots of contention ◆ No concurrency inside the data structure

25. Fine-grained Locking

    ◆ Contention for objects only ◆ Lots of concurrency exposed Limited only to updating and reading each object Cannot actually modify the hash table structure

26. Speculative Address Tracking

    ◆ Scaling the ”link register” idea to memory ◆ Don’t let instructions retire, all addresses stay in LSQ ◆ Keep speculative addresses in the LSQ ◆ Check for conflicts in the critical section ◆ Other corner cases to roll back ◆ If multiple rollbacks, retry with the lock!

27. Benefits of HLE (hardware lock elision)

    ◆ Conservative Locking Easier to show correctness than fine grained locking Our code locks more often than necessary (Why?) ◆ Locking Granularity Tradeoff between Performance and Complexity ◆ Thread-unsafe legacy libraries Require global locking

28. When does lock elision fail?

    ◆ Atomicity violation Detected by coherence protocol Restart from “ts LCK” ◆ Resource constraints Critical section bigger than ROB LD/ST in critical section conflict in cache ◆ Interrupts

29. issues with locks

    ◆ Priority inversion Higher priority threads waiting for a lock held by a lower-priority thread ◆ Convoying Threads holding locks and are de-scheduled ◆ Deadlocks/livelocks Locking in a different order across threads, is deadlock Threads constantly looping to get locks, is livelock

30. Transactional Memory (TM)

    ◆ Memory (not disk) transactions An atomic & isolated sequence of memory accesses Supported in hardware by processor & cache hierarchy ◆ Atomicity Upon commit, all memory writes take effect at once On abort, none of the writes take effect ◆ Isolation No other processor can observe writes before commit ◆ Serializability Transactions seem to commit in a single serial order The exact order is not guaranteed

31. horizontal waste

    unable to use full issue width Software not exposing enough ILP for hardware

32. Vertical waste

    whole cycle empty, nothing issued Most common after long latency events

33. (Coarse Grain) Multithreading

    Switch to a new thread on a long latency event Pay a small cost to switch in a new context Addresses purely vertical waste May increase utilization But, required to swap on long latency events Advantage: small changes to existing hardware Drawback: single-thread performance suffers

34. Fine Grained Multithreading

    Cycle between multiple threads periodically Advantages: With flexible interleave: Reasonable single thread performance and High processor utilization (esp. in case of many thread) Without: Suits “regular” applications with repetitive latencies Drawbacks: More complicated hardware to track dependences Many more contexts means we need many registers Without flex. interleaving, limited single thread perf.

35. Simultaneous Multithreading (SMT)

    Instructions from multiple threads in same cycle