Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-14 04:31:15

At Wed, 13 Oct 2010 16:39:18 -0700,
Smith, Jacob N wrote:

> I've only had a chance to read the Austern paper "Segmented
> Iterators and Hierarchical Algorithms" once. I agree that the
> segmented iterators are rather appealing as an interface to
> packs-of-pods-datatype. However, I'm not sure the conceptual
> interface to segmented iterators are rich enough. Luke Simonson has
> more experience with the construction of an iterator pattern around
> SIMDs used in a high-performance system than I do. However I seem I
> to remember that the pattern for SIMD iteration always looked like
> this:
> 
> Loop A?
> Loop B*
> Loop C?
> 
> Where Loops A & C handle the unaligned start/end (if they exist) and
> Loop B* handles (0 or more of) the aligned packs of the
> sequence. Handling the edge-cases for A & C were definitely not the
> same --- there are memory exceptions that can occur at the
> end-of-range for Loop C that can't (or usually don't) occur for Loop
> A when doing unaligned loads/stores. I seem to remember that it was
> insufficient to just mark "not Loop B" but it was necessary to
> explicitly mark foreach operations as "Loop A" vs. "Loop C". It
> seems that this division of Loop A/B/C will need to be exposed
> through the iterator.

I think you should read the paper again and look at the implementation
of one of the algorithms there.  They all have that structure.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com