螺旋矩阵题型总结。我刷了几道螺旋矩阵相关的题目，这里我们介绍一下一些常见的解法。

螺旋矩阵

方形矩阵

当我们遇到n*n的方形矩阵时，可以用一种特殊的解法来遍历实现，以下面这道题为例：

59. 螺旋矩阵 II

我们可以定义几个变量用来控制遍历的行为：

• startX：每次循环的起点的行数
• startY：每次循环的起点的列数
• offset：每循环一圈，用偏移量表现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        int offset = 1 , startX = 0 , startY = 0;
        int val = 1;
        int i,j;
        for(int k=0;k<n/2;k++){		//循环次数就是圈数
            for(j=startY;j<n-offset;j++)	//左上->右上（从此以下都是左闭右开）
                ans[startX][j] = val++;
            for(i=startX;i<n-offset;i++)	//右上->右下
                ans[i][j] = val++;
            for(;j>startY;j--)				//右下->左下	
                ans[i][j] = val++;
            for(;i>startX;i--)				//左下->右上
                ans[i][j] = val++;
            startX++;
            startY++;
            offset++;	//实际上更新offset就是在更新每次循环的边界（缩小）
        }
        if (n&1){	//如果矩阵的边长为奇数，最中间的值会没法遍历到
            ans[offset-1][offset-1] = val;
        }
        return ans;
    }
};

同时还可以将方形矩阵视作一种特殊的矩形矩阵，以下对矩形矩阵的所有解法对方形都适用。

矩形矩阵

有时候我们会发现矩阵是矩形的，或者只有一层，这个时候就需要用几个通用的方法，来实现。例题：

LCR 146. 螺旋遍历二维数组

54. 螺旋矩阵

2326. 螺旋矩阵 IV

模拟路径法

我们先分析我们的转向条件：（1）当前进的方向上碰到了边界（2）当前进的方向上是已经走过的路径

第一个条件比较好解决，第二条件我们需要维护一个和数组相同大小的矩阵，走过的路线我们设置为true，没走过的设置为false.

由于我们的转向动作是有序的，是顺时针，所以我们可以使用一个数组来存储我们的方向。当到达转向条件时，设置成下一个转向动作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

vector<int> spiralArray(vector<vector<int>>& array) {
        if(array.empty()||array[0].empty())	//判断数组是否为空，注意先后顺序，array[0]在array为空时是不能访问的
            return {};
        int row = array.size();
        int col = array[0].size();
        int total = row*col;
        vector<vector<bool>> use(row,vector<bool>(col,0));	//路径表
        vector<int> ans(total,0);
        vector<vector<int>> direction{{0,1},{1,0},{0,-1},{-1,0}};	//方向表（顺时针）
        int directionIdx = 0;	//方向表索引
        int i=0,j=0;
        for(int k=0;k<total;k++){
            ans[k] = array[i][j];
            use[i][j] = true;
            int ni = i + direction[directionIdx][0];	//预更新i
            int nj = j + direction[directionIdx][1];	//预更新j
            if(ni<0||ni>=row||nj<0||nj>=col||use[ni][nj]==true){	//根据预更新状态判断转向条件
                directionIdx = (directionIdx+1)%4;	//转向则把方向索引设置到下一位
            }
            //实际更新
            i = i + direction[directionIdx][0];
            j = j + direction[directionIdx][1];
        }
        return ans;
    }

层级遍历法（边界收缩）

这个和刚刚用来解决方形矩阵的方法是相同的，只不过更新方式和更新条件要更加复杂。

一开始先设定好边界，当移动到边界的时候就转向，然后收缩边界。这样的好处在于我们不用再特意维护一个数组来判断路径是否被走过 了。因为走过的路径被我们收缩了，所以就不用在考虑。只需要在边界做检测就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m,vector<int>(n,-1));
        int top = 0;	
        int bottom = m-1;	//-1是因为索引和实际位置的差值
        int left = 0;
        int right = n-1;
        while(left<=right&&top<=bottom){	//如果相等就说明，边界收缩了，遍历结束了
            for(int i=left;i<=right;i++)	
                ans[top][i] = val;
            top++;							//左上->右上 top边界收缩
            for(int i=top;i<=bottom;i++)
                ans[i][right] = val;
            right--;						//右上->右下 right边界收缩
            for(int i=right;i>=left;i--)
                ans[bottom][i] = val;
            bottom--;						//右下->左下 bottom边界收缩
            for(int i=bottom;i>=top;i--)
                ans[i][left] = val;
            left++;							//左下->右上 left边界收缩
        }
        return ans;
    }

螺旋生成矩阵

这个算是一个小特例，大多数题目是给你一个矩阵让你去螺旋遍历，但是有的题目需要你自己螺旋生成一个矩阵。我们看到下面的例题：

885. 螺旋矩阵 III

这道题需要我们形成一个螺旋的路径，然后返回矩形内的位置的坐标。难点在于这个螺旋路径的生成，因为转向的条件和每次前进的步长综合考虑起来条件会非常的复杂。下面的话给出两种方法。

边界扩展法

和我们之前所做的边界收缩相反，我们先界定好边界，然后每次转向时宽展这个方向上的边界。通过这种方式来动态的生成一个螺旋的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

const int DIR[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> ans;
        int total = rows*cols;
        int num = 1;
        int i = rStart,j = cStart;	//令i,j记录路径的实时位置
        int left = cStart - 1,right = cStart + 1,top = rStart - 1,bottom = rStart + 1;	//确定边界
        int dir=0;	//记录方向
        while(num <= total){
            if(i>=0&&i<rows&&j>=0&&j<cols){	//当路径到达矩阵内部时，记录当前位置
                ans.push_back({i,j});
                num++;
            }
            if(dir==0&&j==right){	//如果向右移动触碰右边界
                dir+=1;				//则转向
                right++;			//并拓展右边界
            }else if(dir==1&&i==bottom){	//如果向下移动触碰下边界
                dir+=1;						//则转向
                bottom++;					//并拓展下边界
            }else if(dir==2&&j==left){		//...
                dir+=1;
                left--;
            }else if(dir==3&&i==top){		//...
                dir=0;
                top--;
            }
            i += DIR[dir][0];		//根据方向来更新位置
            j += DIR[dir][1];
        }
        return ans;
    }

规律法

我们可以观察螺线路径的一个显著规律：每转向两次会更新一次前进的步长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

const int DIR[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    	int num=0;
    	int dir=0;
    	int run=2;	//步长计数器
        vector<vector<int>> ans;

        while(num < R * C){
            for(int i = 0; i < run / 2; i ++){   //遍历步长，每转两下就会增加一步
                if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                    ans.push_back({r0, c0}), ++ num;
                r0 += DIR[dir][0];
                c0 += DIR[dir][1];
            }
            pos = (pos + 1) % 4;	//每遍历一次步长，就转向
            run++;		//利用取整的性质，每转向两次才会增加一次步长
        }
        return ans;
    }

总结

螺旋矩阵的关键在于边界的检测和变换，还有转向条件的判断。比较简单。

我们已经尽可能的实现各种程度的优化了，但所谓知己知彼，百战不殆。我们不仅要了解程序的性能怎么去优化，同时也要了解制约程序进一步优化的因素是什么。

限制因素

关键路径指明了执行程序所需时间的基本下界。如果程序中有某条数据相关链，这条链上的所有的延迟之和等于T，那么程序至少需要T个周期才能执行完。我们还看到功能单元的吞吐量界限也是程序执行的一个下界。也就是说，假设一个程序一共需要N个某种运算的计算，而微处理器只有C个能执行这个操纵的功能单元，并且这些单元的发射时间为I，那么这个程序的执行至少需要N*I/C个周期。

不过以上是理想状态，实际过程中，我们仍然需要考虑其他的制约因素。

寄存器溢出

循环并行性的好处受汇编代码描述计算的能力限制（如果代码描述不出来，说明寄存器不够用了）。如果并行度p超过了可用的寄存器数量，那么编译器就会溢出。将某些临时值放到内存中，在堆栈上分配空间。比如下面的例子：

为啥20*20的循环展开反而不如10*10呢？现代x86-64处理器可以使用16个YMM寄存器来保存浮点数。一旦数量超过了可用的寄存器的数量，程序就必须在栈上分配变量。内存写入读取的过程会造成不必要的开销。不过大多数循环会在出现寄存器溢出之前就会达到吞吐量的极限。

分支预测和预测错误处罚

指令在进行分支预测时，往往会使用投机执行的机制，但是预测错误意味着很大的代价。虽然代价是无法避免的，但是我们是否可以减少这个代价呢？在x86-64的程序处理中有条件传送的指令。我们可以在进行分支跳转的时候，通过将条件转移编译成条件传送来，减少这个代价。我们直接结算出两个方向上的可能的值，然后根据条件传送选择期望的值。这样，我们就不用考虑条件是否满足了，因为没有代价。

抛开编译器的优化，我们又该如何编写能够减少分支预测处罚的代码呢?

不要过分关心可以预测的分支

错误的分支预测影响可能很大，但是并不意味着所有的程序分支都会减缓程序的运行。现代处理器的分支预测逻辑十分先进，对于循环语句的分支，往往会被预测为选择分支，这样只有最后一次才会导致预测错误。

所以在程序性能优化（1）中的这个现象可以解释：

我们为了减少get_vec_element中的边界检测的延迟，改进成了combine3，发现程序性能几乎没什么改变，这是因为对于i的边界检测，是高度可预测的，对于计算机而言影响微乎其微。这些检测并不会影响程序的关键路径，或是起不到决定性作用。

书写适合用条件传送实现的代码

分支预测对于循环这种有规律的模式还行，但是程序中的大多数测试时完全不可预测的，依赖于数据的任意性，分支预测逻辑会表现得很糟糕。我们无法保证编译器会在编译中使用条件数据传送而不是条件控制转移，但是我们可以引导编译器进行我们想要的编译。

以一个程序为例，给定两个整数数组a和b，对于每个位置i，我们想要将a[i]设置为a[i]和b[i]中较小的那个，将b[i]设置成较大的那个。

首先是我们常用的风格：

1
2
3
4
5
6
7
8
9
10

void minmax1(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        if(a[i]>b[i]){
            long t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

在这里可以看到，我们是在分支预测之后才执行交换的过程。这会扩大分支预测的代价。可是我们尝试另一种写法：

1
2
3
4
5
6
7
8
9

void minmax2(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        long min = a[i] < b[i] ? a[i] : b[i];
        long max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

这里的话相当于去除了条件分支，先把每个位置的最大值和最小值计算出来，然后分别赋值给a[i]和b[i]。通过合理的安排代码，我们也可以更好的帮助编译器优化代码。

理解内存性能

内存性能实际上也是很重要的决定性因素，在之前的测试中，实际上访问的内存都十分少量。所有的现代处理器都包含一个或多个高速缓存存储器，以对少量的存储器提供快速的访问。接下来我们要进一步讨论加载和存储操作的程序的性能印象。不过我们默认所有的数据都是存放在高速缓存中的情况。

加载的性能

一个包含加载操作的程序性能既依赖于流水线的能力，也依赖于加载单元的延迟。在之前的合并函数中，无论什么数据类型和合并操作都无法让CPE下降到0.5以下。这是因为，每一个被计算的元素，所有的示例都需要熊内存中独一个值，对于两个加载单元而言，其每个时钟周期都只能启动一条加载操作，所以CPE不可能小于0.5

到目前为止我们并没有在示例中看到加载操作的延迟产生的影响。加载操作的地址只依赖于循环索引i，所以加载操作不会称为限制性能的关键路径的一部分。

但是我们可以手动构造一个由一系列加载操作构成的计算，一个加载操作的结果决定下一条操作的地址：

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef struct ELE{
    struct ELE* next;
    long data;
}list_ele,*list_ptr;

long list_len(list_ptr ls){
 	long len = 0;
    while (ls){
        len ++;
        ls = ls->next;
    }
    return;
}

在这里变量ls的每个后续只依赖于指针引用ls->next读出的值。我们可以关键部分的汇编代码：

1
2
3
4
5

.L3:
	addq $1,%rax
	movq (%rdi),%rdi	;ls = ls->next
	testq %rdi,%rdi
	jne .L3

我们可以可以看到movq是整个循环中关键的瓶颈，且每次循环都会依赖加载出来的%rdi的值，此时的程序的CPE是由加载操作的延迟决定的。我们之后在存储器部分会详细讨论。

存储的性能

和其他的操作不一样，存储操作不会影响任何寄存器的值。一系列的存储操作并不会产生数据相关。只有加载操作会受存储操作结果的影响，因为只有加载操作才能从由存储操作写的那个位置读回值。

我们可以做一个实验来体现这种影响：

1
2
3
4
5
6
7
8
9

void write_read(long* src,long* dst,long n){
    long cnt = n;
    long val = 0;
    while (cnt){
        *dst = val;
        val = (*src)+1;
        cnt--;
    }
}

然后我们分别使用两种不同的调用方式：

最终的结果是示例A的CPE=1.3远快于示例B的CPE = 7.3。这背后的原因就是因为在调用write_read时，参数src和dst指向了同一个内存位置，导致产生了写/读相关——一个内存读的结果依赖于一个最近的内存写。

为了理解这背后具体的原理，我们需要更加仔细的看看加载和存储执行单元：

存储单元实际上会包含一个存储缓冲区，它包含已经被发射到存储单元而又还没完成的存储操作（这里的完成包括更新数据高速缓存）的地址和数据。提供这么一个缓冲区，使得一系列存储操作不必等待每个操作都更新高速缓存就能执行。当一个加载操作发生时，它必须检查存储缓存区中的条目，看看有没有地址匹配。如果有就取出相应的数据条目作为加载操作的结果。

其机器代码形式如下：

1
2
3
4
5
6
7

; src in %rdi , dst in %rsi , val in %rax
.L3:				; loop:
	movq %rax,(%rsi)	;write val to dst
	movq (%rdi),%rax	;t = *src
	addq $1,%rax		; val = t+1
	subq $1,%rdx		;cnt--
	jne .L3				;if != 0,goto loop

这里的movq (%rdi),%rax在实际的过程中被翻译成了两个操作：

• s_addr指令计算存储操作的地址，在存储缓冲区创建一个条目，并设置该条目的地址字段
• s_data操作设置该条目的数据字段。

这两个计算时独立执行的，不过它们之间有隐含的相关，实际上s_addr的操作必须在s_data之前。同时由于load操作需要检查所有未完成的存储操作的地址，所以s_addr到load之间也会存在数据相关。还有一个有条件的数据相关，存在于s_data和load之间（当%rsi和%rdi相等，即读写的地址相同），此时load操作必须等待直到s_data将它的结果存放到存储缓冲区中。反之，则继续进行。

我们依旧可以图形化抽象write_read的操作，来分析它的关键路径：

右边是最简情况，只保留了使用一次迭代中的值为下一次迭代产生的值的操作。

现在我们可以理解函数write_read的性能特征了，下面是内循环多次迭代形成的数据相关：

在示例A的情况下，有不同的源和目的地址，加载和存储操作都可以独立进行，因此唯一的关键路径是减少变量造成的，因此这个程序的CPE为1.0。对于示例B的情况下，源地址和目的地址相同，导致s_data和load指令之间的数据相关使得关键路径形成。其中包括了存储，加载，增加数据等操作，导致程序的CPE为7.0。

这个例子说明了，内存操作的细微之处。对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响那些指令了。但是对于内存操作，只有到计算出加载和存储的地址被计算出来后，处理器才能确定那些指令会影响哪些。

我们可以通过设置中间变量的方式来避免写/读相关。例如：

我们有a，p两个数组，令p[0] = a[0]，p[i] = p[i-1] + a[i]，我们正常写出来的程序会是这样：

1
2
3
4
5
6

void psum1(long a[],long p[],long n){
    long i;
    p[0] = a[0];
    for (i=1;i<n;i++)
        p[i] = p[i-1] + a[i];
}

但是这里的p[i]=p[i-1] + a[i]存在着读/写相关。我们可以引入一个中间的存储变量，来避免这种数据上的依赖：

1
2
3
4
5
6
7
8
9
10

void psum1(long a[],long p[],long n){
    long i;
    long last_val,val;
    last_val = p[0] = a[0];
    for (i=1;i<n;i++){
        val = last_val + a[i];
        p[i] = val;
        last_val = val;
    }
}

总结：性能提高技术

• 高效设计：为遇到问题选择适当的算法和数据结构，避免使用会渐进的产生糟糕性能的算法或编码技术。
• 基本编码原则：避免限制优化的因素，这样编译器就能产生高效的代码。
  • 消除连续的函数引用：必要时，将计算移到循环外面。
  • 消除不必要的内存引用：引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中
• 低级优化：结构化代码以利用硬件功能。
  • 展开循环，降低开销，并且使得进一步的优化称为可能
  • 通过使用例如多个累计变量和重新结合等技术，提高指令的并行性
  • 用功能性的风格重写条件操作，使得编译采用条件数据传送

上次我们分别从简单的过程调用的优化到了机器级层面的关键路径优化。在此基础之上，我们可以尝试更进一步的优化。

循环展开

循环展开通过增加每次迭代计算的元素的数量，减少循环的迭代次数。它从两个方面改进了程序的性能：

• 减少了循环索引的计算和条件分支的判断
• 提供了一些方法，进一步的变化代码，减少整个计算中关键路径上的操作数量

比如下面这个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
    
    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;
}

这里我们每次迭代都进行了两次迭代，我们可以看到一定程度上的性能优化：

实际上循环展开也有许多需要注意的地方，比如循环展开的边界条件。我们设我们的按k次进行迭代，也就是说每次会将从i到i+k-1的数据进行计算，但是可能会出现一个情况。我们的原迭代次数可能无法被k整除，这意味着我们可能会出现漏处理的情况，需要额外设置一个循环。那么第一个循环的边界应该到哪里为止呢？

1

i+k-1 < n --> i < n-k+1 --> limit = n-k+1

推断可知i只能小于我们得到的limit，以确保程序能够正常迭代。剩下的未能完全迭代的部分，我们使用另一个循环来继续计算。

但是循环展开的次数越多，性能的优化效果就越好吗？我们看到并非如此：

要理解为什么程序没法进一步的优化，我们需要分析程序的关键路径，我们将k=2 data_t=double OP=*时的关键代码转化成图形化表示：

我们进一步的化简，可以看到关键路径的状态：

无论怎么展开，关键路径上还是有n个mul操作，由于数据的依赖关系，这里的乘法操作在每次展开中实际上并不能并行处理。为了进一步的提高程序的性能，我们要想办法提高数据的并行性。

提高并行性

硬件通常有多个相同的硬件组成，实际上硬件有更高速率执行加法和乘法的潜力，但是我们的代码无法实现这个功能，这是因为我们将累计的值放在一个单独的变量中，在前一个操作结束前，我们都无法进行下一个整数操作，所以我们需要相办法打破这种顺序相关，来更好的利用硬件的并行性能。

多个累计变量

对于一个可交换可结合的合并运算来说，我么可以通过将一组合并运算拆分成多个部分，最后合并结果，来提高性能，比如对于：

P_n = a₁ * a₂ * …… * a_n 我们可以将其拆分成 PO_n = a₁ * a₃ * …… * a_2i+1 和 PE_n = a₂ * a₄ * …… * a_2i，最后合并得到 P_n = PO_n * PE_n

我们可以用代码实现，这种既做循环展开，又做两路并行的效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;
    
    for(i=0;i<limit;i+=2){
        acc0 = acc0 OP data[i];
        acc1 = acc1 OP data[i+1];
    }
    	
    for(;i<length;i++)
        acc0 = acc0 OP data[i];
    *dest = acc0 OP acc1;
}

性能如下：

我们的增加并行计算后的程序性能超过了延迟界限，相较于之前提升了两倍，这意味着我们很好的利用了并行计算的优势，我们可以根据对关键路径的分析中很好的看到这一点：

combine6中的两路并行优化将原来的一条关键路径拆分成了两条关键路径，现在每条关键路径上的mul操作变成了n/2次。使得程序的性能极大的提升，对于我们进行k*k的优化，我们可以在下图中看到效率的提升：

可以看到随着k的增加，甚至可以使程序的性能逼近吞吐量的界限。

但是，这样的并行计算一定很好吗？它也有着一定的副作用，受四舍五入和溢出的影响，可能会一定程度上改变程序的行为，造成一定的误差。需要酌情处理。

重新结合变换

现在我们需要探讨另一种打破顺序相关的方式以将性能提高到延迟界限之外。我们只需进行对combine5的循环逻辑进行微小的合并变换即可得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
    
    for(i=0;i<limit;i+=2)
        //原：acc = (acc OP data[i]) OP data[i+1];
        acc = acc OP (data[i] OP data[i+1]);
    
    for(;i<length;i++)
        acc = acc OP data[i];
    *dest = acc;
}

看上去并没有发生什么改变，但是实际测量的性能却得到了很好的提升：

我们还是分析关键路径：

我们可以看到，每次迭代的第一个乘法实际上不存在顺序相关的问题，它的每次计算不依赖于上一次的迭代寄存器，所以关键路径上只有一次乘法操作，另一次乘法操作始终可以并行操作。所以通过这种方式，关键路径上只有n/2次mul操作。

随着展开次数的增多，程序的性能也可以接近吞吐量界限。总的来说重新结合变换会减少计算中关键路径上操作的数量，通过更好的利用功能单元的流水线能力得到更好的性能。要注意的问题和上面一样。

优化合并小结

通过以上的例子，我们应该意识到现代处理器强大的计算能力，可是现代编译器因为种种原因始终不能完全的利用这些能力，但是我们可以按一些非程式化的方式来编写程序以激发这些能力。

对于特定的程序而言，尤其是要长时间多次运行的程序而言，我们需要尽可能的优化他的效率。如计算效率，空间效率…大多数时候编译器会帮助我们完成这个工作，但是特定的场景中，我们需要自己实现程序的优化设计。

优化编译器的能力和局限性

在现代编译器中，编译器往往会通过各种复杂的算法，根据程序中的值，被计算被使用的过程，来优化程序的实现。其中以GCC为例，编译器为我们提供了一系列指定优化级别，如-Og是使用一些基本的优化。使用-O1 -O2 -O3则会使用更多的优化。但是可能会导致一些未定义的复杂的情况出现。

我们需要保证编译器对程序只进行 安全 的优化，也就是说对于程序所有可能遇到的情况，在C语言标准之下，优化后得到的程序和优化前得到程序应该有相同的行为。我们可以看下面的一个范例：

1
2
3
4
5
6
7

void twiddle1(long *xp,long *yp){
    *xp += *yp;		//两次读一次写
    *xp += *yp;		//两次读一次写
}
void twiddle2(long *xp,long *yp){
    *xp += 2* *yp	//两次读一次写
}

看上去，两个程序似乎有这相同的行为，而且看起来twiddle2有着更好的效率。但是实际上，当我们考虑xp=yp的情况时。我们发现twiddle1和 twiddle2的结果并不一样。所以编译器不应该将twddle2做为twiddle1的优化版本。

