インターネットを利用した OR (2)

インターネットを利用 した OR

( 2 )

‑ 並列分散処理について*‑

若 林 信 夫

Abstract

イ ンタ‑ネ ッ トワーク化 されたワークステーションの クラスターは,情報資 源の共有のみな らず,並列分散型の計算処理を可能にす る｡オペ レーションズ

･リサーチ (OR)の問題を解 く上で も,イ ンターネ ッ トを利用 して,ネ ッ ト ワーク化 された情報資源や計算環境を 自由に有効利用す ることが望まれる｡本 稿では,並列計算処理の基礎, ソフ トウェア,オペ レーティングシステムの現 状 に言及 し,ネ ッ トワーク化 された計算環境をより有効 に利用す るためにはど のような工夫が必要であるかを考察す る｡

1

今 日,ネ ッ トワーク,オープ ンシステム,ダウンサイ ジング,マルチメディ アのいわゆる｢ネオダマ｣の勢 いは留まるところを知 らない｡特 に,‑ ‑ ドウェ ア技術の発展 とイ ンターネ ッ トワークの実現によって,研究環境 は劇的に変化

しつつあ る｡前稿 においては,イ ンターネ ッ トワークが OR計算環境 を改善 す る例 と して,電子 メール,ネ ッ トニ ュースの閲覧 ･発信,フ ァイル転送(ftp),

*)本稿は,平成5年夏,米国スタンフォー ド大学OR学科に客員研究員として滞在 中に準備された｡この機会を与えられた小樽商科大学後援会並びにスタンフォー ド 大学OR学科に感謝する｡

〔107〕

108 商 学 討 究 第44巻 第 4号

他 の計算機へのtelnet,rlogin(リモー ト･ログイ ン),データベース検索の 重要性を述べた｡ さらに本稿ではイ ンターネ ッ ト接続のおかげで科学技術の本 来 の計算処理が革新的 に高性能化 され ることを OR計算環境の観点か ら述べ る｡近年,ハ イ ･パ フ ォーマ ンス ･コ ンピューテ ィ ング (HPC)の波 に, OR研究 も好 む と好 まざるとに関わ らず,直面 しているのである｡

イ ンターネ ッ トとは,物理的 には,

LAN

フラス トラクチャとして認識 され るまでにはまだ数年を要す るであろ う｡ 日本 は米国に比べ ると規制緩和が遅れていること,長期的統一的な見通 しに欠 ける ために,10年程遅れているといわれ る^1)｡ 米国では1991年 に成立 したHPC法 に基づ きHPCC (HighPerformanceComputing

&

プ ログラムが推進 されてい る｡ 日本で も1993年,新社会 資本整備政策が立案 された｡わが国で も通信分野 における規制緩和を促進 し,企業間の競争 を活発

表 1:Netfindによ ってサーチ可能な ドメイ ン数 (1992.10) 順位 ドメイ ン名 所属の説明 サ ブ ドメイ ン数

1 edu 米国 .教育 3340

2 COm 米国 .商用 968

3 de ドイツ 836

4 Ca カナダ 603

5 au オース トラ リア 378

6 uk 英国 360 ′

7 jp 日本 350

8 Se スウェーデ ン 263

9 gOV 米国 .政府 248

10 nil 米国 .軍 191

1)南部鶴彦 :日本の電気通信政策を問 う‑21世紀の社会イ ンフラ 高度情報通信ネ ッ トワーク構想のボ トルネック,｢公明｣ 1993 No.381

インターネットを利用 したOR計算環境 の改善(2) 109 にし,高度なサービスの拡大を図ってい くべ きであろう｡ 実際,われわれの周 辺を見て も明 らかであるが, 日本の実情は,表 1がよ く物語 っている｡ 日本の 大部分 は学術機関であるのに対 して,米国は航空会社か らホテルまでイ ンター

ネ ッ ト接続 されはじめている｡

本稿 は,OR計算環境の視点か ら,イ ンターネ ッ トワーク化 されたコンピュー タを用いて問題解決のために並列処理研究の展望を行 う^｡

多 くの社会的な数理モデルは並列的である²⁾｡経済 システム,企業 システ ム,行政 システムか ら,工学,医学 システムに至るまで同時にお互いに交絡 し なが ら進行 している｡フォン ･ノイマ ン型の逐次コンピュータ処理によって も かな りのシミュレー トは可能である｡実際,ほとんどあ らゆるシステムは,逮 次処理である部分 と並列処理の部分の混合である｡いま,オペ レーションズ ･

