前回までに、マルチコアによる性能向上に関連して依存関係やオーバーヘッドの話をしました。では結局の所、性能はどのくらい上がるのでしょうか。特にマネジメントとしては大変気になるところです。しかし、聞いても誰も答えられず、やってみないとわかりません、といったマネジャーの機嫌が悪くなる回答しか得られないことがほとんどです。この問題について2回に分けて考えてみたいと思います。
今回は、まず一つのアプリケーションでの並列性能向上を概算する方法について説明し、次回、システムになったときに性能見積が困難になる要因について考えてみます。
下の図のようなソースコード構成を持つアプリケーションを考えます。ソースコードは図のようにAからEまでの部分に分かれ、Aから開始し、それぞれ最大一回ずつ実行されるとします。括弧内は実行時間です。依存関係については以下のようになっているとします。
・ データ依存関係：Aで生成されたデータをBとCが使い、BとCでそれぞれ生成されたデータをEで使う
・ 制御依存関係：Cの結果によりD-1またはD-2のどちらかが実行される
これらの依存関係をグラフとして表現すると下図右のようになります。実線はデータ依存関係、破線は制御依存関係で、矢印の始点側の処理が終わらないと終点側の処理を開始できない、という関係を表現しています。
これをシングルプロセッサで実行すると、D-1が実行される場合は150、D-2が実行される場合は170の実行時間となります。下図（1）はD-2が実行される場合を表しています。
次にデュアルコアで並列化することを考えます。コア間通信オーバーヘッドを考えなければ、BとCを異なるコアに、D-1（またはD-2）とEを異なるコアに割り当てることが、最も高速化される割当で、下図（2）に示すようにD-1が実行される場合は90、D-2が実行される場合は100の実行時間となります。D-1が実行される場合の並列性能向上は150÷90で約1.67倍、D-2が実行される場合は170÷100で1.7倍の性能向上となり、コア数が2でも2倍高速になるわけではありません。
さらにコア間通信オーバーヘッドについて考えます。ここでは、コア間通信の受信タスクは、送信タスクの終了から時間15以降に開始可能、コア間通信がないタスクは即座に実行可能と仮定します。この場合にはBよりもCの実行時間が長いため、BをAと異なるコアに配置した方が早く終了します。上図（3）の上段はD-1、D-2それぞれの場合の最適解を示しています。この場合、どちらの実行時間も105であり、並列性能向上はD-1の場合150÷105で約1.43倍、D-2の場合は170÷105で約1.62倍となり、少し悪化します。
コア間通信オーバーヘッドが大きくなるに従い性能は悪化します。上図（3）の下段に示すように、コア間通信オーバーヘッドが20を超えるとBとCをAと同じコアで実行し、Cを先に実行するスケジューリングが最適になります。さらに70を超えるとすべての処理を一つのコアで実行させる方が、マルチコア実行よりも実行時間が短くなります。
すなわち、このような単純なプログラムでも条件分岐の結果やコア間通信オーバーヘッドによって2コアで1.7倍高速化できる場合からまったく速くならない場合まで変動することがわかります。
今回の例には含まれないアプリケーション並列化の代表例としてループ並列化があります。
例えば上の例で処理Aがループ構造を持ち、ループ回転間のデータ依存がなく、一回転の実行時間が1で100回転するとします。この場合、2個のコアにそれぞれ50回転ずつ割り当て、ループ並列化の前処理時間をP、後処理時間をQとすると、両方のコアにおいて(P+1×50+Q)の実行時間として概算できます。
このようにターゲット実行環境における各種数値が得られれば概算は可能であることがわかります。
コメントをお書きください