分布式并行计算

person 匿名

发布日期: 2021-03-22 19:02:46 浏览量: 218
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

分布式并行计算

>

Research Interests:

  • Parallel Computing (并行计算 )
  • Heterogeneous Computing (异构计算)
  • Machine Learning(机器学习)

参考书

  • An Introduction to Parallel Programming ,Peter S.Pacheco,机械工业出版社, 2011.——教材

  • Parallel Programming in C with MPI and OpenMP, Michael J. Quinn, McGraw-Hill Science, 2003

  • Programming Massively Parallel Processors(Second Edition) David B Kirk, Wen-mei W. Hwu, Morgan Kaufmann, 2010.

参考网站

课程目标

  • Fundamentals of parallel hardware and software
  • Parallel algorithms design and analysis
  • Parallel programming skills
    • MPI(Message-Passing Interface)
    • OpenMP(self study)
    • CUDA
    • OpenAcc

关键词

key words 解释
fine-grained 细粒度
cparse-grained 粗粒度
ILP Instruction-Level Parallelism 指令级并行
TLP Thread-Level Parallelism 线程级并行

分布式概念

  • Parallel computing:
    • the use of two or more processors (computers), usually within a single system, working simultaneously to solve a single problem.
  • Distributed computing:
    • any computing that involves multiple computers remote from each other that each have a role in a computation problem or information processing.

来源: 企鹅号-架构师技术联盟,并行计算与分布式计算区别与联系,腾讯云,https://cloud.tencent.com/developer/news/324518

A parallel computer is a multiple-processor computer system supporting parallel programming.

  • Two categories of parallel computers
    • Multicomputer:
      • A parallel computer is constructed out of multiple computers and an interconnection network. (message passing)
    • Centralized multiprocessor(symmetric multiprocessor or SMP)//集中式多处理器(对称多处理器或SMP):
      • A more highly integrated system in which all CPUs share access to a single global memory. (communication and synchronization by sharing memory)

来源: Guoming Lu,Chapter1-Introduction.pdf(p16),UESTC

来源: oreilly,Parallel versus distributed computing,https://www.oreilly.com

Why Parallel Computing?

  • 对计算能力的需求
    • 气候模拟
    • 蛋白质折叠
    • 药物发现
  • 摩尔定律变得不太可靠,晶体管密度的增加会伴随着热量的增加,太热了集成电路就变得不可靠了,进而往多核处理器方向发展,并行就显得很重要

How Do We Write Parallel Programs?

  • Task parallelism(任务并行)
    • Partition various tasks carried out solving the problem among the cores.

  • Data parallelism(数据并行)
    • Partition the data used in solving the problem among the cores.
    • Each core carries out similar operations on it’s part of the data.

eg:

一次考试,15个问题,一共300个学生参加考试,也就是300份卷子,现在需要进行改卷。有三个人(处理器)进行改卷。

  • Task parallelism
    • 分成3个任务,分别处理Q1-Q5、Q6-Q10、Q11-Q15
  • Data parallelism
    • 每个人改100份

协调工作coordination

Cores usually need to coordinate their work.

  • Communication(通信)
    • one or more cores send their current partial sums to another core.
  • Load balancing(负载平衡)
    • share the work evenly among the cores so that one is not heavily loaded.
  • Synchronization(同步)
    • because each core works at its own pace, make sure cores do not get too far ahead of the rest.

并行硬件和并行软件

冯·诺伊曼瓶颈

图:冯诺依曼结构 来源:wikipedia

冯诺依曼结构:是一种将程序指令存储器和数据存储器合并在一起的电脑设计概念结构。

在这之前每个程序都是直接设计成电路板的,也就是程序和数据是分离的,每需要修改程序就要重新焊一个电路板。冯诺依曼设计的构想是将成也转为编码然后和数据存储到一起。这种设计思想导致了硬件和软件的分离,即硬件设计和程序设计可以分开执行!

将CPU与存储器分开并非十全十美,反而会导致所谓的冯·诺伊曼瓶颈(von Neumann bottleneck):在CPU与存储器之间的流量(资料传输率)与存储器的容量相比起来相当小,在现代电脑中,流量与CPU的工作效率相比之下非常小,在某些情况下(当CPU需要在巨大的资料上运行一些简单指令时),资料流量就成了整体效率非常严重的限制。CPU将会在资料输入或输出存储器时闲置。由于CPU速度远大于存储器读写速率,因此瓶颈问题越来越严重。

Refrence: wikipedia-冯诺依曼体系

目前解决的方案: 多级缓存、分支预测

对冯诺依曼模型的改进

缓存Cache

高速缓冲存储器(Cache,简称缓存)

Cache 映射

虚拟存储器

交换空间

TLB(Translation-Lookaisde Buffer)

