new

[book_gpu.git] / BookGPU / Chapters / chapter10 / ch10.tex

diff --git a/BookGPU/Chapters/chapter10/ch10.tex b/BookGPU/Chapters/chapter10/ch10.tex
index 2664ff0afea083345dbe7145e4f5f7da707556eb..37a8ba17bc8ccbdee779eba59480327f14f44e63 100644 (file)
--- a/BookGPU/Chapters/chapter10/ch10.tex
+++ b/BookGPU/Chapters/chapter10/ch10.tex
@@ -30,7 +30,7 @@ Finally, we summarize the results obtained and consider new perspectives.
 
 \section{Simplex algorithm}
 \label{chXXX:sec:simplex-algo}
 
 \section{Simplex algorithm}
 \label{chXXX:sec:simplex-algo}

-\subsection{Linear programming model\index{Linear programming}}
+\subsection{Linear programming model\index{linear programming}}

 \label{chXXX:subsec:lp-model}
 %% Mathematics of LP
 An LP model in its canonical form can be expressed as the following optimization problem:
 \label{chXXX:subsec:lp-model}
 %% Mathematics of LP
 An LP model in its canonical form can be expressed as the following optimization problem:


@@ -53,7 +53,7 @@ An optimal solution to the LP problem will therefore reside on a vertex of this
 \subsection{Standard simplex algorithm}
 \label{chXXX:subsec:simplex-std}
 % Simple explanation of the simple algorithm : 3 operations
 \subsection{Standard simplex algorithm}
 \label{chXXX:subsec:simplex-std}
 % Simple explanation of the simple algorithm : 3 operations

-The simplex method\index{Simplex!Standard method}~\cite{VCLP} is an algorithm for solving LP models. 
+The simplex method\index{simplex!standard method}~\cite{VCLP} is an algorithm for solving LP models. 

 It proceeds by iteratively visiting vertices on the boundary of the feasible region.
 This amounts to performing algebraic manipulations on the system of linear equations.
 
 It proceeds by iteratively visiting vertices on the boundary of the feasible region.
 This amounts to performing algebraic manipulations on the system of linear equations.
 


@@ -193,7 +193,7 @@ Update $\mbf{A_\N}$, $\mbf{c_\N}$ and $\mbf{b}$\;
 \subsection{Revised simplex method}
 \label{chXXX:subsec:simplex-rev}
 % Global revised simplex idea
 \subsection{Revised simplex method}
 \label{chXXX:subsec:simplex-rev}
 % Global revised simplex idea

-The operation that takes the most time in the standard method is the pivoting operation, and more specifically, the update of the constraints matrix~$\mbf{A}$. The revised method\index{Simplex!Revised method} tries to avoid this costly operation by updating only a smaller part of this matrix. 
+The operation that takes the most time in the standard method is the pivoting operation, and more specifically, the update of the constraints matrix~$\mbf{A}$. The revised method\index{simplex!revised method} tries to avoid this costly operation by updating only a smaller part of this matrix. 

 
 %% Revised simplex method operations, useful for the algorithm
 The revised simplex method uses the same operations as in the standard method to choose the entering and leaving variables. 
 
 %% Revised simplex method operations, useful for the algorithm
 The revised simplex method uses the same operations as in the standard method to choose the entering and leaving variables. 


@@ -297,10 +297,10 @@ and $\bs\beta = \mbf{N^T} \mbf{(B^{-1})^T} \mbf{d}$
 
 \subsubsection*{Choice of the leaving variable}
 The stability and robustness of the algorithm depend considerably on the choice of the leaving variable. With respect to this, the \textit{expand} method~\cite{GILL1989} proves to be very useful in the sense that it helps to avoid cycles and reduces the risks of encountering numerical instabilities. This method consists of two steps of complexity $\mathcal{O}(m)$. In the first step, a small perturbation is applied to the bounds of the variables to prevent stalling of the objective value, thus avoiding cycles. These perturbed bounds are then used to determine the greatest gain on the entering variable imposed by the most constraining basic variable. The second phase uses the original bounds to define the basic variable offering the gain closest to the one of the first phase. This variable will then be selected for leaving the basis.
 
 \subsubsection*{Choice of the leaving variable}
 The stability and robustness of the algorithm depend considerably on the choice of the leaving variable. With respect to this, the \textit{expand} method~\cite{GILL1989} proves to be very useful in the sense that it helps to avoid cycles and reduces the risks of encountering numerical instabilities. This method consists of two steps of complexity $\mathcal{O}(m)$. In the first step, a small perturbation is applied to the bounds of the variables to prevent stalling of the objective value, thus avoiding cycles. These perturbed bounds are then used to determine the greatest gain on the entering variable imposed by the most constraining basic variable. The second phase uses the original bounds to define the basic variable offering the gain closest to the one of the first phase. This variable will then be selected for leaving the basis.

