// Copyright (C) 2005-2006 Douglas Gregor <doug.gregor@gmail.com>. | |
// Copyright (C) 2004 The Trustees of Indiana University | |
// Use, modification and distribution is subject to the Boost Software | |
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
// Authors: Douglas Gregor | |
// Andrew Lumsdaine | |
// Message Passing Interface 1.1 -- Section 4.9.1. Scan | |
#ifndef BOOST_MPI_SCAN_HPP | |
#define BOOST_MPI_SCAN_HPP | |
#include <boost/mpi/exception.hpp> | |
#include <boost/mpi/datatype.hpp> | |
// For (de-)serializing sends and receives | |
#include <boost/mpi/packed_oarchive.hpp> | |
#include <boost/mpi/packed_iarchive.hpp> | |
// For packed_[io]archive sends and receives | |
#include <boost/mpi/detail/point_to_point.hpp> | |
#include <boost/mpi/communicator.hpp> | |
#include <boost/mpi/environment.hpp> | |
#include <boost/mpi/detail/computation_tree.hpp> | |
#include <boost/mpi/operations.hpp> | |
#include <algorithm> | |
#include <exception> | |
#include <boost/assert.hpp> | |
namespace boost { namespace mpi { | |
/************************************************************************ | |
* Implementation details * | |
************************************************************************/ | |
namespace detail { | |
/********************************************************************** | |
* Simple prefix reduction with MPI_Scan * | |
**********************************************************************/ | |
// We are performing prefix reduction for a type that has an | |
// associated MPI datatype and operation, so we'll use MPI_Scan | |
// directly. | |
template<typename T, typename Op> | |
void | |
scan_impl(const communicator& comm, const T* in_values, int n, T* out_values, | |
Op op, mpl::true_ /*is_mpi_op*/, mpl::true_ /*is_mpi_datatype*/) | |
{ | |
BOOST_MPI_CHECK_RESULT(MPI_Scan, | |
(const_cast<T*>(in_values), out_values, n, | |
boost::mpi::get_mpi_datatype<T>(*in_values), | |
(is_mpi_op<Op, T>::op()), comm)); | |
} | |
/********************************************************************** | |
* User-defined prefix reduction with MPI_Scan * | |
**********************************************************************/ | |
// We are performing prefix reduction for a type that has an | |
// associated MPI datatype but with a custom operation. We'll use | |
// MPI_Scan directly, but we'll need to create an MPI_Op manually. | |
template<typename T, typename Op> | |
void | |
scan_impl(const communicator& comm, const T* in_values, int n, T* out_values, | |
Op op, mpl::false_ /*is_mpi_op*/, mpl::true_ /*is_mpi_datatype*/) | |
{ | |
user_op<Op, T> mpi_op(op); | |
BOOST_MPI_CHECK_RESULT(MPI_Scan, | |
(const_cast<T*>(in_values), out_values, n, | |
boost::mpi::get_mpi_datatype<T>(*in_values), | |
mpi_op.get_mpi_op(), comm)); | |
} | |
/********************************************************************** | |
* User-defined, tree-based reduction for non-MPI data types * | |
**********************************************************************/ | |
template<typename T, typename Op> | |
void | |
upper_lower_scan(const communicator& comm, const T* in_values, int n, | |
T* out_values, Op& op, int lower, int upper) | |
{ | |
int tag = environment::collectives_tag(); | |
int rank = comm.rank(); | |
if (lower + 1 == upper) { | |
std::copy(in_values, in_values + n, out_values); | |
} else { | |
int middle = (lower + upper) / 2; | |
if (rank < middle) { | |
// Lower half | |
upper_lower_scan(comm, in_values, n, out_values, op, lower, middle); | |
// If we're the last process in the lower half, send our values | |
// to everyone in the upper half. | |
if (rank == middle - 1) { | |
packed_oarchive oa(comm); | |
for (int i = 0; i < n; ++i) | |
oa << out_values[i]; | |
for (int p = middle; p < upper; ++p) | |
comm.send(p, tag, oa); | |
} | |
} else { | |
// Upper half | |
upper_lower_scan(comm, in_values, n, out_values, op, middle, upper); | |
// Receive value from the last process in the lower half. | |
packed_iarchive ia(comm); | |
comm.recv(middle - 1, tag, ia); | |
// Combine value that came from the left with our value | |
T left_value; | |
for (int i = 0; i < n; ++i) | |
{ | |
ia >> left_value; | |
out_values[i] = op(left_value, out_values[i]); | |
} | |
} | |
} | |
} | |
// We are performing prefix reduction for a type that has no | |
// associated MPI datatype and operation, so we'll use a simple | |
// upper/lower algorithm. | |
template<typename T, typename Op> | |
inline void | |
scan_impl(const communicator& comm, const T* in_values, int n, T* out_values, | |
Op op, mpl::false_ /*is_mpi_op*/, mpl::false_/*is_mpi_datatype*/) | |
{ | |
upper_lower_scan(comm, in_values, n, out_values, op, 0, comm.size()); | |
} | |
} // end namespace detail | |
template<typename T, typename Op> | |
inline void | |
scan(const communicator& comm, const T& in_value, T& out_value, Op op) | |
{ | |
detail::scan_impl(comm, &in_value, 1, &out_value, op, | |
is_mpi_op<Op, T>(), is_mpi_datatype<T>()); | |
} | |
template<typename T, typename Op> | |
inline void | |
scan(const communicator& comm, const T* in_values, int n, T* out_values, Op op) | |
{ | |
detail::scan_impl(comm, in_values, n, out_values, op, | |
is_mpi_op<Op, T>(), is_mpi_datatype<T>()); | |
} | |
template<typename T, typename Op> | |
inline T | |
scan(const communicator& comm, const T& in_value, Op op) | |
{ | |
T out_value; | |
detail::scan_impl(comm, &in_value, 1, &out_value, op, | |
is_mpi_op<Op, T>(), is_mpi_datatype<T>()); | |
return out_value; | |
} | |
} } // end namespace boost::mpi | |
#endif // BOOST_MPI_SCAN_HPP |