多核平台下串行程序运行时的自动并行化加速方法

《多核平台下串行程序运行时的自动并行化加速方法》涉及的是一种计算机技术领域的方法，具体是一种多核平台下串行程序运行时的自动并行化加速方法。

1.一种多核平台下串行程序运行时的自动并行化加速方法，其特征在于，包括以下步骤：

第一步，建立一个共享读取的程序计数寄存器组SPC，该寄存器组中寄存器的个数与CPU核的数目相同，每个寄存器分别与对应的CPU核相连以实时地储存该CPU核的程序计数器值；

第二步，当存在空闲的CPU核时，进行加速对象选择处理，得到自动并行加速线程的加速对象为线程P；

第三步，当线程P存在已分析指令集合S_p时，载入该集合S_p；否则，为线程P新建一个集合S_p，对线程P所在的CPU核进行读取处理，得到线程P所在的CPU核当前正在读取的指令I_c，并由I_c追踪线程P下一条将要执行指令的地址，将追踪分析的指令代码和跳转关系加入集合S_p中；

第四步，采用第三步的方法，得到线程P将要执行的所有指令，当集合S_p中每次加入条件转移指令后且集合S_p中存在循环代码时，进行进度校验和替换处理；

第五步，当线程P被调度出CPU核时，系统以中断方式将该事件连同当时的SPC_p值发送给自动并行加速线程，当自动并行加速线程正在替换处理中时，则使用此时的SPC_p值作为读取I_c的依据，继续执行替换处理直到退出该步骤；否则，自动并行加速线程根据当时的SPC_p值读取I_c，清空或更新集合S_p，其结果等待线程P被调入时继续使用；

第六步，返回第二步，开始处理新的需要加速的线程。

2.根据权利要求1所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，第一步中所述的共享读取是：每个CPU核实时读取寄存器组中每个寄存器存储的其它CPU核的程序计数器值。

3.根据权利要求1所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，第二步中所述的加速对象选择处理，是：当正在运行且未被加速的用户线程中存在CPU占用率最高的线程时，则选择该线程作为自动并行加速线程的加速对象；否则，时间t后，再次选择正在运行且未被加速的用户线程中CPU占用率最高的线程作为自动并行加速线程的加速对象，直至得到自动并行加速线程的加速对象。

4.根据权利要求3所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，所述的时间t是系统的调度时间片大小。

5.根据权利要求1所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，第三步中所述的读取处理，是：读取线程P所在的CPU核的程序计数寄存器的值，将得到的虚拟地址转换为物理地址，然后从该物理地址得到线程P所在的CPU核正在执行的指令I_c，当集合S_p中包括指令I_c时，删除集合S_p中I_c以前的指令记录，并根据集合S_p追踪线程P下一条将要执行的指令；否则，清空集合S_p。

6.根据权利要求1所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，第四步中所述的进度校验，是：重新读取指令I_c，当指令I_c不在集合S_p中时，清空集合S_p，然后从指令I_c开始追踪；当指令I_c在集合S_p中、线程P走向该循环且线程P已经开始执行该循环，则选取循环接收后第一条语句作为待分析指令，并清空集合S_p；当指令I_c在集合S_p中、线程P走向该循环且线程P未执行该循环，则对该循环进行替换处理；当指令I_c在集合S_p中但线程P未走向该循环时，则删除集合S_p中I_c以前的指令记录，并继续追踪。

7.根据权利要求6所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，所述的替换处理，包括以下步骤：

1）当循环的总工作量大于阈值G时，生成并行化执行该循环的代码，执行该循环的代码出口语句跳转到原循环出口对应的语句，且将新生成的代码单独放在一个或若干个内存页中；否则，放弃替换该循环，并删除集合S_p中I_c以前的指令记录，继续追踪；

2）生成代码后，进行进度校验，当通过进度校验时则中断线程P，且中断线程P后再次进行校验，再次通过进度校验后，执行3）；否则，线程P继续运行；

3）将1）生成的代码所在的内存页分配给线程P，并修改原循环起始地址的二进制代码为跳转到新生成代码的起始位置，在集合S_p中删除原循环对应指令，加入新生成的代码指令；

4）替换完成后通知线程P继续执行，继续分析后续代码。

8.根据权利要求7所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，所述的阈值G是单个CPU核1秒钟执行的最大指令数。