-
-\section{Branch-and-bound\index{Branch-and-bound} algorithm}
+\pagebreak
+\section{Branch-and-bound\index{branch-and-bound} algorithm}

 \label{chXXX:sec:bnb}
 \label{chXXX:sec:bnb}

-\subsection{Integer linear programming\index{Integer linear programming}}
+\subsection{Integer linear programming\index{integer linear programming}}

 \label{chXXX:subsec:ilp}
 % Why and what are integer linear programming problem
 In some problems, variables are integer-valued. For example, in a vehicle routing problem, one cannot assign one third of a vehicule to a specific route. ILP problems restrict LP problems by imposing an integrality condition on the variables. While this change may seem to have little impact on the model, the aftermaths on the resolution method are quite important.
 \label{chXXX:subsec:ilp}
 % Why and what are integer linear programming problem
 In some problems, variables are integer-valued. For example, in a vehicle routing problem, one cannot assign one third of a vehicule to a specific route. ILP problems restrict LP problems by imposing an integrality condition on the variables. While this change may seem to have little impact on the model, the aftermaths on the resolution method are quite important.


@@ -369,7 +369,7 @@ whose objective value $z$ is inferior to the best one yet found.
 \subsection{Branching strategy}
 \label{chXXX:subsec:bnb-branching}
 % What it is and why it is important
 \subsection{Branching strategy}
 \label{chXXX:subsec:bnb-branching}
 % What it is and why it is important

-The branching strategy\index{Branch-and-bound!Branching} defines the method used to select the variable on which branching will occur. 
+The branching strategy\index{branch-and-bound!branching} defines the method used to select the variable on which branching will occur. 

 The objective value of the child node depends greatly on the choice of this variable. 
 Branching on a variable may lead to a drop on the upper bound and thus speed up the exploration, 
 while branching on other variables could leave this bound unchanged.
 The objective value of the child node depends greatly on the choice of this variable. 
 Branching on a variable may lead to a drop on the upper bound and thus speed up the exploration, 
 while branching on other variables could leave this bound unchanged.


@@ -384,7 +384,7 @@ Several branching strategies exist~\cite{Achterberg05}. Let us briefly comment o
 
 \subsection{Node selection strategy}
 \label{chXXX:subsec:bnb-node-select}
 
 \subsection{Node selection strategy}
 \label{chXXX:subsec:bnb-node-select}

-The node selection strategy\index{Branch-and-bound!Node selection} defines the methodology used to explore the tree. 
+The node selection strategy\index{branch-and-bound!node selection} defines the methodology used to explore the tree. 

 While the usual depth-first search and breadth-first search are considered and used,
 some remarks about the tree exploration must be made.
 First let us mention a few facts:
 While the usual depth-first search and breadth-first search are considered and used,
 some remarks about the tree exploration must be made.
 First let us mention a few facts:


@@ -419,7 +419,7 @@ thus improving the upper and lower bounds at the same time.
 
 \subsection{Cutting-plane methods}
 \label{chXXX:subsec:cuts}
 
 \subsection{Cutting-plane methods}
 \label{chXXX:subsec:cuts}

-\textit{Cutting-planes}\index{Branch-and-bound!Cutting-plane}~\cite{WOLTER06} (also simply \textit{cuts}) are new constraints whose role is to cut off parts of the search space. 
+\textit{Cutting-planes}\index{branch-and-bound!cutting-plane}~\cite{WOLTER06} (also simply \textit{cuts}) are new constraints whose role is to cut off parts of the search space. 

 They may be generated from the first LP solution (\textit{cut-and-branch}) or periodically during the B\&B (\textit{branch-and-cut}). 
 On the one hand cutting-planes may considerably reduce the size of the solution space, but on the other hand they increase the problem size. 
 Moreover, generating cutting-planes is costly since it requires a thorough analysis of the current state of the problem.
 They may be generated from the first LP solution (\textit{cut-and-branch}) or periodically during the B\&B (\textit{branch-and-cut}). 
 On the one hand cutting-planes may considerably reduce the size of the solution space, but on the other hand they increase the problem size. 
 Moreover, generating cutting-planes is costly since it requires a thorough analysis of the current state of the problem.


@@ -442,7 +442,7 @@ In the following section, we first quickly describe the CUDA reduction operation
 % Reduce operation
 \subsection{Parallel reduction}
 \label{chXXX:subsec:reduction}
 % Reduce operation
 \subsection{Parallel reduction}
 \label{chXXX:subsec:reduction}