リサーチの標準的な設定を考えると,準備段階 (問題の設定や,定式化) と実 施の段階は逐次的であるが,解の局面 はしば しば,並列的である｡解の局面に ついては,後に,連立一次方程式の解法の例 と,巡回セールスマ ン問題の例を 使 って説明する｡

並列計算の考 えはChurch‑Turingに遡 ることがで きるはど古 い歴史を も

つ ｡ 並列 コンピュータの教科書 は数十冊以上書かれている^3)｡ 並列 プログラ ムの最初の重要な例は,オペ レーティング ･システムの理論 と実装である｡す なわち,装置の管理 とユーザタスクの実行を並列的に処理で きるように した｡

2)Parallel処理 に対 して,Concurrent処理 という言葉があ るo 日本語では,前者 を並列処理 と訳 し,後者を並行処理 と訳す ことが多 い｡前者 は広義で一般的である のに対 し,後者 は論理的な個別的な場合 に使 う｡

3)最近出版 された並列処理 に関す る教科書 としては,

Kai Hwang, Advanced Computer Architecture with ParallelPr0‑

gramming,McGraw‑Hill,1992.

DavidA.PattersonandJohnL.Hennesy,ComputerOrganization&De‑

sign‑TheHardware/Softwareinterface,MorganKaufmannPub.1993. N.Carriero and D.Gelernter,How to Write ParallelPrograms,A FirstCourse,MIT Press(1990)(村岡訳,並列 プログラムの作 り方,共立 出 版,1993).

がある｡

110 商 学 討 究 第44巻 第 4号

分散型相互排除におけるクリティカル ･リージョンの設定 もそ うである｡並列 用の実験的なプログラム言語 も後にみるように,多数発表 されている｡ 日本の ICOT(新世代開発機構)のメイ ンテーマで もあった｡ ここにきて商用の超並 列 マ シ ン (Massively ParallelMachine)の登場 とイ ンターネ ッ トワー ク を利用 した並列分散処理が クローズア ップ してきた｡特 に,テラデータやタ ン デム, シークェン ト,イ ンテル等の多 くの会社4)が高度並列マ シンを開発 し, それをネ ッ トワーク利用 し,実用に供 してきた｡

並列分散 システムアーキテクチャは,多数のプロセ ッサが相互結合網 (いわ ば,ゲー トウェイ)を通 してメ ッセージを送 ることによってのみ,互 いに通信 す る｡各 メモ リーとディスクがその上のデータのサーバ として働 くプロセ ッサ

によって所有 される｡

並列プロセスを互いに結びつ けるためにメ ッセージベースの クライア ン ト･

サーバ ー型のオペ レーティ ングシステム5)が必要 であ る｡ もちろん, イ ンフ ラとして並列 プロセ ッサを結びつける高速ネ ッ トワークが必要である⁰ ‑イ ･ パ フォーマ ンス (高性能) ･コンピューティングは,伝統的なスーパ ーコ ン

ピ土‑ティングと新たに出現 してきた並列 コンピューティングの両方を意味 し ている｡前者についていえば, 日本のスーパーコンピューティングの現状 は周 知のように, 日本電気,富士通, 日立が しのぎを削 っていて,特 に‑‑ ドウェ

ア技術の粋を実現 している｡単一 プロセ ッサの ピーク ･パ フォーマ ンスは外国 のどのメーカのそれよりも優れている｡ 数値をあげれば, クレイ ･リサーチ社 の最新のスーパーコンピュータ

C1 9 0

1GFLOP

5

8GFLOP

4) TeraData,Tandem,Encore,Intel (iPSC/ 2,Paragon), NCR, nCUBE,Sequent,Thinking Machines,KendallSquare Research, MasPar社であり,日本のメーカーはまだ商用並列コンピューター市場に本格的 に参入 していない｡

5)クライアント･サーバー ･コンピューティングは,アプリケーションを複数のユー ザが共有する部分 (サーバー)と,各ユーザー固有の部分 (クライアント)に分割

して処理を行うことである｡

インターネットを利用 したOR計算環境 の改善(2) 111 フォーマ ンスは実際のパ フォーマ ンスとはかな り異なる｡現実の利用者 はスカ ラー算術や入 出力の,ベ ク トル化 には関係のない演算が大部分であ り,ベ ク ト ル化演算を含む割合 は僅少である｡また, 日本の‑‑ ドウェアは高信頼性があ るが,アプ リケーション ･ソフ トウェアは貧弱であることや, 日本語のマニ ュ アルのわか りに くさも指摘 されている｡ 日本 は総合経済対策の一環 として,19 94年 4月 までに,十数台のスーパーコンピュータ (並列 コンピュータを含む) を購入す ることになっている｡ これを機会 に日本が現在遅れている商用の分散 メモ リ‑並列 コンピュータの研究開発への端緒 になることが期待 されているO

