項式の並列計算について

概要

論文の詳細を見る
In this paper we consider the parallel evaluation of arithmetic expressions of n distinct variables with the addition, subtraction, multiplication and division operations. We first show that any such expression can be evaluated in at most 6「log2n」-3 steps using 6n processors. Second, we show that any continued-parenthesis form of n distinct variables can be evaluated in at most 6「log2n」+1 steps using 2n processors. Third,we show that any polynomial form of n distinct variables can be evaluated in at most log2n+2log2n+O(1)step using n processors. We also deduce some results, ln each of the above cases, which apply when a fixed number of processors are available.
一般社団法人情報処理学会の論文
1973-07-15