基于日志的生物基因测序的任务模型构建方法

摘要

本发明公开了一种基于日志的生物基因测序的任务模型构建方法，首先分析并提取生物基因测序日志中任务在提交时间上具有的工作日周期性和节假日周期特性；任务并行度在分布上具有的重尾分布特征，任务并行度同任务运行时间之间的重尾分布特征；任务队列的队列使用率存在指数分布，正态分布，伽马分布，二项分布特征，同时队列使用率同队列的日任务到达数的期望值之间存在非线性关系的特征。本发明模拟了任务提交时间上的工作日周期性以及节假日周期性；然后生成了任务的并行度和任务的运行时间；最后到达数的期望之间存在的关系生成了任务的队列号。最终构建的任务模型可以用于更好地分析生物基因测序技术的优缺点，优化高性能环境的资源利用率。

说明书

技术领域

本发明涉及高性能计算领域，特别涉及一种基于日志的生物基因测序的任 务模型构建方法。

背景技术

自从watson和crick在1953年发现了DNA的双螺旋结构后，生命科学的 发展便翻开了新的篇章。而针对DNA的生物基因测序技术则成为整个生命科学 发展的基础。另一方面，生物基因测序技术需要海量的计算和存储资源进行快 速的测序，因此如果计算资源和存储资源调度不合理的话，会导致资源的利用 率低下，进而延迟基因测序的速度。而生物基因测序日志是生物基因测序技术 在高性能计算环境下的使用记录，通过分析生物基因测序日志中任务的各项属 性（任务的到达时间，任务的并行性，任务的运行时间等），可以很好地掌握 生物基因测序使用计算资源的情况。而通过这些任务特性构建具有相同特性的 任务模型，则有利于提出一种针对这些特性的集群调度策略，进而优化集群的 资源使用率。高性能环境下利用任务日志中的任务特性分为两种：可塑性任务 和刚性任务。可塑性任务是指任务的并行度和任务的运行时间是可变的，而刚 性任务则指任务的并行度和任务的运行时间是固定不变的。本发明主要针对刚 性任务的任务特性进行模型构建，因此以下主要介绍刚性任务方向的任务模型 构建的研究情况。

早期针对刚性任务负载的进行建模主要有以下四个特征：任务的并行性 (任务使用的CPU数量)、任务的运行时间、用户重复提交的任务数量以及任务 的到达时间间隔。首先利用指数分布来模拟任务的到达时间间隔，通过对日志 分析模拟出任务的并行性，再通过任务的并行性产生概率p，然后利用这个概 率和高阶指数分布模拟出任务的运行时间。需要指出的是这种方法在进行任务 时间间隔模拟时，没有考虑任务到达的工作日周期性和休息日周期性。本发明 则同时考虑这两种周期特性。而在最近的研究中，研究人员通过分析上述研究 中未解决的问题，例如任务到达时间间隔的日周期特性等，然后分析了任务到 达的工作日周期性，将一天分为48个时间槽，每个时间槽(1800s)根据其平均 到达的任务数，获得正比于任务数的权重，然后采用伽马分布对任务的工作日 周期性进行模拟。同时研究人员发现任务的并行性与任务运行时间具有正比关 系，且这两个任务特征的对数呈伽马分布，于是，研究人员利用上述信息首先 模拟出任务的并行性，然后通过任务的并行性模拟出任务的运行时间。但是并 没有分析任务到达时间间隔的工作日周期性和节假日周期性，而是将这两种混 合在一起分析了日周期特性。本发明同时考虑了这两种特性。

尽管现有的研究对刚性任务进行了很好的任务模型构建，但是仍然存在待 解决的问题，例如任务的工作日周期特性和节假日周期特性的模型构建。因此， 本发明在现有研究的基础上针对任务到达时间间隔的工作日周期性和节假日 周期性，任务运行时间，任务的并行度以及任务的队列使用特性提出了一种基 于日志的针对生物基因测序的任务模型构建方法。

发明内容

本发明的目的在于克服现有技术的缺点与不足，针对从实际环境中采集的 生物基因测序日志的任务到达时间间隔，任务的运行时间，任务的并行性，以 及任务的队列特性构建一种具有这些任务特性的任务模型。

