《并行计算与多线程技术》课件

并行计算与多线程技术本课程将深入探讨并行计算和多线程技术的理论和实践，为学生提供扎实的理论基础和实用的编程技能，帮助他们掌握现代计算机系统的高效利用方法课程大纲并行计算基础多线程编程性能优化实际应用案例探讨并行计算的定义、发介绍多线程的概念、线程深入分析并行程序的性能通过案例分析，展示并行展历史、必要性、性能指基本操作、同步机制、死优化策略，包括原子操作计算和多线程技术在排序标等基础知识，以及锁问题、线程池技术，以、无锁编程、OpenMP、算法、矩阵运算、图算法Amdahl定律和Gustafson及内存模型和缓存一致性MPI、CUDA等技术，以及、优化算法等领域的应用定律的应用等关键概念数据并行、任务并行等模式什么是并行计算？1并行计算是指将一个计算2与串行计算相比，并行计问题分解成多个子问题，算利用多个处理器同时执并由多个处理器同时执行行任务，可以显著提高计，以加速计算过程算速度，尤其适用于大规模数据处理、实时计算等场景3并行计算技术的发展得益于计算机硬件的进步，例如多核处理器、GPU、超级计算机等，以及并行编程语言和框架的不断完善并行计算的发展历史11960s早期超级计算机如CDC6600的出现，标志着并行计算的萌芽这些机器采用流水线技术，将任务分解成多个步骤，由不同的处理单元并行执行21980s向量处理器技术的成熟，例如Cray-1超级计算机，可以对向量数据进行快速处理，进一步提高并行计算效率32000s多核处理器技术日益普及，使得并行计算应用更加广泛，例如个人电脑、服务器等设备都配备了多核处理器现代发展趋势随着云计算、大数据、人工智能等技术的快速发展4，并行计算技术不断革新，例如GPU加速计算、分布式计算等，为解决更复杂的问题提供支持并行计算的必要性单核性能提升瓶颈功耗墙问题随着芯片工艺的不断发展，单核性能提升的速度逐渐放缓，难随着芯片的集成度不断提高，功耗问题日益突出，为了降低功以满足日益增长的计算需求耗，提高能效比，多核处理器成为一种重要选择大规模数据处理需求实时计算要求在科学计算、数据挖掘、机器学习等领域，需要处理海量数据在金融交易、自动驾驶、游戏等实时性要求高的领域，并行计，并行计算可以有效提高数据处理速度算可以确保及时完成计算任务并行系统硬件架构共享内存系统中，多个处分布式内存系统中，每个NUMA架构结合了共享内理器共享同一个内存空间处理器拥有独立的内存空存和分布式内存的优点，，可以方便地进行数据交间，数据交换需要通过消每个处理器拥有自己的本换和访问，但存在竞争问息传递，通信开销较大，地内存，同时也可以访问题，需要使用同步机制来但可扩展性更高其他处理器的内存，但访协调访问问速度差异较大GPU计算架构是专门为并行计算设计的，拥有大量并行计算单元，可以有效加速图形渲染、机器学习等计算密集型任务分类法FlynnSIMDSISD单指令流多数据流，同一指令同时作用单指令流单数据流，典型的串行计算模于多个数据，适用于向量处理、图像处12型，例如传统单核处理器理等任务，例如向量处理器、GPUMIMD43MISD多指令流多数据流，多个处理器同时执多指令流单数据流，多个指令同时作用行不同的指令，适用于通用并行计算，于同一数据，目前应用较少例如多核处理器、分布式系统并行计算性能指标加速比衡量并行计算的速度提升幅度，定义为并行执行时间与串行执行时间的比值效率衡量并行计算资源的利用率，定义为加速比与处理器数量的比值可扩展性衡量并行计算系统随着处理器数量增加的性能提升能力负载均衡衡量并行计算任务分配的均匀程度，目的是使每个处理器拥有相同的工作量，以最大限度地发挥并行计算的优势定律AmdahlAmdahl定律描述了并行计算中可获得的性能提升上限，该上限取决于可并行化部分的比例公式Speedup=1/f+1-f/N，其中f为不可并行化的部分比例，N为处理器数量理论限制即使处理器数量无限增加，加速比也无法超过1/f，这意味着不可并行化的部分会限制并行计算的性能提升实际应用Amdahl定律可以帮助我们分析并行算法的可行性和效率，引导我们设计高效的并行算法计算示例假设一个程序中50%的部分可以并行化，使用4个处理器执行，理论上的加速比为1/

