負荷分散問題を扱う場合、多くのデータセグメントを再平坦化する必要があり、前置和を計算することがデータを平坦化する効率的な方法であることが多いからです。プリフィックスサムの計算は、例えば並列ベースソートで使用されます。ここでは、シングルスレッド環境での直列プレフィックスサム計算を初めて紹介します。
1.直列プリフィックス和の計算
S[k] = a[0] + a[1] + ... + a[k] のような級数 a[n] が与えられると，級数 S[k] は級数 a[n] の前和です．+ a[k]であるとき，系列 S[k] は系列 a[n] の前和です．例えば、次の列のデータ：
/** 直列プリフィックス和計算機能
@param T * pInput - 入力データ
@param T *pOutput - 出力データ
@param int nLen - 入力データ長
@return void -
*/
template <class T>
void Sequential_PrefixSum(T * pInput, T *pOutput, int nLen)
{
int i;
pOutput[0] = pInput[0];
for ( i = 1; i < nLen; i++ )
{
pOutput[i] = pInput[i] + pOutput[i-1];
}
}
2.並列プレフィックス和の計算
#define MIN_PRARLLEL_PREFIXSUM_COUNT 8192
/** 並列プレフィックス和計算機能
@param T * pInput - 入力データ
@param T *pOutput - 出力データ
@param int nLen - 入力データ長
@return void -
*/
template<class T>
void Parallel_PrefixSum(T * pInput, T *pOutput, int nLen)
{
int i;
int nCore = omp_get_num_procs();
if ( nCore < 4 || nLen < MIN_PRARLLEL_PREFIXSUM_COUNT )
{
Sequential_PrefixSum(pInput, pOutput, nLen);
return;
}
int nStep = nLen / nCore;
if ( nStep * nCore < nLen )
{
nStep += 1;
}
#pragma omp parallel for num_threads(nCore)
for ( i = 0; i < nCore; i++ )
{
int k;
int nStart = i * nStep;
int nEnd = (i+1) * nStep;
if ( nEnd > nLen )
{
nEnd = nLen;
}
pOutput[nStart] = pInput[nStart];
for ( k = nStart+1; k < nEnd; k++ )
{
pOutput[k] = pInput[k] + pOutput[k-1];
}
}
for ( i = 2; i < nCore; i++ )
{
pOutput[i * nStep - 1] += pOutput[(i-1) * nStep - 1];
}
pOutput[nLen-1] += pOutput[(nCore-1)*nStep - 1];
#pragma omp parallel for num_threads(nCore-1)
for ( i = 1; i < nCore; i++ )
{
int k;
int nStart = i * nStep;
int nEnd = (i+1) * nStep - 1;
if ( nEnd >= nLen )
{
nEnd = nLen - 1;
}
for ( k = nStart; k < nEnd; k++ )
{
pOutput[k] += pOutput[nStart-1];
}
}
return;
}
