問題タブ [parallelism-amdahl]

アムダールの法則では、1 プロセッサ システムから N プロセッサ システムへと、計算の分数 S を順次実行する必要がある場合の計算の最大スピードアップは、せいぜい 1 であると述べています。

分数Sを決定するための重要な計算のために、コードの実際の分析が行われている本やメモを知っている人はいますか?

私はアムダールの法則に戸惑い、パフォーマンスの向上とシリアルアプリケーションの部分を決定し、これを理解できません。

知られているのは次のとおりです。

CPU が 4 つあり、スピードアップ係数 (パフォーマンスの向上) が 3 倍だとします。fは何でしょう？

私の推測：

したがって、これらの値を式に入力します。

f = 0,11 と言うのは正しいですか? または、S(N) を 1 に設定する必要がありますか (つまり、3 で割ります)。それとも私は何か他のことを間違っていますか？

次のコードがあるとします。

14ここで、最終結果を並列で計算するために使用できる同一の CPUがあると仮定しましょう。

14上記のコードを実行するときにすべての CPU を使用することで得られる最大速度は? 1各操作（加算）には単位時間がかかるとしましょう。

私が見ているように、速度の向上は一般Ts/Tpに、CPU をTs使用したときに費やされた時間であり、利用可能なすべての CPU を使用したときに費やされた時間です。1Tp

私の例では、 CPU20 + 8*2 = 36でコードを実行するために時間単位を費やさなければなりません。1

次に、14cpus を使用すると、1時間単位を使用して の最初の14値を見つけることができますA。次に6cpus を使用すると、別の1時間単位を使用して の残りの6値を見つけることができますA。

の残りの値を見つけながらA、他の8cpu を使用して の8値Cを見つけ、時間単位Eを費やします。2

1 + (1 || 2) = 1 + 2 = 3したがって、合計で時間単位を費やすことにspeedupなります。つまり、36/3 = 12

これは正しいです？より良い速度を達成するために、より良い方法で CPU を使用することはできますか? また、アムダールの法則を使用して、結果をより迅速に見つけることは可能でしょうか? アムダールの法則によると、xが並列実行できないコード全体の部分である場合、最大速度アップは1/(x + (1 - x)/p)がp使用される CPU の数であるということです。したがって、私の場合、この数は に等しくなり14ます。

しかし、並行して実行できるコードの部分をどのように見つけることができるかわかりません。次の方程式を解くことにした場合：

それからx = 1/78。xしかし、コードを見るだけでこれを見つけるにはどうすればよいですか? 問題をより一般的に見ることにした場合、時間単位を必要とする最初のループを20並行して実行できます。ただし、2 番目のループでは、ループ内の操作を並列に実行できないため、16時間単位のうち、並列8に実行できるのは のみです。

したがって、並行して実行できる合計時間は です28。だからx = 8/36。

したがって、アムダールの法則から次の結果が得られます (wolframalpha から):

しかし、12上で説明したロジックに従うことで速度が向上しました。私は何を間違っていますか？

前もって感謝します

アムダールの法則を適用し、理論上の最大スピードアップを観察するために、並列化できるコードの割合 P を計算しようとしています。

私のコードは、(ライブラリ Eigen を使用して) 行列の乗算にほとんどの時間を費やしています。この部分は完全に並列化可能であると考えるべきですか?

「コンピュータ アーキテクチャ: 定量的アプローチ、第 5 版」を読み、350 ページの第 5 章の例を見ています。問題の例のスキャンが添付されています。私は、この例で彼らがどのように物事を行うかという論理を完全には踏襲していません。

私の質問は次のとおりです。

1. 0.3ns のサイクル タイムはどこから来ているのですか?
2. 200/0.3 はおよそ 666 サイクルです。これに従います。ただし、CPI の式に戻すと意味がありません。0.2% (0.002) x 666 は 1.332 であり、1.2 ではありません。ここで何が起こっているのですか？
3. 彼らが「すべてのローカル参照を備えたマルチプロセッサは 1.7/0.5 = 3.4 倍速い」と言うとき、どこからそれを得ているのでしょうか? 意味: 与えられた情報のどこにも、ローカル通信が 2 倍高速であるとは記載されていません...