0.5+

0.5/4=

1.67定律Gustafson与Amdahl定律不同，Gustafson定律侧重于固定时间内，随着处理器数量增加可以完成1的任务规模实际应用场景适用于大型科学计算、数据挖掘等场景，这些场景往往需要随2着计算资源的增加来处理更大的数据规模可扩展性分析Gustafson定律认为，随着处理器数量的增加，可并行3化的部分比例也会增加，因此加速比可以接近线性增长性能预测Gustafson定律可以帮助我们估计随着处理器数量4增加，并行计算系统可以完成的计算规模并行算法设计方法任务分解1将原始问题分解成多个独立或相互依赖的子问题，每个子问题可以由不同的处理器独立执行负载均衡2合理分配任务到不同的处理器，确保每个处理器都拥有相同的工作量，以最大限度地发挥并行计算的优势通信开销3在并行计算中，处理器之间需要进行数据交换，通信开销会影响整体性能，需要尽量减少通信次数和数据量同步策略4在并行计算中，不同处理器可能需要进行同步操作，例如等待其他处理器完成任务，需要选择合适的同步机制来协调工作什么是多线程？线程进程线程是进程中的一个执行单元，可以理解为轻量级的进程，多个线程可以共享同一个进程的资源，例如内存空间、文件等多线程编程可以让一个程序同时执行多个任务，提高程序效率线程的基本操作1创建线程使用线程库提供的函数创建线程，例如pthread_create，传递线程函数和参数2终止线程线程可以使用pthread_exit函数主动退出，或者在执行完线程函数后自动退出3线程join使用pthread_join函数等待线程执行完毕，并获取线程的返回值4线程detach使用pthread_detach函数分离线程，使其独立运行，不再需要等待线程执行完毕线程状态转换线程的状态转换取决于线程的执行情况，例如创建线程后处于新建状态，等待调度处于就绪状态，获得CPU资源处于运行状态，等待某个事件处于阻塞状态，执行完毕或异常退出处于终止状态线程同步基础临界区互斥量信号量条件变量临界区是指一段代码，多个互斥量是一个二元信号量，信号量是一个计数器，可以条件变量是一个用来通知线线程可能需要访问同一共享它可以控制对共享资源的访用来控制多个线程对共享资程某个条件是否满足的机制资源，需要确保同一时间只问，保证同一时间只有一个源的访问，可以设定信号量，可以与互斥量配合使用，有一个线程访问该资源，以线程可以持有互斥量，从而的最大值，当信号量值为0实现复杂的线程同步避免数据不一致保证临界区的互斥访问时，线程会被阻塞，直到信号量值大于0互斥锁详解mutex基本操作递归锁超时锁共享锁互斥锁的常用操作包括加递归锁允许同一个线程多超时锁可以设定锁的等待共享锁允许多个线程同时锁、解锁、初始化、销毁次加锁，适用于递归函数时间，如果在等待时间内读取共享资源，但只允许等，例如中对共享资源的访问，但无法获取锁，则返回错误一个线程写入，适用于读pthread_mutex_lock、需要注意防止死锁，适用于需要控制等待时多写少的场景pthread_mutex_unlock间的场景、pthread_mutex_init、pthread_mutex_destroy读写锁1读写锁是一种特殊的锁机制，2读优先读写锁在读取共享资源3写优先读写锁在写入共享资源它可以同时允许多个线程进行时优先级更高，写操作需要等时优先级更高，读操作需要等读操作，但只允许一个线程进待所有读操作结束后才能进行待写操作结束后才能进行，适行写操作，适用于读操作远多于写操作用于写操作频率更高的场景的场景4读写锁的实现机制依赖于操作系统或线程库提供的5读写锁的应用场景包括数据库系统、缓存系统、文机制，例如pthread_rwlock_t类型件系统等，可以有效提高系统性能条件变量详解虚假唤醒wait/notify机制条件变量的notify函数可能在条件条件变量使用wait函数等待某个条未满足的情况下唤醒等待线程，这1件满足，使用notify函数通知其他种现象称为虚假唤醒，需要使用循2线程某个条件已满足环来验证条件是否满足实现示例生产者消费者模式使用pthread_cond_t类型来创建条条件变量可以用来实现经典的生产4件变量，使用pthread_cond_wait者消费者模式，生产者线程将数据3函数等待条件满足，使用放入缓冲区，消费者线程从缓冲区pthread_cond_signal函数通知其获取数据，条件变量可以用来协调他线程生产者和消费者线程的工作死锁问题死锁产生条件1死锁是指多个线程相互等待对方释放资源，导致所有线程都无法继续执行的情况，产生死锁需要满足四个必要条件互斥、占有和等待、不可剥夺、循环等待预防策略2预防死锁的方法包括破坏互斥条件、破坏占有和等待条件、破坏不可剥夺条件、破坏循环等待条件检测方法3检测死锁的方法可以通过资源分配图分析，判断是否存在循环等待，或者使用操作系统提供的死锁检测工具恢复机制4恢复死锁的方法包括撤销进程、抢占资源、回滚操作等，需要选择合适的恢复机制，尽量减少损失线程池技术线程池原理线程池是一种管理线程的机制，可以预先创建一定数量的线程，并根据需要分配任务给这些线程，避免频繁创建和销毁线程，提高程序效率核心参数配置线程池的核心参数包括线程池大小、任务队列大小、拒绝策略等，需要根据应用场景进行合理的配置任务调度策略线程池可以使用不同的任务调度策略，例如FIFO、LIFO、优先级调度等，可以根据任务的优先级进行调度性能优化可以通过调整线程池参数、选择合适的调度策略、优化任务执行时间等方法来提高线程池性能内存模型顺序一致性可见性原子性内存屏障顺序一致性是指所有处理可见性是指一个处理器对原子性是指一个操作不可内存屏障是一种指令，它器看到事件发生的顺序一共享内存的修改能够被其分割，要么全部完成，要可以强制处理器对内存进致，即使事件发生的顺序他处理器及时看到，需要么全部不完成，例如在多行刷新，保证内存操作的不同，每个处理器看到的使用同步机制来保证可见线程环境中，对共享内存可见性和顺序性最终结果都是一致的性的读写操作需要保证原子性缓存一致性MESI协议MESI协议是一种常用的缓存一致性协议，它定义了缓存行状态，例如Modified、Exclusive、Shared、Invalid，可以保证多个处理器对同一缓存行的修改一致伪共享伪共享是指多个处理器访问同一个缓存行中的不同数据，导致不必要的缓存行失效，影响性能缓存行对齐为了避免伪共享，可以使用缓存行对齐，将数据分配到不同的缓存行，避免多个处理器竞争同一个缓存行性能影响缓存一致性协议可以保证数据的一致性，但也会引入一定的性能开销，例如缓存行失效、同步操作等原子操作原子类型是一种数据类型比较交换（CAS）操作是内存序可以控制内存操作，它提供了一系列原子操一种原子操作，它可以比的执行顺序，保证操作的作，例如加减、比较交换较内存中的值与期望的值可见性和顺序性，例如、读写等，可以保证操作，如果相等，则将内存中Release、Acquire、的原子性，避免数据竞争的值替换为新值，否则不SequentiallyConsistent做任何操作等内存序原子操作的实现机制依赖于硬件指令，例如x86平台的LOCK前缀指令，可以保证操作的原子性无锁编程1无锁编程是指在多线程环境中2无锁队列是一种不使用锁的队3无锁栈是一种不使用锁的栈实，不使用锁机制来保证数据的列实现方式，它使用原子操作现方式，它使用原子操作来进一致性，而是通过原子操作和来进行数据插入和删除，避免行数据入栈和出栈，避免了锁内存屏障来实现同步了锁的竞争，提高了性能的竞争，提高了性能4ABA问题是指一个值被修改两次，然后恢复到初始5内存回收是指在无锁编程中，需要处理内存回收问值，无锁编程需要处理ABA问题，可以使用版本号题，例如使用引用计数机制来管理内存机制来解决OpenMP基础编程模型1OpenMP是一种用于共享内存并行计算的编程模型，它通过指令和运行时库来实现并行化指令系统2OpenMP提供了一套指令，用于指定并行区域、数据共享、同步机制等，例如#pragma ompparallel、#pragma ompfor、#pragma ompcritical运行时库3OpenMP提供了一个运行时库，用于管理线程、分配任务、同步操作等，例如omp_get_thread_num、omp_get_num_threads、环境变量omp_set_num_threads4OpenMP可以使用环境变量来配置运行时环境，例如OMP_NUM_THREADS、OMP_SCHEDULE、OMP_NESTED等并行区域OpenMP使用#pragma ompparallel指令指定并行区域，该区域内的代码将被多个线程并行执行数据共享属性在并行区域中，可以指定数据的共享属性，例如private、shared、firstprivate等，用于控制数据在多个线程之间的可见性调度策略可以指定任务的调度策略，例如static、dynamic、guided等，用于控制任务分配到不同线程的方式嵌套并行OpenMP支持嵌套并行，可以将多个并行区域嵌套使用，以实现更复杂的并行计算OpenMP任务划分OpenMP提供了一系列指令，可以将循环语句、代码块、任务等并行化，实现不同粒度的并行计算OpenMP同步机制1critical指令critical指令可以指定临界区，确保同一时间只有一个线程执行临界区内的代码，以避免数据竞争2atomic指令atomic指令可以指定原子操作，例如加减、比较交换等，确保操作的原子性，避免数据竞争3barrier指令barrier指令可以创建一个同步点，所有线程都必须到达同步点后才能继续执行，用于协调多个线程的执行4ordered指令ordered指令可以指定有序执行，确保循环语句中迭代的执行顺序一致基础MPI消息传递模型通信模式进程管理环境初始化MPI（Message PassingMPI支持点对点通信和集MPI使用进程来管理并行使用MPI_Init函数初始化Interface）是一种用于分体通信两种模式，点对点计算中的处理器，每个处MPI环境，使用布式内存并行计算的编程通信是指两个处理器之间理器对应一个MPI进程，MPI_Finalize函数关闭模型，它通过消息传递机的通信，集体通信是指多MPI进程可以通过通信来MPI环境，制来实现处理器之间的通个处理器之间的通信交换数据MPI_Comm_rank函数获信取当前进程的编号，MPI_Comm_size函数获取MPI进程的数量点对点通信MPI1阻塞通信是指发送或接收消息的进程会阻塞，直到通信完成，例如MPI_Send、MPI_Recv函数2非阻塞通信是指发送或接收消息的进程不会阻塞，而是立即返回，例如MPI_Isend、MPI_Irecv函数，需要使用MPI_Wait函数等待通信完成3缓冲区管理MPI需要使用缓冲区来存放通信数据，需要选择合适的缓冲区大小，避免数据溢出4通信模式MPI支持同步通信和异步通信，同步通信要求发送方和接收方同时执行通信操作，异步通信则不要求集体通信MPI广播广播操作是指将一个处理器的数据广播到其他所有处理器，例如MPI_Bcast函数归约归约操作是指对多个处理器的数据进行聚合运算，例如MPI_Reduce函数，可以进行求和、求最大值、求最小值等操作散射/收集散射操作是指将一个处理器的数据分散到其他所有处理器，收集操作是指将多个处理器的数据收集到一个处理器，例如MPI_Scatter、MPI_Gather函数全局操作全局操作是指对所有处理器的数据进行操作，例如MPI_Allreduce函数，可以进行全局求和、全局求最大值等操作CUDA编程模型线程层次结构CUDA使用线程层次结构来管理并行计算中的线程，包括线程块、线程组、线程等，可以实现不同粒度的并行计算内存层次结构CUDA提供了一套内存层次结构，包括全局内存、共享内存、常量内存、纹理内存，可以根据数据访问模式选择合适的内存类型核函数核函数是CUDA程序中执行在GPU上的函数，核函数可以被多个线程并行执行，实现并行计算同步机制CUDA提供了一系列同步机制，例如__syncthreads、cudaDeviceSynchronize，用于协调不同线程的执行，保证数据的一致性内存管理CUDA全局内存是GPU上最大共享内存是每个线程块常量内存是每个线程块的内存空间，可以被所中的一个内存空间，可中的一个内存空间，用有线程访问，但访问速以被线程块中的所有线于存储常量数据，访问度较慢，适用于存储大程访问，访问速度快，速度快，可以被所有线型数据集适用于存储线程之间需程访问，但需要在编译要共享的数据时指定常量数据纹理内存是专门用于存储纹理数据的内存空间，访问速度快，可以被所有线程访问，适用于图形渲染等场景CUDA性能优化内存访问模式1优化内存访问模式，例如使用合并访问、减少内存访问次数、使用缓存等方法，可以提高程序性能线程分配策略2选择合适的线程分配策略，例如使用线程块、线程组等，可以充分利用GPU的并行计算能力并行规约3使用并行规约算法，例如并行求和、并行求最大值等，可以有效提高程序性能指令级优化4使用指令级优化，例如循环展开、指令重排序等，可以提高程序性能数据并行模式向量化操作数据分区负载均衡通信优化将对单个数据的操作扩展将数据分成多个部分，每确保每个处理器拥有相同减少处理器之间通信的次到对多个数据的操作，例个处理器处理一部分数据的工作量，避免一个处理数和数据量，例如使用合如将对单个数组元素的操，例如将矩阵分成多个子器过载，而其他处理器空并通信、使用非阻塞通信作扩展到对整个数组的操矩阵，每个处理器处理一闲等方法作个子矩阵任务并行模式1将一个任务分解成多个子任务，每个子任务可以由不同2任务调度将子任务分配到不同的处理器，并协调子任的处理器执行，例如将排序问题分解成多个子排序问题务的执行顺序，例如使用工作窃取算法来分配任务3负载均衡确保每个处理器拥有相同的工作量，避免一4同步开销任务并行模式需要进行同步操作，例如等待个处理器过载，而其他处理器空闲其他处理器完成任务，需要尽量减少同步操作的次数流水线并行流水线设计阶段划分将一个任务分成多个阶段，每个阶将任务分成多个独立的阶段，每个1段由不同的处理器执行，每个处理阶段处理一个子任务，例如将图像2器处理一个阶段的任务，实现流水处理任务分成预处理、特征提取、线式的执行方式分类等阶段性能分析负载均衡4分析流水线并行模式的性能，例如确保每个阶段的处理器拥有相同的3计算吞吐量、延迟等指标，评估流工作量，避免一个阶段的处理器过水线并行模式的效率载，而其他阶段的处理器空闲分治并行问题分解1将一个问题分解成多个规模更小的子问题，每个子问题可以递归地分解，直到子问题足够小，可以直接解决结果合并2将子问题的解合并成原始问题的解，例如使用归并排序算法合并子排序结果递归并行3使用递归的方式，将子问题分配到不同的处理器，并行地解决子问题，最终合并结果性能优化4通过优化问题分解、结果合并、递归并行等步骤，可以提高分治并行算法的效率并行排序算法并行快速排序并行归并排序样本排序性能比较并行快速排序算法通过将数并行归并排序算法通过将数样本排序算法通过将数据分不同并行排序算法的性能取据分成多个部分，每个处理据分成多个部分，每个处理成多个样本，每个处理器排决于数据规模、处理器数量器并行排序一个部分，然后器并行排序一个部分，然后序一个样本，然后将样本排、数据分布等因素，需要根合并排序结果使用归并算法将排序结果合序结果合并成最终排序结果据实际情况选择合适的算法并并行矩阵运算矩阵乘法LU分解Cholesky分解性能优化并行矩阵乘法可以通过将并行LU分解可以通过将矩并行Cholesky分解可以通可以通过优化数据分区、矩阵分成多个子矩阵，每阵分成多个部分，每个处过将矩阵分成多个部分，通信模式、内存访问等方个处理器并行计算一个子理器并行计算一部分的LU每个处理器并行计算一部法，提高并行矩阵运算的矩阵的乘积，然后将结果分解，然后将结果合并分的Cholesky分解，然后性能合并将结果合并并行图算法最短路径1并行最短路径算法可以通过将图分成多个部分，每个处理器并行计算一个部分的最短路径，然后将结果合并最小生成树2并行最小生成树算法可以通过将图分成多个部分，每个处理器并行计算一个部分的最小生成树，然后将结果合并图着色3并行图着色算法可以通过将图分成多个部分，每个处理器并行对一个部分进行着色，然后将结果合并PageRank4并行PageRank算法可以通过将网页分成多个部分，每个处理器并行计算一个部分的PageRank值，然后将结果合并并行优化算法遗传算法并行遗传算法可以通过将种群分成多个子种群，每个处理器并行进化一个子种群，然后将结果合并粒子群优化并行粒子群优化算法可以通过将粒子分成多个子群，每个处理器并行优化一个子群，然后将结果合并蚁群算法并行蚁群算法可以通过将蚂蚁分成多个子群，每个处理器并行模拟一个子群的行动，然后将结果合并神经网络并行神经网络算法可以通过将神经网络分成多个层，每个处理器并行计算一层，然后将结果合并负载均衡策略静态负载均衡1在程序开始前，根据预先设定的规则分配任务，例如将任务平均分配到每个处理器动态负载均衡2在程序运行过程中，根据实际情况调整任务分配，例如将任务分配到负载较低的处理器任务迁移3将任务从一个处理器迁移到另一个处理器，以平衡负载，例如使用工作窃取算法来迁移任务性能监控4监控每个处理器的负载情况，及时调整任务分配，以保证负载均衡容错机制检查点恢复定期保存程序状态，当发生故障时，可以从保存的状态恢复程序执行，例如使用检查点机制来保存程序状态复制容错将程序复制到多个处理器上运行，当一个处理器发生故障时，其他处理器可以继续执行程序，例如使用多副本机制来实现复制容错错误检测检测程序运行过程中出现的错误，例如使用校验和、奇偶校验等方法来检测错误故障恢复当出现故障时，恢复程序的执行，例如使用错误恢复机制来恢复程序执行性能分析工具12性能计数器分析器使用使用操作系统提供的性能计数器来统计程序运行过程中的各种指标，例如CPU使用率使用性能分析工具来分析程序的性能瓶颈，例如使用Valgrind、Gprof等工具、内存使用率、缓存命中率等34瓶颈识别优化建议分析性能计数器和分析工具的结果，找出程序性能瓶颈，例如CPU密集、内存密集、根据性能瓶颈分析结果，给出相应的优化建议，例如优化算法、数据结构、内存访通信开销等问等性能调优方法热点分析内存优化通信优化负载均衡优化分析程序的执行热点，找优化内存访问模式，例如优化处理器之间的通信，优化任务分配，例如使用出程序中最耗时的部分，使用缓存、减少内存访问例如使用合并通信、使用动态负载均衡、任务迁移例如使用性能分析工具来次数、使用内存池等方法非阻塞通信、减少通信次等方法分析程序的执行热点数等方法并行程序调试调试工具常见问题12使用并行程序调试工具来帮助调试并行程序，例如使用并行程序调试中常见的错误包括数据竞争、死锁、同GDB、TotalView、Allinea DDT等工具步问题、通信错误等调试策略案例分析34并行程序调试需要使用特殊的调试策略，例如使用多线通过案例分析，讲解并行程序调试的常见问题和调试策程调试器、使用日志记录、使用断点等略，帮助学生掌握并行程序调试的方法高性能计算平台超级计算机超级计算机是世界上性能最强大的计算机系统，拥有大量的处理器和高速互连网络，可以解决科学计算、大数据处理等复杂问题计算集群计算集群是由多个服务器组成的系统，可以提供高性能计算能力，例如用于科学计算、数据库处理、网站服务等云计算平台云计算平台提供按需使用的高性能计算资源，例如亚马逊的EC

2、谷歌的ComputeEngine等，可以根据需要动态调整计算资源GPU集群GPU集群是使用多个GPU组成的系统，可以提供高性能计算能力，例如用于机器学习、深度学习、图形渲染等分布式系统分布式系统是指由多个独立的计算机系统组成的系统，这些计算机系统通过网络连接在一起，共同完成一个任务分布式系统的设计需要考虑架构设计、通信机制、一致性问题、容错机制等因素。