TLB命中

TLB缺失

页面失效(page fault)

1、Buffer(缓冲区)是系统两端处理速度平衡(从长时间尺度上看)时使用的。它的引入是为了减小短期内突发I/O的影响,起到流量整形的作用。比如生产者——消费者问题,他们产生和消耗资源的速度大体接近,加一个buffer可以抵消掉资源刚产生/消耗时的突然变化。
2、Cache(缓存)则是系统两端处理速度不匹配时的一种折衷策略。因为CPU和memory之间的速度差异越来越大,所以人们充分利用数据的局部性(locality)特征,通过使用存储系统分级(memory hierarchy)的策略来减小这种差异带来的影响。
3、假定以后存储器访问变得跟CPU做计算一样快,cache就可以消失,但是buffer依然存在。比如从网络上下载东西,瞬时速率可能会有较大变化,但从长期来看却是稳定的,这样就能通过引入一个buffer使得OS接收数据的速率更稳定,进一步减少对磁盘的伤害。
4、TLB(Translation Lookaside Buffer,翻译后备缓冲器)名字起错了,其实它是一个cache.

低层次并行

指令级并行
  • 流水线(Pipelining)
    • 指的是将功能单元分阶段安排
  • 多发射(multiple issue)
    • 指的是然多条指令同时启动

其实因为有多个复制的功能单元,所以可以将多发射和流水线认为时并行硬件。但是这种并行硬件对程序员时不可见的,锁以这里将他看作为对冯诺依曼模型的改进。

eg: 举一个关于计算的例子,将$9.8710^4$与$6.5410^4$相加

图:运算步骤 来源:《An Introdution to Parallel Programming》(p26)

我们假设每次操作要1ns,那么上图共需7ns

现在执行下面程序,那么大概需要花费7000ns

  1. float x[1000],y[1000],z[1000];
  2. ···
  3. for(int i=0;i<1000;i++)
  4. {
  5. z[i]=x[i]+y[i];
  6. }

方案一:Pipelinling

使用流水线的方法,虽然运行一次可能看不出来差别,但是数量多了就有差距了。

图:流水线加法。表格中数字表示操作数的下标 来源:《An Introdution to Parallel Programming》(p27)

可以看出这里for循环从7000降到了1000,提高了近7倍。

但是k个阶段不能达到k倍的效果,这里面要烤炉每个阶段的运行时间,会不会在某个阶段阻塞。

方案二:multiple issue

这个就是复制相同的功能单元来同时执行程序中的不同的指令。

假设有两个加法器,那么A计算z[0],B计算z[1],A计算完后,计算z[2]。

硬件多线程(hardware multithreading)

有些程序中有很多部分之间有依赖关系,导致不太容易实现和利用指令级并行。

比如,斐波拉契数f[i]=f[i-1]+f[i-2],这里每次计算都需要上次的结果,就无法设计流水线了。

指令级并行是执行细粒度的程序单元的并行。

线程级并行则是尝试同时执行不同线程了提供并行性。

硬件多线程为系统提供一种机制可以支持线程级的并行,如果当前执行的任务被阻塞时,系统可以继续器他有用的工作。

  • 细粒度的多线程,处理器在每条指令执行完后切换线程,从而跳过被阻塞的线程。
    • 可以避免因为阻塞导致机器时间的浪费
    • 缺点:执行很长一段指令的线程在执行每条指令的时候都需要等待。
  • 粗粒度的多线程,只切换需要等待很长时间才能完成操作而被阻塞的进程。就是这种进程才使用这种每条指令执行完后切换线程机制。

并行硬件

这里说的是如果能够通过修改源代码进而开发并行性或者必须修改源代码来开发并行性,那么认为这种硬件是并行硬件。

Michael J. Flynn是美国斯坦福大学的计算机教授,1972年他提出了著名的费林分类法(Flynn’s taxonomy,或Flynn’s classifications)。Flynn’s taxonomy是一种经典的计算机体系结构分类方式。Flynn根据指令流、数据流的多倍性特征把计算机系统(或体系结构)分成了四类:

  • SISD : single instruction single data
    • Execute a single instruction at a time and fetch or store one item of data at a time
    • Model of serial Von Neumann machine
    • Logically, single control processor
  • MISD : multiple instruction single data
    • Multiple Instruction Single Data
    • The term isn’t used (except when discussing the Flynn taxonomy) .
    • Perhaps applies to pipelined computation.
  • SIMD : single instruction multiple data
    • Applies the same instruction to multiple data items.
    • A single control unit and multiple ALUs
    • Multiple processors execute the same program in lockstep.
      • In a “classical” SIMD system, each ALU must wait for the next instruction to be broadcast before proceeding.
      • All the ALUs execute the same instruction or are idle.
    • Parallelism achieved by dividing data among the processors. Data that each processor sees may be different.
    • GPU利用了这方面的知识。
  • MIMD : multiple instruction multiple data

