MRRGProcedures_tests.cpp

Go to the documentation of this file.

/*******************************************************************************
 * The software programs comprising "CGRA-ME" and the documentation provided
 * with them are copyright by its authors and the University of Toronto. Only
 * non-commercial, not-for-profit use of this software is permitted without ex-
 * plicit permission. This software is provided "as is" with no warranties or
 * guarantees of support. See the LICENCE for more details. You should have re-
 * ceived a copy of the full licence along with this software. If not, see
 * <http://cgra-me.ece.utoronto.ca/license/>.
 ******************************************************************************/
 
#include <CGRA/Module.h>
#include <CGRA/MRRGProcedures.h>
 
#include <catch2/catch.hpp>
 
namespace {
 
Module god_module("m", "", {0,0}, 32); // used for some MRRG nodes created in this file
 
MRRG makeMRRG_4nodeLinear(int II, int latency_of_a, int latency_of_c, ConfigStore options = {}) {
    const int cycle_after_a = (0             + latency_of_a) % II;
    const int cycle_after_c = (cycle_after_a + latency_of_c) % II;
 
    // add operand tags given in the form of "operand-a1" etc.
    std::map<std::string,MRRGNode::SupportedOpTags> operand_tags;
    for (auto& n : {"a", "b", "c", "d"}) {
        auto& tags_for_n = operand_tags[n]; // creates
        for (auto& i : {"1", "2", "3"}) {
            const auto& key = std::string("operand-") + n + i;
            if (options.hasKey(key)) {
                tags_for_n.insert(options.getString(key));
            }
        }
    }
 
    MRRG mrrg(II);
    const auto a  = mrrg.insert(    MRRGNode::make_operand_pin(&god_module, 32, 0,             "a", operand_tags.at("a"), latency_of_a)).first;
    const auto b  = mrrg.insert(a,  MRRGNode::make_operand_pin(&god_module, 32, cycle_after_a, "b", operand_tags.at("b"), 0           )).first;
    const auto c  = mrrg.insert(b,  MRRGNode::make_operand_pin(&god_module, 32, cycle_after_a, "c", operand_tags.at("c"), latency_of_c)).first;
    const auto d  = mrrg.insert(c,  MRRGNode::make_operand_pin(&god_module, 32, cycle_after_c, "d", operand_tags.at("d"), 0           )).first;
    (void)d;
 
    verifyAndPrintReport(mrrg, std::cout, true, true);
    return mrrg;
}
 
MRRG makeMRRG_2nodeFUAndReg(int II, int latency_of_fu, int latency_of_reg) {
    MRRG mrrg(II);
    const int cycle_after_fu = (0             + latency_of_fu) % II;
 
    const auto fu  = mrrg.insert(     MRRGNode::make_function(nullptr, 32, 0,              "fu",  latency_of_fu, {OpCode::ADD})).first;
    const auto reg = mrrg.insert(fu,  MRRGNode::make_routing( nullptr, 32, cycle_after_fu, "reg", latency_of_reg)).first;
 
    mrrg.link(reg, fu);
 
    verifyAndPrintReport(mrrg, std::cout, true, true);
    return mrrg;
}
 
MRRG makeMRRG_2112DAG(int II, int latency_of_a, int latency_of_c) {
    const int cycle_after_a = (0             + latency_of_a) % II;
    const int cycle_after_c = (cycle_after_a + latency_of_c) % II;
    MRRG mrrg(II);
    const auto a1 = mrrg.insert(   MRRGNode::make_routing(nullptr, 32, 0,             "a1", latency_of_a)).first;
    const auto a2 = mrrg.insert(   MRRGNode::make_routing(nullptr, 32, 0,             "a2", latency_of_a)).first;
    const auto b  = mrrg.insertMultiFanin({a1,a2}, MRRGNode::make_routing(nullptr, 32, cycle_after_a, "b", 0)).first;
    const auto c  = mrrg.insert(b, MRRGNode::make_routing(nullptr, 32, cycle_after_a, "c",  latency_of_c)).first;
    const auto d1 = mrrg.insert(c, MRRGNode::make_routing(nullptr, 32, cycle_after_c, "d1", 0           )).first;
    const auto d2 = mrrg.insert(c, MRRGNode::make_routing(nullptr, 32, cycle_after_c, "d2", 0           )).first;
    (void)d1;
    (void)d2;
 
    verifyAndPrintReport(mrrg, std::cout, true, true);
    return mrrg;
}
 
MRRG makeMRRG_112221DAG(int II, int latency_of_a, int latency_of_c) {
    const int cycle_after_a = (0             + latency_of_a) % II;
    const int cycle_after_c = (cycle_after_a + latency_of_c) % II;
    MRRG mrrg(II);
    const auto a  = mrrg.insert(    MRRGNode::make_routing(nullptr, 32, 0,             "a",  latency_of_a)).first;
    const auto b  = mrrg.insert(a,  MRRGNode::make_routing(nullptr, 32, cycle_after_a, "b",  0           )).first;
    const auto c1 = mrrg.insert(b,  MRRGNode::make_routing(nullptr, 32, cycle_after_a, "c1", latency_of_c)).first;
    const auto c2 = mrrg.insert(b,  MRRGNode::make_routing(nullptr, 32, cycle_after_a, "c2", latency_of_c)).first;
    const auto d1 = mrrg.insert(c1, MRRGNode::make_routing(nullptr, 32, cycle_after_c, "d1", 0           )).first;
    const auto d2 = mrrg.insert(c2, MRRGNode::make_routing(nullptr, 32, cycle_after_c, "d2", 0           )).first;
    const auto e1 = mrrg.insert(d1, MRRGNode::make_routing(nullptr, 32, cycle_after_c, "e1", 0           )).first;
    const auto e2 = mrrg.insert(d2, MRRGNode::make_routing(nullptr, 32, cycle_after_c, "e2", 0           )).first;
    const auto f  = mrrg.insertMultiFanin({e1,e2}, MRRGNode::make_routing(nullptr, 32, latency_of_c, "f", 0)).first;
    (void)f;
 
    verifyAndPrintReport(mrrg, std::cout, true, true);
    return mrrg;
}
 
} // end anon namespace
 
