BasePolicies.h

Go to the documentation of this file.

/*
 * This file belongs to the Galois project, a C++ library for exploiting
 * parallelism. The code is being released under the terms of the 3-Clause BSD
 * License (a copy is located in LICENSE.txt at the top-level directory).
 *
 * Copyright (C) 2019, The University of Texas at Austin. All rights reserved.
 * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
 * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
 * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
 * DEALING OR USAGE OF TRADE.  NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
 * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
 * shall University be liable for incidental, special, indirect, direct or
 * consequential damages or loss of profits, interruption of business, or
 * related expenses which may arise from use of Software or Documentation,
 * including but not limited to those resulting from defects in Software and/or
 * Documentation, or loss or inaccuracy of data of any kind.
 */

#ifndef _GALOIS_CUSP_PSCAFFOLD_H_
#define _GALOIS_CUSP_PSCAFFOLD_H_

namespace galois {
namespace graphs {

class PartitioningScaffold {
protected:
  uint32_t _hostID;   
  uint32_t _numHosts; 
  uint64_t _numNodes; 
  uint64_t _numEdges; 
  std::vector<std::pair<uint64_t, uint64_t>> _gid2host;

public:
  PartitioningScaffold(uint32_t hostID, uint32_t numHosts, uint64_t numNodes,
                       uint64_t numEdges)
      : _hostID(hostID), _numHosts(numHosts), _numNodes(numNodes),
        _numEdges(numEdges) {}

  void saveGIDToHost(std::vector<std::pair<uint64_t, uint64_t>>& gid2host) {
    _gid2host = gid2host;
  }
};

class ReadMasterAssignment : public PartitioningScaffold {
public:
  ReadMasterAssignment(uint32_t hostID, uint32_t numHosts, uint64_t numNodes,
                       uint64_t numEdges)
      : PartitioningScaffold(hostID, numHosts, numNodes, numEdges) {}

  uint32_t retrieveMaster(uint32_t gid) const {
    for (auto h = 0U; h < _numHosts; ++h) {
      uint64_t start, end;
      std::tie(start, end) = _gid2host[h];
      if (gid >= start && gid < end) {
        return h;
      }
    }
    assert(false);
    return _numHosts;
  }

  // below all unused if not assigning masters in default manner, but must be
  // defined or compiler complains

  bool masterAssignPhase() const { return false; }
  void enterStage2() {}

  template <typename EdgeTy>
  uint32_t getMaster(uint32_t, galois::graphs::BufferedGraph<EdgeTy>&,
                     const std::vector<uint32_t>&,
                     std::unordered_map<uint64_t, uint32_t>&,
                     const std::vector<uint64_t>&,
                     std::vector<galois::CopyableAtomic<uint64_t>>&,
                     const std::vector<uint64_t>&,
                     std::vector<galois::CopyableAtomic<uint64_t>>&) {
    return 0;
  }

  void saveGID2HostInfo(std::unordered_map<uint64_t, uint32_t>&,
                        std::vector<uint32_t>&, uint64_t) {}
  bool addMasterMapping(uint32_t, uint32_t) { return false; }
};

class CustomMasterAssignment : public PartitioningScaffold {
protected:
  char _status; 
  std::vector<uint32_t> _localNodeToMaster;
  std::unordered_map<uint64_t, uint32_t> _gid2masters;
  uint64_t _nodeOffset;

  unsigned getHostReader(uint64_t gid) const {
    for (auto i = 0U; i < _numHosts; ++i) {
      uint64_t start, end;
      std::tie(start, end) = _gid2host[i];
      if (gid >= start && gid < end) {
        return i;
      }
    }
    return -1;
  }

public:
  CustomMasterAssignment(uint32_t hostID, uint32_t numHosts, uint64_t numNodes,
                         uint64_t numEdges)
      : PartitioningScaffold(hostID, numHosts, numNodes, numEdges), _status(0) {
  }

