时间戳

首页 > 解决方案 > 为什么在给定展开因子 k>C*L 的情况下程序会达到吞吐量界限？

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

问题描述

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

作者说：

“一般来说，一个程序只有在它能够为所有能够执行该操作的功能单元保持管道填充时，才能实现该操作的吞吐量限制。对于具有延迟 L 和容量 C 的操作，这需要展开因子 k ≥ C · L。例如，浮点乘法有 C = 2 和 L = 5，需要展开因子 k ≥ 10。浮点加法有 C = 1 和 L = 3，在 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;
}

标签： cparallel-processinglatencythroughputloop-unrolling

解决方案

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

推荐阅读