这种两个指针可能指向同一个内存位置的情况，我们称之为内存别名使用。在编译器优化中，我们必须假设不同的指针可能会指向内存中的同一个位置。这是妨碍优化的第一个因素。

第二妨碍优化的因素是函数调用，我们假设下面的这个范例：

1
2
3
4
5
6
7

long f();
long func1(){
    return f()+f()+f()+f();
}
long func2(){
    return 4*f();
}

我们乍一看可能认为func1和func2效果是相同的，实际上，当我们考虑如下情况时：

1
2
3
4

long counter = 0;
long f(){
    return counter++;
}

这个时候就会产生不一样的结果，这是因为这个函数有副作用——它修改了全局程序状态的一部分。改变调用它的次数，会的改变程序的行为。

如果编译器不会试图判断一个函数有没有副作用，那可能会被错误的优化成func2。相反，则会保持函数调用不变。不过还有现代编译器也会使用一种特殊的手段来实现这种优化——内联函数替换。如func1可能会被内联替换成：

1
2
3
4
5
6
7

long func1in(){
    long t = counter++; 	//+0
    t += counter++;			//+1
    t += counter++;			//+2
    t += counter++;			//+3
    return t;
}

这样的话就减少了函数调用的开销。同时我们可以实现进一步的优化：

1
2
3
4
5

long func1opt(){
    long t = 4*counter + 6;
    counter += 4;
    return t;
}

我们可以在gcc中使用-finline和-O1以上等级的优化实现这个优化。但是这个优化也有一定的代价，我们将函数调用的过程优化掉了，意味着我们不能在调试器中，跳转到对应的程序，这意味程序行为一定程度上的失真。

程序示例

为了说明一个抽象的程序是如何被系统地转换成更有效的代码的，我们使用一个基于下面的是向量数据结构的运行示例。

向量有两个内存块组成：头部和数据数组，其中头部的结构声明如下：

1
2
3
4

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

这个声明由data_t来表示基本元素的数据类型，我们可以指定类型给data_t。同时，我们还会分配一个len个data_t类型对象的数组，来存放实际的向量元素。

我们给出一个生成向量，访问向量元素，以及确定向量长度的基本过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//生成指定长度的向量数组
vec_ptr new_vec(long len){
	//分配向量头部的空间
    vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));
    data_t *data = NULL;
    if(!result)
        return NULL;	//分配失败
    result->len = len;
    //分配数组的空间
    if(len>0){
        data = (data_t*)calloc(len,sizeof(data_t));
        if(!data){
            free((void *)result);
            return NULL;	//分配失败
        }
    }
    result->data = data;
    return result;
}

//访问向量中的指定元素并存储在指定空间中
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;
}

//返回向量的长度
long vec_length(vec_ptr v){
    return v->len;
}

我们在此基础上实现一个合并运算的实现，通过对基本元素IDENT和合并运算OP的不同声明，我们测量这个函数对不同运算的性能：

1
2
3
4
5
6
7
8
9
10
11
12
13

#define IDENT 0
#define OP +
//#define IDENT 1
//#define OP *
void combine1(vec_ptr v,data_t *dest){
    long i;
    *dest = IDENT;
    for (i = 0;i < vec_length(v);i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val
    }
}

下面我们会给出程序的CPE效率（数值越小性能越好），以参考：

消除循环的低效率

我么可以看到过程combine1调用函数vec_length作为for循环的测试条件。这导致每次循环测试的过程中我们都会有一次函数调用开销，我们可以通过以下方式来减少这个开销：

1
2
3
4
5
6
7
8
9
10
11

void combine2(vec_ptr v,data_t *dest){
    long i;
    long length = vec_length(v);
    
    *dest = IDENT;
    for(i=0;i<length;i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val;
    }
}

效果如下：

这个优化是一个常见的优化，叫做代码移动。这类优化包括识别要执行多次，但是计算结果不会改变的计算。因为可以将计算移动到不会被多次求值的部分。

很遗憾的是，现在的编译器并不能很好的实现这一点。这个看起来无足轻重的代码，实际上在循环次数高的使用环境下，极大的影响了程序的效率。

减少过程的调用

正如我们刚刚所提到的，在循环测试中的过程调用会导致程序的性能下降，同样的在循环体中的过程调用也会导致性能的开销。在我们的代码中，可以看到每次循环迭代都会调用get_vec_element，这个函数会对索引做边界检测，然后再获取指定的数据。

在这里我们可以简化这个过程，我们定义一个新的函数以获取向量的起始位置，然后通过数组索引访问，从而实现对元素的访问。避免在循环体中的过程调用：

1
2
3
4
5
6
7
8
9
10
11
12
13

data_t* get_vec_start(vec_ptr v){
    return v->data;
}
void combine3(vec_ptr v,data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    
    *dest = IDENT;
    for(i=0;i<length;i++){
        *dest = *dest OP data[i];
    }
}

效果如下：

令我们吃惊的是，性能并没有明显的提升。事实上，整数求和的性能还略有下降。显然是内存循环中的其他操作形成了瓶颈，限制性能超过调用get_vec_element我们之后还会在此回头看看这个现象。看看为什么combine2中反复的边界检查不会让性能更差。

消除不必要的内存引用

combine3的代码将合并运算的值累积在指针dest指定的位置。通过检查编译出来的内循环代码我们可以看出，每次我们对指定位置的计算都需要先从内存中取出，再重新存入。在此我们给出的数据类型为double,合并运算为乘法的汇编为：

在这里我们可以看出每次迭代都需要从内存中读出再写入内存。这样的内存读写十分浪费，我们应该先用一个临时寄存器来存储每次迭代后的值，等到迭代结束后，再将值写入内存，从而避免不必要的内存引用:

1
2
3
4
5
6
7
8
9
10
11

void combine4(vec_ptr v, data_t *dest){
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;
    
    for (i=0;i<length;i++){
        acc = acc OP data[i];
    }
    *dest = acc;
}

效果如下：

我们可以看到程序性能显著的提升。但是遗憾的是，编译器无法实现这个简单的变换，因为在大多数情况下，编译器并不能判断函数会在什么情况下被调用，以及程序员的本意是什么。所以在编译的过程中，往往只能进行保守的读写内存。

理解现代处理器

到现在为止，我们所运用的优化都是不依赖于目标机器的任何特性的。这些优化只是简单的降低了过程调用的开销，以及消除了一些妨碍优化的因素。但是随着进一步提高性能，我们必须考虑利用处理器微体系结构的优化，也就是处理器用来执行指令的底层系统设计。

实际上处理器的实际操作与通过观察机器级程序所察觉到的大相径庭。在代码级别上，我们认为程序是一条一条执行的，实际上，在实际的处理器中，使同时对多条指令求值的，我们称这个现象叫做指令并行.

我们对指令并行的认识来理解是什么限制了程序的最大性能：

• 当一系列操作必须按照严格顺序执行时，就会遇到延迟界限，因为在下一条指令开始之前，这条指令必须结束。当代码中的数据相关限制了处理器利用指令并行的功能时，延迟界限能够限制程序性能
• 吞吐量界限刻画了处理器功能单元的原始计算能力。这个界限时程序性能的终极限制。

整数操作

这是现代微处理器的一个简单的示意图。这和我们认知的处理器结构并不一样，我们称这种处理器是超标量的，意味着它可以在每个时钟周期执行多个操作，而且是乱序的——意味着指令执行的顺序并不一定要和它们在机器级程序中的顺序是一样的。整个设计由两个主要部分：控制单元和执行单元。前者负责从内存中读出指令序列，并根据指令序列生成一组针对程序数据的基本操作；后者负责执行这些操作。

ICU（控制单元）从指令高速缓存中读取指令，指令高速缓存是一个特殊的存储器，它包含最近访问的指令。ICU会在当前正在执行的指令很早之前取指，这样它才有足够的时间译码，并把操作发送到EU（执行单元）。同时处理器会使用分支预测预测目标地址，并使用投机执行的技术，处理器会开始取出位于它预测分支的地址的指令，在预测之前正确之前就执行这些操作。如果之后发现预测错误，则将状态重新设置到分支点的状态，并开始取出并执行另一个方向上的指令。

指令译码逻辑将接受实际的程序指令，并将它们转换成一系列的微操作。然后EU接受来自取指单元的操作。通常每个时钟周期会接受多个操作。这些操作被分配到功能单元中执行。

读写内存是由加载和存储单元实现的。加载单元处理从内存读数据到处理器的操作。存储单元处理从内存读数据到处理器的操作。这两个单元都有一个加法器来完成地址的计算。图中的数据高速缓存是一个高速存储器，存放着最近访问的数值。

使用投机执行结束对操作求值，但是最终结果不会存放在程序寄存器和数据内存中，直到处理器确定（确定预测是否正确）实际应该执行这些指令，分支操作被送到EU。如果预测错误，EU会丢弃分支点之后计算出来的结果。它还会发送信号告诉分支单元，说预测是错误的，并指出正确的目的和分支。

在ICU中，退役单元记录正在进行的处理，确保它们遵守机器级程序的顺序语义。退役单元控制这些寄存器的更新。指令译码时，关于指令的信息被防止在一个先进先出的队列中。这个信息会一直保持在队列中，直到发生：

• 一条指令的操作完成了，而且所有引起这条指令的分支点也都被确认为预测正确，那么这条指令就退役了，所有对程序寄存器的更新都可以被实际执行了。
• 如果引起该指令的某个分支点预测错误，这条指令会被清空，丢弃所有计算出来的结果。这样预测错误就不会改变程序的状态。

由于任何对程序寄存器的更新都是在指令退役的时候进行。为了加速从一条指令到另一条指令的结果的传送，许多信息都是在执行单元之间进行交换的，原理和之前的转发原理相同，只不过更加复杂精细。

实现操作数在执行单元间传送的常用机制是寄存器重命名。当一条更新寄存器r的指令译码时，产生一个标记t（一个执行该操作结果的唯一的标识符）。条目（r，t）被加入一张表中，这个表维护着每个程序寄存器与会更新该寄存器的操作的标识符间的关系。当某个执行单元执行完一个操作时，会产生一个结果（v，t）指明标记为t的操作产生值v。所有等待t为源的操作都能使用v作为源值，这就是一种形式的数据转发。

通过这个机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件中再读出来，使得第二个操作能够再第一个操作完成后尽快开始。重命名表只包含关于有未进行写操作的寄存器条目。如果一条被译码的指令需要某寄存器，但是又没有标记与这个寄存器相关联，那么可以直接从寄存器文件中获取这个操作数。

性能瓶颈

想要理解程序的性能，首先我们要能理解程序中的关键路径延迟。在迭代中，影响性能瓶颈的是迭代寄存器（在迭代中被更新，既作为操作数又作为结果的寄存器）的更新速度。因为其他的操作是可以利用现有的数据进行并行计算的，我们可以以下面的一个问题为例：

• 多项式求值

a₀ + a₁X + a₂X² + ……. + a_nXⁿ

这个求多项式的过程可以用下面的函数实现：

1
2
3
4
5
6
7
8
9
10

double poly(double a[],double x,long degree){
    long i;
    double result = a[0];
    double xpwr = x;
    for (i=1;i<=degree;i++){
        result += a[i]*xpwr;
        xpwr = x*xpwr;
    }
    return result;
}

• Horner法多项式求值(减少乘法数量)

a₀ + X ( a₁ + X (a₂ + …… + X (a_n-1 + Xa_n) … ))

这个求值过程，我们可以使用下面的函数实现：

1
2
3
4
5
6
7

double polyh(double a[],double x,long degree){
    long i;
    double result = a[degree];
    for (i=degree-1;i>=0;i--)
        result = a[i] + x*result;
    return result;
}

