多核处理器

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

多核处理器

消息传递与共享存储

共享存储与消息传递的编程复杂度

任务划分与数据划分 ：

  • 共享存储编程只需划分任务
  • 消息传递编程除了划分任务外，还需划分数据和考虑通信 （类似于微信与短信）

传递复杂的数据结构较困难

  • 多个指针组成的结构 ：struct {int pa; int pb; int *pc}

动态通信

  • {for (i,j){ x=…; y=…; a[i][j]=b[x][y];}}

  • 进程迁移及进程数目的变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#define NUM_THREADS 4 //假设线程数目为4
#define n 1000
double *A,*B,*C;
void *matrixMult(void *id) {//计算矩阵乘
    int my_id = (int ) id;
    int i,j,k,start,end;
    //计算进程负责的部分
      start = my_id*(n/NUM_THREADS);
     if(my_id == NUMTHREADS-1)
     end = n;
     else 
      end = start+(n/NUM_THREADS);
     for(i=start;i<end;i++)
        for(j=0;j<n;j++) {
         C[i*n+j] = 0;
         for(k=0;k<n;k++)
          C[i*n+j]+=A[i*n+k]*B[k*n+j];
        }
   }
int main() {
    int i,j;
    pthread_t tids[NUM_THREADS];
    //分配数据空间
   A = (double *)malloc(sizeof(double)*n*n);
   B = (double *)malloc(sizeof(double)*n*n);
  C = (double *)malloc(sizeof(double)*n*n);
  //初始化数组
  for(i=0;i<n;i++)
      for(j=0;j<n;j++){ 
        A[i*n+j] = 1.0;
        B[i*n+j] = 1.0；
       }
  for(i=0; i<NUM_THREADS; i++)
     pthread_create(&tids[i], NULL, matrixMult, (void *) i);
    for(i=0; i<NUM_THREADS; i++)
        pthread_join(tids[i], NULL);
  return 0;
}

共享存储多核处理器的关键问题

共享存储系统中的访存相关性

一致性问题

在单机系统中，只要保持程序中的数据相关性，就可以保证执行正确。在多处理机系统中，不仅要考虑单机内的数据相关，而且要考虑多机之间的数据相关

并行程序模型

程序模型

  • 一个进程P是一个二元组\(<V(P),P_0(P)>\)，其中V(P)是LOAD和STORE指令的集合，\(P_0(P)\)是V(P) 上的一个全序关系

  • 由N个进程P1,P2,…,Pn组成的程序PRG(P1,P2,…,Pn)是一个二元组\(<V(PRG),P_0(PRG)>\)，其 中\(V(PRG)=V(P1) \cup V(P2)...\cup V(Pn)\)是程序PRG的指令集，\(P_O(PRG)=P_O(P1) \cup P_O(P2)...\cup P_O(Pn)\)是程序PRG的程序序

冲突访问

  • 如果两个访存操作访问的是同一单元且其中至少有一个是存数操作, 则称这两个访存操作是冲突的。

\(C(PRG)=\{(u,v)|((u,v) \in V(PRG)) \cap (u,v是冲突访问)\}\) 称为程序PRG中冲突访问对集

执行的概念

在在一个并行执行中，一旦互相冲突的访问的执行次序确定了。那么执行结果也就确定了。

在程序PRG中, 对冲突访问对集C(PRG)的任一无圈定序称为程序PRG的一个执行，记为E(PRG)。

执行的正确性

程序PRG的执行E(PRG)正确的充要条件是\(E(PRG) \cup P_O(PRG)\)无圈。

例子：

针对上图有：

为了保证执行的正确性,程序中的数据相关性不能被破坏。如果两条访存指令访问的是同一变量且其中至少有一条是存数指令，则这两条指令是数据相关的。在单处理器中,程序执行的结果是由程序中数据相关的指令的执行次序来唯一决定的。在多处理器中,与单处理器中“数据相关”这一概念相对应的是“冲突访问”。在共享存储多处理器系统中,如果两个访存操作访问的是同一单元，且其中至少有一个是存数操作,则称这两个访存操作是冲突的。上面的程序PRG1中,L11和L22是冲突访问,因为它们都访问单元a且L1]是存数操作:同样,112和L21也是冲突访问。把程序PRG中冲突访问对的集合记为((PRG),即 \(C(PRG)=\{(u,v)|(u\in V(PRG)) \cap (v \in V(PRG))N(u;v 是冲突访问)\}\)

上图中有：

判断是否有圈：

可见c是有圈的，不是正确执行。

下图中的程序PRG2的冲突访问对集为:

\(C(PRG2)=((L11,L21),(L11,L32),(L31,L22)\)

存储一致性模型

常见的存储一致性模型

  • 顺序一致性模型（Sequential Consistency）
  • 处理器一致性模型（Processor Consistency）
  • 弱一致性模型（Weak Ordering）
  • 释放一致性模型（Release Consistency）
  • 域一致性模型（Scope Consistency）
  • 单项一致性模型（Entry Consistency）

CACHE一致性协议

单写和多写

单写：任一时刻只有一个处理机能写某共享单位

多写：多个处理机同时写某共享单位的不同部分

ESI/MSI协议

ESI 是指Cache 行的三种一致性状态：

  • E（Exclusive，独占）：表明对应Cache 行被当前处理器核独占，当前处理器核可 以随意读写，其他处理器核如果想读写这个cache 行需要请求占有这个cache 块的 处理器核释放该Cache 行
  • S（Shared，共享）：表明当前Cache 行可能被多个处理器核共享，只能读取，不能 写入
  • I （Invalid，无效）：表明当前Cache 块是无效的

协议举例

a)初始状态，目录中块X为CLEAN，Pi为INV，Pj和Pk为SHD。

  1. Pi发出store操作。Pi向目录申请write，目录通告P和Pk invalid，P和Pk状态设置为INV，并回复invalid ack。目录通告Pi，write ack允许写，并记录下X的备份在Pi，修改状态为DIRTY。Pi修改状态为EXC。

c)Pk发出store操作。Pk向目录申请write,目录通告Pi invalid和write backPi回复invalid writeback ack，回传一个修改备份给目录。目录更新备份，发送给Pk，并write ack允许写，并记录下X的备份在Pk，修改状态为DIRTY。Pk修改状态为EXC

d)P发出oad操作。Pi向目录申请read，目录通告Pk write back，Pk复 writeback ack，回传一个修改备份给目录，目录更新备份，发关给Pi，read ack允许读，并记录下X的备份在Pk与Pi，修改状态为CLEAN.P和PK修改状态为SHD

e)P发出oad操作。Pi问目录申请read，目录将备份发送给P，并read ack允许读，并记录下X的备份在Pk、P和Pi。Pi修改状态为SHD。 状态，目录中块X为清洁，n为IN V,pj和pk为SH D。

MSI