どんな助けでも大歓迎です。

Martin Thompsonは、CAS に依存する参照に依存する STM は、最終的にアムダールの法則によって制限されると主張しています。アムダールの法則は、並列プログラムの最大パフォーマンスは、プログラムの順次 (非並列) 部分によって制限されるというものです。Martin Thompson は、CAS は本質的に非並列であると言っていますか?

はじめに:

私は現在、マルチスレッドプログラムを使用してシーケンシャルプログラムをベンチマークするソフトウェアに取り組んでいます。私のハードウェアには 24 個のコアがあり、RAM は 16GB あります。私のプログラムは Java で書かれていますが、プロットが必要なため MATLAB から実行されます。MATLAB を開くと、次のメッセージが表示されます。

仮説

ここで、アムダールの法則に従って、最大のパフォーマンス向上は 1/(B-(1-B)/P) として定義されます。ここで、B は順次部分、P はプロセッサの数です。私の場合、B = 0.01、(1-B = .99)、P = 24 です。これにより、理論上の最大パフォーマンスが約 20 向上します。

今、私が理解parallelGCThreadsしているように、これは利用可能なガベージ コレクター スレッドの最大数です。私のプログラムで集中的なテストを行った後、私が達成できた比率の最大増加は 7.5 倍であり、理論上の 20 にはほど遠いようです。ただし、P = 8 に置き換えると、理論上の限界は次のようになります。これは、私のプログラムで取得したものに非常に近いものです。

質問

parallelGCThreadsアムダールの法則が P = 24 ではなく P = 8 で使用されるように、実際にスレッドの量を制限しますか?

前もって感謝します！

これは宿題です。

問題: プログラムには 20% のメモリ アクセスがあり、50% の乗算があり、残りはどちらにも関係のない他の関数に使用されます。全体で 1.2 倍の高速化が必要な場合、メモリ アクセスと乗算の両方が同等に改善された場合、両方にどれだけの高速化が必要になるか。

アムダールの法則を使用してどちらか一方のスピードアップを探している場合、これを行う方法はわかっていると思いますが、この問題にアプローチして、それらが等しく改善された場合にそれぞれのスピードアップを見つける方法がわかりません。

メモリアクセスを探しているだけなら、x について次の方程式を解くと思います。

2 つのパーセンテージを組み合わせて0.2 + 0.5 = 0.7アムダールの法則で使用することが鍵ですか?

OpenMP スレッドを使用する C++ コードに取り組んでいます。OpenMP スレッドの数と理論上の曲線 (コードを完全に並列化できた場合) に対する高速化曲線をプロットしました。

ここにこのプロットがあります:

この図から、このコードは (並列化の観点から) スケーラブルではないと言えますか? つまり、コードは 2 つの OpenMP スレッドで 2 倍高速ではなく、4 スレッドで 4 高速ではありません。

ありがとう

私は恥ずかしいほど並列問題に Python の Multiprocessing パッケージを使用することを学んでいるので、自然数n以下の素数を決定するための直列バージョンと並列バージョンを作成しました。ブログ投稿とスタック オーバーフローの質問から読んだ内容に基づいて、次のコードを思いつきました。

シリアル

平行

n = 10000000に対して得られるものは次のとおりです (並列の場合、8 つのプロセスを要求します)。

それで、3倍強のスピードアップが得られるようです。ここに私の質問があります：

1. 明らかに、これは直線的なスピードアップではありません。では、どれだけ改善できるでしょうか (または、現実的にどのようなスピードアップを期待すべきでしょうか)。
2. アムダールの法則がこれに答えているように見えますが、プログラムのどの部分が厳密にシリアルであるかを判断する方法がわかりません。

どんな助けでも大歓迎です。

編集：ハイパースレッディングが可能な4つの物理コアがあります。