计算机系统结构 复习笔记

计系构

互连网络

互联函数

1. 恒等函数

   $$I(x_{n - 1}x_{n - 2} \dots x_1x_0) = x_{n - 1}x_{n - 2} \dots x_1x_0$$

2. 交换函数（把某一位取反）

   $$\text{Cube}_i(x_{n - 1}x_{n - 2} \dots x_i \dots x_1x_0) = x_{n - 1}x_{n - 2} \dots \overline{x_i} \dots x_1x_0$$

3. 均匀洗牌（循环左移 1 位）

   $$\sigma(x_{n - 1}x_{n - 2} \dots x_1x_0) = x_{n - 2} \dots x_1x_0x_{n - 1}$$

4. 逆均匀洗牌（循环右移 1 位）

   $$\sigma^{-1}(x_{n - 1}x_{n - 2} \dots x_1x_0) = x_0x_{n - 1}x_{n - 2} \dots x_1$$

5. 蝶式函数（交换第一位和最后一位）

   $$\beta(x_{n - 1}x_{n - 2} \dots x_1x_0) = x_0x_{n - 2} \dots x_1x_{n - 1}$$

6. 反位序函数（倒序）

   $$\rho(x_{n - 1}x_{n - 2} \dots x_1x_0) = x_0x_1 \dots x_{n - 2}x_{n - 1}$$

7. 移数函数（十进制编号错位）

   $$\alpha(x) = (x \plusmn k) \text{ mod } N$$

8. PM2I 函数（二进制编号某一位加减 1，之后正常进位或借位，忽略超出比特位数的进位或借位）

   $$\text{PM2}_{\plusmn\text{i}}(x_{n - 1}x_{n - 2} \dots x_i \dots x_1x_0) = x_{n - 1}x_{n - 2} \dots (x_i \plusmn 1) \dots x_1x_0$$

静态互连网络

静态互联网络参数表

注：

1. Illiac 网是指度为 4 的带弦环，同样也可以对二位网格做如下操作得到：
   1. 把网络的每一列的两个端结点连接起来
   2. 把每一行的尾结点与下一行的头结点连接起来
   3. 把最后一行的尾结点与第一行的头结点连接起来
2. CCC 是指带环立方体，将 k 维立方体中的每一个顶点都换成包含 k 个结点的环

动态互连网络

每一层有若干个开关，开关相当于是一个映射，将输入的 $s$ 个编号映射到输出的 $s$ 个编号上

控制方式：对各个开关模块进行控制的方式

• 级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态
• 单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态
• 部分级控制：第 $i$ 级的所有开关分别用 $i+1$ 个信号控制，$0\leq i \leq n-1$