乍一看我们会认为下面的方法更加高效，因为相较于上面的程序，它只使用了一次乘法。但是事实真的是这样的嘛，我们测得poly的CPE比polyh更低。这是为什么呢？

我们可以判断程序的性能瓶颈主要体现在循环迭代的过程中，而迭代的性能是由迭代寄存器的更新的速度决定的。我们可以看到两个函数对迭代寄存器的更新情况：

• poly：他有两个迭代对象，分别是result和xpwr，由于数据的关联性，两个数据的迭代是互不干扰的。而制约迭代性能的关键则是xpwr的更新——一次乘法。
• polyh：它只有一个迭代对象result，它的每次更新需要一次乘法和一次加法，由于数据依赖的关联性，加法与乘法并不能并行处理。

所以综上所述，程序的性能实际上是由关键路径延迟所决定的，而不是由整体的运算量决定的。

开始算法的简单学习，今天先从二分查找法开始

二分查找

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int binary_search(int start,int end,int key){
    int ret = -1;
    int mid;
    while (start <= end){
        mid = start + ((end - start) >> 1);
        if(arr[mid] < key)
            start = mid + 1;
        else if(arr[mid] > key)
            end = mid - 1;
        else{
            ret = mid;
            break;
        }
    }
    return ret;
}

这个是常用的二分法的代码实现，但是在这里我们仍然有很多要注意的地方：

while的循环条件与start end更新

有时候会疑惑循环不变量中我们什么时候使用<或<=。而在start和end的更新中不知道什么时候使用+1或-1或不变。我们需要理解什么情况下怎么去使用。

当有序数组的数据呈闭区间的时候，即[start,end]。我们令：

1
2
3
4
5

while(start <= end)		//当我们考虑start=end时，条件必须成立，所以等于关系也是其中的一种情况
...
start = mid + 1		//由于每一次的比较中，先前mid的值经过了一次比较，所以需要+1-1来避免重复比较
...
end = mid - 1

当有序数组存在开区间时，如[) (] ()，实际上它们都隐含了一个信息——start!=end，否则区间是不成立的，因此：

1
2
3
4

while(start < end)	//当start=end时，搜索区间实际上是不成立的
...
start = ？？？	//这个和左右的开闭性相关，要考虑什么时候该包括，什么时候不该包括，应该明确有效的搜索区间的范围是什么
end = ？？？

二分法解题思路

我们刚刚实现的是bsearch，即二分查找匹配的数值，实际上更多时候我们需要查找的是一个区间，即在数组内查找第一个不小于X的数值的下标：

1
2
3
4
5
6
7
8
9
10
11
12

int lower_bound(vector<int> arr, int target){
    left = 0;
    right = arr.size() - 1;
    while (left <= right){
        int mid = left + (right-left)>>1;
        if (arr[mid] < target)
            left = mid + 1;
        else:
        	right = mid -1;
    }
    return left;
}

现在，如果程序要求我们返回数组中一个=\>\>=\<\<=某个数的起始下标，实际上可以根据数组的有序性，将他们联系起来：

• >= 这个是最基本的我们binary_search的返回值X就是它的左边界，得到答案 X
• > 我们可以把这个问题的转换成，>= x+1 ，得到答案X+1
• < 实际上就是>=问题的补集，得到答案(>=x) - 1
• <= 是>问题的补集，我们可以得到答案 （>x）-1

以后遇到这种问题，都可以通过这种转换的思想来实现

练习：

704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;

        while (start <= end){
            int mid = end + (start-end)/2;	//这里的除法我一开始使用了位运算，但是由于这里会涉及到有符号整数的运算，所以不能使用位运算
            int num = nums[mid];
            if(target > num)
                start = mid + 1;
            else if (target < num)
                end = mid - 1;
            else {
                return mid;
            }
        }
        return -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lower_bound(nums,target);
        if(nums.empty() || left == nums.size() || nums[left]!=target ){
            //当left==len(nums)时，说明数组中没有>=target的数
            return vector<int>{-1,-1};
        }
        int right = lower_bound(nums,target+1)-1;
        return vector<int>{left,right};

    }
    //返回>=target的第一个数
    int lower_bound(vector<int>& nums,int target){
         int start = 0;
         int end = nums.size() - 1;
         while (start <= end){
            int mid = (end - start)/2 + start;
            if(nums[mid] < target){
                start = mid + 1;
            }else{
                end = mid -1;
            }
         }
        return start;
    }
};

441. 排列硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int arrangeCoins(int n) {
        if(n==1) return 1;
        int start = 1;
        int end = n;
        while (start <= end){
            long mid = start + ((end - start)>>1);
            if (mid*(mid+1)/2 <= n)	//更新比较条件
                start = mid +1;
            else
                end = mid-1;
        }
        return start-1;		//由于得到的是大于n的阶层数，所以想要得到能完整标识的阶层数要-1
    }
};

367. 有效的完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool isPerfectSquare(int num) {
        int start = 1;
        int end = num;
        while(start <= end){
            long mid = start + ((end -start)>>1);
            if(mid*mid==num){
                return true;
            }else if(mid*mid >num){
                end = mid-1;
            }else{
                start = mid +1;
            }
        }
        return false;
    }
};

接着上一次的内容，中间有一段时间在忙着搞大作业的内容，所以就没继续搞这个了。今天我们将具体实现Y86-64的设计。

异常处理

异常控制流导致程序正常的执行流程被破坏掉。异常可以有程序内部产生，也可以由某个外部中断产生。我们的指令集主要包括三种类型：

• halt指令
• 非法指令和功能码组合的结果
• 取指或数据读写访问了非法地址

我们需要考虑的问题也比较简单：

1. 可能有多条指令引起异常。例如取指阶段遇到halt指令，然后访存阶段遇到了非法地址的访问。这个时候我们的处理器应该向操作系统返回哪个异常呢？我们的基本原则是：由流水线中最深的指令引起的异常，优先级最高，所以这里我们应该返回非法地址访问的异常

2. 当取出一条指令时，开始执行时，导致了一个异常，而后来由于分支预测错误，取消了该指令。例如：

1
2
3
4
5
6

	xorq %rax,%rax
	jne target			;处理器默认选择分支
	irmovq $1,%rax
	halt
target:
	.byte oxFF			;非法地址

流水线默认选择分支，在译码阶段会发现一个非法指令异常。但是之后又会发现不应该预测分支，流水线控制逻辑会取消该指令。但是我们想要避免这个异常

3. 流水线化的处理器会在不同的阶段更新系统状态的不同部分。有可能会出现这个情况，一个指令导致了一个异常，可是后面的指令在这个异常前改变了部分的状态。比如：

1
2
3
4

irmovq $1,%rax
xorq %rsp,%rsp		;CC=b100
pushq %rax			;假设此时的栈顶在0xfffffffffffffff8
addq %rax,%rax		;CC=b000

当push时，由于栈顶的移动会导致地址异常，同时addq此时位于执行阶段，它将条件码设置成了新的值。这就违反了异常指令之后所有指令不能影响系统状态的要求。

现在我们明确了我们需要解决的问题，首先需要避免由于分支预测错误取出的指令造成异常。所以我们要在每个流水线寄存器中包括一个状态码stat。如果一个指令在某个阶段中产生了一个异常，这个状态字段就被设置为异常的种类。异常和其他信息一起随着流水线传播，直到写回才发现异常，停止执行。

为了避免异常指令之后的指令更新任何程序员可见的状态，当访存或写回阶段中导致异常时，流水线控制逻辑必须禁止更新条件码寄存器或是数据内存。

所以综上所述，当流水线有一个或多个阶段产生异常时，信息只是简单的存放在流水线寄存器的状态字段中。异常事件不会对流水线中的指令流有任何影响，除了会禁止流水线后面的指令更新程序员可见的状态（条件码寄存器和内存），直到异常指令到最后的写回阶段。由于指令到达写回阶段的顺序就是异常发生的顺序，所以我们可以保证第一个发生异常的指令可以第一个到达写回阶段。如果取出了某条指令，过后又被取消了，那么所有的关于这条指令的异常信息都会被取消。所有导致异常的指令后面的指令都不能改变程序员可见的状态。携带指令的异常状态以及所有其他信息通过流水线的简单原则是处理异常的简单可靠的机制。

PIPE各个阶段实现

PIPE的具体实现和之前SEQ的实现基本差不多，只不过PIPE的每个状态都叫上了前缀。如”D_“表示源值，信息来自流水线D寄存器，而"d_"表示结果值，表明它是在译码阶段产生的。

PC选择和取指阶段

这个阶段用于选择程序计数器的当前值，用于预测下一个PC值。由于从内存中读取指令和抽取不同的字段的硬件单元一样，我就不重复了。

PC选择逻辑从三个程序计数器源中进行选择。当程序分支预测错误时，从M_valA中读出valP(不跳转的话本应执行的地址)。当ret指令进入写回阶段时，会从W_valM中读出返回地址。其他情况则会使用F阶段寄存器中的predPC的值，我们可以选择PC的值：

1
2
3
4
5
6
7
8
9

# f_pc 
# 分支预测有误则回退
if M_icode == JXX && !M_Cnd:
    f_pc = M_valA
# RET在写回阶段
else if W_icode == RET:
    f_pc = W_valM
else:
    f_pc = F_predPC

PC的预测逻辑则很简单。当函数为调用或跳转时，使用valC。否则用valP

1
2
3
4
5

# F_predPC
if f_icode in [JXX,CALL]:
    F_predPC = valC		
else:
    F_predPC = valP

关于Instr valid Need regids Need valC的逻辑块则和SEQ一样。

同时我们需要根据这些信息来确定程序的状态：

1
2
3
4
5
6
7
8
9
10
11
12

# f_stat
# 检查指令地址越界
if imem_error:
    f_stat = SADR
# 检查icode是否存在
else if !instr_valid:
    f_stat = SINS
# 检查手动中断
else if f_icode == HALT:
    f_stat = SHLT
else:
    f_stat = SAOK

译码和写回阶段

标号为"srcA" "srcB" "dstM" "dstE"的逻辑块我们在SEQ中已经实现过，基本不需要什么改动。不过我们也需要注意到，dstE和dstM写端口的寄存器ID不再是直接使用译码阶段所产生的，而是使用来自写回阶段的信号（W_dstE和W_dstM），这是因为我们希望写的目的寄存器是由写回阶段产生的。

不过这个阶段难在转发逻辑的实现上，尤其是”Sel+FwdA”块，不仅要实现valA的转发逻辑，还要实现valA和valP的合并。这两个信号之所以可以合并是因为，只有call和跳转指令才会用到valP的值，且不需要寄存器文件中读出来的值。这个选择通过icode信号可以控制实现。

接下来我们整理一下转发源和目的寄存器的关系以实现转发逻辑：

如果不满足任何的转发条件，就是用原来的d_rvalA作为输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# d_valA
# 注意这里的判断是有优先级的，阶段越浅的数据优先级越高，因为后执行的指令可能会覆盖先执行的指令的数据内容。同阶段的优先级需要特殊考虑
if D_icode in [JXX,CALL]:
    d_valA = D_valP
else if d_srcA == e_dstE:
    d_valA = e_valE
# popq %rsp会试图将两个值写入同一个寄存器中，valE是计算后的数据，有限考虑会造成冲突，与事实不符
else if d_srcA == M_dstM:
    d_valA = m_valM
else if d_srcA == M_dstE
	d_valA = M_valE
# 内存访问的值W_valM比计算出的值W_valE更"新鲜"
else if d_srcA == W_dstM:
    d_valA = W_valM
else if d_srcA == W_dstE:
    d_valA = W_valE
else:
    d_valA = d_rvalA

同理我们可以写出d_valB的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

