arm_compute/core/experimental/DependencyGraph.h

/*
 * Copyright (c) 2022 Arm Limited.
 *
 * SPDX-License-Identifier: MIT
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef ENABLE_EXPERIMENTAL_DYNAMIC_FUSION
#error "This experimental feature must be enabled with -DENABLE_EXPERIMENTAL_DYNAMIC_FUSION"
#endif /* ENABLE_EXPERIMENTAL_DYNAMIC_FUSION */
#ifndef ARM_COMPUTE_EXPERIMENTAL_DYNAMICFUSION_DEPENDENCYGRAPH_H
#define ARM_COMPUTE_EXPERIMENTAL_DYNAMICFUSION_DEPENDENCYGRAPH_H

#include "arm_compute/core/Error.h"

#include <algorithm>
#include <map>
#include <vector>

namespace arm_compute
{
namespace experimental
{
namespace dynamic_fusion
{
template <typename T>
bool is_in(const T &v, const std::vector<T> &vec)
{
    return std::find(std::begin(vec), std::end(vec), v) != std::end(vec);
}

/** The dependency graph of a workload, where the nodes are of 2 types: Tensor or Operator
 *  Represented as a doubly-linked adjacency list with the differentiation between source and destination
 *
 * A "Merge Tensor" is an external tensor associated with the tensor within the graph, and serve as a merge point
 */
class DependencyGraph
{
public:
    /** A serial Id allocator
     *
     */
    class SerialIdAllocator
    {
    public:
        using Id = int;
        Id alloc()
        {
            return _counter++;
        }
        constexpr static Id empty()
        {
            return -1;
        }

    private:
        Id _counter{ 0 };
    };
    using Id = SerialIdAllocator::Id;
    /** Adjacency list
     *
     */
    using AdjList = std::map<Id, std::vector<Id>>;

    /** A pack of operator including its input and output tensors, used by traversing through the graph in topological order
     *
     */
    struct OpPack
    {
        Id              op{};
        std::vector<Id> inputs{};
        std::vector<Id> outputs{};
        friend bool operator==(const OpPack &opp0, const OpPack &opp1)
        {
            return std::make_tuple(
                       opp0.op, opp0.inputs, opp0.outputs)
                   == std::make_tuple(
                       opp1.op, opp1.inputs, opp1.outputs);
        }
    };

public:
    constexpr static Id empty_id()
    {
        return SerialIdAllocator::empty();
    }

    DependencyGraph() = default;
    // Used in cases where two DependencyGraphs may want to share the same configuration of tensors
    explicit DependencyGraph(const std::vector<Id> &imported_tensors);
    // Testing only
    DependencyGraph(const AdjList &adj_src_tensors, const AdjList &adj_dst_tensors, const AdjList &adj_src_ops, const AdjList &adj_dst_ops, std::map<Id, Id> merge_points = {});

    /** Add a new tensor
     *
     * @param merge_tensor The external merge point associated with the tensor. Leave empty if not needed.
     * @return Id  The newly allocated tensor, or a previously added tensor associated with @p merge_tensor
     */
    Id add_tensor(Id merge_tensor = empty_id());

    void remove_tensor(Id tensor);

    /** Add a new operator
     *
     * @param inputs  Input tensors to the operator
     * @param outputs  Output tensors to the operator
     * @return std::pair<Status, DependencyGraph::Id> where id is the newly allocated operator
     */
    std::pair<Status, DependencyGraph::Id> add_operator(const std::vector<Id> &inputs, const std::vector<Id> &outputs);

    void remove_operator(Id op);
    /** Sort the graph in a topological order
     *
     * @return std::pair<Status, std::vector<OpPack>>
     */
    std::pair<Status, std::vector<OpPack>> topological_sort() const;

    std::vector<Id> src_ops(Id op) const;
    std::vector<Id> dst_ops(Id op) const;

