Loading article…
並列コンピューティングでは、タスクの粒度（または粒度サイズ）は、そのタスクによって実行される作業量（または計算量）の尺度です。[1]
粒度の別の定義では、複数のプロセッサまたは処理要素間の通信オーバーヘッドを考慮しています。粒度は計算時間と通信時間の比率として定義され、計算時間はタスクの計算を実行するために必要な時間であり、通信時間はプロセッサ間でデータを交換するために必要な時間です。[2]
T compが計算時間、T commが通信時間を表す場合、タスクの粒度Gは次のように計算できます。 [2]
粒度は通常、特定のタスクで実行される命令の数で測定されます。 [1]また、粒度は計算時間と通信時間を組み合わせたプログラムの実行時間で指定することもできます。[1]
並列処理の種類
並列タスクによって実行される作業量に応じて、並列処理は細粒度並列処理、中粒度並列処理、粗粒度並列処理の 3 つのカテゴリに分類できます。
細粒度並列処理
細粒度並列処理では、プログラムは多数の小さなタスクに分割されます。これらのタスクは、多数のプロセッサに個別に割り当てられます。並列タスクに関連する作業量は少なく、作業はプロセッサ間で均等に分散されます。したがって、細粒度並列処理は負荷分散を容易にします。[3]
各タスクが処理するデータ量が少ないため、処理全体を実行するために必要なプロセッサの数は多くなります。その結果、通信と同期のオーバーヘッドが増加します。
細粒度並列処理は、高速通信をサポートするアーキテクチャで最も効果的に活用されます。通信オーバーヘッドが低い共有メモリアーキテクチャは、細粒度並列処理に最適です。
プログラマがプログラム内の並列性を検出することは難しいため、通常、細粒度の並列性を検出するのはコンパイラの責任です。 [1]
細粒度システム（並列コンピューティング領域以外）の例としては、脳内のニューロンシステムが挙げられる。[4]
コネクションマシン（CM-2）とJマシンは、 4〜5μsの範囲の粒度を持つ細粒度並列コンピュータの例です。 [1]
粗粒度の並列処理
粗粒度の並列処理では、プログラムは大きなタスクに分割されます。このため、プロセッサで大量の計算が行われます。これにより、負荷の不均衡が生じ、一部のタスクが大量のデータを処理し、他のタスクがアイドル状態になる可能性があります。さらに、粗粒度の並列処理では、ほとんどの計算がプロセッサ上で順次実行されるため、プログラム内の並列処理を活用できません。このタイプの並列処理の利点は、通信と同期のオーバーヘッドが低いことです。
メッセージパッシングアーキテクチャはプロセス間でデータを通信するのに長い時間がかかるため、粗粒度の並列処理に適しています。[1]
Cray Y-MPは、約20秒の粒度を持つ粗粒度並列コンピュータの例です。 [1]
中粒度の並列処理
中粒度並列処理は、細粒度並列処理や粗粒度並列処理と相対的に使用されます。中粒度並列処理は、細粒度並列処理と粗粒度並列処理の中間に位置し、タスクサイズと通信時間は細粒度並列処理より大きく、粗粒度並列処理より小さくなります。ほとんどの汎用並列コンピュータはこのカテゴリに分類されます。[4]
Intel iPSCは、約10msの粒度を持つ中粒度並列コンピュータの例です。 [1]
例
処理する必要がある 10x10 ピクセルのサイズの画像 20 枚のスタックを考えてみましょう。100 ピクセルのそれぞれが互いに独立して処理できると仮定します。1 ピクセルの処理には 1 クロック サイクルかかります。
きめ細かな並列処理:各ピクセルは、一度に 1 つのプロセッサによって個別に処理されます。画像の処理を担当するプロセッサが 100 個あると仮定すると、100 個のプロセッサは 1 つの 10x10 画像を 1 つのクロック サイクルで処理できます。プロセッサが 20 個ある場合、画像ごとに 5 クロック サイクルかかります。各プロセッサは、利用可能な時間の 100% 使用できますが、各ピクセルの計算結果は、各画像処理の最後に通信して集計する必要があり、オーバーヘッドが大きくなる可能性があります (画像ごとに 100 回の通信 = 合計 2000 回)。
中粒度の並列処理:画像は 4 分割されます。各 4 分割は、一度に 1 つのプロセッサによって個別に処理され、25 クロック サイクルかかります (5x5 ピクセルの場合)。20 個の画像スタックを処理するプロセッサが 20 個あると仮定すると、4 つのプロセッサが各画像を処理し、5 つの画像を並列処理できます。100 個のプロセッサが使用可能な場合、80 個のプロセッサが 25 クロック サイクルかけてスタックを並列処理し、20 個のプロセッサは作業が割り当てられていないアイドル状態になります。4 つの 4 分割が処理されたら、結果を集計する必要があります (画像ごとに 4 回の通信 = 合計 80)。
粗粒度の並列処理:完全な画像は 1 つのプロセッサで 100 クロック サイクルかけて処理されます。この場合、一度に使用できるプロセッサは 20 個のみで、通信なしで 100 クロック サイクルで作業が完了します。
どのアプローチが最適かは、作業負荷と利用可能な処理ユニットによって決まります。目標は、並列化を最大化 (作業を十分な単位に分割して、利用可能なほとんどのプロセッサに均等に分散する) しながら、通信オーバーヘッド (通信に費やす時間と計算に費やす時間の比率) を最小化することです。この例では、処理する画像数がワーカー数に比べて多い場合、各ワーカーに十分な負荷がかかるため、画像を小さな単位に分割しても意味がありません。画像数がワーカー数に比べて少ない場合、一部のワーカーがアイドル状態になり、計算時間を無駄にする可能性があります。ただし、これは 1 つの画像の処理に長い時間がかかる場合にのみ問題になります。処理が非常に高速な場合は、作業を小さな単位に分割すると、通信に失われる時間が並列化によって得られる時間よりも長くなるため、全体の操作が遅くなる可能性があります。
並列処理のレベル
粒度は処理レベルと密接に関係しています。プログラムは4つの並列レベルに分けられます。
- 指導レベル。
- ループレベル
- サブルーチンレベルと
- プログラムレベル
最も高い並列性は命令レベルで達成され、次にループレベルの並列性が続きます。命令レベルとループレベルでは、細粒度の並列性が達成されます。命令レベルでの典型的な粒度は20命令ですが、ループレベルでの粒度は500命令です。[1]
サブルーチン（またはプロシージャ）レベルでは、粒度は通常数千命令です。中粒度の並列性はサブルーチンレベルで実現されます。[1]
プログラムレベルでは、プログラムの並列実行が行われます。粒度は数万命令の範囲になります。[1]このレベルでは粗粒度の並列処理が使用されます。
以下の表は、並列度、粒度、並列度の関係を示しています。
粒度がパフォーマンスに与える影響
粒度は並列コンピュータのパフォーマンスに影響します。細粒度または小さなタスクを使用すると、並列性が向上し、速度が向上します。ただし、同期オーバーヘッド、スケジュール戦略などは、細粒度タスクのパフォーマンスに悪影響を与える可能性があります。並列性を高めるだけでは最高のパフォーマンスは得られません。[5]
通信オーバーヘッドを減らすために、粒度を上げることができます。粗粒度のタスクは通信オーバーヘッドが少なくなりますが、負荷の不均衡を引き起こすことがよくあります。したがって、細粒度並列処理と粗粒度並列処理の2つの極端な状態の間で最適なパフォーマンスが達成されます。[6]
さまざまな研究[5] [7] [8]では、並列処理を支援するために最適な粒度を決定するための解決策が提案されています。最適な粒度を見つけることは、多くの要因に依存し、問題ごとに大きく異なります。
参照
引用
- ^ abcdefghijk Hwang, Kai (1992). 高度なコンピュータアーキテクチャ: 並列性、スケーラビリティ、プログラマビリティ (第 1 版). McGraw-Hill Higher Education. ISBN 978-0070316225。
- ^ ab Kwiatkowski, Jan (2001 年 9 月 9 日)。「粒度の測定による並列プログラムの評価」。並列処理と応用数学。コンピュータサイエンスの講義ノート。第 2328 巻。pp. 145–153。doi : 10.1007/ 3-540-48086-2_16。ISBN 9783540437925。 9783540480860 。
- ^ Barney, Blaise. 並列コンピューティング入門.
- ^ abミラー、ラス、スタウト、クエンティン F. (1996)。正規アーキテクチャの並列アルゴリズム：メッシュとピラミッド。マサチューセッツ州ケンブリッジ：MIT プレス。pp. 5–6。ISBN 9780262132336。
- ^ ab Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1990 年 1 月 1 日)。「並列システムにおける同期と粒度の影響」。第17回国際コンピュータ アーキテクチャ シンポジウム - ISCA '90 の議事録。第 18 巻。pp. 239–248。CiteSeerX 10.1.1.51.3389。doi : 10.1145 /325164.325150。ISBN 0-89791-366-3. S2CID 16193537。
- ^ Yeung, Donald; Dally, William J.; Agarwal, Anant. 「並列コンピュータの粒度を選択する方法」CiteSeerX 10.1.1.66.3298。
{{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です - ^ McCreary, Carolyn; Gill, Helen (1989 年 9 月 1 日)。 「効率的な並列処理のための粒度の自動決定」。Commun . ACM。32 ( 9 ): 1073–1078。doi : 10.1145 / 66451.66454。ISSN 0001-0782。S2CID 14807217 。
- ^ クルアトラチュエ、ブーンティ;ルイス、テッド（1988年1月1日）。 「並列処理のための粒度の決定」。IEEE ソフトウェア。5 (1): 23-32。土井：10.1109/52.1991。ISSN 0740-7459。S2CID 2034255。