这其实也为并行计算的模型提供了四种实现方式(当前其中SISD其实就是串行的)。

对于涉及大量并行数据的应用而言,SIMD 架构的机器无疑是性价比最高的选择。在这种机器上,单个的 control unit 会将 instructions 向多个 processing elements 并行地进行广播,其中每个 PE 都是拥有本地存储器的一个功能单元集合。

现在市场上的多处理系统更多属于 MIMD 架构的,它比 SIMD 更进一步。一些标准的处理器和存储芯片通过高速总线在内部进行连接(memory 通常是交织的)。

美国计算机科学家、纽约大学教授 Jacob T. Schwartz 定义了两种大致的方法来组织处理器和内存,即 Paracomputers 和 Ultracomputers。Paracomputers 将 memory 从处理中分离出来。Memory 是共享的,处理器之间通过共享的 memory 来进行通讯。在 Paracomputers 中,如果我们认为每一个内存地址都可以被每一个处理器均等地访问,那么就可以据此认为 PRAM 模块以这种方式来被 Paracomputers 近似地模拟。另一方面,Ultracomputers 将 memory 分配给若干个处理器,这样就形成了众多 modules,一个处理器可以用恒定时间来访问它的 module 上的 memory,但是访问远程的 module 上的 memory 则要耗费更长时间。

在更多的资料中,我们常常用另外两个术语来替代 Paracomputers 和 Ultracomputers,即多处理器共享内存(multiprocessor shared memory)多计算机分布内存(multicomputer distributed memory),在共享内存系统中,处理器通过对全局皆知的内存地址(globally known memory address)进行读写来实现通信。硬件实现上会确保所有处理器对内存都有用相同的访问方式(即使用单一地址空间)。因此,这也被称为是对称多处理器机 “symmetric multiprocessor (SMP) machine”。而在分布内存系统中,处理器之间通过发送消息的方式来进行通信。此时硬件将仅负责消息的传递。也不再有单一地址空间。所以这也被称为是消息传送机器(message passing machine)。一个分布共享内存 (DSM) 系统拥有一个分布式的内存但是是一个单一的地址空间。 通常在 SMP 机器上编程要比再 message passing machine 上编程容易很多。然而,message passing machine 可以用更低的代价来进行扩容。

来源:CSDN 白马负金羁

共享内存系统

一个多核处理器在一块芯片上有多个CPU或者核。通常。每个核都拥有是私有的L1cache,而其他的Cache可以在核之间共享,也可以不共享。

类型有

  • 一致内存访问(Uniform Memory Access,UMA)
    • 多个处理器直接连到一块内存上。
  • 非一致内存访问(Nonuniform Memory Access,NUMA)
    • 通过处理器中内置特殊的硬件,可以访问其他处理器的内存。

分布式内存系统

最广泛使用的是集群(clusters).

上传的附件

热门回复

  • 基于SSM的超市订单管理系统
    可以用吗,怎么用的
    2021-04-14 15:44:50 thumb_up( 1 )
  • 线程同步之临界区
    程序还算比较简单的,谢谢分享
    2019-04-20 12:24:58 thumb_up( 1 )
  • 基于WinPcap实现的UDP发包程序
    如果在vs 编译时出现 无法找到元数据文件 platform.winmd 应该怎么解决
    2021-03-23 09:58:16 thumb_up( 2 )
  • 机器视觉MIL Mod匹配
    You can also search within the full angular range of 360� from the nominal angle specified with M_ANGLE. Use the MmodControl()�M_ANGLE_DELTA_POS and M_ANGLE_DELTA_NEG control types to specify the angular range in the counter-clockwise and clockwise direction from the nominal angle, respectively; the default for both is 180�. The angular range limits the possible angles which can be returned as results for an occurrence. Note that the actual angle of the occurrence does not affect search speed. If you need to search for a model at discrete angles only (for example, at intervals of 90 degrees), it is typically more efficient to define several models with different expected angles, than to search through the full angular range. By default, calculations specific to angular-range search strategies are enabled. If you expect that the occurrences sought are close to the specified nominal angle, you can disable these calculations using MmodControl() with M_SEARCH_ANGLE_RANGE set to M_DISABLE. When disabled, you must specify a good nominal angle for each model, which is within the model's angular range. You can restrict which candidates are returned as occurrences by narrowing the angular-range. Note that M_SEARCH_ANGLE_RANGE must be enabled to search for a rotation-invariant non-synthetic model (for example, an image-type model of a circle).
    2021-03-20 13:27:51 thumb_up( 2 )
eject