マルチコアcpuの分岐予測に及ぼすマルチスレッドの影響をテストする

前言:

現代のcpuはいずれも流水ライン、分岐予測機能があり、CPUの分岐予測精度は98%以上に達することができるが、予測に失敗すると流水ラインが失効し、性能損失が深刻である.
CPUが使用するブランチ予測技術は以下のように参照できる.
プロセッサ分岐予測研究の歴史と現状.pdf
同時にマルチスレッドプロセッサ上の動的分岐予測器の設計方案の研究.pdf
これらの特性を正しく利用すれば、効率的なプログラムを書くことができます.
例えばif,else文を書くときは,確率イベントをif文に,小確率イベントをelse文に置くべきである.
しかし、通常、このような考慮は単一スレッドに基づいており、複数のスレッドが同じ場所のコードを同時に実行するなど、マルチスレッドで予期せぬ状況が発生する可能性がある.

テスト:

以下、Intel Core i 5のいくつかのマルチスレッド分岐予測に基づくテストを行う.
テストの考え方(実際のテストでは以下の3つの状況だけでなく、詳細は以下のテスト結果を参照してください):
2つのスレッドは同じコードを実行し、ifは常にtrueであると判断します.
2つのスレッドは同じコードを実行し、1つのif判断は常にtrueであり、もう1つのif判断はtrueでありfalseである.
2つのスレッドは異なるコード(論理機能は同じで、位置が異なるだけ)を実行し、1つのif判断は常にtrueであり、もう1つのif判断はtrueであり、falseである.
コードは次のとおりです.
ここでtest 1は同じコードをテストし、偶数パラメータが入力されるとif判定は常にtrueであり、奇数パラメータが入力されるとif判定はtrueでfalseである.
test 2関数は異なる箇所のコードをテストし,偶数パラメータが入力されるとif判定は常にtrueであり,奇数パラメータが入力されるとif判定はtrueでfalseである.

import java.util.concurrent.CountDownLatch;
public class Test {
	public static int loop = 1000000000;
	public static int sum = 0;
	public static CountDownLatch startGate;
	public static CountDownLatch endGate;
	
	public static void test1(int x1, int x2) throws InterruptedException{
		startGate = new CountDownLatch(1);
		endGate = new CountDownLatch(2);
		new Thread(new T1(x1)).start();
		new Thread(new T1(x2)).start();
		Test.startGate.countDown();
		Test.endGate.await();
	}
	public static void test2(int x1, int x2) throws InterruptedException{
		startGate = new CountDownLatch(1);
		endGate = new CountDownLatch(2);
		new Thread(new T1(x1)).start();
		new Thread(new T2(x2)).start();
		Test.startGate.countDown();
		Test.endGate.await();
	}
}

class T1 implements Runnable{
	int xxx = 0;
	public T1(int xxx){
		this.xxx = xxx;
	}
	@Override
	public void run() {
		try {
			int sum = 0;
			int temp = 0;
			Test.startGate.await();
			long start = System.nanoTime();
			for(int i = 0; i < Test.loop; ++i){
				temp += xxx;
				if(temp % 2 == 0){
					sum += 100;
				}else{
					sum += 200;
				}
			}
			Test.sum += sum;
			long end = System.nanoTime();
			System.out.format("%s, T1(%d): %d
", Thread.currentThread().getName(), xxx, end - start);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}finally{
			Test.endGate.countDown();
		}
	}
}
class T2 implements Runnable{
	int xxx = 0;
	public T2(int xxx){
		this.xxx = xxx;
	}
	@Override
	public void run() {
		try {
			int sum = 0;
			int temp = 0;
			Test.startGate.await();
			long start = System.nanoTime();
			for(int i = 0; i < Test.loop; ++i){
				temp += xxx;
				if(temp % 2 == 0){
					sum += 100;
				}else{
					sum += 200;
				}
			}
			Test.sum += sum;
			long end = System.nanoTime();
			System.out.format("%s, T2(%d): %d
", Thread.currentThread().getName(), xxx, end - start);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}finally{
			Test.endGate.countDown();
		}
	}
}

テストの状況が多いので、以下のように簡潔に説明します.
1つのtest 1関数には、test 1(2,3)のように2つの結果2.1 s,2.2 sが得られ、2つのスレッドが同じコードを実行することを示し、1つのif判断は常にtrue(2は偶数)、もう1つの常にfalse(3は奇数)であり、そのうち1つ目のスレッドが平均して1回の計算を実行する時間は2.1 sであり、2つ目のスレッドが平均して1回の計算を実行する時間は2.2 sである.
テストしたmain関数には、10回ごとに2つのforループがあります.テスト結果を説明するときは、次のように簡単に表示します.
1行のデータはmain関数を1回実行した結果を表し、その後の時間は大まかな平均計算で得られた.
test1(2,3)
2.1s
2.1s
test1(2,4)
2.1s
2.1s
main関数:

	public static void main(String[] args) throws InterruptedException {
		for(int i = 0; i < 10; ++i){
			test1(2, 3);
		}
		System.out.println("!!!!!!!!!!!!!!!!!!!!");
		for(int i = 0; i < 10; ++i){
			test1(2, 4);
		}		
	}

テスト結果は次のとおりです.
1
test1(2,3)
2.0s
2.0s
test1(2,4)
1.8s
2.0s
2
test1(2,4)
1.3s
1.3s
test1(2,3)
1.3s
1.8s
3
 
 
 
 
 
 
4
test2(2,3)
1.3s
1.7s
test2(2,4)
1.3s
1.9s
5
test2(2,4)
1.3s
1.3s
test2(2,3)
1.3s
1.8s
まず1行目のデータを解析するとtest 1(2,3)の結果が最悪であり,2つのスレッドが同じコードを実行し,両者の分岐予測結果が互いに干渉し,常に不適切であることが明らかになった.
しかし、なぜ後ろのtest 1(2,4)の結果も悪いのでしょうか.2つのスレッドは同じコードを実行していますが、2つのスレッドのifの判断は常にtrueです.なぜ時間がかかるのでしょうか.
簡単な推測1:以前のtest 1(2,3)がtest 1(2,4)の分岐予測に影響した結果かもしれないが,分岐予測器には履歴表があり,前に実行した分岐予測履歴が後の選択に影響する.
さらに2行目を解析すると、test 1(2,4)が最良の結果であり、2つのスレッドは同じコードを実行し、ifは常にtrueであることが明らかになった.2行目のtest(2,3)の結果を見ると、1行目より良いのに、なぜこれと1行目のデータがこんなに悪いのですか?
簡単な推測2:異なる核には独自の分岐予測器があるはずだ.
さらにtest 2関数のテスト結果を見ると、4行目から見るとtest 2(2,3)の結果は予想に合っているが、明らかにtest 2(2,4)の結果は理想的ではない.なぜ2つのスレッドが異なる場所のコードを実行し、if判断は常にtrueであり、結果は異なるのか.
単純推定3:test(2,3)の結果の影響で,単純推定1と2を組み合わせると,なぜtest(2,4)の前の結果が1.3 s,後の結果が1.9 sであったのかが理解できる.
さらに5行目のデータを分析し、このデータは予想に完全に合っています.

まとめ:

推定:i 5の分岐予測器は混合分岐予測器である.各コアには履歴表があり、各コアには独自の分岐予測器があります.
マルチスレッドでのブランチ予測は楽観的ではなく,複数のスレッドを避けて同じコードを実行でき,ブランチ予測条件の結果が常に変化する場合は避ける.