modif chap1

[book_gpu.git] / BookGPU / Chapters / chapter1 / ch1.tex

diff --git a/BookGPU/Chapters/chapter1/ch1.tex b/BookGPU/Chapters/chapter1/ch1.tex
index 9a3f4eb1180739700d4355eb6d6dc428afdfbe3b..42b018cf4686083d2f1c774f10f74cc4600a8a29 100755 (executable)
--- a/BookGPU/Chapters/chapter1/ch1.tex
+++ b/BookGPU/Chapters/chapter1/ch1.tex
@@ -10,7 +10,11 @@ This chapter introduces the Graphics  Processing Unit (GPU) architecture and all
 the concepts needed to understand how GPUs  work and can be used to speed up the
 execution of some algorithms. First of all this chapter gives a brief history of
 the development of Graphics card until they can be used in order to make general
 the concepts needed to understand how GPUs  work and can be used to speed up the
 execution of some algorithms. First of all this chapter gives a brief history of
 the development of Graphics card until they can be used in order to make general

-purpose computation.
+purpose computation.  Then  the architecture of a GPU  is illustrated. There are
+many fundamental differences  between a GPU and a  tradition processor. In order
+to benefit from the power of a GPU, a CUDA programmer needs to use threads. They
+have  some particularities  which enables  the CUDA  model to  be  efficient and
+scalable when some constraints are addressed.

 
 
 
 
 
 


@@ -23,9 +27,9 @@ repetitive and very specific.  Hence,  some manufacturers have produced more and
 more sofisticated video cards, providing 2D accelerations then 3D accelerations,
 then some  light transforms. Video cards  own their own memory  to perform their
 computation.  From  at least two dedaces,  every personnal computer  has a video
 more sofisticated video cards, providing 2D accelerations then 3D accelerations,
 then some  light transforms. Video cards  own their own memory  to perform their
 computation.  From  at least two dedaces,  every personnal computer  has a video

-card which a  simple for desktop computers or  which provides many accelerations
+card which is  simple for desktop computers or  which provides many accelerations

 for game  and/or graphic oriented computers.  In the latter  case, graphic cards
 for game  and/or graphic oriented computers.  In the latter  case, graphic cards

-may be more expensive than the CPU.
+may be more expensive than a CPU.

 
 After 2000,  video cards allowed to apply  arithmetics operations simulatenously
 on a  sequence of  pixels, also  later called stream  processing. In  this case,
 
 After 2000,  video cards allowed to apply  arithmetics operations simulatenously
 on a  sequence of  pixels, also  later called stream  processing. In  this case,


@@ -33,7 +37,7 @@ information of the  pixels (color, location and other  information) are combined
 in   order  to   produce   a  pixel   color   that  can   be   displayed  on   a
 screen.  Simultaneous  computations  are  provided by  shaders  which  calculate
 rendering effects on graphics hardware  with a high degree of flexibility. These
 in   order  to   produce   a  pixel   color   that  can   be   displayed  on   a
 screen.  Simultaneous  computations  are  provided by  shaders  which  calculate
 rendering effects on graphics hardware  with a high degree of flexibility. These

-shaders handles the stream data with pipelines
+shaders handles the stream data with pipelines.

 
 
 Some reasearchers  tried to apply  those operations on other  data, representing
 
 
 Some reasearchers  tried to apply  those operations on other  data, representing


@@ -70,12 +74,13 @@ comparison with OpenCL, interested readers may refer to~\cite{ch1:CMR:12}.
 
 \section{Architecture of current GPUs}
 
 
 \section{Architecture of current GPUs}
 

