课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决；如何 比较模型的表达能力 本讲座概要介绍并行编程模 2.程序理论关心的问题 型及一些相关概念 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题，解决该类问题需多少资源
课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源2 本讲座概要介绍并行编程模 型及一些相关概念
讲座提纲 ·基本知识 -多核体系结构、 并行编程模型 ·内存一致性模型 严格一致性模型、顺序一致性模型、内存一致性 模型的重要性 共享变量并行编程模型 一-同步、锁、临界区、条件变量、死锁、数据竞争 消息传递并行编程模型 -消息传递、同步与异步 3
讲 座 提 纲 • 基本知识 – 多核体系结构、并行编程模型 • 内存一致性模型 – 严格一致性模型、顺序一致性模型、内存一致性 模型的重要性 • 共享变量并行编程模型 – 同步、锁、临界区、条件变量、死锁、数据竞争 • 消息传递并行编程模型 – 消息传递、同步与异步 3
基本知识 ·对称多处理器 一对称多处理器的体系结构 通过共 享内存来 处理器 处理器 处理器 处理器 进行通信 级 一级 必须在 缓 缓 缓 缓存 处理器的 级 二级 二级 缓存中找 缓 缓存 爱 缓存 到它操作 的大部分 总线 数据，以 保证性能 内存 4
• 对称多处理器 – 对称多处理器的体系结构 二级 缓存 内存 总线 二级 缓存 二级 缓存 二级 缓存 一级 缓存 一级 缓存 一级 缓存 一级 缓存 处理器 处理器 处理器 处理器 基 本 知 识 必须在 处理器的 缓存中找 到它操作 的大部分 数据，以 保证性能 通过共 享内存来 进行通信 4
基本知识 ·几个概念的粗略解释 任务：一般性的抽象术语，指由软件完成的一个 活动。例如，矩阵分块乘就是把矩阵乘分成多个 任务，以便于在对称多处理器上并行执行这些任务 进程：任务在程序中的对应物，它有自己的数据 和代码，需要在处理器上运行直至结束。进程是 操作系统为其进行资源分配和调度的独立单位 线程：是把进程细分出现的实际运行单位，线程 是进程中一段顺序执行的语句序列。把进程分成 若干线程是为了提高进程执行过程中的并行性。 线程是操作系统调度的基本单位 下面未严格区分进程和线程
• 几个概念的粗略解释 – 任务：一般性的抽象术语，指由软件完成的一个 活动。例如，矩阵分块乘就是把矩阵乘分成多个 任务, 以便于在对称多处理器上并行执行这些任务 – 进程：任务在程序中的对应物，它有自己的数据 和代码，需要在处理器上运行直至结束。进程是 操作系统为其进行资源分配和调度的独立单位 – 线程：是把进程细分出现的实际运行单位，线程 是进程中一段顺序执行的语句序列。把进程分成 若干线程是为了提高进程执行过程中的并行性。 线程是操作系统调度的基本单位 – 下面未严格区分进程和线程 基 本 知 识 5
基本知识 ·几个概念的粗略解释 并行(parallet:多个可以同时执行的任务，在多处 理器上同时执行 B 并发(cuncorrent):多个可以同时执行的任务，在 单处理器上交错执行 A B 并发是逻辑上同时发生，而并行是逻辑上和物理 上都同时发生。下面不区分并行和并发
• 几个概念的粗略解释 – 并行(parallel): 多个可以同时执行的任务，在多处 理器上同时执行 – 并发(cuncorrent)：多个可以同时执行的任务，在 单处理器上交错执行 并发是逻辑上同时发生，而并行是逻辑上和物理 上都同时发生。下面不区分并行和并发 基 本 知 识 t A B t A B 6
基本知识 个高性能处理器 ·对称多处理器 可以集成在一块芯片 -对称多处理器的体系结构 上 处理器 处理器 处理器 处理器 一级 级 一级 缓存 缓 缓 缓存 二级 二级 缓存 缓存 爱 二级 缓存 总线 内存 7
• 对称多处理器 – 对称多处理器的体系结构 二级 缓存 内存 总线 二级 缓存 二级 缓存 二级 缓存 一级 缓存 一级 缓存 一级 缓存 一级 缓存 处理器 处理器 处理器 处理器 基 本 知 识 多个高性能处理器 可以集成在一块芯片 上 7
基本知识 单核结构与多核系统结构 CPU状态 CPU状态 CPU状态 中断逻辑 中断逻辑 中断逻辑 执行单元缓存 执行单元缓存 执行单元缓存 单核结构 多处理器结构 超线程技术充分利用执行 CPU状态 CPU状态 中断逻辑 中断逻辑 单元中的空闲资源，以便在 相同时间内完成更多工作 执行单元缓存 执行单元中的资源：内存 超线程结构 访问部件、算术运算部件和 浮点功能部件等
基 本 知 识 • 单核结构与多核系统结构 执行单元 缓存 CPU状态 中断逻辑 执行单元 缓存 CPU状态 中断逻辑 执行单元 缓存 CPU状态 中断逻辑 单核结构 多处理器结构 执行单元 缓存 CPU状态 中断逻辑 CPU状态 中断逻辑 超线程结构 超线程技术充分利用执行 单元中的空闲资源，以便在 相同时间内完成更多工作 执行单元中的资源：内存 访问部件、算术运算部件和 浮点功能部件等 8
基本知识 单核结构与多核系统结构 CPU状态 CPU状态 CPU状态 中断逻辑 中断逻辑 中断逻辑 执行单元缓存 执行单元缓存 执行单元缓存 单核结构 多处理器结构 超线程技术本质上就是多 CPU状态 CPU状态 个线程共享一个执行核 中断逻辑 中断逻辑 执行单元缓存 两套CPU状态+中断逻辑 是为了适应两个线程同时执 超线程结构 行的需要
基 本 知 识 • 单核结构与多核系统结构 执行单元 缓存 CPU状态 中断逻辑 执行单元 缓存 CPU状态 中断逻辑 执行单元 缓存 CPU状态 中断逻辑 单核结构 多处理器结构 执行单元 缓存 CPU状态 中断逻辑 CPU状态 中断逻辑 超线程结构 超线程技术本质上就是多 个线程共享一个执行核 两套CPU状态 +中断逻辑 是为了适应两个线程同时执 行的需要 9
基本知识 ·单核结构与多核系统结构 多核处理器是 CPU状态 CPU状态 把两个甚至更多 中断逻辑 中断逻辑 的独立执行核嵌 执行单元缓存 执行单元缓存 入到一个处理器 多核体系结构 的内部，每个线 程都有完整的硬 CPU状态 CPU状态 件执行环境，各 中断逻辑 中断逻辑 线程之间实现了 执行单元 执行单元 真正意义上的并 缓存 行 共享缓存的多核体系结构 10
基 本 知 识 • 单核结构与多核系统结构 共享缓存的多核体系结构 执行单元 缓存 CPU状态 中断逻辑 执行单元 缓存 CPU状态 中断逻辑 多核体系结构 执行单元 缓 存 CPU状态 中断逻辑 执行单元 CPU状态 中断逻辑 多核处理器是 把两个甚至更多 的独立执行核嵌 入到一个处理器 的内部，每个线 程都有完整的硬 件执行环境，各 线程之间实现了 真正意义上的并 行 10
基本知识 ·单核结构与多核系统结构 CPU状态 CPU状态 CPU状态 CPU状态 中断逻辑 中断逻辑 中断逻辑 中断逻辑 执行单元 缓存 执行单元 缓存 采用超线程技术的多核体系结构 体系结构越来越复杂，若这些复杂的特征都要反 映到编程语言中，才能写出较好利用体系结构优点 的程序，则编写程序将是很困难的工作 需要设计好的编程模型并通过编译器和操作系统 的帮助和支持来解决
基 本 知 识 • 单核结构与多核系统结构 体系结构越来越复杂，若这些复杂的特征都要反 映到编程语言中，才能写出较好利用体系结构优点 的程序，则编写程序将是很困难的工作 需要设计好的编程模型并通过编译器和操作系统 的帮助和支持来解决 采用超线程技术的多核体系结构 执行单元 缓存 CPU状态 中断逻辑 CPU状态 中断逻辑 执行单元 缓存 CPU状态 中断逻辑 CPU状态 中断逻辑 11