Topological Sort

ver1 DFS

1
2
3
4
5
6
7
8

code:
for each unvisited node u in V:
	DFS(u)
    for each neighbour h of u:
    	if(!visited)
        	DFS(h)
    finish DFS(u) // push_back u to the list
reverse the list!

ver2 BFS (Khan)

1
2
3
4
5
6
7
8
9

code:
push vertices with no incoming edges to the queue
while(!q.empty):
	u = q.top 
    q.pop
    for each neighbor x of u
    	delete u->x
        if x has no incoming edges,then push x to the queu
//done

Bipartite

definition

1.说白了就是图的所有点可以分为两个set，每个set之间互相没有边，只有set与set之间的点有边。

2.应用于无向图。

Bipartite checker

ver1 DFS

每个点的邻居与它不同色（就是不同一个set）

每个点与它的邻居的邻居同色，它邻居的邻居与它在同一个set

1
2
3
4
5
6
7
8

for each unvisited vertex in u:
	dfs(u)
    for each neighbor v in u:
    	if(v is unvisited)
        	assign u as different color
        else if u and v has same color
        	break!
            it is not a bipartite

ver2 BFS

1
2
3
4
5
6
7
8
9

push vertexs with no incoming edged to queue
while(!queue.empty())
	u = queue.top
    q.pop
    for v in neighbor in u
    	if(v.color==u.color)
        	exit;//no bipartite
        else if unvisited 
        	assign different color to v

max flow

intro to mincut problem

intro to maxflow problem

Ford-Fulkerson Algorithm

mincut 和 maxflow problem 实际上是等价的，解决了其中一个，另外一个就自然解决了。

如上图，a为开始点。各边左数字为capacity，右边数字为flow

a->b满了，a->b有一个cut

a->c不满，即（flow<capacity）

c->e满了（flow==capacity）

c->d满了（flow==capacity）

设点a,c为集合P，其余所有点为集合P‘

则capacity of P->P’ 就等于maximum flow

1
2
3
4
5

Start with 0 flow
while there exists an augmenting path:
	find an augmenting path
    compute bottleneck capacity
    increase flow on that path by bottleneck 	 capacity

Augmenting Path:

find an undirected path from s to t such that:

can increase flow on forward edges(not full.)
can decrease flow on backward edge(not empty.)

termination

all paths from s to t are blocked by either a:

full forward edge

empty backward edge

relationship between flow and cuts

network of flow

so how to find mincut from maxflow f?

start from s,find the forward edge that is not full or backward edge that is not empty

Ford-fulkerson算法

Ford-fulkerson算法就是： 不断在残留网络中找增广路，直到没有为止。

Time complexity : O(C*E) ,C 是容量和

1

Time complexity of the above algorithm is O(max_flow * E). We run a loop while there is an augmenting path. In worst case, we may add 1 unit flow in every iteration. Therefore the time complexity becomes O(max_flow * E).

Dinic 算法

Dinic: 每次寻找最短的增广路until找不到，可证明最多能找V次。

Time complexity : O（V^2E）

1
2
3
4
5
6
7
8
9
10

1) Initialize residual graph G as given graph.
1) Do BFS of G to construct a level graph (or
   assign levels to vertices) and also check if 
   more flow is possible.
    a) If more flow is not possible, then return.
    b) Send multiple flows in G using level graph 
       until blocking flow is reached. Here using 
       level graph means, in every flow,
       levels of path nodes should be 0, 1, 2...
       (in order) from s to t.

A flow is Blocking Flow if no more flow can be sent using level graph, i.e., no more s-t path exists such that path vertices have current levels 0, 1, 2… in order.

Dinic code-Kattis maximum flow

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

 #include <stdio.h>
#include <stdbool.h>
#include <bits/stdc++.h>
#define M 50
#define N 50
using namespace std;

//https://www.geeksforgeeks.org/dinics-algorithm-maximum-flow/


struct Edge {

    int to;
    unsigned long rev;//store index of reverse edge in adjacency
    int flow, cap;//cap is capacity
};

class Dinic {
    using AdjacencyList=vector< vector<Edge> >;

    bool bfs() {
        queue<int> q;
        q.push(source);
        fill(begin(levels), end(levels), -1);
        levels[source] = 0;
        while (!q.empty()) {
            const auto now = q.front(); q.pop();
            for (const auto& e : adjList[now]) {
                if (levels[e.to] == -1 && e.flow < e.cap) {
                    q.push(e.to);
                    levels[e.to] = levels[now] + 1;
                }
            }
        }
        return levels[sink] != -1;
    }

    //a dfs based function to send flow after BFS
//has figured out that there is a possible flow
//and constructed levels.This function called multiple times for a
//a single call of BFS
//flow: current flow sent by parent function call


    int dfs(int v, int flow) {
        if (flow == 0) return 0;
        if (v == sink) return flow;
        for (int & i = currentEdge[v]; i < (int) adjList[v].size(); ++i) {
            Edge& edge = adjList[v][i];
            if (levels[v] + 1 == levels[edge.to]) {
                const auto minimalFlow = dfs(edge.to, min(flow, edge.cap - edge.flow));
                if (minimalFlow > 0) {
                    //add flow to current edge
                    edge.flow += minimalFlow;
                    //subtract flow from reverse edge
                    adjList[edge.to][edge.rev].flow -= minimalFlow;
                    return minimalFlow;
                }
            }
        }
        return 0;
    }

    vector<int> levels, currentEdge;

public:

    int source, sink;
    AdjacencyList adjList;

    void AddEdge(int a, int b, int cap) {
        //ADJList动态变化，节省空间
        if (max(a, b) >= (int) adjList.size()) {
            adjList.resize(max(a, b) + 1);
            levels.resize(max(a, b) + 1);
            currentEdge.resize(max(a, b) + 1);
        }
        const auto rev_a = adjList[b].size();
        const auto rev_b = adjList[a].size();
        adjList[a].push_back({b, rev_a, 0, cap});
        adjList[b].push_back({a, rev_b, 0, 0});
    }

    int MaxFlow(int s, int t) {
        source = s;
        sink = t;
        int flow = 0;
        //augment the flow while there is path
        //from source to sink
        for (;;) {
            int m = bfs();
            if (!m) break;
            fill(begin(currentEdge), end(currentEdge), 0);
            while (int pushed = dfs(source, INT_MAX)) {
                flow += pushed;
            }
        }
        return flow;
    }

};

