Zoltan2 Version of the Day
Zoltan2_AlgScotch.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 #ifndef _ZOLTAN2_ALGSCOTCH_HPP_
00046 #define _ZOLTAN2_ALGSCOTCH_HPP_
00047 
00048 #include <Zoltan2_GraphModel.hpp>
00049 #include <Zoltan2_PartitioningSolution.hpp>
00050 #include <Zoltan2_Util.hpp>
00051 
00052 typedef zoltan2_partId_t partId_t;
00053 
00054 #ifndef HAVE_ZOLTAN2_SCOTCH
00055 
00056 // Error handling for when Scotch is requested
00057 // but Zoltan2 not built with Scotch.
00058 
00059 namespace Zoltan2 {
00060 
00072 template <typename Adapter>
00073 void AlgPTScotch(
00074   const RCP<const Environment> &env,
00075   const RCP<const Comm<int> > &problemComm,
00076 #ifdef HAVE_ZOLTAN2_MPI
00077   MPI_Comm mpicomm,
00078 #endif
00079   const RCP<GraphModel<typename Adapter::base_adapter_t> > &model,
00080   RCP<PartitioningSolution<Adapter> > &solution
00081 
00082 )
00083 {
00084   throw std::runtime_error(
00085         "BUILD ERROR:  Scotch requested but not compiled into Zoltan2.\n"
00086         "Please set CMake flag Zoltan2_ENABLE_Scotch:BOOL=ON.");
00087 }
00088 }
00089 
00090 #else  //HAVE_ZOLTAN2_SCOTCH
00091 
00092 
00093 // stdint.h for int64_t in scotch header
00094 
00095 #include <stdint.h>
00096 #ifndef HAVE_ZOLTAN2_MPI
00097 #include "scotch.h"
00098 #else
00099 #include "ptscotch.h"
00100 #endif
00101 
00102 #ifdef SHOW_ZOLTAN2_SCOTCH_MEMORY
00103 //
00104 // Scotch keeps track of memory high water mark, but doesn't
00105 // provide a way to get that number.  So add this function:
00106 //   "size_t SCOTCH_getMemoryMax() { return memorymax;}"
00107 // to src/libscotch/common_memory.c
00108 //
00109 // and this macro:
00110 //   "#define HAVE_SCOTCH_GETMEMORYMAX
00111 // to include/ptscotch.h
00112 //
00113 // and compile scotch with -DCOMMON_MEMORY_TRACE
00114 //
00115 #ifdef HAVE_SCOTCH_GETMEMORYMAX
00116 
00117 extern "C"{
00118 extern size_t SCOTCH_getMemoryMax();
00119 }
00120 
00121 #else
00122 
00123 #error "Either turn off ZOLTAN2_ENABLE_SCOTCH_MEMORY_REPORT in cmake configure, or see SHOW_ZOLTAN2_SCOTCH_MEMORY comment in Zoltan2_AlgScotch.hpp"
00124 
00125 #endif
00126 
00127 #endif
00128 
00129 
00133 
00134 namespace Zoltan2{
00135 
00137 //  Traits struct to handle conversions between gno_t/lno_t and SCOTCH_Num.
00139 
00140 // General case:  SCOTCH_Num and gno_t/lno_t (called zno_t here) differ.
00141 template <typename zno_t>
00142 struct SCOTCH_Num_Traits {
00143 
00144   static inline SCOTCH_Num ASSIGN_TO_SCOTCH_NUM(
00145     SCOTCH_Num &a,
00146     zno_t b,
00147     const RCP<const Environment> &env)
00148   {
00149     // Assign a = b; make sure SCOTCH_Num is large enough to accept zno_t.
00150     if (b <= SCOTCH_NUMMAX) a = b;
00151     else 
00152       env->localInputAssertion(__FILE__, __LINE__, 
00153        "Value too large for SCOTCH_Num, Rebuild Scotch with larger SCOTCH_Num",
00154        false, BASIC_ASSERTION);
00155     return a;
00156   }
00157 
00158   static inline void ASSIGN_SCOTCH_NUM_ARRAY(
00159     SCOTCH_Num **a,
00160     ArrayView<const zno_t> &b,
00161     const RCP<const Environment> &env)
00162   {
00163     // Allocate array a; copy b values into a.
00164     size_t size = b.size();
00165     *a = new SCOTCH_Num[size];
00166     for (size_t i = 0; i < size; i++) ASSIGN_TO_SCOTCH_NUM((*a)[i], b[i], env);
00167   }
00168 
00169   static inline void DELETE_SCOTCH_NUM_ARRAY(SCOTCH_Num *a)
00170   {
00171     // Delete the copy made in ASSIGN_SCOTCH_NUM_ARRAY.
00172     delete [] a;
00173   }
00174 
00175   //TODO static inline ASSIGN_FROM_SCOTCH_NUM(zno_t b, SCOTCH_Num a)
00176   //TODO {
00177   //TODO   Make sure zno_t is large enough to accept SCOTCH_Num.
00178   //TODO   NOT NEEDED AS LONG AS PARTS ARE size_t.
00179   //TODO }
00180 };
00181 
00182 
00183 // Special case:  zno_t == SCOTCH_Num. No error checking or copies needed.
00184 template <>
00185 struct SCOTCH_Num_Traits<SCOTCH_Num> {
00186   static inline SCOTCH_Num ASSIGN_TO_SCOTCH_NUM(
00187     SCOTCH_Num &a,
00188     SCOTCH_Num b,
00189     const RCP<const Environment> &env)
00190   {
00191     a = b;
00192     return a;
00193   }
00194   static inline void ASSIGN_SCOTCH_NUM_ARRAY(
00195     SCOTCH_Num **a,
00196     ArrayView<const SCOTCH_Num> &b,
00197     const RCP<const Environment> &env)
00198   {
00199     *a = const_cast<SCOTCH_Num *> (b.getRawPtr());
00200   }
00201   static inline void DELETE_SCOTCH_NUM_ARRAY(SCOTCH_Num *a) { }
00202 };
00203 
00204 
00206 // Now, the actual Scotch algorithm.
00208 
00220 template <typename Adapter>
00221 void AlgPTScotch(
00222   const RCP<const Environment> &env,        // parameters & app comm
00223   const RCP<const Comm<int> > &problemComm, // problem comm
00224 #ifdef HAVE_ZOLTAN2_MPI
00225   MPI_Comm mpicomm,
00226 #endif
00227   const RCP<GraphModel<typename Adapter::base_adapter_t> > &model, // the graph
00228   RCP<PartitioningSolution<Adapter> > &solution
00229 )
00230 {
00231   HELLO;
00232 
00233   typedef typename Adapter::lno_t lno_t;
00234   typedef typename Adapter::gno_t gno_t;
00235   typedef typename Adapter::scalar_t scalar_t;
00236 
00237   int ierr = 0;
00238 
00239   size_t numGlobalParts = solution->getTargetGlobalNumberOfParts();
00240 
00241   SCOTCH_Num partnbr;
00242   SCOTCH_Num_Traits<size_t>::ASSIGN_TO_SCOTCH_NUM(partnbr, numGlobalParts, env);
00243 
00244 #ifdef HAVE_ZOLTAN2_MPI
00245 
00246   const SCOTCH_Num  baseval = 0;  // Base value for array indexing.
00247                                   // GraphModel returns GNOs from base 0.
00248 
00249   SCOTCH_Strat stratstr;          // Strategy string
00250                                   // TODO:  Set from parameters
00251   SCOTCH_stratInit(&stratstr);
00252 
00253   // Allocate & initialize PTScotch data structure.
00254   //SCOTCH_Dgraph *gr = SCOTCH_dgraphAlloc();  // Scotch distributed graph
00255   SCOTCH_Dgraph *gr = new SCOTCH_Dgraph;  // Scotch distributed graph
00256   ierr = SCOTCH_dgraphInit(gr, mpicomm);
00257 
00258   env->globalInputAssertion(__FILE__, __LINE__, "SCOTCH_dgraphInit", 
00259     !ierr, BASIC_ASSERTION, problemComm);
00260 
00261   // Get vertex info
00262   ArrayView<const gno_t> vtxID;
00263   ArrayView<StridedData<lno_t, scalar_t> > xyz;
00264   ArrayView<StridedData<lno_t, scalar_t> > vtxWt;
00265   size_t nVtx = model->getVertexList(vtxID, xyz, vtxWt);
00266   SCOTCH_Num vertlocnbr;
00267   SCOTCH_Num_Traits<size_t>::ASSIGN_TO_SCOTCH_NUM(vertlocnbr, nVtx, env);
00268   SCOTCH_Num vertlocmax = vertlocnbr; // Assumes no holes in global nums.
00269 
00270   // Get edge info
00271   ArrayView<const gno_t> edgeIds;
00272   ArrayView<const int>   procIds;
00273   ArrayView<const lno_t> offsets;
00274   ArrayView<StridedData<lno_t, scalar_t> > ewgts;
00275 
00276   size_t nEdges = model->getEdgeList(edgeIds, procIds, offsets, ewgts);
00277 
00278   SCOTCH_Num edgelocnbr;
00279   SCOTCH_Num_Traits<size_t>::ASSIGN_TO_SCOTCH_NUM(edgelocnbr, nEdges, env);
00280   const SCOTCH_Num edgelocsize = edgelocnbr;  // Assumes adj array is compact.
00281 
00282   SCOTCH_Num *vertloctab;  // starting adj/vtx
00283   SCOTCH_Num_Traits<lno_t>::ASSIGN_SCOTCH_NUM_ARRAY(&vertloctab, offsets, env);
00284 
00285   SCOTCH_Num *edgeloctab;  // adjacencies
00286   SCOTCH_Num_Traits<gno_t>::ASSIGN_SCOTCH_NUM_ARRAY(&edgeloctab, edgeIds, env);
00287 
00288   // We don't use these arrays, but we need them as arguments to Scotch.
00289   SCOTCH_Num *vendloctab = NULL;  // Assume consecutive storage for adj
00290   SCOTCH_Num *vlblloctab = NULL;  // Vertex label array
00291   SCOTCH_Num *edgegsttab = NULL;  // Array for ghost vertices
00292 
00293   // Get weight info.
00294   // TODO:  Actually get the weights; for now, not using weights.
00295   SCOTCH_Num *veloloctab = NULL;  // Vertex weights
00296   SCOTCH_Num *edloloctab = NULL;  // Edge weights
00297   //TODO int vwtdim = model->getVertexWeightDim();
00298   //TODO int ewtdim = model->getEdgeWeightDim();
00299   //TODO if (vwtdim) veloloctab = new SCOTCH_Num[nVtx];
00300   //TODO if (ewtdim) edloloctab = new SCOTCH_Num[nEdges];
00301   //TODO scale weights to SCOTCH_Nums.
00302 
00303   // Build PTScotch distributed data structure
00304   ierr = SCOTCH_dgraphBuild(gr, baseval, vertlocnbr, vertlocmax,
00305                             vertloctab, vendloctab, veloloctab, vlblloctab,
00306                             edgelocnbr, edgelocsize,
00307                             edgeloctab, edgegsttab, edloloctab);
00308 
00309   env->globalInputAssertion(__FILE__, __LINE__, "SCOTCH_dgraphBuild", 
00310     !ierr, BASIC_ASSERTION, problemComm);
00311 
00312   // Create array for Scotch to return results in.
00313   ArrayRCP<partId_t> partList(new partId_t [nVtx], 0, nVtx,true);
00314   SCOTCH_Num *partloctab;
00315   if (sizeof(SCOTCH_Num) == sizeof(partId_t)) {
00316     // Can write directly into the solution's memory
00317     partloctab = (SCOTCH_Num *) partList.getRawPtr();
00318   }
00319   else {
00320     // Can't use solution memory directly; will have to copy later.
00321     partloctab = new SCOTCH_Num[nVtx];
00322   }
00323 
00324   // Call partitioning; result returned in partloctab.
00325   // TODO:  Use SCOTCH_dgraphMap so can include a machine model in partitioning
00326   ierr = SCOTCH_dgraphPart(gr, partnbr, &stratstr, partloctab);
00327 
00328   env->globalInputAssertion(__FILE__, __LINE__, "SCOTCH_dgraphPart", 
00329     !ierr, BASIC_ASSERTION, problemComm);
00330 
00331   // TODO - metrics
00332 #ifdef SHOW_ZOLTAN2_SCOTCH_MEMORY
00333   int me = env->comm_->getRank();
00334 #endif
00335 
00336 #ifdef HAVE_SCOTCH_ZOLTAN2_GETMEMORYMAX
00337   if (me == 0){
00338     size_t scotchBytes = SCOTCH_getMemoryMax();
00339     std::cout << "Rank " << me << ": Maximum bytes used by Scotch: ";
00340     std::cout << scotchBytes << std::endl;
00341   }
00342 #endif
00343 
00344   // Clean up PTScotch
00345   SCOTCH_dgraphExit(gr);
00346   delete gr;
00347   SCOTCH_stratExit(&stratstr);
00348 
00349   // Load answer into the solution.
00350 
00351   if (sizeof(SCOTCH_Num) != sizeof(partId_t)) {
00352     for (size_t i = 0; i < nVtx; i++) partList[i] = partloctab[i];
00353   }
00354 
00355   ArrayRCP<const gno_t> gnos = arcpFromArrayView(vtxID);
00356 
00357   solution->setParts(gnos, partList, true);
00358 
00359   env->memory("Zoltan2-Scotch: After creating solution");
00360 
00361   //if (me == 0) cout << " done." << endl;
00362   // Clean up Zoltan2
00363   //TODO if (vwtdim) delete [] velotab;
00364   //TODO if (ewtdim) delete [] edlotab;
00365 
00366   // Clean up copies made due to differing data sizes.
00367   if (sizeof(lno_t) != sizeof(SCOTCH_Num)) delete [] vertloctab;
00368   if (sizeof(gno_t) != sizeof(SCOTCH_Num)) delete [] edgeloctab;
00369 
00370 #else // DO NOT HAVE_MPI
00371 
00372   // TODO:  Handle serial case with calls to Scotch.
00373   // TODO:  For now, assign everything to rank 0 and assume only one part.
00374   // TODO:  Can probably use the code above for loading solution,
00375   // TODO:  instead of duplicating it here.
00376   // TODO
00377   // TODO:  Actual logic should call Scotch when number of processes == 1.
00378   ArrayView<const gno_t> vtxID;
00379   ArrayView<StridedData<lno_t, scalar_t> > xyz;
00380   ArrayView<StridedData<lno_t, scalar_t> > vtxWt;
00381   size_t nVtx = model->getVertexList(vtxID, xyz, vtxWt);
00382 
00383   for (size_t i = 0; i < nVtx; i++) partList[i] = 0;
00384 
00385 
00386 #endif // DO NOT HAVE_MPI
00387 }
00388 
00389 }
00390 #endif // HAVE_ZOLTAN2_SCOTCH
00391 #endif