並列計算の虚と実
茨木俊秀
川|川
11 川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川11l川
111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11I川
川lIi川
11 ill
川
1目川
11111
附
1111
川
l川
川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
111111111
川
川
11川
11川
11川
11川
1111111
川
川
11川
11川
11川
1111111
川
川
11川
11川
11l川
111
川
川
11川
11川
11川
11川
11川
111
l

1.

これに対し.

並列化の時代"、かに大きな値であっても，それに見合うだけのプロセッサを準備し並列化すれば対抗できると“.;)Þ-列"や“分散"が情報科学のキーワードとなって考える人がし、る.本当にそうだろうか . n=11 のとき，久しい.情報処理学会や電子情報通信学会などの研究発(n-I)! は 3.6X 10 6 程度であるからつのプロセッサ表をのぞくと，かなりの割合がこれらの話題に関連するで間に合う.そこで 10000 台のプロセッサを準備して並ものであるし，OR 学会の発表でも決してめずらしくな列に処理してみよう.計算量は 3.6X 10 10 ほどに増加す

い.スーパーコンピュータと L 、う名称で(限定された形るが，これは 14! より少ない.つまり 10000 台のプロセではあるが)並列処理が身近なものとなっており，本格ッサで n=11 から n=15 まで拡大できるにすぎない.

的な並列マシンも，あとで述べるように，大学の研究室L 、や 10000 台では少ないという意見もあろう.人間のから容易にアクセスできるようになってきている.最近

