为什么程序在给定展开因子 k>C*L 的情况下会达到吞吐量限制？

Question

我正在阅读计算机系统：程序员的视角，3/E (CS:APP3e) Randal E. Bryant 和 David R. O'Hallaron。

作者说：

"In general, a program can achieve the throughput bound for an operation only when it can keep the pipelines filled for all of the functional units capable of performing that operation. For an operation with latency L and capacity C, this requires an unrolling factor k ≥ C · L. For example, floating-point multiplication has C = 2 and L = 5, necessitating an unrolling factor of k ≥ 10. Floating-point addition has C = 1 and L = 3, achieving maximum throughput with k ≥ 3."

为什么有效？即使吞吐量为 1.00，它也仅表示每个周期都有一个新操作开始。（延迟 3.00，问题 1.00。）

我试着画了一个完全流水线单元的图，例如，一个浮点加法器包含三个阶段（因此有三个周期的延迟），因此它可以在每个时钟周期开始一个新的操作。

3 个周期 - 1 个加法，但每个周期都会开始一个新的操作， 3个循环后，只有第一次添加完成，第二个4个周期后， 5个周期后的第三个。因此，对于完全流水线，我们得到 5 个周期的 3 个操作，而不是 9 个周期（非完全流水线）的 3 个操作。我对全流水线单元的理解有误吗？

k=10的原因是什么？即使有 2 个单元，每次迭代也必须等到计算完最后 2 个操作（即 10 次乘法，但迭代必须等到最后 2 个操作完成），因此没有展开的理由。

也许程序没有按顺序执行（这里我的意思是由于分支预测，处理器不等待每次迭代结束？）

/* 2 x 2 循环展开 */

void combine6(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length-1;
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i+1];
    }

    /* Finish any remaining elements */
    for (;i < length; i++) {
        acc0 = acc0 OP data[i];
    }
    *dest = acc0 OP acc1;
}

Answer 1

随着向量长度的增长，所有这些说法都越来越接近事实。理论上，当流水线启动和关闭时间除以总处理时间为零时，无限长度向量就达到了边界。为了简单起见，作者假设这些时间与测试中的总处理时间相比可以忽略不计。

为什么程序在给定展开因子 k>C*L 的情况下会达到吞吐量限制？

Why does program achieve the throughput bound given an unrolling factor k>C*L?

c

parallel-processing

latency

throughput

loop-unrolling