#include <CGRA/HeuristicMappers.h>
#include <CGRA/ConstraintSet.h>
#include <CGRA/GraphAlgorithms.h>
#include <CGRA/Module.h>
#include <CGRA/MRRGProcedures.h>
#include <CGRA/OpGraphProcedures.h>
#include <CGRA/TupleHash.h>
#include <CGRA/utility/CodeProfiling.h>
#include <CGRA/utility/Functional.h>
#include <gurobi_c++.h>
#include <chrono>
#include <fstream>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>

Classes
struct	OpAndFU

struct	EdgeAndFU

struct	MRRGNodePair

struct	MRRGPathID

struct	GorSatCPVarID

struct	InternalILPHeuristicMapperOptions

Typedefs
template<typename MappedType >
using	OpAndFUMap = std::unordered_map< OpAndFU, MappedType, OpAndFU::Hash >

template<typename MappedType >
using	EdgeAndFUMap = std::unordered_map< EdgeAndFU, MappedType, EdgeAndFU::Hash >

template<typename MappedType >
using	FUMap = std::unordered_map< MRRG::NodeDescriptor, MappedType >

Functions
template<typename CFN >
auto	unionOfCompatibleNodes (const OpGraph &opgraph, const CFN &compatible_fu_nodes)

std::string	from_src_at_to_sink_at (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, MRRG::NodeDescriptor src_compatible_node, OpGraph::OpDescriptor sink_op, MRRG::NodeDescriptor sink_compatible_node, bool make_name_solver_safe=false)

std::string	from_src_at_to_sink_at (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, MRRG::NodeDescriptor src_compatible_node, OpGraph::EdgeDescriptor out_edge, MRRG::NodeDescriptor sink_compatible_node, bool make_name_solver_safe=false)

std::string	from_src_at_to_sink_at_trip_count (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, MRRG::NodeDescriptor src_compatible_node, OpGraph::OpDescriptor sink_op, MRRG::NodeDescriptor sink_compatible_node, int trip_count, bool make_name_solver_safe=false)

std::string	from_src_at_to_sink_at_trip_count (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, MRRG::NodeDescriptor src_compatible_node, OpGraph::EdgeDescriptor out_edge, MRRG::NodeDescriptor sink_compatible_node, int trip_count, bool make_name_solver_safe=false)

std::string	from_src_at_to_sink_at_trip_count_number (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, MRRG::NodeDescriptor src_compatible_node, OpGraph::OpDescriptor sink_op, MRRG::NodeDescriptor sink_compatible_node, int trip_count, int number, bool make_name_solver_safe=false)

std::string	from_src_at_to_sink (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, MRRG::NodeDescriptor src_compatible_node, OpGraph::OpDescriptor sink_op, bool make_name_solver_safe=false)

std::string	from_src_to_sink_at (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, OpGraph::OpDescriptor src_op, OpGraph::EdgeDescriptor out_edge, MRRG::NodeDescriptor sink_compatible_node, bool make_name_solver_safe=false)

std::string	from_mrrg_node_to_mrrg_node (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, MRRG::NodeDescriptor src_compatible_node, MRRG::NodeDescriptor sink_compatible_node, bool make_name_solver_safe=false)

std::string	from_mrrg_node_to_mrrg_node_trip_count_number (std::string prefix, const OpGraph &opgraph, const MRRG &mrrg, MRRG::NodeDescriptor src_compatible_node, MRRG::NodeDescriptor sink_compatible_node, int trip_count, int number, bool make_name_solver_safe=false)

std::ostream &	operator<< (std::ostream &os, const ILPHeuristicMapperOptions &opts)

Mapping	mapViaConnectivityAndPathChoosing (std::unordered_map< std::string, std::string > fix_port, const OpGraph &opgraph, const MRRG &mrrg, const Mapping &initial_mapping, ILPHeuristicMapperOptions options_, ILPHeuristicMapperCaches caches)

Mapping	mapOpsJustByConnectivity (std::unordered_map< std::string, std::string > fix_port, const OpGraph &opgraph, const MRRG &mrrg, ILPHeuristicMapperOptions options, ILPHeuristicMapperCaches caches, Mapping initial_mapping)