int main(){

    int n,m,s,t;
    cin>>n>>m>>s>>t;
    Dinic d;
    d.sink =s;
    d.source = t;
    vector<vector<int>>flow(n,vector<int>(n,0));
    for(int i=0;i<m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        //flow[u][v] = c;
        d.AddEdge(u,v,c);
    }
    cout<<n<<" "<<d.MaxFlow(s,t)<<" ";
    //SIZE is the number of edges used in the solution
    //
    int size = 0;
    vector<tuple<int,int,int>>ans;
    for(int i=0;i<n;i++){
        for(auto &e:d.adjList[i]){
            if(e.flow>0)
            {
                size++;
                ans.push_back({i,e.to,e.flow});
            }
        }
    }
    cout<<size<<endl;
    for(auto &t:ans){
        int from = get<0>(t);
        int to = get<1>(t);
        int f = get<2>(t);
        cout<<from<<" "<<to<<" "<<f<<endl;
    }

}

获取进程ID

每个进程都有一个唯一的正数进程ID，getpid函数返回调用进程的PID，getppid函数返回它的父进程的PID（创建调用进程的进程）

创建和终止进程

1.运行

2.停止

3.终止

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

int main()
{

	pid_t pid;
    int x= 1;
    
    pid = Fork();
    if(pid==0){
		printf("child : x=%d\n",++x);    
    	exit(0);
    }

	printf("parent: x=%d\n",--x);
}

要点：

1.fork函数只调用一次，但是会返回两次，一次是在父进程中，另外一次是在子进程中。

2.父进程总会返回子进程的PID，在子进程当中，fork总会返回0

3.并发执行，内核能够一任意方式交替执行它们逻辑控制流中的指令
在x86上，先完成父进程，再完成子进程,这个顺序不同的系统会不同，画出进程图，所有拓扑排序序列都可以。

4.相同但是独立的地址空间，每个进程都有相同的用户栈，相同的本地变量值，堆等“环境”，但却是独立的，就是说一个进程改变内部的环境不会影响另外一个进程

5.共享文件共享文件

结果如下

所以上面程序的分析：

pid==0，即子进程

那如果是以下程序呢？

解析：

1
2
3

先调用父进程，x=1，所以输出--x=0;
然后调用子进程，子进程除了会执行if内的printf语句，同时还会执行if外的printf语句。

回收子进程

当一个进程由于某种原因中止的时候，内核不会立刻把它从系统中清除，而是保存在一个已经终止的状态中，等待被父进程回收。

所以一个终止了的但是还没有被回收的进程，成为僵死进程

如果父进程终止了，内核会安排init进程成为它孤儿进程的养父，init进程的PID位1，是系统启动的时候由内核创建的，不会终止，是所有进程的祖先。

1
2

pid_t waitpid(pid_t pid,int *statsup,int options){
}

pid参数用来判断等待集合的成员。

如果pid>0，那么等待集合就是一个单独的子进程，它的进程ID等于pid

如果pid=-1，那么等待集合是由父进程的所有子进程组成的

wait函数

wait函数是waitpid函数的简单版本

1

pid_t wait(int *statusp); // = waitpid(-1,&status,0);

让进程休眠

//返回要休眠的秒数

1

unsigned int sleep(unsigned int secs);

1
2
3
4

int pause (void)

让函数休眠，知道进程收到一个信号
//always return -1

加载并运行程序

execve函数在当前进程上下文当中加载并且运行一个新程序

1

int execve(const char *filename,const char *argv[],const char *envp[])

execve函数加载并且运行可执行目标文件，且带参数列表argv和环境变量envp，只有当出现错误例如找不到filename的时候，execve才会返回到调用程序。

execve函数调用一次，而且从不返回

当execve加载了filename后，启动代码设置栈，并将控制传递给新程序的主函数。

1

int main(int argc,char *argv,char **envp)

1.argc argv[]数组中非空指针的数量

2.argv argb[]数组中的第一个条目

3.envp 指向argv[]数组的第一个条目

1
2
3

char *getenv(const char *name) 函数

搜索字符串 name==value,找到就返回一个指向其的指针，否则返回NULL；

1
2
3

int setenv(const char *name,const char *newvalue,int overwrite)//当overwrite非0的时候，如果name不存在，那么setenv把“name=newvalue"添加到数组当中

unsetenv就是会删除它

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

//查看函数的命令行参数和环境变量

int main(int argc,char *argv[],char *envp[])
  {
      int i;
      printf("command-line arguments:\n");
      for(i=0;argv[i]!=NULL;i++){
  
          printf("    argv[%2d]: %s\n",i,argv[i]);
      }
      printf("\n");
      printf("environmental variables:\n");
      for(i=0;envp[i]!=NULL;i++){
  
          printf("    envp[%2d]: %s\n",i,envp[i]);
      }
      exit(0);
  
  }

用户栈的组织结构

动态链接器变量下的envp,argv,与argc是libc_start_main的栈帧

信号

def：一条通知进程系统发生了一个某种类型事件的小信息

传送一个信号到目的进程由两个不同步骤组成：

发送信号

进程组：

每个进程属于一个进程组

1

pid_t getpgrp(void); return id of id group

1

int setpgid(pid_t pid,pit_t pgid);

用/bin/kill发送信号

1
2
3

/bin/kill -9 15213

/bin/kill -9 -15213 负的PID会导致信号被发送到进程组PID中的每个进程

从键盘发射信号

作业（job）用来表示为一条命令行求值而创建的进程，在任何时候，至多只有一个前台作业和0个或多个后台作业。

1

ls | sort //会创建一个由两个进程组成的前台作业

用kill发射信号

1
2
3
4

int kill (pid_t pid,int sig);
成功则返回0，错误则返回-1

如果pid大于0，则kill函数发送信号号码sig给进程pid，如果pid为0，则kill发送信号sig给调用进程所在进程组的每个进程，如果pid小于0，kill发送信号sig给进程组pig绝对值中的每个进程

接收信号

1.内核位每个进程在pending位向量维护着待处理信号的集合，而在blocked位向量维护着被阻塞的信号集合。所以任何时刻一种类型的信号只会被接收一次，在处理它的时候，会先把该类型的信号block，进程可以忽略信号，也可以捕捉这个信号，执行信号处理程序。

2.当内核从一个异常处理程序返回的时候，准备吧控制传递给某个进程p的时候，会检查进程p违背阻塞的待处理信号集合。如果这个集合不为空，那么内核选择集合中的某个信号k（越小越好，因为linux里面编号越小，优先级越高），并且进入k的处理程序。

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

/* 改变blocked向量的值，若oldset!=null，会用来保存以前blocked向量的值 */ 

int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);

/* 初始化set为空集 */ int sigemptyset(sigset_t *set); /* 初始化set全为1，每个信号都填入blocked向量 */ 

int sigfillset(sigset *set); 

/* 添加、删除signum到set */ 
int sigaddset(sigset_t *set, int signum); int sigdelset(sigset_t *set, int signum);

/* set中对应signum是否置1 */ 

