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

摘要

本論文は，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）に改善される．このアルゴリズムは省メモリである．節点の重みw（v）がたビットで表現され，関数の値がW ビットで表現されるとすると，このアルゴリズムは木を格納するために2（k＋1）れビットを用い，関数の計算を行う際の作業領域はO（p（W＋log n））ビットである．単純さとメモリ効率の良さから，このアルゴリズムはGPGPU に適している．%We propose a simple parallel algorithm for computing a function defined on a rooted tree with n nodes. Namely, we want to compute the value of a function f(r) for the root node r, defined as f(v) = w(v) ⊕ ( ⊕_(u∈S(v)) f(u)) where S(v) denotes the set of child nodes of the node v. We propose a simple EREW-PRAM algorithm for computing the function in O(n/p + log2 p) time using p processors. We assume that the operators ⊕ and ⊕ satisfy the following: ⊕ is associative, left-distributive over ⊕, and ⊕ is associative. If ⊕ has the inverse (i.e., ⊕ forms a group), the time complexity is improved to O(n/p + log p). Our algorithm is space efficient. If the weight of a node is represented in k bits and the value of the function is represented in W bits, our algorithm uses 2(k + l)n bits to store the tree, and uses O(p(W + log n)) bit working space for computing the function. Because of the simplicity and space-efficiency, the algorithm is suitable for GPGPU.