В документации Intel-TBB (функция parallel_scan) есть этот серийный код и пояснение:
Например, если × - сложение, параллельный префикс соответствует
промежуточная сумма Последовательная реализация параллельного префикса:
T temp = id×;
for( int i=1; i<=n; ++i ) {
temp = temp × z[i];
y[i] = temp;
}
Параллельный префикс выполняет это параллельно, повторно связывая
применение × и использование двух проходов. Может вызывать × до двух раз
много раз, как алгоритм последовательного префикса. Хотя это делает больше
работать, учитывая правильный размер зерна, параллельный алгоритм может выиграть
последовательный, потому что он распределяет работу по нескольким
аппаратные темы. Чтобы получить приличное ускорение, системы с более чем двумя
рекомендуются ядра.
Может кто-нибудь объяснить, КАК мы можем добиться ускорения с помощью последовательного кода, подобного упомянутому выше? И какое ускорение дает этот подход? есть ли предел этому?