hybrid.hpp

/*******************************<GINKGO LICENSE>******************************
Copyright (c) 2017-2019, the Ginkgo authors
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its
contributors may be used to endorse or promote products derived from
this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
******************************<GINKGO LICENSE>*******************************/

#ifndef GKO_CORE_MATRIX_HYBRID_HPP_
#define GKO_CORE_MATRIX_HYBRID_HPP_


#include <algorithm>


#include <ginkgo/core/base/array.hpp>
#include <ginkgo/core/base/lin_op.hpp>
#include <ginkgo/core/matrix/coo.hpp>
#include <ginkgo/core/matrix/ell.hpp>


namespace gko {
namespace matrix {


template <typename ValueType>
class Dense;


template <typename ValueType = default_precision, typename IndexType = int32>
class Hybrid : public EnableLinOp<Hybrid<ValueType, IndexType>>,
               public EnableCreateMethod<Hybrid<ValueType, IndexType>>,
               public ConvertibleTo<Dense<ValueType>>,
               public ReadableFromMatrixData<ValueType, IndexType>,
               public WritableToMatrixData<ValueType, IndexType> {
    friend class EnableCreateMethod<Hybrid>;
    friend class EnablePolymorphicObject<Hybrid, LinOp>;
    friend class Dense<ValueType>;

public:
    using EnableLinOp<Hybrid>::convert_to;
    using EnableLinOp<Hybrid>::move_to;

    using value_type = ValueType;
    using index_type = IndexType;
    using mat_data = matrix_data<ValueType, IndexType>;
    using coo_type = Coo<ValueType, IndexType>;
    using ell_type = Ell<ValueType, IndexType>;

    class strategy_type {
    public:
        strategy_type()
            : ell_num_stored_elements_per_row_(zero<size_type>()),
              coo_nnz_(zero<size_type>())
        {}

        void compute_hybrid_config(const Array<size_type> &row_nnz,
                                   size_type *ell_num_stored_elements_per_row,
                                   size_type *coo_nnz)
        {
            Array<size_type> ref_row_nnz(row_nnz.get_executor()->get_master(),
                                         row_nnz.get_num_elems());
            ref_row_nnz = row_nnz;
            ell_num_stored_elements_per_row_ =
                this->compute_ell_num_stored_elements_per_row(&ref_row_nnz);
            coo_nnz_ = this->compute_coo_nnz(ref_row_nnz);
            *ell_num_stored_elements_per_row = ell_num_stored_elements_per_row_;
            *coo_nnz = coo_nnz_;
        }

        const size_type get_ell_num_stored_elements_per_row() const noexcept
        {
            return ell_num_stored_elements_per_row_;
        }

        const size_type get_coo_nnz() const noexcept { return coo_nnz_; }

        virtual size_type compute_ell_num_stored_elements_per_row(
            Array<size_type> *row_nnz) const = 0;

    protected:
        size_type compute_coo_nnz(const Array<size_type> &row_nnz) const
        {
            size_type coo_nnz = 0;
            auto row_nnz_val = row_nnz.get_const_data();
            for (size_type i = 0; i < row_nnz.get_num_elems(); i++) {
                if (row_nnz_val[i] > ell_num_stored_elements_per_row_) {
                    coo_nnz +=
                        row_nnz_val[i] - ell_num_stored_elements_per_row_;
                }
            }
            return coo_nnz;
        }

    private:
        size_type ell_num_stored_elements_per_row_;
        size_type coo_nnz_;
    };

    class column_limit : public strategy_type {
    public:
        explicit column_limit(size_type num_column = 0)
            : num_columns_(num_column)
        {}

        size_type compute_ell_num_stored_elements_per_row(
            Array<size_type> *row_nnz) const override
        {
            return num_columns_;
        }

    private:
        size_type num_columns_;
    };

    class imbalance_limit : public strategy_type {
    public:
        explicit imbalance_limit(float percent = 0.8) : percent_(percent)
        {
            percent_ = std::min(percent_, 1.0f);
            percent_ = std::max(percent_, 0.0f);
        }

        size_type compute_ell_num_stored_elements_per_row(
            Array<size_type> *row_nnz) const override
        {
            auto row_nnz_val = row_nnz->get_data();
            auto num_rows = row_nnz->get_num_elems();
            std::sort(row_nnz_val, row_nnz_val + num_rows);
            if (percent_ < 1) {
                auto percent_pos = static_cast<size_type>(num_rows * percent_);
                return row_nnz_val[percent_pos];
            } else {
                return row_nnz_val[num_rows - 1];
            }
        }

    private:
        float percent_;
    };

    class imbalance_bounded_limit : public strategy_type {
    public:
        imbalance_bounded_limit(float percent = 0.8, float ratio = 0.0001)
            : strategy_(imbalance_limit(percent)), ratio_(ratio)
        {}

        size_type compute_ell_num_stored_elements_per_row(
            Array<size_type> *row_nnz) const override
        {
            auto num_rows = row_nnz->get_num_elems();
            auto ell_cols =
                strategy_.compute_ell_num_stored_elements_per_row(row_nnz);
            return std::min(ell_cols,
                            static_cast<size_type>(num_rows * ratio_));
        }

    private:
        imbalance_limit strategy_;
        float ratio_;
    };


    class minimal_storage_limit : public strategy_type {
    public:
        minimal_storage_limit()
            : strategy_(
                  imbalance_limit(static_cast<double>(sizeof(IndexType)) /
                                  (sizeof(ValueType) + 2 * sizeof(IndexType))))
        {}

        size_type compute_ell_num_stored_elements_per_row(
            Array<size_type> *row_nnz) const override
        {
            return strategy_.compute_ell_num_stored_elements_per_row(row_nnz);
        }

    private:
        imbalance_limit strategy_;
    };


    class automatic : public strategy_type {
    public:
        automatic() : strategy_(imbalance_bounded_limit(1.0 / 3.0, 0.001)) {}

        size_type compute_ell_num_stored_elements_per_row(
            Array<size_type> *row_nnz) const override
        {
            return strategy_.compute_ell_num_stored_elements_per_row(row_nnz);
        }

    private:
        imbalance_bounded_limit strategy_;
    };

    void convert_to(Dense<ValueType> *other) const override;

    void move_to(Dense<ValueType> *other) override;

    void read(const mat_data &data) override;

    void write(mat_data &data) const override;

    value_type *get_ell_values() noexcept { return ell_->get_values(); }

    const value_type *get_const_ell_values() const noexcept
    {
        return ell_->get_const_values();
    }

    index_type *get_ell_col_idxs() noexcept { return ell_->get_col_idxs(); }

    const index_type *get_const_ell_col_idxs() const noexcept
    {
        return ell_->get_const_col_idxs();
    }

    size_type get_ell_num_stored_elements_per_row() const noexcept
    {
        return ell_->get_num_stored_elements_per_row();
    }

    size_type get_ell_stride() const noexcept { return ell_->get_stride(); }

    size_type get_ell_num_stored_elements() const noexcept
    {
        return ell_->get_num_stored_elements();
    }

    value_type &ell_val_at(size_type row, size_type idx) noexcept
    {
        return ell_->val_at(row, idx);
    }

    value_type ell_val_at(size_type row, size_type idx) const noexcept
    {
        return ell_->val_at(row, idx);
    }

    index_type &ell_col_at(size_type row, size_type idx) noexcept
    {
        return ell_->col_at(row, idx);
    }

    index_type ell_col_at(size_type row, size_type idx) const noexcept
    {
        return ell_->col_at(row, idx);
    }

    const ell_type *get_ell() const noexcept { return ell_.get(); }

    value_type *get_coo_values() noexcept { return coo_->get_values(); }

    const value_type *get_const_coo_values() const noexcept
    {
        return coo_->get_const_values();
    }

    index_type *get_coo_col_idxs() noexcept { return coo_->get_col_idxs(); }

    const index_type *get_const_coo_col_idxs() const noexcept
    {
        return coo_->get_const_col_idxs();
    }

    index_type *get_coo_row_idxs() noexcept { return coo_->get_row_idxs(); }

    const index_type *get_const_coo_row_idxs() const noexcept
    {
        return coo_->get_const_row_idxs();
    }

    size_type get_coo_num_stored_elements() const noexcept
    {
        return coo_->get_num_stored_elements();
    }

    const coo_type *get_coo() const noexcept { return coo_.get(); }

    size_type get_num_stored_elements() const noexcept
    {
        return coo_->get_num_stored_elements() +
               ell_->get_num_stored_elements();
    }

    std::shared_ptr<strategy_type> get_strategy() const noexcept
    {
        return strategy_;
    }

    Hybrid &operator=(const Hybrid &other)
    {
        if (&other == this) {
            return *this;
        }
        EnableLinOp<Hybrid<ValueType, IndexType>>::operator=(other);
        this->coo_->copy_from(other.get_coo());
        this->ell_->copy_from(other.get_ell());
        return *this;
    }

protected:
    Hybrid(
        std::shared_ptr<const Executor> exec,
        std::shared_ptr<strategy_type> strategy = std::make_shared<automatic>())
        : Hybrid(std::move(exec), dim<2>{}, std::move(strategy))
    {}

    Hybrid(
        std::shared_ptr<const Executor> exec, const dim<2> &size,
        std::shared_ptr<strategy_type> strategy = std::make_shared<automatic>())
        : Hybrid(std::move(exec), size, size[1], std::move(strategy))
    {}

    Hybrid(
        std::shared_ptr<const Executor> exec, const dim<2> &size,
        size_type num_stored_elements_per_row,
        std::shared_ptr<strategy_type> strategy = std::make_shared<automatic>())
        : Hybrid(std::move(exec), size, num_stored_elements_per_row, size[0],
                 {}, std::move(strategy))
    {}

    Hybrid(std::shared_ptr<const Executor> exec, const dim<2> &size,
           size_type num_stored_elements_per_row, size_type stride,
           std::shared_ptr<strategy_type> strategy)
        : Hybrid(std::move(exec), size, num_stored_elements_per_row, stride, {},
                 std::move(strategy))
    {}

    Hybrid(
        std::shared_ptr<const Executor> exec, const dim<2> &size,
        size_type num_stored_elements_per_row, size_type stride,
        size_type num_nonzeros = {},
        std::shared_ptr<strategy_type> strategy = std::make_shared<automatic>())
        : EnableLinOp<Hybrid>(exec, size),
          ell_(std::move(ell_type::create(
              exec, size, num_stored_elements_per_row, stride))),
          coo_(std::move(coo_type::create(exec, size, num_nonzeros))),
          strategy_(std::move(strategy))
    {}

    void apply_impl(const LinOp *b, LinOp *x) const override;

    void apply_impl(const LinOp *alpha, const LinOp *b, const LinOp *beta,
                    LinOp *x) const override;

private:
    std::shared_ptr<ell_type> ell_;
    std::shared_ptr<coo_type> coo_;
    std::shared_ptr<strategy_type> strategy_;
};


}  // namespace matrix
}  // namespace gko


#endif  // GKO_CORE_MATRIX_HYBRID_HPP_