终其一生,我们只不过在寻找自己

0%

MSBD5009 并行计算介绍

并行计算parallel programming

更新:这门课太硬核,换课了

选这门课主要是想提高编程能力,顺便了解一下os相关知识,本科没学过操作系统和编译原理什么的,经常遇到了云里雾里的。
还有以前还去碰过CUDA,自己瞎研究深度学习的项目,最后连CUDA和TF的版本适配都没解决,害,一把辛酸泪。
第一节课遇到各种线程进程cache,中文都不知道是啥,听得云里雾里的。


这门课的分数构成:
50分的三次编程作业,每次作业是对已经有的代码填空。
50分的考试,有编程填题,也有简答题。


三本参考书:

  • Introduction to Parallel Computing 2nd edition
  • An Introduction to Parallel Programming
  • Programming Massively Parallel Processors:
    A Hands-on Approach 3rdd Edition

不出意外是不会看了🤣,以后需要再说吧。

并行计算的基本背景

为什么我们需要一度的提高性能/表现?

随着数据的增长和计算的需求(基因计算,深度学习,天文计算,天气模型,蛋白质计算等等)增加,cpu的性能越来越不够用,简单的办法就是增加核心数。
核心数增加了就需要让程序能充分利用起来各个核心,就像老板跟员工派任务一样,需要充分榨干劳动力。

为什么需要构建并行系统

芯片的瓶颈难以突破,只有从系统上高效调用。
瓶颈:高密度的晶状体-> 更快的芯片->增加耗能->增加发热->导致芯片不稳定
所以需要多核合作。

为什么需要写并行的程序

直接改写串行的程序可能会遇到各种复杂的问题,数据结构,算法设计方面的。改写出来的可能依然不高效。

怎么写并行程序

  • 任务划分
    例子:改卷每人改一道题
  • 数据划分
    例子:改卷每人改100张卷

需要解决多核合作的问题:

  • 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. 齐头并进

concurrent,parallel,distributed

• Concurrent computing – In a program multiple tasks can be in progress at any instant. 程序同时处理多个任务

• Parallel computing – In a program multiple tasks cooperate closely to solve a problem.
多个任务协作

• Distributed computing – A program may need to cooperate with other programs to solve a problem.
程序之间协作

没搞懂这里的tasks和program之间的区别

总结

  • 并行系统是计算趋势
  • 串行的程序不能用上多核
  • 要学习如何要调用内核
  • 也需要可靠的开发技术

硬件和操作系统

冯·诺伊曼模型

[百度百科]
冯·诺依曼型计算机一般具有以下五个功能:必须具有长期记忆程序、数据、中间结果及最终运算结果的能力;能够完成各种算术、逻辑运算和数据传送等数据加工处理的能力;能够根据需要控制程序走向,并能根据指令控制机器的各部件协调操作;能够按照要求将处理结果输出给用户。

冯·诺依曼型计算机从本质上讲是采取串行顺序处理的工作机制,即使有关数据巳经准备好,也必须逐条执行指令序列。而提高计算机性能的根本方向之一是并行处理。因此,近年来人们谋求突破传统冯·诺依曼体制的束缚,这种努力被称为非诺依曼化。对所谓非诺依曼化的探讨仍在争议中,一般认为它表现在以下三个方面的努力。
  (1)在冯·诺依曼体制范畴内,对传统冯·诺依曼机进行改造,如采用多个处理部件形成流水处理,依靠时间上的重叠提高处理效率;又如组成阵列机结构,形成单指令流多数据流,提高处理速度。这些方向已比较成熟,成为标准结构;
  (2)用多个冯·诺依曼机组成多机系统,支持并行算法结构。这方面的研究目前比较活跃;
  (3)从根本上改变冯·诺依曼机的控制流驱动方式。例如,采用数据流驱动工作方式的数据流计算机,只要数据已经准备好,有关的指令就可并行地执行。这是真正非诺依曼化的计算机,它为并行处理开辟了新的前景,但由于控制的复杂性,仍处于实验探索之中。

Central processing unit (CPU)

• Control unit - responsible for deciding which instruction in a program should be executed. (the boss) 控制单元

• Arithmetic and logic unit (ALU) - responsible for executing the actual instructions. (the worker) 计算单元

关键terms

• Register – very fast storage, part of the CPU.

• Program counter – stores address of the next instruction to be executed.

• Bus – wires that connect the CPU and memory.

冯·诺伊曼模型的瓶颈在于CPU和内存的分离,cpu的寄存器太小,必须和内存交换数据,但是互联的速率有限。

Locality

• The same or nearby locations are accessed frequently.
• Spatial locality – accessing a nearby location.
• Temporal locality – accessing in the near future.

从cpu到cache的问题

由于cache分三级,很有可能写入不连续。
–直写式 通过在写入高速缓存时更新主内存中的数据来处理此问题。
–回写式 将缓存cache中的数据标记为脏数据。当高速缓存行由内存中的新高速缓存行替换时,脏行将写入内存。

缓存映射Cache Mapping

• 完全关联–可以在缓存中的任何位置放置新行。
• 直接映射–每条缓存行在缓存中都有一个唯一的位置,将为其分配该位置。
• n向集合关联–每个高速缓存行可以放置在高速缓存中n个不同位置之一中。

缓存逐出Cache Eviction

•缓存比主内存小得多。
•当缓存已满时,需要在内存中添加新行以替换或逐出缓存中的行。
•常见的缓存逐出策略包括LRU / MRU(最近最少使用/最近使用)和LFU(最近最少使用)。

虚拟内存

•如果我们运行非常大的程序或访问非常大的数据集的程序,则所有指令和数据可能无法放入主存储器。
•虚拟内存用作辅助存储的缓存
•它利用时空局部性原理。
•它仅将正在运行的程序的活动部分保留在主存储器中。
交换空间Swap space–辅助存储区,用于保持非活动(部分)正在运行的程序。
虚拟的页page–数据和指令块。大多数系统具有固定的页面大小,当前范围为4到16 KB。

虚拟页码

•编译程序时,其页面为分配的虚拟页码。
•运行程序时,将创建一个表,该表将虚拟页码映射到物理地址。
•页表用于将虚拟地址转换为物理地址。

转换后备缓冲器(Translation-lookaside buffer TLB)

•使用页表有可能显着增加每个程序的整体运行时间。
•TLB是处理器中的特殊地址转换缓存。
•它在非常快的内存中从页表中缓存了少量条目(通常为16–512)。
•页面错误–尝试访问页面表中页面的有效物理地址,但该页面仅存储在磁盘上。

指令级并行(Instruction Level Parallelism ILP)

•试图通过使多个处理器组件或功能单元同时执行指令来提高处理器性能。
•流水线Pipelining-功能单元是分阶段安排的。
•多个问题-可以同时启动多个指令。

硬件多线程Hardware multithreading

•并非总是有机会同时执行不同的线程。
•硬件多线程为系统提供了一种在当前正在执行的任务停滞后继续进行有用工作的方法。
– 例如,当前任务必须等待从内存加载数据。
•细粒度-处理器在每条指令后在线程之间切换,跳过停滞的线程。
–优点:可以避免因停转而浪费机器时间。
–缺点:准备好执行长指令序列的线程可能必须等待执行每条指令。
•粗粒度-仅切换等待耗时的操作完成而停止的线程。
–优点:切换线程几乎不需要即时。
–缺点:处理器可以在较短的停顿时间内空闲,并且线程切换也将导致延迟。
•同步多线程(SMT)-细粒度多线程的变体。
•允许多个线程使用多个功能单元。

-------------    你的留言  是我更新的动力😊    -------------