TEST_CASE("tripCountOfWalk Tests", "") {
    const auto II = GENERATE(1,2,3);
    const auto latency_of_a = GENERATE(0,1,2,3,5);
    const auto latency_of_c = GENERATE(0,1,2,3,5);
    GIVEN("a 4 node linear II == " << II << " MRRG with latency " << latency_of_a << " on node a and latency of " << latency_of_c << " for node c") {
        const auto& mrrg = makeMRRG_4nodeLinear(II, latency_of_a, latency_of_c);
        const auto node_a = mrrg.getNode(0, "a");
        const auto node_b = *mrrg.fanout(node_a).begin();
        const auto node_c = mrrg.getNode(mrrg.getNodeRef(node_b).getContextNum(), "c");
        const auto walk = std::vector<MRRG::NodeDescriptor>{node_a, node_b, node_c, *mrrg.fanout(node_c).begin()};
        const auto total_trip_count = (latency_of_c + latency_of_a)/II;
        auto walk_len = GENERATE_REF(range(2, (int)walk.size()-1+1)); // can't have segments smaller than 2
        GIVEN("a walk that we will spit after " << walk_len << " nodes") {
            const auto expected_trip_count = (walk_len >= 4 ? total_trip_count : latency_of_a/II);
            THEN("the first " << walk_len << "nodes should have the expected trip count") {
                CHECK(expected_trip_count == tripCountOfWalk(mrrg, decltype(walk){walk.begin(), std::next(walk.begin(), walk_len)}));
            }
            THEN("the last " << walk.size() - walk_len << " nodes should have the expected trip count") {
                CHECK(total_trip_count - expected_trip_count == tripCountOfWalk(mrrg, decltype(walk){std::next(walk.begin(), walk_len-1), walk.end()}));
            }
        }
    }
}
 
namespace {
    struct OperandCompatibilityTest {
 
    };
} // end anon namespace
 
