基于Cilk_的遗传算法并行化改造实现

网络新媒体技术

Vol.1No.5Sep.2012

基于Cilk++的遗传算法并行化改造实现

杨川杨斌（西南交通大学信息科学与技术学院成都610031）

摘要：遗传算法是模拟生物进化过程的一种计算模型，在同一代种群间进行基因的选择、交叉和变异时，具有良好的并行性。遗传算法在实际的应用中，选取的种群数目往往比较大，处理的数据量巨大，因此算法性能比较低。目前，处理器已经进入多核时代，但传统的程序还是基于单核编写，程序性能并没有随着处理器数目增加而增加。因此，通过对遗传算法进行并行化改造，使得算法能够充分利用多核处理器资源，算法的性能大大提升。并行遗传算法的实现，符合未来多核程序设计的发展方向，有利于遗传算法更广泛的运用。cilk，关键词：遗传算法，并行化

ParallelizationofGeneticAlgorithmBasedonCilkTechnology

YANGChuan，YANGBin

（SchoolofinformationScience＆Technology，SouthwestJiaotongUniversityChengdu，G10031，China）

Abstract：Geneticalgorithm（GA）isacomputationalmodelwhichisdesignedtosimulatebiologicalevolution.Whendoinggeneticselec-tion，crossoverandmutationatthesamegeneration，GAhasgoodparallelism.

Inpractice，thenumberofpopulationsisoftenrelatively

largeandhugeamountofdatawillbeprocessed，sotheperformanceofthealgorithmisrelativelylow.Currently，CPUhasenteredthetimeofmulticore.However，thetraditionalprogramiswrittenbasedonsingle－core.Simultaneously，Programperformancedidnotin-creasewiththenumberofprocessors.Therefore，throughParallelizationofGeneticAlgorithm，itmakesthealgorithmtotakefulladvan-tageofmulti－coreprocessorandgreatlyenhancestheperformanceofthealgorithm.Parallelgeneticalgorithmisinlinewiththefuturedirectionofdevelopmentofmulticoreprogramming，whichisconducivetomoreextensiveuseofgeneticalgorithm.Keyword：GeneticAlgorithm，cilk，Parallelization

1

1.1

背景介绍

遗传算法

遗传算法是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导

个体），即种群。这里每一个学习和确定搜索的方向。遗传算法的操作对象是一群二进制串（称为染色体、

染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。

由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，

GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。

本文于2012－02－20收到。

5期1.2

Cilk技术

杨川等：基于Cilk++的遗传算法并行化改造实现55

Cilk是在C语言上的扩展，Cilk来简化多核并行化开发过程，从而更好的发挥多核处理器的硬件性能。非常适合，但不局限于分治算法。其核心思想是将问题分解为能够独立执行的若干小任务，然后将小任务的结果进行合并，得到问题的最终结果。递归函数在分治算法广泛应用，Cilk对其有良好的支持。能够并行执行的任务可以是函数，也可以是循环体。Cilk++的关键字可以自动识别能够并行化的函数调用或循环体。Cilk实时系统可以有效的调度这些任务到当前空闲的处理器。Cilk++使用工作线程（Worker）代表操作系统线程，其数量与处理器的数目相同（对于支持超线程的处理器，一个处理器将具有两

Cilk调度器使用该线程来执行任务。个工作线程），在Cilk程序中，

2Cilk技术的执行模型

首先，通过描述一个有向连通图（DAG）来说明Cilk++程序的串行/并行结构，有向连通图（DAG）不依赖

于处理器的具体数量。执行模型描述实时调度器如何将可并行执行单元（strand）映射成若干个工作线程的。随着多核处理器的普及，不同的可并行执行单元可以并行的执行。然而，在Cilk程序中，可并行执行单元可以被并行执行，但不是一定要并行执行。Cilk的调度器会动态地改变策略。这种策略类似于任务秘取调度（work－stealingscheduler），调度器会周期地检测各个处理器的负载情况，以便得到当前空闲处理器。例如双核CPU，它拥有2个硬件线程（同时有2个线程并行化执行），当Cilk调度器分配任务时，它首先会将整个任务分配给一个硬件线程，如果某时第2个硬件线程空闲，则第2个硬件线程会“窃取”第1个任务线程的一半任务进行处理，就这样一层一层地密取，最终使多个任务能够并行化完成。如图1所示，假设Cilk代码段：

