并行处理机

什么是并行计算?

并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器通过网络以一定的连接方式有序地组织起来,现多采用MIMD(多指令多数据流)型计算机
并行处理的两个挑战

  • 程序中有限的并行性
  • 相对较高的通信开销

存储器体系结构分类

  • 集中式共享存储器结构 UMA(Uniform memory access)
  • 分布式存储器结构
    优点:局部存储器的访问延迟低

缺点:处理器之间的通信较为复杂,且各处理器之间访问延迟较大。

两种地址空间的组织方案

  • 物理上分离、逻辑上共享的编址方式。通常被称为分布式共享存储器或可缩放共享存储器
  • 物理上分离、逻辑上独立的编织方式。每一个处理器-存储器模块实际上是一个单独的计算机,这种机器也称为多计算机

两种通信模型

  • 对于共享地址存储器利用Load/Store指令进行数据通信
    优点:易于编程、通信开销低、通信延迟低
  • 对于多个地址空间的机器,使用消息传递机器显式传递消息。(消息传递机器根据简单的网络协议,通过传递消息来请求某些服务或传输数据,从而完成通信,可以看做是RPC远程进程调用)
    优点:硬件简单,着重处理开销大的通信

对称式共享存储器

基本结构:多处理器通过总线共享一个物理存储器,处理器各有独自的Cache
Cache的迁移和复制
迁移针对单个处理器而言备份远程数据项到本处理器Cache
复制针对多个处理器需要同时读取的数据项备份在各自Cache
一致性定义

  • 处理器P对X进行一次写之后又对X进行读,读和写之间没有其它处理器对X进行写,则读的返回值总是写进的值。
  • 一个处理器对X进行写之后,另一处理器对X进行读,读和写之间无其它写,则读X的返回值应为写进的值
  • 对同一单元的写是顺序化的,即任意两个处理器对同一单元
    问题:Cache的一致性问题

例 两个处理器Cache对应同一存储器单元产生出不同的值

时间CPU A CacheCPU B Cache存储器
0 1
A 读 存储器1 1
B 读 存储器111
A 存 入0010

此时如果B读Cache,它将得到1,与存储器值不符。

一致性解决方案

**监听技术
在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权。**
写作废协议
即某处理器在一次写操作后作废其他处理器的Cache备份**

例 在写回Cache的条件下,监听总线中写作废协议的实现

处理器行为总线行为Cache ACache B主存
0
A 读Cache失效0 0
B 读Cache失效000
A 写入1作废主存单元及其他备份1 0
B 读Cache失效111

写更新协议
当一个处理器写某数据项时,通过广播使其它Cache中所有对应的该数据项拷贝进行更新

例: 写回Cache条件下,监听总线中写更新协议的实现

处理器行为总线行为Cache ACache B主存
0
A 读Cache失效0 0
B 读Cache失效000
A 写入1作废主存单元及其他备份111
B 读Cache失效111

写作废协议在连续写情况下比写更新协议性能好得多,实际中常用写作废协议。

实现技术

  • 用Cache中块的标志位实现监听过程(是否作废)。
  • 给每个Cache块加一个特殊的状态位说明它是否为共享。
  • 因为每次总线任务均要检查Cache的地址位,这可能与CPU对Cache的访问冲突。可通过下列两种技术之一降低冲突:

    • 复制标志位
    • 采用多级包含Cache,监听二级Cache来避免访问一级Cache带来的冲突

分布式共享存储器

分布式共享存储器有各自单独的存储器和Cache,物理、逻辑上均独立。
对于分布式共享存储器可以不支持Cache一致性,但当访问数据多为远程节点数据时,巨大延迟是其突出缺点。对于分布式共享存储器有目录技术支持Cache一致性。
目录技术
目录:一种专用的存储器所记录的数据结构,它记录着可以进入Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。一个目录项被分配到一个存储器块。
宿主节点:存放存储器块和对应地址目录项的节点。
每一个目录项主要有状态位向量两种成分。

  • 状态描述该目录所对应存储块的当前情况,状态有三种

    • 共享 在一个或多个处理器上具有这个块的拷贝,且主存中的值是最新值(所有Cache均相同)
    • 未缓冲:所有处理器的Cache都没有此块的拷贝
    • 专有:仅有一个处理器上有此块的拷贝,且已对此块进行了写操作,而主存的拷贝仍是旧的。这个处理器称为此块的拥有者
  • 位向量共有N位,其每一位对应于一个处理器的局部Cache,用于指出该Cache中有无该存储块的拷贝

在各个状态下所接收到的请求和相应的操作

  • 当一个块处于未缓冲状态时,对此块发出的请求及处理操作

    • 读失效 将存储器数据送往请求方处理器,且本处理器成为此块的唯一共享结点,本块的状态转换为共享。
    • 写失效 将存储器数据送往请求方处理器,此块成为专有。
  • 当一个块是共享状态时,存储器中的数据是其当前最新值,对此块发出的请求及处理操作为

    • 读失效 将存储器数据送往请求方处理器,并将其加入共享集合。
    • 写失效 将数据送往请求方处理器,对共享集合中所有的处理器发送写作废消息,且将共享集合置为仅含有此处理器,本块的状态变为专有
  • 当某块处于专有状态时,本块的最新值保存在共享集合指出的拥有者处理器中,从而有三种可能的目录请求。

    • 读失效 将“取数据”的消息发往拥有者处理器,使该块的状态转变为共享,并将数据送回目录结点写入存储器,进而把该数据返送请求方处理器,将请求方处理器加入共享集合。
    • 写失效 本块将有一个新的拥有者
    • 数据写回 拥有者处理器的Cache要替换此块时必须将其写回,从而使存储器中有最新拷贝(宿主结点实际上成为拥有者),此块成为非共享,共享集合为空

改进
有限映射目录 备份数总小于常数M
链式结构目录 可扩展

Last modification:April 20th, 2020 at 09:52 am
如果觉得我的文章对你有用,请随意赞赏