本发明的目的通过下述技术方案实现：

一种基于日志的生物基因测序的任务模型构建方法，包括以下步骤：

（1）DCModel模块构建，主要利用指数分布和伽马分布来模拟任务的工 作日周期性，通过指数分布模拟任务的节假日周期性，最后通过两个指数分布 产生任务的时间间隔T；

（2）PRModel模块构建，首先利用伽马分布模拟出任务并行度P，然后 利用生物基因测序日志中任务并行度与任务运行时间之间存在重尾分布的特 征，利用伽马分布拟合这种特征，然后模拟出任务的运行时间R；

（3）QModel模块构建，首先利用一个伪随机函数发生器对所有要生成的 队列进行分类，分为四类LOW,MIDDLE,SUBHIGH,HIGH，针对这四种不同的分 类分别采用指数分布，正态分布，伽马分布以及二项分布来生成每个队列的使 用率U_i，然后利用队列的使用率U_i同队列日任务到达数目期望之间存在的非 线性关系，生成然后通过一个指数分布产生M_i，最后利用U_i，M_i以及一 个伪随机函数发生器来产生队列号。

优选的，步骤(1)中的DCModel的模型构建，首先判断输入的开始时间S 是工作日还是节假日，如果是工作日则选择工作日周期性模块，生成一个符合 工作日周期性的任务到达的时间间隔T；反之，则生成一个符合节假日周期性 的任务到达时间间隔T，最后用(S+T)作为该任务的提交时间，并修正开始时 间S=S+T。

优选的，DCModel模块实现的数学表达式如下：

$\mathrm{WorkDC}\Rightarrow \left(\begin{array}{cc}{x}_i~E\left(\overline{x_i}\right)& 1\le i\le 9\\ x_i~\Gamma ({\alpha }_i,{\beta }_i)& 10\le i\le 24\end{array}\right)$

$\mathrm{WeekDC}\Rightarrow y_i~E\left(\overline{y_i}\right),1\le i\le 24$

$t_i~\left(\begin{array}{cc}E(3600/x_i)& 1\le i\le 24\\ E(3600/y_i)& 1\le i\le 24\end{array}\right)$

其中，公式中各个参数的意义为：x_i代表工作日的时间槽i到达的任务数 目；y_i代表节假日的时间槽i到达的任务数目；表示工作日时间槽i到达的任 务数目的期望值；代表节假日时间槽i到达的任务数目的期望值；E表示指数 分布；Γ表示伽马分布；t_i表示第i个时间槽任务到达的时间间隔；α_i和β_i表示 伽马分布的规模参数和形状参数；WorkDC表示工作日周期性，WeekDC表示节 假日周期性。

优选的，步骤(2)中的PRModel的模型构建，接收由步骤(1)生成的提交时 间(S+T)作为触发，通过伪随机函数发生器选择任务并行度P所在的区间，然 后利用相应的伽马分布函数产生任务的并行度；然后再利用伪随机函数发生器 选择任务运行时间R所在的区间，然后利用相应的伽马分布函数和任务并行度 P产生任务的运行时间R。

优选的，PRModel模块实现的数学表达式如下：

$P~\left(\begin{array}{cc}U(b_1,b_1)& P=b_1\\ \Gamma ({\alpha }_{11},{\beta }_{11})& b_2\le P\le b_3\\ \Gamma ({\alpha }_{12},{\beta }_{12})& b_3<P\le b_4\end{array}\right)$

$R(\le R_{\mathrm{low}\_\mathrm{th}})~\left(\begin{array}{cc}\Gamma ({\alpha }_{21},{\beta }_{21})& P=b_1\\ \Gamma ({\alpha }_{22},{\beta }_{22})& b_2\le P\le b_3\\ \Gamma ({\alpha }_{23},{\beta }_{23})& b_3<P\le b_4\end{array}\right)$

$R(>R_{\mathrm{mid}\_\mathrm{th}})~\left(\begin{array}{cc}\Gamma ({\alpha }_{41},{\beta }_{41})& P=b_1\\ \Gamma ({\alpha }_{42},{\beta }_{42})& b_2\le P\le b_3\\ \Gamma ({\alpha }_{43},{\beta }_{43})& b_3<P\le b_4\end{array}\right)$

