High Performance Computing

I M. TECH I SEM – CSE(R23)

Parallel Programming Platforms
• The traditional logical view of a sequential computer consists
of a memory connected to a processor via a datapath.
• All three components - processor, memory, and datapath -
present bottlenecks to the overall processing rate of a computer
system.
• A number of architectural innovations over the years have
addressed these bottlenecks.
• One of the most important innovations is multiplicity - in
processing units, datapaths, and memory units.
• This multiplicity is either entirely hidden from the programmer,
as in the case of implicit parallelism, or exposed to the
programmer in different forms.
 Implicit Parallelism: Trends in
Microprocessor Architectures
• While microprocessor technology has delivered
significant improvements in clock speeds over the
past decade, it has also exposed a variety of other
performance bottlenecks.
• To alleviate these bottlenecks, microprocessor
designers have explored alternate routes to cost-
effective performance gains.
• we will outline some of these trends with a view to
understanding their limitations and how they impact
algorithm and code development.
a. Pipelining and Superscalar Execution
• Processors have long relied on pipelines for improving execution rates.
By overlapping various stages in instruction execution (fetch, schedule,
decode, operand fetch, execute, store, among others), pipelining enables
faster execution.
• The assembly-line analogy works well for understanding pipelines. If
the assembly of a car, taking 100 time units, can be broken into 10
pipelined stages of 10 units each, a single assembly line can produce a
car every 10 time units! This represents a 10-fold speedup over
producing cars entirely serially, one after the other.
• It is also evident from this example that to increase the speed of a single
pipeline, one would break down the tasks into smaller and smaller units,
thus lengthening the pipeline and increasing overlap in execution. In the
context of processors, this enables faster clock rates since the tasks are
now smaller.
• For example, the Pentium 4, which operates at 2.0 GHz, has
a 20 stage pipeline. Note that the speed of a single pipeline
is ultimately limited by the largest atomic task in the
pipeline. Furthermore, in typical instruction traces, every
fifth to sixth instruction is a branch instruction. Long
instruction pipelines therefore need effective techniques for
predicting branch destinations so that pipelines can be
speculatively filled. The penalty of a misprediction increases
as the pipelines become deeper since a larger number of
instructions need to be flushed. These factors place
limitations on the depth of a processor pipeline and the
resulting performance gains.
 Example for Superscalar execution
• Consider a processor with two pipelines and the ability
to simultaneously issue two instructions. These
processors are sometimes also referred to as super-
pipelined processors. The ability of a processor to issue
multiple instructions in the same cycle is referred to as
superscalar execution. Since the architecture
illustrated allows two issues per clock cycle, it is also
referred to as two-way superscalar or dual issue
execution.
Example of a two-way superscalar execution of
instructions.
• The first and second instructions are independent and therefore can
be issued concurrently.
• This is illustrated in the simultaneous issue of the instructions load
R1, @1000 and load R2, @1008 at t = 0.
• The instructions are fetched, decoded, and the operands are fetched.
The next two instructions, add R1, @1004 and add R2, @100C are
also mutually independent, although they must be executed after the
first two instructions.
• Consequently, they can be issued concurrently at t = 1 since the
processors are pipelined. These instructions terminate at t = 5. The
next two instructions, add R1, R2 and store R1, @2000 cannot be
executed concurrently since the result of the former (contents of
register R1) is used by the latter.
• Therefore, only the add instruction is issued
at t = 2 and the store instruction at t = 3. Note
that the instruction add R1, R2 can be
executed only after the previous two
instructions have been executed.
• Another source of dependency between instructions results
from the finite resources shared by various pipelines.
• As an example, consider the co-scheduling of two floating
point operations on a dual issue machine with a single
floating point unit.
• Although there might be no data dependencies between the
instructions, they cannot be scheduled together since both
need the floating point unit. T
• his form of dependency in which two instructions compete
for a single processor resource is referred to as resource
dependency.
• The flow of control through a program enforces a third
form of dependency between instructions.
• Consider the execution of a conditional branch
instruction. Since the branch destination is known only
at the point of execution, scheduling instructions a
priori across branches may lead to errors.
• These dependencies are referred to as branch
dependencies or procedural dependencies and are
typically handled by speculatively scheduling across
branches and rolling back in case of errors.
 b. Very Long Instruction Word