Mapping	routeOpMappingByChoosingPaths (std::unordered_map< std::string, std::string > fix_port, const Mapping &op_mapping, const OpGraph &opgraph, const MRRG &mrrg, RouteOpMappingByChoosingPathsOptions options, ILPHeuristicMapperCaches caches)

Variables
const NodeFilter	allowAllNodes = [](const MRRG::NodeDescriptor&) { return true; }

const OpNodeFilter	allowAllNodesForOps = [](const OpGraph::OpDescriptor&, const MRRG::NodeDescriptor&) { return true; }

static const std::map< std::string, FUCoster >	fu_costers

AutoRegisterMapper	ILPHeuristicMapper_arm ("ILPHeuristicMapper", [](std::shared_ptr< CGRA > cgra, int timelimit, const ConfigStore &args) { return std::make_unique< ILPHeuristicMapper >(cgra, timelimit, args);}, false, "Iteratively considers more flexibility.\n" "Initially presented in 'Generic Connectivity-Based CGRA Mapping via Integer Linear Programming' (FCCM 2019)", { {"allow_recomputation", false, "Allow ops to map to more than one FU"}, {"allow_unbalanced_latency", false, "Assume a dataflow-like architecture"}, {"fu_coster", "", "Specify one of the available cost functions on functional units.\n" "Empty string for none. Other options include: `one': each FU costs 1"}, {"do_cache_warmup", true, "Low-overhead option that gives a better estimate of what mapping time would be like if arch-specific data was saved to disk"}, {"nneigh_start", "", "The number-of-neighbours to start solving at. Default depends on arch_id"}, {"nneigh_stop", "", "The last number-of-neighbours to try. Default depends on arch_id"}, {"nneigh_step", 2, "The amount number-of-neighbours is increased between attempts"}, {"do_test_placement", true, "At each number-of-neighbours, try solving without modelling routing first"}, {"do_final_combined_attempt", false, "At each number-of-neighbours, if unable to route any placements, try placing & routing at the same time"}, {"max_threads", 1, ""}, {"model_dump_filename", "", ""}, {"model_IIS_dump_filename", "", ""}, {"seed", 0, ""}, {"verbosity", 0, ""}, {"arch_id", "", ""}, }, { {"hm_test_placement_.", "Pass options directly to test_placement"}, {"hm_outer_.", "Pass options directly to outer"}, {"hm_inner_.", "Pass options directly to inner"}, {"hm_combined_.", "Pass options directly to final combined P+R attempt"}, })

Typedef Documentation

◆ EdgeAndFUMap

template<typename MappedType >

using EdgeAndFUMap = std::unordered_map<EdgeAndFU, MappedType, EdgeAndFU::Hash>

Definition at line 342 of file HeuristicMappers.cpp.

◆ FUMap

template<typename MappedType >

using FUMap = std::unordered_map<MRRG::NodeDescriptor, MappedType>

Definition at line 345 of file HeuristicMappers.cpp.

◆ OpAndFUMap

template<typename MappedType >

using OpAndFUMap = std::unordered_map<OpAndFU, MappedType, OpAndFU::Hash>

Definition at line 339 of file HeuristicMappers.cpp.

Function Documentation

◆ from_mrrg_node_to_mrrg_node()

std::string from_mrrg_node_to_mrrg_node	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		MRRG::NodeDescriptor	src_compatible_node,
		MRRG::NodeDescriptor	sink_compatible_node,
		bool	make_name_solver_safe = `false`
	)

Definition at line 232 of file HeuristicMappers.cpp.

◆ from_mrrg_node_to_mrrg_node_trip_count_number()

std::string from_mrrg_node_to_mrrg_node_trip_count_number	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		MRRG::NodeDescriptor	src_compatible_node,
		MRRG::NodeDescriptor	sink_compatible_node,
		int	trip_count,
		int	number,
		bool	make_name_solver_safe = `false`
	)

Definition at line 241 of file HeuristicMappers.cpp.

◆ from_src_at_to_sink()

std::string from_src_at_to_sink	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		MRRG::NodeDescriptor	src_compatible_node,
		OpGraph::OpDescriptor	sink_op,
		bool	make_name_solver_safe = `false`
	)

Definition at line 214 of file HeuristicMappers.cpp.

