dace.transformation.subgraph package

Submodules

dace.transformation.subgraph.expansion module

This module contains classes that implement the expansion transformation.

class dace.transformation.subgraph.expansion.MultiExpansion(*args, **kwargs)

Bases: SubgraphTransformation

Implements the MultiExpansion transformation. Takes all the lowest scope maps in a given subgraph, for each of these maps splits it into an outer and inner map, where the outer map contains the common ranges of all maps, and the inner map the rest. Map access variables and memlets are changed accordingly

allow_offset

Offset ranges to zero

apply(sdfg, map_base_variables=None)

Applies the transformation on the given subgraph.

Parameters:

sdfg – The SDFG that includes the subgraph.

can_be_applied(sdfg, subgraph)

Tries to match the transformation on a given subgraph, returning True if this transformation can be applied.

Parameters:
  • sdfg (SDFG) – The SDFG that includes the subgraph.

  • subgraph (SubgraphView) – The SDFG or state subgraph to try to apply the transformation on.

Return type:

bool

Returns:

True if the subgraph can be transformed, or False otherwise.

check_contiguity

Don’t allow expansion if last (contiguous)dimension is partially split

debug

Debug Mode

expand(sdfg, graph, map_entries, map_base_variables=None)

Expansion into outer and inner maps for each map in a specified set. The resulting outer maps all have same range and indices, corresponding variables and memlets get changed accordingly. The inner map contains the leftover dimensions

Parameters:
  • sdfg – Underlying SDFG

  • graph – Graph in which we expand

  • map_entries – List of Map Entries(Type MapEntry) that we want to expand

  • map_base_variables – Optional parameter. List of strings If None, then expand() searches for the maximal amount of equal map ranges and pushes those and their corresponding loop variables into the outer loop. If specified, then expand() pushes the ranges belonging to the loop iteration variables specified into the outer loop (For instance map_base_variables = [‘i’,’j’] assumes that all maps have common iteration indices i and j with corresponding correct ranges)

permutation_only

Only allow permutations without inner splits

properties()
sequential_innermaps

Make all inner maps that arecreated during expansion sequential

dace.transformation.subgraph.expansion.offset_map(state, map_entry)

dace.transformation.subgraph.gpu_persistent_fusion module

class dace.transformation.subgraph.gpu_persistent_fusion.GPUPersistentKernel(*args, **kwargs)

Bases: SubgraphTransformation

This transformation takes a given subgraph of an SDFG and fuses the given states into a single persistent GPU kernel. Before this transformation can be applied the SDFG needs to be transformed to run on the GPU (e.g. with the GPUTransformSDFG transformation).

If applicable the transform removes the selected states from the original SDFG and places a launch state in its place. The removed states will be added to a nested SDFG in the launch state. If necessary guard states will be added in the nested SDFG, in order to make sure global assignments on Interstate edges will be performed in the kernel (this can be disabled with the include_in_assignment property).

The given subgraph needs to fulfill the following properties to be fused:

  • All states in the selected subgraph need to fulfill the following:
    • access only GPU accessible memory

    • all concurrent DFGs inside the state are either sequential or inside a GPU_Device map.

  • the selected subgraph has a single point of entry in the form of a single InterstateEdge entering the subgraph (i.e. there is at most one state (not part of the subgraph) from which the kernel is entered and exactly one state inside the subgraph from which the kernel starts execution)

  • the selected subgraph has a single point of exit in the form of a single state that is entered after the selected subgraph is left (There can be multiple states from which the kernel can be left, but all will leave to the same state outside the subgraph)

apply(sdfg)

Applies the transformation on the given subgraph.

Parameters:

sdfg (SDFG) – The SDFG that includes the subgraph.

static can_be_applied(sdfg, subgraph)

Tries to match the transformation on a given subgraph, returning True if this transformation can be applied.

Parameters:
  • sdfg (SDFG) – The SDFG that includes the subgraph.

  • subgraph (SubgraphView) – The SDFG or state subgraph to try to apply the transformation on.