    std::vector<Id> src_ops_from_tensor(Id tensor) const;
    std::vector<Id> dst_ops_from_tensor(Id tensor) const;
    /** Get the merge points object
     *
     * @return std::map<Id, Id>
     */
    std::map<Id, Id> get_merge_points() const;
    /** Get all root ops. Root ops can also be referred to as "src ops" of the whole graph
     *
     * @return std::vector<Id>
     */
    std::vector<Id> get_root_ops() const;
    /** Get all dst ops of the whole graph
     *
     * @return std::vector<Id>
     */
    std::vector<Id> get_dst_ops() const;

    /** Get source tensors to an operator
     *
     * @param op
     * @return std::vector<Id>
     */
    std::vector<Id> src_tensors(Id op) const;
    /** Get destination tensors to an operator
     *
     * @param op
     * @return std::vector<Id>
     */
    std::vector<Id> dst_tensors(Id op) const;
    /** Get source tensors of the whole graph
     *
     * @return std::vector<Id>
     */
    std::vector<Id> src_tensors() const;
    /** Get destination tensors of the whole graph
     *
     * @return std::vector<Id>
     */
    std::vector<Id> dst_tensors() const;
    /** Get all operators
     *
     * @return std::vector<Id>
     */
    std::vector<Id> all_ops() const;
    /** Get all tensors
     *
     * @return std::vector<Id>
     */
    std::vector<Id> all_tensors() const;
    /** Number of operators
     *
     * @return unsigned int
     */
    unsigned int number_of_ops() const;
    /** Number of tensors
     *
     * @return unsigned int
     */
    unsigned int number_of_tensors() const;

    /** Update @p merge_point to point to @p t_id
     *
     * @param t_id
     * @param merge_point
     */
    Status update_merge_point(Id t_id, Id merge_point);

    /** Strict equality comparison (all internal ids and order of insertion matter).
     *        In the future this may be replaced with a topological comparison, allowing equivalent graphs with different internal ids to be equal
     *
     *
     * @param g0
     * @param g1
     * @return true
     * @return false
     */
    friend bool operator==(const DependencyGraph &g0, const DependencyGraph &g1)
    {
        // Do not compare id allocators
        return std::make_tuple(
                   g0._adj_src_tensors, g0._adj_dst_tensors, g0._adj_src_ops, g0._adj_dst_ops, g0._merge_to_internal)
               == std::make_tuple(
                   g1._adj_src_tensors, g1._adj_dst_tensors, g1._adj_src_ops, g1._adj_dst_ops, g1._merge_to_internal);
    }
    void link_input(Id op, Id in_tensor);
    void link_output(Id op, Id out_tensor);
    /** Check if there's a path from @p src_tensor to @p dst_op
     *
     * @param src_tensor
     * @param dst_op
     * @return true
     * @return false
     */
    bool path_exists_from_tensor_to_op(Id src_tensor, Id dst_op) const;
    /** Check if there's a path from @p src_op to @p dst_op
     *
     * @param src_op
     * @param dst_op
     * @return true
     * @return false
     */
    bool path_exists_from_op_to_op(Id src_op, Id dst_op) const;
    /** Check if tensor is the src tensor of the entire graph
     *
     * @param tensor
     * @return true
     * @return false
     */
    bool is_src_tensor(Id tensor) const;
    /** Check if tensor is the dst tensor of the entire graph
     *
     * @param tensor
     * @return true
     * @return false
     */
    bool is_dst_tensor(Id tensor) const;

private:
    Id   insert_new_tensor();
    Id   insert_new_op();
    bool tensor_exists(Id tensor) const;
    bool operator_exists(Id op) const;
    bool is_src_tensor_of(Id op, Id tensor) const;
    bool is_dst_tensor_of(Id op, Id tensor) const;
    bool are_connected(Id op, Id tensor) const;

private:
    AdjList _adj_src_tensors{};
    AdjList _adj_dst_tensors{};
    AdjList _adj_src_ops{};
    AdjList _adj_dst_ops{};
    std::map<Id, Id> _merge_to_internal{}; // From merge tensor to internal tensor
    SerialIdAllocator _operator_id{};
    SerialIdAllocator _tensor_id{};
};

} // namespace dynamic_fusion
} // namespace experimental
} // namespace arm_compute

#endif //ARM_COMPUTE_EXPERIMENTAL_DYNAMICFUSION_DEPENDENCYGRAPH_H