◆ from_src_at_to_sink_at() [1/2]

std::string from_src_at_to_sink_at	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		MRRG::NodeDescriptor	src_compatible_node,
		OpGraph::EdgeDescriptor	out_edge,
		MRRG::NodeDescriptor	sink_compatible_node,
		bool	make_name_solver_safe = `false`
	)

Definition at line 161 of file HeuristicMappers.cpp.

◆ from_src_at_to_sink_at() [2/2]

std::string from_src_at_to_sink_at	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		MRRG::NodeDescriptor	src_compatible_node,
		OpGraph::OpDescriptor	sink_op,
		MRRG::NodeDescriptor	sink_compatible_node,
		bool	make_name_solver_safe = `false`
	)

Definition at line 146 of file HeuristicMappers.cpp.

◆ from_src_at_to_sink_at_trip_count() [1/2]

std::string from_src_at_to_sink_at_trip_count	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		MRRG::NodeDescriptor	src_compatible_node,
		OpGraph::EdgeDescriptor	out_edge,
		MRRG::NodeDescriptor	sink_compatible_node,
		int	trip_count,
		bool	make_name_solver_safe = `false`
	)

Definition at line 188 of file HeuristicMappers.cpp.

◆ from_src_at_to_sink_at_trip_count() [2/2]

std::string from_src_at_to_sink_at_trip_count	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		MRRG::NodeDescriptor	src_compatible_node,
		OpGraph::OpDescriptor	sink_op,
		MRRG::NodeDescriptor	sink_compatible_node,
		int	trip_count,
		bool	make_name_solver_safe = `false`
	)

Definition at line 175 of file HeuristicMappers.cpp.

◆ from_src_at_to_sink_at_trip_count_number()

std::string from_src_at_to_sink_at_trip_count_number	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		MRRG::NodeDescriptor	src_compatible_node,
		OpGraph::OpDescriptor	sink_op,
		MRRG::NodeDescriptor	sink_compatible_node,
		int	trip_count,
		int	number,
		bool	make_name_solver_safe = `false`
	)

Definition at line 201 of file HeuristicMappers.cpp.

◆ from_src_to_sink_at()

std::string from_src_to_sink_at	(	std::string	prefix,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		OpGraph::OpDescriptor	src_op,
		OpGraph::EdgeDescriptor	out_edge,
		MRRG::NodeDescriptor	sink_compatible_node,
		bool	make_name_solver_safe = `false`
	)

Definition at line 223 of file HeuristicMappers.cpp.

◆ mapOpsJustByConnectivity()

Mapping mapOpsJustByConnectivity	(	std::unordered_map< std::string, std::string >	fix_port,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		ILPHeuristicMapperOptions	options,
		ILPHeuristicMapperCaches	caches = `{}`,
		Mapping	initial_mapping = `Mapping{std::make_shared< CGRA >(), -1, std::make_shared< OpGraph >()}`
	)

Finds compatible FU nodes in mrrg for the ops in opgraph, and uses just the connectivity of these FUs to come up with a op mapping.

Definition at line 1707 of file HeuristicMappers.cpp.

◆ mapViaConnectivityAndPathChoosing()

Mapping mapViaConnectivityAndPathChoosing	(	std::unordered_map< std::string, std::string >	fix_port,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		const Mapping &	initial_mapping,
		ILPHeuristicMapperOptions	options_,
		ILPHeuristicMapperCaches	caches
	)

Definition at line 347 of file HeuristicMappers.cpp.

◆ operator<<()

std::ostream& operator<<	(	std::ostream &	os,
		const ILPHeuristicMapperOptions &	opts
	)

Definition at line 252 of file HeuristicMappers.cpp.

◆ routeOpMappingByChoosingPaths()

Mapping routeOpMappingByChoosingPaths	(	std::unordered_map< std::string, std::string >	fix_port,
		const Mapping &	op_mapping,
		const OpGraph &	opgraph,
		const MRRG &	mrrg,
		RouteOpMappingByChoosingPathsOptions	options = `{ {}, acceptTheFirstSolution, {} }`,
		ILPHeuristicMapperCaches	caches = `{}`
	)

Queries op_mapping for the FUs that the ops in opgraph are mapped to, finds candidate paths between those FUs, and tries to find a legal set of paths.