9.根据权利要求7所述的多核平台下串行程序运行时的自动并行化加速方法，其特征是，所述的通过进度校验是指：指令I_c在集合S_p中、线程P走向该循环且线程P未执行该循环。

二十一世纪以来，随着芯片功耗的不断提升和芯片复杂度的不断提升，通过提升频率等方法来提高单核处理器的性能变得非常困难。单芯片多处理器（Chip Multiprocessor，即CMP）技术成为了新的发展热点。截至2010年8月，使用CMP技术的处理器已经占据了大部分市场，从大型商用机型，到普通桌面机，再到嵌入式系统，无论高端低端，CMP都成为了各领域处理器结构的必然选择。

然而CMP的使用并不是应用驱动的，它的出现主要是为了有效地利用新制造工艺带来的更多的晶体管。由于功耗和验证难度的限制，已经难以通过设计更复杂的单核来提升处理器的性能。与此同时传统的图灵机串行程序模型和串行地址空间结构并没有发生本质改变，原有的大量程序和许多新增的程序依然遵循传统的设计方法，导致串行化的程序并不能很好的利用2010年可并行执行的物理结构以提高性能。

2010年之前技术中采用传统的并行程序设计方法重写已有的程序，该方法好像非常简单，但是事实上并不可行。常用的并行化库和编译指令主要有OpenMP（共享存储并行设计的库）和MPI（消息传递并行编程环境）。它们一方面难于掌握：并行程序的设计与调试都比串行程序要困难很多；另一方面也不是特别适用于多核环境。由于编写单个并行程序代价就很高，要想把已有的各种应用程序都重写，实际上是不可能的。

经对2010年之前文献检索发现，中国专利申请号为：200510026587.4，名称为：用户指导的程序半自动并行化方法，该技术提出了一种使用较为简单的模型开发并行化程序，能减小开发并行程序的复杂度。但是，其使用范围有限而且仍然需要大量精力进行重新开发，不能很好地解决大量已有的串行程序的问题。

另外一种方法是对串行程序进行自动分析翻译，生成并行化程序，即线程级推测（ThreadLevel Speculation，即TLS）技术。使用该技术可以使用相应的自动并行化工具，通过对原有串行程序的源代码、中间代码或者二进制代码的分析，自动划分线程，并生成并行化代码。该方法虽然可以不用重写程序，但还是需要对原有的代码进行重新编译，这就要求用户有能力进行代码重新编译或者要求用户更换为已经重新编译的程序，这一要求在一般情况下是不成立的。同时，使用推测技术，虽然在一定程度上提高了并行度，但同时也增加了硬件设计的复杂度，并且在推测级数较多时推测成功率很低。

多核平台下串行程序运行时的自动并行化加速方法专利目的

《多核平台下串行程序运行时的自动并行化加速方法》的目的在于提供一种多核平台下串行程序运行时的自动并行化加速方法。该发明新增可共享读取的程序计数器寄存器组，并在操作系统中建立自动并行加速线程，选择一个线程作为加速的对象，然后实时地分析此线程将要执行到的指令代码，并对其中执行循环的指令代码进行修改，达到使被加速线程自动并行执行的目的。

多核平台下串行程序运行时的自动并行化加速方法技术方案

《多核平台下串行程序运行时的自动并行化加速方法》包括以下步骤：

第一步，建立一个共享读取的程序计数寄存器组SPC，该寄存器组中寄存器的个数与CPU核的数目相同，每个寄存器分别与对应的CPU核相连以实时地储存该CPU核的程序计数器值。

所述的共享读取是：每个CPU核实时读取寄存器组中每个寄存器存储的其它CPU核的程序计数器值。

第二步，当存在空闲的CPU核时，进行加速对象选择处理，得到自动并行加速线程的加速对象为线程P。

所述的加速对象选择处理，是：当正在运行且未被加速的用户线程中存在CPU占用率最高的线程时，则选择该线程作为自动并行加速线程的加速对象；否则，时间t后，再次选择正在运行且未被加速的用户线程中CPU占用率最高的线程作为自动并行加速线程的加速对象，直至得到自动并行加速线程的加速对象。

