示例

p14

#include <stdio.h>
#include <stdlib.h>

// #define IDENT 0
// #define OP +

#define IDENT 1
#define OP *


typedef double data_t;

typedef struct 
{
    long len;
    data_t *data;
}vec_rec, *vec_ptr;

/*Create vector of specified length*/
vec_ptr new_vec(long len)
{
    /* Allocate memory*/
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    data_t *data = NULL;
    if (!result)
        return NULL; /* Couldn't allocate storage */
    result->len = len;

    /* Allocate array*/
    if (len > 0)
    {
        data = (data_t *)calloc(len, sizeof(data_t));
        if (!data)
        {
            free((void *) result);
            return NULL; /* Couldn't allocate storage */
        }
    }
    result->data = data;
    return result;
}

/*
    * Retieve vector element and store at dest.
    * Return 0 (out of bounds) or 1 (successful)
    */
int get_vec_element(vec_ptr v, long index, data_t *dest)
{
    if (index < 0 || index >= v->len)
        return 0;
    *dest = v->data[index];
    return 1;
}

/* Return length of vector */
long vec_length(vec_ptr v)
{
    return v->len;
}

data_t *get_vec_start(vec_ptr v)
{
    return v->data;
}


void combine5(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 acc = IDENT;

    // 使用2 x 1循环展开
    for (i = 0; i < limit; i+=2)
    {
        acc = (acc OP data[i]) OP data[i+1];
    }

    for (; i < length; i++)
    {
        acc = acc OP data[i];
    }
    *dest = acc;
}

void combine7(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 acc = IDENT;

    // 使用2 x 1循环展开
    for (i = 0; i < limit; i+=2)
    {
        acc = acc OP (data[i] OP data[i+1]);
    }

    for (; i < length; i++)
    {
        acc = acc OP data[i];
    }
    *dest = acc;
}

总结

这个几个例子可以看出我们提高并行性就是为了实现让处理器并行处理指令，从而可以让处理器发挥出他的优势，从而提高程序性能

示例解答

示例 1 解答

`aprod` 函数的作用：

aprod 计算一个长度为 n 的数组 a[] 的所有元素的乘积。在第一部分，它以步长为 3 展开循环，一次计算 3 个元素的乘积。在第二部分，它处理剩下的少数（不足 3 个）的元素。

循环展开：

在 for 循环中，通过 3 次展开，将数组 a[] 中的 i, i+1, 和 i+2 三个元素分别赋给 x, y, 和 z，然后计算这三者与 r 的乘积。

五种结合方式：

给出的五种结合方式是 r = r * x * y * z 的不同结合顺序。每一种结合顺序可能会影响运算流水线的效率，进而影响每次迭代的 CPE。

具体结合方式如下：

A 1:
```
r = ((r * x) * y) * z;
```
A 2:
```
r = (r * (x * y)) * z;
```
A 3:
```
r = r * ((x * y) * z);
```
A 4:
```
r = r * (x * (y * z));
```
A 5:
```
r = (r * x) * (y * z);
```

CPE 分析：

考虑到乘法指令的延迟为 5 个时钟周期，我们需要计算每种结合方式在不同流水线架构下的效果：

A 1: ((r * x) * y) * z
- 这是严格的左结合，每一步都依赖前一步的结果，无法并行执行。由于存在依赖关系，每次乘法的结果都必须等待上一次计算结束，因此 CPE 会较高。
A 2: (r * (x * y)) * z
- 这种结合方式能够让 x * y 在一条流水线中计算完成，然后与 r 结合再乘以 z。这减少了一些依赖关系，但仍存在部分依赖，CPE 可能会稍微降低。
A 3: r * ((x * y) * z)
- 这里的右结合使得 x * y 和 y * z 可以先并行计算，再与 r 相乘。这样减少了依赖，允许更多的并行化处理，CPE 进一步降低。
A 4: r * (x * (y * z))
- 类似于 A 3，y * z 可以并行计算，结果再与 x 结合后计算乘积，依赖链更短，这使得流水线的利用率提升，CPE 更低。
A 5: (r * x) * (y * z)
- 这种结合方式允许 r * x 和 y * z 完全并行计算，是依赖最少的一种结合方式。两组操作可以在不同的流水线上同时进行，从而极大地提升了并行性，预计 CPE 最低。

总结：

