计算机结构:(m, n)-关联-分支预测器 — (m,n)-Korrelationsprädiktor

首先吐槽Rechnerstruktur这门课懒惰的教授:Prof. Dr. Wolfgang Karl。老头子Folien不改动直接改日期拿来用就不提了,Korrelationsprädiktor这么重要的考试内容居然在Folien上只给了个名字,Übungsblatt里面这个题让我查资料查了两个多小时才搞懂。

正文开始:

(m, n)-关联-分支预测器是由以下两个部分组成:

一个m位-全局分支历史寄存器 (BHR: Branch History Register)

由m位移位寄存器构成,用于记录当前跳转的前m个实际分支行为历史,每一位用来记录该分支是否实际被执行,1对应实际执行,0对应实际未执行。

一个含有2^m个条目(Eintrag)的模式历史表 (PHT: Pattern History Table),每个条目对应一个n位-简单预测器

继续阅读计算机结构:(m, n)-关联-分支预测器 — (m,n)-Korrelationsprädiktor

图论:树,图的生成树

树的定义:
如果一个无向简单图G满足以下相互等价的条件之一,那么G是一棵树:
1. G是没有回路的连通图。
2. G没有回路,但是在G内添加任意一条边,就会形成一个回路。
3. G是连通的,但是如果去掉任意一条边,就不再连通。
4. G内的任意两个顶点能被唯一路径所连通。 继续阅读图论:树,图的生成树

图论:连通,连通图,强连通图,连通分量,强连通分量概念及解析

概念:
1. 连通:在一个无向图G中,若从顶点v_i到顶点v_j有路径相连(当然从v_j到v_i也一定有路径),则称v_i和v_j是连通的。如果G是有向图,那么连接v_i和v_j的路径中所有的边都必须同向。
2. 连通图:如果图中任意两点都是连通的,那么图被称作连通图。
3. 强连通图:有向图G = (V,E)中,若对于V中任意两个不同的顶点x和y,都存在从x到y以及从y到x的路径,则称G是强连通图。
4. 连通分量:无向图G的一个极大连通子图称为G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

解析:
对于一个无向图,说强联通没有意义,因为此时强连通就是连通。

而对于一个有向图,它不一定是强连通的,但可以分为几个极大的强连通子图(“极大”的意思是再加入任何一个顶点就不满足强连通了)。这些子图叫做这个有向图的强连通分量。

强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连通分量,且多个强连通分量之间没有共享边及共享节点。

任意一个强连通分量都至少包含一个有向环。