]> AND Private Git Repository - book_gpu.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ch10
authorcouturie <couturie@extinction>
Tue, 23 Apr 2013 14:31:32 +0000 (16:31 +0200)
committercouturie <couturie@extinction>
Tue, 23 Apr 2013 14:31:32 +0000 (16:31 +0200)
13 files changed:
BookGPU/BookGPU.tex
BookGPU/Chapters/chapter10/biblio.bib [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/Big2.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/Med2.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/Model.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/Reduc2.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/Small2.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/diagSTD2.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/figures/tree2.pdf [new file with mode: 0644]
BookGPU/Chapters/chapter10/optiSE.cu [new file with mode: 0644]
BookGPU/Chapters/chapter10/updateBasis.cu [new file with mode: 0644]
BookGPU/Chapters/chapter17/ch17.tex
BookGPU/Makefile

index 95ea162d536abfb8013066597d4c40bac722d5cd..0d2d4e8199cec09bfec195d7bf8d523af2dc6039 100755 (executable)
@@ -1,6 +1,7 @@
 \documentclass[sunil1,ChapterTOCs]{sunil}
 \usepackage[utf8]{inputenc}
 \usepackage{amssymb}
+%usepackage{amsbsy}
 \usepackage{amsfonts,amssymb}
 \usepackage{amsmath}
 \usepackage{amscd}
 \newcommand{\mymat}[1]{\mathcal{#1}}
 \newcommand{\myvec}[1]{\mathbf{#1}} 
 
+\newcommand{\mbf}{\mathbf}
+\newcommand{\mc}{\mathcal}
+%newcommand{\bs}{\boldsymbol}
+\newcommand{\N}{\mathcal{N}}
+\newcommand{\B}{\mathcal{B}}
+
+\DeclareMathOperator*{\argmax}{arg\,max}
+
+
 \lstset{morekeywords={HALF4,HALF3,float2,float3,float4,half,half2,half3,half4,tex2D,dim3,endif,threadIdx,blockIdx,blockDim,gridDim,Dim3,__host__,__global__,__shared__,float}}
 \lstset{
   language=C,
 
 
 \makeindex
-%\includeonly{Chapters/chapter17/ch17}
+ \includeonly{Chapters/chapter10/ch10}
 
 \begin{document}
 
 \part{Optimization}
 \include{Chapters/chapter8/ch8}
 \include{Chapters/chapter9/ch9}
+\include{Chapters/chapter10/ch10}
 
 \part{Numerical applications}
 \include{Chapters/chapter7/ch7} %pb fonts
diff --git a/BookGPU/Chapters/chapter10/biblio.bib b/BookGPU/Chapters/chapter10/biblio.bib
new file mode 100644 (file)
index 0000000..380d5f6
--- /dev/null
@@ -0,0 +1,299 @@
+@Book{VCLP,
+author = {V. Chvatal},
+title = {Linear Programming},
+publisher = {W.H. Freeman},
+year = {1983}
+}
+
+
+@Article{PAN2008,
+title = {A largest-distance pivot rule for the simplex algorithm},
+author = {P.-Q. Pan},
+journal = {European Journal for Operational Research},
+year = {2008},
+volume = {187},
+pages = {393-402}
+}
+
+@Article{PAN2006,
+title = {Partial Pricing Rule Simplex Method with Deficient Basis},
+author = {P. Pan{,} W. Li and J. Cao},
+journal = {NUMERICAL MATHEMATICS},
+year = {2006},
+volume = {15},
+pages = {22-30},
+note = {A Journal of Chinese Universities}
+}
+
+@Article{SWIET1998,
+author = {A. Swietanowski},
+title = {A New Steepest Edge Approximation for the Simplex Method for Linear Programming},
+journal = {Computat. Optimization and Appl.},
+year = {1998},
+volume = {10},
+pages = {271-281}
+}
+
+@Article{GILL1989,
+author = {P.E. Gill et al.},
+title = {A pratical anti-cycling procedure for linearly constrained optimization},
+journal = {Mathematical Programming},
+year = {1989},
+volume = {45},
+pages = {437-474}
+}
+
+@Misc{VOLKOV2010,
+author = {V. Volkov},
+title = {Better Performance at Lower Occupancy},
+howpublished = {http://www.cs.berkeley.edu/~volkov/},
+year = {2010}
+}
+
+@TechReport{MODEL,
+author = {K. Kothapalli et al.},
+title = {A Performance Prediction Model for the {CUDA GPGPU} Platform},
+institution = {Int'l Inst. of Information Technology, Hyderabad},
+year = {2009}
+}
+
+@Misc{NETBLIB,
+author = {J. Dongarra and E. Grosse},
+title = {The {NETLIB} Repository},
+howpublished = {http://www.netlib.org},
+year = {2010}
+}
+
+@Misc{APMTECH,
+title = {{APM} Technologies SA},
+howpublished = {http://www.apmtechnologies.com/},
+year = {2010}
+}
+
+@InCollection{BREAR74,
+author = {A.L. Brearley{,} G. Mitra and H.P. Williams},
+title = {Analysis of mathematical programming problems prior to applying the simplex algorithm},
+booktitle = {Mathematical Programming 8 (1975) 54-83},
+pages = {54-83},
+publisher = {North-Holland Publishing Company},
+year = {1975},
+volume = {8}
+}
+
+@InProceedings{BIELING,
+author = {J. Bieling et al.},
+title = {An Efficient {GPU} Implementation of the Revised Simplex Method},
+booktitle = {Proc. of the 24th Int'l Parallel and Distributed Processing Symp.},
+organization = {IEEE},
+year = {2010},
+}
+
+@Book{WRIGHT,
+author = {S.J. Wright},
+title = {Primal-dual interior-point methods},
+publisher = {SIAM},
+year = {1998}
+}
+
+@Misc{THOMAD,
+author = {M.E. Thomadakis and J.-C. Liu},
+title = {An efficient steepest-edge simplex algorithm for {SIMD} computers},
+year = {1996}
+}
+
+@Misc{HALL,
+author = {J.A.J. Hall},
+title = {Towards a practical parallelisation of the simplex method},
+year = {2007}
+}
+
+@Book{HILLIER,
+author = {F.S Hillier and G.J. Lierberman},
+title = {Introduction to Operations Research},
+year = {2010},
+edition = {9}
+}
+
+@Manual{CUDA,
+author = {NVIDIA},
+title = {CUDA Compute Unified Device Architecture : Programming Guide},
+year = {2008},
+}
+
+@Misc{MPS,
+title = {{MPS} file format},
+howpublished = {http://lpsolve.sourceforge.net/5.5/mps-format.htm},
+year = {2010}
+}
+
+@Misc{IMPL,
+author = {X. Meyer},
+title = {Code source : implmentation du simplexe standard sur {GPU}s},
+howpublished = {http://spc.unige.ch/open\_source},
+year = {2011}
+}
+
+@TechReport{DANTZIG80,
+author = {G.B. Dantzig},
+title = {Expected number of steps of the simplex method for a linear program with a convexity constraint},
+institution = {Stanford {U}niversity},
+year = {1980}
+}
+
+@MastersThesis{MEYER11,
+author = {X. Meyer},
+title = {Etude et implmentation de l'algorithme standard du simplexe sur {GPU}s},
+school = {University of {Geneva}},
+year = {2011},
+}
+
+@Article{LALAMI11,
+author = {M.E. Lalami{,} D. El-Baz and V. Boyer},
+title = {Multi GPU Implementation of the Simplex Algorithm},
+journal = {IEEE International Conference on High Performance Computing and Communications},
+year = {2011},
+pages = {179-186}
+}
+
+@Article{JUNG08,
+author = {J. H. Jung and D. P. O'Leary},
+title = {Implementing an interior point method for linear programs on a CPU-GPU system},
+journal = {Electronic Transactions on Numerical Analysis},
+year = {2008},
+pages = {174-189},
+volume = {28}
+}
+
+@Article{ELSTER09,
+author = {D. G. Spampinato{,} A. C. Elster and T. Natvig},
+title = {Modeling Multi-GPU Systems in Parallel Computing: From Multicores and GPU's to Petascale},
+journal = {Advances in Parallel Computing},
+year = {2010},
+pages = {562-569},
+volume = {19}
+}
+
+@book{dantzig1953product,
+  title={The Product Form for the Inverse in the Simplex Method},
+  author={DANTZIG, G.B. and Orchard-Hays, W. and RAND CORP SANTA MONICA CALIF.},
+  url={http://books.google.ch/books?id=XLuttgAACAAJ},
+  year={1953},
+  publisher={Defense Technical Information Center}
+}
+
+
+
+@article{Marchand:2002:CPI:772382.772395,
+ author = {Marchand, Hugues and Martin, Alexander and Weismantel, Robert and Wolsey, Laurence},
+ title = {Cutting planes in integer and mixed integer programming},
+ journal = {Discrete Appl. Math.},
+ issue_date = {15 November 2002},
+ volume = {123},
+ number = {1-3},
+ month = nov,
+ year = {2002},
+ issn = {0166-218X},
+ pages = {397--446},
+ numpages = {50},
+ url = {http://dx.doi.org/10.1016/S0166-218X(01)00348-1},
+ doi = {10.1016/S0166-218X(01)00348-1},
+ acmid = {772395},
+ publisher = {Elsevier Science Publishers B. V.},
+ address = {Amsterdam, The Netherlands, The Netherlands},
+ keywords = {cutting planes, mixed integer programming},
+} 
+
+@PhdThesis{WOLTER06,
+author = {Kati Wolter},
+title = {Implementation of cutting plane separators for mixed integer programs},
+school = {TU Berlin},
+year = {2006}
+}
+
+@PhdThesis{ACHTERBERG07,
+author = {Tobias Achterberg},
+title = {Constraint integer programming},
+school = {TU Berlin},
+year = {2007}
+}
+
+@article{SUHL93,
+year={1993},
+issn={0254-5330},
+journal={Annals of Operations Research},
+volume={43},
+issue={1},
+doi={10.1007/BF02025534},
+title={A fast LU update for linear programming},
+url={http://dx.doi.org/10.1007/BF02025534},
+publisher={Baltzer Science Publishers, Baarn/Kluwer Academic Publishers},
+author={Suhl, LeenaM. and Suhl, UweH.},
+pages={33-47},
+language={English}
+}
+
+@article{GOLDFRAB77,
+author = {D. Goldfarb and J. K. Reid},
+title = {{A practicable steepest-edge simplex algorithm}},
+journal = {Mathematical Programming},
+volume = {12},
+year = {1977},
+pages = {361--371},
+issue = {1},
+doi = {10.1007/BF01593804},
+masid = {1275008}
+}
+
+@article{BENICHOU71,
+year={1971},
+issn={0025-5610},
+journal={Mathematical Programming},
+volume={1},
+number={1},
+doi={10.1007/BF01584074},
+title={Experiments in mixed-integer linear programming},
+url={http://dx.doi.org/10.1007/BF01584074},
+publisher={Springer-Verlag},
+author={Benichou, M. and Gauthier, J.M. and Girodet, P. and Hentges, G. and Ribiere, G. and Vincent, O.},
+pages={76-94},
+language={English}
+}
+
+@article{Achterberg05,
+ author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander},
+ title = {Branching rules revisited},
+ journal = {Oper. Res. Lett.},
+ issue_date = {January, 2005},
+ volume = {33},
+ number = {1},
+ month = jan,
+ year = {2005},
+ issn = {0167-6377},
+ pages = {42--54},
+ numpages = {13},
+ url = {http://dx.doi.org/10.1016/j.orl.2004.04.002},
+ doi = {10.1016/j.orl.2004.04.002},
+ acmid = {2309403},
+ publisher = {Elsevier Science Publishers B. V.},
+ address = {Amsterdam, The Netherlands, The Netherlands},
+ keywords = {Branch-and-bound, Mixed-integer-programming, Pseudocost-branching, Reliability-branching, Strong-branching, Variable selection}
+} 
+
+@ARTICLE{Linderoth97,
+    author = {J. T. Linderoth and M. W. P. Savelsbergh},
+    title = {A Computational Study of Search Strategies for Mixed Integer Programming},
+    journal = {INFORMS Journal on Computing},
+    year = {1997},
+    volume = {11},
+    pages = {173--187}
+}
+
+@ARTICLE{FORREST74,
+title = {Practical Solution of Large Mixed Integer Programming Problems with Umpire},
+author = {Forrest, J. J. H. and Hirst, J. P. H. and Tomlin, J. A.},
+year = {1974},
+journal = {Management Science},
+volume = {20},
+number = {5},
+pages = {736-773}
+}
diff --git a/BookGPU/Chapters/chapter10/figures/Big2.pdf b/BookGPU/Chapters/chapter10/figures/Big2.pdf
new file mode 100644 (file)
index 0000000..504cb63
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/Big2.pdf differ
diff --git a/BookGPU/Chapters/chapter10/figures/Med2.pdf b/BookGPU/Chapters/chapter10/figures/Med2.pdf
new file mode 100644 (file)
index 0000000..0330503
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/Med2.pdf differ
diff --git a/BookGPU/Chapters/chapter10/figures/Model.pdf b/BookGPU/Chapters/chapter10/figures/Model.pdf
new file mode 100644 (file)
index 0000000..64290b7
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/Model.pdf differ
diff --git a/BookGPU/Chapters/chapter10/figures/Reduc2.pdf b/BookGPU/Chapters/chapter10/figures/Reduc2.pdf
new file mode 100644 (file)
index 0000000..4a0bb8c
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/Reduc2.pdf differ
diff --git a/BookGPU/Chapters/chapter10/figures/Small2.pdf b/BookGPU/Chapters/chapter10/figures/Small2.pdf
new file mode 100644 (file)
index 0000000..e1423f8
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/Small2.pdf differ
diff --git a/BookGPU/Chapters/chapter10/figures/diagSTD2.pdf b/BookGPU/Chapters/chapter10/figures/diagSTD2.pdf
new file mode 100644 (file)
index 0000000..e23bc6d
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/diagSTD2.pdf differ
diff --git a/BookGPU/Chapters/chapter10/figures/tree2.pdf b/BookGPU/Chapters/chapter10/figures/tree2.pdf
new file mode 100644 (file)
index 0000000..eea4cc2
Binary files /dev/null and b/BookGPU/Chapters/chapter10/figures/tree2.pdf differ
diff --git a/BookGPU/Chapters/chapter10/optiSE.cu b/BookGPU/Chapters/chapter10/optiSE.cu
new file mode 100644 (file)
index 0000000..9033d98
--- /dev/null
@@ -0,0 +1,35 @@
+extern __shared__ volatile double sData[];
+__global__ void
+selectInVar(int m, int n, double *c, double *AN, uint pitchAN, uint *resIdx, double *resVal)
+{
+       uint i, maxIdx = -1, bid = blockIdx.x;
+       double val, locSum, xScore, maxScore = 0.0;
+       while(bid < n){ // Processing multiple column
+               i = threadIdx.x;
+               locSum = 0.0;
+               if(isPotentialEnteringVar(bid)){ // Do the local processing
+                       while(i < m) { // Each thread process multiple elements
+                               val = AN[i+bid*pitchAN];
+                               locSum += val*val;
+                               i += blockDim.x;
+                       }
+                       // Reduce the value using the shared memory
+                       reduceSum(locSum);
+                       if (tid == 0){ // Is this the best variable encoutered ?
+                               // on tid=0 locSum eqals the s.e. coeffcient
+                               xScore = cVal*rsqrt(locSum); 
+                               if(fabs(maxScore) < fabs(xScore)){
+                                       maxIdx = bid;
+                                       maxScore = xScore;
+                               }
+                       }
+                       __syncthreads();
+               }
+               bid += gridDim.x;
+       }
+       // Write the result into global memory
+       if (tid == 0){
+               resIdx[blockIdx.x] = maxIdx;    
+               resVal[blockIdx.x] = maxScore;
+       }
+}
diff --git a/BookGPU/Chapters/chapter10/updateBasis.cu b/BookGPU/Chapters/chapter10/updateBasis.cu
new file mode 100644 (file)
index 0000000..894667a
--- /dev/null
@@ -0,0 +1,31 @@
+extern __shared__ volatile double sData[];
+__global__ void
+updateBasisKernel(int m, uint l, double d_l, double *B, uint pitch_B, double *d)
+{        
+       uint bId = blockIdx.x, tId = threadIdx.x;
+       uint colStart = bId*pitch_B;    
+       double Bij, d_i, B2ij;
+
+       // First thread load Blj so it can be 
+       // broadcasted via shared memory to each threads
+       if(tId == 0)
+               sdata[0] = B[colStart+leave] / d_l;                                     
+       __syncthreads();                
+       
+       // Each thread proccess mutiple elements
+       while(tId < m){         
+               // Load di and Bij
+               d_i = d[tId];
+               Bij = B[colStart+tId];
+               // Update Bij
+               B2ij = sdata[0];
+               if(tId != q){
+                       B2ij *= -d_i;
+                       B2ij += Bij
+               }
+               __syncthreads();        
+               B[colStart+tId] = B2ij;
+
+               tId += blockDim.x;                                      
+       }
+}
\ No newline at end of file
index 6ad3a8c663019c9d14f1caf79642264ae2d7c1c7..80da091a2f7f945376ab7740e7c7840ff28331d1 100755 (executable)
@@ -11,7 +11,7 @@
   \setlength\hangindent{\mylen}%
   \hspace*{\mylen}#1\\}
 
-\chapter{Implementing MAS on GPU}
+\chapter{Implementing Multi-Agent Systems on GPU}
 \label{chapter17}
 
 
index 049fb5b16ff9680199f49a878aaecad19b53a87f..847d0984654ce603436ad00e2052056bfa5897c2 100644 (file)
@@ -22,6 +22,7 @@ all:
        bibtex bu15
        bibtex bu16
        bibtex bu17
+       bibtex bu18
 
        makeindex  ${BOOK}.idx
        pdflatex ${BOOK}