benes_routing_algorithm.cpp

Go to the documentation of this file.

 
#include <cassert>
#include <libsnark/common/routing_algorithms/benes_routing_algorithm.hpp>
 
namespace libsnark
{
 
size_t benes_cross_edge_mask(const size_t dimension, const size_t column_idx)
{
    return (
        column_idx < dimension ? 1ul << (dimension - 1 - column_idx)
                               : 1ul << (column_idx - dimension));
}
 
size_t benes_lhs_packet_destination(
    const size_t dimension,
    const size_t column_idx,
    const size_t row_idx,
    const bool use_top)
{
    const size_t mask = benes_cross_edge_mask(dimension, column_idx);
    return (use_top ? row_idx & ~mask : row_idx | mask);
}
 
size_t benes_rhs_packet_source(
    const size_t dimension,
    const size_t column_idx,
    const size_t row_idx,
    const bool use_top)
{
    return benes_lhs_packet_destination(
        dimension, column_idx - 1, row_idx, use_top); /* by symmetry */
}
 
bool benes_get_switch_setting_from_subnetwork(
    const size_t dimension,
    const size_t column_idx,
    const size_t row_idx,
    const bool use_top)
{
    return (
        row_idx !=
        benes_lhs_packet_destination(dimension, column_idx, row_idx, use_top));
}
 
size_t benes_packet_cross_destination(
    const size_t dimension, const size_t column_idx, const size_t row_idx)
{
    const size_t mask = benes_cross_edge_mask(dimension, column_idx);
    return row_idx ^ mask;
}
 
size_t benes_packet_cross_source(
    const size_t dimension, const size_t column_idx, const size_t packet_idx)
{
    return benes_packet_cross_destination(
        dimension, column_idx - 1, packet_idx); /* by symmetry */
}
 
size_t benes_num_columns(const size_t num_packets)
{
    const size_t dimension = libff::log2(num_packets);
    assert(num_packets == 1ul << dimension);
 
    return 2 * dimension;
}
 
benes_topology generate_benes_topology(const size_t num_packets)
{
    const size_t num_columns = benes_num_columns(num_packets);
    const size_t dimension = libff::log2(num_packets);
    assert(num_packets == 1ul << dimension);
 
    benes_topology result(num_columns);
 
    for (size_t column_idx = 0; column_idx < num_columns; ++column_idx) {
        result[column_idx].resize(num_packets);
        for (size_t packet_idx = 0; packet_idx < num_packets; ++packet_idx) {
            result[column_idx][packet_idx].first = packet_idx;
            result[column_idx][packet_idx].second =
                benes_packet_cross_destination(
                    dimension, column_idx, packet_idx);
        }
    }
 
    return result;
}
 
void route_benes_inner(
    const size_t dimension,
    const integer_permutation &permutation,
    const integer_permutation &permutation_inv,
    const size_t column_idx_start,
    const size_t column_idx_end,
    const size_t subnetwork_offset,
    const size_t subnetwork_size,
    benes_routing &routing)
{
#ifdef DEBUG
    assert(permutation.size() == subnetwork_size);
    assert(permutation.is_valid());
    assert(permutation.inverse() == permutation_inv);
#endif
 
    if (column_idx_start == column_idx_end) {
        /* nothing to route */
        return;
    }
    // adjusted by subnetwork_offset
    libff::bit_vector lhs_routed(subnetwork_size, false);
 
    // left-hand-side vertex to be routed.
    size_t w = subnetwork_offset;
    size_t last_unrouted = subnetwork_offset;
 
    integer_permutation new_permutation(
        subnetwork_offset, subnetwork_offset + subnetwork_size - 1);
    integer_permutation new_permutation_inv(
        subnetwork_offset, subnetwork_offset + subnetwork_size - 1);
 
    while (true) {
        /* route w to its target on RHS, wprime = pi[w], using upper network */
        size_t wprime = permutation.get(w);
 
        /* route (column_idx_start, w) forward via top subnetwork */
        routing[column_idx_start][w] = benes_get_switch_setting_from_subnetwork(
            dimension, column_idx_start, w, true);
        new_permutation.set(
            benes_lhs_packet_destination(dimension, column_idx_start, w, true),
            benes_rhs_packet_source(dimension, column_idx_end, wprime, true));
        lhs_routed[w - subnetwork_offset] = true;
 
        /* route (column_idx_end, wprime) backward via top subnetwork */
        routing[column_idx_end - 1][benes_rhs_packet_source(
            dimension, column_idx_end, wprime, true)] =
            benes_get_switch_setting_from_subnetwork(
                dimension, column_idx_end - 1, wprime, true);
        new_permutation_inv.set(
            benes_rhs_packet_source(dimension, column_idx_end, wprime, true),
            benes_lhs_packet_destination(dimension, column_idx_start, w, true));
 
        /* now the other neighbor of wprime must be back-routed via the lower
         * network, so get vprime, the neighbor on RHS and v, its target on LHS
         */
        const size_t vprime =
            benes_packet_cross_source(dimension, column_idx_end, wprime);
        const size_t v = permutation_inv.get(vprime);
        assert(!lhs_routed[v - subnetwork_offset]);
 
        /* back-route (column_idx_end, vprime) using the lower subnetwork */
        routing[column_idx_end - 1][benes_rhs_packet_source(
            dimension, column_idx_end, vprime, false)] =
            benes_get_switch_setting_from_subnetwork(
                dimension, column_idx_end - 1, vprime, false);
        new_permutation_inv.set(
            benes_rhs_packet_source(dimension, column_idx_end, vprime, false),
            benes_lhs_packet_destination(
                dimension, column_idx_start, v, false));
 
        /* forward-route (column_idx_start, v) using the lower subnetwork */
        routing[column_idx_start][v] = benes_get_switch_setting_from_subnetwork(
            dimension, column_idx_start, v, false);
        new_permutation.set(
            benes_lhs_packet_destination(dimension, column_idx_start, v, false),
            benes_rhs_packet_source(dimension, column_idx_end, vprime, false));
        lhs_routed[v - subnetwork_offset] = true;
 
        /* if the other neighbor of v is not routed, route it; otherwise, find
         * the next unrouted node  */
        if (!lhs_routed
                [benes_packet_cross_destination(
                     dimension, column_idx_start, v) -
                 subnetwork_offset]) {
            w = benes_packet_cross_destination(dimension, column_idx_start, v);
        } else {
            while ((last_unrouted < subnetwork_offset + subnetwork_size) &&
                   lhs_routed[last_unrouted - subnetwork_offset]) {
                ++last_unrouted;
            }
 
            if (last_unrouted == subnetwork_offset + subnetwork_size) {
                // all routed!
                break;
            } else {
                w = last_unrouted;
            }
        }
    }
 
    const integer_permutation new_permutation_upper = new_permutation.slice(
        subnetwork_offset, subnetwork_offset + subnetwork_size / 2 - 1);
    const integer_permutation new_permutation_lower = new_permutation.slice(
        subnetwork_offset + subnetwork_size / 2,
        subnetwork_offset + subnetwork_size - 1);
 
    const integer_permutation new_permutation_inv_upper =
        new_permutation_inv.slice(
            subnetwork_offset, subnetwork_offset + subnetwork_size / 2 - 1);
    const integer_permutation new_permutation_inv_lower =
        new_permutation_inv.slice(
            subnetwork_offset + subnetwork_size / 2,
            subnetwork_offset + subnetwork_size - 1);
 
    /* route upper part */
    route_benes_inner(
        dimension,
        new_permutation_upper,
        new_permutation_inv_upper,
        column_idx_start + 1,
        column_idx_end - 1,
        subnetwork_offset,
        subnetwork_size / 2,
        routing);
 
    /* route lower part */
    route_benes_inner(
        dimension,
        new_permutation_lower,
        new_permutation_inv_lower,
        column_idx_start + 1,
        column_idx_end - 1,
        subnetwork_offset + subnetwork_size / 2,
        subnetwork_size / 2,
        routing);
}
 
benes_routing get_benes_routing(const integer_permutation &permutation)
{
    const size_t num_packets = permutation.size();
    const size_t num_columns = benes_num_columns(num_packets);
    const size_t dimension = libff::log2(num_packets);
 
    benes_routing routing(num_columns, libff::bit_vector(num_packets));
 
    route_benes_inner(
        dimension,
        permutation,
        permutation.inverse(),
        0,
        num_columns,
        0,
        num_packets,
        routing);
 
    return routing;
}
 
/* auxiliary function that is used in valid_benes_routing below */
template<typename T>
std::vector<std::vector<T>> route_by_benes(
    const benes_routing &routing, const std::vector<T> &start)
{
    const size_t num_packets = start.size();
    const size_t num_columns = benes_num_columns(num_packets);
    const size_t dimension = libff::log2(num_packets);
 
    std::vector<std::vector<T>> res(
        num_columns + 1, std::vector<T>(num_packets));
    res[0] = start;
 
    for (size_t column_idx = 0; column_idx < num_columns; ++column_idx) {
        const size_t mask = benes_cross_edge_mask(dimension, column_idx);
 
        for (size_t packet_idx = 0; packet_idx < num_packets; ++packet_idx) {
            size_t next_packet_idx = (routing[column_idx][packet_idx] == false)
                                         ? packet_idx
                                         : packet_idx ^ mask;
            res[column_idx + 1][next_packet_idx] = res[column_idx][packet_idx];
        }
    }
 
    return res;
}
 
bool valid_benes_routing(
    const integer_permutation &permutation, const benes_routing &routing)
{
    const size_t num_packets = permutation.size();
    const size_t num_columns = benes_num_columns(num_packets);
 
    std::vector<size_t> input_packets(num_packets);
    for (size_t packet_idx = 0; packet_idx < num_packets; ++packet_idx) {
        input_packets[packet_idx] = packet_idx;
    }
 
    const std::vector<std::vector<size_t>> routed_packets =
        route_by_benes(routing, input_packets);
 
    for (size_t packet_idx = 0; packet_idx < num_packets; ++packet_idx) {
        if (routed_packets[num_columns][permutation.get(packet_idx)] !=
            input_packets[packet_idx]) {
            return false;
        }
    }
 
    return true;
}
 
} // namespace libsnark