本节简要回顾与本文相关的一些过程挖掘概念，更详细的内容可以参考文献[1, 6, 14]。在过程挖掘问题中，过程模型往往被建模为工作流网。工作流网属于一种特殊的Petri网，称为库所(Place)/变迁(Transition)网(P/T网)，其定义如下：

定义 1 (P/T网)^[6]：P/T网表示为一个三元组$N = (P, T, F)$，其中：

1)  $P$是库所的有穷集合；

2)  $T$是变迁的有穷集合，满足$P \cap T = \emptyset $且$P \cup T \ne \emptyset $；

3)  $F = (P \times T) \cup (T \times P)$是有向弧的集合，称为流关系。

定义 2 (工作流网)^[6]：令$N = (P, T, F)$为P/T网，$t'$为不属于$P \cup T$的新结点，$N$是工作流网当且仅当：

1) $N$有两个特殊的库所$i$和$o$，其中$i$称为开始库所，$o$称为结束库所，即$\cdot i = \emptyset $，$ o \cdot = \emptyset $；

2) $N' = (P, {\rm{ }}T \cup \{ t'\} , {\rm{ }}F \cup \{ (t', {\rm{ }}i), (o, {\rm{ }}t')\} )$是强连通的。

定义2中的符号$\cdot i$和$o \cdot $分别表示结点$i$的前驱结点和结点$o$的后继结点。图 1给出了一个采用工作流网表示的过程模型，其中圆圈表示库所，方框表示变迁(变迁对应了过程挖掘问题中的任务)，方框内的字母表示任务的编号。

图  1  过程模型示例

过程挖掘的目标是从事件日志中发现过程模型，下面给出事件轨迹和事件日志的定义。

定义 3 (事件轨迹、事件日志)^[6]：令$T$为任务集合，${T^*}$为由$T$中任务构成的有限序列的集合，$\sigma \in {T^*}$是一个事件轨迹，$W \subseteq {T^*}$称为一个事件日志。

需要说明的是，一个事件日志中包含了若干个事件轨迹，每一个事件轨迹对应业务过程中的一个实际的执行案例。以到医院门诊看病为例，网上预约挂号$ \to $现场取号$ \to $医生看病$ \to $化验$ \to $医生确诊开药$ \to $取药，就是一个案例，这个案例生成的所有实际业务执行的过程记录就是事件轨迹。图 1的过程模型中包含了4个事件轨迹：{ABH，ACH，ADEFGH，ADFEGH}。

遗传过程挖掘算法将过程模型表示为因果矩阵，通过遗传搜索，最终发现适应度最高的因果矩阵作为算法输出。因果矩阵可以按照一定的规则转换为P/T网。因果矩阵的定义如下。

定义 4 (因果矩阵)^[9]：因果矩阵表示为一个四元组${\rm{CM}} = (T, C, I, O)$，其中：

1)  $T$表示所有任务的有穷集合；

2)  $C \subseteq T \times T$是因果关系的有限集；

3)  $I:T \to I(T)$为输入映射函数，$\forall t \in T$，$I(t) = \{ t'\left| {(t', t) \in C} \right.\} $；

4)  $O:T \to O(T)$为输出映射函数，$\forall t \in T$，$O(t) = \{ t'\left| {(t, t') \in C} \right.\} $。

图 1中的过程模型，其对应的因果矩阵的集合表示如表 1所示。其中$I(A) = \{ {\rm{ }}\} $表示任务$A$的输入为空集；$O(A) = \{ \{ B, C, D\} \} $表示任务$A$的输出为任务$B, C, D$，并且$B, C, D$之间为选择关系。$O(D) = \{ \{ E\} , \{ F\} \} $表示$D$的后继为$E, F$，但是$E, F$之间为并行关系。换句话说，子集内部的元素之间为选择关系，子集与子集之间为并行关系。

本节先简要回顾CUDA编程模型，然后再介绍CUDA程序设计优化的几个关键点。

在CUDA编程模型中，程序被分为两个部分，分别是主机端(Host)和设备端(Device)^[15]。Host端是指在CPU上执行的程序，Device端是指在GPU上执行的并行程序。Device端程序又被称为内核函数(kernel)。Nvidia GPU采用了一种层次化的方式对线程进行组织管理。首先，线程是指令执行的最小单位；32个线程组成一个线程束(warp)。warp是线程调度的最小单位。同一warp中的线程，采用单指令多线程(single instruction multiple threads, SIMT)的模式执行。其次，若干个warp被组织成一个线程块(block)。同一block中的线程会在相同的流多处理器上执行，因此同一block中的线程能够通过共享存储器(shared memory)进行通信和同步。最后，若干个block被组织成一个网格(grid)。CUDA程序每次启动kernel时都需要创建一个grid。