Returns:

True if the subgraph can be transformed, or False otherwise.

static get_entry_states(sdfg, subgraph)

Returns a 2-tuple of the (internal, external) states inside and outside of the SDFG, around which the new nested SDFG will be created. The first element will be a set of source nodes in the internal SDFG; and the second element will be a set of predecessor nodes to the nested SDFG.

static get_exit_states(sdfg, subgraph)

Returns a 2-tuple of the (internal, external) states inside and outside of the SDFG, around which the new nested SDFG will be created. The first element will be a set of sink nodes in the internal SDFG; and the second element will be a set of successor nodes to the nested SDFG.

include_in_assignment

Wether to include global variable assignments of the edge going into the kernel inside the kernel or have it happen on the outside. If the assignment is needed in the kernel, it needs to be included.

static is_gpu_state(sdfg, state)
Return type:

bool

kernel_prefix

Name of the kernel. If no value is given the kerenl will be refrenced as kernel, if a value is given the kernel will be named <kernel_prefix>_kernel. This is useful if multiple kernels are created.

properties()
validate

Validate the sdfg and the nested sdfg

dace.transformation.subgraph.helpers module

Subgraph Transformation Helper API

dace.transformation.subgraph.helpers.common_map_base_ranges(ranges)

Finds a maximal set of ranges that can be found in every instance of the ranges in the given list

Return type:

List[Range]

dace.transformation.subgraph.helpers.find_reassignment(maps, common_ranges, offset=False)

Provided a list of maps and their common base ranges (found via common_map_base_ranges()), for each map greedily assign each loop to an index so that a base range has the same index in every loop. If a loop range of a certain map does not correspond to a common base range, no index is assigned (=-1)

Parameters:
  • maps (List[Map]) – List of maps

  • common_ranges – Common ranges extracted via common_map_base_ranges()

  • offset – If true, offsets each range to 0 before checking

Return type:

Dict[Map, List]

Returns:

Dict that maps each map to a vector with the same length as number of map loops. The vector contains, in order, an index for each map loop that maps it to a common base range or ‘-1’ if it does not.

dace.transformation.subgraph.helpers.get_outermost_scope_maps(sdfg, graph, subgraph=None, scope_dict=None)

Returns all Map Entries inside of a given subgraph that have the outermost scope. If the underlying subgraph is not connected, there might be multiple locally outermost scopes. In this ambiguous case, the method returns an empty list. If subgraph == None, the whole graph is taken for analysis.

dace.transformation.subgraph.helpers.outermost_scope_from_maps(graph, maps, scope_dict=None)

Returns the outermost scope of a set of given maps. If the underlying maps are not topologically connected to each other, there might be several scopes that are locally outermost. In this case it throws an Exception

dace.transformation.subgraph.helpers.outermost_scope_from_subgraph(graph, subgraph, scope_dict=None)

Returns the outermost scope of a subgraph. If the subgraph is not connected, there might be several scopes that are locally outermost. In this case, it throws an Exception.

dace.transformation.subgraph.helpers.subgraph_from_maps(sdfg, graph, map_entries, scope_children=None)

Given a list of map entries in a single graph, return a subgraph view that includes all nodes inside these maps as well as map entries and exits as well as adjacent nodes.

dace.transformation.subgraph.subgraph_fusion module

This module contains classes that implement subgraph fusion.

class dace.transformation.subgraph.subgraph_fusion.SubgraphFusion(*args, **kwargs)

Bases: SubgraphTransformation

Implements the SubgraphFusion transformation. Fuses together the maps contained in the subgraph and pushes inner nodes into a global outer map, creating transients and new connections where necessary.

SubgraphFusion requires all lowest scope level maps in the subgraph to have the same indices and parameter range in every dimension. This can be achieved using the MultiExpansion transformation first. Reductions can also be expanded using ReduceExpansion as a preprocessing step.