int sigismember(const sigset_t *set, int signum);
--------------------- 

原文：https://blog.csdn.net/WMLWONDER/article/details/53728630

singal函数

1

sighandler_t signal(int signum,sighandler_t handler)

如果handler不是SIG_IGN或者SIG_DFL，handler 就是用户定义的函数的地址，这个函数叫做信号处理程序。这个过程叫设置信号处理程序，调用过程叫做捕获信号，执行信号处理过程叫做处理信号

阻塞和解除阻塞信号

隐式阻塞：例如信号s对应程序S，当在处理程序S的时候，如果发送进程一个信号s，那么直到S返回，s会一直是待处理而不被接收。

显式阻塞：使用sigprocmask函数和其辅助函数，明确阻塞和解除阻塞选定的信号。

临时阻塞一个信号

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

sigset_t mask,prev_mask;
Sigemptyset(&mask);
Sigaddset(&mask,SIGINT);

//block sigint and save previous blocked set

Sigprocmask(SIG_BLOCK，&mask，&prev_mask);

	//Code region that will not be interrupt by SIGINT
    
Sigprocmask(SIG_SETMASK,&prev_mask,NULL);

非本地跳转

一些原则：

1.注意保存与恢复errno

2.当访问一个全局数据结构的时候，阻塞所有的信号

3.用volatile声明全局变量，告诉编译器不要缓存这个变量，那么每次引用g的时候，都要从内存中读取g的数值。

adjustment to the CPU

when the results computed by ALU shows that there is an error,
then add a signal path from ALU to PC UPDATE

now PC update have 3 choice to update its value:

1.PC+4

2.JUMP instruction PC+offset*4

3.when the error signal is valid PC -> 0 ,which means it turns to address 0 ,execute few instructions from address 0 to rectify the mistakes or show there is an error.

you can also record the PC value then error occurs, so next time you can jump back to the PC value and then continue the execution.

what is interruption and exception

the original way to handle exception and interruptoin

interrupt vector

how intel 8086 divide its address space?

中断向量用来存储address which process the interruption

IP 存放在指令指针寄存器
CS 存放在代码段寄存器

IP，CS寄存器参见https://blog.csdn.net/qq_35212671/article/details/52752808

总的来说，CS:IP 两个寄存器指示了 CPU 当前将要读取的指令的地址。

当要执行一个可执行文件的时候，shell程序会把CS：IP寄存器设置这个程序的初始地址,然后CPU从这个地址开始读取指令

逻辑地址生成物理地址

中断向量表要在系统启动的时候进行初始化

一个中断向量占4个字节，1共有1KB空间用来存放中断向量，因此一共有256个中断向量。

CPU发现中断的时候，如果是1号，转向1号中断向量。由于中断向量的位置是固定的，CPU只需要通过硬件电路来访问中断向量，不需要通过软件。而且CS是段基值，IP是偏移量，根据段偏移计算方法：

对应地址为43006H
因此转到存储器里面的40996H，执行处理1号中断的服务程序。

注意终端服务程序存放顺序不固定

exercise

中断类型码就是中断向量序号，由于第0个中断向量是存放在地址0的，因此中断向量码与其存放地址的关系就是 地址 = 向量码×4

10H 20H 对应IP寄存器 30H 40H 对应CS寄存器

因此地址为 4030:2010H

23 40 对应CS寄存器
78 90 对应IP寄存器

因此字节单元对应的内容分别为

23

40

78

90

(从上往下地址减少)

中断向量表的发展

1.回顾一下，实模式下，地址是有CS寄存器×4 + IP寄存器 来产生一个20位的地址来实现的

2.但是现在EIP的寻址能力和32位地址线寻址范围是对应的，因此保护模式下寻址方式和实模式有所不同。

IA-32的存储器寻址

1.保护模式下，段基址不在CS中，而在内存中

为什么会有8192个描述符？

因为CS寄存器寻址能力是16位，可以寻找2^16也就是64K个地址，也就是8192个描述符

而这时候由于不知道起始地址，因此需要一个GDTR寄存器，来存储描述符0所在的地址。这是一个系统寄存器，在系统启动的时候就写好。

#####总结流程：

1.GDTR 结合 CS 寄存器，用来访问存储器中的描述符

2.然后从描述符当中提取出4个保存着基地址的字节，把得到的基地址与EIP指针寄存器结合，得到所要访问的寄存器的地址

保护模式的中断操作

中断向量表

这时候由于地址不是从0开始的，因此与上图类似，CPU需要一个IDTR来记录描述符0所在的地址。

这时候CPU把 (中断类型号 * 8 + IDTR)，得到描述符的地址，然后从描述符中选取2个段选择符字节放到CS寄存器，字节0,1,6,7放到EIP寄存器，（理解为偏移量）。记住实模式下，段基址并不是在CS中，而是需要用CS到内存中寻找。

所以当从中断向量取回CS与EIP后，要利用CS和GDTR结合，来寻找段基址，再把段基址与EIP结合，这样最后才能得到中断服务程序的入口地址

与实模式下的不同:

实模式下中断向量4个字节，其中低位的两个放到IP寄存器，高位的两个放到CS寄存器

中断处理过程

根据上图： 发生中断的时候先压栈，保存好处理完中断后应该返回的地址的信息。

Flags保存好标志，以免处理的时候会改变某些标志位。

清楚IF-TF 起到关中断的作用？？？

然后再从存储器找到中断向量，取到CS、IP之后就找到了终端服务程序的入口地址。

总结：

集中内部中断的类型：

注意上述两种中断类型的时机是不同的哦。

中断类型0 是在检测出异常的时候立即发生，而内部中断需要自己主动执行INTO指令才可以检测出来

为什么INT n是两字节指令？ 因为 INT 指令操作码 首先占一个字节 ，然后n范围是0-255 需要8位来表示，所以用2个字节。

那为啥INT 3用1个字节呢？

因为x86地址最短的就是一个字节。如果INT 3 是两个字节或以上，可能会覆盖掉下面的指令的一些字节。

例如：

OFFSET instruction 1, one byte

OFFSET+1 instruction 2, one byte

如果在inst1设置断点，则而且inst1内容是跳到inst2，则替换的时候INT 3会把inst2某些字节覆盖掉。那么就不能实现跳到inst2的指令了。

OFFSET INT3……………….

OFFSET+1 ………………….

详情参考 http://www.cs.columbia.edu/~junfeng/09sp-w4118/lectures/int3/int3.txt

INT 3对应的中断服务程序可以查看 AL寄存器的值

Part B

引用
https://blog.csdn.net/xbb224007/article/details/81103995?utm_source=blogxgwz0

2-6就是常说的“抖动”

就是A，B数组下标相同的元素会映射到同一个cache块当中。

