并行评估特定值的函数

Question

这个问题可能看似含糊不清,但让我解释一下.

假设我们有一个函数f(x,y,z ....),我们需要在点(x1,y1,z1 .....)找到它的值.

最简单的方法是将(x,y,z ......)替换为(x1,y1,z1 .....).

现在假设该函数在评估中花费了大量时间,我想并行化算法来评估它.显然它也取决于功能的性质.

所以我的问题是:在"思考"并行化f(x,y,z ......)时,我必须寻找什么约束？

如果可能,请分享学习链接.

Answer 1

以这样一般的方式提出问题不允许给出非常具体的建议.

我将通过寻找使用密切交互的变量组来评估或重写函数的方法开始分析,创建可用于进行最终评估的中间表达式.您可能会找到一种方法来执行此操作,涉及从变量本身到最终函数的子表达式层次结构.

通常,这种评估树越短越宽,并行度越大.要记住,有两个注意事项会减损"更多并行性更好".

一方面,高度并行的方法实际上可能涉及比原始"串行"方法更多的总计算.事实上,在这方面会有一些效率损失,因为串行方法可以利用所有先前的子表达式评估并最大化它们的重用.

另一方面,并行评估通常会比选择的串行评估具有更差的舍入/准确性行为,以提供良好或最佳的误差估计.

在涉及矩阵的评估方面已经做了很多工作,其中函数值如何依赖于它的参数通常有很多对称性.因此,熟悉那里开发的数值线性代数和并行算法是有帮助的.

众所周知的另一个领域是多元多项式和有理函数.

当函数是超验的时候,人们可能希望进行一些变换或重构,使依赖更容易处理(代数).

与您的问题没有直接关系的算法是通过多个参数分摊计算函数值的成本.例如,在计算常微分方程的解时,可能存在"多步"方法,其通过多次重复使用这些值来共享在中间点评估导数的成本.

我建议您加快对功能评估的关注表明您计划执行多个评估.因此,您可能会考虑如何利用先前的评估或以相关参数执行评估,从而有助于您搜索并行性.

补充: 搜索策略的一些链接和讨论

大多数作者使用短语"并行函数评估"来表示在多个参数点评估相同的函数.

参见例如:

寻找Gaurav Kalra询问的材料的搜索策略应该尽量避免这些.例如,我们可能会在搜索字词中包含"细粒度".

专注于特定类型的功能也是有效的,例如"多项式评估"而不是"功能评估".

例如,我们对一些众所周知的"快速"评估技术进行了处理,这些技术应用于基于GPU的计算设计:

(来自他们的摘要)"在这里,我们已经解决了快速求和算法(快速多极方法和快速高斯变换),并应用算法重新设计以获得GPU的性能.所获得的性能改进的进展说明了为大规模并行制定算法的练习GPU的架构."

可能值得排除的另一个搜索词是"流水线".该术语总是讨论在进行多项功能评估时可以使用的并行性.计算的早期阶段可以与后期阶段并行完成,但是在不同的输入上.

这是一个人们可能想要排除的搜索词.或不.

这是一篇讨论有限域GF(p)上n-变量多项式评估的n倍加速的论文.这可能对加密应用程序有直接的兴趣,但通过改进的Horner方法的方法可能对其泛化的潜力感兴趣:

[用于评估有限环上非结构函数的位和字级算法的比较 - Sunar和Cyganski]
http://www.iacr.org/archive/ches2005/018.pdf

"我们对Horner的算法进行了修改,用于评估在有限环和场上定义的任意n变量函数.如果域是有限域GF(p),多元Horner多项式评估的复杂度从O(p ^)得到改善. n)到O((p ^ n)/(2n)).我们证明了所提算法的最优性."

多元有理函数可以简单地视为两个这样的多项式函数的比率.对于单变量有理函数的特殊情况,其可以在近似基本超越函数和其他函数中特别有效,可以通过有限(分别截断)连续分数来评估,其会聚(部分分子和分母)可以递归地定义.

继续分数评估的主题允许我们将这个主题与一些熟悉的数值线性代数并行性相关联的最终链接:

[LU分解和连续分数的并行评估 - ÖmerEgecioglu]
http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/lu-cf98.pdf

"使用O(n/log(n))处理器,可以在对数平行时间内最优地计算一般连续分数(CF)的前n个收敛."