Recap

This is the second lecture among the series of lectures to cover a framework for evaluating the parallelism in hardware and software. In last lecture we introduced the framework to evaluate a parallel architecture according to following aspects:

  • concurrency
  • communication
  • synchronization
  • what is being shared
  • what is being partitioned

The resources might be shared and partitioned. They can be categorized as:

  • Execution
    • ALU
    • cores/processors
  • Control
    • sequencer
    • instruction
    • OOO scheduler
  • State
    • register
    • memory
  • Networks

Apart from simple pipelined architecture we looked at several architectures and applied the above framework for different types of architectures including

  • Superscalar
  • Simultaneous Multi-Threading(SMT)/Thread Level Speculation(TLS)
  • Very Large Instruction Width(VLIW)
  • Explicit Data Flow
  • Data Level Parallelims(DLP) in SIMD and Vector machines
  • Thread Level Parallelism(TLP) as known as MIMD in both shared memory as well as distributed memory

Please refer to slide lectures for the details.

Clarifications from last lecture

Implicit vs Explicit mechanisms

Implicit mechanisms are usually manged by hardware and are transparent to the user and compiler where as explicit mechanisms are visible to the user and/or compiler. As an example, a machine that provides message passing interface has explicit communication mechanism. On the other hand a shared memory machine has an implicit communication mechanism because the user and/or compiler can’t tell whether the loads are from local memory or remote memory.

In an explicit data flow the dependency between instructions and scheduling of instructions to different functional units is done with software help. However in an OoO machine a limited window of data flow is captured and used by the hardware itself. Dependencies are resolved using renaming hardware, and scheduling is done using the scheduler(which is a pure hardware unit.)

SIMD vs Vector machines

Vector machines are special type of SIMD machines. In SIMD machine a single instruction can work on different lane of data. Therefore ALUs and registers are partitioned. Vector machines unlike SIMD machines can’t have independent addresses for different lanes of SIMD. Other words, a SIMD machine can have partitioned memory and memory addressing. Therefore the following operation is not possible in a vector machine for two different lanes of the same instruction.

dest_reg_1=Mem[address_reg_1] dest_reg_2=Mem[address_reg_2]

Of course in a vector machine we can load consequent addresses like in the same instruction:

dest_reg_1=Mem[address_reg_1] dest_reg_2=Mem[address_reg_1+8]

Intel SSE instructions can provide load from un-alinged address but not load from independent addresses for different lanes.

Larabee has the feature of independent addressing on different lanes. It is an Intel product and for the first time it is going to be used in a HPC platform in UT.

Shuffle network

Arbitrary shuffle operation in a SIMD instruction requires complex hardware. A generalized format for an arbitrary shuffle operation is

dest_reg = shuffle source_reg, permutation_reg

Different part of permutation_reg species in which chunk of destination, each chunk of source should go. We can simplify the shuffle network by limiting the shuffle operation. For example limiting the shuffle only with neighbor lane. Some machines have instructions for simple shuffle operations for very wide data. For example such mechanisms can be find in chips used in Cameras.

Wide SIMDs has the drawback of underutilized resources because it is very hard to find operations for all the lanes in a SIMD machine to fully utilize the resources.

Thread Level Parallelism

In a TLP machine different instruction streams execute completly independent of each other using independent sequencer, scheduler, register file, and ALUs. However the memory is shared among different threads. Memory consistency model determines the ordering of memory operations. The programmer/compiler needs to know the memory consistency model to write/generate the correct code.

Different flavors of hardware and/or software mechanisms are used for synchronization between the threads (Barriers, Lockes, Mutexes.) Note that we can not use only clock or time based rendezvous for synchronization.

Distributed system vs parallel system

Parallel systems are more tightly coupled comparing to distributed systems. Therefore different execution threads have some idea about the status of each other and they need less explicit synchronization. On the other hand distributed systems need lots of synchronizations. In this class we rarely talk about explicit synchronization because we mostly talk about parallel systems.

Symmetric Multi-Processor system vs Distributed Shared Memory

In and SMP all processors/cores have a shared memory whereas in a DSM memory accesses go through a home processor.