7

这是一个教科书问题，涉及重写一些 C 代码以使其在给定的处理器架构上表现最佳。

给定：针对具有 4 个加法器和 2 个乘法器单元的单个超标量处理器。

输入结构（在别处初始化）：

struct s {
    short a;
    unsigned v;
    short b;
} input[100];

这是对该数据进行操作的例程。显然，必须确保正确性，但目标是优化其中的废话。

int compute(int x, int *r, int *q, int *p) {

    int i;
    for(i = 0; i < 100; i++) {

        *r *= input[i].v + x;
        *p = input[i].v;
        *q += input[i].a + input[i].v + input[i].b;
    }

    return i;
}

所以这个方法有 3 个算术指令来更新整数 r、q、p。

这是我尝试用评论解释我的想法：

//Use temp variables so we don't keep using loads and stores for mem accesses; 
//hopefully the temps will just be kept in the register file
int r_temp = *r;
int q_temp = *q;

for (i=0;i<99;i = i+2) {
    int data1 = input[i];
    int data2 = input[i+1]; //going to try partially unrolling loop
    int a1 = data1.a;
    int a2 = data2.a;
    int b1 = data1.b;
    int b2 = data2.b;
    int v1 = data1.v;
    int v2 = data2.v;

    //I will use brackets to make my intention clear the order of operations I was planning
    //with respect to the functional (adder, mul) units available

    //This is calculating the next iteration's new q value 
    //from q += v1 + a1 + b1, or q(new)=q(old)+v1+a1+b1

    q_temp = ((v1+q1)+(a1+b1)) + ((a2+b2)+v2);
    //For the first step I am trying to use a max of 3 adders in parallel, 
    //saving one to start the next computation

    //This is calculating next iter's new r value 
    //from r *= v1 + x, or r(new) = r(old)*(v1+x)

    r_temp = ((r_temp*v1) + (r_temp*x)) + (v2+x);
}
//Because i will end on i=98 and I only unrolled by 2, I don't need to 
//worry about final few values because there will be none

*p = input[99].v; //Why it's in the loop I don't understand, this should be correct
*r = r_temp;
*q = q_temp;

好的，我的解决方案给了我什么？查看旧代码，i 的每个循环迭代都将采用 max((1A + 1M),(3A)) 的最小延迟，其中前一个值用于计算新的 r，而 3 次添加的延迟用于 q。

在我的解决方案中，我展开 2 并尝试计算 r 和 q 的第二个新值。假设加法器/乘法器的延迟使得 M = c*A（c 是某个整数 > 1），r 的乘法运算绝对是速率限制步骤，所以我专注于此。我尝试尽可能多地并行使用乘法器。

在我的代码中，首先并行使用 2 个乘法器来帮助计算中间步骤，然后加法必须将它们组合起来，然后使用最终乘法来获得最后的结果。因此，对于 r 的 2 个新值（即使我只保留/关心最后一个），我需要 (1M // 1M // 1A) + 1A + 1M，总延迟依次为 2M + 1M。除以 2，我每个循环的延迟值为 1M + 0.5A。我计算出原始延迟/值（对于 r）为 1A + 1M。因此，如果我的代码是正确的（我都是手工完成的，还没有测试过！）那么我的性能会有一点提升。

此外，希望通过不直接在循环中访问和更新指针（主要感谢临时变量 r_temp 和 q_temp），我节省了一些加载/存储延迟。

那是我的尝试。绝对有兴趣看看其他人想出什么更好！

4

1 回答 1

3

是的，可以利用这两条短裤。重新排列你的结构

struct s {
    unsigned v;
    short a;
    short b;
} input[100];

并且您可能能够更好地对齐体系结构上的内存字段，这可能允许更多这些结构位于同一内存页面中，这可能使您遇到更少的内存页面错误。

这都是推测性的，这就是为什么配置文件如此重要。

如果您有正确的架构，重新排列将为您提供更好的数据结构对齐，这会导致内存中更高的数据密度，因为更少的位丢失到必要的填充以确保类型与常见内存架构强加的数据边界对齐。

于 2012-09-11T18:42:57.910 回答