From 311a3d781a29b24ff2a8b0b0c9556c4f89949abf Mon Sep 17 00:00:00 2001 From: Mark Hoemmen Date: Fri, 11 Mar 2016 12:37:25 +0800 Subject: [PATCH 1/5] Kokkos::StaticCrsGraph: Add findRelOffset (see Trilinos #205) Kokkos::Details::findRelOffset is a new function (free function, not method) that finds the relative offset of an index in a row of a sparse graph or matrix, given an array of column indices in that row. The array may be either a rank-1 Kokkos::View or a raw 1-D array. The new function is intended to replace Tpetra::CrsGraph::find*Index in Trilinos, and thus fix https://github.com/trilinos/Trilinos/issues/205 and related issues. NOTE: This function is NOT fully optimized! In particular, it only does linear search, and currently ignores the 'isSorted' argument (which would let it do binary search). Please see Tpetra::CrsGraph::findLocalIndex in Trilinos for the full set of optimizations. --- .../containers/src/Kokkos_StaticCrsGraph.hpp | 89 ++++++++++++++++++++++ 1 file changed, 89 insertions(+) diff --git a/packages/kokkos/containers/src/Kokkos_StaticCrsGraph.hpp b/packages/kokkos/containers/src/Kokkos_StaticCrsGraph.hpp index 1ce3863..d6bff23 100644 --- a/packages/kokkos/containers/src/Kokkos_StaticCrsGraph.hpp +++ b/packages/kokkos/containers/src/Kokkos_StaticCrsGraph.hpp @@ -138,6 +138,95 @@ public: } }; +namespace Details { + +/// \brief Search indsToSearch[0 .. numEnt-1] for +/// \c indToFind, using equality comparison. +/// +/// \return If found, return index of \c indToFind in \c indsToSearch; +/// else, return \c numEnt (by analogy with C++ Standard Library +/// functions like std::find, that return "the end of the sequence" +/// in this case). +/// +/// \tparam OffsetType Integer type that can be used to represent any +/// valid index in \c indsToSearch, up to and including \c numEnt. +/// \tparam IndexViewType 1-D array of equality-comparable entries +/// (generally intended to be column indices). +/// +/// \param indsToSearch [in] Array of indices to search. For a sparse +/// graph or matrix, this is the array of all the column indices for +/// some row of the graph / matrix. +/// \param numEnt [in] Number of entries to search in \c indsToSearch. +/// This is a separate argument, rather than just calling +/// indsToSearch.dimension_0(), in order to avoid the +/// overhead of calling Kokkos::subview. This may help performance, +/// especially for the case of the begin/end-pointer variant of CSR +/// graph/matrix storage. +/// \param indToFind [in] (Local) column index for which to find the +/// offset. This has the same type as that of each entry in +/// \c indsToSearch. +/// \param hint [in] Hint for where to find \c indToFind in the array. +/// If indsToSearch[hint] == indToFind, then the hint is +/// correct. The hint is ignored if it is out of range (that is, +/// greater than or equal to the number of entries in the given +/// row). +/// \param isSorted [in] Whether the input array of indices to search +/// is sorted in increasing order. +/// +/// The hint optimizes for the case of calling this method several +/// times with the same sparse graph / matrix row, when several index +/// inputs occur in consecutive sequence. This may occur (for +/// example) when there are multiple degrees of freedom per mesh +/// point, and users are handling the assignment of degrees of freedom +/// to global indices manually (rather than letting some other class +/// take care of it). In that case, users might choose to assign the +/// degrees of freedom for a mesh point to consecutive global indices. +/// Epetra implements the hint for this reason. +/// +/// The hint only costs two comparisons (one to check range, and the +/// other to see if the hint was correct), and it can save searching +/// for the indices (which may take a lot more than two comparisons). +/// +/// \note To implementers: We put \c indsToSearch before \c indToFind +/// so that we can derive the type of indToFind directly from that +/// of each entry of \c indsToSearch, without needing +/// \c IndexViewType to be a Kokkos::View. Thankfully, arguments to +/// a C++ function behave more like LET* than LET (in ANSI Common +/// Lisp terms). +template +KOKKOS_INLINE_FUNCTION OffsetType +findRelOffset (const IndexViewType& indsToSearch, + const OffsetType numEnt, + /* typename IndexViewType::const_value_type */ + const typename std::decay::type indToFind, + const OffsetType hint, + const bool /* isSorted */) +{ + // IndexViewType doesn't have to be a Kokkos::View; it just has to + // implement operator[] like a 1-D array. + // + // static_assert (Kokkos::is_view::value, + // "IndexViewType must be a Kokkos::View"); + // static_assert (static_cast (IndexViewType::rank) == 1, + // "IndexViewType must be a rank-1 Kokkos::View"); + static_assert (std::is_integral::value, + "OffsetType must be an integer."); + + if (hint < numEnt && indsToSearch[hint] == indToFind) { + return hint; // hint was correct + } + + // Start with simple linear search for now. + for (OffsetType k = 0; k < numEnt; ++k) { + if (indsToSearch[k] == indToFind) { + return k; + } + } + return numEnt; // "end of sequence" +} + +} // namespace Details + //---------------------------------------------------------------------------- template< class StaticCrsGraphType , class InputSizeType > -- 2.5.4 (Apple Git-61)