-Architecure  of current GPUs  is constantly  evolving. Nevertheless  some trends
-remains true  through this evolution. Processing  units composing a  GPU are far
-more simpler  than a  traditional CPU but  it is  much easier to  integrate many
-computing units inside a  GPU card than many cores inside a  CPU. This is due to
-the fact that cores  of a GPU a simpler than cores of a  CPU.  In 2012, the most
-powerful  GPUs own  more  than  500 cores  and  the most  powerful  CPUs have  8
+Architecture  \index{Architecture  of  a  GPU}  of current  GPUs  is  constantly
+evolving.    Nevertheless    some    trends    remains   true    through    this
+evolution.  Processing  units  composing a  GPU  are  far  more simpler  than  a
+traditional CPU but it is much easier to integrate many computing units inside a
+GPU card than many  cores inside a CPU. This is due to the  fact that cores of a
+GPU are simpler than  cores of a CPU.  In 2012, the  most powerful GPUs own more
+than     500    cores     and    the     most    powerful     CPUs     have    8

 cores. Figure~\ref{ch1:fig:comparison_cpu_gpu} shows  the number of cores inside
 a  CPU  and  inside a  GPU.   In  fact,  in  a  current NVidia  GPU,  there  are
 multiprocessors which have 32 cores (for example on Fermi cards). The core clock
 cores. Figure~\ref{ch1:fig:comparison_cpu_gpu} shows  the number of cores inside
 a  CPU  and  inside a  GPU.   In  fact,  in  a  current NVidia  GPU,  there  are
 multiprocessors which have 32 cores (for example on Fermi cards). The core clock


@@ -99,7 +104,7 @@ get maximum performance.
 On most powerful  GPU cards, called Fermi, multiprocessors  are called streaming
 multiprocessors  (SM). Each  SM contains  32  cores and  is able  to perform  32
 floating point or integer operations on  32bits numbers per clock or 16 floating
 On most powerful  GPU cards, called Fermi, multiprocessors  are called streaming
 multiprocessors  (SM). Each  SM contains  32  cores and  is able  to perform  32
 floating point or integer operations on  32bits numbers per clock or 16 floating

-point  on  64bits number  per  clock. SM  have  their  own registers,  execution
+point  on  64bits number  per  clock. SMs  have  their  own registers,  execution

 pipelines and caches.  On Fermi architecture,  there are 64Kb shared memory + L1
 cache  and 32,536 32bits  registers per  SM. More  precisely the  programmer can
 decide what amount  of shared memory and  L1 cache SM can use.  The constaint is
 pipelines and caches.  On Fermi architecture,  there are 64Kb shared memory + L1
 cache  and 32,536 32bits  registers per  SM. More  precisely the  programmer can
 decide what amount  of shared memory and  L1 cache SM can use.  The constaint is


@@ -119,7 +124,9 @@ through  the  use  of  cache  memories. Moreover,  nowadays  CPUs  perform  many
 performance optimizations  such as speculative execution  which roughly speaking
 consists in executing  a small part of  code in advance even if  later this work
 reveals to  be useless. In  opposite, GPUs do  not have low latency  memory.  In
 performance optimizations  such as speculative execution  which roughly speaking
 consists in executing  a small part of  code in advance even if  later this work
 reveals to  be useless. In  opposite, GPUs do  not have low latency  memory.  In

-comparison GPUs have ridiculous cache memories. Nevertheless the architecture of GPUs is optimized for throughtput computation and it takes into account the memory latency.
+comparison GPUs have ridiculous cache memories. Nevertheless the architecture of
+GPUs  is optimized for  throughtput computation  and it  takes into  account the
+memory latency.

 
 
 
 
 
 


@@ -145,13 +152,13 @@ computation of other tasks.
 \section{Kinds of parallelism}
 
 Many  kinds  of parallelism  are  avaible according  to  the  type of  hardware.
 \section{Kinds of parallelism}
 
 Many  kinds  of parallelism  are  avaible according  to  the  type of  hardware.

-Roughtly  speaking,  there are  three  classes  of parallism:  instruction-level
-parallelism,   data  parallelism   and   task  parallelism.   
+Roughtly  speaking, there  are three  classes of  parallelism: instruction-level
+parallelism, data parallelism and task parallelism.

 
 Instruction-level parallelism consists in re-ordering some instructions in order
 
 Instruction-level parallelism consists in re-ordering some instructions in order

