BT

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

| 作者: Jonathan Allen フォローする 611 人のフォロワー , 翻訳者 伊藤 幸博 フォローする 0 人のフォロワー 投稿日 2009年4月30日. 推定読書時間: 3 分 |

原文(投稿日: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つのポイントについては片付けることができる。 学校教育では実際に並列アルゴリズムの観点から考えるよう学生に指導する時間をもっと増やす必要があり、また次世代のライブラリに関しては平行ではないにしても並列なシステムについては大いに有望であるということだ。

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT