串行算法并行化处理

542232023

参考：第二届“数学中国杯”数学建模网络挑战赛

承  诺  书  

我们仔细阅读了第二届“数学中国杯”数学建模网络挑战赛的竞赛规则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们允许数学中国网站(www.madio.net)公布论文，以供网友之间学习交流，数学中国网站以非商业目的的论文交流不需要提前取得我们的同意。

       我们的参赛报名号为：1143

参赛队员  (签名) ：

                            队员1：

              队员2：

队员3：

    参赛队教练员 (签名)：

    参赛队伍组别：大学组

第二届“数学中国杯”数学建模网络挑战赛

编 号 专 用 页

参赛队伍的参赛号码：（请各个参赛队提前填写好）：1143







竞赛统一编号（由竞赛组委会送至评委团前编号）：
















竞赛评阅编号（由竞赛评委团评阅前进行编号）：

2009年 第二届“数学中国杯”

数学建模网络挑战赛

题    目     串行算法的并行化处理        
  关 键 词   负载均衡模型 重建分解模型 算法优化模型 语句分解模版         

摘       要

随着台式机和笔记本电脑已广泛地采用了双核或多核CPU，将串行程序转化为并行程序将使得CPU能够尽量发挥双核或多核心的计算能力。那么就是需要将串行算法的并行化处理使得两个或多个核心的运算量基本相同，但是并不是任意的串行程序都可以转化为并行程序。

本文通过建立模型对前阶段的串行算法并行化处理模型给以检验，加入负载均衡模型达到检验的目的，经过检验发现该分解模型尚未考虑到负载均衡的问题，以及尚未考虑到源程序可能是使用了多种算法编写，分解方法也可能有适用范围的限制。本文通过重建分解模型即是对前阶段的分解模型给予优化，使得一个任务虽然可能能够分解到两个核心上分别处理，也能较好地达到负载均衡的要求。建立算法优化模型使得即使是由多种算法编写的源程序也可以很好的按照算法模版将源程序分解，按照语句分解模版得到的子程序在负载均衡模型下将子程序合理分配到两个核中，实现串行算法的并行化处理。

参赛密码 （由组委会填写）

参赛队号   1143         

所选题目    A题        

英文摘要（选填）

（此摘要非论文必须部分，选填可加分，加分不超过论文总分的5%）

With the desktop and notebook computers have been widely used in the dual-core or multi-core CPU, the serial process into a parallel program will allow the CPU to make full use of dual-core or multi-core computing power. Well, the serial algorithm is the need for parallel processing of two or more core makes the computation is basically the same as, but not any of the serial programs can be translated into parallel programs.
In this paper, the model through the establishment of the former stage of the serial processing model in parallel algorithm given test model by adding load balancing to achieve the purpose of testing, after testing revealed that the decomposition of the model has yet to take into account the problem of load balancing, and has yet to take into account the source may be prepared using a variety of algorithms, decomposition methods may also be restrictions on the scope of application. Decomposition model of this paper is the reconstruction of the former stage of the decomposition given optimization model, although the possibility of a task may be decomposed into two separate processing cores, but also achieve better load balancing requirements.
Model-building algorithm allows a variety of algorithms, even if prepared by the source can also be a good template to the source code in accordance with the decomposition algorithm, decomposition of the template to be in accordance with the statement of the subroutine in the load balancing model will be reasonably assigned to the subroutine two nuclear , the realization of serial parallel processing algorithm.

一、     问题重述

随着台式机和笔记本电脑已广泛地采用了双核或多核CPU，将串行程序转化为并行程序将使得CPU能够尽量发挥双核或多核心的计算能力。那么就是需要将串行算法的并行化处理使得两个或多个核心的运算量基本相同。能够将一个常规的串行程序分解成两个部分，使之能够在CPU 的两个核心上并行运算，并且希望能够尽量发挥双核心的计算能力。一般来说，如果两个核心的运算量基本相当，那么总的运算效率较高。如果出现某个核心空闲等待的状态，双核CPU 的运算力就没有被充分的利用起来。

问题： 在合理划分任务的前提下，双核处理器比单核处理器的运算效能要高。在算法级别上的划分，主要目的是进行数据的划分，以及顺序执行和循环的分解。分解的方法也就是第一阶段问题的目的。一个任务虽然可能能够分解到两个核心上分别处理，但不一定能较好地达到负载均衡的要求。由于算法的种类极多，所以分解方法也可能有适用范围的限制。请建立合理的模型，对你们设计的分解方法的效果作出评价，并根据你的评价，有针对性地对分解方法作出优化。

    注：解决这类问题，按照软件行业的要求，最终产品本应是一个代码预处理器，就是可以把源代码进行分解的计算机程序。但完成本问题不需要进行编程，也不需要考虑语法分析等详细的问题。只需要在算法的层面上进行分析，给出确切的分析方法和模型即可。

