From e26434979adc33bd949566ba7bf02dff64e80a3e Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Tue, 2 Oct 2012 00:19:43 -0400 Subject: cdec cleanup, remove bayesian stuff, parsing stuff --- gi/pyp-topics/src/mpi-pyp.hh | 447 ------------------------------------------- 1 file changed, 447 deletions(-) delete mode 100644 gi/pyp-topics/src/mpi-pyp.hh (limited to 'gi/pyp-topics/src/mpi-pyp.hh') diff --git a/gi/pyp-topics/src/mpi-pyp.hh b/gi/pyp-topics/src/mpi-pyp.hh deleted file mode 100644 index c2341b9e..00000000 --- a/gi/pyp-topics/src/mpi-pyp.hh +++ /dev/null @@ -1,447 +0,0 @@ -#ifndef _mpipyp_hh -#define _mpipyp_hh - -#include -#include -#include -//#include - -#include -#include -#include -#include -#include -#include -#include -#include -#include - - -#include "pyp.hh" - -// -// Pitman-Yor process with customer and table tracking -// - -template > -class MPIPYP : public PYP { -public: - typedef std::map dish_delta_type; - - MPIPYP(double a, double b, Hash hash=Hash()); - - template < typename Uniform01 > - int increment(Dish d, double p0, Uniform01& rnd); - template < typename Uniform01 > - int decrement(Dish d, Uniform01& rnd); - - void clear(); - void reset_deltas(); - - void synchronise(dish_delta_type* result); - -private: - typedef std::map::TableCounter> table_delta_type; - - dish_delta_type m_count_delta; - table_delta_type m_table_delta; -}; - -template -MPIPYP::MPIPYP(double a, double b, Hash h) -: PYP(a, b, 0, h) {} - -template - template -int -MPIPYP::increment(Dish dish, double p0, Uniform01& rnd) { - //std::cerr << "-----INCREMENT DISH " << dish << std::endl; - int delta = 0; - int table_joined=-1; - typename PYP::TableCounter &tc = PYP::_dish_tables[dish]; - - // seated on a new or existing table? - int c = PYP::count(dish); - int t = PYP::num_tables(dish); - int T = PYP::num_tables(); - double& a = PYP::_a; - double& b = PYP::_b; - double pshare = (c > 0) ? (c - a*t) : 0.0; - double pnew = (b + a*T) * p0; - if (pshare < 0.0) { - std::cerr << pshare << " " << c << " " << a << " " << t << std::endl; - assert(false); - } - - if (rnd() < pnew / (pshare + pnew)) { - // assign to a new table - tc.tables += 1; - tc.table_histogram[1] += 1; - PYP::_total_tables += 1; - delta = 1; - table_joined = 1; - } - else { - // randomly assign to an existing table - // remove constant denominator from inner loop - double r = rnd() * (c - a*t); - for (std::map::iterator - hit = tc.table_histogram.begin(); - hit != tc.table_histogram.end(); ++hit) { - r -= ((hit->first - a) * hit->second); - if (r <= 0) { - tc.table_histogram[hit->first+1] += 1; - hit->second -= 1; - table_joined = hit->first+1; - if (hit->second == 0) - tc.table_histogram.erase(hit); - break; - } - } - if (r > 0) { - std::cerr << r << " " << c << " " << a << " " << t << std::endl; - assert(false); - } - delta = 0; - } - - std::tr1::unordered_map::operator[](dish) += 1; - //google::sparse_hash_map::operator[](dish) += 1; - PYP::_total_customers += 1; - - // MPI Delta handling - // track the customer entering - typename dish_delta_type::iterator customer_it; - bool customer_insert_result; - boost::tie(customer_it, customer_insert_result) - = m_count_delta.insert(std::make_pair(dish,0)); - - customer_it->second += 1; - if (customer_it->second == 0) - m_count_delta.erase(customer_it); - - // increment the histogram bar for the table joined - /* - typename PYP::TableCounter &delta_tc = m_table_delta[dish]; - - std::map &histogram = delta_tc.table_histogram; - assert (table_joined > 0); - - typename std::map::iterator table_it; bool table_insert_result; - boost::tie(table_it, table_insert_result) = histogram.insert(std::make_pair(table_joined,0)); - table_it->second += 1; - if (delta == 0) { - // decrement the histogram bar for the table left - typename std::map::iterator left_table_it; - boost::tie(left_table_it, table_insert_result) - = histogram.insert(std::make_pair(table_joined-1,0)); - left_table_it->second -= 1; - if (left_table_it->second == 0) histogram.erase(left_table_it); - } - else delta_tc.tables += 1; - - if (table_it->second == 0) histogram.erase(table_it); - - //std::cerr << "Added (" << delta << ") " << dish << " to table " << table_joined << "\n"; - //std::cerr << "Dish " << dish << " has " << count(dish) << " customers, and is sitting at " << PYP::num_tables(dish) << " tables.\n"; - //for (std::map::const_iterator - // hit = delta_tc.table_histogram.begin(); - // hit != delta_tc.table_histogram.end(); ++hit) { - // std::cerr << " " << hit->second << " tables with " << hit->first << " customers." << std::endl; - //} - //std::cerr << "Added (" << delta << ") " << dish << " to table " << table_joined << "\n"; - //std::cerr << "Dish " << dish << " has " << count(dish) << " customers, and is sitting at " << PYP::num_tables(dish) << " tables.\n"; - int x_num_customers=0, x_num_table=0; - for (std::map::const_iterator - hit = delta_tc.table_histogram.begin(); - hit != delta_tc.table_histogram.end(); ++hit) { - x_num_table += hit->second; - x_num_customers += (hit->second*hit->first); - } - int tmp_c = PYP::count(dish); - int tmp_t = PYP::num_tables(dish); - assert (x_num_customers <= tmp_c); - assert (x_num_table <= tmp_t); - - if (delta_tc.table_histogram.empty()) { - assert (delta_tc.tables == 0); - m_table_delta.erase(dish); - } - */ - - //PYP::debug_info(std::cerr); - //std::cerr << " Dish " << dish << " has count " << PYP::count(dish) << " tables " << PYP::num_tables(dish) << std::endl; - - return delta; -} - -template - template -int -MPIPYP::decrement(Dish dish, Uniform01& rnd) -{ - //std::cerr << "-----DECREMENT DISH " << dish << std::endl; - typename std::tr1::unordered_map::iterator dcit = find(dish); - //typename google::sparse_hash_map::iterator dcit = find(dish); - if (dcit == PYP::end()) { - std::cerr << dish << std::endl; - assert(false); - } - - int delta = 0, table_left=-1; - - typename std::tr1::unordered_map::TableCounter>::iterator dtit - = PYP::_dish_tables.find(dish); - //typename google::sparse_hash_map::iterator dtit = _dish_tables.find(dish); - if (dtit == PYP::_dish_tables.end()) { - std::cerr << dish << std::endl; - assert(false); - } - typename PYP::TableCounter &tc = dtit->second; - - double r = rnd() * PYP::count(dish); - for (std::map::iterator hit = tc.table_histogram.begin(); - hit != tc.table_histogram.end(); ++hit) { - r -= (hit->first * hit->second); - if (r <= 0) { - table_left = hit->first; - if (hit->first > 1) { - tc.table_histogram[hit->first-1] += 1; - } - else { - delta = -1; - tc.tables -= 1; - PYP::_total_tables -= 1; - } - - hit->second -= 1; - if (hit->second == 0) tc.table_histogram.erase(hit); - break; - } - } - if (r > 0) { - std::cerr << r << " " << PYP::count(dish) << " " << PYP::_a << " " - << PYP::num_tables(dish) << std::endl; - assert(false); - } - - // remove the customer - dcit->second -= 1; - PYP::_total_customers -= 1; - assert(dcit->second >= 0); - if (dcit->second == 0) { - PYP::erase(dcit); - PYP::_dish_tables.erase(dtit); - } - - // MPI Delta processing - typename dish_delta_type::iterator it; - bool insert_result; - boost::tie(it, insert_result) = m_count_delta.insert(std::make_pair(dish,0)); - it->second -= 1; - if (it->second == 0) m_count_delta.erase(it); - - assert (table_left > 0); - typename PYP::TableCounter& delta_tc = m_table_delta[dish]; - if (table_left > 1) { - std::map::iterator tit; - boost::tie(tit, insert_result) = delta_tc.table_histogram.insert(std::make_pair(table_left-1,0)); - tit->second += 1; - if (tit->second == 0) delta_tc.table_histogram.erase(tit); - } - else delta_tc.tables -= 1; - - std::map::iterator tit; - boost::tie(tit, insert_result) = delta_tc.table_histogram.insert(std::make_pair(table_left,0)); - tit->second -= 1; - if (tit->second == 0) delta_tc.table_histogram.erase(tit); - - // std::cerr << "Dish " << dish << " has " << count(dish) << " customers, and is sitting at " << PYP::num_tables(dish) << " tables.\n"; - // for (std::map::const_iterator - // hit = delta_tc.table_histogram.begin(); - // hit != delta_tc.table_histogram.end(); ++hit) { - // std::cerr << " " << hit->second << " tables with " << hit->first << " customers." << std::endl; - // } - int x_num_customers=0, x_num_table=0; - for (std::map::const_iterator - hit = delta_tc.table_histogram.begin(); - hit != delta_tc.table_histogram.end(); ++hit) { - x_num_table += hit->second; - x_num_customers += (hit->second*hit->first); - } - int tmp_c = PYP::count(dish); - int tmp_t = PYP::num_tables(dish); - assert (x_num_customers <= tmp_c); - assert (x_num_table <= tmp_t); - - if (delta_tc.table_histogram.empty()) { - // std::cerr << " DELETING " << dish << std::endl; - assert (delta_tc.tables == 0); - m_table_delta.erase(dish); - } - - //PYP::debug_info(std::cerr); - //std::cerr << " Dish " << dish << " has count " << PYP::count(dish) << " tables " << PYP::num_tables(dish) << std::endl; - return delta; -} - -template -void -MPIPYP::clear() { - PYP::clear(); - reset_deltas(); -} - -template -void -MPIPYP::reset_deltas() { - m_count_delta.clear(); - m_table_delta.clear(); -} - -template -struct sum_maps { - typedef std::map map_type; - map_type& operator() (map_type& l, map_type const & r) const { - for (typename map_type::const_iterator it=r.begin(); it != r.end(); it++) - l[it->first] += it->second; - return l; - } -}; - -template -struct subtract_maps { - typedef std::map map_type; - map_type& operator() (map_type& l, map_type const & r) const { - for (typename map_type::const_iterator it=r.begin(); it != r.end(); it++) - l[it->first] -= it->second; - return l; - } -}; - -// Needed Boost definitions -namespace boost { - namespace mpi { - template <> - struct is_commutative< sum_maps, std::map > : mpl::true_ {}; - } - - namespace serialization { - template - void serialize(Archive & ar, PYP::TableCounter& t, const unsigned int version) { - ar & t.table_histogram; - ar & t.tables; - } - - } // namespace serialization -} // namespace boost - -template -struct triple { - triple() {} - triple(const A& a, const B& b, const C& c) : first(a), second(b), third(c) {} - A first; - B second; - C third; - - template - void serialize(Archive &ar, const unsigned int version){ - ar & first; - ar & second; - ar & third; - } -}; - -BOOST_IS_BITWISE_SERIALIZABLE(MPIPYP::dish_delta_type) -BOOST_CLASS_TRACKING(MPIPYP::dish_delta_type,track_never) - -template -void -MPIPYP::synchronise(dish_delta_type* result) { - boost::mpi::communicator world; - //int rank = world.rank(), size = world.size(); - - boost::mpi::all_reduce(world, m_count_delta, *result, sum_maps()); - subtract_maps()(*result, m_count_delta); - -/* - // communicate the customer count deltas - dish_delta_type global_dish_delta; - boost::mpi::all_reduce(world, m_count_delta, global_dish_delta, sum_maps()); - - // update this restaurant - for (typename dish_delta_type::const_iterator it=global_dish_delta.begin(); - it != global_dish_delta.end(); ++it) { - int global_delta = it->second - m_count_delta[it->first]; - if (global_delta == 0) continue; - typename std::tr1::unordered_map::iterator dit; bool inserted; - boost::tie(dit, inserted) - = std::tr1::unordered_map::insert(std::make_pair(it->first, 0)); - dit->second += global_delta; - assert(dit->second >= 0); - if (dit->second == 0) { - std::tr1::unordered_map::erase(dit); - } - - PYP::_total_customers += (it->second - m_count_delta[it->first]); - int tmp = PYP::_total_customers; - assert(tmp >= 0); - //std::cerr << "Process " << rank << " adding " << (it->second - m_count_delta[it->first]) << " of customer " << it->first << std::endl; - } -*/ -/* - // communicate the table count deltas - for (int process = 0; process < size; ++process) { - typename std::vector< triple > message; - if (rank == process) { - // broadcast deltas - for (typename table_delta_type::const_iterator dish_it=m_table_delta.begin(); - dish_it != m_table_delta.end(); ++dish_it) { - //assert (dish_it->second.tables > 0); - for (std::map::const_iterator it=dish_it->second.table_histogram.begin(); - it != dish_it->second.table_histogram.end(); ++it) { - triple m(dish_it->first, it->first, it->second); - message.push_back(m); - } - // append a special message with the total table delta for this dish - triple m(dish_it->first, -1, dish_it->second.tables); - message.push_back(m); - } - boost::mpi::broadcast(world, message, process); - } - else { - // receive deltas - boost::mpi::broadcast(world, message, process); - for (typename std::vector< triple >::const_iterator it=message.begin(); it != message.end(); ++it) { - typename PYP::TableCounter& tc = PYP::_dish_tables[it->first]; - if (it->second >= 0) { - std::map::iterator tit; bool inserted; - boost::tie(tit, inserted) = tc.table_histogram.insert(std::make_pair(it->second, 0)); - tit->second += it->third; - if (tit->second < 0) { - std::cerr << tit->first << " " << tit->second << " " << it->first << " " << it->second << " " << it->third << std::endl; - assert(tit->second >= 0); - } - if (tit->second == 0) { - tc.table_histogram.erase(tit); - } - } - else { - tc.tables += it->third; - PYP::_total_tables += it->third; - assert(tc.tables >= 0); - if (tc.tables == 0) assert(tc.table_histogram.empty()); - if (tc.table_histogram.empty()) { - assert (tc.tables == 0); - PYP::_dish_tables.erase(it->first); - } - } - } - } - } -*/ - -// reset_deltas(); -} - -#endif -- cgit v1.2.3