マルチコアプログラミングにおける負荷分散の課題

マルチコア CPU で複数の CPU のパフォーマンスを最大限に活用するには、各 CPU に割り当てられたタスクの負荷バランスが適切であることを確認する必要があります。そうしないと、一部の CPU が実行され、他の CPU がアイドル状態になり、マルチコア CPU の利点が活かされなくなります。

通常、適切な負荷分散を実現するには 2 つのソリューションがあります。1 つは静的負荷分散、もう 1 つは動的負荷分散です。

1. 静的負荷分散

静的負荷分散では、プログラムを並列実行可能な複数の部分に手動で分割し、分割された部分が各 CPU に均等に分散されて実行されるようにする必要があります。高い加速係数を達成するには、作業負荷を複数のタスク間で均等に分散する必要があります。

数学的に言えば、静的負荷分散問題は、Richard M. Karp、Jeffrey D. Ullman、Christos H. Papadimitriou、M. Garey、D. Johnson らが相次いで解決した問題です。いくつかの異なる制約の下での静荷重問題の NP 完全性が 1972 年から 1983 年の間に証明されました。

NP 完全性問題は数学の難しい問題ですが、NP 完全性問題は一般に非常に効果的な近似アルゴリズムによって解決できるため、タイトルで述べたような難しい問題ではありません。

2. 動的負荷分散

動的負荷分散とは、負荷分散の目的を達成するために、プログラムの実行プロセス中にタスクを割り当てることです。実際には、静的な負荷分散では解決できない問題が多くあります。たとえば、ループの数が外部から入力される場合、ループの数は事前にわかりません。静的な負荷分散分割戦略を実装するのは困難です。

動的負荷分散におけるタスクのスケジューリングは通常、システムによって実装されます。実際のタスクには多くの不一致があるため、プログラマは通常、動的分散スケジューリング戦略を選択することしかできず、スケジューリング戦略を変更することはできません。特定の要因により、スケジューリング アルゴリズムが適切に機能しないため、動的負荷分散が確立された負荷分散要件を満たさない場合があります。

3. 負荷分散の問題は何ですか?

負荷分散の問題は、負荷分散の程度にありません。各 CPU に割り当てられるタスクの実行時間に多少のギャップがあっても、CPU コアの数が増加すると、負荷分散の程度は低下します。 CPU コアの数が増加すると、加速係数が増加するため、合計実行時間が減少します。

負荷分散の難しさは、デュアルコアや 4 コアなど CPU コアの数が少ない場合には、プログラム内の多くの並列実行ブロックをプログラマが分割する必要があることです。 , この分け方はそれほど難しくありません。しかし、コアの数が増えると、分割の粒度はさらに細かくなります。コアの数が 16 を超えると、プログラマはタスクをどのように分割するかにおそらく混乱するでしょう。たとえば、逐次実行されるコードを 128 コアの CPU で実行すると、手動で 128 個のタスクに分割する必要があり、その分割の困難さは容易に想像できます。

たとえば、16 時間単位かかるプログラムを 4 つのタスクに分割して実行し、それぞれの平均ロード実行時間を計算すると、負荷分割の誤差は増大します。タスクが 4 時間単位で、除算誤差が 1 時間単位である場合、加速係数は 16/(4+1)=3.2 になり、これは理想的な状況での加速係数 4 の 80% になります。しかし、16 コア CPU で実行した場合、あるタスクの除算誤差が 0.5 時間単位であれば、加速係数は 16/(1+0.5) = 10.67 となり、理想的な加速係数 16 だけが 66.7 になります。さらにコア数が増加すると、誤差が増幅されて理想加速係数に対する比率が低下します。

負荷分割の問題は、CPU とソフトウェアのアップグレードにも反映されます。たとえば、4 コア CPU では負荷分割はバランスが取れていますが、8 コアや 16 コアでは負荷分割が行われます。 CPU、負荷がアンバランスになる可能性があります。ソフトウェアのバージョンアップでも同様で、ソフトウェアに機能が追加されると負荷バランスが崩れ、バランスをとるために負荷を再分割する必要があり、ソフトウェア設計の難易度や手間が大幅に増加します。

ロックが使用されている場合、一見バランスが取れているように見える負荷の一部が、ロックの競合によりアンバランスになる可能性があります。

4. 負荷分散戦略

計算量が少ないソフトウェアの場合、たとえシングルコア CPU に配置されていても、負荷分散が不十分であっても、実際には大きな影響はありません。計算負荷が高く大規模なソフトウェアは、複数のコアを有効に活用してパフォーマンスを向上させるために、複数のコアで負荷分散する必要があります。

大規模ソフトウェアの負荷分散で採用される対応戦略は、並列ブロックを分割するマクロ分割手法を開発し、特定の部分を対象とするのではなく、ソフトウェアシステム全体のレベルで分割することです。従来の方法と同様に、並列分解にはプログラムとアルゴリズムが使用されます。これは、ローカル プログラムを数十を超えるタスクに分解して実行することが通常難しいためです。

もう 1 つの対処戦略はツール レベルです。つまり、コンパイル ツールは並列ブロックの手動分解を支援し、適切な分解ソリューションを見つけることができます。インテルはこの点に関してある程度の努力をしてきましたが、まだ努力する必要があります。コア数が多い場合の状況に対処するために、ツールをより強力にするために作成されています。