高性能コンピューティングアプリケーションのテスト

並行アプリケーションは、基盤となるオペレーティングシステムのあらゆるスレッドスケジュールで正しく実行される必要があります。しかし、従来のテスト方法では、主にハイゼンバグ^{[ 1 ]の}問題のために、バグを検出できるのはごくわずかです。ハイゼンバグとは、同期要求や遅延ステートメントなどの構造を追加してデバッガ で分離して調査しようとすると、変化したり消えたりするエラーのことです。

もう一つの問題は、スケジューラの予測不可能な動作に起因します。システム負荷の違いはスケジューラの動作に影響を与えます。この動作は手動で変更することはできません。この不確定性に対処するには、さまざまな実行環境でプログラムを何度も実行する必要があります。それでも、バグが再現できるとは限りません。ほとんどの場合、プログラムは正しく実行され、バグは特定の条件が一致した場合にのみ現れます。結果として、並行プログラムの再現性の低さは、エラー検出の大きな障害となります。例として、以下を考えてみましょう。

明らかに、これはデッドロックを引き起こすという問題を抱えている。しかし、プログラムの実行によってはデッドロックが発生する場合もあれば、正常に実行される場合もある。

プローブ効果は、同期の問題を抱える並列プログラムに遅延文を挿入した際に発生します。この効果は、ハイゼンバグと同様に、動作の変化を引き起こし、問題を隠蔽する可能性があります。プローブ効果の原因を特定することは、並列アプリケーションのテストにおいて大きな課題となります。プローブ効果とハイゼンバグの主な違いは、ハイゼンバグはテスト中に並行アプリケーションに遅延文や同期要求を追加した際に発生するのに対し、プローブ効果は開発者が同期が不十分な並行アプリケーションに遅延文を追加した際に発生する点です。

スケジューリングの不確定性には2つの原因がある。^{[ 1 ]}

1. タイムスライシング

スケジューラは、一定の時間間隔でコンテキストを切り替えます。この間隔は、個々のプロセッサの速度、メモリキャッシュ階層の状態、およびシステム負荷によって異なります。同じプロセッサ上で同じ負荷がかかっている場合でも、システムクロックの周波数のわずかな変動により、間隔はわずかに変化します。

2. ページフォルト

スケジューラは、ページフォルトが発生するとプログラムを一時停止し、システムがページを取得する間、他のスレッドの実行を継続させます。ページフォルトの発生は実行中の他のプロセスに依存するため、コンテキストスイッチのタイミングは不確定になります。

並行プログラムの再現性を確保するために、外部スケジューラが使用されます。テスト対象プログラムは、このスケジューラへの呼び出しを追加するようにインストルメンテーションされます。このような呼び出しは、各スレッドの開始時と終了時、およびすべての同期要求の前に行われます。このスケジューラは、各スレッドに関連付けられたセマフォを維持することにより、実行スレッドを選択的にブロックし、任意の時点で実行可能なスレッドが1つだけになるようにします。このようにして、並列非決定性アプリケーションを直列実行シーケンスに変換し、再現性を実現します。直列化スケジューラによって行われるスケジューリング決定の数は、次式で与えられます。

(N * K / P)*{(N + P)!} ここで、 N = スレッド数、 K = 潜在的なコンテキストスイッチポイント、 P = プリエンプティブコンテキストスイッチの予算

決定論的スケジューリングを使用してより正確な結果を得るには、別の方法を選択できます。並行プログラムに適切な場所にプリエンプションをいくつか配置すると、データ競合に関連するバグを検出できます。^{[ 1 ]}バグはクラスターで見つかります。1 つのバグが存在すると、同じコード領域にさらに多くのバグが存在する可能性が高くなります。したがって、テスト プロセスの各パスで、バグのあるコード セクションが特定されます。次のパスでは、スケジューラ呼び出しを周囲に追加することで、これらのセクションをより徹底的に精査します。問題のある場所を異なる順序で実行できるようにすると、予期しない動作が明らかになることがあります。

この戦略により、アプリケーションがプローブ効果の影響を受けにくくなります。プローブ効果を引き起こすエラーの原因は、タスク作成の問題から同期や通信の問題まで多岐にわたります。タイミング関連のテストの要件: ^{[ 3 ]}

• 遅延時間は変動しなければならない
• 遅延地点は適切なプログラムの場所をカバーする必要がある
• プローブ効果を誘発するには、遅延ステートメントを挿入、削除、または移動する必要があります。

入力データセットごとのテストケース数は次のとおりです。

n C 1 + n C 1 + … + n C 1 = 2 n -1 ここで、n は同期、プロセス作成、通信呼び出しの総数です。

この方程式は指数関数的なオーダーを持つ。テストケースの数を減らすために、決定論的実行法（DET）または多重実行法（MET）のいずれかが用いられる。対処すべき様々な問題がある。

• 実行の遅延

遅延を追加するのは簡単な作業です。一般的な sleep() 文を使用して遅延を挿入できます。

• 遅延を挿入する場所を決定する

挿入箇所は遅延ポイントと呼ばれます。タイミング関連のテストケースの目的は、同期、通信、スレッド作成のエラーを検出することであるため、これらのエラーが発生する直前に遅延ステートメントが追加されます。

この方法は、定義と使用のペアという概念を適用して、テスト対象となるパスを決定します。

既知の結果を生成するために、システムに入力が与えられます。この入力と結果のペアは、以前の経験的結果や手動計算から取得できます。^{[ 4 ]}これは、関連するすべてのモジュールが統合されている場合にのみ実行できるシステムレベルのテストです。さらに、バグが存在することを示すだけで、バグの数、場所、性質に関​​する詳細な情報は提供しません。

これらのテストは主に科学シミュレーションに使用されます。シミュレーションの出力は予測できないことがよくあります。これらのシミュレーションは科学法則を記述しようとするため、理論における対称性はシミュレーションによって尊重されなければなりません。したがって、対称性の線に沿って入力条件を変化させ、得られた結果を外部から得られた結果と比較することにより、バグの存在を検出できます。^{[ 4 ]}

科学計算では、ほとんどのデータはシミュレーション条件の中央領域に集中しています。そのため、リアルタイムの実験データで境界値テスト^{[ 2 ]}を実行することは困難です 。そこで、境界条件を効果的にテストするために、シミュレーションの中心（例えば、図1のデータ値10の場合）を境界のいずれかに移動させます。

並列実装テストは通常​​、メッセージパッシングなどの分散メモリプログラミングモデルを使用するアプリケーションに使用されます。これらのテストは、プロセッサの規則的なグリッドを使用するプログラムによく適用されます。^{[ 4 ]}

このツールは、決定論的スケジューリングを使用して非決定性を排除します。以前に実行されたスケジュール パスを追跡し、新しいスケジュール パスが実行されるたびに保証します。^{[ 1 ]}