orderingScotch.cpp

Go to the documentation of this file.

// @HEADER
//
// ***********************************************************************
//
//   Zoltan2: A package of combinatorial algorithms for scientific computing
//                  Copyright 2012 Sandia Corporation
//
// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
// the U.S. Government retains certain rights in this software.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Karen Devine      (kddevin@sandia.gov)
//                    Erik Boman        (egboman@sandia.gov)
//                    Siva Rajamanickam (srajama@sandia.gov)
//
// ***********************************************************************
//
// @HEADER
#include <Zoltan2_OrderingProblem.hpp>
#include <Zoltan2_XpetraCrsMatrixAdapter.hpp>
#include <Zoltan2_TestHelpers.hpp>
#include <iostream>
#include <fstream>
#include <limits>
#include <vector>
#include <Teuchos_ParameterList.hpp>
#include <Teuchos_RCP.hpp>
#include <Teuchos_CommandLineProcessor.hpp>
#include <Tpetra_CrsMatrix.hpp>
#include <Tpetra_Vector.hpp>
#include <MatrixMarket_Tpetra.hpp>

using Teuchos::RCP;

// Program to demonstrate use of Zoltan2 to order a TPetra matrix
// (read from a MatrixMarket file or generated by Galeri::Xpetra).
// Usage:
//     a.out [--inputFile=filename] [--outputFile=outfile] [--verbose]
//           [--x=#] [--y=#] [--z=#] [--matrix={Laplace1D,Laplace2D,Laplace3D}
// Karen Devine, 2011

// Eventually want to use Teuchos unit tests to vary z2TestLO and
// GO.  For now, we set them at compile time based on whether Tpetra
// is built with explicit instantiation on.  (in Zoltan2_TestHelpers.hpp)

typedef zlno_t z2TestLO;
typedef zgno_t z2TestGO;
typedef zscalar_t z2TestScalar;

typedef Tpetra::CrsMatrix<z2TestScalar, z2TestLO, z2TestGO> SparseMatrix;
typedef Tpetra::Vector<z2TestScalar, z2TestLO, z2TestGO> Vector;
typedef Vector::node_type Node;
typedef Zoltan2::XpetraCrsMatrixAdapter<SparseMatrix> SparseMatrixAdapter;


// Using perm
size_t computeBandwidth(RCP<SparseMatrix> A, z2TestLO *perm)
{
  z2TestLO ii, i, j, k;
  typename SparseMatrix::local_inds_host_view_type  indices;
  typename SparseMatrix::values_host_view_type  values;

  z2TestLO bw_left = 0;
  z2TestLO bw_right = 0;

  z2TestLO  n = A->getLocalNumRows();

  // Loop over rows of matrix
  for (ii=0; ii<n; ii++) {
    A->getLocalRowView (ii, indices, values);
    for (k=0; k< static_cast<z2TestLO>(indices.size()); k++){
      if (indices[k] < n){ // locally owned
        if (perm){
          i = perm[ii];
          j = perm[indices[k]];
        } else {
          i = ii;
          j = indices[k];
        }
        if (j-i > bw_right)
          bw_right = j-i;
        if (i-j > bw_left)
          bw_left = i-j;
      }
    }
  }
  // Total bandwidth is the sum of left and right + 1
  return (bw_left + bw_right + 1);
}