Definition at line 1718 of file HeuristicMappers.cpp.

◆ unionOfCompatibleNodes()

template<typename CFN >

auto unionOfCompatibleNodes	(	const OpGraph &	opgraph,
		const CFN &	compatible_fu_nodes
	)

Definition at line 83 of file HeuristicMappers.cpp.

Variable Documentation

◆ allowAllNodes

const NodeFilter allowAllNodes = [](const MRRG::NodeDescriptor&) { return true; }

Definition at line 31 of file HeuristicMappers.cpp.

◆ allowAllNodesForOps

const OpNodeFilter allowAllNodesForOps = [](const OpGraph::OpDescriptor&, const MRRG::NodeDescriptor&) { return true; }

Definition at line 32 of file HeuristicMappers.cpp.

◆ fu_costers

const std::map<std::string,FUCoster> fu_costers

static

Initial value:

{
    {"", {}},
    {"one", [](
        const OpGraph& opgraph, const MRRG& mrrg,
        const OpGraph::OpDescriptor& op,  const MRRG::NodeDescriptor& node
    ) {
        (void)opgraph; (void)mrrg; (void)op; (void)node;
        return 1.0;
    }},
}

Definition at line 1731 of file HeuristicMappers.cpp.

◆ ILPHeuristicMapper_arm

AutoRegisterMapper ILPHeuristicMapper_arm("ILPHeuristicMapper",[](std::shared_ptr< CGRA > cgra, int timelimit, const ConfigStore &args) { return std::make_unique< ILPHeuristicMapper >(cgra, timelimit, args);}, false, "Iteratively considers more flexibility.\n" "Initially presented in 'Generic Connectivity-Based CGRA Mapping via Integer Linear Programming' (FCCM 2019)", { {"allow_recomputation", false, "Allow ops to map to more than one FU"}, {"allow_unbalanced_latency", false, "Assume a dataflow-like architecture"}, {"fu_coster", "", "Specify one of the available cost functions on functional units.\n" "Empty string for none. Other options include: `one': each FU costs 1"}, {"do_cache_warmup", true, "Low-overhead option that gives a better estimate of what mapping time would be like if arch-specific data was saved to disk"}, {"nneigh_start", "", "The number-of-neighbours to start solving at. Default depends on arch_id"}, {"nneigh_stop", "", "The last number-of-neighbours to try. Default depends on arch_id"}, {"nneigh_step", 2, "The amount number-of-neighbours is increased between attempts"}, {"do_test_placement", true, "At each number-of-neighbours, try solving without modelling routing first"}, {"do_final_combined_attempt", false, "At each number-of-neighbours, if unable to route any placements, try placing & routing at the same time"}, {"max_threads", 1, ""}, {"model_dump_filename", "", ""}, {"model_IIS_dump_filename", "", ""}, {"seed", 0, ""}, {"verbosity", 0, ""}, {"arch_id", "", ""}, }, { {"hm_test_placement_.*", "Pass options directly to test_placement"}, {"hm_outer_.*", "Pass options directly to outer"}, {"hm_inner_.*", "Pass options directly to inner"}, {"hm_combined_.*", "Pass options directly to final combined P+R attempt"}, })

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ EdgeAndFUMap

◆ FUMap

◆ OpAndFUMap

Function Documentation

◆ from_mrrg_node_to_mrrg_node()

◆ from_mrrg_node_to_mrrg_node_trip_count_number()

◆ from_src_at_to_sink()

◆ from_src_at_to_sink_at() [1/2]

◆ from_src_at_to_sink_at() [2/2]

◆ from_src_at_to_sink_at_trip_count() [1/2]

◆ from_src_at_to_sink_at_trip_count() [2/2]

◆ from_src_at_to_sink_at_trip_count_number()

◆ from_src_to_sink_at()

◆ mapOpsJustByConnectivity()

◆ mapViaConnectivityAndPathChoosing()

◆ operator<<()

◆ routeOpMappingByChoosingPaths()

◆ unionOfCompatibleNodes()

Variable Documentation

◆ allowAllNodes

◆ allowAllNodesForOps

◆ fu_costers

◆ ILPHeuristicMapper_arm