并行成本和并行工作有什么区别？
What's the difference between parallel cost and parallel work?
我读了一篇论文，其中 parallel cost for (parallel) algorithms is defined as CP(n) = p * T P(n)，其中 p 是处理器数量，T 是处理时间，n 是输入。如果 CP(n) 近似恒定，即如果算法使用两个处理器而不是同一个处理器，则算法是 cost-optimal输入只需一半时间
还有一个概念叫做并行工作，我没有完全理解。
论文称它测量执行的并行 OP 的数量。
一个算法是 work-optimal，如果它执行的 OPs 与其顺序对应物（渐近）一样多。 成本最优算法总是工作最优，但反之则不然。
谁能说明并行工作的概念，并说明与并行成本的异同？
听起来并行工作只是对所有进程并行执行的指令总数 运行 的一种度量，但并行的只计算一次。如果是这样，那么它与并行成本方程式中的时间项关系更密切。这样想：如果算法的并行版本比顺序版本运行更多的指令——这意味着它不是工作最优，假设所有指令都是持续时间相等。通常这些额外的指令位于并行算法的开始或结束处，并被视为并行算法的开销。它们可以对应于额外的记账或沟通或结果的最终聚合。
因此，不是工作最优的算法不可能是成本最优的。
另一种调用 "parallel cost" 的方法是 "cost of context switching" 尽管它也可能由不同线程之间的相互依赖性引起。
考虑排序。
如果您并行实施 Bubble Sort，其中每个线程只进行下一次比较，您将在 "parallel" 中 运行 付出巨大的代价，以至于它将本质上是算法的混乱顺序版本，您的并行工作基本上为零，因为大多数线程大部分时间都在等待。
现在将其与 Quick Sort 进行比较，并为原始数组的每个拆分实现一个线程 - 线程不需要来自其他线程的数据，渐近地更大的起始阵列旋转这些线程的成本将由完成工作的并行性质支付......如果系统具有无限的内存带宽。实际上，与内存访问通道相比，旋转更多的线程是不值得的，因为通过共享顺序访问内存，线程之间仍然具有不可见的（从代码角度来看）依赖性
短
我认为并行成本和并行工作是同一枚硬币的两面。它们都是加速的措施，
其中后者是使前者成为可能的理论概念。
长
我们把n维向量加法看成一个容易并行化的问题，因为它可以分解成n个独立的任务。
问题本质上是work-optimal，因为如果算法并行运行，parallel work不会改变，有总是需要添加 n 个矢量分量。
考虑到 并行成本 如果不在（虚拟）机器上执行算法就无法完成，在这种情况下会出现内存带宽不足等实际限制。因此，如果硬件（或硬件访问模式）允许完美执行和划分问题 - 和时间。
成本最优 是一个更强烈的需求，正如我现在意识到的，这只是 efficiency
的另一个例证
在正常情况下，成本最优算法也将是工作最优，
但是如果通过缓存、内存访问模式等获得的加速是超线性的，
即两个处理器的执行时间是十分之一而不是预期的一半，执行更多工作的算法可能不是工作最优，但仍然是成本最优.
我读了一篇论文，其中 parallel cost for (parallel) algorithms is defined as CP(n) = p * T P(n)，其中 p 是处理器数量，T 是处理时间，n 是输入。如果 CP(n) 近似恒定，即如果算法使用两个处理器而不是同一个处理器，则算法是 cost-optimal输入只需一半时间
还有一个概念叫做并行工作，我没有完全理解。 论文称它测量执行的并行 OP 的数量。 一个算法是 work-optimal，如果它执行的 OPs 与其顺序对应物（渐近）一样多。 成本最优算法总是工作最优，但反之则不然。
谁能说明并行工作的概念，并说明与并行成本的异同？
听起来并行工作只是对所有进程并行执行的指令总数 运行 的一种度量，但并行的只计算一次。如果是这样，那么它与并行成本方程式中的时间项关系更密切。这样想：如果算法的并行版本比顺序版本运行更多的指令——这意味着它不是工作最优，假设所有指令都是持续时间相等。通常这些额外的指令位于并行算法的开始或结束处，并被视为并行算法的开销。它们可以对应于额外的记账或沟通或结果的最终聚合。
因此，不是工作最优的算法不可能是成本最优的。
另一种调用 "parallel cost" 的方法是 "cost of context switching" 尽管它也可能由不同线程之间的相互依赖性引起。
考虑排序。
如果您并行实施 Bubble Sort，其中每个线程只进行下一次比较，您将在 "parallel" 中 运行 付出巨大的代价，以至于它将本质上是算法的混乱顺序版本，您的并行工作基本上为零，因为大多数线程大部分时间都在等待。
现在将其与 Quick Sort 进行比较，并为原始数组的每个拆分实现一个线程 - 线程不需要来自其他线程的数据，渐近地更大的起始阵列旋转这些线程的成本将由完成工作的并行性质支付......如果系统具有无限的内存带宽。实际上，与内存访问通道相比，旋转更多的线程是不值得的，因为通过共享顺序访问内存，线程之间仍然具有不可见的（从代码角度来看）依赖性
短
我认为并行成本和并行工作是同一枚硬币的两面。它们都是加速的措施， 其中后者是使前者成为可能的理论概念。
长
我们把n维向量加法看成一个容易并行化的问题，因为它可以分解成n个独立的任务。
问题本质上是work-optimal，因为如果算法并行运行，parallel work不会改变，有总是需要添加 n 个矢量分量。
考虑到 并行成本 如果不在（虚拟）机器上执行算法就无法完成，在这种情况下会出现内存带宽不足等实际限制。因此，如果硬件（或硬件访问模式）允许完美执行和划分问题 - 和时间。
成本最优 是一个更强烈的需求，正如我现在意识到的，这只是 efficiency
的另一个例证在正常情况下，成本最优算法也将是工作最优， 但是如果通过缓存、内存访问模式等获得的加速是超线性的， 即两个处理器的执行时间是十分之一而不是预期的一半，执行更多工作的算法可能不是工作最优，但仍然是成本最优.