第三步，当线程P存在已分析指令集合S_p时，载入该集合S_p；否则，为线程P新建一个集合S_p，对线程P所在的CPU核进行读取处理，得到线程P所在的CPU核当前正在读取的指令I_c，并由I_c追踪线程P下一条将要执行指令的地址，将追踪分析的指令代码和跳转关系加入集合S_p中。

所述的读取处理，是：读取线程P所在的CPU核的程序计数寄存器的值，将得到的虚拟地址转换为物理地址，然后从该物理地址得到线程P所在的CPU核正在执行的指令I_c，当集合S_p中包括指令I_c时，删除集合S_p中I_c以前的指令记录，并根据集合S_p追踪线程P下一条将要执行的指令；否则，清空集合S_p。

第四步，采用第三步的方法，得到线程P将要执行的所有指令，当集合S_p中每次加入条件转移指令后且集合S_p中存在循环代码时，进行进度校验和替换处理。

所述的进度校验，是：重新读取指令I_c，当指令I_c不在集合S_p中时，清空集合S_p，然后从指令I_c开始追踪；当指令I_c在集合S_p中、线程P走向该循环且线程P已经开始执行该循环，则选取循环接收后第一条语句作为待分析指令，并清空集合S_p；当指令I_c在集合S_p中、线程P走向该循环且线程P未执行该循环，则对该循环进行替换处理；当指令I_c在集合S_p中但线程P未走向该循环时，则删除集合S_p中I_c以前的指令记录，并继续追踪。

所述的替换处理，包括以下步骤：

1）当循环的总工作量大于阈值G时，生成并行化执行该循环的代码，执行该循环的代码出口语句跳转到原循环出口对应的语句，且将新生成的代码单独放在一个或若干个内存页中；否则，放弃替换该循环，并删除集合S_p中I_c以前的指令记录，继续追踪；

2）生成代码后，进行进度校验，当通过进度校验时则中断线程P，且中断线程P后再次进行校验，再次通过进度校验后，执行3）；否则，线程P继续运行；

3）将1）生成的代码所在的内存页分配给线程P，并修改原循环起始地址的二进制代码为跳转到新生成代码的起始位置，在集合S_p中删除原循环对应指令，加入新生成的代码指令；

4）替换完成后通知线程P继续执行，继续分析后续代码。

所述的通过进度校验是指：指令I_c在集合S_p中、线程P走向该循环且线程P未执行该循环。

第五步，当线程P被调度出CPU核时，系统以中断方式将该事件连同当时的SPC_p值发送给自动并行加速线程，当自动并行加速线程正在替换处理中时，则使用此时的SPC_p值作为读取I_c的依据，继续执行替换处理直到退出该步骤；否则，自动并行加速线程根据当时的SPC_p值读取I_c，清空或更新集合S_p，其结果等待线程P被调入时继续使用。

第六步，返回第二步，开始处理新的需要加速的线程。

多核平台下串行程序运行时的自动并行化加速方法改善效果

与2010年之前的技术相比，《多核平台下串行程序运行时的自动并行化加速方法》的有益效果是：2010年之前的技术使用不方便，需要重新开发程序或者重新编译原来的代码，而该发明在运行时对程序进行自动并行，不用对已有程序进行预先的处理，整个过程由操作系统完成，对于用户完全透明。该发明能够在有空闲的CPU核时自动利用空闲资源对程序进行并行加速，免去等待预先处理程序的时间，也省去用户手动转换程序的麻烦。

实施例

该实施例包括以下步骤：

第一步，建立一个共享读取的程序计数寄存器组SPC，该寄存器组中寄存器的个数与CPU核的数目相同，每个寄存器分别与对应的CPU核相连以实时地储存该CPU核的程序计数器值。

所述的共享读取是：每个CPU核实时读取寄存器组中每个寄存器存储的其它CPU核的程序计数器值。

第二步，当存在空闲的CPU核时，进行加速对象选择处理，得到自动并行加速线程的加速对象为线程P。

所述的加速对象选择处理，是：当正在运行且未被加速的用户线程中存在CPU占用率最高的线程时，则选择该线程作为自动并行加速线程的加速对象；否则，时间t后，再次选择正在运行且未被加速的用户线程中CPU占用率最高的线程作为自动并行加速线程的加速对象，直至得到自动并行加速线程的加速对象。

所述的时间t是系统的调度时间片大小，该实施例为20毫秒。

