Parallelism In The SeqAn Library: 1D Load Balancing With Divide & Conquer: Conceptual Draft

Related to 1DLoadBalancingConceptualDraft. This part looks at the divide & conquer paradigm in [Näher, 2009].

Important caveat: since D&C uses progressive splitting of tasks into sub-tasks, and since merging is an essential step of D&C, it makes no sense to start with N algorithm states.

Instead, this schedule should start with a single algorithm state and a single data specification, and progressively splitting and subsequently merging them.

Interface Description

template <typename TSpec>
struct DivideAndConquer;

template <typename TString, typename TSpec>
struct DataSpec<Independent1D<TString, DivideAndConquer<TSpec> > > :
    DataSpec<Independent1D<TString, void> >
{
    typedef DataSpec<Independent1D<TString, void> > TBase;
    typedef typename Iterator<TBase>::Type TIterator;
};

template <typename TString, typename TSpec>
inline void
split(
    String<DataSpec<Independent1D<TString, DivideAndConquer<TSpec> > > >& specs,
    DataSpec<Independent1D<TString, DivideAndConquer<TSpec> > > const& spec
);

template <typename TString, typename TSpec, typename TDataSpec>
inline void
split(
    String<AlgorithmState<TSpec> >& states,
    AlgorithmState<TSpec> const& state,
    DataSpec<TDataSpec> const& spec
);

template <typename TString, typename TSpec>
inline void
merge(
    DataSpec<Independent1D<TString, DivideAndConquer<TSpec> > >& spec,
    String<DataSpec<Independent1D<TString, DivideAndConquer<TSpec> > > > const& specs
);

template <typename TString, typename TSpec>
inline void
merge(
    AlgorithmState<TSpec>& state,
    String<AlgorithmState<TSpec> > const& states
);

template <typename TString, typename TSpec>
inline bool
isLeaf(
    DataSpec<Independent1D<TString, DivideAndConquer<TSpec> > > const& spec
);