在进行CUDA程序设计优化时，有以下4点需要注意^[16]：1) CUDA程序需要启动足够多的线程以隐藏指令延迟，以提升GPU的利用率；2)共享内存的带宽远远高于全局内存，因此充分利用共享内存能够大幅提升CUDA程序的性能；3)同一warp中线程的指令执行采用的是SIMT模式，因此要尽量避免分支；4)由于GPU和主机内存之间进行数据传输依靠的是PCI-E总线，数据传输的效率非常低，因此在进行CUDA程序设计时要尽量减少数据传输。

本文提出的并行遗传过程挖掘框架如下所示。

Host端算法流程如下：

1)  在CPU上初始化种群，并按照3.2节中介绍的方法对因果矩阵进行染色体编码。因果矩阵的随机初始化方法仍然采用文献[9]中的方法。

2)  将事件日志、初始化的种群、相关参数拷贝到GPU的全局内存；

3)  启动kernel进行并行遗传挖掘；

4)  等待Device端程序执行完毕。将当前最优染色体的适应度值拷贝回Host端，判断是否满足算法结束条件。如果满足，则跳转到步骤5)；否则跳转到步骤3)；

5)  Host端算法结束。

Device端算法(kernel)流程如下：

1)  各线程从当前种群中随机选择一个个体；

2)  采用3.3节方法进行并行遗传交叉；

3)  采用3.4节方法进行并行遗传变异；

4)  采用3.5节方法对所有个体的适应度进行计算和排序，并保留其中的精英；

5)  Device端算法结束。

文献[10]中采用二进制方式进行染色体编码，因果矩阵按行组合形成一个染色体。这种编码方案的缺陷是无法反映过程模型中的AND-Split/ AND-Join和OR-Split/OR-Join关系。举例来说，假设因果矩阵某一行的值为[0 1 1 0 1]，5个位置分别对应任务A~E。此时算法将无法判定B，C，E之间是并行关系还是选择关系(如{{B, C, E}}，{{B, C}, {E}}，{{B}, {C}, {E}}等等)。文献[9]采用集合方式进行编码，能够有效表示过程模型，但目前集合编码还难以在GPU上实现。

针对以上问题，本文提出一种新的实数编码方案。该方案中，因果矩阵由集合内容(chromosome)、集合标识(set label)和集合位置(set position)3个数组共同表示。为了便于说明，图 2给出了表 1中$I(T)$的编码。数组chromosome中存储的是从$I(A)$到$I(H)$中包含的所有任务ID(内容)，如果集合为空，则对应位置的值为-1。数组set position中存储的是$I(t)$在chromosome中的起始地址，该数组的长度与任务集合$T$的大小一致。例如，图 2中set position的第6个元素的起始位置是6，结束位置是下一个元素的起始位置减1(即为7)，所以$I(G)$中有两个任务ID，分别是$E$和$F$。最后，数组set label中存储的是$I(t)$中元素所属子集合的ID。例如，set label中E对应的值为0，F对应的值为1，它们对应的$I(G) = \{ \{ E\} , \{ F\} \} $；同理，$I(H) = \{ B, C, G\} $。

图  2  因果矩阵在GPU上的染色体编码

本文提出的并行交叉遗传算子计算步骤如下：

1)  各个线程随机计算一个个体ID；

2)  每个warp中的前16个线程各计算一个活动ID，并将计算结果保存在共享内存中；

3)  每个warp中的第i号线程(i < 16)和第i+16号线程去查找第i个活动ID，并结合自身的个体ID，从全局内存中读取对应活动的染色体片段，并保存在共享内存中；

4)  各线程随机计算一个交叉点，取值范围不超过染色体片段中子集的个数，将结果保存在共享内存中；

5)  第i号线程和第i+16号线程进行遗传交叉运算，得到新的个体；