第三步，当线程P存在已分析指令集合S_p时，载入该集合S_p；否则，为线程P新建一个集合S_p，对线程P所在的CPU核进行读取处理，得到线程P所在的CPU核当前正在读取的指令I_c，并由I_c追踪线程P下一条将要执行指令的地址，将追踪分析的指令代码和跳转关系加入集合S_p中。

所述的读取处理，是：读取线程P所在的CPU核的程序计数寄存器的值，将得到的虚拟地址转换为物理地址，然后从该物理地址得到线程P所在的CPU核正在执行的指令I_c，当集合S_p中包括指令I_c时，删除集合S_p中I_c以前的指令记录，并根据集合S_p追踪线程P下一条将要执行的指令；否则，清空集合S_p。

第四步，采用第三步的方法，得到线程P将要执行的所有指令，当集合S_p中每次加入条件转移指令后且集合S_p中存在循环代码时，进行进度校验和替换处理。

所述的进度校验，是：重新读取指令I_c，当指令I_c不在集合S_p中时，清空集合S_p，然后从指令I_c开始追踪；当指令I_c在集合S_p中、线程P走向该循环且线程P已经开始执行该循环，则选取循环接收后第一条语句作为待分析指令，并清空集合S_p；当指令I_c在集合S_p中、线程P走向该循环且线程P未执行该循环，则对该循环进行替换处理；当指令I_c在集合S_p中但线程P未走向该循环时，则删除集合S_p中I_c以前的指令记录，并继续追踪。

所述的替换处理，包括以下步骤：

1）当循环的总工作量大于阈值G时，生成并行化执行该循环的代码，执行该循环的代码出口语句跳转到原循环出口对应的语句，且将新生成的代码单独放在一个或若干个内存页中；否则，放弃替换该循环，并删除集合S_p中I_c以前的指令记录，继续追踪；

2）生成代码后，进行进度校验，当通过进度校验时则中断线程P，且中断线程P后再次进行校验，再次通过进度校验后，执行3）；否则，线程P继续运行；

3）将1）生成的代码所在的内存页分配给线程P，并修改原循环起始地址的二进制代码为跳转到新生成代码的起始位置，在集合S_p中删除原循环对应指令，加入新生成的代码指令；

4）替换完成后通知线程P继续执行，继续分析后续代码。

所述的阈值G是单个CPU核1秒钟执行的最大指令数。

所述的通过进度校验是指：指令I_c在集合S_p中、线程P走向该循环且线程P未执行该循环。

第五步，当线程P被调度出CPU核时，系统以中断方式将该事件连同当时的SPC_p值发送给自动并行加速线程，当自动并行加速线程正在替换处理中时，则使用此时的SPC_p值作为读取I_c的依据，继续执行替换处理直到退出该步骤；否则，自动并行加速线程根据当时的SPC_p值读取I_c，清空或更新集合S_p，其结果等待线程P被调入时继续使用。

第六步，返回第二步，开始处理新的需要加速的线程。

该实施例方法实现简单，且完全由操作系统完成；能够在有空闲的CPU核时自动利用空闲资源对程序进行并行加速，免去等待预先处理程序的时间，从而大大提高了多核平台下串行程序运行时的并行处理速度。

2020年7月14日，《多核平台下串行程序运行时的自动并行化加速方法》获得第二十一届中国专利奖优秀奖。

在计算机中，数据传输的方式有两种，一种就是串行通讯，每个字符的二进制位按位排列进行传输，速度慢，但传输距离相对较远，鼠标口和USB口都是串行端口；另一种是并行通讯，每个字符的二进制位使用多条数据线同时进行传输，传输速度相对要快些，但传输距离相对不能太远，计算机内部数据传输一般都是采用这种方法，标准打印口是属并行端口。

简单地说，串行ATA （Serial ATA）是一种采用连续串行数据传输方式的硬盘接口新标准，作为新一代的接口规范，它有望替代我们所用的并行ATA接口。