adjust_arrays_nsdfg(sdfg, nsdfg, name, nname, memlet)

DFS to replace strides and volumes of data that exhibits nested SDFGs adjacent to its corresponding access nodes, applied during post-processing of a fused graph. Operates in-place.

Parameters:
  • sdfg (SDFG) – SDFG

  • nsdfg (NestedSDFG) – The Nested SDFG of interest

  • name (str) – Name of the array in the SDFG

  • nname (str) – Name of the array in the nested SDFG

  • memlet (Memlet) – Memlet adjacent to the nested SDFG that leads to the access node with the corresponding data name

apply(sdfg, do_not_override=None, **kwargs)

Apply the SubgraphFusion Transformation. See @fuse for more details

can_be_applied(sdfg, subgraph)

Fusible if :rtype: bool

  1. Maps have the same access sets and ranges in order

  2. Any nodes in between two maps are AccessNodes only, without WCR There is at most one AccessNode only on a path between two maps, no other nodes are allowed

  3. The exiting memlets’ subsets to an intermediate edge must cover the respective incoming memlets’ subset into the next map. Also, as a limitation, the union of all exiting memlets’ subsets must be contiguous.

  4. Check for any disjoint accesses of arrays.

static check_topo_feasibility(sdfg, graph, map_entries, intermediate_nodes, out_nodes)

Checks whether given outermost scoped map entries have topological structure apt for fusion

Parameters:
  • sdfg – SDFG

  • graph – State

  • map_entries – List of outermost scoped map entries induced by subgraph

  • intermediate_nodes – List of intermediate access nodes

  • out_nodes – List of outgoing access nodes

Returns:

Boolean value indicating fusibility

clone_intermediate_nodes(sdfg, graph, intermediate_nodes, out_nodes, map_entries, map_exits)

Creates cloned access nodes and data arrays for nodes that are both in intermediate nodes and out nodes, redirecting output from the original node to the cloned node. Operates in-place.

Parameters:
  • sdfg (SDFG) – SDFG

  • state – State of interest

  • intermediate_nodes (List[AccessNode]) – List of intermediate nodes appearing in a fusible subgraph

  • out_nodes (List[AccessNode]) – List of out nodes appearing in a fusible subgraph

  • map_entries (List[MapEntry]) – List of outermost scoped map entries in the subgraph

  • map_exits (List[MapExit]) – List of map exits corresponding to map_entries in order

Returns:

A dict that maps each intermediate node that also functions as an out node to the respective cloned transient node

consolidate

Consolidate edges that enter and exit the fused map.

copy_edge(graph, edge, new_src=None, new_src_conn=None, new_dst=None, new_dst_conn=None, new_data=None, remove_old=False)

Copies an edge going from source to dst. If no destination is specified, the edge is copied with the same destination and port as the original edge, else the edge is copied with the new destination and the new port. If no source is specified, the edge is copied with the same source and port as the original edge, else the edge is copied with the new source and the new port If remove_old is specified, the old edge is removed immediately If new_data is specified, inserts new_data as a memlet, else else makes a deepcopy of the current edges memlet

debug

Show debug info

static determine_compressible_nodes(sdfg, graph, intermediate_nodes, map_entries, map_exits, do_not_override=[])

Checks for all intermediate nodes whether they appear only within the induced fusible subgraph my map_entries and map_exits. This is returned as a dict that contains a boolean value for each intermediate node as a key.

Parameters:
  • sdfg (SDFG) – SDFG

  • state – State of interest

  • intermediate_nodes (List[AccessNode]) – List of intermediate nodes appearing in a fusible subgraph

  • map_entries (List[MapEntry]) – List of outermost scoped map entries in the subgraph

  • map_exits (List[MapExit]) – List of map exits corresponding to map_entries in order

  • do_not_override (List[str]) – List of data array names not to be compressed

  • return – A dictionary indicating for each data string whether its array can be compressed

