Lecture Notes for Concurrent Programming

27 May 2003 - System Architecture and Concurrency

Outline

• Concurrency sources.

• System architectures.

  • Uniprocessor architectures.

  • Multiprocessor architectures.

• Caches

  • Cache copy consistency.

  • Primary store consistency.

Concurrency Sources

• Concurrency comes from hardware.

  • Multiple CPUs.

  • The hardware doesn't have to be real (virtual machines).

  • Hardware concurrency is natural or true or actual concurrency.

• Concurrency comes from software.

  • Process and threads.

  • Programming languages and libraries.

  • Software concurrency is simulated or faux or virtual concurrency.

    • But, software can use hardware to provide true concurrency too.

• For greater flexibility, combine software and hardware.

  • Software abstracts hardware.

  • Smooth over differences in number, kind, and behavior.

System Architectures

• The arrangement of hardware and software into a system is the system architecture.

• System architecture greatly influences concurrency.

  • Hardware and software provide concurrency.

  • System architecture determines behavior.

  • And concurrent behavior can get really weird.

• Architectures and concurrency.

  • Uniprocessors and caches (parallel computing).

  • Multiprocessors and shared memory (concurrent computing).

  • Networked computers (distributed computing).

Uniprocessor Architectures

• Natural concurrency in uniprocessors occurs within the CPU.

  • Vectoring, pipelining, multi-core CPUs (maybe).

• Application-level concurrency comes from software.

  • Multi-processing, threads.

• Caches are crucial for good execution performance.

  • They also cause problems for concurrency.

Cache Read Behavior

• Memory reads either hit or miss the cache.
  
  

• Notice that caches make copies of the data.

Cache Write Behavior

• Written values can either stop at the cache or pass on through.

  • Write-back caching.
  

  • Write-through caching.
  

• Write-back cache and main store values may differ.

  • That is, the values in the cache and primary store may be inconsistent.

Multiprocessor Architectures

• Multiprocessors are naturally concurrent.

  • They usually implement software concurrency too.

• The Java Virtual Machine (JVM) is (roughly) a multiprocessor architecture.

  • A class instance corresponds to a CPU-cache.

Cache Copy Consistency

• This is not the only source of consistency problems.

Primary Store Consistency

• If writes compete, who wins?

  • Caches and network delays make this a difficult answer.

• Different computations can see different winners.
  

• But it's even worse: a computation may not see its own writes.

  str x, r0
  ld  r1, x
  eq  r0, r1 # maybe true, maybe false.
  

• Storage consistency models determine observed behavior.

  • Sequential consistency.

  • Processor consistency.

  • Release consistency.

Points to Remember

• The system architecture influences concurrency.

  • Usually to the architect's benefit.

• Uniprocessors are a too simple model.

  • But the caching behavior is realistic.

• Multiprocessor architectures are more realistic.

  • Mostly simulated by software.

• Mind the cache.

  • This is a preview of problems to come.

This page last modified on 27 May 2003.