脳には約 10 10 個のユユーロンがあるといわれているのでは，で，このオーダーのプロセッサを用いてみよう.その結コネクションマシンなど，数万台のプロセッサをもっ並列マシンが商品化されており[1 ，2J , 通産省の果は ，3.6x1
06x1010<{
19!，つまりようやくn=20 程

次の大型プロジェクトである“新情報処理技術"は百万度である.この簡単な考察からも，プロセッサ台数の増のオーダーのプロセッサを念頭においたものであるとい加が決して本質点な解決にはならないことがわかる.

う.まさに並列化の時代である，

これに対し，巡回セールスマン問題の数学的性質にもこの状況を反映して，並列化によってすべての問題をとづくアルゴリズムでは，たとえば最近注目を集めてい解決できると L 、う素朴な信仰が流布しているかにみえる多面体アプローチによるとる.しかし，これは間違っている.並列化にも，アルゴ合を(逐次計算で)厳密に解くことに成功している.すn が数百，数千という場リズムと物理的実現性の観点からおのずと限界があるとなわち，並列化では越せない壁を巧妙なアルゴリズムをいう事実を認識することは重要である.限界を知っては考案することで突破しているのである.

じめて可能性を正確に把撞できるからである.

それでは並列化による高速化は意味がないのかと関わ

以下，並列計算の虚と実と L 、ぅ形で，この限界を私なりに説明してみたい.

2.

れると，それも正しくない.時間量が n ， nlogn , n 2 ,…

程度の高速アルゴリズムをもっ問題に対しては，並列化並列化は計算量の壁を超えるか?

計算最の意味で困難な問題の例として，よく知られた巡回セールスマン問題を考えてみよう

n 個の点をまわはきわめて効果的である.たとえば ，n=106 のときnlogn=6xl0 6ッサで処理できるとするとたとしても ，nlog
lon ならば，であるので l 台のプロセn がこの 100 倍がになっnlogn=8x10 8 であるから，プロセッ+る巡回路の中で最短のものを求める問題である.これを100 台で対応できる.論理上，時間量が入力データ長 n解くには，巡回路は節点 1 から始まるとして一般性を失の多項式オーダーであるような(逐次)アルゴリズムをわな L 、から，残りの n-I 点について (n-I )!個のすべてもっこれらの問題のクラスを P と記している.幸 L 、，世の順列を調べ，最短のものを残せばよい.しかし，このの中には，実用上重要でしかもクラス P に属する問題が方法の難点は，結構たくさんあることがわかっている.

個数 (n-I )!が急速に大きくなり，すぐグラフの最小に手に負えなくなるとし、う“組合せ的爆発"を生ずると木，最短路，最大フロー，最小コストコロー，さらに線ころにある.

形計画問題などが代表例である.

L 、ばらきとしひで京都大学工学部数理工学科〒 606 京都市左京区吉田本町
1992 年 8 月号

3. どんな問題も並列化できるか?
上の議論では ，p 台のプロセッサを用いると計算時間© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(5) 3
59

1=3t=2t=1

図 2

図 1

PRAMが 1/ρ に短縮されると仮定していたふしがある.

…XXa

くないプロセッサ数 j ，時間量 O((logN) 川は「非常しかし，複数台のプロセツザを協力させて効率よく解を求めるのは決して容易ではない.これまでの経験から，逐次アルゴリズムの中で並列化できるところは並列化するという消極的な方法では，ある程度以上の効果は期待できないことがわかっている.やはり，並列処理に合った新しい並列向きアルゴリズムが必要である.に早 L 、」ことの理論的表現である.

先の， r すべての問題は並列化できるか」という問い
は，r すべての問題はクラス NC に属すか」と言 L 、かえることができる.そこでまず，列アルゴリズムを見出すことができるだろうか.答はやはり否である.以下，そのような並列化にむかない問題

跡すると。(( logN)k')O(Nk) 三 O(Nk+l) ，つまり，多項式オーダーの逐次計算で実行できるからである.これより，NC~Pを得る.しかし，並列計算を理論的に扱う時，計算モデルとして図 1 のPRAM(parallel randomaccess machine) を用い

P がきわめて多様な問題を含んでいることから，そのすべてが並列化に向いているわけではな

L、，つまりNC*Pることが多い [3 ]. すなわち p 台の並列プロセツサは共通のクロックによって同期的に動作し，共有メモリを介して自由にいつでもデータを交換することができる.
たとえば p 個の数字 Ii ， i=1 ， 2 ，… ， p の積を求めると L 、う計算を次のように実行できる.

引をプロセッサに受け持たせ，時刻 t=I ， 2 ， …にO(Nk)

個ある全プロセッサの動作を逐次的に 1 ステップずつ追を理論的に示す手段が築かれつつあることを紹介してみよう.

AeNC であるためにはAeP でなければならないことに注意しよう .

それでは，どのような問題でも工夫すれば効果的な並PRAM によれば，XIXX2Xと予想されている(この予想は有名な P*NP 予想とともに未解決である).

これが正しいとすれば，クラス Pの中で最も難しい問題は NC に属さない(つまり並列化に向かな L 、)ことになる.

い説明は略すが)そのような問題は，(詳しP 完全問題と呼ばれ，多数存在することが明らかにされてきている.

Xi!=XiX Xi+2 ト 1とすれば，図 2 に示すように，時刻 t=[log2p] のとき，

クラス NC の問題と P 完全問題の違いをみるため，次のグラフ問題を考えよう.

Xl に全 Xj の積が入る.
この並列計算の時間量は台のプロセッサのみを用極大独立集合いたときの時間量 P の l/p までには至っていないが，入力:グラフ G=(V ， E).

それに近い効果が得られている.このように(非常に)効出力 :G の極大独立集合を 1 つ.

率よい並列アルゴリズムをもっ問題を示すため，クラス

ただし，節点集合 W~V が独立であるとは ， u , veW

NC(Nick'sclass , Nick はこの分野の研究者 Pippen­を満たす枝 (u ， v) eE が存在しないことをいう.独立集ger の第 1 名)が次のように定義されている.
問題 A の入力データ長がN であるような任意の問題例

に対して，プロセツサ数 p=O(Nk) (k は定数)をもっ PRAM によって，常に時間量 O( (logN)k') (k'も定数)で解を求めることができるならば， A はクラ

ところで，この問題は，次の欲張りアルゴリズムによって簡単に解くことができ，明らかに P に属す.
ステップ o (初期解い適当な節点 v を l つ選び， 1:={v}ス NC に属するという.

多項式オーダーのプロセッサ数 O(Nk) は「あまり多380 (6)合 W はそれを真に含む独立集合 W' が存在しないとき極大である.とする .

ステップ kk:=1.
( 反復 ):ueV-I で I 内のどの節点とも© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ接続しないものがあれば，その 1 つ u を任意に選び.

1:lU{u }, k:==k+1 としてステップ k へ戻る.そのような

P: プロセッサu がなければ終了. 1 は位数 h の極大独立集合である.口M: メモリ

この問題は，さらに NC にも属している.そのための詳しい説明は略すが，ステップ h の u の選択を並列に行ない，複数の独立節点をいちどにみつけ 11こ追加することで，反復回数を (log n)k 1 に抑えることができるというのがポイントである.

条件を付すと事情は異なってくる.節点集合 V={V t，の任意の独立集合 1= {vi 1> 叫2. …. v
itl(一般性を失なうことなくむくらく…くらとする)を文字系列

I=i1i.
.
ik2.

すなわち PRAM では任意の時刻に任意の個数のプロセるが，この機能を物理的に実現することは困難である.
すなわち，データを送るには線を張らねばならず，その場所とそこから通るためにかかる時間が必要である.このため，たとえば単一パス結合による共有メモリの実現法では，十数台のプロセッ+が限度とされている.とみなすとき，辞書式順序で先頭にくる極大独立集合を求める問題である.

より多くの並列プロセツザをもっシステムを実現するには，メモリを各プロセッ+に分散することが不可避でこの問題を解くには，逐次計算ならば，上の欲張り法のアルゴリズムを少し修正し，ステップ O の u を引に，ステップ h の u を条件を満たすものの中で最小の添字 iをもっ刊とするだけでよい.

メモリの分散による実現

ツサが共有メモリを介してデータを交換できるとしていしかし，独立集会に対し，さらに辞書式に先頭というV2 , …. v ，，}

図 S

これも P にしたがって，属す問題である.

あろう.つまり，図 3 のように，各プロセッサに局所メモリをもたせ，それらを相互結合網で結びつける方式が考えられる.相互結合網の具体的な形は

2 次元あるい

は 3 次元の格子，ハイパーキュープ，クロスパー，多段結合，木結合，その他数多くのアイデアがあり [1 ， 4J.

しかし，この計算を並列化して，いちどにたくさんの独立節点を求めようとしても，辞書式に先頭であることを保証するには，各要素列 j の添字を Vj1.列島… . Vij‑l

商品化されているものもある.
さらに，これら多数のプロセッサをどのように制御するかについては，

図 4 の SIMD

(singleinstructionを知った上で決定しなければならず，逐次的条件が介入multiplestream/multipledatastream) と MIMD (してきてしまう.実際，この問題は P 完全であることがinstructionstream/multipledatastream) に大別さ知られているー

れる.前者は I つの制御部ですべてのプロセッサを制御

クラス NC の代表的な問題には，数の整列，最小木問題，最短路問題などがある.これに対し，する方式で，全プロセッサは同ーの(あるいは若干の修P 完全問題の飾を加えた)演算を一斉に実行する.もちろん，各プロリストには，最大フロー問題，線形計画問題などが含ま

セッサは自己のデータに対してその演算を実行し，そのれている [3 ，4J.

結果を相互結合網を通して交換できるので，全体として4. 並列アルゴリズムはそのまま実現できるか?

有機的にまとまった計算を実現できる.これに対し後者
は，プロセッサごとに制御部をもち互いに独立に演算を実行する.したがってつのノード(プロセッサ，メPRAM 上の並列アルゴリズムとそれに関する理論的性質をそのまま現実の並列アルゴリズムにあてはめることは許されるだろうか.

モリ，制御部を合わせたもの)が複雑になると L 、う欠点はあるが，汎用性はずっと高い.
これらのモデルは，理論モデルである PRAM を物理そのプロ的に可能な形で実現するための妥協の産物であるといっ

セツサ台数 P を P=Nk のように自由に置くことができてよい.しかし，その結果，データの分散保持，相互通る.

信，各プロセッサの制御(つまりプログラム)など細部

まず，PRAM は理論モデルであるから，さらにN→∞の場合の挙動を問題にすることすらある.当然ある程度の有限の P しか実現できない現実の設定が複雑になる.つまり，のコンピュータとの閑にギャップがある.

並列アルゴ担ズムと比べると，データの相互通信と全プ

もう 1 つの問題点は，プロセッ+間およびプロセッサとメモリの問のデータ通信であって，より深刻である.
1992 年 8 月号

PRAM 上での概念的なロセッサの制御に整合性をもたせるための無駄(オーバヘッド)が生じる.その結果.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

PRAM 上で得られてい(7) 381の構造を意識する必要はほとんどない.

計算実験の 1 っとして，町田君の卒業研究[ラ]の一部を紹介する.研究指導は福島雅夫先生が行なったので当然非線形計厨であって，目的関数 L: 7=1{+XJG内 +hJ Xj}→最小制約条件 L: 7=la[jXj+bj::;;0 ， i=I , 2 , …, m(a) SIMD

XjER d.,j=I , 2 , …, mと L 、う分離形 2 次計商問題を対象としている.各 Xj はd 次元の変数ベクトルであり，目的関数は dxd 正定行

列 G j で定まる分離形 2 次関数 ，h j , aij , b j は係数ベクトルである.

この問題に文献 [6J のアルゴリズムを適用したわけであるが，ここでは計算結果のみを示す.

図 5 は上のm=2 , d=5 の場合の問題例をランダムに発生し，いろいろな n に対する結果をプロットしたものである.図の(b) MIMD
図 42 つの制御方式 (C は制御部を示す)た並列化によるスピード向上比がそのまま実現される保実現比は ADENA による計算時間と，同じ計算を 1 台のプロセッサで行なった場合の計算時間の比，つまり，速度比を示している.最高で、 80近い実現比が得られている.これは ADENA のプロセッサ数256 に比べると 1/3証はない.
もちろん，PRAM を想定した並列アルゴリズムが無弱で小さいようにもみえるが，アルゴリズムに自体逐次意味であるわけではない.モデルが単純であるだけ並列的な部分が含まれているために，計算の本質的な部分を把握しやす L 、からである.そのあ本質的に不可能である.とのチューエングの作業を容易にするため，並列コンピュータのアーキテクチャとプログラム言語を工夫して，256 まで上げることはこの点を明確にするため，図ラにはこのアルゴリズムの並列計算の部分が理想的に行なわれるとした場合の速個々のマシンの構造や特性を意識せずにプログラムして度比を理論比として示している.理論比はn が 256 のも，オーパヘッドを大きくしないよう，地道な努力が払倍数近くで最も大きく 160 程度になるが256 よりはかわれている.これら，ハードとソフトの両面の現状につなり小さい.この理論比と実現比の問にはまだ約 2 倍の違いがあるが，いては，文献[ 2]などに詳しい.

5. 数理計画の例からこれが物理的に実現された ADENA の(倍)160
並列計算が理論だけのものでも対岸のものでもないことを理解していただくには，“われわれの研究室でも"並列コンピュータを用いて計算を行なっていることを伝120えるだけで十分であろう.じつは，われわれの数理工学教室には，野木達夫先生と松下電器の共同開発になるADENA が設置しであり，ネットワークを通して自由に80アクセスできる. ADENA は 256個のプロセッサをもっMIMD タイプのマシンで，偏微分方程式などに生じる配列で効率よく処理できるよう，相互結合網の構成に特40殊的な工夫がこらされている(詳しくは，文献 [2J 中の解説記事参照).われわれユーザは FORTRAN の拡張である ADETRAN( これは ADENA を SIMD 的に動作させている)を用いてプログラムでき，382 (8)ADENA。

100

図 5© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

200 300 400500
並列計算による速度比
オベレーションズ・リサーチオーパヘッドと解釈できる量である.他の並列コンピュータとの比較を行なったわけではないが，この程度のオーノミヘッドで済むのはかなりよい結果だと考えている.

6.

むすび

9 月号/18 日発売/定価 930 円

並列計算について日頃感じていることをわかりやすく説明したつもりであるが，どの程度成功しただろうか.
要点をキャッチフレーズ的にまとめると次のようになろ

lexと yacc-字句・構文解析・コンパイラ

う.

・並列化しても難しい問題はやはり難しい.

・ I ex.yacc

・しかし，やさしい問題はもっとやさしくなる.

・応用プログラミング

・並列コンピュータには並列j 向きのアルゴリズムを.

<連載>.並列化に向く問題とそうでない問題がある.
・理論と現実のギャップはまだ大きい.しかし，近づきつつある.

高尾直弥
鹿瀬通孝

texinfo 入門

ヒューマ ν インタフェースを採る
証明とプログラムと萩谷昌己

遺伝的アルゴリズム

和田健之介

・並列計算はすでに現実である.

るわけでもない.アルゴリズムをこれまでの逐次的な観決定版DynaBook活用法

点ではなく並列化という方向から眺めると，それまで気定価 2884 円

私は決して並列計算の専門家ではないが，無視していづかなかった新しい発見に出会 L 、，新鮮な驚きを感じる
ことヵ:しは:し tまある.

幸い本特集には並列アルゴリズムをさまざまな観点から扱った興味深い記事が集められているので，読者の方

8 月号/発売中/定価 980 円々もぜひこの新しいおもしろさに触れていただきたい.

パターン形成参三考文献

自然のアラベスク[1] 富田真治，末吉敏則，並列処理マシン，電子情報通信学会編，オーム社，

1989.

[2] 特集:超並列マシンとその応用，情報処理， Vol.
32 , No.4,

パターンと人間高木隆司

熱力学とパターン形成

沢田康次

振動反応の動的パターン

吉川研一

パターン形成とかたちIJ¥
JII 泰

コウジカピコロニーの成長形態宮島佐介・松浦執1991 年 4 月.

[3] A. Gibbonsand W. Rytter , E 白icient Paraｭ

形の進化を考える本多久夫

生体膜のパターン形成

関村利朗

llel Algorithms , Cambridge University Press ,生物リズムに現れるパターン

本間研一

Cambridge , 1
988.

沸騰のパターン

柳田達雄[4] 茨木俊秀，アルゴリズムと離散最適化，応用数学講座，岩波書店(近日出版).

[5] 町田直樹，分離可能な凸計画問題に対する交互方向乗数法の並列計算，京都大学工学部数理工学教室特別研究報告書，

tingdirectio
nmethodo
fmultiplier
stoseparaｭble convex programming problems , Computaｭ
tional Optimization and Applications (掲載予1992 年 8 月号

三村畠泰

結晶成長におけるパターン形成

小林亮

形の物理学

小野健一

“進化"を生成する自己言及システム郡司ベギオ=幸夫

コンビュータ

古舘毎週恥準品店主ト

サイエンスのための同区nA耳、すー1992.

[6] M.Fukushima , Applicationo
f the alternaｭ定).

界面のダイナミクス

守屋悦郎著/A5/定価 2472 円
酔価格表示は，税込み価格となっています.

サイエンス社
東京都千代田区神田須田町2-4 安部徳ビル
電話 (03) 3256‑1091(代)振替東京 7 ‑2387© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(9) 363