木上の関数の簡単な並列計算アルゴリズム

摘要

本論文は．n節点の根付き木で定義される関数を計算する問題を扱う．具体的には．f(v)＝w(v)×(?_(u∈S(v)) f(u)) で定義される関数の，木の根rでの値f(r)を求める（S(v)は節点vの子の集合を表す．）．本論文は，この関数をpプロセッサのEREW-PRAMモデルでO（n/p＋log^2 p）時間で計算するアルゴリズムを提案する．演算子×と?は次の条件を満たすとする：×は結合的で，?に対して左分配的であり，?は結合的である．もし×が逆元を持つなら（つまり×が群を成すなら），時間計算量はO（n/p+log p）に改善される．このアルゴリズムは省メモリである．節点の重みu（v）がkビットで表現され，関数の値がWビットで表現されるとすると，このアルゴリズムは木を格納するために2（k+1）nビットを用い，関数の計算を行う際の作業領域はO（p（W+log n））ビットである．単純さとメモリ効率の良さから，このアルゴリズムはGPGPUに適している．