在第2节中提到过，同一个warp中的线程基于SIMT模式执行指令。而在指令层，GPU是按半个warp进行线程调度。因此为了避免出现执行分支，上述算法中让warp中前16个线程计算活动ID。然后让第i号线程与第i+16号线程共享同一个活动ID，并进行遗传交叉得到新的个体(下文中称为后代)。图 3给出了一个遗传交叉的例子。此外，上述算法中，活动ID、染色体片段、交叉点都保存在共享内存中，这样算法的性能可以得到最大提升。

图  3  一个遗传交叉的例子

本文算法的另一个特点是没有采用交叉概率，而是通过启动大量的线程进行随机交叉遗传，以此增强算法的搜索范围来加快算法收敛。由于在CPU上无法进行大规模并行操作，因此文献[9]中遗传交叉算子采用的方法是先计算一个随机数，若该随机数小于交叉概率才对随机选择的两个个体进行交叉遗传，以此提高算法的随机性。

本文提出的并行遗传变异算子计算步骤如下：

1)  每个warp的第0号线程计算一个随机数，并保存在共享内存中；

2)  各线程计算自己的warp ID，然后去读取步骤1)中生成的随机数；

3)  将得到的随机数与变异概率进行比较。若随机数小于变异概率，则继续执行；否则算法结束；

4)  按照文献[9]中的方法对后代个体进行遗传变异操作。

从上述算法可以看出，本文采用了一种粗粒度的方式进行并行遗传变异。这样做的目的仍然是因为GPU的SIMT机制。若采用细粒度的方式，即各个线程各自计算随机数以决定是否进行遗传变异，则会导致大量的执行分支，降低GPU的利用率。遗传变异结束后，本文算法采用了动态并行的方式，对后代中每个任务对应的染色体片段进行修复。

本文采用文献[9]中的适应度函数，如式(1)所示：

式中，$L$表示事件日志；$\mathit{\boldsymbol{C}}$表示因果矩阵(即遗传个体)；$\mathit{\boldsymbol{C}}[]$表示种群中所有的遗传个体；${\rm{P}}{{\rm{F}}_{{\rm{complete}}}}$表示的是模型(即遗传个体代表的因果矩阵)的完整性；${\rm{P}}{{\rm{F}}_{{\rm{precise}}}}$表示的是模型的精度；κ是惩罚系数。更详细的解释请参考文献[9]，在此不再累述。

上述适应度函数的基本思想是利用事件日志来检验模型的完整性和精度。具体来讲，就是将事件日志中的事件轨迹依次输入到模型中进行检验。本文算法在计算适应度时，同一block中的线程处理相同的事件轨迹和不同的遗传个体。这样设计的目的仍然是为了遵循SIMT机制。同一warp中的线程读取相同的事件轨迹，这样同一warp中的线程之间就能保持执行同步。每个线程计算完毕后，再通过CUDA提供的atomicAdd()原子操作，将计算结果累加到全局内存的数据中，从而实现适应度的计算。