图1Cilk原理代码

如图2所示，该代码用有向图可以表示为

图2cilk实现原理

如果cilk调度器中存在大于1个工作线程，这段程序可能有两种方法执行：

整个程序执行在一个工作线程中；

调度器将可并行执行单元2和3调度到不同的工作线程上；为了确保程序顺序执行，考虑程序在单核情况下的执行模型，可并行执行的任务（执行节点3与主函数（执行节点4）应该是同一个线程中，因此，在cilk调度器中，在初始状态时，执行节点1和3必须在同一同一工作线程中。当调度器在进行处理器负载均衡的检测中，发现有一个工作线程空闲时，这时通

56网络新媒体技术2012年

过任务秘取机制，该线程会获取部分执行节点3的任务，即执行节点2，从此可并行化任务开始并行执行。

图3程序在单工作线程上的执行过程

图4程序在有空闲工作线程上的执行过程

如图3所示，程序在单个工作线程上的执行与传统串行版本的程序完全相同，虽然任务在A点也被划分成为执行节点2和3两个部分，但由于没有空闲的工作线程节点2也只能在节点3完成后才能执行，最后在B点完成结果的合并，结束可并行执行的区域。如图4所示，如果系统中出现一个空闲工作线程，从A点开始，可并行任务被划分到执行节点2和3，并调度到不同的工作线程并行执行，执行完成后，两者在B点完成同步（所谓同步，就是保证所有并行的工作线程运行结束后，才进入下一步操作）。值得注意的是，在并行

下一步的任务（即执行节点4）理论上可以在执行节点2或3所在的工作线任务完成同步和结果的合并后，

程上继续执行，但cilk调度器为了更充分的利用程序执行的上下文环境，将会在最先前的工作线程上继续执

行，即执行节点1和3所在的工作线程。

3遗传算法并行化改造的设计

通过对遗传算法的学习，在进行并行化改造之前，首先设计遗传算法的串行执行版本，其流程图如图5所示。算法第一步主要进行一些初始化工作，主要是种群信息和遗传代数目，种群信息通过输入的20组基因数据（每一组为基因变化的上下界，数值在1到1000之间）和配置的种群数量动态生成，同时还需要设置最大遗传代数、基因数目、基因交叉概率和编译概率；第二步，使用遗传算法对第一代种群进行处理，并选出及保存第一代中的最优个体，同时保留中间结果到文件；第三步，对上一代种群中个体的基因进行筛选，形成新的种群并对新种群的基因不断交叉和突变，并将当前种群的最优个体和上一代种群最优个体进行比筛选出最优个体，这样反复迭代，直到种群的遗传代达到最大遗传代，最后得到最优个体。较，

图5遗传算法串行程序流程图

图6串行版本程序并行化程度分析

5期杨川等：基于Cilk++的遗传算法并行化改造实现57

如图6所示，通过ParallelStudio对串行程序进行并行化程度分析，可以发现程序的大量运行时间花在种群个体筛选（select函数）和基因变异（mutate函数），因此对这部分进行并行化改造，可以大大提高程序性能。另外，通过对遗传算法分析，个体筛选和基因变异都是对当前遗传代种群中个体的单独处理，与前后遗对其进行并行化改造是安全的。因此，对遗传算法的并行化改传代和种群中其他个体之间没有迭代关系，造，就是对当前种群个体的筛选和基因变异并行化执行。

图7遗传算法并行化改造设计

如图7所示，遗传算法并行化改造设计流程图，实验环境采用IntelQ8200四核处理器，即工作线程数目为4。执行节点1主要实现种群信息和相关参数的初始化；当程序运行到A点，即对当前种群中个体进行筛选和基因变异处理，进入并行执行环境，所有的任务在开始时全部被调度到n1工作线程上，在理想情况下，n3和n4此时另外3个工作线程应该处于空闲状态（视操作系统的不同负载情况而有所不同），工作线程n2、会秘取n1的任务，从而实现任务的并行化执行；在B点（同步点），待所有工作线程运行结束，将各个线程的结果进行合并，再进入执行节点4。

