1、第第8 8章章 多核并发（并行）程序设计多核并发（并行）程序设计 主讲主讲:黎忠文黎忠文8.1 8.1 什么是多核并发什么是多核并发设计设计 并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。8.1 8.1 什么是多核并发什么是多核并发设计设计两个或多个独立运行的内核集成于同一
2、个处理器上面双核处理器=一个处理器上包含2个内核多核处理器=一个处理器上包含2个或多个内核8.1 8.1 什么是多核并发什么是多核并发设计设计8.1 8.1 什么是多核并发什么是多核并发设计设计8.1 8.1 什么是多核并发什么是多核并发设计设计 实现最优的价值实现最优的价值 缩减处理时间，提高计算能力缩减处理时间，提高计算能力 开发平台的新特性和新功能开发平台的新特性和新功能8.1 8.1 什么是多核并发什么是多核并发设计设计8.1 8.1 什么是多核并发什么是多核并发设计设计多核技术的发多核技术的发展展几种不同的技术几种不同的技术处理器上的某些资源会被共享使用相同的缓存和运算器共享系统总线
3、与双处理器的性能相同只共享系统总线，独立缓存高性能，资源冲突少8.1 8.1 什么是多核并发什么是多核并发设计设计8.1 8.1 什么是多核并发什么是多核并发设计设计不会发生资源冲突每个线程拥有自己的缓存、寄存器和运算器HT 使处理器的性能至少提升了1/3 双核的性能相当于2块 non-HT 处理器8.1 8.1 什么是多核并发什么是多核并发设计设计Single core,With HT(Eg.Pentium 4 Processor With HT)Integer and Floating Point ThreadsL2 Cache and ControlL2 Cache and Contro
4、l L1 D-Cache and D-TLBSchedulersIntegerTrace CacheRename/Allocuop QueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPoint2 threads can be executed at the same time(per processor)if theyre not competing for the same execution resource8.1 8.1 什么是多核并发什么是多核并发设计设计Single core,With HT(Eg.Pentium 4 Processor with
5、HT)Two Floating Point ThreadsL2 Cache and ControlL2 Cache and Control L1 D-Cache and D-TLBSchedulersIntegerTrace CacheRename/Allocuop QueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPoint2 threads CANNOT be executed at the same time(per processor)if theyre competing for the same execution resource(eg.2 f
6、loating point threads in a P4P architecture)8.1 8.1 什么是多核并发什么是多核并发设计设计Dual core,Without HT(Eg.Pentium D Processor)Two Floating Point ThreadsL2 Cache and ControlL2 Cache and Control L1 D-Cache and D-TLBSchedulersIntegerTrace CacheRename/Allocuop QueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointL2 Cach
7、e and ControlL2 Cache and Control L1 D-Cache and D-TLBSchedulersIntegerTrace CacheRename/Allocuop QueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointEven 2 floating pointthreads can be executedat the same time now(per processor)as there are multiple floating point execution units8.1 8.1 什么是多核并发什么是多核并发设
8、计设计Dual core,With HT(Eg.Dual Core Pentium Processor Extreme Edition)Supports HTMultiple Integer and Floating Point ThreadsL2 Cache and ControlL2 Cache and Control L1 D-Cache and D-TLBSchedulersIntegerTrace CacheRename/Allocuop QueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointL2 Cache and ControlL2 Ca
9、che and Control L1 D-Cache and D-TLBSchedulersIntegerTrace CacheRename/Allocuop QueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointWith dual core&HT together,maximum#of threads that can be executed at a time is 4 per processor多核技术与超线程技术的结合多核技术与超线程技术的结合Dual Core with Hyper-Threading4 threads/socket Dual
10、 Core2 threads/socket 8.1 8.1 什么是多核并发什么是多核并发设计设计AMDAMD与与IntelIntel双核架构双核架构的对比的对比 8.18.1 什么是多核并发什么是多核并发设计设计DualCoreDualCore、SMPSMP、ClusterCluster8.1 8.1 什么是多核并发什么是多核并发设计设计8.2 8.2 为什么要学习多核程序设计为什么要学习多核程序设计8.2 8.2 为什么要学习多核程序设计为什么要学习多核程序设计Back8.2 8.2 为什么要学习多核程序设计为什么要学习多核程序设计8.3 8.3 多核并发（并行）程序设计环境多核并发（并行）
11、程序设计环境 及开发方法及开发方法 按指令与数据分 按存储方式分8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法存储方式存储方式8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法.8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法8.3 8.3 多核并发（并行）程序设计环境及开发方法多核
12、并发（并行）程序设计环境及开发方法什么是什么是MPIMPI？是一个库而不是一门语言是一种标准或规范的代表而不特指某一个对它的具体实现是一种消息传递编程模型并成为这种编程模型的代表和事实上的标准对MPI的使用必须和特定的语言结合起来进行：C,JAVA,FORTRANC,JAVA,FORTRAN目前主要的目前主要的MPIMPI实现实现MPICH:http:/www-unix.mcs.anl.gov/mpi/mpichChimp:ftp:/ftp.epcc.ed.ac.uk/pub/packages/chimp/release/Lam :http:/www.mpi.nd.edu/lam/8.3 8.
13、3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法MPIMPI并行程序设计平台由并行程序设计平台由标准消息传递函数及相关标准消息传递函数及相关辅助函数辅助函数构成，多个进程通过调用这些函数（类构成，多个进程通过调用这些函数（类似调用子程序），进行通信；似调用子程序），进行通信；一个程序同时启动多份，形成多个独立的进程，一个程序同时启动多份，形成多个独立的进程，在不同的处理机上运行，拥有独立的内存空间，在不同的处理机上运行，拥有独立的内存空间，进程间通信通过调用进程间通信通过调用MPIMPI函数来实现；每个进函数来实现；每个进程程 开始执行时，将获得一个唯一的序号（
14、开始执行时，将获得一个唯一的序号（rankrank）。）。例如启动例如启动P P个进程，序号依次为个进程，序号依次为0 0，1 1，P-1P-1；MPI并行进程的实现8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法 消息传递是相对于进程间通信方式而言的，与具体并行机存储模式无关，任何支持进程间通信的并行机，均可支持消息传递并行程序设计；几乎有共享和分布存储并行计算环境均支持进程间的消息传递通信；进程0发送一个整数给进程1；进程1将该数加1，传递给进程2；进程2再将该数加1，再传递给进程3；依次类推，最后，进程N-1将该数传递给进程0，由进程1负责广播
15、该数给所有进程，并打印输出。进程 1传递信息进程 3传递信息进程 2传递信息进程 0传递信息8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法PCAMPCAM设计过程设计过程8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能
16、分解是一种更深层次的分解，是否合理？8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法通讯是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通讯则限制了这种并发性；8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法所有任务是否执行大致相当的通讯?是否尽可能的局部通讯？通讯操作是否能并行执行?同步任务的计算能否并行执行？8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环
17、境及开发方法组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯成本；保持映射和扩展的灵活性，降低软件工程成本；8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法增加粒度是否减少了通讯成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通讯？有没有减少并行执行的机会？8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方
18、法每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间 并发的任务 不同的处理器 任务之间存在高通讯的 同一处理器映射实际是一种权衡，属于NP完全问题8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法采用集中式负载平衡方案，是否存在通讯瓶颈？采用动态负载平衡方案，调度策略的成本如何？8.3 8.3 多核并发（并行）程序设计环境及开发方法多核并发（并行）程序设计环境及开发方法8.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP2400平
19、台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400
20、平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计IXP2400 IXP2400 网络处理器简介网络处理器简介 IXA 是用于Internet 数据交换设备的处理器系统结构，它使得Internet 设备由传统的固定协议、低效率走向具有软件升级功能的高效率可编程设备。IXP2400 是IXA 系统结构的一个具体处理器产品。其外部特性如下图 所示。8.4 IXP24008.4 IXP
21、2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计.Intel IXP2400 Intel IXP2400 网络处理器外部特性网络处理器外部特性 Scratchpad存储器 2个QDR SRAM控制器 1个DDR DRAM控制器IXP2400IXP2400典型系统结构典型系统结构8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计IXP2400IXP2400的典型模块系统结构的典型模块系统结构返回8.4 IXP24008.
22、4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计返回8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计 1个16K字节的板载便笺存储器（Scratchpad）1个DDR SDRAM控制器（最高支持1GB）2个独立的QDR SRAM控制器（每个控制器最高支持64MB）。8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计ixp2400ixp2400各级存储器对
23、照表各级存储器对照表返回8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设平台上多核程序并发（并行）设计计返回8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设平台上多核程序并发（并行）设计计便笺存储器便笺存储器（Scratchpad Memory）散列单元散列单元（Hash Unit）CAPCAP（CSR Access Proxy）返回8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计网络处理
24、器的技术特点网络处理器的技术特点8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计控制层面控制层面管理层面管理层面数据层面数据层面8.4.4 8.4.4 基于基于Intel IXPIntel IXP网络处理器的软件设计网络处理器的软件
25、设计包括慢速数据通道和快速数据通道。快速数据通道是由微引擎负责处理的数据转发通道，大部分数据包通过此通道完成处理与转发。慢速数据通道：由通用RISC核负责处理一些例外复杂的数据包，如数据包分段、带扩展头部的数据包处理等。处理各种通信协议。转发表和状态信息维护。安装配置接口。策略管理接口。系统管理、统计、计费。8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计MicroenginePipelineControl Plane Protocol StackControl Plane PDKCore ComponentsCore Component
26、 LibraryResource Manager LibraryMicroblock LibraryProtocol LibraryHardware Abstraction LibraryMicroblockMicroblockMicroblockUtility LibraryXScaleCoreMicroengineC Language/Assembly LanguageC/C+LanguageExternalProcessorsIXAIXA软件框架软件框架8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 I
27、XP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计如何实现线速处理？如何保持数据包的顺序？如何在多个线程间传递数据包的状态？如何实现数据互斥？如何隐藏存储器访问时延？如何对数据包进行排队？8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计IXP2400IXP2400处理过程举例处理过程举例SDH FramerDRAMSRAMMSFDRAMControllerDRAMControllerSRAMControllerSHaCMEMEMEMEME Cluster 0MEMEMEMEME Cluster 1XScaleIXP24001,1323124,1151067,8,98.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计8.4 IXP24008.4 IXP2400平台上多核程序并发（并行）设计平台上多核程序并发（并行）设计本讲小结 理解多核程序设计的基本原理 了解IXP2400平台上进行多核程序并发（并行）设计的过程