这里不命中本质上是因为访问同一个block的两个元素的时候，由于中间访问了其他块，导致已经加载的块被驱逐，进而导致第二次访问时候不命中。

解决办法： 同时把一个block若干个元素取出来，即省去了中间访问其他块导致驱逐的过程。利用blocking思想

CMU 文章
http://csapp.cs.cmu.edu/2e/waside/waside-blocking.pdf

1、A数组访问A[0][0]，冷不命中，将块11装入cache。

 2、B数组访问B[0][0]，虽然B[0][0]所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组B对应的块11装入cache。

 3、A数组访问A[0][1]，虽然A[0][1] 所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组A对应的块11装入cache。

 4、B数组访问B[1][0]，虽然B[1][0]所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组B对应的块11装入cache。

 5、A数组访问A[0][2]，虽然A[0][2]所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组A对应的块11装入cache。

 6、B数组访问B[2][0]，B[2][0] 所映射的块12不在cache中，冷不命中，将数组B对应的块12装入cache。

 7、A数组访问A[0][3]，A[0][3]所映射的块11在cache中，且标记位相同，故命中。

 8、B数组访问B[3][0]，B[3][0]所映射的块12在cache中，且标记位相同，故命中。

 9、A数组访问A[1][0]，A[1][0]所映射的块11在cache中，且标记位相同，故命中。

 10、B数组访问B[0][1]，虽然B[0][1] 所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组B对应的块11装入cache。

 11、A数组访问A[1][1]，虽然A[1][1]所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组A对应的块11装入cache。

 12、B数组访问B[1][1]，虽然B[1][1]所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组B对应的块11装入cache。

 13、A数组访问A[1][2]，虽然A[1][2]所映射的块11在cache中，但是标记位不同，造成冲突不命中，重新将数组A对应的块11装入cache。

 14、B数组访问B[2][1]，B[2][1] 所映射的块12在cache中，且标记位相同，故命中。

 15、A数组访问A[1][3]，A[1][3]所映射的块11在cache中，且标记位相同，故命中。

本实验的Cache

b = 5,s = 5，E=1

B =2^b = 2^5 = 32

S =2^s =2^5 =32

所以就是有32个块，每个块能存 32 bytes，就是8个int

先分析 32X32

一行32个元素，所以一行4个block，一共32个block，所以cache能应付8行。

所以每8行就会遇到冲突。就是两个int之间相差8行的整数倍，那么读取这两个元素所在的block就会发生替换

所以使用 8 * 8 blocking ，这样可以避免冲突

注意处理对角线的情况

因为矩阵转置之后，A【i,j】 = B【j,i】是相等的。

所以会发生冲突，可以采取的方法是，遇到对角线上的元素先不放到B，等block的其他七个元素写完之后，再把这个元素写到目的地。避免了由于中间加载B块，导致A块被驱逐所引起的命中冲突。

代码：

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

if(M==32)
{   //separate the the 32X32 block into 8X8 , decrease the number of misses
    for(row_Block = 0;row_Block < N ;row_Block+=8){
        for(col_Block =0 ;col_Block < M; col_Block+=8){
            for(i=row_Block ; i<row_Block+8;i++){
                for(j=col_Block;j<col_Block+8;j++){
                    if(i!=j){
                        B[j][i] = A[i][j];
                    }else{
                        tmp = A[i][j];                  //i==j means is the diagonal. if we set B right now ,the  misses and evictions will increase . because the cache set of B is same to A.
                        index = i;
                    }
                }
                if(col_Block == row_Block){             //just set B on the diagonal. other than shouldn't set the B
                    B[index][index] = tmp;
                }
            }
        }
    }
}

分析 61 x 67 情况

尝试 88,1616,17*17等各种情况即可。

最难的就是

64 X 64 情况

一行用掉8个block，所以每4行就会发生冲突。

1.先要想清楚，转置的时候，对A数组是按行访问的，而对与B数组是按列访问的。

我们先来分析一下，如果在64 x 64情况下 ，采用8分块，那列访问B的时候，前四行和后四行映射的块是相同的。

所以会发生这种情况：

1.访问前4行第一列之后，再访问后4行的第一列，会发生冲突，使得原来的块被驱逐。

2.再回去访问前四行的第二列，由于原来的块被驱逐，又会导致冲突不命中，

3.访问后4行第二列又产生冲突不命中。

如果采用 4 X 4 分块

对于B 数组而言，访问顺序为
前四行前四列-》后四行前四列-》前四行后四列-》后四行后四列

这里有点不懂

参考文章提到，后四行前四列所在的块会覆盖前四行前四列的块，后面两次访问又会有一次不命中。为什么是2次？不是3次？

因此采取的策略：

按照这个顺序，对于B数组每一个块的元素，只会有一次不命中

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

else if(M==64){
     for (i = 0; i < N; i+=8) {
         for (j = 0; j < M; j+=8) {
             for(x=i;x<i+4;x++){

                 x1 = A[x][j];
                 x2 = A[x][j+1];
                 x3 = A[x][j+2];
                 x4 = A[x][j+3];
                 x5 = A[x][j+4];
                 x6 = A[x][j+5];
                 x7 = A[x][j+6];
                 x8 = A[x][j+7];
                 //leftup as usual
                 B[j][x] = x1;
                 B[j+1][x] = x2;
                 B[j+2][x] = x3;
                 B[j+3][x] = x4;
                 B[j][x+4] = x5;
                 B[j+1][x+4] = x6;
                 B[j+2][x+4] = x7;
                 B[j+3][x+4] = x8;
             }
             for(y=j;y<j+4;y++){
                 
                 x1 = A[i+4][y];
                 x2 = A[i+5][y];
                 x3 = A[i+6][y];
                 x4 = A[i+7][y];
                 x5 = B[y][i+4];
                 x6 = B[y][i+5];
                 x7 = B[y][i+6];
                 x8 = B[y][i+7];

                 B[y][i+4] = x1;
                 B[y][i+5] = x2;
                 B[y][i+6] = x3;
                 B[y][i+7] = x4;
                 B[y+4][i] = x5; 
                 B[y+4][i+1] = x6;
                 B[y+4][i+2] = x7;
                 B[y+4][i+3] = x8;
             }

             for(x = i+4;x<i+8;x++){
                 x1 = A[x][j+4];
                 x2 = A[x][j+5];
                 x3 = A[x][j+6];
                 x4 = A[x][j+7];

                 B[j+4][x] = x1;
                 B[j+5][x] = x2;
                 B[j+6][x] = x3;
                 B[j+7][x] = x4;

             }
         }
     }
 }

上述代码就是：

1. B数组访问前4行

2. B数组访问前四行后四列，和后四行前四列