4

4.1

遗传算法并行化的实现

遗传算法并行化改造流程

第一，通过intelparallelstudio性能分析软件，对传统非并行程序进行性能分析，找出程序的运行瓶颈和存

在并行化改造的地方，同时记录程序的运行的各个中间结果，便于比较。第二，结合Cilk并行化技术的特点，对

进行并行化优化。第三，通过intelparallelstudio中的inspector检测软件，对并行程序中存在的可并行化部分，

化后程序中存在的数据竞争和死锁进行检测和修复，确保程序的并行化版本和非并行化版本的结果（包括中间分析并行化程序的性能提升。结果）的完全一致性。第四，4.2

遗传算法并行化改造方法

cilk_sync、grainsize、reducer_opadd、__cilkrts_get_在进行并行化改造的过程中，主要使用到了cilk_for、nworkers（）等cilk技术。通过遗传算法并行化改造的设计可知，并行化改造的核心工作就是要实现在当前

种群中对个体筛选和基因突变的并行化化执行。4.2.1

个体筛选函数（select）的并行化改造如图8所示，该代码为并行化改造的最重要代码，采用cilk_for对程序中的for循环进行并行化改造。代

码中的#pragma是一条编译指导语句grainsize=POPSIZE/__cilkrts_get_nworkers（）－100，实现了对系统粒度值得设置，所谓粒度值就是最小的任务大小，系统通过它来划分任务，划分的过程采用二分法，即不断的将任务折半，直到任务的大小小于或等于粒度值。其中__cilkrts_get_nworkers（）用来获取当前的工作线程的数

在这里粒度没有按照系统实际拥有的工作线程数目平均分配，而是比这个平均值稍微小一点，这是因为量，

58网络新媒体技术2012年

多线程在并行执行一个任务时，其结束时间可能会不同，这就造成了执行速度快的线程会等待执行速度慢的线程。为了解决这个问题，我们适当多分出一点任务，让执行较快的线程通过任务密取来执行这部分任务，从而减少等待时间，更充分利用CPU。

对于循环体的并行化，该循环为一个二重循环，如果对内层循环采用cilk_for，这样会产生大量的子任务，过多的子任务会造成大量的开销，这样的开销远远大于并行化后带来的性能提升，因此这样做会造成程序的执行速度甚至比非并行程序还要慢，因此在外层循环中使用cilk_for，减少子任务数量，同时具有较好的并行性，有利于提高程序的运行效率。这样的设计就是将种群划分为若干较小种群，然后在各个较小种群中，并行地进行个体的筛选操作，从而达到并行化的改造效果。

图8个体筛选函数（select）的并行化改造

4.2.2

基因突变函数（mutate）的并行化改造

如图9所示，对于基因突变操作，首先定义了函数randval来实现个体的基因突变操作，具体算法在输入

的基因上下界中产生一个随机值，来代替原有基因。同时，在选择种群某个个体的某个基因进行基因突变时，采用随机概率小于变异概率的操作，实现了选择的随机性。在并行化的改造过程中，由4.2.1的经验可得，应该对循环体外层进行并行化改造，这样的设计就是将种群划分为若干较小种群，然后在各个较小种群中，并行地进行基因突变操作，从而达到并行化的改造效果。

图9基因突变函数（mutate）的并行化改造

4.2.3

工作线程结果的合并

在实现任务并行执行后，必须对并行化执行的各个工作线程的运行结果进行合并，才能得到完整的最

在cilk中，使用reducer进行结果的合并操作。终运行结果，

如图10所示，首先定义reducer_opadd类型的变量，该变量用来存储各个线程的私有结果，其次，定义reducer中合并操作，这里合并可以加、减、乘和除等运算，最后将reducer_opadd类型的变量赋值给返回值，