Processors
• The parallelism extracted by superscalar processors is often
limited by the instruction look-ahead.
• The hardware logic for dynamic dependency analysis is
typically in the range of 5-10% of the total logic on
conventional microprocessors (about 5% on the four-way
superscalar Sun UltraSPARC).
• This complexity grows roughly quadratically with the number
of issues and can become a bottleneck.
• An alternate concept for exploiting instruction-level parallelism
used in very long instruction word (VLIW) processors relies on
the compiler to resolve dependencies and resource availability
at compile time.
• The VLIW concept, first used in Multiflow Trace (circa 1984)
and subsequently as a variant in the Intel IA64 architecture,
has both advantages and disadvantages compared to
superscalar processors.
• Since scheduling is done in software, the decoding and
instruction issue mechanisms are simpler in VLIW processors.
• The compiler has a larger context from which to select
instructions and can use a variety of transformations to
optimize parallelism when compared to a hardware issue unit.
• Additional parallel instructions are typically made available to
the compiler to control parallel execution.
• However, compilers do not have the dynamic
program state (e.g., the branch history buffer)
available to make scheduling decisions.
• This reduces the accuracy of branch and memory
prediction, but allows the use of more sophisticated
static prediction schemes.
• Other runtime situations such as stalls on data fetch
because of cache misses are extremely difficult to
predict accurately. This limits the scope and
performance of static compiler-based scheduling.
 2 Limitations of Memory System
Performance
• The effective performance of a program on a computer
relies not just on the speed of the processor but also on the
ability of the memory system to feed data to the processor.
• At the logical level, a memory system, possibly consisting
of multiple levels of caches, takes in a request for a memory
word and returns a block of data of size b containing the
requested word after l nanoseconds.
• Here, l is referred to as the latency of the memory. The rate
at which data can be pumped from the memory to the
processor determines the bandwidth of the memory system.
 Ex: Effect of memory latency on
performance
• Consider a processor operating at 1 GHz (1 ns clock) connected
to a DRAM with a latency of 100 ns (no caches).
• Assume that the processor has two multiply-add units and is
capable of executing four instructions in each cycle of 1 ns.
• The peak processor rating is therefore 4 GFLOPS. Since the
memory latency is equal to 100 cycles and block size is one
word, every time a memory request is made, the processor must
wait 100 cycles before it can process the data.
• Consider the problem of computing the dot-product of two
vectors on such a platform. A dot-product computation performs
one multiply-add on a single pair of vector elements, i.e., each
floating point operation requires one data fetch. It is easy to see
a. Improving Effective Memory Latency
Using Caches
• Handling the mismatch in processor and DRAM
speeds has motivated a number of architectural
innovations in memory system design.
• One such innovation addresses the speed mismatch
by placing a smaller and faster memory between the
processor and the DRAM.
• This memory, referred to as the cache, acts as a low-
latency high-bandwidth storage.
• The data needed by the processor is first fetched into
the cache. All subsequent accesses to data items
residing in the cache are serviced by the cache.
• Thus, in principle, if a piece of data is repeatedly used, the
effective latency of this memory system can be reduced by
the cache.
• The fraction of data references satisfied by the cache is
called the cache hit ratio of the computation on the system.
• The effective computation rate of many applications is
bounded not by the processing rate of the CPU, but by the
rate at which data can be pumped into the CPU.
• Such computations are referred to as being memory bound.
The performance of memory bound programs is critically
impacted by the cache hit ratio.
 Ex: Impact of caches on memory system
