並列プログラミングのエキスパートのようになるには – パート 1: 並行性 (コンカレンシー) と並列性 (パラレリズム)

HPC特集

この記事は、インテル® ソフトウェア・ネットワークに掲載されている「How to sound like a Parallel Programming Expert Part 1: Introducing concurrency and parallelism」(http://software.intel.com/en-us/articles/how-to-sound-like-a-parallel-programming-expert-part-1-introducing-concurrency-and-parallelism/) の日本語参考訳です。


並列プログラミングのエキスパートのようになるには

パート1 パート2 パート3 パート4

並列コンピューティングの時代がやってきました。現に、これを書いているのはデュアルコアのラップトップです。先日、息子が買ったゲーム機には 9 コアが、そして、現在使用している携帯電話には 4 つのプロセッサーが搭載されています。GPU (グラフィックス・プロセシング・ユニット) でも多数のコアが使用され、世界一高速なスーパーコンピューターでは、その数が 10 万を超えています。

近年、並列コンピューティングはありとあらゆるところで使用されています。

なぜこうなったのでしょう?

スーパーコンピューターの分野では、この 20 年間、究極のパフォーマンスを引き出すために並列化が進められてきました。しかし、この動きがコンピューター業界全体に広がったのは、スピードアップへの要求からだけではありません。その背景には、電力効率や消費電力 1 ワットあたりの最大パフォーマンスを向上させる必要性があったからです。

チップの消費電力はクロック周波数の上昇に伴い急増しますが、ある時点で、効率的な利用と適切な消費ができなくなるほど多くの電力をソケットへ供給しない限り、チップのクロック周波数を上げることができなくなります。こうなると、各プロセッサーのクロック周波数を固定し、そのプロセッサーのコア数を増やすことでしかパフォーマンスの向上は望めません。

つまり、これこそがコンピューター業界全体で並列化が行われ、あらゆるところで並列コンピューターが注目されている理由です。並列システムを活用するためには、計算ユニットに一度に複数の命令を渡す必要があります。しかし、そのためには、複数の命令を生成できるようにアルゴリズムとソフトウェアを大幅に見直し、変更しなければならず、つまり「並列プログラミング」と呼ばれる知識が必要になります。

並列プログラミングを極めるのは優しいことではありません。これまで、並列プログラミングのエキスパートは、ハイエンドのスーパーコンピューティングi でのみ必要とされてきました。しかし、今日では、ソフトウェア業界全体が並列プログラミングへの大きな転換を迫られています。並列プログラミングのエキスパートになるのは難しく、長い年月がかかりますが、たいていの場合は並列化に関する高レベルの問題を理解するだけで十分です。大半の開発者は、実際にエキスパート・レベルにまでなる必要はなく、「並列プログラミングのエキスパートのようになる」だけで十分でしょう。

このシリーズでは、「並列プログラミングのエキスパートのようになる」ことを目的としています。並列コンピューティングに関する専門用語を正しく理解し活用するための情報を 次の 4 つのパートにわたって提供します。

  • パート 1: 概要および並行性 (コンカレンシー) と並列性 (パラレリズム) の相違点
  • パート 2: 並列ハードウェア
  • パート 3: 並列プログラミングにおける問題
  • パート 4: 並列プログラミング手法

このシリーズでは、高レベルの並列プログラミングを理解し、並列プログラミングの専門用語の正しい使用方法を知ることができます。ひょっとしたら、このシリーズがきっかけとなり、「エキスパートみたい」ではなく、実際に「エキスパート」になろうと思うようになるかもしれません。

並行性 (コンカレンシー)

並列コンピューティングの基本概念は並行性といえます。

並行性: システムの複数のタスクをアクティブな状態で維持し、同時に処理を実行すること。

並行性は古くからある概念で、現在使用されているメインストリームのすべてのオペレーティング・システム (OS) で活用されています。システムで待機が発生した場合にほかの作業を実行できるように、複数のスレッドをアクティブな状態で維持して、迅速にスレッドの切り替えを行います。人間の時間感覚はミリ秒ですが、コンピューターのクロックはナノ秒であるため、OS は、システムに 1 つのプロセッサーしかない場合でも、複数のタスクが同時に実行されているかのように見せることができます。

並行ソフトウェアのコーディングは容易ではありません。最初に、同時に実行可能な処理の塊 (タスク) を見つけ、その中に並行性を見出さなければなりません。プログラムでは、タスク間のデータ共有方法を管理し、異なるタスクがどのような順番で実行されても、常に正しい結果が生成されるようにしなければなりません。そして、ソースコードでは、ある種の表記方法やアプリケーション・プログラミング・インターフェイス (API) を使用して並行性を実装します。

並列性 (パラレリズム)

並列性とは?

並列性: 問題を短時間で解くためにプログラムで並行性を活用すること。

並列コンピューティングとは、並行性を活用することです。並行性を備えていない並列性はありえません。そして、並列プログラムを並列で実行するには、並行タスクが並列で実行されるように、複数のプロセッサーを搭載したハードウェアが必要です。

例えば、レイトレーシングは、イメージのレンダリングに使用される一般的な手法です。原則として、それぞれの光線は独立したタスクとして処理可能なため、レイトレーシングには必然的に多くの並行性が含まれています。そのため、これらのタスクを実行キューに追加し、複数のスレッドを使用して並列コンピューターで並列に実行できます。つまり、レイトレーシングでは並行処理を活用して、固定サイズのイメージを短時間でレンダリングする並列プログラムを作成できます。

アルゴリズム

アルゴリズムとは、問題を解くための手順です。従来のシリアル・アルゴリズムでは、この手順は特定の順序で一度だけ実行されます。当然のことながら、並行アルゴリズムと並列アルゴリズムではこれがより複雑になります。

アルゴリズムにおける並行性とは、手順が 1 つだけではなく、複数の手順が同時に実行されることを意味します。これらの手順がどのようにスケジューリングされるかによって、さまざまな組み合わせが存在することになります。つまり、プログラムの実行ごとに、メモリーアクセス操作の順序が変わります。そのため、同じメモリー位置への読み取り操作と書き込み操作がある場合、プログラムの実行ごとに結果が変わる可能性があります。これを競合状態、略して「競合」と呼びます。

したがって、並行性を含むアルゴリズムを設計する場合、読み取りと書き込みが発生するメモリー位置では、アクセス順序が保障されるような構造にする必要があります。このような構造 - いわゆる同期構造 - を適切な場所に組み込むことはなかなか難しいことです。

並行性を実装する 2 つのアルゴリズムについて考えてみましょう。1 つ目は、並行アルゴリズムと呼ばれるもので、割り当てられたタスクが処理を完了するために本質的に並行性を必要とする問題です。例えば、複数のユーザーからのジョブを管理するネットワーク・プリンターでは、印刷キューはジョブを実行するため本質的に並行でなければなりません。

2 つ目は、並列アルゴリズムと呼ばれるもので、アルゴリズムの中で並行処理を行う場合に使用します。これは、先ほどの並列性の定義からも予測できるかと思いますが、操作を並行に実行することにより問題を短時間で解くためのアルゴリズムです。ここでは、どうしたら並列プログラミングのエキスパートのようになれるのか、この並列アルゴリズムに注目します。

並列アルゴリズムの研究は、大変なことのように思えるかもしれません。並列プログラムに関する文献では、一見異なる多数のアルゴリズムが紹介されています。幸いなことに、この分野はすでに成熟していて、これらのアルゴリズムは解り易い体系に組織化されています。

特に興味深いアプローチでは、デザインパターン言語を使用して、並列アルゴリズム設計のエキスパートによって使用されている知識を分かりやすい形に置き換えています。『Patterns for Parallel Programming』 (Mattson、Sanders、Massingill 著。2004 年) にあるように、並列アルゴリズムが持つ並行性の要因によって、3 つのカテゴリーに分けられます。

  • タスクベースのアルゴリズム
  • データ並列アルゴリズム
  • さまざまな処理段階を通じたデータフロー

これらのアルゴリズム・パターンは、異なる並列プログラミング環境を使用して並列アルゴリズムを表現するさらに低レベル指向なパターンへとマッピングされます。

並列ソフトウェアの作成方法については後述します。その前に、並列ハードウェア、並列パフォーマンスの問題、正当性について見てみましょう。

次のステップ

ここまでは、並列プログラミングにおける問題の概要、並行性と並列性の概念、そして並列アルゴリズムについて説明しました。パート 2 では、並列プログラムの実行に必要な並列ハードウェアについて見てみましょう。

パート1 パート2 パート3 パート4

著者紹介

Tim Mattson はインテル コーポレーションのマイクロプロセッサー・テクノロジー研究部門の主任エンジニアで 並列プログラマー。20 年以上にわたり、並列コンピューターを使用して、化学反応、タンパク質分解、石油発見、遺伝子解読など、多数の科学的問題に取り組む。将来の目標は、シーケンシャル・ソフトウェアを希少なものにすること。この目標達成に向けて日々努力している。

i http://www.top500.org/

タイトルとURLをコピーしました