其中，上述四个公式中各个参数的意义：b₁，b₂，b₃，b₄表示划分任务并 行度的界限值，同生物基因测序日志中任务并行度的分布有关；α₁₁和β₁₁，α₁₂和 β₁₂表示任务并行度服从伽马分布的参数值；α₂₁和β₂₁，α₂₂和β₂₂，α₂₃和β₂₃，α₃₁和 β₃₁，α₃₂和β₃₂，α₃₃和β₃₃，α₄₁和β₄₁，α₄₂和β₄₂，α₄₃和β₄₃表示任务并行度同任务运 行时间之间的伽马分布关系的参数值；R_{low_th}和R_{mid_th}表示任务运行时间的阈值； U表示一致性分布。

优选的，步骤(3)中的QModel的模型构建，接收步骤(1)和(2)中生成的 (S+T),P,R作为触发，根据生物基因测序日志中队列的分布特性模拟并生成该 任务的队列号Q，最终完成整体任务模型的构建，生成的任务具有任务的提交 时间，任务的并行度，任务的运行时间，任务的队列号。

优选的，QModel的数学表达式：

$U_i~\left(\begin{array}{cc}E\left({\bar{U}}_i\right)& i\in \mathrm{LOW}\\ N({\mu }_i,{\sigma }_i)& i\in \mathrm{MIDDLE}\\ \Gamma ({\alpha }_i,{\beta }_i)& i\in \mathrm{SUBHIGH}\\ B(0.2,1.0)& i\in \mathrm{HIGH}\end{array}\right)$

${\bar{M}}_i=\left(\begin{array}{cc}{l}_i{U_i}^3+l_2{U_i}^2+l_3{U}_i+l_4& i\in \mathrm{LOW}\\ m_1{U_i}^3+m_2{U_i}^2+m_3{U}_i+m_4& i\in \mathrm{MIDDLE}\\ s_1{U_i}^3+s_2{U_i}^2+s_3{U}_i+s_4& i\in \mathrm{SUBHIGH}\end{array}\right)$

${\bar{M}}_i=\left(\begin{array}{cc}{C}_{0.2}& U_i=0.2,i\in \mathrm{HIGH}\\ C_{1.0}& U_i=1.0,i\in \mathrm{HIGH}\end{array}\right)$

$M_i~E\left({\bar{M}}_i\right),i\in \mathrm{LOW}\cup \mathrm{MIDDLE}\cup \mathrm{SUBHIGH}\cup \mathrm{HIGH}$

其中，上述四个公式中各个参数的意义：LOW，MIDDLE，SUBHIGH，HIGH 是依据生物基因测序日志中每个队列的日任务到达数目的期望值的大小进行划 分的区间；N表示正态分布，B是二项分布(不同于概率论里面的二项分布)，主 要为了生成HIGH区间内的队列使用率；U_i表示队列i的队列使用率，队列使用 率表示队列有任务到达的天数与总天数的比率；表示队列i的日任务到达数目 的期望值；M_i表示队列i的日任务达到数目；C_0.2和C_1.0是针对生物基因中两个不 同的队列使用率的日任务到达数目的期望值(由于这两个数值比较大，故进行单 独的模拟)；μ_i，σ_i，α_i，β_i可以通过生物基因测序日志得出具体的数值。）

本发明相对于现有技术具有如下的优点及效果：

1.DCModel模拟了生物基因测序日志中任务的工作日周期性和节假日周期 性，而以往的任务模型只是考虑的任务的日周期性，即不区分工作日和节假日。

2.PRModel将生物基因测序日志中任务的运行时间和任务的并行度联系起 来，首先产生出任务的并行度，然后利用任务并行度同任务运行时间的关系， 利用伽马分布生成任务的运行时间。

3.QModel首先模拟出生物基因测序日志中任务的和，然后利用这两个特 性模拟出任务的队列号，而现有研究中并没有考虑任务的队列号的模拟。

4.与现有研究不同，本发明是针对生物基因测序日志进行的模型构建，因 此可以更好地用于生物基因测序技术的分析。

