Zoltan2 Version of the Day
Metric.cpp
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 //
00046 // Test the following:
00047 //         PartitioningSolutionQuality class
00048 //         MetricValues class
00049 //         Metric related namespace methods
00050 
00051 
00052 #include <Zoltan2_PartitioningSolutionQuality.hpp>
00053 #include <Zoltan2_TestHelpers.hpp>
00054 #include <Zoltan2_BasicIdentifierInput.hpp>
00055 #include <stdlib.h>
00056 #include <vector>
00057 
00058 typedef Zoltan2::BasicUserTypes<scalar_t, gno_t, lno_t, gno_t> user_t;
00059 typedef Zoltan2::BasicIdentifierInput<user_t> idInput_t;
00060 typedef Zoltan2::PartitioningSolutionQuality<idInput_t> quality_t;
00061 
00062 using Teuchos::ArrayRCP;
00063 using Teuchos::Array;
00064 using Teuchos::RCP;
00065 using Teuchos::rcp;
00066 using Teuchos::arcp;
00067 
00068 using namespace std;
00069 using std::endl;
00070 using std::cout;
00071 
00072 typedef zoltan2_partId_t partId_t;
00073 
00074 void doTest(RCP<const Comm<int> > comm, int numLocalObj,
00075   int weightDim, int numLocalParts, bool givePartSizes);
00076 
00077 int main(int argc, char *argv[])
00078 {
00079   Teuchos::GlobalMPISession session(&argc, &argv);
00080   RCP<const Comm<int> > comm = Teuchos::DefaultComm<int>::getComm();
00081   int rank = comm->getRank();
00082 
00083   doTest(comm, 10, 0, -1, false);
00084   doTest(comm, 10, 0, 1, false);
00085   doTest(comm, 10, 0, 1, true);
00086   doTest(comm, 10, 1, 1, false);
00087   doTest(comm, 10, 1, 1, true);
00088   doTest(comm, 10, 2, 1, false);
00089   doTest(comm, 10, 2, 1, true);
00090   doTest(comm, 10, 1, 2, true);
00091   doTest(comm, 10, 1, 2, false);
00092   doTest(comm, 10, 1, -1, false);
00093   doTest(comm, 10, 1, -1, true);
00094   doTest(comm, 10, 2, -1, false);
00095 
00096   if (rank==0)
00097     cout << "PASS" << endl;
00098 }
00099 
00100 // Assumes numLocalObj is the same on every process.
00101 
00102 void doTest(RCP<const Comm<int> > comm, int numLocalObj,
00103   int weightDim, int numLocalParts, bool givePartSizes)
00104 {
00105   int rank = comm->getRank();
00106   int nprocs = comm->getSize();
00107   int fail=0;
00108   srand(rank+1);
00109   bool testEmptyParts = (numLocalParts < 1);
00110   int numGlobalParts = 0;
00111 
00112   if (testEmptyParts){
00113     numGlobalParts = nprocs / 2;
00114     if (numGlobalParts >= 1)
00115       numLocalParts = (rank < numGlobalParts ? 1 : 0);
00116     else{
00117       numLocalParts = 1;
00118       testEmptyParts = false;
00119     }
00120   }
00121   else{
00122     numGlobalParts = nprocs * numLocalParts;
00123   }
00124 
00125   if (rank == 0){
00126     cout << endl;
00127     cout << "Test: weight dimension " << weightDim;
00128     cout << ", desired number of parts " << numGlobalParts;
00129     if (givePartSizes)
00130       cout << ", with differing part sizes." << endl;
00131     else
00132       cout << ", with uniform part sizes." << endl;
00133     cout << "Number of procs " << nprocs;
00134     cout << ", each with " << numLocalObj << " objects, part = rank." << endl;
00135   }
00136 
00137   // An environment.  This is usually created by the problem.
00138 
00139   Teuchos::ParameterList pl("test list");
00140   pl.set("num_local_parts", double(numLocalParts));
00141   
00142   RCP<const Zoltan2::Environment> env = 
00143     rcp(new Zoltan2::Environment(pl, comm));
00144 
00145   // A simple identifier map.  Usually created by the model.
00146 
00147   gno_t *myGids = new gno_t [numLocalObj];
00148   for (int i=0, x=rank*numLocalObj; i < numLocalObj; i++, x++){
00149     myGids[i] = x;
00150   }
00151 
00152   ArrayRCP<const gno_t> gidArray(myGids, 0, numLocalObj, true);
00153 
00154   RCP<const Zoltan2::IdentifierMap<user_t> > idMap = 
00155     rcp(new Zoltan2::IdentifierMap<user_t>(env, comm, gidArray)); 
00156 
00157   // Part sizes.  Usually supplied by the user to the Problem.
00158   // Then the problem supplies them to the Solution.
00159 
00160   int partSizeDim = (givePartSizes ? (weightDim ? weightDim : 1) : 0);
00161   ArrayRCP<ArrayRCP<partId_t> > ids(partSizeDim);
00162   ArrayRCP<ArrayRCP<scalar_t> > sizes(partSizeDim);
00163 
00164   if (givePartSizes && numLocalParts > 0){
00165     partId_t *myParts = new partId_t [numLocalParts];
00166     myParts[0] = rank * numLocalParts;
00167     for (int i=1; i < numLocalParts; i++)
00168       myParts[i] = myParts[i-1] + 1;
00169     ArrayRCP<partId_t> partNums(myParts, 0, numLocalParts, true);
00170 
00171     scalar_t sizeFactor = nprocs/2 - rank;
00172     if (sizeFactor < 0) sizeFactor *= -1;
00173     sizeFactor += 1;
00174 
00175     for (int dim=0; dim < partSizeDim; dim++){
00176       scalar_t *psizes = new scalar_t [numLocalParts];
00177       for (int i=0; i < numLocalParts; i++)
00178         psizes[i] = sizeFactor;
00179       sizes[dim] = arcp(psizes, 0, numLocalParts, true);
00180       
00181       ids[dim] = partNums;
00182     }
00183   }
00184 
00185   // An input adapter with random weights.  Created by the user.
00186 
00187   std::vector<const scalar_t *> weights;
00188   std::vector<int> strides;   // default to 1
00189 
00190   int len = numLocalObj*weightDim;
00191   ArrayRCP<scalar_t> wgtBuf;
00192   scalar_t *wgts = NULL;
00193 
00194   if (len > 0){
00195     wgts = new scalar_t [len];
00196     wgtBuf = arcp(wgts, 0, len, true);
00197     for (int i=0; i < len; i++)
00198       wgts[i] = (scalar_t(rand()) / scalar_t(RAND_MAX)) + 1.0;
00199   }
00200 
00201   for (int i=0; i < weightDim; i++, wgts+=numLocalObj)
00202     weights.push_back(wgts);
00203 
00204   RCP<const idInput_t> ia;
00205 
00206   try{
00207     ia = rcp(new idInput_t(numLocalObj, myGids, weights, strides));
00208   }
00209   catch (std::exception &e){
00210     fail=1;
00211   }
00212 
00213   TEST_FAIL_AND_EXIT(*comm, fail==0, "create adapter", 1);
00214 
00215   // A solution (usually created by a problem)
00216 
00217   RCP<Zoltan2::PartitioningSolution<idInput_t> > solution;
00218 
00219   try{
00220     if (givePartSizes)
00221       solution = rcp(new Zoltan2::PartitioningSolution<idInput_t>(
00222         env, comm, idMap, weightDim,
00223         ids.view(0,partSizeDim), sizes.view(0,partSizeDim)));
00224     else
00225       solution = rcp(new Zoltan2::PartitioningSolution<idInput_t>(
00226         env, comm, idMap, weightDim));
00227   }
00228   catch (std::exception &e){
00229     fail=1;
00230   }
00231 
00232   TEST_FAIL_AND_EXIT(*comm, fail==0, "create solution", 1);
00233 
00234   // Part assignment for my objects: The algorithm usually calls this. 
00235 
00236   partId_t *partNum = new partId_t [numLocalObj];
00237   ArrayRCP<partId_t> partAssignment(partNum, 0, numLocalObj, true);
00238   for (int i=0; i < numLocalObj; i++)
00239     partNum[i] = rank;
00240 
00241   solution->setParts(gidArray, partAssignment, false);  // could use true,
00242                                                         // but test false
00243   RCP<const Zoltan2::PartitioningSolution<idInput_t> > solutionConst =
00244     rcp_const_cast<const Zoltan2::PartitioningSolution<idInput_t> >(solution);
00245 
00246   // create metric object (also usually created by a problem)
00247 
00248   RCP<quality_t> metricObject;
00249 
00250   try{
00251     metricObject = rcp(new quality_t(env, comm, ia, solutionConst));
00252   }
00253   catch (std::exception &e){
00254     fail=1;
00255   }
00256 
00257   TEST_FAIL_AND_EXIT(*comm, fail==0, "compute metrics", 1);
00258 
00259 
00260   if (rank==0){
00261     scalar_t imb;
00262     try{
00263       metricObject->getObjectCountImbalance(imb); 
00264       cout << "Object imbalance: " << imb << endl;
00265     }
00266     catch (std::exception &e){
00267       fail=1;
00268     }
00269   }
00270 
00271   TEST_FAIL_AND_EXIT(*comm, fail==0, "getObjectCountImbalance", 1);
00272 
00273   if (rank==0 && weightDim > 0){
00274     scalar_t imb;
00275     try{
00276       for (int i=0; i < weightDim; i++){
00277         metricObject->getWeightImbalance(imb, i);
00278         cout << "Weight " << i << " imbalance: " << imb << endl;
00279       }
00280     }
00281     catch (std::exception &e){
00282       fail=10;
00283     }
00284     if (!fail && weightDim > 1){
00285       try{
00286         metricObject->getNormedImbalance(imb);
00287         cout << "Normed weight imbalance: " << imb << endl;
00288       }
00289       catch (std::exception &e){
00290         fail=11;
00291       }
00292     }
00293   }
00294 
00295   TEST_FAIL_AND_EXIT(*comm, fail==0, "get imbalances", 1);
00296   
00297   if (rank==0){
00298     try{
00299       metricObject->printMetrics(cout);
00300     }
00301     catch (std::exception &e){
00302       fail=1;
00303     }
00304   }
00305 
00306   TEST_FAIL_AND_EXIT(*comm, fail==0, "print metrics", 1);
00307 }