2 並列処理 マシンの基礎知識 2. 1 並列処理 マシンの分類

並列処理マシンは,演算装置を多数並べて仕事を分割 して処理できるように したマシンであ る｡超並列マ シンとか超計算機 と呼ばれ ることもあるが,超 は, massivelyの訳であること,超 は もっと機 の熟 した場合 に使 いたい とい う理 由で以下で は積極的には採用 しない｡並列計算処理を実現す るコンピュータの 分類 は,アーキテ クチ ャ(方式設計)とメモ リーの両方か ら分類 されているが, 以下では, 3つの主要な型 と例をあげる｡

●分散 メモ リー付 きSIMD (Singlelnstruction,MultipleData単一命 令多重データ)

SIMDマ シンの例 は,ThinkingMachines社の CM ‑2 (CM‑はコネ クシ ョン ･マ シンを表す),MasPar社のMP‑2,Wavetracerがある｡

●分散 メモ リー付 きMIMD (Multiplelnstruction,MultipleData多重 命令 ･多重データ)

この例 は,イ ンテルのiPSC/860および,Paragon,ThinkingMachines 社の CM‑5,nCUBE2および各種 の ワー クステーシ ョンのネ ッ トワー クである｡

●共有 メモ リー付 きMIMD

112 商 学 討 究 第44巻 第 4号

この例には, シリコングラフィックスのパ ワーシリーズマシン, コンベ ッ クスのC3,サ ンマイクロのSunSPARCcenter2000がある｡

本稿で関心のある並列マシンは,高価で高度な商用の並列マシンではな く, 分散メモ リー付 きMIMDに属す るネ ッ トワーク化 されたワークステーション 群である｡ネ ッ トワーク接続された複数のワークステーションで並列処理を行

うことによって, 1台の処理性能をはるかに超えた成果が実現す ることが期待 され る｡ しか し,そのためには,並列アルゴリズムと並列処理環境に多 くの課 題がある｡

2. 2 並列アルゴリズムと並列型プログラム言語の問題

並列アルゴリズムは,‑度に複数個の演算を実行す る計算手続 きである｡並 列計算のための適切なモデルは,PRAM (ピーラム) といわれ,逐次アルゴ リズムのRAM (Random‑AccessMachine)を応用 したものである｡ ソー ティングネ ッ トワークや回路問題 に対 して,配列, リス ト,木,グラフを表現 した理論上 の並列マシンを想定 している6)｡ pRAM モデルは,一般 に,共有 メモ リーを もつ密結合のコンピュータを前提に していることに注意する｡並列 マ シンを司 るための OSや言語 は,未成熟 な分野である｡FORTRAN,C, Pascal,APL (J)等のプログラム言語 とライブラ リーが使われている7)0

新 しい並列プログラム言語 としてスタンプオ‑ ド大学のJadeが注 目されてい る｡Jadeは,メ ッセージ ･パ ッシング ･マ シン,共有メモ リ ･マシンおよび 異機種のワークステーション群をサポー トしてお り,Fortran,C,C++ など と結合で きる｡FORTRAN77にベ ク トル化機能をっけ加えた,Fortran90や 並列化機能 を追加 した,High Performance Fortran (HPF)が発 表 さ 6)T.H.Cormen,C.E.LeisersonandR.L Rivest,IntroductiontoAlgo‑

rithms,TheMITPress,1990.,および,脚注13参照｡

7)並列処理の教科書には,FORTRANとCの例が多数見 られる｡Pascalについて は,Portable,ParallelizingPascalCompiler,IEEE Software,1993p.

71‑81,

APL(∫)については,APL93ConferenceProceedings,ACM,1993.を参照｡

インターネットを利用 したOR計算環境の改善(2) 113 れている.例えば,デ‑タベ ク トルAの平均を出す新Fartranには,

AVG‑SUM ( A)/FLOAT( N)

である｡Fortran90コンパイラーのサブセ ッ トは,い くつかの並列マシンでサ ポー トされてい るが,ベ ク トル言語の域 を出ていない｡今 日, スーパ ー コン ピュータはベ ク トル ･コンピュータか ら並列マ シンない し,｢超｣並列マ シン に移行 しているのでそれに合わせたHPFの開発が重要 になっている0 HPF は,米国では,産学の共同プロジェク トとして推進 されている｡