3. B数组最后把后四行后四列转置

我感觉就是先把一行的数据处理完再去处理下一行，尽量不要交替着4行访问数据，这样会导致块被驱逐，加载，增加了总的冲突次数。

存储层次结构概况

存储器的特性

1.非易失性，即断电后不会丢失数据

CPU和主存都是易失性，而BIOS和硬盘是非易失的

通电之后CPU通过BIOS芯片开始执行程序，把硬盘配置好后，再从硬盘读取数据搬运到主存，然后CPU才能够执行程序。

2.可读可写

3.随机访问

访问数据与其位置无关

主存与BIOS(basic input output system)能够实现随即访问数据。

但是硬盘则不是。

4.访问时间

主存速度高于硬盘访问时间

DRAM读取数据时间是CPU读取时间的一百倍，因此执行一条指令的时候非常的慢！

因此考虑在CPU 和DRAM之间添加一个SRAM，使得CPU所需要的程序和数据大部分时间存放在Cache中，大大缩短执行指令时候所需要的时间周期。

DRAM

右下角就是内存条，通常也叫内存模组，是由若干个DRAM芯片组成的，核心就是左图的内存阵列，从外界输入行列信号，就可以读取一个基本存储单元，如红圈每个存储单元有若干个bit，通常是4个或者8个，每一个放大来看如右上角电路图所示。

基本存储单元

通过存储的电容来表示存储的bit信息，对SDRAM的读写，主要体现在电容的冲放电，而这个是很难再做提高的。

SRAM采取的是晶体管开关存储，远比电容充电放电要快，所以SRAM比DRAM要快，现代CPU的高速缓存通常用SRAM实现

内存工作原理

第一步，申请系统总线，获得总线控制权后，会把地址送到内存控制器中。

然后内存控制器会把地址分解为行地址和列地址

第二步 行访问

内存控制器向SDRAM发起访存操作

这一行当中所有存储单元的信号通过放大器之后会放在一个缓冲区当中。这就是激活/行访问

第三步 列访问

第四步 送回CPU

内存控制器把采样到的数据送回给CPU

CPU之后又发送地址信号，如果不是同一行，则就要把激活的行关闭。

这个过程叫做预充电

SDRAM的关键性能参数：

1.tRCD row to column delay 从行选到列选的延迟时间

2.CL CAS Latency 从列选到数据输出的延迟周期数

3.tRP 行预充电时间

数据个数就等同于内存条上DRAM芯片个数

所以整个过程的周期并不等于7.5ns！

DDR SDRAM 比 SDR SDRAM 要快，原因是前者一次能比后者取多两倍的数据

DDR是数据传输的方式，不等同于内存

DDR 与 SDR 对比

DDR由于一次读取两个数据，所以tRCD和CL变慢了，但是每个周期能同时取两个数据。
这里的带宽就是由每个周期取得的数据计算出来的。

衡量CPU有两个指标

访存带宽

单位时间内存储器所存取的信息量。

访存延迟

读出第一个数据所需要的时间。

Cache工作原理

空间局部性：

空间局部性是一旦一个指令一个存储单元被访问，那么它附近的单元也将很快被访问

时间局部性：

时间局部性是一旦一个指令被执行了，则在不久的将来，它可能再被执行。

操作过程

怎么把虚拟地址转化为实际地址是个问题

Cache读操作

1.第一条指令，由于一开始Cache是空的，所以没有命中。因此Cache访问主存。

之所以分配给表项1，是由地址倒数第二个数字决定的。（不看H）

然后前面的所有项(20)放到标签处。

2.第二种情况，没有命中，因为表被占用了。

4011H，先检查有效位1，发现原来标签是20H，因此把地址替换掉。

Cache写操作

平均访存时间

Cache映射策略，直接映射会遇到这么一个问题：

就是存储器会每隔八个地址把数据映射到Cache中，如果程序交替访问这两个数据，那么每次访问都会访问主存，把地址写入到Cache中，这样性能比没有Cache的时候还要差。

也可以通过二路组，四路组相联策略，但是代价是每次取数据的时候，要取多个标签比较，如直接映射只需要取一个标签出来，如图中的0，而二路组则要2个。而且这样会使得硬件电路变得复杂化，增加了命中时间，得不偿失。

常见Cache替换算法

LRU的实现：

1.队列

2.用LRUnumber，例如初始化每块的LRUnumber为0，当要访问这块Cache的时候重新设置为0，然后其他块++1，然后LRUnumber最大的那个block就是最近最少使用的块。

计算机领域单位使用情况

Cache 映射

直接映射

Cache 大小：

假设每个槽，就是cache的每个block能装512个(2^9)byte，说明b = 9

然后一共有16个sets，说明 s = 4，

因此cache地址一共是（s+b = 13位）

主存的第0块，第16块，第32块。。都能放在cache的0槽当中，但是怎么知道
是哪个块群的呢?因此用标记号来说明，那么标记号该有几位？就是块群的个数2^7=128

所以标记号就是7位，标记号用来指出对应行来自于哪个块群。

主存大小：
2048 块 512B/块 = 2^11 2^ 9 = 2^20

所以主存地址一共20位，包含了9位的块内地址，4位cache索引，剩下7位主存标记。
主存一共2048（2^11）块，所以主存标记和cache索引用来标记主存的具体块号。

1
2
3
4
5
6
7
8
9

例如：给定地址 0220CH

转化为二进制 0000 0010 0001 0000 1100

前7位 0000 001  决定来自于块群 1

中间4位 0001 决定来自块群的具体哪个块  第一块

后面9位，块内地址 决定了块内的哪个单元 第12个单元

所以大概过程

拿来一个主存地址，然后划分为三段，根据中间索引号来寻找cache对应槽，然后看
valid位和标记位，如果valid=0，说明里面是空的，冷不命中，要从主存把地址送过来。如果valid=1，而且主存标记刚好是标记位，就根据块内地址在槽内寻找对应单元。

给定32位主存地址，划分为三部分。

首先由于块大小为16（2^4）B，因此b = 4,偏移位 4位

索引位呢？ 中间的索引位决定于cache有多少行

因此行数=64KB/16B = 4K = 2^12 行

因此中间索引位一共有12位

剩下16位就是tag位，标记位

给定内存地址，先由中间12行找到cache对应的行，看tag位与valid位是否满足条件，（valid=1说明这一行有数据）满足条件就hit，hit了就根据偏移位寻找对应的数据。

块大小位16B，即128bit，使用多路选择器MUX来选择取哪个32位的data。

11 最左边 10 中左 01 中右 00最右边

如果取的是int型（word），由于word alignment，即内存地址最后的两位其实是不需要理会的。那么只看第三第四位，就是所谓的block offset。决定所取int放在哪个block.

