3

文章在这里

http://en.wikipedia.org/wiki/Reconfigurable_computing#Example_of_a_streaming_model_of_computation

计算流模型示例
问题：给定 2 个长度为 256 的字符数组：A[]和B[]。我们需要计算数组C[]使得C[i]=B[B[B[B[B[B[B[B[A[i]]]]]]]]]. 尽管这个问题是假设性的，但也存在类似的问题，但也有一些应用。

考虑上述问题的软件解决方案（C 代码）： 

for(int i=0;i<256;i++){
        char a=A[i];
        for(int j=0;j<8;j++)
                a=B[a];
        C[i]=a;
}

该程序将占用 CPU 大约 256*10*CPI 周期，其中 CPI 是每条指令的周期数。

这个问题可以在像 Haskell GHC 这样的高级编译器中优化吗？

4

1 回答 1

2

这个 wiki 页面没有多大意义（我认为它也在讨论页面中注明）。

示例机器毫无意义，因为它们忽略了这样一个事实，即要流水线化访问，您需要一个不仅可以维持 8 个同时请求（来自不同的流水线阶段）而且还可以在一个周期内完成它们的内存。以任何方式存储或拆分内存都不会真正起作用，因为它们都访问 B 的相同地址。

你可以稍微扩展一下，说你已经将 B 克隆到 8 个不同的内存单元中，但是你必须找到一些更复杂的控制器来保持一致性，否则你只能将它们用于读取。另一方面，如果你有这种内存，那么他们竞争的“CPU”应该被允许使用它。如果我们有这个存储的内存，一个具有乱序执行的现代 CPU 将能够发出以下指令，例如，在每次加载 1 个周期的相同假设下： 第一个周期：加载 a[i]，计算 i+ 1 第二循环：加载 a[i+1]，加载 b[a[i]]，计算 (i+1)+1 第三循环：加载 a[i+2]，加载 b[a[i+1]] , 加载 b[b[a[i]]], 计算 i+1+1+1 ... 所以它基本上和他们展示的特殊管道一样好，即使使用基本的编译器。

至于你关于编译器的问题 - 你没有具体说明你认为哪个功能可以解决这个问题。一般来说 - 这些问题很难通过编译器进行优化，因为您无法减轻内存依赖关系的延迟。换句话说，您首先必须访问 a[i]，然后 CPU 才有访问 b[a[i]] 的地址，然后它才有 b[b[a[i]] 的地址]]， 等等。为了猜测尚未访问的内存内容，编译器无能为力（即使它确实推测了，将它用于任何实际的事情也不明智，因为它可能会在实际负载到达时发生变化节目顺序）。

这类似于遍历链表的“指针追逐”问题——所需的地址不仅在编译时是未知的，而且在运行时也很难预测，并且可能会发生变化。

我并不是说这不能被优化，但它通常需要一些专用的硬件解决方案（例如内存银行），或者一些在使用上非常有限的花哨的推测算法。有关于该主题的论文（主要是硬件预取），例如 - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=765944

于 2013-09-23T08:29:52.780 回答