\chapter{Multicore Systems}
\label{chap:multcore}

Today many applications require speed, with run times of minutes, hours
or in extreme cases even months.  Since physical obstacles, e.g. chip
feature size, clock signal distribution and heat dissipation make it
difficult to keep increasing clock speed, the primary method of speedup
today is to many computations in parallel, on multiple processors.

\section{Classic Multiprocessor Structure}

Multiple processor systems used to be only for ``the rich,'' meaning
large corporations such as insurance companies or banks.  Multiple CPU
chips would be attached to a comomn bus, to which memory modules are
also attached, shared among the processors:

\includegraphics{Images/UMABus.jpg}

This is called a {\it symmetric multiprocessor system} (SMP, the word
{\it symmetric} referring to the fact that all the processors have the
same structural access to memory.  More elaborate systems, use complex
interconnection networks such as crossbarsw instead of a bus; they are
not covered here.

Now similar systems have entered the home.  They can be cheaply made, by
placing many processors---called {\it cores}---onto one CPU chip, hence
the name {\it multicore}.  As mentioned in the Preface to this book,
today it is hard to buy a desktop, laptop or even a smart phone that is
not multicore.  Dual core is the {\it de facto} standard, quad core is
widely available in chain electronics stores, and larger systems are not
too expensive.

Note that the cores are full CPUs, each one having its own set of
registers, ALU and so on.  They still share a common memory. 

A note on terminology:  A multicore chip is still called a {\it
processor}, somewhat contradictingly.  In our treatment here, we will
use the terms {\it core} for both the cores in a multicore chip and for
a processor that is not multicore.  If for example we have a single-bus
system consisting of eight chips, each of which is quad-core, we refer
to it as a 32-core system.  In other words, we use the number of cores
to indicate the degree of parallel computation possible in a system.

The situation is somewhat complicated by the fact that manyt Intel
multicore chips also are capable of {\it hyperthreading}.  This is
accomplished by making better usage of the pipeline in the core.
So, our 32-core machine described above could sometime run 64 threads at
once.

The total threading capability of a machine, say 64 above, is sensed by
the OS.  On Linux systems, this information is shown in the file
{\bf /proc/cpuinfo}

\section{GPUs}

Another type of many-core hardware of great interest today is graphics
processing units (GPUs).  If your desktop or laptop machine  has a
somewhat high-end graphics card, you actually have, as a slogan puts it,
``a supercomputer on your desk,'' with hundreds or even thousands of
cores.  They operate in a very restrictive manner, though, and one can
achieve a high degree of parallelism only on certain types of
applications.

GPU structure, on the other hand, is considerably more complex.  An
NVIDIA GPU's processing area is broken down into a number of {\bf
streaming multiprocessors} (SMs).  Many threads can be active at once on
an SM, and all the SMs are active at once; thus very large degrees of
parallel operation are possible.  All of the threads on all the SMs
share the same main memory, as in the multicore/SMP case.  However,
there is also separate memory specific to each SM, that serves in
essence as a programmer-managed cache.

It is crucial to understand that within an SM, the threads run in
lockstep.  In the fetch/execute cycle, each thread fetches the same
instruction, and then either executes that instruction or does nothing
at all.  This allows for having many parallel threads, but
becomes problematic when a branch instruction is encountered.  If the
condition of the branch holds for some threads but not others, the
others are forced to be idle.  If there are k threads with k separate
conditions, this effectively serializes that SM during that period.

So, although the GPU has multiple cores and threads share memory,
this lockstep nature of the GPU means that programming it is very
different from multicore programming.  It will also manifest itself in
another major difference, involving locks, to be discussed later.

Another interesting difference is that the GPU actually has an OS in the
hardware.  It decides when to run which threads.

\section{Message-Passing Systems}

Note that there is another form of parallel processing machines, knowing
as {\bf message-passing systems}.  Today these typically take the form
of a set of ordinary computers connected via an Ethernet or other
network.  Here memory is not shared; location 500 on one computer is
physically separate from one on another.  The software infrastructure,
the most popular of which is a library called MPI, consists of two
fundamental functions {\bf send()} and {\bf recv()} (plus other related
ones).  This kind of system will not be covered here.

\section{Threads}

The primary vehicle for programming multicore/SMP systems in via
threads, which are special OS processes, special in the sense that all
the threads in a program share the memory space in which the global
variables are stored.  

