問題タブ [parallelism-amdahl]

これは宿題です。

問題: プログラムには 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つの物理コアがあります。

簡単に言えば、プログラムは 15% が順次部分で実行され、85% がその並列部分で実行されます。

無限の数のプロセッサで最大のスピードアップをどのように把握できますか?

また、たとえば、プログラムを最大速度の 80% まで高速化するには、いくつのプロセッサが必要かをどのように計算できますか?

アムダールの法則を使用。インターネットやグーグルなどを調べてみましたが、この単純な問題を解決するのに役立つものは何も見つかりませんでした!

追加のアルファ ベータ プルーニング実装を備えた従来のミニマックス問題ソルバーがあります。

アルファベータ実装のない Minimax は、基本的にツリー全体の深さ優先検索を最大深さまで実行します。alpha-beta でも同じことを行っていますが、いずれにせよ悪い結果につながるいくつかの枝を剪定します。

編集: コードをさらに調べた後、コードの 1 行にバグがあり、プログラムが「チート」していくつかの動きに従わなくなりました。実際のスピードアップ係数は現在 3.6 です。皆さんの時間を無駄にして申し訳ありません.. 今日のコンピューティングにはブレークスルーがありません。:/

私は自分の課題の 1 つでこの問題を与えられました。高速化、実行時間などのプロセスの原則を理解しています。しかし、この質問は不完全だと感じています。それは本当ですか、それとも解決できますか？もしそうなら、あなたは説明してもらえますか。

プログラムは、2GHz のクロック レートで動作するマシンの元のバージョンで実行されます。このプログラムには 450 マイクロ秒の CPU 時間がかかります。プログラム内のコードの 80% に影響するマシンに改善が加えられています。アムダールの法則に基づくと、この改善により、プログラムの実行時間が N% 高速化されます。N の値は? 答えを小数点以下 2 桁まで表してください。

355 秒を消費するシリアル部分と 645 秒を使用する並列部分を持つプログラム T があるとします。

プログラム T の並列実行時間をシリアル実行時間の 51% 以下にするために必要なプロセッサの数を調べるにはどうすればよいですか?