二、问题分析

本组前阶段提出的串行算法的并行化算法的优势在于[1]：①可以较准确的识别出串行程序的可并行部分，特别是对与顺序结构和循环结构有较好识别效果；②对于程序的可并行部分文章的算法是从外向内递归的分层标记，所以我们的识别是较深入的，这样就充分的利用了CPU资源；③如果我们的算法对串行程序识别错误而导致了内存读写冲突，算法将执行回朔到原始状态后顺序执行，这样保证了程序的结果正确性。
但是该模型只是在算法级别上的划分，主要目的是进行数据的划分，以及顺序执行和循环的分解。但是一个任务虽然可能能够分解到两个核心上分别处理，但不一定能较好地达到负载均衡的要求。由于算法的种类极多，所以分解方法也可能有适用范围的限制。所以本文将建立模型，对前阶段的设计的分解方法的效果作出评价，并对分解方法作出优化处理。

三、模型假设

1．假设串行算法用类C语言写成的，代码里只有顺序执行、分支、循环三种结构。

2．假设代码中只有整型以及整型数组，并且不需要调用已有的库函数。

3．假设程序中只有简单的代数运算，赋值运算，条件分支语句（if-else 语句），循

环语句（while 语句）。

4. 代码在并行化处理后运行结果与串行算法运行结果相同；

四、符号说明

η：CPU负载均衡效率，指某个期间内核的负载平衡效率；

m：指CPU的个数；

：指在该期间内第i个CPU执行完程序花费的时间（在该CPU上运行的并行子程序的时间之和）；

t1,t2......tn：划分出来的并行子程序各自运行时间；

n1，2，3:一个程序包含的基本语句，if...else语句，while语句的条数；

pi(i=1,2......n2):if...else语句中包含基本语句的条数；

qi(i=1,2......n3):while语句中包含基本语句的条数；

Nj(j=1,2......n3):while语句中包含基本语句的条数；

Δt: 每个基本语句的执行时间

U: 划分出来的并行子程序各自运行时间的集合即U=﹛t1,t2......tn﹜

V1：集合 中一元素 ，使 的集合

V2:在集合 中取一元素 ，使  的集合

S1，S2:V1，V2元素中之和；

Δη：1与负载平衡效率 的差.

B1：B2……Bn :1－n中算法建立分解的语句模版

β：源程序分解后得到的子程序个数;

Bj,k: 源程序分解的程序段.

五、负载评价模型建立与求解

本文所做的负载均衡是有条件的负载均衡。在预处理器对源程序扫描后，发现该源程序为简单的程序，则不再进行下一步的并行化处理等，而是随机分配到一个空闲的核中运行。因为如果不这样做，而是对所有的源程序都进行负载均衡处理，则有可能会增加处理时间，例如对简单的源程序就会这样。

所以这里的均衡处理将不再用于简单的、满足可并行化处理的源程序。这里做的负载均衡将用于非上述的源程序。

一、负载均衡模型[2]

前阶段我们讨论了如何将一个程序划分为若干个程序段的模型，算法将串行程序划分成了具有一定相关性但可独立执行的若干子程序，但是因为并行模型中的子程序段个数不确定，如果是2个子程序段，那就直接将其分别放到不同的CPU中进行执行即可；但若是n个子程序段，那么我们就考虑如何组合这n个独立的子程序段，使其分为两个计算量尽量相当的程序段，放入到双核CPU中独立运行，使其达到负载均衡。





在我们的问题中，因为是双核运算，那么如果两个核心的运算量基本相当，那么CPU总的运算效率最大，负载均衡效率达到1。
对于并行计算的CPU执行，CPU1执行一个程序段花费的时间为 ，CPU2执行另外一个程序段花费的时间为 ，则有
时，负载平衡效率 达到最大为1。
那么如何使其尽量接近呢？我们可以假设划分出来的并行子程序各自运行的时间 ；

<SPAN style="FONT-SIZE: 12pt; mso-hansi-font-family: 宋体">这里对于划分出来的并行子程序各自运行时间 的估算我们需要说明如下：