-to executed  some of them in parallel  without changing the result  of the code.
+to execute  some of them in parallel  without changing the result  of the code.

 In  modern CPUs, instruction  pipelines allow  processor to  execute instruction
 In  modern CPUs, instruction  pipelines allow  processor to  execute instruction

-faster.   With   a  pipeline  a  processor  can   execute  multiple  instruction
+faster.   With   a  pipeline  a  processor  can   execute  multiple  instructions

 simultaneously due  to the fact that  the output of a  task is the  input of the
 next one.
 
 simultaneously due  to the fact that  the output of a  task is the  input of the
 next one.
 


@@ -162,24 +169,28 @@ data parallelism paradigm. This paradigm  is linked with the Single Instructions
 Multiple Data  (SIMD) architecture. This is  the kind of  parallism providing by
 GPUs.
 
 Multiple Data  (SIMD) architecture. This is  the kind of  parallism providing by
 GPUs.
 

-Taks parallelism  is the common parallism  achieved out on cluster  and grid and
-high performance  architecture where different  tasks are executed  by different
+Taks parallelism is the common parallism  achieved out on clusters and grids and
+high performance  architectures where different tasks are  executed by different

 computing units.
 
 \section{CUDA Multithreading}
 
 The data parallelism  of CUDA is more precisely based  on the Single Instruction
 computing units.
 
 \section{CUDA Multithreading}
 
 The data parallelism  of CUDA is more precisely based  on the Single Instruction

-Multiple Thread (SIMT) model. This is due to the fact that the programmer access
+Multiple Thread (SIMT) model. This is due to the fact that a programmer accesses

 to  the cores  by the  intermediate of  threads. In  the CUDA  model,  all cores
 execute the  same set of  instructions but with  different data. This  model has
 similarities with vector programming  model proposed for vector machines through
 the  1970s into  the  90s, notably  the  various Cray  platforms.   On the  CUDA
 architecture, the  performance is  led by the  use of  a huge number  of threads
 (from thousand upto  to millions). The particularity of the  model is that there
 to  the cores  by the  intermediate of  threads. In  the CUDA  model,  all cores
 execute the  same set of  instructions but with  different data. This  model has
 similarities with vector programming  model proposed for vector machines through
 the  1970s into  the  90s, notably  the  various Cray  platforms.   On the  CUDA
 architecture, the  performance is  led by the  use of  a huge number  of threads
 (from thousand upto  to millions). The particularity of the  model is that there

-is no context switching as in CPUs and each thread has its own registers. In practice, threads are executed by SM and are gathered into groups of 32 threads. Those groups are call ``warps''. Each SM alternatively executes ``active warps'' and warps becoming temporaly inactive due to waiting of data (as shown in Figure~\ref{ch1:fig:latency_throughput}).
+is no  context switching as in  CPUs and each  thread has its own  registers. In
+practice,  threads  are executed  by  SM  and are  gathered  into  groups of  32
+threads.  Those  groups  are  call  ``warps''. Each  SM  alternatively  executes
+``active warps''  and warps becoming temporaly  inactive due to  waiting of data
+(as shown in Figure~\ref{ch1:fig:latency_throughput}).

 
 The key to scalability in the CUDA model is the use of a huge number of threads.
 
 The key to scalability in the CUDA model is the use of a huge number of threads.

-In practice threads are not only gathered  in warps but also in thread blocks. A
+In practice, threads are not only gathered  in warps but also in thread blocks. A

 thread block is executed  by only one SM and it cannot  migrate. Typical size of
 thread block is a number power of two (for example: 64, 128, 256 or 512).
 
 thread block is executed  by only one SM and it cannot  migrate. Typical size of
 thread block is a number power of two (for example: 64, 128, 256 or 512).
 