#define MDM
#ifdef MDM
// This is all temp code to be deleted when refactoring is compelte.
void tempDebugTest(
  RCP<SparseMatrix> origMatrix, Zoltan2::LocalOrderingSolution<z2TestLO> *soln)
{
  typedef typename SparseMatrixAdapter::lno_t lno_t;

  lno_t * perm = soln->getPermutationView();
  lno_t * iperm = soln->getPermutationView(true);

  lno_t numRows = origMatrix->getLocalNumRows();

  std::cout << "origMatrix->getLocalNumRows(): " << numRows << std::endl;

  if (numRows == 0) {
    std::cout << "Skipping analysis - matrix is empty" << std::endl;
    return;
  }

  Array<lno_t> oldMatrix(numRows*numRows);
  Array<lno_t> newMatrix(numRows*numRows);

  // print the solution permutation
  lno_t showSize = numRows;
  if(showSize > 30) {
    showSize = 30;
  }

  std::cout << std::endl << "perm:  ";
  for(lno_t n = 0; n < showSize; ++n) {
    std::cout << " " << perm[n] << " ";
  }
  if(showSize < numRows) {
    std::cout << " ..."; // partial print...
  }
  std::cout << std::endl << "iperm: ";
  for(lno_t n = 0; n < showSize; ++n) {
    std::cout << " " << iperm[n] << " ";
  }
  if(showSize < numRows) {
    std::cout << " ..."; // partial print...
  }

  std::cout << std::endl;

  // write 1's in our matrix
  for (lno_t j = 0; j < numRows; ++j) {
    typename SparseMatrix::local_inds_host_view_type  indices;
    typename SparseMatrix::values_host_view_type  wgts;
    origMatrix->getLocalRowView( j, indices, wgts );
    for (lno_t n = 0; n < static_cast<lno_t>(indices.size()); ++n) {
      lno_t i = indices[n];
      if (i < numRows) { // locally owned
        oldMatrix[i + j*numRows] = 1;
        newMatrix[perm[i] + perm[j]*numRows] = 1;
      }
    }
  }

  // print oldMatrix
  std::cout << std::endl << "original graph in matrix form:" << std::endl;
  for(lno_t y = 0; y < showSize; ++y) {
    for(lno_t x = 0; x < showSize; ++x) {
      std::cout << " " << oldMatrix[x + y*numRows];
    }
    if(showSize < numRows) {
      std::cout << " ..."; // partial print...
    }
    std::cout << std::endl;
  }
  if(showSize < numRows) {
    for(lno_t i = 0; i < showSize; ++i) {
      std::cout << " ."; // partial print...
    }
    std::cout << " ..."; // partial print...
  }
  std::cout << std::endl;

  // print newMatrix
  std::cout << std::endl << "reordered graph in matrix form:" << std::endl;
  for(lno_t y = 0; y < showSize; ++y) {
    for(lno_t x = 0; x < showSize; ++x) {
      std::cout << " " << newMatrix[x + y*numRows];
    }
    if(showSize < numRows) {
      std::cout << " ..."; // partial print...
    }
    std::cout << std::endl;
  }
  if(showSize < numRows) {
    for(lno_t i = 0; i < showSize; ++i) {
      std::cout << " ."; // partial print...
    }
    std::cout << " ..."; // partial print...
  }
  std::cout << std::endl;
}
#endif