determine_invariant_dimensions(sdfg, graph, intermediate_nodes, map_entries, map_exits)

Determines the invariant dimensions for each node – dimensions in which the access set of the memlets propagated through map entries and exits does not change.

Parameters:
  • sdfg (SDFG) – SDFG

  • state – State of interest

  • intermediate_nodes (List[AccessNode]) – List of intermediate nodes appearing in a fusible subgraph

  • map_entries (List[MapEntry]) – List of outermost scoped map entries in the subgraph

  • map_exits (List[MapExit]) – List of map exits corresponding to map_entries in order

Returns:

A dict mapping each intermediate node (nodes.AccessNode) to a list of integer dimensions

disjoint_subsets

Check for disjoint subsets in can_be_applied. If multipleaccess nodes pointing to the same data appear within a subgraphto be fused, this check confirms that their access sets areindependent per iteration space to avoid race conditions.

fuse(sdfg, graph, map_entries, do_not_override=None, **kwargs)

takes the map_entries specified and tries to fuse maps.

all maps have to be extended into outer and inner map (use MapExpansion as a pre-pass)

Arrays that don’t exist outside the subgraph get pushed into the map and their data dimension gets cropped. Otherwise the original array is taken.

For every output respective connections are crated automatically.

Parameters:
  • sdfg (SDFG) – SDFG

  • graph (SDFGState) – State

  • map_entries (List[MapEntry]) – Map Entries (class MapEntry) of the outer maps which we want to fuse

  • do_not_override – List of data names whose corresponding nodes are fully contained within the subgraph but should not be compressed nevertheless.

static get_adjacent_nodes(sdfg, graph, map_entries)

For given map entries, finds a set of in, out and intermediate nodes as defined below

Parameters:
  • sdfg – SDFG

  • graph – State of interest

  • map_entries – List of all outermost scoped maps that induce the subgraph

Return type:

Tuple[List[AccessNode], List[AccessNode], List[AccessNode]]

Returns:

Tuple of (in_nodes, intermediate_nodes, out_nodes)

  • In_nodes are nodes that serve as pure input nodes for the map entries

  • Out nodes are nodes that serve as pure output nodes for the map entries

  • Interemdiate nodes are nodes that serve as buffer storage between outermost scoped map entries and exits of the induced subgraph

-> in_nodes are trivially disjoint from the other two types of access nodes -> Intermediate_nodes and out_nodes are not necessarily disjoint

get_invariant_dimensions(sdfg, graph, map_entries, map_exits, node)

For a given intermediate access node, return a set of indices that correspond to array / subset dimensions in which no change is observed upon propagation through the corresponding map nodes in map_entries / map_exits.

Parameters:
  • map_entries (List[MapEntry]) – List of outermost scoped map entries

  • map_exits (List[MapExit]) – List of corresponding exit nodes to map_entries, in order

  • node (AccessNode) – Intermediate access node of interest

Returns:

Set of invariant integer dimensions

keep_global

A list of array names to treat as non-transients and not compress

prepare_intermediate_nodes(sdfg, graph, in_nodes, out_nodes, intermediate_nodes, map_entries, map_exits, do_not_override=[])

Helper function that computes the following information: 1. Determine whether intermediate nodes only appear within the induced fusible subgraph. This is equivalent to checking for compresssibility. 2. Determine whether any intermediate transients are also out nodes, if so they have to be cloned 3. Determine invariant dimensions for any intermediate transients (that are compressible).

Returns:

A tuple (subgraph_contains_data, transients_created, invariant_dimensions) of dictionaries containing the necessary information

propagate

Propagate memlets of edges that enter and exit the fused map.Disable if this causes problems (e.g., if memlet propagation doesnot work correctly).

properties()
schedule_innermaps

Schedule of inner maps. If none, keeps schedule.

transient_allocation

Storage Location to push transients to that are fully contained within the subgraph.

Module contents

This module initializes the subgraph transformations package.