# d_valB
if d_srcB == e_dstE:
    d_valB = e_valE
else if d_srcB == M_dstM:
    d_valB = m_valM
else if d_srcB == M_dstE:
    d_valB = M_valE
else if d_srcB == W_dstM:
    d_valB = W_valM
else if d_srcB == W_dstE:
    d_valB = W_valE
else:
    d_valB = d_rvalB

然后就是写回阶段的逻辑，写回阶段基本是不用保持不变的。其中Stat需要根据W中的状态值计算出来，因为W保存着最近完成的指令的状态，所以我们需要用这个信号来表示整个处理器的状态。不过也要考虑写回阶段有气泡时。这也是一种正常状态，我们可以写出：

1
2
3
4
5

# Stat
if W_stat == SBUB:
    Stat = AOK
else:
    Stat = W_stat

执行阶段

这一部分和SEQ种基本没有什么区别，其中e_dstE和e_valE被作为了指向译码阶段的转发源。不过有一点需要注意，SetCC不仅由icode控制，同时还以m_stat和W_stat作为输入。这样可以实现，当一条导致异常的指令通过后面的流水线时，任何对条件码的更新都会被停止。

访存阶段

访存阶段中SEQ和PIPE的逻辑基本差不多，区别在于，这里用了很多流水线的数值用来向译码阶段做转发源。同时我们在这里来验证程序地址的合理性从而计算m_stat：

1
2
3
4
5

# m_stat
if dmem_error:
    m_stat = SADR
else:
    m_stat = M_stat

流水线的控制逻辑

现在我们要创建我们的流水线控制逻辑，以完成我们处理器设计，我们需要处理以下四种情况，这是我们无法通过分支预测和数据妆发处理的：

• 加载/使用冒险：在一条从内存中读出一个值的指令和一条使用该值的指令之间，流水线必须暂停一个周期
• 处理ret：流水线必须暂停直到ret指令到达写回阶段
• 预测错误的分支：再分支逻辑发现不应该选择分支之前，分支目标处的几条指令已经进入流水线了。必须取消这些命令，并从跳转指令后面的那条指令开始取指。
• 异常：当一条指令导致异常，我们想要禁止后面的指令更新程序员可见的状态，并且再异常指令到达写回阶段时，停止执行。

我们先设计每种情况所期望的行为，然后再设计处理些情况的控制逻辑：

特殊控制情况所期望的处理

• 加载/使用冒险：

  只有mrmovq和popq指令会从内存中读取数据。当这两条指令中的任一一条处于执行阶段时，并且需要该目的寄存器的指令正处在译码阶段时（此时我们无法完成数据转发）。我们需要将第二条指令阻塞在译码阶段，并在下一个周期，往执行阶段中插入一个气泡。此后转发逻辑会解决这个数据冒险，可以将流水线寄存器D保持为固定状态，从而将一个指令阻塞在译码阶段。这样做还可以保证流水线寄存器F保持在固定状态，由此第二条指令会被再取指一次。总而言之我们需要保持流水线寄存器F和D不变，并在执行阶段中差插入气泡。

• 处理ret：

  对ret指令的处理，我们需要将流水线停顿三个时钟周期，直到ret经过了访存阶段，读出返回地址。我们遇到ret时会默认PC新值为valP，也就是下一条指令地址。然后会对下一条指令进行取指，在下一条指令的译码阶段会被插入气泡，空转三个周期。

• 分支预测错误：

  当跳转指令执行到执行阶段时就可以检测到预测错误。然后在下一个周期，控制逻辑会在译码和执行阶段插入气泡，取消两条不正确的已取指令。在同一个时钟周期，流水线将正确的指令读取到取指阶段。

• 异常：

  我们必须保证，在前面的所有的指令结束前，后面的指令不能影响程序的状态。当异常发生时，我们的stat信息作为指令状态的一部分记录下来，并且继续取指译码和执行命令。当异常指令到达访存阶段时，我们采取措施防止之后的指令会修改程序员可见的状态：（1）禁止执行阶段设置条件码（2）向内存中插入气泡，禁止数据向内存中写入（3）当写回阶段中有异常指令时，暂停写回阶段，暂停流水线。这样我们实现了异常发生之前的指令完成，异常发生之后的指令不对程序员可见的状态进行修改。

发现特殊控制条件

总结一下各个特殊控制触发的条件：

流水线控制机制

我们对流水线控制需要使用两个最简单的机制：暂停和气泡。它们分别将指令阻塞在流水线寄存器中（让真个流水线暂时停滞），或是往流水线中插入一个气泡（用空操作替换错误指令）。

• 在正常操作下，这两个输入都设为0，使得寄存器加载它的输入作为新的状态。
• 在暂停时，将暂停信号设置为1，禁止更新状态。
• 在气泡时，将气泡信号设置为1，寄存器状态会设置成一个固定的复位配置，得到一个等效于nop的状态
• 当暂停信号和气泡信号都设为1时会导致错误

当我们遇到特定的条件时，我们可以将各个阶段的流水线状态设置为以下情况，以控制流水线逻辑：

暂停后面跟气泡时为了取消进入该阶段的指令，避免产生影响

控制条件的组合

我们在之前的讨论中，默认一个时钟周期只能出现一个特殊情况，实际上，一个时钟周期可能会同时出现多种特殊情况的组合。我们把所有可能出现的特殊情况列出来，讨论它们组合的可能性。

从这里我们可以看出大多数的控制条件之间是互斥的。加载/使用要求执行阶段是加载指令，预测错误要求执行阶段是跳转指令，所以是冲突的。ret的另外两种情况也是同理。所以实际上只有组合A和组合B可能会出现。

组合A中执行阶段有一条不选择分支的跳转指令，而译码阶段有一条ret指令，这种组合要求ret位于不选择分支的目标处。流水线控制逻辑发现分支预测错误，因此要取消ret指令。由此我们可以得出控制逻辑的控制动作

因为下一个周期，PC选择逻辑会跳转到后面那条指令的地址，所以流水线寄存器F的保存的内容是无所谓的，因为正确的取指会覆盖他，错误的旧值会被取消。

组合B中包括一个加载/使用冒险，其中加载指令设置%rsp，然后ret用这个寄存器作为原操作数，因为它必须从栈中弹出返回地址。所以流水线控制逻辑应该将ret指令阻塞在译码阶段。我们看下组合B的控制逻辑的控制动作：

这里我们发现组合B需要进行特殊的处理。我们可以看到，在组合B的译码阶段，控制动作将寄存器的气泡信号和暂停信号同时设置成了1，这会导致错误。

实际上，我们在组合B中应该优先处理加载/使用冒险，我们要优先确保数据被成功加载后，再进行使用。所以这里将ret的处理推迟了一个周期。

控制逻辑的实现

下图是流水线控制逻辑的整体结构，根据流水线寄存器和流水线阶段的信号，控制逻辑产生流水线寄存器的暂停和气泡控制信号，同时决定是否更新条件码寄存器。

接下来我们将控制条件和控制动作结合起来，产生各个流水线控制信号的描述：

1
2
3
4
5
6
7
8
9
10
11
12
13

# F_stall
	# 加载/使用冒险