2. 3 並列 マシン環境

並列 マ シン環境の最 も基本 は,｢メ ッセー ジ ･パ ッシング言語｣である｡ こ れは並列実行のためにアプ リケーシ ョンを分解す る方法を与える｡データが分 割 され,他のプロセ ッサにメ ッセージとして渡 され る｡デ‑夕は,圧縮 されデ‑

夕保護機能を付 けて,送出され,受信側 はそのデータを解凍 し,処理を し,そ の結果を再 び,圧縮 して保護機能を付 けて返送す る｡MIMDマ シン上でのプ ログラ ミングモデルには,分散 メモ リー型 と,分散共有 メモ リー型が区別 され る｡分散 メモ リ‑型のメ ッセー ジ ･パ ッシングは,通信 と同期化が基本であ り, クライアン ト･サ‑バ方式や

RPC

いるが論理的には共有で きるデータ空間を通 じて通信 と同期化 を行 う0Sci‑ entificComputing社のLirldaは,分散共有 メモ リーの考えに似た ｢タプル 空間｣を軸 にプロセ ッサー間で情報の交換を行 うソフ トウェアである0Linda

は並列化を与え るために, CとFortranに6つの基本命令を追加 し,タスク を自動的に分配す る.NetworkLindaは,異質の ワークステーションのネ ッ

トワークでの並列化を可能 にす るo

LAN環境 またはイ ンターネ ッ ト環境の簡単 な送受信では,UNIXのrcp, ftpコマ ン ドが有効であるが, さ らに強力な コマ ン ドが用意 されている｡それ

は, イーサ ーネ ッ ト通信 の場合,バ ン ド幅は最大10MByteと比較 的高 いが

TCP

114 商 学 討 究 第44巻 第 4号

た,多端末か らの利用頻度が高い とコ リジ ョンの検知のためにさ らに遅れ る｡

したが って,ネ ッ トワークで実行す る並列 プログラムを作成す るときには通信 の遅れが発生 しない環境を選ぶ ことが重要である｡最近, ワークステーシ ョン 間の通信方式 と して,FDDI(FiberDistributionData∫nterface)に代 ゎ るFDDI2や ATM (AsynchronousTransferMode)の 出現や,バ スの 直接結合 など技術的な側面か ら新機軸が打 ち出されている｡特 に,ATM技術 がサポー トされ るな らば,よ り高速で,柔軟で,スケーラブルで,高いバ ン ド 幅で,低 い遅延の通信が達成 され る｡

3 PVM :ParaHelVirtuaIMachine (並列仮想 マシン) PVM は,マ シンの クラスターを リンクす るソフ トウェア システムである｡

ここで, クラスターとは,異機種の コンピュータの集 まりの ことであ り,それ が単一のマ シンとしてプログラム化 され ることを可能 にす るソフ トウェアシス テムである｡それ はユーザに,相異な るホス ト上で実行 しているタスク間の通 信 に対 してプロセスの コン トロール とメ ッセージ ･パ ッシングの コールを提供 す る｡ したが って,PVM はTCP/IP接続 されたイ ンターネ ッ トワーク上で

もイーサーネ ッ ト接続 されたLAN環境で も実現可能である｡

PVM は現在, ワー クステー シ ョンか らスーパー コンピュータまで各種 のマ シンとオペ レーティ ングシステム ･ネ ッ トワーク環境上で FortranとCプロ グラムをサポー トして いる｡PVM は,米国のオー ク リッジ国立研究所(ONL) のチームによ って開発 され,パ ブ リック ドメイ ンに置かれてい る｡現在 の版 は, 3.2.3 (1993年12月)であ り,アジア地区は,本学 と学生 の交換協定を結ん でいる豪州 ウ‑ ロンゴ ン大学 の[email protected]にメール を送 る ことによ って得 られ る｡ また,[email protected],または,netlib@

research.att.com にメールを送 るか,netlib2.cs.utk.eduよ り匿名ftp によって も得 られ る｡PVMは,ネ ッ トニ ュースcomp.parallel.pvmで活 発 な議論 によ り発展 しているが, Ⅹウィン ドウとのイ ンターフェースを持たせ

イ ンタ‑ネ ッ トを利 用 したOR計 算環境 の改善(2) 115

たⅩAB (Ⅹ window AnalysisanddeBugger)や,HeNCE (Heteroge‑

neousNetworkComputingEnvironment)が派生 した開発 ツール とな っ て展開されている｡また,商用のメッセー ジパ ッシングのパ ッケージとして, ExpressとLindaが注 目されている｡

