並列計算における時間計算量と通信計算量について

石岡 博  丸岡 章  木村 正行  

誌名
電子情報通信学会論文誌 D   Vol.J68-D   No.11   pp.1810-1819
発行日: 1985/11/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(657.9KB)>>
論文を購入




あらまし: 
この論文では複数個のプロセッサーで実行される並列計算におけるデータの依存関係をグラフとして与えられるものとし,計算時間とプロセッサー間の通信量の間のトレードオフを導く.即ち,グラフとしては,一辺の長さがnd次元格子空間を考え,グラフの頂点はデータの値を,辺はデータの値の間の依存関係を表すものとしたとき,計算時間Tと通信量Cの間にはTCd-1Ωnd2d+1)の関係が成立することを導く.次いでd種類のスケジュール(各プロセッサーが格子空間のどの頂点をいつ計算するか指定するもの)を与え,その中の2種類のスケジュールに対して,TCd-1は上に述べた下界と一致することを導く.最後に,データの依存関係がd次元格子空間で与えられるようなアルゴリズムの例として,d個の記号列の部分並びを求めるアルゴリズムを示す.