models/cpm_brsg_tree_builders.hpp

#ifndef CPM_BRSG_TREE_BUILDERS_HPP_
#define CPM_BRSG_TREE_BUILDERS_HPP_

#include "MPIBlib/collectives/comm_tree.hpp"
#include "cpm_model.h"
#include "collectives/cpm_coll_ops_list.h"
#include "cpm_functional.hpp"

namespace CPM {
namespace BRSG {
using namespace MPIB::comm_tree;

class UCS_binomial_builder {
protected:
    CPM_predictor* predictor;
    CPM_next_node_strategy next_node;
    CPM_coll_op_types coll_op; 

public:
    UCS_binomial_builder(CPM_predictor* _predictor, CPM_next_node_strategy _next_node, CPM_coll_op_types _coll_op): predictor(_predictor), next_node(_next_node), coll_op(_coll_op) {}

    void build(int size, int root, int rank, int count,
            Graph& g, Vertex& r, Vertex& u, Vertex& v)
    {
        // root
        r = add_vertex(g);
        put(vertex_index, g, r, root);
        if (rank == root)
            v = r;
        // ranks(free rank, source->rank prediction) for searching min/max prediction
        deque<pair<int, double> > ranks;
        for (int i = 0; i < size; i++)
            if (i != root)
                ranks.push_back(make_pair(i, 0));
        // blocks(binomial size, parent vertices)
        multimap<int, Vertex> blocks;
        // size - 1 = sum of powers of 2
        int tmp, bin;
        for (tmp = size - 1, bin = 1; tmp > 0; tmp /= 2, bin *= 2)
            if (tmp % 2)
                blocks.insert(map<int, Vertex>::value_type(bin, r));
        bin /= 2;
        // construction, starting with the highest order
        while (!blocks.empty()) {
            //  subtrees of the same order
            pair<map<int, Vertex>::iterator, map<int, Vertex>::iterator> range =
                blocks.equal_range(bin);
            for (map<int, Vertex>::iterator b = range.first; b != range.second; b++) {
                // add source->target
                Vertex s = b->second;
                int source = get(vertex_index, g, s);
                for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++)
                    i->second = predictor->predict_p2p(predictor, source, i->first, (coll_op == BR)? count : (count * bin));
                deque<pair<int, double> >::iterator i = (next_node == MAX) ?
                        max_element(ranks.begin(), ranks.end(), second_less()):
                        min_element(ranks.begin(), ranks.end(), second_less());
                int target = i->first;

                if ( (rank == root) && (mpib_coll_verbose ==1) ){
                    printf("DEBUG: source(fixed)= %d, target(selected)=%d, prediction=%lf, message_size=%d\n", source, target, i->second, (coll_op == BR)? count : (bin * count));
                    for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                        printf("DEBUG: alternative link prediction: (%d-%d) = %lf\n", source, i->first, i->second);
                    }
                    printf("DEBUG: ===\n");
                }

                ranks.erase(i);
                Vertex t = add_vertex(g);
                put(vertex_index, g, t, target);
                add_edge(s, t, g);


                if (rank == target) {
                    u = s;
                    v = t;
                }
                // add lesser blocks
                for (int bin = b->first / 2; bin > 0; bin /= 2)
                    blocks.insert(map<int, Vertex>::value_type(bin, t));
            }
            blocks.erase(range.first, range.second);
            bin /= 2;
        }
    }
};

class BFS_binomial_builder {
private:
    CPM_predictor* predictor;
    CPM_next_node_strategy next_node;
    CPM_coll_op_types coll_op; 

public:
    BFS_binomial_builder(CPM_predictor* _predictor, CPM_next_node_strategy _next_node, CPM_coll_op_types _coll_op): predictor(_predictor), next_node(_next_node), coll_op(_coll_op) {}

