Scalable parallelism とは

ソフトウェアは、より大きな問題を解決するために追加のプロセッサを使用することができればスケーラブルな並列性を示すと言われる。すなわち、この用語はグスタフソンの法則が保持するソフトウェアを指す。実行時間が1つまたは複数のループによって支配され、それぞれが配列のすべての要素を更新するプログラムを考えてください。たとえば、次の有限差分熱方程式のステンシル計算があります。
 (i-1)+ A(i)+ A(i)+ A(i + 1))* .25 // R = 0.25での明示的な前進差分i:= 1からN-1への終わりdo A(i):= new(i)end end
上記のコードでは、各 "i"ループのすべての反復を同時に実行することができます。つまり、それぞれを並列ループにすることができます。そのような場合、配列サイズNの問題と同じように、配列サイズ2Nの問題に対して2倍のプロセッサーを有効に使用することが可能です。この例のように、スケーラブルな並列処理は通常、データ並列処理の一形態です。この形式の並列処理は、しばしばループの自動並列化のターゲットになります。
分散コンピューティングシステムおよび非一様メモリアクセスアーキテクチャは、通常、多数のプロセッサに最も容易にスケーリングされるため、スケーラブルな並列性を示すソフトウェアの本来の目標と思われる。しかしながら、スケーラブルな並列性を有するアプリケーションは、そのようなシステム上で効果的に動作するには(ソフトウェアが混乱しない限り)十分に粗い粒子の並列性を有さないことがある。上記の例では、2番目の「i」ループは恥ずかしく並行していますが、最初のループでは各反復でいくつかの前の反復で生成された結果が必要です。したがって、第1のループでは、並列化はプロセッサ間の広範な通信または同期を必要とすることがあり、そのような相互作用が非常に低いオーバヘッドを有する場合には正味のスピードアップをもたらすだけであるか、またはこの問題を解決するためにコードを変換できる局所性/スケーラブルな並列性最適化)。