performance
• consider a 1 GHz processor with a 100 ns latency DRAM. In
this case, we introduce a cache of size 32 KB with a latency
of 1 ns or one cycle (typically on the processor itself).
• We use this setup to multiply two matrices A and B of
dimensions 32 x 32. We have carefully chosen these
numbers so that the cache is large enough to store
matrices A and B, as well as the result matrix C.
• Once again, we assume an ideal cache placement strategy in
which none of the data items are overwritten by others.
Fetching the two matrices into the cache corresponds to
fetching 2K words, which takes approximately 200 µs.
• We know from elementary algorithmics that multiplying
two n x n matrices takes 2n3 operations. For our problem, this
corresponds to 64K operations, which can be performed in
16K cycles (or 16 µs) at four instructions per cycle. The total
time for the computation is therefore approximately the sum of
time for load/store operations and the time for the computation
itself, i.e., 200+16 µs. This corresponds to a peak computation
rate of 64K/216 or 303 MFLOPS. Note that this is a thirty-fold
improvement over the previous example, although it is still
less than 10% of the peak processor performance. We see in
this example that by placing a small cache memory, we are
able to improve processor utilization considerably.
b. Impact of Memory Bandwidth
• Memory bandwidth refers to the rate at which data can be
moved between the processor and memory.
• It is determined by the bandwidth of the memory bus as well as
the memory units. One commonly used technique to improve
memory bandwidth is to increase the size of the memory blocks.
• For an illustration, let us relax our simplifying restriction on the
size of the memory block and assume that a single memory
request returns a contiguous block of four words. The single
unit of four words in this case is also referred to as a cache line.
Conventional computers typically fetch two to eight words
together into the cache. We will see how this helps the
performance of applications for which data reuse is limited.
 Ex: Effect of block size: dot-product of
two vectors
• Consider again a memory system with a single
cycle cache and 100 cycle latency DRAM with
the processor operating at 1 GHz. If the block
size is one word, the processor takes 100
cycles to fetch each word. For each pair of
words, the dot-product performs one multiply-
add, i.e., two FLOPs. Therefore, the algorithm
performs one FLOP every 100 cycles for a
peak speed of 10 MFLOPS.
 Ex: Impact of strided access
• 1 for (i = 0; i < 1000; i++)
column_sum[i] = 0.0;
for (j = 0; j < 1000; j++)
column_sum[i] += b[j][i];
Multiplying a matrix with a vector: (a) multiplying column-by-column, keeping a running
sum; (b) computing each element of the result as a dot product of a row of the matrix with
the vector
 c. Alternate Approaches for Hiding
Memory Latency
• Imagine sitting at your computer browsing the web during
peak network traffic hours. The lack of response from your
browser can be alleviated using one of three simple
approaches:
• (i) we anticipate which pages we are going to browse ahead
of time and issue requests for them in advance;
• (ii) we open multiple browsers and access different pages
in each browser, thus while we are waiting for one page to
load, we could be reading others; or
• (iii) we access a whole bunch of pages in one go -
amortizing the latency across various accesses.
• The first approach is called prefetching, the
second multithreading, and the third one
corresponds to spatial locality in accessing
memory words. Of these three approaches,
spatial locality of memory accesses has been
discussed before. We focus on prefetching and
multithreading as techniques for latency hiding
in this section.
• Multithreading for Latency Hiding
• A thread is a single stream of control in the flow of a
program
• Prefetching for Latency Hiding
• In a typical program, a data item is loaded and used by a
processor in a small time window. If the load results in a
cache miss, then the use stalls. A simple solution to this
problem is to advance the load operation so that even if
there is a cache miss, the data is likely to have arrived by
the time it is used. However, if the data item has been
overwritten between load and use, a fresh load is issued.
 d. Tradeoffs of Multithreading and
Prefetching
• While it might seem that multithreading and
prefetching solve all the problems related to
memory system performance, they are
critically impacted by the memory bandwidth.
 Ex: Impact of bandwidth on
multithreaded programs
• Consider a computation running on a machine with a 1 GHz
clock, 4-word cache line, single cycle access to the cache, and
100 ns latency to DRAM.
• The computation has a cache hit ratio at 1 KB of 25% and at
32 KB of 90%. Consider two cases: first, a single threaded
execution in which the entire cache is available to the serial
context, and second, a multithreaded execution with 32 threads
where each thread has a cache residency of 1 KB.
• If the computation makes one data request in every cycle of 1
ns, in the first case the bandwidth requirement to DRAM is one
word every 10 ns since the other words come from the cache
(90% cache hit ratio).
• This corresponds to a bandwidth of 400 MB/s.
In the second case, the bandwidth requirement
to DRAM increases to three words every four
cycles of each thread (25% cache hit ratio).
Assuming that all threads exhibit similar cache
behavior, this corresponds to 0.75 words/ns, or
3 GB/s.