    void build(int size, int root, int rank, int count,
            Graph& g, Vertex& r, Vertex& u, Vertex& v)
    {
        // root
        r = add_vertex(g);
        put(vertex_index, g, r, root);
        if (rank == root)
            v = r;
        // ranks(free rank, source->rank prediction) for searching min/max prediction
        deque<pair<int, double> > ranks;
        for (int i = 0; i < size; i++)
            if (i != root)
                ranks.push_back(make_pair(i, 0));
        // blocks(parent vertex, binomial size) in ascending order
        deque<pair<Vertex, int> > blocks;
        // size - 1 = sum of powers of 2
        for (int tmp = size - 1, bin = 1; tmp > 0; tmp /= 2, bin *= 2)
            if (tmp % 2)
                blocks.push_back(make_pair(r, bin));
        // powers of 2
        while (!blocks.empty()) {
            Vertex s = blocks.back().first;
            int source = get(vertex_index, g, s);
            int bin = blocks.back().second;
            for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                int target = i->first;
                i->second = predictor->predict_p2p(predictor, source, target, (coll_op == BR ) ?  count : (count * bin));
            }
            deque<pair<int, double> >::iterator i = (next_node == MAX) ?
                    max_element(ranks.begin(), ranks.end(), second_less()):
                    min_element(ranks.begin(), ranks.end(), second_less());
            int target = i->first;

                if ( (rank == root) && (mpib_coll_verbose ==1) ){
                    printf("DEBUG: source(fixed)= %d, target(selected)=%d, prediction=%lf, message_size=%d\n", source, target, i->second, (coll_op == BR)? count : (bin * count));
                    for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                        printf("DEBUG: alternative link prediction: (%d-%d) = %lf\n", source, i->first, i->second);
                    }
                    printf("DEBUG: ===\n");
                }

            ranks.erase(i);
            Vertex t = add_vertex(g);
            put(vertex_index, g, t, target);
            if (rank == target) {
                u = s;
                v = t;
            }
            add_edge(s, t, g);
            blocks.pop_back();
            for (bin /= 2; bin > 0; bin /= 2)
                blocks.push_front(make_pair(t, bin));
        }
    }
};

class DFS_binomial_builder {

private:
    CPM_predictor* predictor;
    CPM_next_node_strategy next_node;
    CPM_coll_op_types coll_op; 

public:
    DFS_binomial_builder(CPM_predictor* _predictor, CPM_next_node_strategy _next_node, CPM_coll_op_types  _coll_op): predictor(_predictor), next_node(_next_node), coll_op(_coll_op) {}

    void build(int size, int root, int rank, int count,
            Graph& g, Vertex& r, Vertex& u, Vertex& v)
    {
        // root
        r = add_vertex(g);
        put(vertex_index, g, r, root);
        if (rank == root)
            v = r;
        // ranks(free rank, source->rank prediction) for searching min/max prediction
        deque<pair<int, double> > ranks;
        for (int i = 0; i < size; i++)
            if (i != root)
                ranks.push_back(make_pair(i, 0));
        // blocks(parent vertex, binomial size) in ascending order
        deque<pair<Vertex, int> > blocks;
        int bin;
        // size - 1 = sum of powers of 2
        for (int tmp = size - 1, bin = 1; tmp > 0; tmp /= 2, bin *= 2)
            if (tmp % 2)
                blocks.push_back(make_pair(r, bin));
        // powers of 2
        while (!blocks.empty()) {
            Vertex s = blocks.front().first;
            bin = blocks.front().second;    
            int source = get(vertex_index, g, s);
            for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                int target = i->first;
                i->second = predictor->predict_p2p(predictor, source, target, (coll_op == BR ) ?  count : (count * bin));
            }
            deque<pair<int, double> >::iterator i = (next_node == MAX) ?
                    max_element(ranks.begin(), ranks.end(), second_less()):
                    min_element(ranks.begin(), ranks.end(), second_less());
            int target = i->first;
            if ( (rank == root) && (mpib_coll_verbose ==1) ){
                printf("DEBUG: source(fixed)= %d, target(selected)=%d, prediction=%lf, message_size=%d\n", source, target, i->second, (coll_op == BR)? count : (bin * count));
                for (deque<pair<int, double> >::iterator i = ranks.begin(); i != ranks.end(); i++) {
                    printf("DEBUG: alternative link prediction: (%d-%d) = %lf\n", source, i->first, i->second);
                }
                printf("DEBUG: ===\n");
            }

            ranks.erase(i);
            Vertex t = add_vertex(g);
            put(vertex_index, g, t, target);
            if (rank == target) {
                u = s;
                v = t;
            }
            add_edge(s, t, g);
            blocks.pop_front();
            for (bin /= 2; bin > 0; bin /= 2)
                blocks.push_front(make_pair(t, bin));
        }
    }
};
}
}

#endif //CPM_BRSG_TREE_BUILDERS_HPP_