问题标签 [parallelism-amdahl]

这是家庭作业。

问题： 一个程序有 20% 的内存访问，50% 的乘法，其余的用于与两者无关的其他函数。如果需要 1.2 的整体加速，那么如果内存访问和乘法都得到同等改进，则需要多少加速。

我想如果我正在使用阿姆达尔定律寻找其中一个或另一个的加速，我想我知道如何做到这一点，但我不确定如何解决这个问题以找到每个问题的加速，如果它们得到同样的改进。

如果它只是在寻找内存访问，我想我会为 x 求解以下方程：

将这两个百分比结合起来并0.2 + 0.5 = 0.7在阿姆达尔定律中使用的关键是什么？

我正在研究使用 OpenMP 线程的 C++ 代码。我绘制了加速曲线与 OpenMP 线程数和理论曲线的关系（如果代码能够完全并行化）。

这是这个情节：

从这张图片中，我们可以说这段代码不可扩展（从并行化的角度来看）吗？即代码不是用 2 个 OpenMP 线程快两倍，用 4 个线程等快四...？

谢谢

我正在学习使用 Python 的 Multiprocessing 包来解决令人尴尬的并行问题，因此我编写了串行和并行版本来确定小于或等于自然数n的素数的数量。根据我从博客文章和Stack Overflow 问题中读到的内容，我想出了以下代码：

串行

平行

这是我得到的n = 10000000 （对于并行我请求 8 个进程）：

所以看起来我可以获得超过 3 倍的加速。这是我的问题：

1. 显然这不是线性加速，所以我能做得更好（或者我应该实际期望什么样的加速）？
2. 看起来阿姆达尔定律回答了这个问题，但我不知道如何确定我的程序的哪一部分是严格串行的。

任何帮助表示赞赏。

编辑：有 4 个物理内核，能够进行超线程。

简单来说，一个程序有 15% 运行在顺序部分，85% 是它的并行部分。

我如何计算出无限数量的处理器的最大加速比？

而且，我怎么能算出，比如说，需要多少个处理器才能将程序加速到其最大速度的 80%？

使用阿姆达尔定律。我试过浏览互联网、谷歌等。没有找到任何可以帮助我解决这个简单问题的东西！

我有一个经典的极小极大问题求解器，带有额外的 alpha-beta 修剪实现。

没有 alpha-beta 实现的 Minimax 基本上是对整个树进行深度优先搜索，直到某个最大深度。对于 alpha-beta，它的作用相同，只是它会修剪一些分支，这无论如何都会导致更糟糕的结果。

编辑：在进一步检查代码后，我在一行代码中发现了一个错误，导致程序“作弊”而不遵循某些动作。现在实际的加速因子是 3.6。很抱歉浪费大家的时间.. 今天在计算方面没有突破。：/

I have been given this problem in one of my assignments. I understand the principles of the process of speedup, execution time etc.. However, I feel that this question is incomplete. Is it true or can it be solved? If so can you please explain.

A program executes on the original version of a machine that runs at a 2GHz clock rate. The program takes 450 micro-seconds of CPU time. An improvement is made to the machine that affects 80% of the code in the program. Based on Amdahl’s law, this improvement would yield an N% speedup in the execution time for the program. What value is N? Express your answer to two decimal places.

我有一个 N 核处理器（在我的例子中是 4 个）。为什么 N 个线程上的 N 个完全独立的函数调用不快大约 N 倍（当然创建线程会产生开销，但请进一步阅读）？

看下面的代码：

我得到如下结果：

11756 20317

那大约快2倍。我也用大量的数字尝试过这个，比如num = 355555. 我得到了非常相似的结果：

177462588 346575062

为什么会这样？我完全了解阿姆达尔定律，并且多核处理器并不总是number_of_cores快几倍，但是当我有独立操作时，我会期待更好的结果。至少附近的东西number_of_cores。

更新：

如您所见，所有线程都按预期工作，所以这不是问题：

假设我有一个程序 T，它有一个消耗 355 秒的串行部分和一个使用 645 秒的并行部分。

如何找出我需要多少个处理器才能使程序 T 的并行运行时间小于或等于其串行运行时间的 51%？

在计算机体系结构中，阿姆达尔定律给出了在固定工作负载下执行任务的延迟的理论加速，这是资源得到改善的系统所期望的。

Slatency是整个任务执行延迟的理论加速；

s是受益于系统资源改进的部分任务执行延迟的加速；

p是整个任务的执行时间占改进前从系统资源改进中受益的部分的百分比。

Slatency = 1/[(1-p) + (p/s)]

这都是理论上的，它让我思考，什么时候不适用。估计 CPU 性能的准确度如何？

我有一个代码
（用于矩阵中最短路径的Floyd-Warshall 算法NxN），
具有三个for循环，一个在另一个循环中，并且循环数相同。

最后for，我通过三元运算进行了分配= <bool> ? <val1> : <val2>-基于比较以及是否True存在。

我使用 OpenMP 将第二个for与.#pragma omp parallel for

我无法计算代码的并行百分比和串行百分比以成功应用阿姆达尔定律来恢复理论加速。

我使用的是四个核心，所以我预计理论上的加速是 4。

X[i][j]是矩阵，其中每个元素都充当连接节点i和的边的权重j；INF如果它们未连接，则为宏（无限）。