本节通过仿真实验对本文算法进行验证。实验的硬件平台是Dell PowerEdge T630服务器，装配有一个至强E5-2609处理器和32 GB内存；GPU是Nvidia GTX 1080Ti。仿真实验分为两个部分，首先验证本文算法中优化策略的有效性，其次是通过比较本文算法(GPM-GPU)与已有算法来验证算法性能。在第二部分实验中，实验基线采用的是原始的遗传过程挖掘算法(genetic process miner, GPM)^[9]，另一个用于比较的算法采用的是有4个计算节点的分布式遗传过程挖掘算法(distributed genetic process miner, DGPM)^[16]。本文提出算法采用C/C++实现，软件环境是windows server 2012 + CUDA 8.0, ；实验比较所采用算法已经作为插件集成在ProM中，实验中采用的是版本是ProM 6.8(http://www.promtools.org/)。

与文献[9，16]中的实验类似，本文采用了两个不同规模的事件日志作为实验数据，均是通过CPN工具(http://cpntools.org/)生成。第一个事件日志(event log 48)中包含了48个任务和300个随机生成的事件轨迹，第二个事件日志(event log 72)中包含了72个任务和500个随机生成的事件轨迹。此外，生成事件日志的模型中除了顺序、选择、并行结构外，还随机加入了少量循环结构和非自由选择结构。

遗传过程挖掘算法的参数设置如表 2所示。在GPM-GPU算法中，block大小设置为256，grid大小分别设置为6和8。

本节首先通过3组实验来验证本文算法中优化策略的有效性。第一组实验比较warp内的遗传交叉(warp crossover, WC)和相邻线程遗传交叉的性能差异(neighbor crossover, NC)。二者实现上的区别在于，前者是用warp内的前16个线程计算任务ID，然后由第i号线程和i+16号线程进行遗传交叉；后者用warp内的偶数号线程计算任务ID，然后由第i号线程和i+1号线程进行遗传交叉。第二组实验比较粗粒度遗传变异和细粒度遗传变异的性能差异。粗粒度遗传变异即本文算法中采用的策略(coarse-grained mutation, CGM)；细粒度遗传变异则是由线程各自计算一个随机数与变异概率进行比较，从而决定是否发生遗传变异(fine-grained mutation, FGM)。第三组实验比较的是两种不同的适应度计算方法，第一种方法使用的是本文提出的策略(same trace in block, STB)，第二种方法则是同一线程块中的线程处理不同的事件轨迹和相同的遗传个体(same individual in block, SIB)。

实验结果如表 3所示。在第一组实验中，基于不同交叉策略的GPM-GPU算法在两个数据集上的搜索质量几乎没有区别，但是在遗传交叉算子的平均执行时间开销上，WC策略比NC策略在两个数据集上分别快约71%和75%。在第二组实验中，两种不同的遗传变异策略同样对算法的搜索质量没有影响，但是在遗传变异的平均计算时间开销上，粗粒度遗传变异策略CGM比细粒度遗传变异策略FGM在两个数据集上分别快约121%和123%。在第三组实验中，不同的适应度计算顺序对计算结果无影响，但是本文提出的策略STB要比第二种策略SIB在两个数据集上分别快约450%和438%。以上实验结果表明，本文提出的优化策略是有效的。

本节通过比较本文算法GPM-GPU和CPU上的遗传过程挖掘算法以及4个计算节点的分布式遗传过程挖掘算法DGPM来验证提出算法的性能。实验结果如图 4、图 5所示。

图  4  event log 48数据集下的性能比较

图  5  event log 72数据集下的性能比较

从实验结果看，GPM-GPU的收敛速度和搜索结果都要明显优于GPM和DGPM。在event log 48数据集上，GPM-GPU在第10代左右已经趋于收敛，而GPM和DGPM在遗传进化至200代时，其最优遗传个体的适应度值依然低于GPM-GPU搜索到的最优个体。而在event log 72数据集上，GPM-GPU在第50代左右已经趋于收敛，而GPM和DGPM则均是遗传进化至200代时才逐渐趋于收敛，并且GPM-GPU搜索到的最优个体的适应度值也要略优于GPM和DGPM搜索到的最优个体。

本实验还比较了3个算法在两个数据集上进化200代/400代的执行时间开销，并且计算了GPM-GPU和DGPM相对于基线算法GPM的执行时间加速比，结果如表 4所示。从表中可以看出，4个计算节点的DGPM算法相对于GPM算法能取得3.2倍和3.4倍的执行时间加速比。这与文献[16]中的实验结果基本一致。根据文献[16]中所述，DGPM算法在计算节点继续增加时并不能进一步降低执行时间开销，这是因为计算节点增多会导致节点之间的数据传输次数增多，反而降低加速性能。而GPM- GPU与DGPM相比则能够获得更好的执行时间加速比。从表 4可以看出，GPM-GPU算法在两个数据集上分别取得了36.4倍和47.2倍的加速比。而且可以看出，事件日志中的任务数和事件轨迹数越多，GPM-GPU算法得到的执行时间加速比越大。

本文提出了一种基于GPU的并行遗传过程挖掘算法GPM-GPU。该算法首先解决了遗传过程挖掘算法中的因果矩阵在GPU上的表示问题；其次，充分利用GPU高并行的特点，利用海量线程对过程模型进行搜索；第三，对并行遗传过程挖掘算法中的遗传交叉和遗传变异算子、以及适应度计算都进行了较好的并行设计和实现。本文通过仿真实验对提出的算法进行了验证。实验结果表明：1)本文算法中采用的优化策略是有效的，并且对所提出算法的整体性能提升能起到较大帮助；2)本文算法能够充分利用GPU计算性能，其收敛速度和搜索质量都要明显优于现有遗传挖掘算法GPM和DGPM。在两个实验数据集上，本文算法与GPM算法相比达到了36.4倍和47.2倍的执行时间加速比。以上实验结果证实了本文算法的有效性及性能。