A 1 的完全左结合方式最依赖于前一次的计算结果，限制了并行化，CPE 最高。
A 5 的并行度最高，因为两组计算可以完全同时进行，CPE 最低。
A 2 至 A 4 则处于两者之间，依次减少数据依赖，CPE 逐步降低。

根据这些分析，答案会是 结合方式越能并行化计算，CPE 就越低，A 5 的表现最佳，而 A 1 最差。

示例 2 解答

在分析 combine7 和 combine5 的区别以及它们对 CPE（每个循环体的周期数）的影响时，关键在于它们的计算顺序不同，这种不同导致了数据依赖的变化，影响了指令级并行性。为了理解这一点，我们可以通过数据流图来说明。

`combine5` 的数据流图

在 combine5 中，计算的方式是：

acc = (acc OP data[i]) OP data[i+1];

其展开步骤是：

计算 acc OP data[i]。
将结果与 data[i+1] 进行运算。

这种方式依赖于 acc 的值在每次循环迭代中不断被更新，这会导致 循环间依赖（loop-carried dependency），即下一次循环的计算必须等待前一次循环的计算结果。这种数据依赖会限制指令的并行性，因为下一次的操作不能提前进行。

数据流图表现为线性依赖，每次循环必须等待上一次的结果完成才能继续：
```
acc -> acc OP data[i] -> acc OP data[i+1]
```

`combine7` 的数据流图

在 combine7 中，计算的方式是：

acc = acc OP (data[i] OP data[i+1]);

这里的展开步骤是：

先计算 data[i] OP data[i+1]。
然后将结果与 acc 进行运算。

这种方式打破了循环内部分计算的顺序，使得 data[i] OP data[i+1] 可以并行地计算，因为这两次计算之间没有依赖关系。这就减少了数据依赖，使得处理器能够更容易地并行执行操作。

数据流图表现为：

(data[i] OP data[i+1]) -> acc OP 上次的 acc

这里 data[i] OP data[i+1] 是独立的，可以与其他操作并行处理。

重新结合变换的效果

指令级并行性：在 combine7 中，数据依赖关系较少，处理器能够更好地利用指令级并行性。例如，现代处理器有多个执行单元，可以同时处理多个独立的操作，而 data[i] OP data[i+1] 就可以在不同的执行单元中并行处理。这可以大幅提高性能，尤其是在乘法运算较慢的情况下。
流水线效率：由于 combine7 中的操作顺序减少了数据依赖，处理器流水线能够更顺畅地执行。相较之下，combine5 的依赖链较长，流水线每次都需要等待上一次计算的结果才能继续执行，这降低了流水线的效率。
CPE 变化：对于加法和乘法这样的操作，重新结合变换的效果是不同的。对于加法，指令往往可以并行执行，流水线中的数据依赖不显著，CPE 改变不大。而对于乘法，由于乘法的延迟通常较大，减少数据依赖可以显著提高指令并行性，减少 CPE。因此，在 combine7 中，乘法的 CPE 下降幅度可能会比加法更明显。

总结

combine 5 中存在较多的循环依赖，导致指令级并行性差，流水线利用率较低。
combine 7 通过重新组合操作减少了数据依赖，使得计算可以更好地并行化，提高了处理器的执行效率，尤其是对于复杂操作如乘法，其 CPE 明显改善。

提高并行性方法

[!TIP] 一个提高并行性最核心的就是减少依赖

减少依赖的方法

重新结合变换
循环展开
- k X 1 循环展开
- k X m 循环展开
- k X 1 a 循环展开

用数据流分析

这个方法是最有效分析依赖关系的，从而实现减少依赖关系，提高并行性，从而提高程序性能。

在分析一个等式的依赖关系时，我们主要关心的是某些操作是否必须等待其他操作完成，才能得到最终结果。通过分析依赖关系，可以找到可以并行计算的部分，进而减少计算所需的时间和周期数 (CPE)。以下是一些方法来分析依赖关系和找出依赖项最少的路径：

1. 数据流图 (Data Flow Graph)

数据流图是分析依赖关系的常用工具。它用图的形式表示每个操作之间的依赖关系。节点表示操作（如加法或乘法），而边表示依赖关系。如果一个操作的输出是另一个操作的输入，那么前一个操作必须先完成。

步骤：
- 将每个操作（例如乘法）表示为一个节点。
- 使用有向边表示依赖关系：一个节点的结果被下一个节点所依赖。
- 图中所有操作必须按照依赖关系的顺序来进行。
- 最优路径是依赖关系最少的路径，也就是最长的依赖链。