Expressは,米国パサデナのParaSort社の製品で,全体的でポータブル なメ ッセー ジパ ッシング環境 を提供 し,解析 ツールやデバ ッガーを備えてい る8)0Lindaは,米国ニ ューヘ ブ ンの ScientificComputingAssociates の製品で,TupleSpaceとい う掲示板ふ うのプロセス管理を している｡また, デバ ッガーや管理 ツールを備えている.

PVMを用 いたコー ド例 は,物理のn一体 (多体)問題 に多数適用 されてき たが,オペ レー シ ョンズ ･リサ ーチの問題 に も適用 されつつ あ る｡実 際, PVM のマニ ュアルの一つ9)には,最短路問題 を, Cを用 いた PVM によっ てプログラム している｡すなわち,有向,無向グラフに辺のコス トを与えたと き,あ らゆる節点間の最短経路を計算 している｡ この種の問題 は,LOAPSP

(LengthsOfAllPairs'ShortestPaths)と呼ばれ る^｡

線形方程式をpvm が実装 された並列計算処理 によって解 くコー ドとしては 以下の2つがある｡

(1) 完全なScaLapac車 (ScalableLapack)パ ッケー ジ netlib@ornl.govか ら入手できる｡

(2) 共役 勾 配 法 (CG)を含 む反 復解 法 によ る PIM (Parallellteration Methods)パ ッケージ

PVM によるプログラ ミングは,緒 についたばか りで個別的なノウ‑ ウの蓄 積を必要 とす る｡

PVM の長所 は,

8)Expressは 日本で はニチメ ンデータシステムが ｢ParallelWare｣の名でサボ‑

卜している｡UNIXワークステー ション ･ネ ッ トワーク上での並列処理 システム は,｢Network‑Parallelware｣の名で販売 されている｡

9)ThePVM Systems: Anln‑DepthAnalysュsandDocumentingStudy

‑ConciseEdition,byち.K.GrantandA.Skjellum.

116 商 学 討 究 第44巻 第 4号

●イ ンターネ ッ トを通 じて無料で入手でき,ニュースグループやメイ リング

･リス トで議論ができる｡

●規模が小 さく,イ ンス トール,コンパイル,実行等が しやすい｡

●Unix互換機の上で,ポータブルであり,異質のネ ッ トワーク環境で稼働 す る^｡

他方,短所 としては,

●進行中の研究 コー ドであり,未完成な部分が残 っている｡

●セマフォがない｡ トレースの実行や,デバ ッガーがない｡

PVM は,研究用,学習用のツール として位置づけ られる｡

今後ますます強化 され,多 くのワークステーションをあたか も一つの並列 コ ンピュータのよ うに取扱い,大規模の問題を高速に実現できるかはボランティ アの参加 いかんによる所,大である｡

4 線形計算 と並列計算

連立一次方程式の解に関係 した線形計算は,オペ レーションズ ･リサーチの 基礎である｡ガウス消去法ない し改良ガウス消去法は簡単であ り,手計算にお いて もプログラ ミング演習において も採用 される｡計算の手間は,未知数 (同 じことであるが,式の数)の3乗 に比例す る算術演算で解が得 られ る｡しか し, ガウス消去法は, ピボ ッ ト計算を含むために数値的安定性において若干危険な 解法である｡数値的不安定さを もた らす現実のシステムがどの くらいあるかは 応用分野 による｡数値的安定性の保証 された別の方法 として ｢‑ウスホルダ一 法｣がある｡ しか しこの方法は理論的には,計算量がほぼ 2倍,多いことが欠 点 とされてきた｡今 日,並列 コンピュータの進展 につれて ピボ ッ ト演算を必要

としない‑ ウスホルダー法が,再び脚光を浴びてきた¹⁰⁾｡

ハウスホルダー法は,線形方程式体系Ax‑bを,‑ ウスホルダー変換を施 10)PerBrinchHansen, ̀̀HouseholderReductionofLinearEquations,''

ACM CoTnPutingSurueys,Vol.24,No.2 (June,1992).

インターネットを利用 したOR計算環境の改善(2) 117 して,逐次的に,上 3角形式に変換 し,後退代入により解 く｡上 3角形式に変 換するアルゴリズムは,以下に示すハウスホルダー変換 により,行列Aと右辺 ベ ク トルbをそれぞれ,HA,Hbに縮約する｡ このとき,HAの第 1列の第