if (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
    F_stall = 1
	# ret处理
else if RET in [D_icode,E_icode,M_icode]:
    F_stall = 1
    
    
# D_stall
	# 加载/使用冒险
if (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
    D_stall = 1

遇到预测错误和ret指令时，流水线寄存器D必须设置成气泡。不过前面提到的对于加载/使用冒险和ret的组合，我们需要将流水线寄存器设置成暂停

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# D_bubble
	# 排除组合状态
if not (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
	if RET in [D_icode,E_icode,M_icode]:
        D_bubble = 1
	# 分支预测错误
else if E_icode == JXX && !e_Cnd:
    D_bubble
  

# E_bubble
	# 分支预测错误
if E_icode == JXX && !e_Cnd:
    E_bubble = 1
	# 加载/冒险使用
else if (E_icode in [MRMOVQ,POPQ] and E_dstM in [d_srcA,d_srcB]):
    E_bubble = 1

同时为了避免异常后的指令更新了程序状态，我们设置条件码不被整数操作设置：

1
2
3
4

# set_cc
if E_icode == OPq:
    if (not m_stat in [SADR,SINS,SHLT] and not W_stat in [SADR,SINS,SHLT]):
        set_CC = 1

同时，在下一个周期需要向访存阶段插入气泡，因为如果访存或写回阶段有异常时，我们不希望其他的指令改变了内存状态：

1
2
3
4
5

# M_bubble
if m_stat in [SADR,SINS,SHLT]:
    M_bubble = 1
else if W_stat in [SADR,SINS,SHLT]:
    M_bubble = 1

为了在写回阶段将异常提交到异常处理程序，所以我们也需要在异常指令到达W阶段时，阻塞整个流水线。从而实现异常之前的指令都被完成，后续的指令像没执行过一样：

1
2
3

# W_stall
if W_stat in [SADR,SINS,SHLT]:
    W_stat

至此，我们处理器的流水线控制逻辑就实现了。

一下子就到七月了，我六月的总结并没有写，因为六月比较忙…前半个月急着复习。后半个月忙着玩儿和打游戏。

上次说这个学期希望绩点高一点，我对这个学期的绩点还算比较满意吧，好歹花了很多时间精力在上面。然后是时长两周的小学期，感觉还是很不错的，前端的基础知识稍微巩固了一下，同时学习了很多新的东西，相较于刚开学的时候自己学前端，现在很多思路就很清晰。项目实践也比较容易上手。最有意思的是接触了一下XSS漏洞，发现网络安全也是很有意思的，并没有想象中的那么难，感觉是一个很好的上手点。

然后就是联系了一位老师做我的导师，他的方向是混沌密码学，他建议我尝试将混沌密码学用于图像编码，以此作为研究方向。让我去研究一些相关的知识和阅读其他的论文。但是感觉我的数学和英语基础还是比较薄弱，这样也是我需要加强的地方。

接下来的话，做下暑假的安排吧，我就先规划一下七月的，八月的之后再说：

• 首先是CSAPP的学习从现在开始的一周内，至少要学到第七章链接。
• 然后是接下来时间争取能学完第九章，在八月份之前。
• 平时累了的时候要着手开始学习算法，目前的打算是跟着OIwiki入门，争取每天写2~5题，学一个新的知识点
• 在时间有多的情况下，要开始学习Java，因为之后的很多知识都不可避免的要用到它
• 坚持每天都要背单词，先把四级背完
• 然后是这个月要把科目二结束，争取下个月可以把科目三过完

感觉暑假要做的事情很多，当然，可以做的事情也很多。要抓住这个机会，提升强化基本功能力，好迎接下个学期大量的专业课程和专业知识。加油呀相信自己。

我有时候也会在想自己为什么要学的这么辛苦，是因为喜欢吗，是为了更优秀一点吗。可能都有吧，关键是我想这么做，也许想学的时候也会学一学吧，想玩的时候也会好好玩一下吧。也许我的目标和规划做的到，也许做不到。但是没关系，我想这么做就行了。

文章原文：mov is Turing-complete ——by Stephen Dolan，Computer Laboratory, University of Cambridge

不使用特殊的寻址模式，代码自修改，和运行时生成代码。用mov实现图灵完备的模拟器

介绍

我们在学习下x86的指令集中我们时常会用到MOV指令。我们通常使用它的多种寻址模式：

• 用于内存数据的加载和存储
• 加载立即数到寄存器中

但是它并不具备比较和分支跳转的功能，所以我们一般认为MOV不是图灵完备的

但是实际上在x86的处理器中，我们可以通过mov来加载或者自修改代码来实现图灵完备性，但是这并不是我们想要的。

执行有限数量的mov指令将会在有限时间内结束。为了验证它的图灵完备性，所以我们需要无限循环。因此我们的图灵机将由一系列mov指令组成，执行完成后无条件跳转到第一条指令继续执行。

机器模型

我们将使用一个简单的抽象机器模型，我们介绍其组成：

• 一个由字组成的随机存储内存：每一个字可以存储一个内存地址或一个偏移值（偏移值只能是0或1，其中偏移值不被视作一个有效的内存地址）
• n个寄存器R₁ R₂ … R_n ：我们暂时假设我们会用到很多寄存器，不过我们之后会讨论怎么减少使用寄存器的数量
• Intel格式的mov指令：
  • 加载立即数：mov R_dest,c
  • 索引加载：mov R_dest,[R_src+R_offset]
  • 索引存储：mov [R_dest+R_offset],R_src
• 内存：内存被逻辑的划分为单元，这些单元都是成对的相邻的字。我们的加载存储操作本质可以视作是在这些单元中进行的。我们的指令从偶数的地址开始，我们使用两个寄存器，其中一个用来确定单元的地址R_src，另一个用来确定使用哪个字R_offset

使用这些组成，我们就可以模拟一个由mov进行的图灵机了

表示图灵机

我们使用一个元组来描述图灵机M:

1

M = (Q,q0,∑,σ0,δ)

• Q是一个有限状态集，其中指定一个起始状态q0∈Q
• ∑是有一个有限符号集，其中指定一个空白符号σ0∈∑
• δ是一个转换函数，图灵机根据当前的状态和读取到的符号决定：
  • 写入带上的新符号（Σ 中的一个符号）
  • 磁头移动的方向（左 L 或右 R）
  • 转换到的新状态（Q 中的一个状态）

图灵机有一个磁带，由无限多个位置组成，每个位置上有一个单独的符号。图灵机会持有一个当前的状态q0，和当前的位置（初始位置为磁带的最左边，磁带向右无限延申）。每个磁带的位置都被初始化为空白符号σ0。

图灵机会反复计算转换表δ，如果当前的状态和读取到的符号的情况在δ中并没有被定义，机器将会终止。如果是已有定义（σ，d，q），那么机器会将当前的状态设置为q，将σ写入当前的位置，同时根据d来决定纸带的跳转方向（如果d=L向左，如果d=R向右），然后机器继续运行。

我们可以在内存单元中表示我们的符号集。我们首先要将图灵机的符号集∑映射到每个单元中，符号集中的每个符号都对应一个内存的单元，这些单元的地址被描述为S₁，S₂，…，S_|∑|，其中|∑|是符号集的数量，即大小。每个单元S_i的内容是未指定的，他可能包含任何值。但是对于第一个内存单元S₁，它的值始终是空白符号σ0。

接下来我们要在计算机内存中表示图灵机的状态和转换表。转换函数实际上就是根据当前给定的状态和当前读取的符号，来给出图灵机要进行的操作。我们可以理解为δ(σ,q) = (σ',d',q')。在内存中，每个状态q被表示为出转换的列表。每个做出转换被表示为一个包含四个元素的元组(σ,σ‘,d’,q’)，其中：

• σ表示当前状态下图灵机读取到的符号。在内存中，这个符号被表示为对应单元S_i的地址
• σ’表示图灵机在当前单元写入的新符号。在内存中，这个符号被表示为对应单元S_j的地址
• d’表示图灵机的读写头移动的方向。在内存中，这个状态被表示为一个数字，0L1R
• q’表示图灵机转换后的新状态。在内存中，对应出转换列表的地址

我们用一张图片来描述这个过程：

这个Q₀和Q₁则是转换的规则，我们可以根据它确定图灵机接下来的行为。

内存中的其他单元则用来表示我们图灵机中的磁带。我们假设磁带是无限长的（尽管现实中的内存地址是有限的），我们将单元按T₁,T₂,…来进行，命名使得T_n的中的字就是S₁的地址，T_n+1中的字是T_n+1的地址

通过这个方式，我们可以将T₁视作一个无限的表的起始，且无限的表中的每一个元素的初始值为S₁。在讨论图灵完备的过程中，我们通常只关心计算的过程，而忽略输入和输出。我们假设在程序开始前，输入是一串符号队列，从T₁到T_n。而输出则是在指令执行结束后，纸带上的值就是输出。

比较和条件语句

计算的基础之一就是分支，根据运行的值选择下一个要执行的操作，我们接下来尝试用mov来实现它。

我们可以用一下方式来比较A和B是否相等：

1
2
3

mov [R_i],0
mov [R_j],1
mov R_k,[R_i]

我们可以根据R_k的值判断R_i和R_j是否相等。如果R_i和R_j相等，那么相当于向同一个地址写入了两次值，如果不相等，[R_i]处的值就不会被修改。所以A=B->1 A!=B->0

我们也可以比较一个指定的值和N是否相等：

1
2
3
4
5

mov X,[R_i]
mov [N],0
mov [R_i],1
mov R_j,[N]
mov [R_i],X

原理同上，只不过这里我们用X保存了R_i地址上的数据

这个原理允许我们实现比较语句，结果要么是0要么是1。我们可以用这些结果去选择不同的值。如我们上面所说的在一个单元中我们可以根据index(即R_k)来计算使用哪个字。假如N是其中一个单元格的地址，我们就可以利用比较的结果来判断读取单元中的哪个字：

1
2
3

mov [N],R_i
mov [N+1],R_j
mov R_l,[N+R_k]

通过这些操作我们已经可以模拟一个图灵机了

模拟图灵机

• 我们使用T来存储当前的要测试的转换（存储了转换规则的地址）
• 使用S来存储当前读取的符号（用来查找规则）
• 使用L来代表当前位置左侧磁带部分的列表
• 使用R来代表当前位置右侧磁带部分的列表（LR可以用来模拟读写头移动的操作）

磁带由L+S+R组成

程序的开始，T会存储Q₀的地址，S存储T₁的地址，L存储N的地址（代表空列表，用于逆向存储左边磁带的部分。这样最近的位置总是左边的列表的第一个元素，这样向左处理无需移动整个列表），R存储T₂的地址（初始时为T，即磁带上除了第一个位置外所所有位置的列表）。L和R寄存器中的列表被视作栈，当图灵机向右移动时，当前的符号S被推入L队列中，R队列中的符号被弹出到S。同时由于我们会经常用到N，所以我们设置寄存器N始终保存地址N。

介绍完这些前置的条件，我们现在开始实现图灵机：

首先我们需要根据当前符号S和转换规则T来判断是否应该触发转换：

1
2
3
4
5
6

mov X,[T]		;获取转换规则
mov X,[X]		;获取触发符号
mov Y,[S]		;获取当前符号
mov [Y],0		;比较当前符号与触发符号
mov [X],1
mov M.[Y]

再此基础之上，我们构造功能来更新当前符号，当M=1(匹配)时触发

1
2
3
4
5
6
7
8

mov X,[T]		;获取转换规则（触发符号,新符号,...）
mov X,[X+1]		;跳过触发符号
mov X,[X]		;加载新符号	
mov Y,[S]		;记载旧符号
mov [N],Y		;选择新旧符号
mov [N+1],X
mov Z,[N+M]
mov [S],Z		;写入新符号

接着，我们加载纸带的移动方向：

1
2
3
4

mov D,[T]		;获取转换规则（触发符号,新符号,方向,...）
mov D,[D+1]		;跳过触发符号
mov D,[D+1]		;跳过新符号
mov D,[D]		;加载方向

然后根据D的值0左1右。将单元添加到磁带栈上的过程是，先将磁带栈的顶端写为[S+1]，然后修改磁带栈寄存器为S，下面这个是将S压入栈顶的过程：

1
2
3
4
5
6
7
8
9
10

mov [N],R		;获取[S+1]的值（[S+1]就是下一个要被读取的符号）
mov [N+1],L
mov X,[N+D]
mov [S+1],X
mov [N],L		;确定L的值
mov [N+1],S
mov L,[N+D]
mov [N],S		;确定R的值
mov [N+1],R
mov R,[N+D]

我们必须确认只有在转换规则匹配的时候才有移动。如果不匹配的话，我们需要翻转刚刚D的值，以复原移动

1
2
3
4
5
6

mov [N],1		;X~=D
mov [N+1],0
mov X,[N+D]
mov [N],X 		;选择X或者D
mov [N+1],D
mov D,[N+M]

接下我们将根据D的值将栈顶的值弹出至S:

1
2
3
4
5
6
7
8
9
10

mov [N],L		;获取S的值
mov [N+1],R
mov S,[N+D]
mov X,[S+1]		;获取L或R的栈顶元素
mov [N],X		;为L赋值
mov [N+1],R		;这里让L=R看起来很奇怪，实际上刚刚更新了当前的S_current = R_old，此时R栈顶尚未更新
mov L,[N+D]		
mov [N],R		;当左移时
mov [N+1],X
mov R,[N+D]

如果M是匹配的话就会正常移动，不匹配就会不动。然后接下来我们要更新图灵机的状态：

1
2
3
4
5
6
7
8
9

mov X,[T+1]		;加载下一个转换列表的地址
mov Y,[T]		;获取转换规则（触发符号,新符号,方向,下个状态的转换列表）
mov Y,[Y+1]		;跳过触发符号
mov Y,[Y+1]		;跳过新符号
mov Y,[Y+1]		;跳过方向
mov Y,[Y]		;获取下个状态的转换列表的地址
mov [N],X
mov [N+1],Y
mov T,[N+M]

不过有时候也会出现没有合适的转换规则的情况，这个时候我们需要做一个验证，检测是否到达了某个状态列表的末尾：

1
2
3
4
5

mov X,[T]
mov [N],0	;这里N代表空列表的地址，所以用T与N比较
mov [T],1
mov H,[N]
mov [T],X

如果H=0我们需要停止机器，我们通过从无效地址0中读取来实现这一点：

1
2
3
4

mov [N],0		;从0或N中选择
mov [N+1],N		
mov X,[N+H]
mov X,[X]		;加载0或N

如果程序地址没有终止程序，说明我们找到了下一个转换规则并将指针指向了T。同时我们将当前符号存放在S中。因此我们现在又一次的处于了一个合适的状态中，我们跳转到开始，再次重复上述的过程，这就是一个图灵机的完整的行为过程：

1

jump start

我们把之前的SEQ结构已经实现了，可是为了更好的符合流水线执行的特性，为我们需要对顺序的SEQ处理器做一点小的改动，我们需要将PC的计算拿到取指阶段。然后在不同的阶段之间留下流水线寄存器来保存状态。

Y86-64的流水线实现

SEQ+：重新安排计算阶段

我们要把更新PC的阶段放在取值阶段，在第一个时钟周期开始执行。这样可以保证每个周期都能做到去除指令，从而实现流水线运作的状态。我们把这种改动后的结构称为SEQ+

我们可以注意到，在SEQ中PC的计算是根据当前时钟周期中的信号值和数据机型计算的。而在SEQ+中PC的计算则是根据上一个时钟周期产生的信号计算得到的。我们可以在下面的整体架构中起初的看到这一点

要特别指出，在SEQ+中并没有设置硬件来保存当前的PC，而是根据前一条指令保存下来的状态信息动态的计算出PC

插入流水线寄存器

这是更新后的SEQ+架构，但是我们需要向其中插入流水线寄存器，以保存每个阶段的状态信息和数据

我们将流水线寄存器插入之后，可以得到PIPE-处理器，两者的硬件架构实际上差不多，但是信号的含义并不完全相同，我们接下来介绍一下其架构功能：

流水线寄存器的功能如下：

• F 保存程序计数器的预测值
• D 位于取指和译码阶段之间。它保存关于最新取出的指令的信息，即将由译码阶段进行处理
• E 位于译码和执行阶段之间。它保存关于最新译码的指令和从寄存器文件中读出的信息，接下来交给执行阶段处理
• M 位于执行和访存阶段之间。它保存最新执行的指令的结果，即将由访存阶段进行处理。它还保存关于用于处理条件转移的分支条件和分支目标的信息
• W 位于访存阶段和反馈路径之间，反馈路径将计算出来的值提供给寄存器文件写，当完成ret指令时，它还要向PC选择逻辑提供返回地址

在PIPE-处理器中我们流水线执行指令的效果是这样的：

对信号进行重新排列和标号

在之前的SEQ和SEQ+架构中，我们在每个时刻只处理一条指令，因此每个信号值在同一个时刻的都是唯一的值。在流水线化的设计中，不同的阶段使用和保存的是不同的信号值所以我们需要加以区分。并使用重新的命名机制。我们将流水线寄存器中的信号前面用大写的前缀标识，如D_atat E_stat M_stat W_stat。对于从一个阶段中计算出来的值，我们用小写开头来标识，不过特别注意实际状态Stat是由写回阶段计算出来的。

下面我们需要注意几个特别的地方：

1. 在译码阶段会产生dstM和dstE的值，他们指明valE和valM的目的寄存器。在SEQ+中我们可以直接将信号连到写端口地址输入。在PIPE-中，会在流水线中一直携带这样的信号穿过执行和访存阶段，直到写回才送到寄存器文件中。这样是为了确保写端口地址和数据输入最终是来自同一条指令。不然写回的数据是写回阶段的，但是给定的写端口却是取值阶段的。我们要避免这种情况
2. PIPE-中一个块在相同的表示形式的SEQ+中是没有的，那就是译码阶段中的SelectA块。这个块会从寄存器文件中的valA和流水线寄存器中D中的valP中的选出一个值作为流水线寄存器E的valA值。这个块用来减少携带给流水线寄存器E和M的状态数量。在所有的指令中，只有call在访存阶段中需要valP的值，只有跳转指令在执行阶段需要valP，而又恰好这些指令都不需要从寄存器文件中读出来的值。所以我们用这个块来合并这两个信号，将它作为valA携带穿过流水线，从而可以减少流水线寄存器的状态数量。
3. 不同阶段之间的流水线寄存器中包括一个状态码stat字段，开始时是在取指阶段计算出来的，但是在访存阶段可能因为错误访问导致修改状态。所以最好的办法就是让与每条指令关联的状态码和指令一起通过流水线，像图中一样。

预测下一个PC

在PIPE-设计中我们通过流水线化的设置使得每个时钟周期都发送一条新的指令，也就是说每个时钟周期都有一条新的指令进入执行阶段并最终完成。但是这要求我们取出一条指令之后能够立马确定下一条指令的文职。但是，当我们取出的是ret或者条件分支指令的时候，我们需要几个周期后才能确定返回的地址。

除了条件转移指令和ret以外，根据取指阶段中计算出来的信息，我们都能够确定下一条指令的地址。对于call和jmp而言，下一条指令的地址就是指令中的常数字valC，而对于其他指令来说就是valP。因此，我们对于这些指令都可以实现PC的预测。

而对于条件转移，我们既可以预测选择了分支，新PC为valC；也可以预测没有选择分支，新PC为valP。这种情况叫做分支预测，我们会在之后讨论这个问题。

对于ret指令的PC值的预测。通条件转移不同，此时可能的返回值是无限的，因为返回地址是位于栈顶的字，其可能是任意的。在设计中，我们不会试图对返回地址进行预测。只是简单的暂停处理新指令，直到ret指令完成写回，我们之后会讨论这个内容。

PIPE-的取指阶段，负责预测PC的下一个值，以及为取指选择实际的PC。其中标号为”Predict PC”的块会从PC增加器计算出的valP和取出指令中得到的valC中进行选择。然后将这个值放在流水线寄存器F中，作为程序计数器的预测值。

流水线冒险

将流水线技术引入一个带反馈的系统，当像相邻指令间存在相关时则会出现问题。这些相关有两种形式：

• 数据相关：下一条指令会用到这一条指令计算出的结果
• 控制相关：一条指令要确定下一条指令的未知。如执行跳转、调用或返回指令时。

这些相关可能会导致流水线产生错误，我们称之为冒险（分为数据冒险和控制冒险，我们先考虑数据冒险），这里我们可以了解一下不同程序状态可能产生的冒险的类型和状态：

• 程序寄存器：寄存器文件的读写是在不同的阶段进行的，导致不同指令之间可能出现不希望的相互作用
• 程序计数器：更新和读取程序计数器之间的冲突会导致控制冒险。当我们的取指阶段在取下一个指令之前，正确预测了程序计数器的新值时，就不会产生冒险。预测错误的分支和ret指令需要特殊处理。
• 内存：对数据内存的读和写都发生在访存阶段。在一条读内容的指令之前，我们需要将所有写内存的指令都完成，以免读写的状态不一样。同时我们要确保写入的内存空间不会影响指令代码，所以我们在此禁止，指令自我修改的情况。
• 条件寄存器：在执行阶段中，整数操作会写这些寄存器。条件传送指令会在执行阶段以及条件转移会在访存阶段读这些寄存器。在条件传送或条件转移到达执行阶段前，整数操作就已经完成了这个阶段。所以不会发生冒险
• 状态寄存器：指令经过流水线时，会影响程序状态。我们采用流水线中的每个指令都与一个状态码关联的机制，使得发生异常时，处理器可以有条理的停止。

我们用图片简单的演示一下冒险的发生：

上面展示了不同情况下可能发生冒险的情况及其原因。我们可以用以下几种方法来避免冒险：

用暂停来避免数据冒险

暂停时，处理器会停止流水线中一条或多条指令，直到冒险条件不再满足。让一条指令停顿在译码阶段，直到它的原操作书通过了写回阶段，这样我们的处理器就能避免数据冒险。例如：

当addq指令处于译码阶段时，流水线控制逻辑发现执行、访存或写回阶段中至少有一条指令会更新寄存器rdx或rax。处理器不会让addq指令带着错误的结果通过，于是会暂停这个指令，将其阻塞在译码阶段。直到得到正确的源操作数，然后沿着流水线继续执行。当然addq指令被阻塞在译码阶段时，halt指令也被阻塞在取指阶段，我们通过保持PC不变来实现这一点。

总之，暂停技术就是让一组指令阻塞在他们所处的阶段，而允许其他指令继续通过流水线。我们实现所用的方法是：每次要把一条指令阻塞在译码阶段，就像执行阶段插入一个气泡，气泡就像一个自动产生的nop指令——它不会改变任何程序状态。关于其详细机制，我们之后会讨论

在实际的指令中，像这样的数据冒险十分常见。如果我们频繁的使用暂停，会导致流水线的效率下降，严重降低了整体的吞吐量

用转发避免数据冒险

PIPE-的设计是在译码阶段从寄存器文件中读入原操作数。但是这些源操作数只有在写回阶段才能进行。与其等其暂停写入，不如直接将要写的值传到流水线寄存器E作为源操作数。这种将结果值直接从一个流水线阶段传到较早阶段的技术称为数据转发。例如：

不仅如此，为了充分利用数据转发技术，我们还可以将访存阶段对寄存器没有完成的写和执行阶段新计算出来的值转到译码阶段。

总结一下，我们可以将还没有写回的信号（W_valM，W_valE）转发到我们的E端口。也可以将刚从内存中读出的信号m_valM转发。也可以将尚未进行访存的信号M_valE进行转发。或者是将刚计算出来的e_valE进行转发。也就是说，我们有五个转发源（e_valE，m_valM，M_valE，W_valE，W_valM）和两个不同的转发目的（E_valA，E_valB）

我们在硬件层面上实现转发的功能，从而得到我们最终的PIPE处理器架构，使得我们不用暂停流水线就能处理大多形式的数据冒险。

这就要求处理器在译码阶段能够检测转发需求，所以我们看到来自五个转发源的值反馈到译码阶段中两个标号为”Sel+Fwd A”和”Fwd B”的块。标号为”Sel+Fwd A”的块是”SelectA”功能和转发逻辑功能的组合。它允许流水线寄存器E的valA位已增加的程序计数器valP，从寄存器文件A端口读出的值，或者某个转发过来的值。

加载/使用数据冒险

有一类数据冒险不能简单的使用转发来解决。这是因为内存读在流水线中发生的比较晚，我们以下图为例。可以看到，我们在周期7想要将数据转发时，程序还没有访问到指定内存的值

我们可以将暂停和转发结合起来，来避免加载/使用数据冒险。这个做法需要改变控制逻辑，但是我们可以使用现有的旁路路径。当流水线控制逻辑发现译码阶段的指令需要从内存中读取出来的结果是。它会将译码阶段中的指令暂停一个周期，导致执行阶段中插入一个气泡。从而实现避免数据冒险

这种用暂停来处理加载/使用冒险的方法称为加载互锁。加载互锁和转发技术结合起来足以处理所有可能的数据冒险类型，因为加载互锁出现的情况有限，流水线的吞吐效率几乎不会受到影响

避免控制冒险

当处理器无法根据取指阶段来确定下一条指令的地址时，就会出现控制冒险。不过控制冒险指挥发生在ret指令和跳转指令，我们将简单谈论其处理方式。

ret

ret控制冒险的处理比较简单，我们只需要在ret的译码、执行、访存阶段时，暂停流水线，在处理过程中插入三个气泡。当指令到达写回阶段，PC选择器就会选择返回地址作为指令的取指地址。从而避免控制冒险

分支错误预测

我们以一个汇编程序为例

1
2
3
4
5
6
7
8

0x000:	xorq %rax,%rax	
0x002:	jne target
0x00b:	irmovq $1,%rax
0x015:	halt
0x016:target:
0x016:	irmovq $2,%rdx
0x020:	irmovq $3,%rbx
0x02a:	halt

处理器处理的流程如下图

首先程序的预测分支逻辑会选择分支，于是在周期3中会把target指令进行取指。在周期4中，target进入译码，而target+1被取指，此时跳转指令会在执行阶段判断是否应该进行跳转。如果选择分支，则保持程序逻辑不变；如果不应该选择分支，我们则应该停止执行这两条命令（我们需要在下一个周期往译码和执行阶段插入气泡，并取消这两个错误的指令）。在周期5中，程序的条件码被改变，我们需要取消两条跳转预测指令，同时取指一条跳转指令后面的指令，从而避免了分支预测错误导致的控制冒险。

所以综上所述，通过暂停和往流水线中插入气泡的技术可以动态调整流水线的流程。我们对基本时钟寄存器设计的基本拓展可以实现暂停流水线，并向流水线控制逻辑一部分的流水线寄存器中插入气泡，从而实现避免控制冒险。

我们已经基本了解了Y86-64的指令集和汇编的用法，现在我们要尝试模拟处理器的硬件行为。这里描述一个称为SEQ的处理器，我们了解它的使用过程，并尝试构建它。

Y86-64的顺序实现

将处理组织成阶段

处理一条指令包括很多的操作和步骤，如果我们有序的将其进行划分。我们就可以得到一个顺序序列，所有的指令都可以按这个顺序进行处理，从而实现高效的流水线处理。我们可以将其划分为几个阶段：

• 取址：从内存读取指令字节，读取地址为当前PC的值。先取出指令指示符字节的两个四位部分：icode和ifunc，然后根据指令类型判断是否要取出寄存器指示符字节和8字节常数字。然后再按顺序计算当前指令的下一条指令的地址，将其作为下一次取指的PC。
• 译码：从寄存器文件中读入最多两个操作数，得到值valA和valB。读入的寄存器是rA和rB指明的寄存器。
• 执行：在执行阶段，ALU要么根据ifunc的值，计算内存引用的有效地址；要么增减栈指针。我们将得到的数据称为valE。同时执行阶段也可能会设置条件码，对于条件传送指令来说，这个阶段会检验条件码和传送条件(ifun)，如果条件成立，就更新目标寄存器。同样的，对于跳转指令，这个阶段决定是否应该选择分支。
• 访存：该阶段将数据写入内存，或从内存中读出数据。读出数据称为valM
• 写回：写回阶段最多将两个结果写到寄存器文件
• 更新PC：将PC设置为下一条指令的地址

处理器会不停的执行这些阶段，从而实现执行指令的功能。

而现在的难点在于我们怎么将每一个指令转换成这些阶段内，以实现处理器的按阶段执行，我们需要好好处理一下。

OPq rrmovq irmovq

这几个指令的共同点在于计算了一个值，并将值存放在寄存器中。而OPq则代表四个整数操作，因为它们只有OPq操作和ifunc值是不一样的，所以我们统一处理。这里的M_x[]的x指的是从内存中读取的字节数。

注意到并不是每个阶段都需要进行处理

rmmovp mrmovp

这两个指令都有访存阶段

pushq popq

这个过程的实现相对复杂，同时pushq和popq的实现过程，正是上一篇中push %rsp和pop %rsp行为的答案

jXX call ret

这三个指令都有控制转移的处理，有跳转，所以我们放到一起来进行讨论

这里需要注意JXX的执行阶段，我们通过条件码和跳转条件来确定是否选择分支，并将其设置为位信号Cnd

SEQ的硬件结构

我们将指令组织成了6个阶段来进行，现在每个阶段我们使用一个硬件单元来负责这些处理。这样子，在每个时钟周期，一个硬件都可以完成一次处理。现在我们根据这张图介绍一下硬件单元和各个处理阶段的关联：

• 取指：将PC作为指令内存的地址，读取指令的字节。使用PC增加器计算valP，即增加后的PC
• 译码：寄存器文件有两个读端口A和B,从这两个端口同时读寄存器值valA和valB
• 执行：执行阶段会根据指令的类型，将ALU用于不同的目的。同时计算条件码的新值。并根据跳转类型和条件码设置分支信号Cnd
• 访存：在访存时，数据内存读出或写入一个内存字。
• 写回：寄存器文件有两个写端口。端口E用来写ALU计算的值，端口M用来写从数据内存中得到的值
• PC更新：程序计数器的新值选择自：valP，下一条指令的地址；valC，调用指令或跳转指令指定的目标地址；valM，从内存读取的返回地址

我们可以这样笼统的表现我们的一个计算过程：

SEQ的时序

我们从软件层面上的习惯会使得我们认为，这几个阶段是从上到下按顺序执行的。但是SEQ作为一个硬件模型，它的操作运行并不一样。一个时钟变化会引发一个经过组合逻辑的流，从而执行整个指令。我们不妨分析一下这个行为。

SEQ的硬件实现主要由组合逻辑和两种存储器设备：时钟寄存器（程序计数器和条件码寄存器），随机访问存储器（寄存器文件，指令内存和数据内存）。组合逻辑则不需要任何时序和控制，只要输入变化了，值就通过逻辑电路传播。

我们由四个硬件单元需要对他们的时序进行明确的控制——程序计数器，条件码寄存器，数据内存和寄存器文件。这些单元通过一个时钟信号来控制，它触发将新值装载到寄存器，以及将值写到随机访问存储器。

我们可以看看这几个硬件单元的不同：

• 每个时钟周期，程序计数器都会装载新的指令地址。
• 只有在进行整数运算指令时，才会装载条件码寄存器。
• 只有在执行rmmovq pushq call时，才会写数据内存。
• 寄存器文件的两个写端口允许每个时钟周期更新两个程序寄存器，我们可以通过特殊ID 0xF来作为端口地址，表明端口不进行写操作

也就是说实际上，每个硬件的功能是同时进行的，且互不干扰的。我们用它来执行我们的程序，这就对我们的指令有着“从不回读”的要求。这意味着处理器从来不用为了完成一条指令的执行而去读由该指令更新的状态。

以pushq %rsp为例，如果是先将%rsp-8，在将更新后的%rsp作为写操作的地址。这就是错误的，为了执行内存操作，他需要先从寄存器中读更新过的栈指针，这是错误的。因为在硬件各个阶段同步执行下，没有一个指令可以即设置自己的状态又根据这个状态继续执行。

SEQ阶段的实现

取指阶段

取指阶段包括指令内存硬件单元。以PC作为第一个字节的地址，这个单元读取10个字节。

• 第一个字节为Split单元：
  • 高四位用来得到icode
  • 第四位用来得到ifunc
• 第二到十个字节为Align单元：
  • 第一个字节用来得到rA和rB根据高低四位得到
  • 后八个字节用来得到8字节常数valC

根据icode的值我们可以计算三个一位的信号：

• instr_valid：用来判断icode的是否是一个合法的指令
• need_registers：这个指令是否包括一个寄存器指示符字节
• need_valC：这个指令是否包括一个常数字

1
2
3
4
5
6
7
8
9
10
11

# need_registers 实现
if icode in [RRMOVQ,OPQ,PUSHQ,POPQ,IRMOVQ,RMMOVQ,MRMOVQ]:
	need_registers = 1
else:
    need_registers = 0
    
# need_valC 实现
if icode in [IRMOVQ,RMMOVQ,MRMOVQ,JXX,CALL]:
    need_valC = 1
else:
    need_valC = 0

我们根据信号来获取rA rB valC，如果need_registers==1，第二个字节分开装入rA和rB。对于valC，如果need_registers==0&&need_valC==1，第二到九个字节装入常数字valC；如果need_registers==1&&need_valC==1，则将第三到十个字节装入常数字valC

PC增加器应将单元则根据当前的PC以及两个信号need_valC和need_registers的值得到信号valP。对于PC值p，need_registers值r，以及need_valC值i，增加器产生的值为PC = p + 1 + r + 8*i

译码和写回阶段

之所以将译码和写回阶段放在一起，是因为它们都要对寄存器文件进行访问。

寄存器文件中有四个端口，其支持同时进行两个读（对端口A和B）和两个写（在端口E和M）。每个端口都有一个地址连接线（rArB）和一个数据连接线（icode）。地址连接线是寄存器ID，数据连接线则既可以做输出字也可以做读取字。两个读端口的地址输入为srcA和srcB，两个写端口的地址输入为dstE和dstM。如果某个地址端口上的值为0xF(RNONE)则代表不需要访问寄存器。

现在我们可以写出四个端口的输出情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# srcA
if icode in [RRMOVQ,RMMOVQ,OPQ,PUSHQ]:
    srcA = rA
else if icode in [POPQ,RET]:
    srcA = RSP
else:
    srcA = RNONE
# srcB
if icode in [OPQ,RMMOVQ,MRMOVQ]:
    srcB = rB
else if icode in [PUSHQ,POPQ,CALL,RET]:
    srcB = RSP
else:
    srcB = RNONE
# dstE
if icode in [OPQ,RRMOVQ,IRMOVQ]:
    dstE = rB
else if icode in [PUSHQ,POPQ,CALL,RET]:
    dstE = RSP
else:
    dstE = RNONE
# dstM
if icode in [MRMOVQ,POPQ]:
    dstM = rA
else:
    dstM = RNONE

这里我们要额外注意一个问题当我们执行popq %rsp的时候同时有向%rsp写入valE和valM，因此我们要对dstE和dstM端口设置一个优先级，以确保最后%rsp的值是弹出的值，而不是更新后的%rsp值。因此我们将M端口的优先级设置的高于E端口。

执行阶段

执行阶段的硬件主要使用ALU，这个单元根据alufun信号的设置，对输入aluA aluB进行ADD SUB AND OR运算。这些数据和控制信号是由三个控制块产生的，valE就是ALU的输出。

这里我们要明确，aluB是被计算的数，而aluB是用于计算的数。我们根据icode来选择性的设置aluA和aluB的值以完成计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# aluA
if icode in [RRMOVQ,OPQ]:
    aluA = valA
else if icode in [IRMOVQ,RMMOVQ,MRMOVQ]:
    aluA = valC
else if icode in [CALL,PUSHQ]:
    aluA = -8
else if icode in [POPQ,RET]:
    aluA = 8
# aluB
if icode in [RMMOVQ,MRMOVQ,OPQ,CALL,RET,PUSHQ,POPQ]：
	aluB = valB
else if icode in [IRMOVQ,RRMOVQ]:
    aluB = 0

同时我们要设置ALUfun，大多数时候ALU是做加法工作的，在执行OPQ指令时，对应ifun:

1
2
3
4
5

# alufun
if icode == OPQ:
    alufun = ifun
else:
    alufun = ADD

执行阶段还要设置条件码寄存器。每次运行时要设置（零，符号，溢出），不过我们只希望在执行OPQ指令时才设置CC：

1
2
3
4

if icode == OPQ:
    setCC = 1
else:
    setCC = 0

标号为Cond的硬件单元则会根据ifun和CC来设置信号Cnd，来确定是否要进行条件分支，或条件数据传送。它产生信号Cnd，用于设置条件传送的dstE，同时沿用在条件分支的下一个逻辑。对此我们可以设置指令CMOVXX的传送条件，即优化dstE的设置：

1
2
3
4
5
6
7
8
9

# dstE
if icode == RRMOVQ && Cnd:
    dstE = rB
else if icode in [OPQ,IRMOVQ]:
    dstE = rB
else if icode in [PUSHQ,POPQ,CALL,RET]:
    dstE = RSP
else:
    dstE = RNONE

访存阶段

该阶段的任务就是读写程序数据。两个控制块产生内存地址和内存输入数据的值。两外两个块产生表明读写操作的控制信号。当执行读操作时，数据内存产生值valM

我们根据指令的访存阶段的分析，可以简单的得到Mem_addr和Mem_data的设置：

1
2
3
4
5
6
7
8
9
10

# mem_addr
if icode in [RMMOVQ,PUSHQ,CALL,MRMOVQ]:
    mem_addr = valE
else if icode in [POPQ,RET]:
    mem_addr = valA
# mem_data
if icode in [RMMOVQ,PUSHQ]:
    mem_data = valA
else if icode == CALL:
    mem_data = valP

然后根据指令类型，判断数据内存读写的使用：

1
2
3
4
5
6
7
8
9
10

# mem_read
if icode in [MRMOVQ,POPQ,RET]
	mem_read = 1
else:
    mem_read = 0
# mem_write
if icode in [RMMOVQ,PUSHQ,CALL]:
	mem_write = 1
else:
    mem_write = 0

然后时是设置状态码，分别为SADR SINS SHLT SAOK

1
2
3
4
5
6
7
8
9

# Stat
if imem_error || dmem_error:
    Stat = ADR
else if !instr_valid:
    Stat = INS
else if icode == HALT:
    Stat = HLT
else:
    Stat = AOK

更新PC阶段

SEQ的最后一个阶段会产生PC的新值，我们需要根据指令的类型和是否要选择分支来设置PC，PC可能是valC，valM，valP。

1
2
3
4
5
6
7
8
9

# new_pc
if icode == CALL:
	new_pc = valC
else if icode == JXX && Cnd:
    new_pc = valC
else if icode == RET:
    new_pc = valM
else:
    new_pc = valP

到此为止，我们的SEQ的各个阶段的硬件模拟就完成了。之后我们会进一步优化SEQ的实现。