diff options
Diffstat (limited to 'bottleneck/include/dnn')
| -rw-r--r-- | bottleneck/include/dnn/geometry/euclidean-fixed.h | 162 | ||||
| -rw-r--r-- | bottleneck/include/dnn/local/kd-tree.h | 106 | ||||
| -rw-r--r-- | bottleneck/include/dnn/local/kd-tree.hpp | 296 | ||||
| -rw-r--r-- | bottleneck/include/dnn/local/search-functors.h | 119 | ||||
| -rw-r--r-- | bottleneck/include/dnn/parallel/tbb.h | 235 | ||||
| -rw-r--r-- | bottleneck/include/dnn/parallel/utils.h | 100 | ||||
| -rw-r--r-- | bottleneck/include/dnn/utils.h | 47 |
7 files changed, 1065 insertions, 0 deletions
diff --git a/bottleneck/include/dnn/geometry/euclidean-fixed.h b/bottleneck/include/dnn/geometry/euclidean-fixed.h new file mode 100644 index 0000000..f45b980 --- /dev/null +++ b/bottleneck/include/dnn/geometry/euclidean-fixed.h @@ -0,0 +1,162 @@ +#ifndef HERA_BT_DNN_GEOMETRY_EUCLIDEAN_FIXED_H +#define HERA_BT_DNN_GEOMETRY_EUCLIDEAN_FIXED_H + +#include <boost/operators.hpp> +#include <boost/array.hpp> +#include <boost/range/value_type.hpp> +#include <boost/serialization/access.hpp> +#include <boost/serialization/base_object.hpp> + +#include <fstream> +#include <string> +#include <sstream> +#include <cmath> + +#include "../parallel/tbb.h" // for dnn::vector<...> + +namespace hera { +namespace bt { +namespace dnn +{ + // TODO: wrap in another namespace (e.g., euclidean) + + template<size_t D, typename Real = double> + struct Point: + boost::addable< Point<D,Real>, + boost::subtractable< Point<D,Real>, + boost::dividable2< Point<D, Real>, Real, + boost::multipliable2< Point<D, Real>, Real > > > >, + public boost::array<Real, D> + { + public: + typedef Real Coordinate; + typedef Real DistanceType; + + + public: + Point(size_t id = 0): id_(id) {} + template<size_t DD> + Point(const Point<DD,Real>& p, size_t id = 0): + id_(id) { *this = p; } + + static size_t dimension() { return D; } + + // Assign a point of different dimension + template<size_t DD> + Point& operator=(const Point<DD,Real>& p) { for (size_t i = 0; i < (D < DD ? D : DD); ++i) (*this)[i] = p[i]; if (DD < D) for (size_t i = DD; i < D; ++i) (*this)[i] = 0; return *this; } + + Point& operator+=(const Point& p) { for (size_t i = 0; i < D; ++i) (*this)[i] += p[i]; return *this; } + Point& operator-=(const Point& p) { for (size_t i = 0; i < D; ++i) (*this)[i] -= p[i]; return *this; } + Point& operator/=(Real r) { for (size_t i = 0; i < D; ++i) (*this)[i] /= r; return *this; } + Point& operator*=(Real r) { for (size_t i = 0; i < D; ++i) (*this)[i] *= r; return *this; } + + Real norm2() const { Real n = 0; for (size_t i = 0; i < D; ++i) n += (*this)[i] * (*this)[i]; return n; } + Real max_norm() const + { + Real m = std::fabs((*this)[0]); + for (size_t i = 1; i < D; ++i) + if (std::fabs((*this)[i]) > m) + m = std::fabs((*this)[i]); + return m; } + + // quick and dirty for now; make generic later + //DistanceType distance(const Point& other) const { return sqrt(sq_distance(other)); } + //DistanceType sq_distance(const Point& other) const { return (other - *this).norm2(); } + + DistanceType distance(const Point& other) const { return (other - *this).max_norm(); } + DistanceType sq_distance(const Point& other) const { DistanceType d = distance(other); return d*d; } + + size_t id() const { return id_; } + size_t& id() { return id_; } + + private: + friend class boost::serialization::access; + + template<class Archive> + void serialize(Archive& ar, const unsigned int version) { ar & boost::serialization::base_object< boost::array<Real,D> >(*this) & id_; } + + private: + size_t id_; + }; + + template<size_t D, typename Real> + std::ostream& + operator<<(std::ostream& out, const Point<D,Real>& p) + { out << p[0]; for (size_t i = 1; i < D; ++i) out << " " << p[i]; return out; } + + + template<class Point> + struct PointTraits; // intentionally undefined; should be specialized for each type + + template<size_t D, typename Real> + struct PointTraits< Point<D, Real> > // specialization for dnn::Point + { + typedef Point<D,Real> PointType; + typedef const PointType* PointHandle; + typedef std::vector<PointType> PointContainer; + + typedef typename PointType::Coordinate Coordinate; + typedef typename PointType::DistanceType DistanceType; + + static DistanceType + distance(const PointType& p1, const PointType& p2) { return p1.distance(p2); } + static DistanceType + distance(PointHandle p1, PointHandle p2) { return distance(*p1,*p2); } + static DistanceType + sq_distance(const PointType& p1, + const PointType& p2) { return p1.sq_distance(p2); } + static DistanceType + sq_distance(PointHandle p1, PointHandle p2) { return sq_distance(*p1,*p2); } + static size_t dimension() { return D; } + static Real coordinate(const PointType& p, size_t i) { return p[i]; } + static Real& coordinate(PointType& p, size_t i) { return p[i]; } + static Real coordinate(PointHandle p, size_t i) { return coordinate(*p,i); } + + static size_t id(const PointType& p) { return p.id(); } + static size_t& id(PointType& p) { return p.id(); } + static size_t id(PointHandle p) { return id(*p); } + + static PointHandle + handle(const PointType& p) { return &p; } + static const PointType& + point(PointHandle ph) { return *ph; } + + void swap(PointType& p1, PointType& p2) const { return std::swap(p1, p2); } + + static PointContainer + container(size_t n = 0, const PointType& p = PointType()) { return PointContainer(n, p); } + static typename PointContainer::iterator + iterator(PointContainer& c, PointHandle ph) { return c.begin() + (ph - &c[0]); } + static typename PointContainer::const_iterator + iterator(const PointContainer& c, PointHandle ph) { return c.begin() + (ph - &c[0]); } + + private: + friend class boost::serialization::access; + + template<class Archive> + void serialize(Archive& ar, const unsigned int version) {} + }; + + template<class PointContainer> + void read_points(const std::string& filename, PointContainer& points) + { + typedef typename boost::range_value<PointContainer>::type Point; + typedef typename PointTraits<Point>::Coordinate Coordinate; + + std::ifstream in(filename.c_str()); + std::string line; + while(std::getline(in, line)) + { + if (line[0] == '#') continue; // comment line in the file + std::stringstream linestream(line); + Coordinate x; + points.push_back(Point()); + size_t i = 0; + while (linestream >> x) + points.back()[i++] = x; + } + } +} // dnn +} // bt +} // hera +#endif diff --git a/bottleneck/include/dnn/local/kd-tree.h b/bottleneck/include/dnn/local/kd-tree.h new file mode 100644 index 0000000..c1aed2b --- /dev/null +++ b/bottleneck/include/dnn/local/kd-tree.h @@ -0,0 +1,106 @@ +#ifndef HERA_BT_DNN_LOCAL_KD_TREE_H +#define HERA_BT_DNN_LOCAL_KD_TREE_H + +#include "../utils.h" +#include "search-functors.h" + +#include <unordered_map> +#include <stack> + +#include <boost/tuple/tuple.hpp> +#include <boost/shared_ptr.hpp> +#include <boost/range/value_type.hpp> + +#include <boost/static_assert.hpp> +#include <boost/type_traits.hpp> + +namespace hera { +namespace bt { +namespace dnn +{ + // Weighted KDTree + // Traits_ provides Coordinate, DistanceType, PointType, dimension(), distance(p1,p2), coordinate(p,i) + template< class Traits_ > + class KDTree + { + public: + typedef Traits_ Traits; + typedef hera::bt::dnn::HandleDistance<KDTree> HandleDistance; + + typedef typename Traits::PointType Point; + typedef typename Traits::PointHandle PointHandle; + typedef typename Traits::Coordinate Coordinate; + typedef typename Traits::DistanceType DistanceType; + typedef std::vector<PointHandle> HandleContainer; + typedef std::vector<HandleDistance> HDContainer; // TODO: use tbb::scalable_allocator + typedef HDContainer Result; + typedef std::vector<DistanceType> DistanceContainer; + typedef std::unordered_map<PointHandle, size_t> HandleMap; + //private: + typedef typename HandleContainer::iterator HCIterator; + typedef std::tuple<HCIterator, HCIterator, size_t, ssize_t> KDTreeNode; + typedef std::tuple<HCIterator, HCIterator> KDTreeNodeNoCut; + + //BOOST_STATIC_ASSERT_MSG(has_coordinates<Traits, PointHandle, int>::value, "KDTree requires coordinates"); + + public: + KDTree(const Traits& traits): + traits_(traits) {} + + KDTree(const Traits& traits, HandleContainer&& handles); + + template<class Range> + KDTree(const Traits& traits, const Range& range); + + template<class Range> + void init(const Range& range); + + HandleDistance find(PointHandle q) const; + Result findR(PointHandle q, DistanceType r) const; // all neighbors within r + Result findFirstR(PointHandle q, DistanceType r) const; // first neighbor within r + Result findK(PointHandle q, size_t k) const; // k nearest neighbors + + HandleDistance find(const Point& q) const { return find(traits().handle(q)); } + Result findR(const Point& q, DistanceType r) const { return findR(traits().handle(q), r); } + Result findFirstR(const Point& q, DistanceType r) const { return findFirstR(traits().handle(q), r); } + Result findK(const Point& q, size_t k) const { return findK(traits().handle(q), k); } + + + + template<class ResultsFunctor> + void search(PointHandle q, ResultsFunctor& rf) const; + + const Traits& traits() const { return traits_; } + + void get_path_to_root(const size_t idx, std::stack<KDTreeNodeNoCut>& s); + // to support deletion + void init_n_elems(); + void delete_point(const size_t idx); + void delete_point(PointHandle p); + void update_n_elems(const ssize_t idx, const int delta); + void increase_n_elems(const ssize_t idx); + void decrease_n_elems(const ssize_t idx); + size_t get_num_points() const { return num_points_; } + //private: + void init(); + + + struct CoordinateComparison; + struct OrderTree; + + //private: + Traits traits_; + HandleContainer tree_; + std::vector<char> delete_flags_; + std::vector<int> subtree_n_elems; + HandleMap indices_; + std::vector<ssize_t> parents_; + + size_t num_points_; + }; +} // dnn +} // bt +} // hera +#include "kd-tree.hpp" + +#endif diff --git a/bottleneck/include/dnn/local/kd-tree.hpp b/bottleneck/include/dnn/local/kd-tree.hpp new file mode 100644 index 0000000..5b84eb0 --- /dev/null +++ b/bottleneck/include/dnn/local/kd-tree.hpp @@ -0,0 +1,296 @@ +#include <boost/range/counting_range.hpp> +#include <boost/range/algorithm_ext/push_back.hpp> +#include <boost/range.hpp> + +#include <queue> + +#include "../parallel/tbb.h" + +template<class T> +hera::bt::dnn::KDTree<T>::KDTree(const Traits& traits, HandleContainer&& handles): + traits_(traits), + tree_(std::move(handles)), + delete_flags_(handles.size(), static_cast<char>(0) ), + subtree_n_elems(handles.size(), static_cast<size_t>(0)), + num_points_(handles.size()) +{ + init(); +} + +template<class T> +template<class Range> +hera::bt::dnn::KDTree<T>::KDTree(const Traits& traits, const Range& range): + traits_(traits) +{ + init(range); +} + +template<class T> +template<class Range> +void hera::bt::dnn::KDTree<T>::init(const Range& range) +{ + size_t sz = std::distance(std::begin(range), std::end(range)); + subtree_n_elems = std::vector<int>(sz, 0); + delete_flags_ = std::vector<char>(sz, 0); + num_points_ = sz; + tree_.reserve(sz); + for (PointHandle h : range) + tree_.push_back(h); + parents_.resize(sz, -1); + init(); +} + +template<class T> +void hera::bt::dnn::KDTree<T>::init() +{ + if (tree_.empty()) + return; + +#if defined(TBB) + task_group g; + g.run(OrderTree(this, tree_.begin(), tree_.end(), -1, 0, traits())); + g.wait(); +#else + OrderTree(this, tree_.begin(), tree_.end(), -1, 0, traits()).serial(); +#endif + + for (size_t i = 0; i < tree_.size(); ++i) + indices_[tree_[i]] = i; + init_n_elems(); +} + +template<class T> +struct +hera::bt::dnn::KDTree<T>::OrderTree +{ + OrderTree(KDTree* tree_, HCIterator b_, HCIterator e_, ssize_t p_, size_t i_, const Traits& traits_): + tree(tree_), b(b_), e(e_), p(p_), i(i_), traits(traits_) {} + + void operator()() const + { + if (e - b < 1000) + { + serial(); + return; + } + + HCIterator m = b + (e - b)/2; + ssize_t im = m - tree->tree_.begin(); + tree->parents_[im] = p; + + CoordinateComparison cmp(i, traits); + std::nth_element(b,m,e, cmp); + size_t next_i = (i + 1) % traits.dimension(); + + task_group g; + if (b < m - 1) g.run(OrderTree(tree, b, m, im, next_i, traits)); + if (e > m + 2) g.run(OrderTree(tree, m+1, e, im, next_i, traits)); + g.wait(); + } + + void serial() const + { + std::queue<KDTreeNode> q; + q.push(KDTreeNode(b,e,p,i)); + while (!q.empty()) + { + HCIterator b, e; ssize_t p; size_t i; + std::tie(b,e,p,i) = q.front(); + q.pop(); + HCIterator m = b + (e - b)/2; + ssize_t im = m - tree->tree_.begin(); + tree->parents_[im] = p; + + CoordinateComparison cmp(i, traits); + std::nth_element(b,m,e, cmp); + size_t next_i = (i + 1) % traits.dimension(); + + // Replace with a size condition instead? + if (m - b > 1) + q.push(KDTreeNode(b, m, im, next_i)); + else if (b < m) + tree->parents_[im - 1] = im; + if (e - m > 2) + q.push(KDTreeNode(m+1, e, im, next_i)); + else if (e > m + 1) + tree->parents_[im + 1] = im; + } + } + + KDTree* tree; + HCIterator b, e; + ssize_t p; + size_t i; + const Traits& traits; +}; + +template<class T> +void hera::bt::dnn::KDTree<T>::update_n_elems(ssize_t idx, const int delta) +// add delta to the number of points in node idx and update subtree_n_elems +// for all parents of the node idx +{ + //std::cout << "subtree_n_elems.size = " << subtree_n_elems.size() << std::endl; + // update the node itself + while (idx != -1) + { + //std::cout << idx << std::endl; + subtree_n_elems[idx] += delta; + idx = parents_[idx]; + } +} + +template<class T> +void hera::bt::dnn::KDTree<T>::increase_n_elems(const ssize_t idx) +{ + update_n_elems(idx, static_cast<ssize_t>(1)); +} + +template<class T> +void hera::bt::dnn::KDTree<T>::decrease_n_elems(const ssize_t idx) +{ + update_n_elems(idx, static_cast<ssize_t>(-1)); +} + +template<class T> +void hera::bt::dnn::KDTree<T>::init_n_elems() +{ + for(size_t idx = 0; idx < tree_.size(); ++idx) { + increase_n_elems(idx); + } +} + + +template<class T> +template<class ResultsFunctor> +void hera::bt::dnn::KDTree<T>::search(PointHandle q, ResultsFunctor& rf) const +{ + typedef typename HandleContainer::const_iterator HCIterator; + typedef std::tuple<HCIterator, HCIterator, size_t> KDTreeNode; + + if (tree_.empty()) + return; + + DistanceType D = std::numeric_limits<DistanceType>::infinity(); + + // TODO: use tbb::scalable_allocator for the queue + std::queue<KDTreeNode> nodes; + + nodes.push(KDTreeNode(tree_.begin(), tree_.end(), 0)); + + //std::cout << "started kdtree::search" << std::endl; + + while (!nodes.empty()) + { + HCIterator b, e; size_t i; + std::tie(b,e,i) = nodes.front(); + nodes.pop(); + + CoordinateComparison cmp(i, traits()); + i = (i + 1) % traits().dimension(); + + HCIterator m = b + (e - b)/2; + size_t m_idx = m - tree_.begin(); + // ignore deleted points + if ( delete_flags_[m_idx] == 0 ) { + DistanceType dist = traits().distance(q, *m); + // + weights_[m - tree_.begin()]; + //std::cout << "Supplied to functor: m : "; + //std::cout << "(" << (*(*m))[0] << ", " << (*(*m))[1] << ")"; + //std::cout << " and q : "; + //std::cout << "(" << (*q)[0] << ", " << (*q)[1] << ")" << std::endl; + //std::cout << "dist^q + weight = " << dist << std::endl; + //std::cout << "weight = " << weights_[m - tree_.begin()] << std::endl; + //std::cout << "dist = " << traits().distance(q, *m) << std::endl; + //std::cout << "dist^q = " << pow(traits().distance(q, *m), wassersteinPower) << std::endl; + + D = rf(*m, dist); + } + // we are really searching w.r.t L_\infty ball; could prune better with an L_2 ball + Coordinate diff = cmp.diff(q, *m); // diff returns signed distance + DistanceType diffToWasserPower = (diff > 0 ? 1.0 : -1.0) * fabs(diff); + + size_t lm = m + 1 + (e - (m+1))/2 - tree_.begin(); + if ( e > m + 1 and subtree_n_elems[lm] > 0 ) { + if (e > m + 1 && diffToWasserPower >= -D) { + nodes.push(KDTreeNode(m+1, e, i)); + } + } + + size_t rm = b + (m - b) / 2 - tree_.begin(); + if ( subtree_n_elems[rm] > 0 ) { + if (b < m && diffToWasserPower <= D) { + nodes.push(KDTreeNode(b, m, i)); + } + } + } + //std::cout << "exited kdtree::search" << std::endl; +} + +template<class T> +typename hera::bt::dnn::KDTree<T>::HandleDistance hera::bt::dnn::KDTree<T>::find(PointHandle q) const +{ + hera::bt::dnn::NNRecord<HandleDistance> nn; + search(q, nn); + return nn.result; +} + +template<class T> +typename hera::bt::dnn::KDTree<T>::Result hera::bt::dnn::KDTree<T>::findR(PointHandle q, DistanceType r) const +{ + hera::bt::dnn::rNNRecord<HandleDistance> rnn(r); + search(q, rnn); + //std::sort(rnn.result.begin(), rnn.result.end()); + return rnn.result; +} + +template<class T> +typename hera::bt::dnn::KDTree<T>::Result hera::bt::dnn::KDTree<T>::findFirstR(PointHandle q, DistanceType r) const +{ + hera::bt::dnn::firstrNNRecord<HandleDistance> rnn(r); + search(q, rnn); + return rnn.result; +} + +template<class T> +typename hera::bt::dnn::KDTree<T>::Result hera::bt::dnn::KDTree<T>::findK(PointHandle q, size_t k) const +{ + hera::bt::dnn::kNNRecord<HandleDistance> knn(k); + search(q, knn); + // do we need this??? + std::sort(knn.result.begin(), knn.result.end()); + return knn.result; +} + +template<class T> +struct hera::bt::dnn::KDTree<T>::CoordinateComparison +{ + CoordinateComparison(size_t i, const Traits& traits): + i_(i), traits_(traits) {} + + bool operator()(PointHandle p1, PointHandle p2) const { return coordinate(p1) < coordinate(p2); } + Coordinate diff(PointHandle p1, PointHandle p2) const { return coordinate(p1) - coordinate(p2); } + + Coordinate coordinate(PointHandle p) const { return traits_.coordinate(p, i_); } + size_t axis() const { return i_; } + + private: + size_t i_; + const Traits& traits_; +}; + +template<class T> +void hera::bt::dnn::KDTree<T>::delete_point(const size_t idx) +{ + // prevent double deletion + assert(delete_flags_[idx] == 0); + delete_flags_[idx] = 1; + decrease_n_elems(idx); + --num_points_; +} + +template<class T> +void hera::bt::dnn::KDTree<T>::delete_point(PointHandle p) +{ + delete_point(indices_[p]); +} + diff --git a/bottleneck/include/dnn/local/search-functors.h b/bottleneck/include/dnn/local/search-functors.h new file mode 100644 index 0000000..63ad11d --- /dev/null +++ b/bottleneck/include/dnn/local/search-functors.h @@ -0,0 +1,119 @@ +#ifndef HERA_BT_DNN_LOCAL_SEARCH_FUNCTORS_H +#define HERA_BT_DNN_LOCAL_SEARCH_FUNCTORS_H + +#include <boost/range/algorithm/heap_algorithm.hpp> + +namespace hera +{ +namespace bt +{ +namespace dnn +{ + +template<class NN> +struct HandleDistance +{ + typedef typename NN::PointHandle PointHandle; + typedef typename NN::DistanceType DistanceType; + typedef typename NN::HDContainer HDContainer; + + HandleDistance() {} + HandleDistance(PointHandle pp, DistanceType dd): + p(pp), d(dd) {} + bool operator<(const HandleDistance& other) const { return d < other.d; } + + PointHandle p; + DistanceType d; +}; + +template<class HandleDistance> +struct NNRecord +{ + typedef typename HandleDistance::PointHandle PointHandle; + typedef typename HandleDistance::DistanceType DistanceType; + + NNRecord() { result.d = std::numeric_limits<DistanceType>::infinity(); } + DistanceType operator()(PointHandle p, DistanceType d) { if (d < result.d) { result.p = p; result.d = d; } return result.d; } + HandleDistance result; +}; + +template<class HandleDistance> +struct rNNRecord +{ + typedef typename HandleDistance::PointHandle PointHandle; + typedef typename HandleDistance::DistanceType DistanceType; + typedef typename HandleDistance::HDContainer HDContainer; + + rNNRecord(DistanceType r_): r(r_) {} + DistanceType operator()(PointHandle p, DistanceType d) + { + if (d <= r) + result.push_back(HandleDistance(p,d)); + return r; + } + + DistanceType r; + HDContainer result; +}; + +template<class HandleDistance> +struct firstrNNRecord +{ + typedef typename HandleDistance::PointHandle PointHandle; + typedef typename HandleDistance::DistanceType DistanceType; + typedef typename HandleDistance::HDContainer HDContainer; + + firstrNNRecord(DistanceType r_): r(r_) {} + + DistanceType operator()(PointHandle p, DistanceType d) + { + if (d <= r) { + result.push_back(HandleDistance(p,d)); + return -100000000.0; + } else { + return r; + } + } + + DistanceType r; + HDContainer result; +}; + + +template<class HandleDistance> +struct kNNRecord +{ + typedef typename HandleDistance::PointHandle PointHandle; + typedef typename HandleDistance::DistanceType DistanceType; + typedef typename HandleDistance::HDContainer HDContainer; + + kNNRecord(unsigned k_): k(k_) {} + DistanceType operator()(PointHandle p, DistanceType d) + { + if (result.size() < k) + { + result.push_back(HandleDistance(p,d)); + boost::push_heap(result); + if (result.size() < k) + return std::numeric_limits<DistanceType>::infinity(); + } else if (d < result[0].d) + { + boost::pop_heap(result); + result.back() = HandleDistance(p,d); + boost::push_heap(result); + } + if ( result.size() > 1 ) { + assert( result[0].d >= result[1].d ); + } + return result[0].d; + } + + unsigned k; + HDContainer result; +}; + +} // dnn +} // bt +} // hera + +#endif // HERA_BT_DNN_LOCAL_SEARCH_FUNCTORS_H diff --git a/bottleneck/include/dnn/parallel/tbb.h b/bottleneck/include/dnn/parallel/tbb.h new file mode 100644 index 0000000..14f0093 --- /dev/null +++ b/bottleneck/include/dnn/parallel/tbb.h @@ -0,0 +1,235 @@ +#ifndef HERA_BT_PARALLEL_H +#define HERA_BT_PARALLEL_H + +#ifndef FOR_R_TDA +#include <iostream> +#endif + +#include <vector> + +#include <boost/range.hpp> +#include <boost/bind.hpp> +#include <boost/foreach.hpp> + +#ifdef TBB + +#include <tbb/tbb.h> +#include <tbb/concurrent_hash_map.h> +#include <tbb/scalable_allocator.h> + +#include <boost/serialization/split_free.hpp> +#include <boost/serialization/collections_load_imp.hpp> +#include <boost/serialization/collections_save_imp.hpp> + +namespace hera { +namespace bt { +namespace dnn +{ + using tbb::mutex; + using tbb::task_scheduler_init; + using tbb::task_group; + using tbb::task; + + template<class T> + struct vector + { + typedef tbb::concurrent_vector<T> type; + }; + + template<class T> + struct atomic + { + typedef tbb::atomic<T> type; + static T compare_and_swap(type& v, T n, T o) { return v.compare_and_swap(n,o); } + }; + + template<class Iterator, class F> + void do_foreach(Iterator begin, Iterator end, const F& f) { tbb::parallel_do(begin, end, f); } + + template<class Range, class F> + void for_each_range_(const Range& r, const F& f) + { + for (typename Range::iterator cur = r.begin(); cur != r.end(); ++cur) + f(*cur); + } + + template<class F> + void for_each_range(size_t from, size_t to, const F& f) + { + //static tbb::affinity_partitioner ap; + //tbb::parallel_for(c.range(), boost::bind(&for_each_range_<typename Container::range_type, F>, _1, f), ap); + tbb::parallel_for(from, to, f); + } + + template<class Container, class F> + void for_each_range(const Container& c, const F& f) + { + //static tbb::affinity_partitioner ap; + //tbb::parallel_for(c.range(), boost::bind(&for_each_range_<typename Container::range_type, F>, _1, f), ap); + tbb::parallel_for(c.range(), boost::bind(&for_each_range_<typename Container::const_range_type, F>, _1, f)); + } + + template<class Container, class F> + void for_each_range(Container& c, const F& f) + { + //static tbb::affinity_partitioner ap; + //tbb::parallel_for(c.range(), boost::bind(&for_each_range_<typename Container::range_type, F>, _1, f), ap); + tbb::parallel_for(c.range(), boost::bind(&for_each_range_<typename Container::range_type, F>, _1, f)); + } + + template<class ID, class NodePointer, class IDTraits, class Allocator> + struct map_traits + { + typedef tbb::concurrent_hash_map<ID, NodePointer, IDTraits, Allocator> type; + typedef typename type::range_type range; + }; + + struct progress_timer + { + progress_timer(): start(tbb::tick_count::now()) {} + ~progress_timer() + { +#ifndef FOR_R_TDA + std::cout << (tbb::tick_count::now() - start).seconds() << " s" << std::endl; +#endif + } + + tbb::tick_count start; + }; +} +} +} + +// Serialization for tbb::concurrent_vector<...> +namespace boost +{ + namespace serialization + { + template<class Archive, class T, class A> + void save(Archive& ar, const tbb::concurrent_vector<T,A>& v, const unsigned int file_version) + { stl::save_collection(ar, v); } + + template<class Archive, class T, class A> + void load(Archive& ar, tbb::concurrent_vector<T,A>& v, const unsigned int file_version) + { + stl::load_collection<Archive, + tbb::concurrent_vector<T,A>, + stl::archive_input_seq< Archive, tbb::concurrent_vector<T,A> >, + stl::reserve_imp< tbb::concurrent_vector<T,A> > + >(ar, v); + } + + template<class Archive, class T, class A> + void serialize(Archive& ar, tbb::concurrent_vector<T,A>& v, const unsigned int file_version) + { split_free(ar, v, file_version); } + + template<class Archive, class T> + void save(Archive& ar, const tbb::atomic<T>& v, const unsigned int file_version) + { T v_ = v; ar << v_; } + + template<class Archive, class T> + void load(Archive& ar, tbb::atomic<T>& v, const unsigned int file_version) + { T v_; ar >> v_; v = v_; } + + template<class Archive, class T> + void serialize(Archive& ar, tbb::atomic<T>& v, const unsigned int file_version) + { split_free(ar, v, file_version); } + } +} + +#else + +#include <algorithm> +#include <map> +#include <boost/progress.hpp> + +namespace hera { +namespace bt { +namespace dnn +{ + template<class T> + struct vector + { + typedef ::std::vector<T> type; + }; + + template<class T> + struct atomic + { + typedef T type; + static T compare_and_swap(type& v, T n, T o) { if (v != o) return v; v = n; return o; } + }; + + template<class Iterator, class F> + void do_foreach(Iterator begin, Iterator end, const F& f) { std::for_each(begin, end, f); } + + template<class F> + void for_each_range(size_t from, size_t to, const F& f) + { + for (size_t i = from; i < to; ++i) + f(i); + } + + template<class Container, class F> + void for_each_range(Container& c, const F& f) + { + BOOST_FOREACH(const typename Container::value_type& i, c) + f(i); + } + + template<class Container, class F> + void for_each_range(const Container& c, const F& f) + { + BOOST_FOREACH(const typename Container::value_type& i, c) + f(i); + } + + struct mutex + { + struct scoped_lock + { + scoped_lock() {} + scoped_lock(mutex& ) {} + void acquire(mutex& ) const {} + void release() const {} + }; + }; + + struct task_scheduler_init + { + task_scheduler_init(unsigned) {} + void initialize(unsigned) {} + static const unsigned automatic = 0; + static const unsigned deferred = 0; + }; + + struct task_group + { + template<class Functor> + void run(const Functor& f) const { f(); } + void wait() const {} + }; + + template<class ID, class NodePointer, class IDTraits, class Allocator> + struct map_traits + { + typedef std::map<ID, NodePointer, + typename IDTraits::Comparison, + Allocator> type; + typedef type range; + }; + + using boost::progress_timer; +} +} +} + +#endif // TBB + +namespace dnn +{ + template<class Range, class F> + void do_foreach(const Range& range, const F& f) { do_foreach(boost::begin(range), boost::end(range), f); } +} + +#endif diff --git a/bottleneck/include/dnn/parallel/utils.h b/bottleneck/include/dnn/parallel/utils.h new file mode 100644 index 0000000..9809e77 --- /dev/null +++ b/bottleneck/include/dnn/parallel/utils.h @@ -0,0 +1,100 @@ +#ifndef HERA_BT_PARALLEL_UTILS_H +#define HERA_BT_PARALLEL_UTILS_H + +#include "../utils.h" + +namespace hera +{ +namespace bt +{ +namespace dnn +{ + // Assumes rng is synchronized across ranks + template<class DataVector, class RNGType, class SwapFunctor> + void shuffle(mpi::communicator& world, DataVector& data, RNGType& rng, const SwapFunctor& swap, DataVector empty = DataVector()); + + template<class DataVector, class RNGType> + void shuffle(mpi::communicator& world, DataVector& data, RNGType& rng) + { + typedef decltype(data[0]) T; + shuffle(world, data, rng, [](T& x, T& y) { std::swap(x,y); }); + } +} +} +} + +template<class DataVector, class RNGType, class SwapFunctor> +void +hera::bt::dnn::shuffle(mpi::communicator& world, DataVector& data, RNGType& rng, const SwapFunctor& swap, DataVector empty) +{ + // This is not a perfect shuffle: it dishes out data in chunks of 1/size. + // (It can be interpreted as generating a bistochastic matrix by taking the + // sum of size random permutation matrices.) Hopefully, it works for our purposes. + + typedef typename RNGType::result_type RNGResult; + + int size = world.size(); + int rank = world.rank(); + + // Generate local seeds + boost::uniform_int<RNGResult> uniform; + RNGResult seed; + for (size_t i = 0; i < size; ++i) + { + RNGResult v = uniform(rng); + if (i == rank) + seed = v; + } + RNGType local_rng(seed); + + // Shuffle local data + hera::bt::dnn::random_shuffle(data.begin(), data.end(), local_rng, swap); + + // Decide how much of our data goes to i-th processor + std::vector<size_t> out_counts(size); + std::vector<int> ranks(boost::counting_iterator<int>(0), + boost::counting_iterator<int>(size)); + for (size_t i = 0; i < size; ++i) + { + hera::bt::dnn::random_shuffle(ranks.begin(), ranks.end(), rng); + ++out_counts[ranks[rank]]; + } + + // Fill the outgoing array + size_t total = 0; + std::vector< DataVector > outgoing(size, empty); + for (size_t i = 0; i < size; ++i) + { + size_t count = data.size()*out_counts[i]/size; + if (total + count > data.size()) + count = data.size() - total; + + outgoing[i].reserve(count); + for (size_t j = total; j < total + count; ++j) + outgoing[i].push_back(data[j]); + + total += count; + } + + boost::uniform_int<size_t> uniform_outgoing(0,size-1); // in range [0,size-1] + while(total < data.size()) // send leftover to random processes + { + outgoing[uniform_outgoing(local_rng)].push_back(data[total]); + ++total; + } + data.clear(); + + // Exchange the data + std::vector< DataVector > incoming(size, empty); + mpi::all_to_all(world, outgoing, incoming); + outgoing.clear(); + + // Assemble our data + for(const DataVector& vec : incoming) + for (size_t i = 0; i < vec.size(); ++i) + data.push_back(vec[i]); + hera::bt::dnn::random_shuffle(data.begin(), data.end(), local_rng, swap); + // XXX: the final shuffle is irrelevant for our purposes. But it's also cheap. +} + +#endif diff --git a/bottleneck/include/dnn/utils.h b/bottleneck/include/dnn/utils.h new file mode 100644 index 0000000..f4ce632 --- /dev/null +++ b/bottleneck/include/dnn/utils.h @@ -0,0 +1,47 @@ +#ifndef HERA_BT_DNN_UTILS_H +#define HERA_BT_DNN_UTILS_H + +#include <boost/random/uniform_int.hpp> +#include <boost/foreach.hpp> +#include <boost/typeof/typeof.hpp> + +namespace hera +{ +namespace bt +{ +namespace dnn +{ + +template <typename T, typename... Args> +struct has_coordinates +{ + template <typename C, typename = decltype( std::declval<C>().coordinate(std::declval<Args>()...) )> + static std::true_type test(int); + + template <typename C> + static std::false_type test(...); + + static constexpr bool value = decltype(test<T>(0))::value; +}; + +template<class RandomIt, class UniformRandomNumberGenerator, class SwapFunctor> +void random_shuffle(RandomIt first, RandomIt last, UniformRandomNumberGenerator& g, const SwapFunctor& swap) +{ + size_t n = last - first; + boost::uniform_int<size_t> uniform(0,n); + for (size_t i = n-1; i > 0; --i) + swap(first[i], first[uniform(g,i+1)]); // picks a random number in [0,i] range +} + +template<class RandomIt, class UniformRandomNumberGenerator> +void random_shuffle(RandomIt first, RandomIt last, UniformRandomNumberGenerator& g) +{ + typedef decltype(*first) T; + random_shuffle(first, last, g, [](T& x, T& y) { std::swap(x,y); }); +} + +} // dnn +} // bt +} // hera + +#endif |