5期杨川等：基于Cilk++的遗传算法并行化改造实现59

程序的其他部分可通过返回值来访问并行算法的最后结果。

图10工作线程结果的合并

4.34.3.1

性能分析

程序运行结果分析

图11非并行程序运行结果图12并行程序运行结果

分析：程序运行的中间结果较多，在这里无法给出，具体可参照程序中的galog.txt文件。由于遗传算法中采用很多随机概率来决定交叉和变异的概率，同时加上浮点数运算，因此中间结果会有一定误差。但遗传算法的目的，是最终筛选出最优良的个体，只要保证并行化程序最后筛选出的结果与非并行程序相同，就可以说明并行化算法的正确性。如图11和图12可知，两者的结果均为764227.247，完全一致（注：由于浮可能在运行的过程中并行与非并行程序的结果会有一定的误差，这样的误差很小，点数计算有一定的误差，是可以接受的），因此可以认为并行化算法是正确的。

4.3.2

程序时间结果分析

图13并行化程序的执行时间

图14非并行化程序的执行时间

分析：如图13和图14可知：并行化程序的执行时间约为7.19s，而非并行程序的执行时间为30.25s，因

60网络新媒体技术2012年

此程序的效率提升约为30.25/7.19=4.2倍。4.3.3程序执行中的性能分析

图15非并行程序CPU使用情况图16并行程序CPU使用

ElapsedTime代表程序的整个运行时间，分析：如图16所示，比前面的算法执行时间略长；CPUTime代

表使用CPU的总时间（对于单线程的程序而言，该时间等于使用一个CPU的时间，而对于多线程并行执行的程序，该时间等于使用各个CPU的时间总和）；WaitTime和WaitCount分别代表CPU等待的时间和次数；CoreCount代表CPU拥有的核心数目；ThreadsCreated代表程序运行的过程中创建的线程数目。非并行程序在执行的过程中，由于没有使用多核，因此在程序的整个执行过程中，仅仅创建了一个线程，因此CPU核数平均为1.00，因此其运行的时间较长；而并行化程序，其执行的过程中采用并行的方式，产生了5个线程，其中最开始在主函数中执行时，产生了1个线程，在并行化执行的部分，开启了4个线程来执行。由于存在非并行化的部分，因此并行化程序使用CPU核数平均为3.08，而不是理想情况下4，从CPUtime可以看出，程序总体使用CPU的时间为24.781s，由于是同时使用4个CPU核心，因此程序的运行时间取决于最后结束线程的时间，这样把CPU的运行时间同时分配到多个CPU核心上，大大提高了CPU的利用率，是整个程序的执行效率大大提高。

参

［2］张军.计算智能［M］.北京：清华出版社，2009，45－66

［3］英特尔网络软件学院.Cilk－Programmers－Guide.http：//software.intel.com/en－us/articles/intel－parallel－studio－home.

［电子文献］

［4］英特尔软件学院教材编写组.多核多线程技术［M］.上海：上海交通大学出版社，2011：12－88

［5］Guang－IenCheng，MingdongFeng，CharlesE.Leiserson，KeithH.Randall，andAndrewF.Stark.Detectingdataracesincilk

programsthatuselocks.InProceedingsoftheTenthAnnualACMSymposiumonParallelAlgorithmsandArchitectures（SPAA’98）［C］，pages298–309，PuertoVallarta，Mexico，June28–July21998.

［6］AnneDinningandEdithSchonberg.Anempiricalcomparisonofmonitoringalgorithmsforaccessanomalydetection.InProceed-ingsoftheSecondACMSIGPLANSymposiumonPrinciples＆PracticeofParallelProgramming（PPoPP）［C］，ACMPress，1990．pages1–10

考

文

献

［1］戴文华.基于遗传算法的文本分类及聚类研究［M］.北京：科学出版社，2008，10－55

作者简介

（1989－），杨川，男，硕士研究生，主要研究方向为多核并行化、嵌入式系统开发。（1956－），杨斌，男，硕士，教授，主要研究方向为计算机系结构、嵌入式系统。