Шаблоны структурного параллельного программирования презентация

Размытие
{ 1/9, 1/9, 1/9,
1/9, 1/9, 1/9,
1/9, 1/9, 1/9 };

Выделение границ
{ 0, -1, 0,
-1, 4, -1,
0, -1, 0 };

Увеличение четкости
{ 0, -1, 0,
-1, 5, -1,
0, -1, 0 };

"Lady Agnew of Lochnaw," by John Singer Sargent

Объем данных большой
Строка не помещается в кэш полностью
Разбиение на блоки по столбцам
Ширина столбца кратна строке кэша
Нет ложного разделения
Нужные данные всегда в кэше
Реализация:
Cilk plus – автоматически при векторной нотации
TBB: affinity_partitioner

Свертка блоков

Сцепление блоков (результат не детерминирован)

using namespace tbb;

class Body { T sum; T* const y; const T* const z;
public:
Body( T y_[], const T z_[] ) : sum(0), z(z_), y(y_) {}
T get_sum() const {return sum;}

template
void operator()( const blocked_range& r, Tag ) {
T temp = sum;
for( int i=r.begin(); i temp = temp + z[i];
if( Tag::is_final_scan() )
y[i] = temp;
}
sum = temp;
}
Body( Body& b, split ) : z(b.z), y(b.y), sum(0) {}
void reverse_join( Body& a ) { sum = a.sum + sum;}
void assign( Body& b ) {sum = b.sum;}
};

float DoParallelScan( T y[], const T z[], int n ) {
Body body(y,z);
parallel_scan( blocked_range(0,n), body );
return body.get_sum();
}

Возможные результаты Scatter

Gather

Pack

Unpack

Zip

Unzip