Auto-tuner infrastructure: optimal fusion infrastructure

Global optimization of a pipeline consists of a set of choices. Some choices are "local" (i.e. what is the best miopen kernel for a particular convolution), and some choices are more "global".

I will open multiple Auto-tuner tickets over time. This is the first one.

Examples of global choices:
Consider a simple pipeline subgraph, the following sequence of kernels:
A -> B -> C

Assume that the following fusions are available:
(AB) = A->B, and (BC) = B->C

What is the best pipeline implementation?

1. A ->B->C (no fusions)?
2. AB -> C (fuse AB, then do C)?
3. A->BC (A, and then fused BC)?

There are multiple other use cases, and designs of increasing complexity and sophistication, but in the interest of getting the feet wet, a good start is as follows:

Represent the execution graph as a dataflow graph datastructure, where each vertex represents data, and edges in the graph represent kernels implementations available that connect input to output data nodes.

In the example above, for simplicity assume that
A B C
D1 ---> D2 ---->D3---->D4.

With the available fusions, there are two more edges in the graph: Edge D1->D3, via fusion AB, and edge D2->D4, via fusion BC.

Decorate each edge via an (preferably GPU side) execution time. The goal is to find a path in the graph that connects D1 to D4, such that the sum of the times along that path is minimized. This is a well known problem in graph theory, for example algorithms include Dijkstra’s shortest path algorithm, and the Bellman–Ford algorithm.

for future (just to have an idea of what future extensions would be):
The datatypes of various tensors will in general decorate the vertices, as well the layouts (NCHWc) of the various tensors. Depending on the decorators, there will be more edges in the graph. For the quantization part, this is hardly worth the effort, as it can be assumed that quantization will unambiguously win. However mixed-layouts may present a non trivial and not a priori obvious optimization opportunity. Once miopen exposes this, it will be important to include it in the auto-tuning scheme.

Furthermore, in the future, assuming we move towards depth first fusion pipelines, this will be a very important ingredient.

The issue names no files, tests, or existing entry point; start by locating the auto-tuner infrastructure and graph representation in AMDMIGraphX. Define the graph and shortest-path design, including edge execution-time data, and document how the initial A→B→C fusion example will be evaluated.