而如果要取的是char型，要在取了word之后再通过一个MUX，根据主存地址最后两位（Byte Offset）来得到要取哪个byte。

cache 容量

上图中容量为 行数 X（每一行的bit数）

（16+1）4K + 64K 8 = 72.5KB

数据 64KB/72.5KB =88.3%

有一个64行，块容量为16bytes的cache

十进制地址 1200应该映射到哪一行？

方法一： 【1200/16】mod 64 = 11

方法二： 1200转换为二进制 0100 1011 0000

索引号 = 6 ，即看中间存的是哪一行，001011 就是 11

实现一个直接映射，16K行数据，块大小为1个字（4B），32位主存地址的cache需要多少容量？

16K = 2^14 行数据，即中间索引有14位

byte =4B ，b = 2

所以tag = 32-2-14 =16

因此16K（1+16）+16K4B =16K*(1+16+32) =784Kbits
(1+16)中，1是valid位

特点

全相联映射方式

给定地址，根据标记主存块号找到数据所在主存的哪一块，00000001111就是第15块，但是不知道在Cache的哪个槽中，所以只能一个一个槽比较。所以叫按内容访问。

为什么没有cache索引字段？

因为其可以任意映射到某一个行当中.

优点就是没有冲突，时间相对加快，但是tag长了，而且每一行都有一个比较器，比较时间长了，相当于命中时间会加长，而且比较成本也增加了，cache容量也变大了！

前8位标记表示cache属于哪个组群

中间3位表示属于哪个组

后面9位表示偏移量，表示要找到那个数据

Eg: 地址 0000 0001 001 00000 1100

前8位表示在第一组群 中间三位（cache索引）表示cache的第一个set ，就是第一个族群的第001块，就是第九块，把这一块映射到cache的第一组当中。

两个比较器并向同时比较，最多有一个cache的tag与主存地址的tag相同，OR选择器的结果就是hit的结果。

通过多路选择器把所要找的cache data的block找出来！

顺便讲一下什么叫按字节编址，按字编址。

字 word = 4byte

字节 byte = 8bit

位 bit

上面的图怎么看？

1. 每一block64个字。访问第0block，冷不命中，放到第0组。那哪一行呢？都可以，一般按照顺序来，因此放在第0组第0行。然后第0组所有元素就都在第0组第0行中取。
2. 然后访问第1组，冷不命中，放在第1组第0行。第0，16，32，48block都放在第0组，分别放在第0，1，2，3行。
3. 当取到第64block的时候，miss，根据LRU把第0组行第0行替换掉。一直到第67block结束第一次循环。
4. 然后来到第二次循环，想要找第0组，但是已经被刚才第64组替换掉了，而且第0block只能放在第0组，因此根据LRU，替换掉第0组第一行，一直到第四个block的时候，这时候第4block放在第4组的的第0行，没有miss。
5. 由于第16，17，18，19个block已经被替换，当访问第16,17,18,19个block的时候，根据LRU，分别吧0，1，2，3组的第二行的32，33，34，35block替换。同理，当访问32，33，34，35block的时候，又把第三行的48495051替换。同理，访问48，49，50，51的时候，又miss，又把第一行的对应64，65，66，67替换掉。
6. 所以第二次-第九次循环，每次都有5*4=20次miss

命中率： (43520-68-9*20)/43520 = 99.43%

Cache读和写的一致性问题

同时写cache和主存，但是主存要慢得多，这样写完了cache之后要等待主存。
所以可以增加一个buffer 写缓冲。
就是CPU可以把数据写到cache中。写完了之后不等写道主存，继续写cache，写到主存的工作就交给write buffer，由memory controller传回到DRAM

写穿透就是同时写cache和主存，写分配就是同时更新主存和cache
Write Trough 算法
如果能够找到i，使得TAG（i） == X,
如果是读操作，就直接返回块内地址DATA[i]；
写操作就除了要写块内地址，还要写主存

如果miss掉
读操作就是读主存的数据，然后打标签，送到cache
写操作就是先写主存，然后打标签，最后在块内new一个新的数据

Cache越大越好，命中率越高，但是越大的话成本越高
Block 不能太大，也不能太小

Cache 数目

L1，分立cache，为了实现流水线，同时取数据和指令，提高并行性。

第二个问题：
因为他有L1，L2两个cache，即使不命中也没有关系

第三个问题：最后Level的cache与指令流无关，不需要考虑并行。因此优先考虑空间的利用率，同时命中率比命中时间更重要。

L1比L2容量小，（越大命中率越高）比L2快，命中时间短，如果L1不命中，只好寄托在L2身上，因此L2的命中率就显得特别重要。

Cache 实现举例

用2个状态位：

S: SHARE
E：EXCLUSIVE
M: MODIFIED （是否dirty bit）
VALID 是否有效

LRU用1位：

例题

1. 不考虑一致性：dirty bit ；替换控制即LRU位

256MB 表示主存地址 28位

64B – b = 6

Cache 8行 -中间索引位 3

Tag位 19位 别忘了要考虑valid位

（1+19）8 + 648*8 （每行一个block）(64B是64byte，1byte 8 bits)

2. 64B-16个元素 一行16个元素

A[0][31] 地址 320+4*31 = 444 [444/64] = 6

因此主存块号为6，6mod8 = 6因此在第六行。

或者444 为0000110111100B 中间三位是索引位，就是第六行

而A[1][1] = (320+256*4+8 )/64 mod 8=5 同理也可以把地址转化为二进制来计算。

3.A 每隔16元素一次冷不命中，命中率（15/16）

B 每次相隔256个元素，256/16 = 16 块，16mod 8=0，每次访问后面数组元素的时候，总会把上一次装入到cache中的主存块覆盖掉。

所以每次访问的时候都会发生冲突，替换，因此没有一次命中。

General Useful Optimizations

Code Motion

reduce the frequency where computation performed

try to use shift,add to replace multiply

Reduction on strength

leaq (%rsi,%rcx),%rcx means %rcx = %rcx+%rsi

%rcx now is n

%rsi now is i*n+j

Share common Subexpressions

####

possibly the memory of A and B overlap and the change of B might affect A

Memory aliasing, closely related (arguably synonymous) to pointer aliasing, means that more than one variable name points to the same underlying stored value.

Benchmark Computation

Cycles Per Element(CPE)

Length = n

CPE =cycles per OP

T = CPE*n+Overhead?? what is overhead?

You don’t need to use get_vec in each loop,so avoid bound checking

流水线的冒险

阻止下一条指令在下一个时钟周期开始执行的情况

1.结构冒险

所需要的硬件部件正在为之前的指令工作

2.数据冒险

需要等待之前的指令来完成数据的读写

3.控制冒险