2行以下は 0になる｡第 1段階における‑ウスホルダー変換 : .(Ll.ト ヽ

t L l ､ / L l

dl

l

(

日αlH ifα ..> O Halll else w ll‑ all‑ dll

fl ‑√ 2w lld ll

Hal‑ ldllO･･

･0

u‑ [w lla21･･･

an l ] T /fl

第 n段階における‑ ウスホルダー変換 :

(a‑ 1)× (a‑ 1)部分行列 と,(a‑ 1)右辺ベク トルに対 して‑ ウスホ ルダー変換を適用す るO これを,1要素になるまで続ける｡

i‑ 2,3,..., a,に対 して,

fl

Hat･‑ aI‑

fl

BrinchHansenは,ハウスホルダー法を用いると,n元連立一次方程式をp 台のプロセ ッサを もつ多重 コンピュータで並列に解 くとき,行列変換がpに依 存 して (プロセ ッサ通信時間は固定的である)削減できることを示 し,ガウス 消去法に対する優位を示 している^｡

線形計算の方法 には上記のよ うないわゆる直接法の他 に,反復的解法があ る^｡ 反復法 は初期近似解か ら出発 し,ある許容限界まで続 ける｡一般に,反復 法の方が演算回数 は少ない｡ しか しなが ら,並列化やその加速化 は,直接法よ

りも困難である｡

線形計画法の単体法に代わる内点法の研究において も並列計算処理が論 じら れて きた｡並列計算機構を用いていないが,パ ソコンレベルでは,1992年 に

は6千制約式,3万変数を処理す ることができるLPパ ッケージがあった｡

118 _{商 学 討 究 第}44巻 第 4号

pricing (価格)段階でのベ ク トル化を利用 して,スーパ ーコンピュータ CRAY Y‑M P上 では,1200万変数の問題 を約 3分少 々で解 いた報告が あ

る11)0

5 巡 回セール スマ ン問題 と並列計算

巡回セールスマ ン問題 は,地理的に離れたn都市があって,その都市の間の コス ト (距離,時間等)が既知のとき,セールスマ ンがある都市を出発 して全 都市を回って再び元の都市に戻 る最小のコス トの経路を求めるという問題であ

る｡

これは,多項式時間では解 けないのでNP一完全問題 として有名である｡

対 称型 の巡回 セ ール スマ ン問題 の1991年 までの記録 は,Padberg らの 2,392都市 で,変数 は,350万 変数 に及 んで い る｡Chvatalは,1992年 に TSPLIBとい うデータベース12)を用 いて3,038都市問題を解 き,世界記録 を 作 ったが,翌1993年 はじめには,4,461都市問題を解 き,記録を更新 した｡ し か し, 1994年 には7,397都市間題を解 くことを予告 している^｡ あれ ほど手 に負 えない巡回セールスマ ン問題が飛躍的に記録を更新 しているのは,約百台近い ワークステーションを用いて並列演算を しているか らである｡残念なが ら筆者 の手元のワークステーシ ョンを提供 し,協同作業の一端を担 うことがで きな かったが, 日本か らも協力 しているワークステーションがあると思われる｡

巡回セールスマ ン問題の世界記録を樹立す るためには,高速演算装置一個で 仕事をするスーパーコンピュータを必要 としない｡む しろ,それほど速 くな く て も (Sun SPARC Stationで も可能である)仕事やデータを うま く分割 し ll)Bixby,R.E.,∫.W.Gregory,∫.∫.Lustig,R.E.Marsten and D.F

Shanno,"VeryLarge‑scaleLinearProgramming: A CaseStudyin Combining lnterior Point and Simplex Methods,''Operations Re‑

search,40(1992),pp.885‑897.

12)Archieサ ー ビス によれ ば, 京 都 大 学 (ftp.kuis.kyoto‑u.ac.jp)と千 葉 大 学

･(ftp.ipc.chiゎa‑u.ac.jp)に所在す る.

イ ンターネ ッ トを利 用 したOR計算環境 の改善(2) 119

て協調 して解 くことが 出来 る環境 が必要 であ る｡並列処理 マ シ ンの PVM, nCUBE,CM ‑2上で,巡回セールスマ ン問題を並列 に解 く試み もある｡

並列 アル ゴ リズムには,問題を同 じ種類の部分問題 に分割 してそれぞれを並 行実行 させ るいわゆ る問題分割型が よ く用 い られ る｡ (それ以外 にはデータ分 割型が ある｡)通常 は,分割 され た部分 問題 を さ らに再帰的 に部分問題 に分割 してい く｡ そのため｡部分問題 は,指数関数的に増加す る｡ したが って,親処 理単位が再帰的に部分問題処理単位を生成 していき, しか もそれぞれの親がそ のすべての部分問題 の完了 を待 って後処理 を実行す る｡ これ は,入 れ子型 の fork‑join型 といわれ る｡

