.. _Elementwise:
Elementwise
===========
.. container:: section
.. rubric:: Problem
:class: sectiontitle
Initiate similar independent computations across items in a data set,
and wait until all complete.
.. container:: section
.. rubric:: Context
:class: sectiontitle
Many serial algorithms sweep over a set of items and do an
independent computation on each item. However, if some kind of
summary information is collected, use the Reduction pattern instead.
.. container:: section
.. rubric:: Forces
:class: sectiontitle
No information is carried or merged between the computations.
.. container:: section
.. rubric:: Solution
:class: sectiontitle
If the number of items is known in advance, use
``oneapi::tbb::parallel_for``. If not, consider using
``oneapi::tbb::parallel_for_each``.
Use agglomeration if the individual computations are small relative
to scheduler overheads.
If the pattern is followed by a reduction on the same data, consider
doing the element-wise operation as part of the reduction, so that
the combination of the two patterns is accomplished in a single sweep
instead of two sweeps. Doing so may improve performance by reducing
traffic through the memory hierarchy.
.. container:: section
.. rubric:: Example
:class: sectiontitle
Convolution is often used in signal processing. The convolution of a
filter ``c`` and signal ``x`` is computed as:
|image0|
Serial code for this computation might look like:
::
// Assumes c[0..clen-1] and x[1-clen..xlen-1] are defined
for( int i=0; i<xlen+clen-1; ++i ) {
float tmp = 0;
for( int j=0; j<clen; ++j )
tmp += c[j]*x[i-j];
y[i] = tmp;
}
For simplicity, the fragment assumes that ``x`` is a pointer into an
array padded with zeros such that ``x[k]``\ returns zero when ``k<0``
or ``k≥xlen``.
The inner loop does not fit the elementwise pattern, because each
iteration depends on the previous iteration. However, the outer loop
fits the elementwise pattern. It is straightforward to render it
using ``oneapi::tbb::parallel_for`` as shown:
::
oneapi::tbb::parallel_for( 0, xlen+clen-1, [=]( int i ) {
float tmp = 0;
for( int j=0; j<clen; ++j )
tmp += c[j]*x[i-j];
y[i] = tmp;
});
``oneapi::tbb::parallel_for`` does automatic agglomeration by implicitly
using ``oneapi::tbb::auto_partitioner`` in its underlying implementation. If
there is reason to agglomerate explicitly, use the overload of
``oneapi::tbb::parallel_for`` that takes an explicit range argument. The
following shows the example transformed to use the overload.
::
oneapi::tbb::parallel_for(
oneapi::tbb::blocked_range<int>(0,xlen+clen-1,1000),
[=]( oneapi::tbb::blocked_range<int> r ) {
int end = r.end();
for( int i=r.begin(); i!=end; ++i ) {
float tmp = 0;
for( int j=0; j<clen; ++j )
tmp += c[j]*x[i-j];
y[i] = tmp;
}
}
);
.. |image0| image:: Images/image004a.jpg
:width: 99px
:height: 29px
Generated by dwww version 1.15 on Wed May 22 15:47:29 CEST 2024.