需要根据之前指令的结果决定下一步的行为

结构冒险

执行指令的硬件发生争抢

解决方案一： 冒泡停顿

但如果连续出现冒泡停顿，则会影响指令执行的效率

解决方案二： 把数据和指令放在不同的存储器

但值得注意的是，冯诺伊曼结构要求内存（主存储器）同时存放
数据和指令，而只是在CPU的高速缓存（cache）当中，数据和指令可以分开存放

这个在设计CPU就已经处理好了，但是如果要设计一个新的处理器，这是一个要考虑的问题

数据冒险

解决方法1：

解决方法2：

冲突产生原因是add 指令 需要 read 上一条指令write的结果（$t0）

但其实，$t0的值已经在ALU阶段就已经计算好，而add指令中，其实不是非得在
R阶段读$t0，只要在ALU阶段读取到数值就行。

那么就可以在sub指令中，把ALU计算得到的结果$t0送到流水线寄存器当中，
然后再送到add指令的ALU中。

从硬件角度来看，我们要这样修改：

sub先执行，所以在前面，add后执行，所以在后面

add指令需要用到前一条指令的结果，因此设置了绿色的旁路，
以是否有数据冒险情况作为激活信号。

第二种情况

对应下图

第三条指令需要用到第一条指令得到的结果，第一条的$t0在DMEM与write back阶段之间，所以呢，就是对应上上图，在访存阶段末期，通过旁路把数据传回给ALU

如果 instruction 3也需要用到$t0，因为R阶段之前，第一条指令刚好完成了write back，因此可以正常运行

load-use冒险，不能用数据前递来解决

如下图，因为or需要用到上一条指令的$t1,但是or至少要在ALU阶段读取$t1的数值，然而lw只能在完成了访存阶段后才能把结果写回到$t1,因此只能通过冒泡来延后or指令的执行时间了。

控制冒险

要到ALU阶段才能决定是否要取分支

转移指令对流水线的影响

beq指令只有在进行完执行（ALU）阶段之后才能确定是否发生跳转，加入跳转条件成立，则说明lw sw是不应该取的。这时跳回sub指令，导致性能被浪费。

转移指令的分类

优化

j指令在取指的时候就能判断是否为j指令，然后取出后26位，加上末两位的00，
然后在PC - update 阶段就能取PC+4的前四位，这些操作都能在一个时钟周期内完成。

译码阶段进行R【rs】，R【rt】的读取，在执行阶段进行两数的比较

但实际上进行减法不需要ALU那么复杂的部件，可以在译码阶段进行一点小改动

总结

为了避免停顿，可以把转移指令的前一条与转移指令无关的指令（xor）移到转移指令的下一条。

Arch Lab

Part C

利用循环展开技术与加载使用冒险

加载使用冒险：

因此可以在mrmovl后添加另外一条mrmovl指令，来抵消流水线停顿，同时也使得下一次操作提前取值。

循环展开大意就是减少循环次数，在每次循环的时候同时进行多次操作。同时也可以配合并行，并行就是例如把每次累加操作的的结果分为两部分，如奇数项累加成S1，偶数项累加成S2，最后结果就是S1+S2。

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
33

#You can modify this portion
    # Loop header
    xorq %rax,%rax      # count = 0;
    iaddq $-2,%rdx
    andq %rdx,%rdx      # len <= 0?
    jl newLoop      # if so, goto Done:

Loop:   mrmovq (%rdi), %r10 # read val from src...
    mrmovq 8(%rdi),%r11
    rmmovq %r10, (%rsi) # ...and store it to dst
    andq %r10, %r10     # val <= 0?
    jle Npos        # if so, goto Npos:
    iaddq $1, %rax      # count++
Npos:
    rmmovq %r11,8(%rsi)
    andq %r11,%r11
    jle judge
    iaddq $1,%rax

judge:
    iaddq $16,%rdi
    iaddq $16,%rsi
    iaddq $-2,%rdx
    jge Loop

newLoop:
    iaddq $2,%rdx
    je Done
    mrmovq (%rdi),%r10
    rmmovq %r10,(%rsi)
    andq %r10,%r10
    jle Done
    iaddq $1,%rax

Y86 流水线的实现

PC的计算

在非流水线结构中，计算PC是在时间周期结束的时候进行的。

而在流水线实现中，计算PC作为指令执行的第一步。

Fetch 阶段

三种情况：

1.预测错误，从流水线寄存器M（M_valA）读出该指令valP的数值，即下一条指令的地址。

2.RET 指令 W_valM 从流水线寄存器读出返回地址（访存）。

3.其他情况会使用存放在流水线寄存器F中的PC的预测值。

HCL代码如下：

其中 f_predPC

exercises:

写出 f_stat的HCL代码，提供取出指令的临时状态

word f_stat =

f_icode == IHALT : SHLT

mem_error : SADR

!instr_valid : SINS

1: SAOK

译码和写回阶段

dsrc_A

1
2
3
4
5
6
7

word dsrc_A =

DICODE in {IRRMOVQ,IRMMOVQ,IPUSHQ,IOPQ} : D_rA

DICODE in {IPOPQ,IRETURN} : RRSP

1: RNONE

PUSH

RRMOVQ，RMMOVQ source A的值来自于寄存器A

而push 实际上就是

subl $4,%esp

movl %ebp,(%esp)

call实际上是 push+jump,先把返回地址（此时存放在EIP中）push进%ebp，
然后再jump到要执行指令的地址

POP

而POP指令实际上是

movl (%esp),%eip //eip寄存器是保存CPU所要读取指令地址的寄存器

addl $4,%esp

return

return 实际上是 把栈顶地址弹出到EIP，然后按照EIP指示的指令地址继续执行程序

需要用到栈指针来作为source A

dsrc_B

1
2
3
4
5
6

word d_srcB = 

DICODE IN {IOPQ，IMRMOVQ，IRMOVQ} ：d_srcB
DICODE IN {IPUSHQ,IPOPQ,IRET,ICALL} ：RRSP
1:RNONE

dstE

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

word d_dstE = 

// 目的寄存器是rB而且存储的是由数值运算得到的结果

DICODE IN {IOPQ,IIRMOVQ,IRRMOVQ} : D_rB:


//因为pushq,popq都需要涉及到

push: subl $4,%rsp
pop : addl $4,%rsp


DICODE IN {IPUSHQ,IPOPQ,IRET,ICALL}： RRSP

1： RNONE

dstM

1
2
3
4

DICODE IN {IMRMOVQ,IPOPQ}: R_rA

1: RNONE

d_valA

这五个转发源存在优先级，通常流水线的实现总是给处于最早的流水线阶段中的转发源以较高的优先级。

只有pop指令关心访存或者写回阶段的两个源之间的优先级