附图说明

图1是为本发明基于生物基因测序日志构建的任务模型的框架图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方 式不限于此。

实施例

如图1所示，基于生物基因测序日志构建的任务模型的方法，包括以下 步骤：

(1)DCModel的构建。在生物基因测序日志中任务的到达时间间隔存在工作 日周期特性和节假日周期特性，因此DCModel需要同时能够产生具有工作日周 期特性和节假日周期特性的任务日志。首先将一天分为24个时间槽，每个时间 槽对应一个小时，生物基因测序日志的日周期特性显示：在时间槽1和时间槽9 之间每个时间槽任务到达的数目呈现逐渐降低然后升高的过程，而在时间槽10 到时间槽24之间每个时间槽任务到达的数目呈现逐渐升高然后降低的过程；同 时在时间槽1到时间槽9内任务到达数目同时间槽存在指数分布关系，而时间 槽10到时间槽24存在伽马分布关系。

$\mathrm{WorkDC}\Rightarrow \left(\begin{array}{cc}{x}_i~E\left(\overline{x_i}\right)& 1\le i\le 9\\ x_i~\Gamma ({\alpha }_i,{\beta }_i)& 10\le i\le 24\end{array}\right)$

$\mathrm{WeekDC}\Rightarrow y_i~E\left(\overline{y_i}\right),1\le i\le 24$

$t_i~\left(\begin{array}{cc}E(3600/x_i)& 1\le i\le 24\\ E(3600/y_i)& 1\le i\le 24\end{array}\right)$

针对生物基因测序日志中日周期特性，本发明的DCModel的具体实现方 案如上述三个公式。DCModel的构建步骤如下：

1)首先通过生物基因测序日志可以计算出工作日各个时间槽中的α_i和 β_i，然后计算出x_i；

2)同样可以从生物基因测序日志中计算出节假日各个时间槽的然后计 算出y_i；

3)从现有的研究中易知集群中任务到达的时间间隔服从指数分布，同时一 个时间槽的时间长度为3600s，因此可以利用上述最后一个公式，x_i和y_i产生工 作日和节假日任务到达的时间间隔，从而完成DCModel的模型构建。

(2)PRModel的构建。生物基因测序日志中的任务的运行时间和任务的并行 度之间存在重尾分布关系。但是重尾分布的数据生成误差比较大，因此本发明 首先将任务的并行度按照不同大小划分成不同的任务并行度区间，然后利用伽 马分布来拟合划分后区间内任务的并行度同任务运行时间之间的关系。下述四 个公式是PRModel的数学关系表达式。

$P~\left(\begin{array}{cc}U(b_1,b_1)& P=b_1\\ \Gamma ({\alpha }_{11},{\beta }_{11})& b_2\le P\le b_3\\ \Gamma ({\alpha }_{12},{\beta }_{12})& b_3<P\le b_4\end{array}\right)$

$R(\le R_{\mathrm{low}\_\mathrm{th}})~\left(\begin{array}{cc}\Gamma ({\alpha }_{21},{\beta }_{21})& P=b_1\\ \Gamma ({\alpha }_{22},{\beta }_{22})& b_2\le P\le b_3\\ \Gamma ({\alpha }_{23},{\beta }_{23})& b_3<P\le b_4\end{array}\right)$

$R(>R_{\mathrm{mid}\_\mathrm{th}})~\left(\begin{array}{cc}\Gamma ({\alpha }_{41},{\beta }_{41})& P=b_1\\ \Gamma ({\alpha }_{42},{\beta }_{42})& b_2\le P\le b_3\\ \Gamma ({\alpha }_{43},{\beta }_{43})& b_3<P\le b_4\end{array}\right)$

PRModel的构建步骤如下：

1)首先在上述第一个公式中，利用生物基因测序日志计算出不同并行度区 间内任务所占的概率值，利用伪随机函数发生器产生一个概率，利用这个概率 值选择对应的并行度区间，然后利用相应的分布函数产生出任务的并行度值P；