@@ -187,7 +198,7 @@ thread block is a number power of two (for example: 64, 128, 256 or 512).
 
 In this  case, without changing anything inside  a CUDA code, it  is possible to
 run your  code with  a small CUDA  device or  most performant Tesla  CUDA cards.
 
 In this  case, without changing anything inside  a CUDA code, it  is possible to
 run your  code with  a small CUDA  device or  most performant Tesla  CUDA cards.

-Blocks are  executed in any number depending  on the number of  SM available. So
+Blocks are  executed in any order depending  on the number of  SMs available. So

 the  programmer  must  conceive  its  code  having this  issue  in  mind.   This
 independence between threads blocks provides the scalability of CUDA codes.
 
 the  programmer  must  conceive  its  code  having this  issue  in  mind.   This
 independence between threads blocks provides the scalability of CUDA codes.
 


@@ -198,43 +209,56 @@ independence between threads blocks provides the scalability of CUDA codes.
 \end{figure}
 
 
 \end{figure}
 
 

-A kernel is a function which contains a block a instruction that are executed by
-threads of a GPU.  When the problem considered is a 2 dimensions or 3 dimensions
-problem,  it is  possible to  group thread  blocks into  grid. In  practice, the
-number of thread  blocks and the size  of thread block is given  in parameter to
-each  kernel.   Figure~\ref{ch1:fig:scalability}  illustrates  an example  of  a
-kernel composed  of 8  thread blocks. Then  this kernel  is executed on  a small
-device containing only 2 SMs. So in in  this case, blocks are executed 2 by 2 in
-any order.  If the kernel is executed  on a larger CUDA device containing 4 SMs,
-blocks  are executed  4  by 4  simultaneously.   The execution  times should  be
+A kernel is a function which  contains a block of instructions that are executed
+by the  threads of a GPU.   When the problem considered  is a 2  dimensions or 3
+dimensions  problem,  it is  possible  to group  thread  blocks  into grid.   In
+practice, the number of  thread blocks and the size of thread  block is given in
+parameter  to  each  kernel.   Figure~\ref{ch1:fig:scalability}  illustrates  an
+example of a kernel composed of 8 thread blocks. Then this kernel is executed on
+a small device containing only 2 SMs.  So in in this case, blocks are executed 2
+by 2 in any order.  If the kernel is executed on a larger CUDA device containing
+4 SMs, blocks are executed 4 by 4 simultaneously.  The execution times should be

 approximately twice faster in the latter  case. Of course, that depends on other
 parameters that will be described later.
 
 Thread blocks provide a way to cooperation  in the sens that threads of the same
 block   cooperatively    load   and   store   blocks   of    memory   they   all
 use. Synchronizations of threads in the same block are possible (but not between
 approximately twice faster in the latter  case. Of course, that depends on other
 parameters that will be described later.
 
 Thread blocks provide a way to cooperation  in the sens that threads of the same
 block   cooperatively    load   and   store   blocks   of    memory   they   all
 use. Synchronizations of threads in the same block are possible (but not between

-thread of different blocks). Threads of the same block can also share results in
-order to compute a single  result. In chapter~\ref{chapter2}, some examples will
-explicit that.
+threads of different  blocks). Threads of the same block  can also share results
+in order  to compute a  single result. In chapter~\ref{chapter2},  some examples
+will explicit that.

 
 
 \section{Memory hierarchy}
 
 
 
 \section{Memory hierarchy}
 

-The memory  hierarchy of GPUs  is different from  the one of CPUs.  In practice,
-there is registers, local memory, shared memory, cache memroy and global memory.
+The memory hierarchy of  GPUs\index{Memory~hierarchy} is different from the CPUs
+one.  In practice,  there are registers\index{Memory~hierarchy!registers}, local
+memory\index{Memory~hierarchy!local~memory},                               shared
+memory\index{Memory~hierarchy!shared~memory},                               cache
+memory\index{Memory~hierarchy!cache~memory}              and              global
+memory\index{Memory~hierarchy!global~memory}.
+

 
 As  previously  mentioned each  thread  can access  its  own  registers.  It  is
 important to keep in mind that the  number of registers per block is limited. On
 recent cards,  this number is  limited to 64Kb  per SM.  Access to  registers is
 very fast, so when possible it is a good idea to use them.
 
 
 As  previously  mentioned each  thread  can access  its  own  registers.  It  is
 important to keep in mind that the  number of registers per block is limited. On
 recent cards,  this number is  limited to 64Kb  per SM.  Access to  registers is
 very fast, so when possible it is a good idea to use them.
 