TEST_CASE("Operand Compatibility Tests", "") {
    const auto mrrg = makeMRRG_4nodeLinear(1, 0, 0, {
        {"operand-c1","C1"},
        {"operand-c2","C2"},
    });
 
    // some node tests
 
    const auto& node_a = mrrg.getNode(0,"a");
    const auto& node_b = mrrg.getNode(0,"b");
    const auto& node_c = mrrg.getNode(0,"c");
    const auto& node_d = mrrg.getNode(0,"d");
 
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_a, Operands::UNTAGGED));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_a, "aoeu"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_a, "C1"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_a, "C2"));
 
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_b, Operands::UNTAGGED));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_b, "aoeu"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_b, "C1"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_b, "C2"));
 
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_c, Operands::UNTAGGED));
    CHECK_FALSE(nodeIsCompatibleWithOperand(mrrg, node_c, "aoeu"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_c, "C1"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_c, "C2"));
 
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_d, Operands::UNTAGGED));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_d, "aoeu"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_d, "C1"));
    CHECK      (nodeIsCompatibleWithOperand(mrrg, node_d, "C2"));
 
    // some walk tests
 
    const auto nodes_a_to_a = std::vector<MRRG::NodeDescriptor>{node_a, node_b};
    const auto nodes_a_to_b = std::vector<MRRG::NodeDescriptor>{node_a, node_b, node_c};
    const auto nodes_b_to_c = std::vector<MRRG::NodeDescriptor>{        node_b, node_c, node_d};
    const auto nodes_a_to_c = std::vector<MRRG::NodeDescriptor>{node_a, node_b, node_c, node_d};
 
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, Operands::UNTAGGED));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, "aoeu"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, "C1"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, "C2"));
 
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_b, Operands::UNTAGGED));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_b, "aoeu"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_b, "C1"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_b, "C2"));
 
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, Operands::UNTAGGED));
    CHECK_FALSE(walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, "aoeu"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, "C1"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, "C2"));
 
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, Operands::UNTAGGED));
    CHECK_FALSE(walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, "aoeu"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, "C1"));
    CHECK      (walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, "C2"));
 
    // some composability tests. Concatenation == logical AND
 
    CHECK(walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, Operands::UNTAGGED) == (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, Operands::UNTAGGED) && walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, Operands::UNTAGGED)));
    CHECK(walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, "C1"  ) == (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, "C1"  ) && walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, "C1"  )));
    CHECK(walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, "C2"  ) == (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, "C2"  ) && walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, "C2"  )));
    CHECK(walkIsCompatibleWithOperand(mrrg, nodes_a_to_c, "aoeu") == (walkIsCompatibleWithOperand(mrrg, nodes_a_to_a, "aoeu") && walkIsCompatibleWithOperand(mrrg, nodes_b_to_c, "aoeu")));
}
 
namespace {
 
struct FindNRoutingPathsBetweenTest {
    std::pair<int,int> num_paths_to_search_for_min_max;
    int max_paths_expected;
    std::pair<int,std::string> source;
    std::pair<int,std::string> sink;
    std::pair<int,int> cycle_path_latency_min_max;
    std::string mrrg_description;
    std::function<MRRG()> mrrg_generator;
};
 
}
 
TEST_CASE("findNRoutingPathsBetween Tests", "") {
    const auto test = GENERATE(values<FindNRoutingPathsBetweenTest>({
        { {1,3}, 1, {0,"fu"}, {0,"fu"}, {1,1}, "2 node loop with II=1, fu latency 0, reg latency 1", []{ return makeMRRG_2nodeFUAndReg(1, 0, 1); } },
    }));
 
    const auto num_paths_to_search_for = GENERATE_REF(range(
        test.num_paths_to_search_for_min_max.first, test.num_paths_to_search_for_min_max.second+1
    ));
    const auto mrrg = test.mrrg_generator();
    const auto src  = mrrg.getNode(test.source.first, test.source.second);
    const auto sink = mrrg.getNode(test.sink.first, test.sink.second);
    const auto actual = findNRoutingPathsBetween(
        num_paths_to_search_for, mrrg, src, sink, test.cycle_path_latency_min_max, {}, nullptr);
    CHECK(actual.size() <= test.max_paths_expected);
    CHECK(actual.size() <= num_paths_to_search_for);
}
 