  uint32_t retrieveMaster(uint32_t gid) const {
    if (_status != 0) {
      // use map if not a locally read node, else use vector
      if (getHostReader(gid) != _hostID) {
        auto gidMasterIter = _gid2masters.find(gid);
        // found in map
        if (gidMasterIter != _gid2masters.end()) {
          uint32_t mappedMaster = gidMasterIter->second;
          // galois::gDebug("[", _hostID, "] ", gid, " found with master ",
          //               mappedMaster, "!");
          // make sure host is in bounds
          assert(mappedMaster < _numHosts);
          return mappedMaster;
        } else {
          // NOT FOUND (not necessarily a bad thing, and required for
          // some cases)
          galois::gDebug("[", _hostID, "] ", gid, " not found!");
          if (_status == 2) {
            // die if we expect all gids to be mapped already (stage 2)
            GALOIS_DIE("should not fail to find a GID after stage 2 "
                       "of master assignment phase");
          }
          return (uint32_t)-1;
        }
      } else {
        // determine offset
        uint32_t offsetIntoMap = gid - _nodeOffset;
        assert(offsetIntoMap != (uint32_t)-1);
        assert(offsetIntoMap < _localNodeToMaster.size());
        return _localNodeToMaster[offsetIntoMap];
      }
    } else {
      // stage 0 = this function shouldn't be called
      GALOIS_DIE("master setup incomplete");
      return (uint32_t)-1;
    }
  }

  void saveGID2HostInfo(std::unordered_map<uint64_t, uint32_t>& gid2offsets,
                        std::vector<uint32_t>& localNodeToMaster,
                        uint64_t nodeOffset) {
#ifndef NDEBUG
    size_t originalSize = _gid2masters.size();
#endif

    for (auto i = gid2offsets.begin(); i != gid2offsets.end(); i++) {
      assert(i->second < localNodeToMaster.size());
      galois::gDebug("Map ", i->first, " to ", localNodeToMaster[i->second]);
      _gid2masters[i->first] = localNodeToMaster[i->second];
    }
    assert(_gid2masters.size() == (originalSize + gid2offsets.size()));
    // get memory back
    gid2offsets.clear();

    size_t myLocalNodes = _gid2host[_hostID].second - _gid2host[_hostID].first;
    assert((myLocalNodes + _gid2masters.size() - originalSize) ==
           localNodeToMaster.size());
    // copy over to this structure
    _localNodeToMaster = std::move(localNodeToMaster);
    assert(myLocalNodes <= _localNodeToMaster.size());

    // resize to fit only this host's read nodes
    _localNodeToMaster.resize(myLocalNodes);
    _nodeOffset = nodeOffset;

    // stage 1 setup complete
    _status = 1;
  }

  bool masterAssignPhase() const { return true; }
  void enterStage2() { _status = 2; }

  template <typename EdgeTy>
  uint32_t getMaster(uint32_t, galois::graphs::BufferedGraph<EdgeTy>&,
                     const std::vector<uint32_t>&,
                     std::unordered_map<uint64_t, uint32_t>&,
                     const std::vector<uint64_t>&,
                     std::vector<galois::CopyableAtomic<uint64_t>>&,
                     const std::vector<uint64_t>&,
                     std::vector<galois::CopyableAtomic<uint64_t>>&) {
    return (uint32_t)-1;
  }

  bool addMasterMapping(uint32_t gid, uint32_t mappedMaster) {
    assert(mappedMaster < _numHosts);
    if (_status <= 1) {
      auto offsetIntoMapIter = _gid2masters.find(gid);
      if (offsetIntoMapIter == _gid2masters.end()) {
        // NOT FOUND
        galois::gDebug("[", _hostID, "] ", gid, " not found; mapping!");
        _gid2masters[gid] = mappedMaster;
        return true;
      } else {
        // already mapped
        galois::gDebug("[", _hostID, "] ", gid, " already mapped with master ",
                       offsetIntoMapIter->second, "!");
        assert(offsetIntoMapIter->second == mappedMaster);
        return false;
      }
    } else {
      GALOIS_DIE("unexpected status in add master mapping: ", _status);
      return false;
    }
  }
};

} // end namespace graphs
} // end namespace galois

#endif