int mainExecute(int narg, char** arg, RCP<const Teuchos::Comm<int> > comm)
{
  std::string inputFile = "";            // Matrix Market file to read
  std::string outputFile = "";           // Output file to write
  bool verbose = false;                  // Verbosity of output
  int testReturn = 0;

  int rank = comm->getRank();

  // Read run-time options.
  Teuchos::CommandLineProcessor cmdp (false, false);
  cmdp.setOption("inputFile", &inputFile,
                 "Name of a Matrix Market file in the data directory; "
                 "if not specified, a matrix will be generated by Galeri.");
  cmdp.setOption("outputFile", &outputFile,
                 "Name of file to write the permutation");
  cmdp.setOption("verbose", "quiet", &verbose,
                 "Print messages and results.");

  if (rank == 0 ) {
    std::cout << "Starting everything" << std::endl;
  }

  // Even with cmdp option "true", I get errors for having these
  //   arguments on the command line.  (On redsky build)
  // KDDKDD Should just be warnings, right?  Code should still work with these
  // KDDKDD params in the create-a-matrix file.  Better to have them where
  // KDDKDD they are used.
  int xdim=10;
  int ydim=10;
  int zdim=10;
  std::string matrixType("Laplace3D");

  cmdp.setOption("x", &xdim,
                "number of gridpoints in X dimension for "
                "mesh used to generate matrix.");
  cmdp.setOption("y", &ydim,
                "number of gridpoints in Y dimension for "
                "mesh used to generate matrix.");
  cmdp.setOption("z", &zdim,
                "number of gridpoints in Z dimension for "
                "mesh used to generate matrix.");
  cmdp.setOption("matrix", &matrixType,
                "Matrix type: Laplace1D, Laplace2D, or Laplace3D");

  // Ordering options to test.
  std::string orderMethod("scotch"); // NYI
  cmdp.setOption("order_method", &orderMethod,
                "order_method: natural, random, rcm, scotch");

  std::string orderMethodType("local");
  cmdp.setOption("order_method_type", &orderMethodType,
                "local or global or both" );

  cmdp.parse(narg, arg);


  RCP<UserInputForTests> uinput;

  // MDM - temp testing code
  // testDataFilePath = "/Users/micheldemessieres/Documents/trilinos-build/trilinosrepo/parZoltan2/packages/zoltan2/test/driver/driverinputs/ordering";
  // inputFile = "orderingTest";

  if (inputFile != ""){ // Input file specified; read a matrix
    uinput = rcp(new UserInputForTests(testDataFilePath, inputFile, comm, true));
  }
  else {                  // Let Galeri generate a matrix
    uinput = rcp(
      new UserInputForTests(xdim, ydim, zdim, matrixType, comm, true, true));
  }

  RCP<SparseMatrix> origMatrix = uinput->getUITpetraCrsMatrix();

  if (rank == 0) {
    std::cout << "NumRows     = " << origMatrix->getGlobalNumRows() << std::endl
         << "NumNonzeros = " << origMatrix->getGlobalNumEntries() << std::endl
         << "NumProcs = " << comm->getSize() << std::endl;
  }

  // Currently Not Used
  /*
  RCP<Vector> origVector, origProd;
  origProd   = Tpetra::createVector<z2TestScalar,z2TestLO,z2TestGO>(
                                    origMatrix->getRangeMap());
  origVector = Tpetra::createVector<z2TestScalar,z2TestLO,z2TestGO>(
                                    origMatrix->getDomainMap());
  origVector->randomize();
  */

  Teuchos::ParameterList params;
  params.set("order_method", orderMethod);
  params.set("order_method_type", orderMethodType);

  SparseMatrixAdapter adapter(origMatrix);


  try {
    Zoltan2::OrderingProblem<SparseMatrixAdapter> problem(&adapter, &params,
                                                          comm);

    if( rank == 0 ) {
      std::cout << "Going to solve" << std::endl;
    }
    problem.solve();

    size_t checkLength;
    z2TestLO *checkPerm, *checkInvPerm;
    Zoltan2::LocalOrderingSolution<z2TestLO> *soln =
      problem.getLocalOrderingSolution();

    if( rank == 0 ) {
      std::cout << "Going to get results" << std::endl;
    }

  #ifdef MDM // Temp debugging code all of which can be removed for final
  for( int checkRank = 0; checkRank < comm->getSize(); ++checkRank ) {
    comm->barrier();
    if( checkRank == comm->getRank() ) {
      std::cout << "Debug output matrix for rank: " << checkRank << std::endl;
      tempDebugTest(origMatrix, soln);
    }
    comm->barrier();
  }
  #endif

    // Permutation
    checkLength = soln->getPermutationSize();
    checkPerm = soln->getPermutationView();
    checkInvPerm = soln->getPermutationView(true); // get permutation inverse

    // Separators.
    // The following methods needs to be supported:
    // haveSeparators: true if Scotch Nested Dissection was called.
    // getCBlkPtr: *CBlkPtr from Scotch_graphOrder
    // getRangeTab: RangeTab from Scotch_graphOrder
    // getTreeTab: TreeTab from Scotch_graphOrder
    z2TestLO    NumBlocks = 0;
    z2TestLO    *RangeTab;
    z2TestLO    *TreeTab;
    if (soln->haveSeparators()) {
      NumBlocks = soln->getNumSeparatorBlocks(); // BDD
      RangeTab = soln->getSeparatorRangeView(); // BDD
      TreeTab = soln->getSeparatorTreeView(); // BDD
    }
    else {
      // TODO FAIL with error
    }

    if (outputFile != "") {
      std::ofstream permFile;

      // Write permutation (0-based) to file
      // each process writes local perm to a separate file
      //std::string fname = outputFile + "." + me;
      std::stringstream fname;
      fname << outputFile << "." << comm->getSize() << "." << rank;
      permFile.open(fname.str().c_str());
      for (size_t i=0; i<checkLength; i++){
        permFile << " " << checkPerm[i] << std::endl;
      }
      permFile.close();
    }

    // Validate that checkPerm is a permutation
    if (rank == 0 ) {
      std::cout << "Checking permutation" << std::endl;
    }

    testReturn = soln->validatePerm();
    if (testReturn) return testReturn;

    // Validate the inverse permutation.
    if (rank == 0 ) {
      std::cout << "Checking inverse permutation" << std::endl;
    }
    for (size_t i=0; i< checkLength; i++){
      testReturn = (checkInvPerm[checkPerm[i]] != z2TestLO(i));
      if (testReturn) return testReturn;
    }

    // Validate NumBlocks
    if (rank == 0 ) {
      std::cout << "Checking num blocks" << std::endl;
    }
    testReturn = !((NumBlocks > 0) && (NumBlocks<z2TestLO(checkLength)));
    if (testReturn) return testReturn;

    // Validate RangeTab.
    // Should be monitonically increasing, RT[0] = 0; RT[NumBlocks+1]=nVtx;
    if (rank == 0 ) {
      std::cout << "Checking range" << std::endl;
    }
    testReturn = RangeTab[0];
    if (testReturn) return testReturn;

    for (z2TestLO i = 0; i < NumBlocks; i++){
      testReturn = !(RangeTab[i] < RangeTab[i+1]);
      if (testReturn) return testReturn;
    }

    // How do we validate TreeTab?
    // TreeTab root has -1, other values < NumBlocks
    if (rank == 0 ) {
      std::cout << "Checking Separator Tree" << std::endl;
    }

    if (checkLength) {
      testReturn = (TreeTab[0] != -1);
    }

    if (testReturn) {
      std::cout << "TreeTab[0] = " << TreeTab[0] << " != -1" << std::endl;
      return testReturn;
    }

    for (size_t i=1; i< checkLength; i++){
      testReturn = !(TreeTab[i] < NumBlocks);
      if (testReturn) {
        std::cout << "TreeTab[" << i << "] = " << TreeTab[i] << " >= NumBlocks "
                  << " = " << NumBlocks << std::endl;
        return testReturn;
      }
    }

    if (rank == 0 ) {
      std::cout << "Going to compute the bandwidth" << std::endl;
    }

    // Compute original and permuted bandwidth
    z2TestLO originalBandwidth = computeBandwidth(origMatrix, nullptr);
    z2TestLO permutedBandwidth = computeBandwidth(origMatrix, checkPerm);

    if (rank == 0 ) {
      std::cout << "Original Bandwidth: " << originalBandwidth << std::endl;
      std::cout << "Permuted Bandwidth: " << permutedBandwidth << std::endl;
    }

    if(permutedBandwidth >= originalBandwidth) {
      if (rank == 0 ) {
        std::cout << "Test failed: bandwidth was not improved!" << std::endl;

        std::cout << "Test in progress - returning OK for now..." << std::endl;
      }

     // return 1; // TO DO - we need test to have proper ordering
    }
    else {
      if (rank == 0) {
        std::cout << "The bandwidth was improved. Good!" << std::endl;
      }
    }
  }
  catch (std::exception &e) {
    std::cout << "Exception caught in ordering" << std::endl;
    std::cout << e.what() << std::endl;
    return 1;
  }

  return 0;
}

int main(int narg, char** arg)
{
  Tpetra::ScopeGuard tscope(&narg, &arg);
  Teuchos::RCP<const Teuchos::Comm<int> > comm = Tpetra::getDefaultComm();

  int result = mainExecute(narg, arg, comm);

  // get reduced return code form all procsses
  comm->barrier();
  int resultReduced;
  reduceAll<int,int>(*comm, Teuchos::EReductionType::REDUCE_MAX, 1,
                     &result, &resultReduced);

  // provide a final message which guarantees that the test will fail
  // if any of the processes failed
  if (comm->getRank() == 0) {
    std::cout << "Scotch Ordering test with " << comm->getSize()
              << " processes has test return code " << resultReduced
              << " and is exiting in the "
              << ((resultReduced == 0 ) ? "PASSED" : "FAILED") << " state."
              << std::endl;
  }
}