pop 指令看作是

movl (%rsp) , %rsp

addl $4,%rsp

因为默认 m_valM 访存的优先级 大于 M_valE 计算的优先级
因此加入下一条指令是

movl %rsp, %rax

则会把%rsp+4 之前的值传到%rax，满足x86的pop操作规定

aluA

1
2
3
4
5
6
7
8

word aluA = [
   E_icode in {IRRMOVQ,IOPQ} : E_valA
   E_icode in {IIRMOVQ,IRMMOVQ,IMRMOVQ} : E_valC
   E_icode in {ICALLQ, IPUSHQ} : -8 //如果是iaddl 就是-4
   E_icode in {IPOPQ,IRETQ} : 8
   
   
]

aluB

CPU的基本结构与功能

CPI （Cycles Per Instruction）用于衡量电脑的性能
，指每条指令的时钟数

1

CPI=TC/IC

表示某个程序的所有指令的条数；TC表示执行某个程序所花费的时钟周期)

加深理解：
M【R【ebp】+8】指的是命令行参数首个地址，即char *str的地址，M【地址】等于在内存中取值，相当于这个就是strcpy的第二个实际参数str

而R【ebp】-16 意思就是buffer[0]，即buffer的首地址

红线下面都是在CPU了里面进行操作

红线上面都是通过总线在外面进行操作

笔记：

取值令和PC+“1” 是并行的，（同时操作），“1”指一条指令的长度

在MIPS中，每个指令都是定长的，32位，占4位，因此实际上是PC+4

而在X86中，每个指令都不是定长的，是边长的，一定要在指令译码之后才能确定指令有多长

异常和指令区别：

异常指和处理中的这条指令有关的的问题

中断指和处理中的指令无关的问题

MDR：内存数据寄存器

MAR: 主存地址寄存器

GPR 8个通用寄存器 属于可见寄存器

EFLAGs 标志寄存器 属于半可见寄存器

EIP 指令指针 属于半可见寄存器

绿色的地址实际上是虚拟空间的地址。这里假定

取值令

取地址放到EIP中，再放到主存地址寄存器当中。55 89 e5 放在主存。

控制器会发出读命令（红线），存储器会根据读信号根据传入的地址寻找里面的数值

过一段时间后（取数时间） 数据就会放在数据线上。

指令译码

根据功能产生控制信号

R[esp]<-R[esp]-4 ESP处的地址-4 变成 bffefffc

M[R[esp]]<-R[ebp]

esp内容放到MAR

写信号，把要写的地址bffeffc 和写的内容（MDR中的bfff0020）传输到存储器中

而eax是0号寄存器，edx是2号寄存器

经过这条指令之后

结果变成这样

小结

练习答案

什么是指令寄存器？什么是程序计数器？

指令寄存器（IR，Instruction Register），是临时放置从内存里面取得的程序指令的寄存器，用于存放当前从主存储器读出的正在执行的一条指令。

什么是程序计数器PC？

程序计数器是用于存放下一条指令所在单元的地址的地方。

当执行一条指令时，首先需要根据PC中存放的指令地址，将指令由内存取到指令寄存器中，此过程称为“取指令”。与此同时，PC中的地址或自动加1或由转移指针给出下一条指令的地址。此后经过分析指令，执行指令。完成第一条指令的执行，而后根据PC取出第二条指令的地址，如此循环，执行每一条指令。

访问存储操作与基本术语

存储器的分类

按工作性质/存储方式分类

1. Random Access Memory(RAM)

随机存取存储器

每个单元读写时间一样，与各单元所在位置无关，如内存

2.Sequential Access Memo在ry（SAM）

顺序采取存储器

数据按照顺序从存储载体的始端读出或者写入，因此存取时间长短与所在信息的位置有关。如磁带

其他分类方式

按功能/容量/速度/所在位置分类

寄存器：

封装在CPU中，用于存放当前执行的指令以及使用的数据

用触发器实现，速度快，x86 8个,MIPS 32个

高速存储（cache）：

位于CPU内部或者附近，用来存放当前要执行的局部程序段和数据

用SRAM实现，速度可以与CPU匹配，容量小

内存与外存关系：

存储器受CPU总线控制，总线就是链接CPU和存储器的数据线，地址线和控制线

由于地址线是36位，因此存储单元地址有2^36种可能性，即可以寻找地址的范围为0-2^32-1 即64GB

Tmc>TA

神经网络是什么

左下角，第一层就是计算a[1]，然后加上更新后的W【2】，b【2】，在第二层计算新的结果
z【2】

注意一般不把输入层算在神经网络层内

注意hidden layer 其实就是一个4x1的列矩阵

神经网络表示

符号右上角表示层数，右下角表示该层第几个结点

实际上可以把神经网络计算过错化为向量矩阵运算

Z （4X1） = W (4X3) * x(3,1) +b(4,1)

激活函数

tanh

用tanh效果会比sigmodi好，因为均值为0，说明能起到数据中心化效果

线性整流函数（ReLU）

使用ReLU 会使得神经网络学习的速度加快，因为在tanh与sigmoid当中，当斜率降低的时候，学习的速度也会相应的下降。

而ReLu则会减少则种情况

一般而言，不用sigmoid

激活函数的导数

在反向传播的时候，需要计算激活函数的导数

神经网络的梯度下降

重点关注dZ【1】 dW的计算原理

共享库与动态链接概述

使用静态库 .a文件有一些缺点

1.静态库函数被包含在每个进程的代码段中，对于并发运行上百个进程的系统，会造成极大的主存资源浪费

2.静态库函数会被和并在可执行目标中，磁盘上存放着数千个可执行文件，会造成磁盘空间的极大浪费

解决方案：

Shared Libraries(共享库)

Linux 称为 动态共享对象 (Dynamic Shared Objects,.so文件)

Windows 中的.dll 文件

原理就是： 包含目标模块的文件，每个模块包含有代码和数据，从程序中分离出来，磁盘和内存中只有一个备份，可以在装入或者运行的时候被动态加载与链接。

举个例子，printf（）的代码不会包含在每个调用其的文件当中，所有进程共享调用这一份代码。

共享库优点：

第一次加载的时候进行：（load-time linking）

在linux当中通常由动态链接器自动处理

libc.so 通常按这种方式被动态链接

在开始运行后进行：

在linux中，调用dlopen()等接口实现

生成的代码文件是放在内存当中

位置无关代码（PIC）

要跳转的目标地址 = 当前PC（当前指令下一条指令地址）+ 立即数

不需要重定位

第三种情况

call 指令的功能是：
1.把下一条指令地址压栈

2.jump到那条指令

popl %ebx 的功能就是把该条指令的地址送到 %ebx寄存器当中