From: couturie Date: Tue, 23 Apr 2013 14:31:32 +0000 (+0200) Subject: ch10 X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/commitdiff_plain/d74981733767eca78dbbe5be810b9b2e239e8aee?ds=sidebyside;hp=--cc ch10 --- d74981733767eca78dbbe5be810b9b2e239e8aee diff --git a/BookGPU/BookGPU.tex b/BookGPU/BookGPU.tex index 95ea162..0d2d4e8 100755 --- a/BookGPU/BookGPU.tex +++ b/BookGPU/BookGPU.tex @@ -1,6 +1,7 @@ \documentclass[sunil1,ChapterTOCs]{sunil} \usepackage[utf8]{inputenc} \usepackage{amssymb} +%usepackage{amsbsy} \usepackage{amsfonts,amssymb} \usepackage{amsmath} \usepackage{amscd} @@ -65,6 +66,15 @@ \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, @@ -137,7 +147,7 @@ \makeindex -%\includeonly{Chapters/chapter17/ch17} + \includeonly{Chapters/chapter10/ch10} \begin{document} @@ -178,6 +188,7 @@ \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 index 0000000..380d5f6 --- /dev/null +++ b/BookGPU/Chapters/chapter10/biblio.bib @@ -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 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 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 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 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 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 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 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 index 0000000..9033d98 --- /dev/null +++ b/BookGPU/Chapters/chapter10/optiSE.cu @@ -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 index 0000000..894667a --- /dev/null +++ b/BookGPU/Chapters/chapter10/updateBasis.cu @@ -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 diff --git a/BookGPU/Chapters/chapter17/ch17.tex b/BookGPU/Chapters/chapter17/ch17.tex index 6ad3a8c..80da091 100755 --- a/BookGPU/Chapters/chapter17/ch17.tex +++ b/BookGPU/Chapters/chapter17/ch17.tex @@ -11,7 +11,7 @@ \setlength\hangindent{\mylen}% \hspace*{\mylen}#1\\} -\chapter{Implementing MAS on GPU} +\chapter{Implementing Multi-Agent Systems on GPU} \label{chapter17} diff --git a/BookGPU/Makefile b/BookGPU/Makefile index 049fb5b..847d098 100644 --- a/BookGPU/Makefile +++ b/BookGPU/Makefile @@ -22,6 +22,7 @@ all: bibtex bu15 bibtex bu16 bibtex bu17 + bibtex bu18 makeindex ${BOOK}.idx pdflatex ${BOOK}