例子：
对于表达式 r = ((r * x) * y) * z，可以画出以下数据流图：

r * x -> temp1
temp1 * y -> temp2
temp2 * z -> r

这个表达式中的依赖是线性的，必须先计算 r * x，然后 temp1 * y，最后 temp2 * z，无法并行化。

改进：
对于 r = (r * x) * (y * z)，数据流图会变成：

r * x -> temp1
y * z -> temp2
temp1 * temp2 -> r

这里，r * x 和 y * z 可以并行计算，这样减少了依赖关系，因此可以同时计算这两项，依赖更少，效率更高。

2. 并行性和指令调度

在现代处理器中，指令调度器试图尽可能并行执行指令。如果多个指令之间没有依赖关系，调度器会并行执行它们。这意味着依赖关系越少，潜在的并行计算就越多。

方法：

并行性原则：查看一个表达式中，哪些部分相互独立，能否同时进行计算。
指令调度窗口：设想处理器的执行单位如何调度指令。如果有多个独立的操作，它们可以被放入同一个执行窗口中，减少延迟。

例子：
对于 r = (r * x) * (y * z)，我们看到 r * x 和 y * z 没有相互依赖，因此可以并行计算。这就减少了总的执行时间。

3. 重写结合律 (Reassociating)

使用 结合律 可以改变操作的顺序，进而减少依赖关系。结合律说明了 (a * b) * c = a * (b * c)。通过不同的结合方式，可以尝试减少某些计算之间的依赖。

方法：

对原表达式进行重新结合，尝试将依赖最少的部分提前计算。
尽可能将并行的部分分离出来，使它们同时计算。

例子：
考虑 r = r * x * y * z，我们可以通过结合律改写为不同形式：

(r * x) * (y * z)：允许 r * x 和 y * z 并行计算。
r * (x * (y * z))：允许先计算 y * z 再结合 x，这仍然比线性依赖好一些，但比 (r * x) * (y * z) 稍差。

4. 指令流水线 (Pipelining)(并发?😕)

指令流水线是现代处理器中提高性能的关键技术。如果两个指令相互依赖，它们无法同时进入流水线。依赖越少的操作可以同时进入流水线，这样处理器能够更好地利用资源。

方法：

分析每个操作是否会导致流水线阻塞（即下一个指令必须等待前一个指令完成）。
尽量重写表达式，减少阻塞，避免串行依赖。

例子：
对于 r = ((r * x) * y) * z，因为每一步的结果依赖于前一步，必须等待前一步的乘法完成后才能进行下一步，这会阻塞流水线。而 r = (r * x) * (y * z) 则允许 r * x 和 y * z 同时进入流水线，从而避免阻塞。

5. 循环展开 (Loop Unrolling)

循环展开可以减少循环体中的依赖项，因为每次迭代会计算更多的结果，允许多个操作并行进行。

方法：

尝试将循环体中的操作分为多个块，使得每个块之间没有依赖关系，可以并行计算。
通过一次计算多个元素，减少依赖和操作的数量。

例子：
假设 for (i = 0; i < n; i++) r *= a[i];。如果我们展开为：

for (i = 0; i < n-1; i+=2) {
    r = (r * a[i]) * a[i+1];
}

现在每次循环中，a[i] 和 a[i+1] 可以并行计算。这样通过减少依赖，能够提高性能。

总结：

数据流图：绘制操作的依赖图，分析依赖路径的长短。
并行性分析：找出可以并行计算的部分，减少顺序依赖。
结合律：通过重新结合表达式，减少依赖项。
流水线分析：确保操作能够同时进入处理器流水线，避免阻塞。
循环展开：一次计算更多元素，减少依赖关系。

通过这些方法，你可以有效地分析和优化计算中的依赖关系，从而提高性能。

示例

总结

示例解答

示例 1 解答

aprod 函数的作用：

循环展开：

五种结合方式：

CPE 分析：

总结：

示例 2 解答

combine5 的数据流图

combine7 的数据流图

重新结合变换的效果

总结

提高并行性方法

减少依赖的方法

用数据流分析

1. 数据流图 (Data Flow Graph)

2. 并行性和指令调度

3. 重写结合律 (Reassociating)

4. 指令流水线 (Pipelining)(并发?😕)

5. 循环展开 (Loop Unrolling)

总结：

`aprod` 函数的作用：

`combine5` 的数据流图

`combine7` 的数据流图