文档介绍：计算机系统构造
第一章 根本概念
第二章 指令系统
第三章 存储系统
第四章 输入输出系统
第五章 标量处理机
第六章 向量处理机
第七章 互连网络
第八章 并行处理机
第九章 多处理机
精选
*
互连网络是一y) B(k)最低k位的最高位与最低位互换位置
超蝶式(superbutterfly) B(k)最高k位的最高位与最低位互换位置
显然成立
教材P398L1,2错
精选
*
5、蝶式置换Butterfly
与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连。
精选
*
6、位序颠倒置换Bit Reversal
将输入端二进制地址的位序反过来就得相应输出的地址。
子反位序函数：最低k位的位序反过来
超反位序函数：最高k位的位序反过来
对于n=3的情况，正好有 R=B，R(2)=B(2)，R(2)=B(2)。
精选
*
7、移数置换
将输入端数组循环移动一定的位置向输出端传输。
也可以将整个输入数组分成假设干个子数组，在子数组内进展循环移数置换，这种段内循环移数的表达式可写成为两个式子如下：
(a)移数量换k=2 (b)段内移数置换k=1,r=2
精选
*
8、加减2i置换
其中：0 x N-1，0 i n-1，n = log2 N。
精选
*
8、加减2i置换
通常采用移数函数可以构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网等。
例如，Illiac函数是构成Illiac IV阵列的根底，它包含PM20和PM2n/2等四个互连函数。
采用全部移数函数构成网络称为移数网，移数网的结点度d=2n-1，网络直径D=n/2
精选
*
1 互连网络的特性
互连网络通常是用有向边或无向边连接有限个结点的组成。
互连网络的主要特性有
(1) 网络规模：网络中结点的个数
(2) 结点度：与结点相连接的边数称为结点度。包括入度和出度。
进入结点的边数叫入度，从结点出来的边数那么叫出度
(3) 距离：两个结点之间相连的最少边数
(4) 网络直径：网络中任意两个结点间距离的最大值。
用结点间的连接边数表示
精选
*
(5) 等分宽度：
当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示。
于是线等分宽度就是B=b×w，w为通道宽度(用位表示)。
等分宽度是说明沿等分网络最大通信带宽的一个参数。
网络的所有其它横截面都应限在等分宽度之内。
(6) 结点间的线长：
两个结点间连线的长度。用米、公里等表示
(7) 对称性：
从任何结点看到拓扑构造都是一样的网络称为对称网络。
对称网络比较易实现，编程也较容易。
精选
*
2 互连网络传输的性能参数
一台机器发送消息给另一台机器时，发送方的步骤如下：
(1) 用户程序把要发送的数据拷贝到操作系统的缓冲区。
(2) 操作系统把缓冲区中的数据打包，并发送的网络接口部件。
(3) 网络接口硬件开场发送消息。
数据包的接收步骤如下：
(1) 把数据包从网络接口部件拷贝到操作系统缓冲区。
(2) 检查收到的数据包，如果正确，给接收方发答复信号。
(3) 把接收到的数据拷贝到用户地址空间。发送方接收到答复信号后，释放系统缓冲区
精选
*
互连网络在传输方面的主要性能参数
(1) 频带宽度(Bandwidth)：
互连网络传输信息的最大速率
(2) 传输时间(Transmission time)：
等于消息长度除以频宽
(3) 飞行时间(Time of flight)：
第一位信息到达接收方所花费的时间
(4) 传输时延(Transport latency)：
等于飞行时间与传输时间之和
(5) 发送方开销(Sender overhead)：
处理器把消息放到互连网络的时间
(6) 接收方开销(Receiver overhead)：
处理器把消息从网络取出来的时间
精选
*
一个消息的总时延
总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销
精选
*
假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？
解
，信号在导体中传递速度大约是光速的50%，相距100米时总时延
相距1000公里时的总时延
精选
*
.