我们所见到的内置硬盘、CD-ROM、DVD-ROM、刻录机等IDE设备，采用的大多是并行ATA（Parallel ATA）接口，包括常见的Ultra ATA/33/66/100以及最新的Ultra ATA/133标准。几年来，随着硬盘设计和制造技术的不断进步，在外部接口数据传输率提升的同时，硬盘的内部数据传输率也在不断提高。采用ATA-3接口的昆腾FireBall EL六代硬盘的内部传输率仅为20MB/s；而采用ATA-4接口的迈拓钻石十代（DiamondMax Plus 40）硬盘则提高到43.02MB/s；采用ATA-5接口的希捷酷鱼ATA Ⅳ硬盘，更是高达69.3MB/s。从硬盘性能的提升速度来看，在2001年如果还没有新型IDE硬盘接口推出，将会出现一个危险区，即硬盘的内部数据传输率会超过外部接口所能支持的最大数据传输率.

即使不考虑硬盘内部数据传输率，单就硬盘的接口数据传输率而言，其技术潜力也是非常有限的。自ATA/66起硬盘的接口电缆也一直没有变化过，都是采用40针80芯的。随着并行ATA接口的不断提速，电缆之间的电磁干扰越来越严重，硬盘数据信号在高速传输中的信号串扰制约着接口速度的提升。在40针80芯并行电缆上的速度极限到底有多大？硬盘业内专家普遍认为大约是200MB/s。这还只是理论上的极限值，由于损耗的原因实际上能够达到的接口速度只有理论值的70%左右，外部数据传输率成为硬盘速度瓶颈的那一天很可能会更早到来。

硬件厂商当然不会坐等这一天的到来而无所作为，他们的解决办法就是推出新的串行ATA（Serial ATA）规范。串行ATA最早是在2000年秋季的Intel开发者论坛上（IDF Fall 2000）提出的，一年多后的IDF Fall 2001上，“串行ATA工作组”正式确立了Serial ATA 1.0标准。2100433B

1988年,美国国防分析研究所（IDA）以武器生产为背景, 对传统的生产模式进行了分析,首次系统化地提出了并行工程的概念。几年来，并行工程在美国及西方许多国家十分盛行，已成为制造自动化的一个热点。

90年代是信息时代，更确切地说是知识的时代。大量新知识的产生，促使新知识的应用的更迭周期越来越短，技术的发展越来越快。如何利用这些技术提供的可能性，抓住用户心理，加速新产品的构思及概念的形成，并以最短的时间开发出高质量及价格能被用户接受的产品，已成为市场竞争的焦点。而这一焦点的核心是产品的上市时间。并行工程作为加速新产品开发过程的综合手段迅速获得了推广，并行工程已成为90年代制造企业在竞争中赢得生存和发展的重要手段。

并行工程是集成地、并行地设计产品及相关过程, 包括制造过程和支持过程的系统化方法。这种方法要求开发人员在设计一开始就考虑产品整个生命周期从概念形成到产品报废处理的所有因素，包括质量、成本、进度计划和用户要求，而不是已经做到哪一步，再考虑下一步怎么走。

传统的产品开发模式为功能部门制，信息共享存在障碍；串行的流程，设计早期不能全面考虑产品生命周期中的各种因素；以基于图纸的手工设计为主，设计表达存在二义性，缺少先进的计算机平台，不足以支持协同化产品开发。全球化大市场的形成，要求企业必须改变经营策略：提高产品开发能力、增强市场开拓能力，但传统的产品开发模式已不能满足激烈的市场竞争要求，因而提出了并行工程的思想。并行工程是一种企业组织、管理和运行的先进设计、制造模式；是采用多学科团队和并行过程的集成化产品开发模式。它把传统的制造技术与计算机技术、系统工程技术和自动化技术相结合，在产品开发的早期阶段全面考虑产品生命周期中的各种因素，力争使产品开发能够一次获得成功。从而缩短产品开发周期、提高产品质量、降低产品成本、增强市场竞争能力。一些著名的企业通过实施并行工程取得了显著效益，如波音(Boeing)、洛克希德(Lockheed)、雷诺(Renauld)、通用电力(GE)等。

传统产品开发过程信息流向单一、固定，以信息集成为特征的CIMS可以支持、满足这种产品开发模式的需求。并行产品的设计过程是并发式的，信息流向是多方向的。只有支持过程集成的CIMS才能满足并行产品开发的需求。

并行工程具有以下特点：

●强调团队工作（Team work）精神和工作方式；

●强调设计过程的并行性；

●强调设计过程的系统性；

●强调设计过程的快速“短”反馈；

利用并行工程对改造传统产业有重要作用，并将对提高中国企业新产品开发能力、增强其竞争力具有深远的意义。