1つのプロセッサがn秒でジョブを実行すると、4つのプロセッサがn / 4秒を費やすと考えるのは論理的です。 「スピードアップ係数」という用語は、1つのプロセッサがジョブに費やす時間と、マルチプロセッサシステムが同じジョブに費やす時間の比率です。
S（p）= T s / T p
計算には、最適なT s 、つまり可能な限り最適な非並列アルゴリズムを使用することが重要です。
悪いニュース：この加速には限界があります。 これはアムダールの法則（アムダールの法則）と呼ばれ、その本質は次のとおりです。これは、通常のシングルプロセッサシステムでのタスクの外観です。
すでにおなじみの実行時間T sは 、複数のプロセッサに分散できる部分（並列化）-（1-f）T sと、並列化できない部分（シリアル）-fT sで構成されています。
複数のプロセッサの同じタスクのレイアウトはどのようになりますか？
合計実行時間Tpは、シリアル時間と、複数のプロセッサに割り当てた最大時間で構成されます（これらはすべて同時に実行されますが、最も遅く待機する必要があります）。 簡単にするために、それらはすべて同じ時間がかかると仮定しましょう。
加速係数は次の式で計算されます。
つまり、それはすべて、プログラムのどの部分を並列化できるかによって異なります（fのパーセントは、シリアルコードの量を意味します）。 f = 0％、つまり、絶対にすべてのコードが並列化された場合（実際には不可能）、使用するプロセッサーが多いほど、タスクはより速く完了し、比率は線形になります：10倍高速になります-10個のプロセッサーを使用し、 100万倍高速-100万プロセッサを購入します。 しかし、シリアルコードの5％を残し、95％を並列化する価値はあります。その場合、加速係数は20に等しくなり、ジャンプすることはできません。 さらに100万台のプロセッサを購入しても、プログラムは20倍高速に実行されます。 この悲しい事実が、さまざまなパーセンテージfの例でチャート上にどのように見えるかを以下に示します。
並列コードの効率について最も重要なことは、アルゴリズム自体の適切な設計であることがわかります。 細部が拡張性に大きく影響する可能性があります：アルゴリズムが通常クアッドコアプロセッサのリソースを使用する場合、おそらく8個以上のコアを通常使用することはできず、1年以内にプログラムを書き直す必要があります-結局、トランジスタの数ではなく、6か月ごとにコアの数が増加します！
適切な並列アルゴリズムを作成するには、問題の本質を理解し、別々の（理想的な）部分に分割して、すべてが異なるプロセッサで並列に実行されるようにする方法を考える必要があります。 行列Aにベクトルbを掛けるというかなり容量の大きい問題の例を見てみましょう。 結果は、サイズがベクトルbと同じであるベクトルyに書き込まれます。 ベクトルyの最初の値を取得するには、マトリックスの最初の行にベクトルbを乗算して、yの2番目の値を取得する必要があります。 ベクトルyの各要素は、他の要素とは独立して、つまり並列に考慮できることがわかります。
そのような各タスクのサイズは同じです-すべての行Aは同じサイズです（マトリックス密度などの詳細に触れるまで-ゼロが多数存在する可能性がありますが、これは実行時間に大きく影響しないと仮定します）。 タスク間に依存関係はなく、すべてのタスクが同じbを使用します。
別の例-データベースへのクエリ：
MODEL =「CIVIC」AND YEAR = 2001 AND（COLOR =” GREEN” OR COLOR =” WHITE”）;
要求は、そのような拠点から2001年のすべての緑または白の市民を取得しようとしています。
このようなタスクは3つの部分に分解できます：1つのプロセッサは2001年のすべてのCiviksのテーブルを形成し、別のプロセッサはすべての白と緑のマシンのテーブルを形成し（これら2つのクエリは並行して実行できます）、その後、これら2つのテーブルの結合の結果が答えとなります。
リクエストの構造を変更できます。これは同時実行性に影響を与える可能性があります
これらのパーツを異なるプロセッサに後で配布するためのタスクのパーツへの分割は、分解と呼ばれます。 行列にベクトルを掛けることは、問題の結果を分解する例です。結果（ベクトルy）はいくつかの独立した部分に分割され、それぞれが別々に計算されました。 行列乗算でも同じことができます。
最初の並列プログラム
Cilkを使用して最初の並列プログラムを作成します。 これは、基本的にタスクを並列化および同期するための便利なツールを備えたC言語であるプログラミング言語です。 Cilkは1994年にMITで開発され、無料で無料でしたが、2006年までに商用化され、C ++をサポートし始め、1年前にIntelによってGibletsで購入されました。もちろん、マルチコアシステム用の優れたプログラミング言語を持つことは有益です：結局のところ、彼ら自身がそのようなシステムを作り出しています。 コンパイラを無料で入手する方法がわかりません。大学には学生向けのアカデミック版があります（Cilk開発者は教授の良き友人です）。 しかし、Cilkは非常にシンプルで便利なので、検索する価値があると思います。 Pthreadsと比較しないでください。 プログラミングを開始するために知っておく必要があるのは、 cilk 、 spawn 、 syncの 3つのキーワードだけです。
例から始めることをお勧めします。Cでのお気に入りの再帰タスク-フィボナッチ数-を次に示します。
int fib (int n){ if (n<2) return n; else { int x, y; x = fib (n-1); y = fib (n-2); return (x+y); } }
そして、これがCilkの同じプログラムです：
cilk int fib (int n){ if (n<2) return n; else { int x, y; x = spawn fib (n-1); y = spawn fib (n-2); sync; return (x+y); } }
違いに気づきましたか？ 、）
cilkキーワードは、機能を示すために使用されます。 最も重要な単語はspawnとsyncです。 Spawnには、別のカーネルで実行する関数呼び出しが表示され、 syncは、spawnによって以前に呼び出されたすべての関数の完了を待機します。 それがラインです
x = spawn fib（n-1）;
別のカーネルで実行し、すぐに行y = spawn fib（n-2）を実行します。 結果を返す前に（ return（x + y） ）、実行が完了するまで待つ必要があります。そうしないと、変数xとyの値が正しくありません。 名前が示すように、これはsyncコマンドによって行われます。
本当に簡単？
そのようなプログラムは多くのコアをロードします！ n = 4の場合、このアルゴリズムは次のように機能します
コードのハイライトの色は、グラフノードの色に対応しています。 グラフの各レベルは同時に実行されます。つまり、n = 4の最初の呼び出しは、2と1、および1と0のそれぞれに対して、3と2の2つの関数を呼び出します。
このプログラムのソースコードは次のとおりです。
次の記事では、並列アルゴリズムのスケーラビリティがどのように計算されるか、どの種類のスケジューリングが利用でき、cilkで使用されるか、ソートと並列動的プログラミングについて触れます。