localVectors.hh

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*  This file is part of the library KASKADE 7                               */
/*  https://www.zib.de/research/projects/kaskade7-finite-element-toolbox     */
/*                                                                           */
/*  Copyright (C) 2018-2018 Zuse Institute Berlin                            */
/*                                                                           */
/*  KASKADE 7 is distributed under the terms of the ZIB Academic License.    */
/*    see $KASKADE/academic.txt                                              */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef LOCALVECTORS_HH
#define LOCALVECTORS_HH
 
#include <vector>
#include <mutex>
 
namespace Kaskade
{
  
  template <class Entry, class SortedIdx>
  class LocalVector
  {
  public:
 
    LocalVector(SortedIdx const& idx, Entry* data_)
    : idx_(idx), data(data_)
    {
    }
    
    SortedIdx idx() const { return idx_; }
 
    size_t size() const
    {
      return idx().size();
    }
    
    void relocate(Entry* newData)
    {
      data = newData;
    }
    
    Entry& operator[](int idx)
    {
      return data[idx];
    }
    
    Entry const& operator[](int idx) const
    {
      return data[idx];
    }
    
  private:
    SortedIdx idx_;
    
    // a pointer to the raw storage for the entries
    Entry* data;
  };
  
  template <class Entry, class SortedIdx, class Vector>
  class LocalVectors
  {
  public:
    using value_type = LocalVector<Entry,SortedIdx>;
    
    LocalVectors(Vector& globalVector, std::vector<std::mutex> & scatterMutexes_, size_t maxStorage=256*1024)
    : globalVector(&globalVector), scatterMutexes(&scatterMutexes_)
    {
      // Allocate memory as desired. The vector will only grow if there is a local matrix with more entries than defined here.
      localData.reserve(maxStorage/sizeof(Entry));
      if(scatterMutexes_.empty())
      {
        throw DetailedException("At least one mutex must be given.",__FILE__,__LINE__);
      }
    }
    
    LocalVectors()
    {}
    
    ~LocalVectors()
    {
      scatter();
    }
 
    void push_back(SortedIdx const& idx)
    {
      size_t size = idx.size();
      
      // Appending the new vector exceeds the storage capacity. Scatter the existing vectors to their target and
      // remove them.
      if (localData.capacity() < localData.size()+size)
        scatter();
      
      // Append the new local vector. Note that either the capacity of localData is sufficient, and
      // the localVectors data pointers remain valid, or the local vectors have been scattered,
      // such that localVectors is empty and no pointer exists that could be invalidated.
      Entry* pos = &*localData.insert(localData.end(),size,Entry(0));
      localVectors.emplace_back(idx,pos);
    }
 
    value_type      & operator[](int n)       { return localVectors[n]; }
    value_type const& operator[](int n) const { return localVectors[n]; }
    
    value_type      & back()       { return localVectors.back(); }
    value_type const& back() const { return localVectors.back(); }
    
    size_t size() const { return localVectors.size(); }
    
    void scatter()
    {
      if (localData.empty()) return;
 
      if (!globalVector)
      {
        throw DetailedException("No global vector given to scatter to",__FILE__,__LINE__);
      }
 
      // step through all global vector ranges and scatter all the included local vectors' components
      unsigned n = scatterMutexes->size();
      for (unsigned ri=0; ri<n; ++ri)
      {
        // lock global vector range
        std::lock_guard<std::mutex> lock((*scatterMutexes)[ri]);
 
        // step through all local vectors
        for (auto const& vec : localVectors)
        {
          size_t globalStartIdx = uniformWeightRangeStart(ri,   n, globalVector->size());
          size_t globalEndIdx   = uniformWeightRangeStart(ri+1, n, globalVector->size());
 
          for (auto const& glIdx : vec.idx())
          {
            // check which rows are inside the global vector range
            if (glIdx.first >= globalEndIdx) break; // vec.idx() are sorted by global index
            if (globalStartIdx <= glIdx.first)
            {
              (*globalVector)[glIdx.first] += vec[glIdx.second];
            }
          }
        }
      }
 
      // everything's scattered - clean up
      clear();
    }
    
    void clear() 
    {
      localData.clear();
      localVectors.clear();
    }
    
    size_t storageSize() const
    {
      return localData.size() * sizeof(Entry);
    }
 
  private:
    // This allows to hold a single array into which the local vectors are scattered, and
    // thus improves memory locality (for better cache hit rates and less false sharing).
    // Contains the local vectors one after the other.
    std::vector<Entry> localData;
    // Storage for local vectors.
    std::vector<value_type> localVectors;
 
    Vector* globalVector = nullptr;
    std::vector<std::mutex>* scatterMutexes = nullptr;
  };
  
}
 
#endif