問題 やアル ゴ リズムの可視化,アニ メーシ ョン化 されたアルゴ リズム,分枝 限定法の並列処理の可視化 は本来的な並列化 問題 とは独立 に検討 されなければ な らない13)0

6 数 理 計 画 法 の学会 と並 列 コ ン ピュー テ ィング

第14回数理計画法 国際 シ ンポ ジウムは1991年 8月,オ ラ ンダのアムステル ダム大学 で開催 され,筆者 も出席 した｡基調 講演 は,W.R.Pulleyblank

(IBM, ウ オータールー大学) によ り ｢数理計 画法 ‑その進歩 と趨勢｣の演 題で行われたが,超並列 コンピュータの数理計画法のアルゴ リズム とデータ構 造 の研究が今後重要 になる と述べ た｡ また招待講演 の一つ は,K .Kennedy

(ライス大学)による｢超並列 スーパ ーコ ンピュータの来 るべ き世代｣であ り, 1990年代後半 に登場す るで あろ うテ ラフロ ツプのスーパ ー コ ンピュータは, 超並列 システムになるであろ う｡ そのアーキテ クチ ャとプログラ ミングの問題 は数理計画法 とどのよ うな関連があるかを述べた｡一般講演 は,全体で5日間 にわた り14会場 で並行 して行われ,延べ400件近 い,講演がなされたが,その 13)PeterGloor,ScottDynes,andIreneLee,AnimatedAlgorithms:A

Hypermedia Learning Environmentforintroduction to Algorithms, CDROM forAppleMacintoshComputer,TheMITPress.1993.

120 商 学 討 究 第44巻 第 4号

うち,並列 コンピューティングのセ ッションには,30件近い報告がなされた｡

その全 リス トを,アルファベ ッ ト順にソー トして,付録に掲げた｡3年後の第 15回大会 (1994年)にはその数量,品質 ともに倍に増加す るであろう｡

他方, 日本国内最大の数理計画法の シンポジウムは,毎年 1回,RAMP (ResearchAssociationofMathematicalProgramming)と して 日本 OR学会特設研究部会の もとに開催されている｡1993年には,福島雅夫 (奈良 先端科学技術大学 院大学)によ り,｢数理計画問題 に対す る並列 アルゴ リズ ム｣14)のチュー トリアル講演がなされた｡参考文献 は,95件掲載 され,特に並 列 コンピュータによる計算結果を含む25件を弁別 している｡

大規模線形計画法では,従来より,特殊なブロック分解構造を利用 した高速 化分解原理が適用 されていたが,それはベ ク トル計算機向きといえ る｡近年 は, 並列計算の細粒 (finegrained)分解を適用 して,与え られたデータ構造を 並列計算向きに変換す る｡

線形計 画法 の単体法 (Simplex Method)に代 わ る内点法 (Projective interior‑pointalgorithm)が大規模問題を解 く有力な方法 として注 目され ているが, この方法にも並列 コンピューティングが適用されつつある15)｡

非線形計画法では,関数 と微係数の評価部分 と,いわゆる線形計算部分が並 列化の鍵であ り,分散型および分散共有型のMIMDマシンを利用 した並列化 の結果が現れつつある｡

7 インターネ ッ トニ ュースのニ ュースグループ

並列 に関するインターネ ッ ト上のニ ュースグループとして, fj.comp.parallel 日本における並列アーキテクチャ関連

14)第5回RAMPシンポ ジウム論文集,pp.15‑28.

15)例えば,付録のAndersenのはか,日本でも,小田,熊野,前田,｢ベ ク トル処理

･並列処理 を用 いた内点法 プ ログラム ー通信網計画問題‑の適用 を中心 と して｣

ProceedingsoftheSecondRAMPSymposium,pp.21‑33,1990.を参照｡

インターネットを利用 したOR計算環境 の改善(2) 121 comp.parallel 米国における並列アーキテクチャ関連

comp.parallel.pvm 米国におけるpvm関連

オペ レーションズ ･リサーチ関係のニ ュ‑スグループには,

s°i.op‑search 米国におけるオペ レーションズ ･リサーチの議請 s°i.econ.research 米国における経済学の研究

s°i.staも.consulting 米国における応用統計学 と実践的利用 があり,活発な議論を展開 している｡

8 結語的覚え書き