Each type of OS offers one or more {\it APIs}, Application Programmer
Interfaces, meaning library functions one calls to create and use
threads.  On Unix family systems, including Linux, the most popular API
library is {\bf pthreads}.

\subsection{What Is Shared and What Is Not}

So the global variables are shared among the threads.  However, each
core has its own stack pointer register, and each thread will have its
stack pointer pointed to a different place in the shared memory.  So the
threads have separate stacks, and separate local variables.

Since the threads have separate PC registers (EIP on Intel), different
threads will in general be executing at different points in our
program.\footnote{Though this is not the case of GPUs}

Note that we are still in a timeshared system.  Just as with regular
processes, the OS will assign a thread to a core dynamically.  When a
thread's turn is up, the thread may be running on a different core when
its next turn comes.  In some systems, the programmer has some control
over this, though, by specifying thread {\it affinity}.

\subsection{Really?  It's OK to Use Global Variables?}

This will require some adjustment for those who've been taught that
global variables are ``evil.''  

All communication between threads is done via global
variables.\footnote{Technically one could use locals in {\bf main()} (or
whatever function it is where the threads are credated) for this
purpose, but this would be so unwieldy that it is seldom done.} So even
if you consider globals to be evil, they are a necessary evil in threads
programming.  

Personally I have always thought the stern admonitions against global
variables are overblown anyway; see
\url{http://heather.cs.ucdavis.edu/~matloff/globals.html}.  But as
mentioned, those admonitions are routinely ignored in threaded
programming.  For a nice discussion on this, see the paper by a famous
MIT computer scientist on an Intel Web page, at
\url{http://software.intel.com/en-us/articles/global-variable-reconsidered/?wapkw=%28parallelism%29}.

\subsection{Sample Pthreads Program}
\label{primes}

In order to motivate the hardware issues to be discussed in this
chapter, we first consider a sample threads program.  

Here is a threads program that does involve computation, involving
counting prime numbers.  It's not the most efficient possible prime
finder, but it will illustrate the principles.

\begin{lstlisting}[numbers=left]
// PrimesThreads.c

// threads-based program to find the number of primes between 2 and n;
// uses the Sieve of Eratosthenes, deleting all multiples of 2, all
// multiples of 3, all multiples of 5, etc. 

// for illustration purposes only; NOT claimed to be efficient

// Linux compilation:  gcc -g -o primesthreads PrimesThreads.c -lpthread -lm

// usage:  primesthreads n num_threads

#include <stdio.h>
#include <math.h>
#include <pthread.h>  // required for threads usage

#define MAX_N 100000000
#define MAX_THREADS 25

// shared variables
int nthreads,  // number of threads (not counting main())
    n,  // range to check for primeness
    prime[MAX_N+1],  // in the end, prime[i] = 1 if i prime, else 0
    nextbase;  // next sieve multiplier to be used
// lock for the shared variable nextbase
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;
// ID structs for the threads
pthread_t id[MAX_THREADS];

// "crosses out" all odd multiples of k
void crossout(int k)
{  int i;
   for (i = 3; i*k <= n; i += 2)  {
      prime[i*k] = 0;
   }
}

// each thread runs this routine
void *worker(int tn)  // tn is the thread number (0,1,...)
{  int lim,base,
       work = 0;  // amount of work done by this thread
   // no need to check multipliers bigger than sqrt(n)
   lim = sqrt(n);
   do  {
      // get next sieve multiplier, avoiding duplication across threads
      // lock the lock
      pthread_mutex_lock(&nextbaselock);
      base = nextbase;
      nextbase += 2;
      // unlock
      pthread_mutex_unlock(&nextbaselock);
      if (base <= lim)  {
         // don't bother crossing out if base known composite
         if (prime[base])  {
            crossout(base);
            work++;  // log work done by this thread
         }
      }
      else return work; 
   } while (1);
}

main(int argc, char **argv)
{  int nprimes,  // number of primes found 
       i,work;
   n = atoi(argv[1]);
   nthreads = atoi(argv[2]);
   // mark all even numbers nonprime, and the rest "prime until
   // shown otherwise"
   for (i = 3; i <= n; i++)  {
      if (i%2 == 0) prime[i] = 0;
      else prime[i] = 1;
   }
   nextbase = 3;
   // get threads started
   for (i = 0; i < nthreads; i++)  {
      // this call says create a thread, record its ID in the array
      // id, and get the thread started executing the function worker(), 
      // passing the argument i to that function
      pthread_create(&id[i],NULL,worker,i);
   }

   // wait for all done
   for (i = 0; i < nthreads; i++)  {
      // this call says wait until thread number id[i] finishes
      // execution, and to assign the return value of that thread to our
      // local variable work here
      pthread_join(id[i],&work);
      printf("%d values of base done\n",work);
   }
   
   // report results
   nprimes = 1;
   for (i = 3; i <= n; i++)
      if (prime[i])  {
         nprimes++;
      }
   printf("the number of primes found was %d\n",nprimes);

}
\end{lstlisting}

To make our discussion concrete, suppose we are running this program
with two threads on a dual core machine.  Suppose also that both threads
are running simultaneously most of the time.  This will occur if they if
there are no other big threads.  (Actually, the original thread is {\bf
main()}, but it lies dormant most of the time, as you'll see.)

Note the global variables:

\begin{lstlisting}
int nthreads,  // number of threads (not counting main())
    n,  // range to check for primeness
    prime[MAX_N+1],  // in the end, prime[i] = 1 if i prime, else 0
    nextbase;  // next sieve multiplier to be used
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;
pthread_t id[MAX_THREADS];
\end{lstlisting}

As mentioned earlier, the globals are shared by all threads, but each
thread has its own stack space, thus its own locals.  If one thread,
for instance, assigns the value 0 to {\bf prime{[}35{]}} in the function
{\bf crossout()}, then that variable will have the value 0 when accessed
by any of the other processors as well.  On the other hand, the variable
{\bf i} in {\bf crossout()} has a different value at each thread.

Note that in the statement

\begin{lstlisting}
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;
\end{lstlisting}

the right-hand side is not a constant.  It is a macro call, and is thus
something which is executed.

In the code

\begin{lstlisting}
pthread_mutex_lock(&nextbaselock);
base = nextbase
nextbase += 2
pthread_mutex_unlock(&nextbaselock);
\end{lstlisting}

we see a \textbf{critical section} operation which is typical in
shared-memory programming, as noted in Section \ref{threadsintro}.  In
this context here, it means that we cannot allow more than one thread to
execute

\begin{lstlisting}
base = nextbase;
nextbase += 2;
\end{lstlisting}

at the same time.  We say that the actions in the critical section must
be done {\it atomicly}, meaning not divisible among threads.  The calls
to {\bf pthread\_mutex\_lock()} and {\bf pthread\_mutex\_unlock()}
ensure this.\footnote{The term {\it mutex} stands for ``mutual
exclusion.''}  If thread A is currently executing inside the critical
section and thread B tries to lock the lock by calling {\bf
pthread\_mutex\_lock()}, the call will block at thread B until thread 
A executes {\bf pthread\_mutex\_unlock()}.

As will be seen later, there are other operations that are different
from locks but which have the same goal, of atomic access to critical
sections.  The general term is to call all such operations {\bf
synchronization}.

Here is why this is so important:  Say currently {\bf nextbase} has the
value 11.  What we want to happen is that the next thread to read {\bf
nextbase} will ``cross out'' all multiples of 11.  But if we allow
two threads to execute the critical section at the same time, problems
may occur, as follows.

The C statement

\begin{lstlisting}
nextbase += 2;
\end{lstlisting}

will likely compile to two or three machine instructions.  For instance,
on a 32-bit Intel machine, I found that it compiled to this:

\begin{lstlisting}
movl nextbase, %eax  # instruction 1
movl %eax, -20(%ebp)  # instruction 2, setting base
addl $2, %eax  # instruction 3
movl %eax, nextbase  # instruction 4
\end{lstlisting}

Then we could have the following scenario with two threads, A and B:

\begin{itemize}

\item A executes instructions 1 and 2, setting its EAX and
its {\bf base} to 11

\item A executes instruction 3; A's EAX contains
13, but {\bf nextbase} is still 11

\item A's turn ends and B's turn begins

\item B, which had been executing at some place far from the critical
section, eventually reaches that section

\item B executes instructions 1 and 2, setting its EAX and
its {\bf base} to 11

\item B executes instructions 3 and 4; {\bf nextbase} becomes 13

\item B crosses out multiples of 11

\item B's turn ends and A's turn begins

\item A executes instruction 4; {\bf nextbase} stays at 13
since thread A still had 13 in its EAX

\item A (needlessly) crosses out multiples of 11

\end{itemize}

So, both threads would do ``crossing out'' of multiples of 11.  Thus
lack of locks would result in  duplicating work and thus a slowing down
of execution speed.  

In the above scenario, we at least would not result in incorrect results.
However, think of a program that, say, counts 2s in a huge array, with
each thread being responsible for counting 2s in some chunk of the
array.  

\label{count2s}

More specifically, say the array is of length {\bf n}, we have {\bf nth}
threads, and that the latter evenly divides the former.  With various
quantities stored as globals, the code executed by each thread might
look like this:

\begin{lstlisting}
void *worker(int tn)  // tn is the thread number (0,1,...,nth-1)
{  int i, mycount = 0;
   int chunksize = n / nth;
   for (i = tn*chunksize; i < (tn+1)*chunksize; i++)
      if (x[i] == 2) mycount++;      
   pthread_mutex_lock(&nextbaselock);
   overallcount += mylocalcount;
   pthread_mutex_unlock(&nextbaselock);
}
\end{lstlisting}

Without the locks, a scenario similar to that outlined above for the
primes program could result in an undercount, with the final value of
{\bf overallcount} being too low.

Note that all this could occur even if we have a multicore systems.
Thus the locks can be icrucial to correct and speedy execution of a
threaded programs.

This problem frequently arises in parallel database systems.  For
instance, consider an airline reservation system. If a flight has only
one seat left, we want to avoid giving it to two different customers who
might be talking to two agents at the same time. The lines of code in
which the seat is finally assigned (the \textbf{commit} phase, in
database terminology) is then a critical section.

A critical section is always a potential bottleneck in a parallel
program, because its code is serial instead of parallel.  In our program
here, we may get better performance by having each thread work on, say,
five values of {\bf nextbase} at a time.  Our line

\begin{lstlisting}
nextbase += 2;
\end{lstlisting}

would become

\begin{lstlisting}
nextbase += 10;
\end{lstlisting}

(We would still have locks surrounding the critical section.)

That would mean that any given thread would need to go through the
critical section only one-fifth as often, thus greatly reducing
overhead.  

On the other hand, near the end of the run, this may result in some
threads being idle while other threads still have a lot of work to
do---a {\it load balance} problem.

Note this code.

\begin{lstlisting}
for (i = 0; i < nthreads; i++)  {
   pthread_join(id[i],&work);
   printf("%d values of base done\n",work);
}
\end{lstlisting}

This is a special case of of {\it barrier}.

A barrier is a point in the code that all threads must reach before
continuing.  In this case, a barrier is needed in order to prevent
premature execution of the later code, but in most cases they are used
to coordinate threads in the midst of a program.  Barriers are very
common in shared-memory programming. 

Here is an example of pthreads' built-in barrier function.  

\begin{lstlisting}
// illustrates use of a barrier instead of pthread_join() (not
// preferable, just an example)

// the goal of the code is to find the sum of elements in an array

#include <stdio.h>
#include <pthread.h>  // required for threads usage

#define MAX_N 100000000
#define MAX_THREADS 25

// shared variables
int nthreads,  // number of threads (not counting main())
    n,  
    x[MAX_N+1],
    sum = 0;  
pthread_mutex_t sumlock = PTHREAD_MUTEX_INITIALIZER;
// ID structs for the threads
pthread_t id[MAX_THREADS];
pthread_barrier_t barr;

// each worker sums its chunk of x, with x's length n assumed to be a
// multiple of nthreads
void *summer(int tn)  // tn is the thread number (0,1,...)
{  int i, chunksize = n/nthreads;
   int mysum = 0;
   for (i = tn*chunksize; i < (tn+1)*chunksize; i++)
      mysum += x[i];
   pthread_mutex_lock(&sumlock);
   sum += mysum;
   pthread_mutex_unlock(&sumlock);
   pthread_barrier_wait(&barr);
}

main(int argc, char **argv)
{  int nprimes,  // number of primes found 
       i,work;
   n = atoi(argv[1]);
   nthreads = atoi(argv[2]);
   // we'll be having the thread-creating function use the barrier too,
   // so count it in the barrier init
   pthread_barrier_init(&barr,NULL,nthreads+1); 
   for (i = 0; i < n; i++)  
      x[i] = i*i*i % 5;  // just a test
   for (i = 0; i < nthreads; i++)  {
      pthread_create(&id[i],NULL,summer,i);
   }
   pthread_barrier_wait(&barr);
   printf("the array sum was %d\n",sum);
}
\end{lstlisting}

\subsection{Debugging Threaded Programs}

See Section \ref{debugthreads}.

\subsection{Higher-Level Threads Programming}

Threads programming, e.g. surrounding critical sections by lock/unlock
code, can become tedious and error-prone.  So it is common to write a
higher level; the current standard for multicore is the OpenMP library,
which handles all the thread details for you.

The OpenMP library gives the programmer a higher-level view of
threading.  The threads are there, but rather hidden by higher-level
abstractions.  However, it is beyond the scope of this book.

\section{``Embarrassingly Parallel'' Applications}

As noted, the use of locks in our primes-counting code above is a
potentially major source of slowdown.  Many refinements could be made to
reduce the locks overhead, but the point is that the frequent access to
locks is a recurring problem in parallel applications.

There are many other applications, though, in which locks play a quite
minimal role.  They are generally terms {\it embarrassingly parallel}.
Technically, the term actually means something else; it refers to
applications that are so easy to parallelize that it's ``embarrassing''
to the programmer, since there is no challenge to them.  But the term
later evolved (or devolved) to mean applications in which very little
synchronization is performed.

An example is matrix multiplication.  Suppose we are multiplying a
vector X by a matrix A.  Since the i$^{th}$ component of the overall
product is equal to the product of the i$^{th}$ row of A with X, the
computation of AX is very easily parallelized:  Say we have k threads,
and that A has n rows Then have thread 0 handle the first n/k rows of A,
thread 1 handle the next n/k rows, and so on.  The only synchronization
needed would be a barrier operation at the end.

Much of the discussion of parallel hardware and software revolves around
the question of how it performs on non-embarrassingly parallel
applications.

\section{Hardware Support for Critical Section Access}

In shared memory programming, the handling of critical sections, lock
variables and the like play a vital role in performance.  Remember, a
critical section in effect serializes the program if many threads are
waiting to enter it at the same time.  Thus fast handling of critical
sections is important, and most processors have some support for that.

\subsection{Test-and-Set Instructions}

Consider a bus-based system. In addition to whatever memory read and
memory write instructions the processor included, there will be a TAS
instruction, or one or more similar instructions.\footnote{This
discussion is for a mythical machine, but any real system works
essentially in this manner.}  This instruction controls a TAS pin on the
processor chip, and the pin in turn is connected to a TAS line on the
bus.

Applied to a location L in memory and a register R, say, TAS does the
following:

\begin{lstlisting}
   copy L to R
   if R is 0 then write 1 to L
\end{lstlisting}

And most importantly, these operations are done in an \textbf{atomic}
manner; no bus transactions by other cores may occur between the
two steps.

The TAS operation is applied to variables used as locks. Let's say that
1 means locked and 0 unlocked. Then the guarding of a critical section C
by a lock variable L, using a register R, would be done by having the
following code in the program being run:

\begin{lstlisting}
   TRY:  TAS R,L
         JNZ TRY  ; TAS result in flags register
     C:  ...   ; start of critical section
         ...
         ...   ; end of critical section
         MOV 0,L  ; unlock
\end{lstlisting}

where of course JNZ is a jump-if-nonzero instruction, and we are
assuming that the copying from the Memory Data Register to R results in
the core's N and Z flags (condition codes) being affected.

\subsubsection{LOCK Prefix on Intel Processors}
\label{lockprefix}

On Pentium machines, the LOCK prefix can be used to get atomicity for
certain instructions:  ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, DEC, INC,
NEG, NOT, OR, SBB, SUB, XOR, XADD.  The bus will be locked for the
duration of the execution of the instruction, thus setting up atomic
operations.  There is a special LOCK line in the control bus for this
purpose.  (Locking thus only applies to these instructions in forms in
which there is an operand in memory.) By the way, XCHG asserts this
LOCK\# bus signal even if the LOCK prefix is not specified.

For example, consider our count-the-2s example on  page
\pageref{count2s}.  If we store {\bf mycount} in a register, say EDX,
then

\begin{lstlisting}
lock add %edx, overallcount
\end{lstlisting}

would replace the code we had earlier,

\begin{lstlisting}
pthread_mutex_lock(&nextbaselock);
overallcount += mylocalcount;
pthread_mutex_unlock(&nextbaselock);
\end{lstlisting}

without locks!

Here is how we could implement a lock if needed.  The lock would be in a
variable named, say, {\bf lockvar}.

\begin{lstlisting}
   movl $lockvar, %ebx
   movl $1, %ecx
top:
   movl $0, %eax
   lock cmpxchg (%ebx), %ecx
   jz top  # else leave the loop and enter the critical section
\end{lstlisting}

The operation CMPXCHG has EAX as an unnamed operand.  The instruction
basically does (here {\bf source} is ECX and {\bf destination} is {\bf
lockvar})

\begin{lstlisting}
if c(EAX) != c(destination)  # sorry, lock is already locked
   c(EAX) <- c(destination)
   ZF <- 0  # the Zero Flag in the EFLAGS register
else
   c(destination) <- c(source)  # lock the lock
   ZF <- 1
\end{lstlisting}

The LOCK prefix locks the bus for the entire duration of the
instruction.  Note that the ADD instruction here involves two memory
transactions---one to read the old value of {\bf overallcount}, and the
second the write the new, incremented value back to {\bf overallcount}.
So, we are locking for a rather long time, potentially compromising
performance when other threads want to access memory, but the benefits
can be huge.

\subsubsection{Synchronization Operations on the GPU}

The lockstep-within-SM  nature of the GPU makes lock operations of the
sort we've been examining infeasible.  There are indeed across-SM
operations for synchronization, such as one for atomic addition, working
similar to the Intel LOCK ADD example above.  However, they are very slow.

At the within-SM level, synchronization is available in the form of
barriers.  These are fairly efficient, but again, available only within
SMs.

For these reasons, it's very difficult to parallelize non-embarrassingly
parallel applications with GPUs.  

\section{Memory Issues}

Many times a scientist, engineer, economist, statistician, sociologist
etc. has eagerly sat down to write his/her first parallel program, and
to be horrified to find that it actually runs more slowly than the
serial version!  In most such cases, the primary culprit underlying the
poor performance involves memory.  

\subsection{Overview of the Problems}

Problems arising for multicore/SMP systems include:

\begin{itemize}

\item {\it bus contention:}  Two or more threads try to access memory
(though possibly in different memory modules) at the same
(near-)instant, thus all needing the bus at the same time, causing
some serialization.

\item {\it memory module contention:}  One or more threads try to access
the same memory module while it is still busy processing the prior
request of another thread.  The bus is free, but the memory module
isn't.  Again, the result is some serialization.

\item {\it cache coherency transactions:}  One or more cores discovers
that its local cache is inconsistent with the up-to-date values held in
either main memory or in the cache of another core.  As with any cache
update procedure, a very large amount of bus traffic is generated, thus
severely slowing performance during that period.

\item {\it false sharing:}  Say two of our program variables, {\bf x}
and {\bf y}, have no relation to each other, but happen to be stored in
the same cache line.  Suppose a thread writes to {\bf x}, without
touching {\bf y}.  Then the entire cache line at that core will be
invalidated---with the consequence that {\bf y} is now considered
invalid at the other threads, even though it is perfectly fine.  If
another thread needs to read {\bf y}, that thread's core will need to go
through a cache coherency transaction, which as noted above can really
slow things down.

\end{itemize}

In the GPU case, problems can include:

\begin{itemize}

\item {\it bank conflicts:}  In the old days, memory modules
were called {\it banks}.  The designers of the GPU revived this term.
At any rate, putting terminology aside, what problems can occur?

Once again, the lockstep nature of SMs is key:  Each thread executes the
same instruction at the same time, but accessing different memory
locations.  So, many memory locations are accessed at once.  If they are
all in different banks (better, all are to consecutive words), all those
accesses can be done simultaneously (due to the DRAM construction of
memory); if not, then some serialization occurs.

\item {\bf ``cache misses'':}  The memory shared by all threads in all
SMs is called {\it global memory}.  Depending on the model of GPU, each
SM may have a cache, but on any model, each SM also has a
programmer-managed cache named {\it shared memory}.  (The terminology is
confusing, but the word {\it shared} refers to the fact that all threads
in that SM share it.)  Shared memory is much faster than global memory,
but it is also very small.  Thus the programmer may write code which
moves data back and forth between the two levels of memory, thus causing
a slowdown.

\end{itemize}

The programmer can often refine the program to ameliorate these
problems, though in some applications it may be difficult.

\subsection{Memory Interleaving}
\label{interleaving1}

Here we address (pun intended) the issue of how addresses are assigned
to memory modules.

Most systems today do this via {\it low-order interleaving}.   Here
consecutive addresses assigned to consecutive banks (except when we get
to the right end).  For example, suppose for simplicity that our memory
consists of word-addresses 0 through 1023, and that there are four
banks, M0 through M3.  Then word-address 0 would be in M0, 1 would be in
M1, 2 would be in M2, 3 would be in M3, 4 would be back in M0, 5 in M1,
and so on.  

In terms of bus connections:  Again for simplicity, assume that
consecutive words have consecutive addresses (i.e. bytes within words
don't have addresses).  Since the address space of the system consists
of $2^{10} = 1024$ words, we would have lines A0-A9 in the address bus.
Each module would consist of $2^8 = 256$ words, connected to lines
A2-A9.  Lines A0-A1 would then be used to activate the correct module.

All this impacts the way we write our applications code.  We want to
avoid bus contention, and sometimes proper arrangement of data
structures can help in this regard.

As a simple illustration, think of the toy 4-module example above, with
4 cores.  (It is typical to have as many modules as cores, the idea
being to keep all modules busy.)

Suppose we have a C array of 10 rows and 4 columns, and consider two
ways to traverse the entire array---row-by-row or column-by-column, say
to find the sum of all the elements in the array.  Say we have 4 threads
running.  Here is the row-by-row version, with {\bf thrnum} being the
thread's thread number and {\bf sum} being global:

\begin{lstlisting}
sum = 0;
for (i = 0; i < 10; i++) {
   myj = thrnum;
   sum += x[i][thrnum];
}
\end{lstlisting}

This is meshing perfectly with the interleaving, and at least in the GPU
case it should produce good performance.  The corresponding
column-by-column version would have terrible performance:  There would
be maximal clashes at every access.

The restriction to the GPU in the preceding paragraph is due to the
lockstep nature.  We know that the machine instructions corresponding to
the line

\begin{lstlisting}
sum += x[i][thrnum];
\end{lstlisting}

will execute simultaneously, and thus the memory accesses will occur
simultaneously.  On a multicore/SMP machine, the execution is
asynchronous, and the effects less clear.

\subsubsection{Implications for the Number of Threads to Run}

When one writes code for any of these systems, the question then arises
at run time as to how many threads to run.  

Recall that for pthreads, this is done by setting an environment
variable.  For instance, on a Linux system running the C shell, to set
up 8 threads we would give this command in the shell:

\begin{lstlisting}
% setenv OMP_NUM_THREADS 8
\end{lstlisting}

For a GPU, it's more complicated, as one needs to decide both the number
of threads per {\it block}, and the number of blocks overall.  (We don't
define the term {\it block} here, nor will we show code in CUDA, an
extension of C that is NVIDIA's main vehicle for writing GPU code.) The
point here, though, is that one must make such decisions.

On a multicore/SMP system, it seems reasonable to set the number of
threads equal to the number of cores.  This way all cores should be kept
busy.  Actually, sometimes it is helpful to run slightly more threads
than cores, since on occasion one thread may be in the midst of a
virtual memory page fault (Chapter \ref{chap:osmemio}) and thus its core
may be free to work on another thread.

By contrast, the designers of the GPU intend one to run many more
threads than cores.  The reason for this is that the GPU global memory
has very long {\it latency}, the time it takes one bit to get from the
GPU global memory to/from a core.  When the mini-OS in the GPU hardware
notices that the current set of threads has just submitted a request to
global memory, the mini-OS will do a context switch, having a different
set of threads run during the long delay of the memory request of the
previous set.  Hence, one should set up lots of threads, so that the
mini-OS can always find something to run.

\section{To Learn More}

Much more material on parallel processing (including the message-passing
case) is available in my open source book on the subject, at
\url{http://heather.cs.ucdavis.edu/parprocbook}.