-A parallel reduction\index{Parallel reduction} operation is performed in an efficient manner inside a GPU block as shown in Figure~\ref{chXXX:fig:reduc}. Shared memory is used for a fast and reliable way to communicate between threads. However, at the grid level, reduction cannot be easily implemented due to the lack of direct communication between blocks. The usual way of dealing with this type of limitation is to apply the reduction in two separate steps. The first one involves a GPU kernel reducing the data over multiple blocks, the local result of each block being stored on completion. The second step finishes the reduction on a single block or on the CPU.
+A parallel reduction\index{parallel!reduction} operation is performed in an efficient manner inside a GPU block as shown in Figure~\ref{chXXX:fig:reduc}. Shared memory is used for a fast and reliable way to communicate between threads. However, at the grid level, reduction cannot be easily implemented due to the lack of direct communication between blocks. The usual way of dealing with this type of limitation is to apply the reduction in two separate steps. The first one involves a GPU kernel reducing the data over multiple blocks, the local result of each block being stored on completion. The second step finishes the reduction on a single block or on the CPU.

 An optimized way of doing the reduction can be found in the examples\footnote{Available at http://docs.nvidia.com/cuda/cuda-samples/index.html\#advanced} provided by NVIDIA. 
 %In order to keep code listings compact hereafter, the reduction of values among a block will be referred to as \textit{reduceOperation(value)} (per extension \textit{reduceArgMax(maxVal)}).
 
 An optimized way of doing the reduction can be found in the examples\footnote{Available at http://docs.nvidia.com/cuda/cuda-samples/index.html\#advanced} provided by NVIDIA. 
 %In order to keep code listings compact hereafter, the reduction of values among a block will be referred to as \textit{reduceOperation(value)} (per extension \textit{reduceArgMax(maxVal)}).
 


@@ -752,12 +752,12 @@ The first critical choice is to select an efficient tree traversal strategy that
 There are two cases where starting from a fresh problem is required or beneficial. The first one is imposed by the numeric inaccuracy appearing after several iterations of the LP solver. The second is upon the request of a new subtree. To avoid the extensive communication costs of a full restart, the GPU keeps in memory an intermediate stable state of the problem, a \textit{warmstart}. This state could, for example, be the one found after solving the root node of the tree.
 
 % Global flow
 There are two cases where starting from a fresh problem is required or beneficial. The first one is imposed by the numeric inaccuracy appearing after several iterations of the LP solver. The second is upon the request of a new subtree. To avoid the extensive communication costs of a full restart, the GPU keeps in memory an intermediate stable state of the problem, a \textit{warmstart}. This state could, for example, be the one found after solving the root node of the tree.
 
 % Global flow

-\subsubsection*{Multi-GPU\index{Multi-GPU} exploration}
+\subsubsection*{Multi-GPU\index{multi-GPU} exploration}

 Having the CPU act as a decision maker and the GPU as an explorer, allows for the possibility of using multiple GPUs to explore the tree. The global knowledge is maintained by the CPU task. The CPU assigns to the GPUs the task of exploring subtrees of promising nodes. Since each plunging is done locally, no communications are required between the GPUs. Moreover, the amount of nodes processed during a plunging can be used to tune the load of the CPU task.
 
 \section{Performance model}
 \label{chXXX:sec:MODEL}
 Having the CPU act as a decision maker and the GPU as an explorer, allows for the possibility of using multiple GPUs to explore the tree. The global knowledge is maintained by the CPU task. The CPU assigns to the GPUs the task of exploring subtrees of promising nodes. Since each plunging is done locally, no communications are required between the GPUs. Moreover, the amount of nodes processed during a plunging can be used to tune the load of the CPU task.
 
 \section{Performance model}
 \label{chXXX:sec:MODEL}

-Performance models\index{Performance model} are useful to predict the behaviour of implementations as a function of various parameters. Since the standard simplex algorithm is the easiest to understand, we will focus in this section on its behaviour as a function of the problem size.
+Performance models\index{performance model} are useful to predict the behaviour of implementations as a function of various parameters. Since the standard simplex algorithm is the easiest to understand, we will focus in this section on its behaviour as a function of the problem size.

 
 CUDA kernels require a different kind of modeling than usually encountered in parallelism. The key idea is to capture in the model the decomposition into threads, warps, and blocks. One must also pay a particular attention to global memory accesses and to how the pipelines reduce the associated latency.
 
 
 CUDA kernels require a different kind of modeling than usually encountered in parallelism. The key idea is to capture in the model the decomposition into threads, warps, and blocks. One must also pay a particular attention to global memory accesses and to how the pipelines reduce the associated latency.