-Likewise each thread can access local  memory which in practice much slower than
-registers.  In practice, local memory is automatically used by the compiler when
-all the  registers are  occupied. So  the best idea  is to  optimize the  use of
-registers even if this implies to reduce the number of threads per block. 
+Likewise each thread can access local  memory which, in practice, is much slower
+than registers.  Local memory is automatically used by the compiler when all the
+registers are  occupied. So the  best idea is  to optimize the use  of registers
+even if this implies to reduce the number of threads per block.
+
+\begin{figure}[hbtp!]
+\centerline{\includegraphics[scale=0.60]{Chapters/chapter1/figures/memory_hierarchy.pdf}}
+\caption[Memory hierarchy of a GPU]{Memory hierarchy of a GPU.}
+\label{ch1:fig:memory_hierarchy}
+\end{figure}
+
+

 
 Shared memory allows  cooperation between threads of the  same block.  This kind
 
 Shared memory allows  cooperation between threads of the  same block.  This kind

-of memory  is fast by  it requires  to be manipulated  manually and its  size is
+of memory is fast because it requires to be manipulated manually and its size is

 limited.  It is accessible during the execution of a kernel. So the principle is
 to fill the shared  memory at the start of the kernel  with global data that are
 used very  frequently, then threads can  access it for  their computation.  They
 limited.  It is accessible during the execution of a kernel. So the principle is
 to fill the shared  memory at the start of the kernel  with global data that are
 used very  frequently, then threads can  access it for  their computation.  They


@@ -248,11 +272,7 @@ shared memory is attributed to a kernel. The cache memory is a L1 cache which is
 directly  managed by  the GPU.  Sometimes,  this cache  provides very  efficient
 result and sometimes the use of shared memory is a better solution.
 
 directly  managed by  the GPU.  Sometimes,  this cache  provides very  efficient
 result and sometimes the use of shared memory is a better solution.
 

-\begin{figure}[b!]
-\centerline{\includegraphics[scale=0.60]{Chapters/chapter1/figures/memory_hierarchy.pdf}}
-\caption[Memory hierarchy of a GPU]{Memory hierarchy of a GPU.}
-\label{ch1:fig:memory_hierarchy}
-\end{figure}
+

 
 
 Figure~\ref{ch1:fig:memory_hierarchy}  illustrates  the  memory hierarchy  of  a
 
 
 Figure~\ref{ch1:fig:memory_hierarchy}  illustrates  the  memory hierarchy  of  a


@@ -262,6 +282,13 @@ the shared memory of this block. The cache memory is not represented here but it
 is local  to a thread. Then  each block can access  to the global  memory of the
 GPU.
 
 is local  to a thread. Then  each block can access  to the global  memory of the
 GPU.
 

+ \section{Conclusion}
+
+In this chapter,  a brief presentation of the video card,  which later have been
+used to perform computation, has been  given. The architecture of a GPU has been
+illustrated focusing on the particularity of GPUs in term of parallelism, memory
+latency and  threads. In order to design  an efficient algorithm for  GPU, it is
+essential to have all these parameters in mind.

 
 %%http://people.maths.ox.ac.uk/gilesm/pp10/lec2_2x2.pdf
 %%https://people.maths.ox.ac.uk/erban/papers/paperCUDA.pdf
 
 %%http://people.maths.ox.ac.uk/gilesm/pp10/lec2_2x2.pdf
 %%https://people.maths.ox.ac.uk/erban/papers/paperCUDA.pdf