2)然后利用生物基因测序日志，计算出pdf(P,R)的概率值，其中pdf表示不 同并行度P的区间和不同任务运行时间R的区间之间的概率值。其中P被b₁，b₂， b₃，b₄分为三个不同的并行度区间，而R被R_{low_th}，R_{mid_th}分为三个区间。同时，由 步骤1)已经得出任务并行度所在的区间，而利用生物基因测序日志可以得出对 应该任务并行度P区间的三个任务运行时间R区间的概率值，然后利用一个伪随 机函数发生器可以来选择相应的任务运行时间R的区间。

3)最后利用步骤1)中得出的任务并行度的P的区间和任务运行时间R的区 间，以及上述最后三个公式选择合适的伽马分布函数来产生任务的运行时间R。

(3)QModel的构建。生物基因测序日志中使用多队列任务调度模型，各个 队列的使用率并不相同，且存在某种规律性，因此本发明通过研究和分析这种 规律性构建了一种针对生物基因测序日志队列的QModel模型。下面四个公式是 QModel的数学关系式。

$U_i~\left(\begin{array}{cc}E\left({\bar{U}}_i\right)& i\in \mathrm{LOW}\\ N({\mu }_i,{\sigma }_i)& i\in \mathrm{MIDDLE}\\ \Gamma ({\alpha }_i,{\beta }_i)& i\in \mathrm{SUBHIGH}\\ B(0.2,1.0)& i\in \mathrm{HIGH}\end{array}\right)$

${\bar{M}}_i=\left(\begin{array}{cc}{l}_i{U_i}^3+l_2{U_i}^2+l_3{U}_i+l_4& i\in \mathrm{LOW}\\ m_1{U_i}^3+m_2{U_i}^2+m_3{U}_i+m_4& i\in \mathrm{MIDDLE}\\ s_1{U_i}^3+s_2{U_i}^2+s_3{U}_i+s_4& i\in \mathrm{SUBHIGH}\end{array}\right)$

${\bar{M}}_i=\left(\begin{array}{cc}{C}_{0.2}& U_i=0.2,i\in \mathrm{HIGH}\\ C_{1.0}& U_i=1.0,i\in \mathrm{HIGH}\end{array}\right)$

$M_i~E\left({\bar{M}}_i\right),i\in \mathrm{LOW}\cup \mathrm{MIDDLE}\cup \mathrm{SUBHIGH}\cup \mathrm{HIGH}$

QModel的具体实现步骤如下：

1)首先从生物基因测序日志中计算出LOW，MIDDLE，SUBHIGH，HIGH四 个区间所占的比率，然后利用一个伪随机函数将要生成的队列号随机地分布到 这四个区间内。然后计算每个队列的U_i和最后计算出每个队列的M_i。

2)通过上述第一个公式计算出队列i所在的区间，并选出合适的分布函数， 利用相应的分布函数产生出队列i的队列使用率U_i。在生物基因测序日志中的区 间LOW，MIDDLE和SUBHIGH内，队列的U_i同队列的存在非线性关系，本发 明利用三个三次二项式来拟合这三个区间内U_i和的关系；而在区间HIGH内， 由于队列较少，因此队列使用率U_i和采用一一对应的关系如上述第三个公式 所示。然后可以从上述第三个和第四个公式中选择队列i对应的U_i和的关系式 求出队列的重复步骤2)，直到求出所有队列的U_i和

3)在生物基因测序日志中，队列的M_i的分布是服从期望值为的指数分 布。因此可以通过上述第四个公式，同时利用队列i的求出队列的M_i。

4)最后利用各个队列的U_i和M_i生成队列号：首先利用一个伪随机数发生器 生成一个介于0和1之间的数值，将所有U_i大于这个数值的队列放入一个临时 列表中；然后将这个临时列表中所有队列按照它们M_i的大小标准化到区间[0,1] 内，即按照M_i的大小在区间[0,1]内对应一块同比率的区间；最后，再利用另一 个伪随机数发生器产生一个介于0和1之间的数值，数值所在的区间对应的队 列号即为最终生成的队列号。

最后综合步骤(1)(2)(3)生成拥有任务提交时间，任务的运行时间，任务 的并行度以及任务的队列号的任务。重复这三个步骤即可生成多个任务记录， 从而形成用于生物基因测序技术的性能评估。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实 施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、 替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。