维基百科 "Reconfigurable computing"代码示例可以在像 Haskell 这样的高级编译器中解决吗？

Question

文章在这里

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

Example of a streaming model of computation
Problem: We are given 2 character arrays of length 256: A[] and B[]. We need to compute the array C[] such that C[i]=B[B[B[B[B[B[B[B[A[i]]]]]]]]]. Though this problem is hypothetical, similar problems exist which have some applications.

Consider a software solution (C code) for the above problem:

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

This program will take about 256*10*CPI cycles for the CPU, where CPI is the number of cycles per instruction.

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

Answer 1

这个 wiki 页面没有多大意义(我认为它也在讨论页面中提到)。

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

你可以稍微扩展一下，说你已经将 B 克隆到 8 个不同的内存单元中，但是你必须找到一些更复杂的 Controller 来保持一致性，否则你将只能使用它们阅读。 另一方面，如果你有这种内存，那么他们竞争的“CPU”应该被允许使用它。如果我们有这个分组内存，一个乱序执行的现代 CPU 将能够发出以下指令，例如，在每次加载 1 个周期的相同假设下: 第一个循环:加载 a[i]，计算 i+1 第 2 次循环:加载 a[i+1]，加载 b[a[i]]，计算 (i+1)+1 第3次循环:加载a[i+2]，加载b[a[i+1]]，加载b[b[a[i]]]，计算i+1+1+1 ... 因此，即使使用基本的编译器，它基本上也能像他们展示的特殊管道一样好。请注意，现代 CPU 可以在执行窗口中超前查找独立操作，但如果编译器执行循环展开(这是大多数语言支持的基本功能)，它可以以更容易的方式重新排序操作以便 CPU 发出它们。

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

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

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