计算机系统结构课程总结(互连网络)

多处理机

包含两个或两个以上功能大致相同的处理器
所有处理器共享一个公共内存
所有处理器共享I/O通道、控制器和外围设备
整个系统由统一的操作系统控制，全面并行

多处理机属于MIMD。

多处理机系统的cache一致性保障

静态一致性校验：对于共享的可写（即可修改）的信息不准进入cache。
增加一个共享cache：共享信息均在共享cache内，而取指令和独用数据则使用独用cache。
动态一致性校验：在若干个cache中使同一个信息始终保持动态一致。
- 广播法
- 目录法

互连网络(ICN)

互连网络是由开关元件按照一定拓扑结构和控制方式构成的网络，实现多个结点对之间的相互连接。

出端编码是入端编码的排列、组合、移位、取反等操作的结果。表示所有入端与出端的连接关系。

互连函数表示法：
$f (b_{n - 1} . . . b_{0}) = b_{0} b_{n - 2} . . . b_{1} b_{n - 1}$
这里的b都是二进制位，也就是说，入端和出段的编码都用一串二进制，它所表示的数值则表达了具体的结点，但是使用二进制会方便书写映射关系。
图形表示法
输入输出对应表示法：
$输入： 7654321$
$输出： 1654327$

一个互连函数即表征了一个单级互连网络。

恒等置换(可逆)

f (b_{n - 1} . . . b_{0}) = b_{n - 1} . . . b_{0}

立方体置换(可逆)

一位编码取反，如：

C u b e_{2} (b_{3} b_{2} b_{1} b_{0}) = b_{3} \bar{b_{2}} b_{1} b_{0}

交换置换(可逆)

$b_{0}$ 位(最低位)取反的立方体置换。

E x c h a n g e (. . .) = C u b e_{0} (. . .)

混洗置换

循环左移1位：

S h u f f l e (b_{n - 1} b_{n - 2} . . . b_{1} b_{0}) = b_{n - 2} . . . b_{1} b_{0} b_{n - 1}

混洗置换与交换置换的多次组合，可实现某结点到任意结点的连接。

逆混洗置换

循环右移1位：

S h u f f l e^{- 1} (b_{n - 1} b_{n - 2} . . . b_{1} b_{0}) = b_{0} b_{n - 1} b_{n - 2} . . . b_{1}

蝶式置换(可逆)

最高位和最低位交换位置：

β u t t e r f l y (b_{n - 1} b_{n - 2} . . . b_{1} b_{0}) = b_{0} b_{n - 2} . . . b_{1} b_{n - 1}

反位序置换(可逆)

把编码倒过来：

R e v e r s a l (b_{n - 1} . . . b_{0}) = b_{0} . . . b_{n - 1}

移数置换

输入端向量循环移动一定的位置：

α (x) = (x + r) m o d 2^{n}, 0 \leq x \leq 2^{n}

经常取

r = 2^{i}

，因此移数函数又称为加减

2^{i}

函数、

P M 2 I

函数等。

注意，当 $P M 2 I$ 中 $I$ 取负值时，表示 $r = - 2^{I}$ ，而不是 $r = 2^{- I}$ 。例如， $P M 2 - 0$ 即表示 $r = - 2^{0} = - 1$ 。

单级互连网络特性

任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。

多级互连网络

多级互连网络采用多个相同的或不同的单级互连网络直接连接起来，实现任意节点间的直接互连。

交换开关
交换开关之间的拓扑连接
对交换开关的不同控制方式

axb交换开关

$a \times b$ 交换开关具有 $a$ 个输入和 $b$ 个输出，常用 $a = b = 2$ 。
计算机系统结构课程总结(互连网络)
仅具有直通和交换两种功能的是二功能开关，需1位控制信号；具有全部4种功能的是四功能开关，需4位控制信号。

拓扑结构

前一级交换开关的输出端和后一级交换开关的输入端的连接模式。

控制方式

级控制：同级交换开关使用同一个控制信号控制。
单元级控制：每个交换开关分别控制。
部分级控制：第i级使用第i+1个控制信号控制。

超立方体寻径

截PPT：
计算机系统结构课程总结(互连网络)

集群系统

通过高速互连网络把通用计算机连接起来，采用消息传递机制，并最终向用户提供单一并行编程环境和计算资源。