イ ンターネ ッ トワークは,全世界をおお う情報通信のイ ンフラス トラクチャ として不可欠の基礎環境 となってきた｡多 くの研究者 は,イ ンターネ ッ トを利 用 して,情報サー ビスを得て,研究に役立てるとか,研究者同士のオ ンライ ン

リアルタイムの交換,交流のみな らず,phoneやtalkコマ ン ドによる電子授 業 も展開 して きた｡今後 はさ らに使 いやすいイ ンターネ ッ ト環境が期待 され

る｡

インターネ ッ トのソフ ト,ハー ド両面への波及効果 も大 きい｡パ ソコン翠明 期 は,ワー ドプロセ ッサーやスプ レッ ドシー ト (表計算)ソフ トウェアを快適 に利用するために,パ ソコンの性能が上が ったといわれる｡イ ンターネ ッ トに おいて も利用者の声は着実に変革を もた らしている｡ネ ットワーク トラフィッ クの逓増 に対 しては,FDDIに代 わ る高速多機能で安定 した FI)DI‑ 2や ATM があるO高価なスーパ ーコンピュータを しの ぐネ ッ トワーク化 された

ワークステーシ ョン群,あるいは共有分散メモ リーの並列マシンが商用化され 始めた｡ただそれに付随するソフ トウェアやツールが遅れている.最後 まで残 される問題 は情報セキュリティや知的保有権の問題であり, グローバルな社会 規範の確立が可能かどうか となる｡

本稿 は,

TCP/I P

122 商 学 討 究 第44巻 第 4号

アクセスに留 まらず,並列分散処理を利用す ることの背景,現状,問題点をオ ペ レーションズ ･リサーチの計算環境の側面か ら概観 した｡伝統的なORは, いま,イ ンターネ ッ トワーキ ングや‑イパ フォーマ ンス ･コンピューティング の到来 とともに大 きく変容をもた らしつつある｡OR研究者 は新 しい計算環境 に受動的であるべ きではな く能動的でなければな らない｡

イ ンターネ ッ トを利 用 したOR計算環境の改善(2)

付録 :第14回数理計画法国際シンポジウム (1991年)における並列 コンピューティングのセッションでの一般講演の全 リス ト

123

1.Abraha.msson,S.T.,Matrix‑balancingappliedtotrafficasslgnment 2.Akman,Ⅹ､Ⅰ.,ParallelcomputinglnStatistics

3.Andersen,♂.,Theinteriorpointmethodforl∫ponaparallelcomputer 4.Archibald,T.W.,ParallelalgorithmsforMarkovdecisionprocesses 5.Ariyawansa,A.A.,A palrallelVanSlyke‑Wetsalgorithm

6.Bachem,A.,Simulatedtradingforparallelizingvehiclerouting 7.Bertsekas,D.P.,Anauctionalgorithm forshortestpaths

8.Byrd,R.班.,Limitedmemorymethodsinlargescaleoptimization 9.Clausen,∫.,Combinatorialoptimizationusingtransputers

10.Conforti,D.,ImplementingaparallelNewtonmethod

ll.Ebara,H.,Parallelbranchandboundfortheknapsackproblem 12.Edwards,∫.∫.,TowardsahighlyparallelMPsystem

13.Ferris,M.C.,Parallelconstraintdistribution

14.Ferrls,M,C.,Pivotalmethodsforaffinevariationalinequalities 15.Fukushima,M.,Analgorithm fornonsmoothoptimization

16.Garcia‑Palomares,U.M.,Aggregationmethodsforconvexsystem 17.Ho,∫.K.,StochasticLPonahypercube

18.Levkovitz,R.,Solvingsparseequationsonaparallelcomputer 19.Lindstr6m,P.J.B.,Globaloptimizationonahypercube 20.Lootsma,F.A･,TestingalgorithmicideasinparallelNLP 21.Maier,R.S.,A trust‑reglOnalgorithm forlarge‑scaleNI.f'

22.Mckinnon,K.I.M.,ParallelassumptlOninchemicalenglneering 23.Meyer,R･R,Paralleltaskasslgnmentforrectangulararrays

24.Nagurney,A.,Massivelyparallelcomputationofeconomicequilibri‑ um

25.Perekhod,i.A.,Generalenumeration:conceptandalgorithms 26.Sofer,A.,Solvinglargeunconstrainedproblemsinparallel 27.Torczon,Ⅴ.∫.,Ontheconvergenceofpatternsearchmethods

28.Zenios,S.,Massively parallelcomputationsfor stochasticprogram‑

ming