BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ ニュース 並列プログラミングは難しい?Guy Blelloch 教授はそうではないと主張

並列プログラミングは難しい?Guy Blelloch 教授はそうではないと主張

原文(投稿日:2009/4/21)へのリンク

Cilk Arts での評論(リンク)において Guy Blelloch 教授は並列プログラミングは本来難しいものではなく、むしろ抽象化に関する問題であると主張している。Blelloch 氏が特定する3つの問題点は、並列的思考の訓練の欠如、並列的な実装のアルゴリズムからの分離、そして決定論である。それぞれの問題についての詳述の後、彼はなぜそれらが克服可能であると考えるのかを説明している。

「並列的思考」の問題において、彼はクイックソートアルゴリズムを引き合いに出している。 クイックソートはその再帰的な呼び出し、およびピボット要素とリスト内の各要素との比較という両面において本質的に並列的である。

ところが私たちの授業では大抵それが並列的であるということを指摘しないままにクイックソートを教えます。  順次実行を注意深く一通り調べて分析し、その期待計算時間は O(n log n) であると論じます。  学生たちのほとんどはアルゴリズムの並列性の度合いについて、そして並列性の分析方法については確実に何も分からないままです。  例えば、あるアルゴリズムをそのまま利用する場合あるいは他の形式の並列処理の場合だったらどのようになって、どのくらいの並列性があるか、などです。

Blelloch 氏はアルゴリズムは既に的確な抽象化のレベルにあるため、これは単にプログラマが並列性の観点から思考する訓練の問題であると考えている。

彼が取り上げる2つ目の課題は低レベルな要素と高レベルな要素の分離である。 40年前、アルゴリズムに関する書籍のほとんどにはメモリの割り当てに関する覚え書き、スタックを用いた擬似的な再帰、また少なくはない量のアセンブリコードが含まれていたものであった。 近頃ではプログラマは再帰について熟考することがないばかりか、ほとんどメモリ管理について考えることすらない。 にもかかわらず多数の並列ライブラリはいまだに「フォークされたタスクのスタックサイズを指定する、自身のスケジューラを実装するもしくはスケジューリング方針を指定する、あるいはメモリのプロセッサへのマッピングを理解する」ことを開発者に要求する。

Blelloch 氏は「もみ殻からの小麦の分離」の良い例として Cilk++ を奨励している。もちろん、例えば Microsoft の並列協調ランタイム(CCR)/分散ソフトウェアサービス(DSS)(リンク)、Parallel LINQ(参考記事)、Java の fork-join フレームワーク(リンク)、そして Erlang(リンク) のような特化された言語などの他の計画もまた同じ方向へと進んでいる。

3つ目の課題は決定論、あるいはまた平行プログラミングとして知られているものについてである。  Blelloch 氏は非決定論的なコードはごくまれであるべきであり、それが存在する場所は外面的には決定論的なコンポーネントの内部に隠蔽されているべきであると主張する。

残念ながら、これは彼の主張が通用しない部分である。 外部通信に対応するシステムはシーケンスおよび振る舞いの両面において本質的に非決定論的である。 どんなに抽象化を行ったとしてもビデオゲームで他のプレイヤーがいつキャラクターを移動させるか予測しようとしてもできないという事実を変えることはできない。 あるいは各取引先の業者が特定の在庫処分を行うのか見送るのかを予見するのもまた不可能である。

それでも、この評論より2つのポイントについては片付けることができる。 学校教育では実際に並列アルゴリズムの観点から考えるよう学生に指導する時間をもっと増やす必要があり、また次世代のライブラリに関しては平行ではないにしても並列なシステムについては大いに有望であるということだ。

この記事に星をつける

おすすめ度
スタイル

BT