Computer Organization and architecture notes

Notes.md

Chapter 17 - Parallel Processing

General Organization

• Four types of organization
• SISD
  • Single Instruction, Single Data stream
  • Single processor executes a single instruction stream to operate on data stored in a single memory.
  • Examples: Uniprocessors
• SIMD
  • Single Instruction, Multiple Data stream
  • Single machine instruction controls the simulataneous execution of a number of processing elements on a lockstep basis
  • Examples: Vector and array processors
• MISD
  • Multiple Instruction, Single Data stream
  • A sequence of data is transmitted to a set of processors, each of which executes a different instruction in sequence.
  • Not commercially implemented
• MIMD
  • Multiple Instruction, Multiple Data stream
  • A set of processors simultaneously execute different instruction sequences on different data sets.
  • Examples: SMPs, clusters, and NUMA systems

Bus Organization

• Pros

  • Simplest approach to multiprocessor organization
  • Flexible. Able to add new processors easily by attaching more processors to the bus
  • Reliable. The bus is a passive medium, so failure of any attached device will not cause failure of the whole system.

• Cons:

  • Performance is limited by bus cycle time.
  • Each processor should have it's own cache memory
    • Reduces the number of bus access
    • Leads to cache coherence problems
      • If a word is altered in one cache it could conceivably invalidate a word in another cache.
      • Prevented by alerting other processors when an update takes place.
      • Addressed in hardware, not typically the OS.

System Design considerations

• Simultaneous concurrent processes

  • OS routines need to be reentrant to allow several processors to execute the same IS code simultaneously
  • OS tables and management structures must be managed properly to avoid deadlock or invalid operations

• Scheduling

  • Any processor may perform scheduling so conflicts must be avoided
  • Scheduler must assign ready processes to available processors

• Synchronization

  • With multiple active processes having potential access to shared address spaces or I/O resources, care must be taken to provide effective synchronization
  • Synchronization is a facility that enforces mutual exclusion and event ordering

• Memory management

  • In addition to dealing with all of the issues found on uniprocessor machines, the OS needs to exploit the available hardware parallelism to achieve the best performance
  • Paging mechanisms on different processors must be coordinated to enforce consistency when several processors share a page or segment and to decide on page replacement

• Reliability and fault tolerance

  • OS should provide graceful degradation in the face of processor failure
  • Scheduler and other portions of the operating system must recognize the loss of a processor and restructure accordingly

Cache Coherence

• Software Solutions

  • Relies on compiler
  • Detects overhead at compile time
    • The compile-time software approaches must make conservative decisions, leading to inefficient cache utilization.

• Hardware Solutions

  • Referred to as cache coherence protocols
  • Provide dynamic recognition at run-time of potential inconsistency conditions
  • Only dealt with when it arises, thus utilizing the cache more efficiently than a software approach (more performant)
  • Transparent to programmers and compilers, reducing software development burden.
  • Two Categories
    • Directory protocols
    • Snoopy protocols