namespace {
 
template<typename VertexNameLists>
auto resolve_node_name_lists(bool create_if_not_exist, MRRG& mrrg, const VertexNameLists& vertex_lists) {
    std::vector<std::vector<MRRG::NodeDescriptor>> result;
    for (const auto& vlist : vertex_lists) {
        std::vector<MRRG::NodeDescriptor> resolved_list;
        for (const auto& v_name : vlist) {
            const auto curr_ndesc_and_is_new = mrrg.insert(
                MRRGNode::make_routing(&god_module, 32, 0, v_name));
            if (curr_ndesc_and_is_new.second && not create_if_not_exist) {
                throw make_from_stream<std::logic_error>([&](auto&& s) {
                    s << "used non-existant node " << v_name;
                });
            }
            resolved_list.push_back(curr_ndesc_and_is_new.first);
            if (resolved_list.size() > 1) {
                const auto prev_ndesc = *std::next(resolved_list.rbegin());
                const auto& prev_fo = mrrg.fanout(prev_ndesc);
                // link if not already linked
                if (std::find(prev_fo.begin(), prev_fo.end(), curr_ndesc_and_is_new.first) == prev_fo.end()) {
                    if (not create_if_not_exist) { throw make_from_stream<std::logic_error>([&](auto&& s) {
                        s << "used non-existant edge to " << v_name;
                    });}
                    mrrg.link(prev_ndesc, curr_ndesc_and_is_new.first);
                }
            }
        }
        result.push_back(std::move(resolved_list));
    }
    return result;
};
 
struct MergeMRRGWalksTest {
    std::string test_description;
    // MRRG mrrg;
    std::vector<std::vector<std::string>> input;
    std::vector<std::vector<std::string>> expected;
};
 
} // end anon namespace
 
TEST_CASE("mergeMRRGWalks Tests", "") {
    const auto test = GENERATE(values<MergeMRRGWalksTest>({
        // NOTE: Many of these tests are tuned so that there is a unique solution.
        //       Nothing is assumed about the graph, but there is an assumption that
        //           mergeMRRGWalks uses breadth-first searches.
        { "two isolated paths", {
                { "a1", "z1" },
                { "a2", "z2" },
            }, {
                { "a1", "z1" },
                { "a2", "z2" },
            },
        },
        { "two diverging paths", {
                { "a", "z1" },
                { "a", "z2" },
            }, {
                { "a", "z1" },
                { "a", "z2" },
            },
        },
        { "two re-converging paths -- same start and end", {
                { "a", "b1", "c", "z" },
                { "a", "b2",      "z" },
            }, {
                { "a", "b2",      "z" },
            },
        },
        { "two re-converging paths -- same start, different end", {
                { "a", "b1", "c", "d", "e", "z1" },
                { "a", "b2",      "d",      "z2" },
            }, {
                { "a", "b2",      "d",      "z2" },
                {                 "d", "e", "z1" },
            },
        },
        { "two re-converging paths -- different start, different end", {
                { "x1", "y", "a", "b1", "c", "d", "e", "z1" },
                { "x2",      "a", "b2",      "d",      "z2" },
            }, {
                { "x2",      "a", "b2",      "d",      "z2" },
                {                            "d", "e", "z1" },
                { "x1", "y", "a",                           },
            },
        },
        { "a loop", {
                { "a", "b", "c", "a"},
            }, {
                { "a", "b", "c", "a"},
            },
        },
        { "a loop, plus a line -- only sharing a source", {
                { "a", "b", "c", "a"},
                { "a",                "z"},
            }, {
                { "a", "b", "c", "a"},
                { "a",                "z"},
            },
        },
        { "a loop, plus a line -- sharing the source and a fanout", {
                { "a", "b", "c", "a"},
                { "a", "b",           "d", "e", "z"},
            }, {
                { "a", "b", "c", "a"},
                {      "b",           "d", "e", "z"},
            },
        },
    }));
 
    GIVEN("A '" << test.test_description << "' test") {
        MRRG mrrg(1);
        const auto input = resolve_node_name_lists(true, mrrg, test.input);
        auto expected = resolve_node_name_lists(false, mrrg, test.expected);
        std::sort(expected.begin(), expected.end());
 
        auto actual = mergeMRRGWalks(mrrg, input);
        std::sort(actual.begin(), actual.end());
 
        CHECK(actual == expected);
    }
}
 
// remove if used
TEST_CASE("unused functions", "[!hide]") {
    (void)makeMRRG_2112DAG;
    (void)makeMRRG_112221DAG;
}