algorithm - 并行评估特定值的功能

Question

这个问题似乎很模糊，但让我解释一下。
假设我们有一个函数f（x，y，z…），我们需要在点（x1，y1，z1…）找到它的值。
最简单的方法是将（x，y，z…）替换为（x1，y1，z1…）。
现在假设函数的求值时间很长，我想将算法并行化来求值显然，这也将取决于功能的性质。
所以我的问题是：在“思考”使f（x，y，z…）并行时，我必须寻找哪些约束条件？
如果可能的话，请分享学习链接。

Answer 1

以这种笼统的方式提出这个问题不允许提出非常具体的建议。
我将从寻找方法来计算或重写函数开始分析，使用一组紧密交互的变量，创建可用于进行最终计算的中间表达式。您可能会找到一种方法来实现这一点，它涉及子表达式的层次结构，这些子表达式从变量本身指向最终函数。
一般来说，这样的评估树越短越宽，并行度就越高。有两个值得注意的注意事项可以提醒我们，有损于“更多的并行性更好”
首先，一个高度并行的方法实际上可能比原来的“串行”方法需要更多的总计算量。事实上，在这方面的一些效率损失是可以预料的，因为串行方法可以利用所有先前的重新评估，并最大限度地利用它们。
另一方面，平行评估通常比选择给出良好或最佳误差估计的串行评估具有更差的舍入/精度行为。
在涉及矩阵的求值方面已经做了很多工作，通常情况下，函数值如何依赖于它的参数有很多对称性。因此，它有助于熟悉数值线性代数和并行算法已经开发了那里。
另一个众所周知的领域是多元多项式和有理函数。
当函数是超越的时，人们可能希望进行一些转换或重构，使依赖关系更容易处理（代数）。
与您的问题不直接相关的是算法，这些算法将计算函数值的成本分摊到多个参数上。例如，在计算常微分方程的解时，可能有“多步骤”方法通过多次重用这些值来分担在中间点计算导数的成本。
我建议您考虑加快对功能的评估，建议您计划执行多个评估。因此，您可能会考虑如何利用先前的求值，或在相关参数处执行求值，从而有助于搜索并行性。
附加：搜索策略的一些链接和讨论
大多数作者使用“并行函数求值”来
意思是在多个参数点计算同一个函数。
例如，请参见：
[粗粒度并行函数求值——Rulon和Youssef]
http://cdsweb.cern.ch/record/401028/files/p837.pdf
寻找Gaurav karla所要求的材料的搜索策略
应该尽量避免这些。例如，我们可以包括
“细粒度”在我们的搜索条件。
专注于特定类型的功能也是有效的，例如。
“多项式求值”而不是“函数求值”。
举个例子，我们有一些著名的技术
对于应用于基于GPU计算的设计的“快速”评估：
[如何获得高效的GPU内核--Cruz、Layton和Barba]
http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.3457v1.pdf
（摘自他们的摘要）“在这里，我们处理了快速求和
算法（快速多极方法和快速高斯变换）；
并应用算法重新设计以获得
GPU绩效改进的进展
说明了为
GPU的大规模并行架构。”
另一个值得排除的搜索词是“流水线”。
这个术语总是讨论可以
当要进行多个功能评估时使用。早起
计算的各个阶段可以与后面的并行进行
阶段，但输入不同。
所以这是一个我们可能想排除的搜索词或者不。
这里有一篇论文讨论了n个变量的n倍加速
有限域gf（p）上的多项式求值。这可能是
对密码应用程序有直接的兴趣，但是
通过改进的霍纳方法可能对
其推广潜力：
[位级和字级评估算法的比较
有限环上的非结构函数——Sunar和Cyganski]
http://www.iacr.org/archive/ches2005/018.pdf
“我们对Horner的评估算法进行了修改
在有限环和有限域上定义的任意n元函数。
... 如果域是有限域GF（p）的复杂性
多元horner多项式估计是由o（p^n）改进而来的
到o（（p^n）/（2n））。我们证明了该算法的最优性。”
多元有理函数可以简单地看作
两个这样的多项式函数的比率对于特殊情况
一元有理函数，它可以是
逼近初等超越函数的有效性
其他的，可以通过有限（分别截短的）
连续分数，其收敛性（部分分子
和分母）可以递归定义。
连续分数评估的主题让我们可以
最后一个链接将这个主题与一些熟悉的
数值线性代数的并行性：
[lu因子分解与连分式的并行计算
--厄默·埃吉奥卢]
http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/lu-cf98.pdf
“一般连分式的前n个收敛
（cf）可在对数并行中优化计算
使用O（n/log（n））处理器的时间。”