一种调度器及其减少异步迭代处理中冗余开销的方法

摘要

本发明公开了一种减少异步迭代处理中冗余开销的方法，包括以下步骤：建立一个哈希表，每一表项对应一个数据组，其中每一表项又包括三个域，接收来自于消息接收器的数据D，根据该数据D的ITC值和IN值计算该数据D的权值Pri(D)，判断在哈希表中是否存在与该数据D具有相同键值的数据组G(D)存在，若存在则更新该数据组G(D)的权值和数据列表，否则在哈希列表中创建与该数据D相同键值的数据组G(D)，并进行初始化，判断任务执行器是否空闲，如果是则从哈希表中选择权值最大的一个数据组，将该数据组对应的数据传送给任务执行器处理。本方法能够解决现有方法中存在的冗余计算和通信开销大、计算机资源浪费、迭代计算的收敛速度慢的问题。

说明书

技术领域

本发明属于大数据处理领域，更具体地，涉及一种调度器及其减少异 步迭代处理中冗余开销的方法。

背景技术

异步迭代处理普遍存在于万维网应用，数据挖掘和科学计算等领域中， 例如：万维网搜索引擎中的PageRank算法,链接分析和推荐系统中的 Adsorption算法,以及用于解决线性方程组的Jacobi方法，它允许前面迭代 中产生的中间结果立即被用于目前迭代中的计算,加快迭代计算的收敛速 度，并且不存在负载均衡问题而使得云计算基础设施得到更好的应用。

然而，当有很多可用的中间结果可用时，异步迭代处理就会由于下面 两个原因触发后续迭代中大量没必要的计算开销和通信开销：一）盲目的 选择一个中间结果进行处理，而不考虑每个数据对收敛速度的影响和首先 处理它们将引起的开销；二）为每一个中间结果都在后续迭代中级联触发 大量的计算和通信开销，从而使得异步迭代处理对大多数迭代应用会引起 大量冗余计算和通信开销，减慢异步迭代处理的收敛速度，浪费大量计算 机资源，实际上，这些冗余触发可以通过调度算发被避免掉，然而目前所 有的用于异步迭代处理的调度算法，例如：优先级调度（Priority scheduling）、 轮询调度（Round-robin scheduling）等，在选择一个中间结果进行处理时， 都不考虑首先处理这些中间结果的开销。同时，这些调度算法都不是以组 的形式进行调度的，从而需要为每一个中间结果数据级联触发后续迭代中 的计算和通信，最终使得使用这些调度算法的异步迭代处理对于很多迭代 应用仍然存在大量的级联性的计算和通信冗余开销。然而，这些冗余计算 和通信开销会大量的浪费了计算机资源，并减慢了迭代计算的收敛速度。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种减少异步迭 代处理中冗余开销的方法，其目的在于解决现有方法中存在的冗余计算和 通信开销大、计算机资源浪费、迭代计算的收敛速度慢的问题。

为实现上述目的，按照本发明的一个方面，提供了一种减少异步迭代 处理中冗余开销的方法，其应用在一种调度器中，该调度器分别与任务执 行器和消息接收器通讯连接，该方法包括以下步骤：

（1）建立一个哈希表，每一表项对应一个数据组，其中每一表项又包 括三个域：第一个域用于存储数据组的键值，第二个域用于数据组的权值， 第三个域用于存储数据组中的数据列表，数据列表中包括数据的值、以及 数据所在的迭代层次；

（2）接收来自于消息接收器的数据D；

（3）根据该数据D的ITC值和IN值计算该数据D的权值Pri(D)，具 体包括以下子步骤：

（3-1）计算数据D的ITC值ITC(D)和IN值IN(D)，其中ITC(D)＝±D， IN(D)是记录在数据D中的信息，其具体为数据D的最初原始数据变化到数 据D期间所处理的次数；

（3-2）根据ITC（D）和IN(D)并利用以下等式计算数据D的权值Pri(D)： Pri(D)＝t₁×ITC(D)+t₂×IN(D)/T，其中t₁和t₂分别为表示ITC（D）和 IN(D)重要性的权重值，且其取值为0至1之间的小数，T为调整IN(D)取 值范围的值，其取值范围是大于1的整数；

（4）判断在哈希表中是否存在与该数据D具有相同键值的数据组G(D) 存在，若存在则更新该数据组G(D)的权值和数据列表，否则在哈希列表中 创建与该数据D相同键值的数据组G(D)，并进行初始化，

（5）判断任务执行器是否空闲，如果是则进入步骤（6），否则返回步 骤（2）；

（6）从哈希表中选择权值最大的一个数据组，将该数据组对应的数据 传送给任务执行器处理，然后进入步骤（7）；

（7）判断任务执行器中运行的应用程序是否结束，如果是则过程结束， 否则转入步骤（8）；

（8）判断哈希表中是否还有未处理的数据组，如果有则返回步骤（5）， 否则返回步骤（2）。

优选地，步骤（4）包括以下子步骤：

（4-1）获得数据D的键值D_key，对该键值进行哈希函数处理以获得一 个唯一组标识K；

（4-2）根据该唯一标识K在哈希表中进行查询，以判断是否有键值为 D_key的数据组G(D)，若有,则转入步骤（4-3），否则转入步骤（4-4）；

（4-3）将数据D插入具有键值D_key的数据组G(D)中，然后转入步骤 （4-5）；

（4-4）创建一个键值为D_key的数据G(D)，并将数据D插入数据组G(D) 中，然后转向步骤(4-6)；

（4-5）采用以下公式更新哈希表中键值为D_key的数据组的权值， Pri(G(D))＝Pri(G(D))+Pri(D)，然后转向步骤（5）；

（4-6）将数据组G(D)的权值设置为Pri(D)，然后转向步骤（5）。

按照本发明的另一方面，提供了一种调度器，其分别与任务执行器和 消息接收器通讯连接，该调度器包括：

第一模块，用于建立一个哈希表，每一表项对应一个数据组，其中每 一表项又包括三个域：第一个域用于存储数据组的键值，第二个域用于数 据组的权值，第三个域用于存储数据组中的数据列表，数据列表中包括数 据的值、以及数据所在的迭代层次；

第二模块，用于接收来自于消息接收器的数据D；

第三模块，用于根据该数据D的ITC值和IN值计算该数据D的权值 Pri(D)，具体包括以下子步骤：

第一子模块，用于计算数据D的ITC值ITC(D)和IN值IN(D)，其中 ITC(D)＝±D，IN(D)是记录在数据D中的信息，其具体为数据D的最初原 始数据变化到数据D期间所处理的次数；

第二子模块，用于根据ITC（D）和IN(D)并利用以下等式计算数据D 的权值Pri(D)：Pri(D)＝t₁×ITC(D)+t₂×IN(D)/T，其中t₁和t₂分别为表 示ITC（D）和IN(D)重要性的权重值，且其取值为0至1之间的小数，T 为调整IN(D)取值范围的值，其取值范围是大于1的整数；

第四模块，用于判断在哈希表中是否存在与该数据D具有相同键值的 数据组G(D)存在，若存在则更新该数据组G(D)的权值和数据列表，否则在 哈希列表中创建与该数据D相同键值的数据组G(D)，并进行初始化；

第五子模块，用于判断任务执行器是否空闲，如果是则进入第六模块， 否则返回第二模块；

第六模块，用于从哈希表中选择权值最大的一个数据组，将该数据组 对应的数据传送给任务执行器处理，然后进入第七模块；

第七模块，用于判断任务执行器中运行的应用程序是否结束，如果是 则过程结束，否则转入第八模块；

第八模块判断哈希表中是否还有未处理的数据组，如果有则返回第五 模块，否则返回第二模块。

优选地，第四模块包括：

第三子模块，用于获得数据D的键值D_key，对该键值进行哈希函数处 理以获得一个唯一组标识K；

第四子模块，用于根据该唯一标识K在哈希表中进行查询，以判断是 否有键值为D_key的数据组G(D)，若有,则转入第五子模块，否则转入第六 子模块；

第五子模块，用于将数据D插入具有键值D_key的数据组G(D)中，然后 转入第七子模块；

第六子模块，用于创建一个键值为D_key的数据G(D)，并将数据D插入 数据组G(D)中，然后转向第八子模块；

第七子模块，用于采用以下公式更新哈希表中键值为D_key的数据组的 权值，Pri(G(D))＝Pri(G(D))+Pri(D)，然后转向第八子模块；

第八子模块，用于将数据组G(D)的权值设置为Pri(D)，然后转向步骤 第七子模块。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列的有益效果：

1、冗余计算量和冗余通信量小：由于采用步骤（1）解决了每一个数 据都引起级联触发带来的一些冗余计算和通信开销，步骤（3-4）和步骤（6） 解决了以任意顺序盲目处理数据带来的冗余开销，因此本方法能够有效消 除异步迭代处理中大量存在的冗余计算开销和通信开销。

2、迭代计算的收敛速度快：由于采用了步骤（1），步骤（3-4）和步骤 （6），使得对异步迭代处理收敛更有效的计算和通信更快并优先地被处理， 因此本方法加快了异步迭代处理的收敛速度，提高云计算基础设施的资源 利用率。

附图说明

图1是本发明减少异步迭代处理中冗余开销的方法的应用环境图。

图2是本发明减少异步迭代处理中冗余开销的方法的流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

本发明的总体思路在于，提出了一个调度算法是以组的形式进行的， 并且在调度中间结果处理顺序时同时考虑数据们对迭代计算的收敛速度的 重要性和首先处理这些数据的开销的，此调度算法使用一个收集器将待处 理的数据以组的形式收集起来，同时为每组都分别计算一个权值，而每一 组的权值的计算需要考虑这一组所收集的数据们对迭代计算收敛速度起到 的重要性和首先处理这些数据将带来的开销，然后此调度算法就选择一个 权值最大的组，让此组的数据先被处理，从而达到有效消除异步迭代处理 中大量存在的这些冗余计算开销和通信开销,加快异步迭代处理的收敛速 度，提高云计算基础设施的资源利用率。

如图1所示，本发明减少异步迭代处理中冗余开销的方法是应用在一 种支持程序运行的系统（简称运行时系统）中，该系统包括任务管理器和 数据处理器，其中任务管理器用于管理数据处理器的初始化和结束，数据 处理器用于接收消息和处理数据，并包括消息接收器、本发明的调度器、 以及任务执行器，消息接收器用于接收其余数据处理器发来的包含处理数 据的消息，调度器用于调度接收到的消息中的数据的处理顺序，任务执行 器用于执行用户程序来处理调度器输出的待处理数据。

如图2所示，本发明减少异步迭代处理中冗余开销的方法是应用在一 种调度器中，该调度器分别与任务执行器和消息接收器通讯连接，该方法 包括以下步骤：

（1）建立一个哈希表，每一表项对应一个数据组，其中每一表项又包 括三个域：第一个域用于存储数据组的键值，第二个域用于数据组的权值， 第三个域用于存储数据组中的数据列表，数据列表中包括数据的值，以及 数据所在的迭代层次（Iteration number），其具体如表1所示；

本步骤的优点在于，通过建立哈希表，能够有利于数据组的快速查找 插入和更新。

数据组 数据组的键值 数据组的权值 数据列表                

表1

（2）接收来自于消息接收器的数据D；

（3）根据该数据D的收敛重要性（Importance To Convergence，简称 ITC）值和迭代层次（Iteration Number，简称IN）值计算该数据D的权值 Pri(D)，具体包括以下子步骤：

（3-1）计算数据D的ITC值ITC(D)和IN值IN(D)；具体而言， ITC(D)＝±D，其中正负号需要由任务执行器中的应用程序在配置文件里面 给出，对于一个应用程序，如果数据D的值越大对收敛起的作用越大，那 么用正号，否则用负号，而IN(D)是记录在数据D中的一个信息，其具体 为数据D的最初原始数据变化到数据D期间所处理的次数。

本子步骤的优点在于，通过近似计算ITC和IN值，能够有效的减少权 值计算开销。

（3-2）根据ITC（D）和IN(D)并利用以下等式计算数据D的权值Pri(D)： Pri(D)＝t₁×ITC(D)+t₂×IN(D)/T，其中t₁和t₂分别为表示ITC（D）和 IN(D)重要性的权重值，且其取值为0至1之间的小数，T为调整IN(D)取 值范围的值，主要使其取值范围和ITC（D）基本一致，其取值范围是大于 1的整数。

本子步骤的优点在于，通过为每个数据计算权值，能够使得数据组的 权值在以前的基础上通过数据D的权值增量获得，有效的获得数据组的实 时权值。如此计算Pri(D)的原因会在后面解释。

（4）判断在哈希表中是否存在与该数据D具有相同键值的数据组G(D) 存在，若存在则更新该数据组G(D)的权值和数据列表，否则在哈希列表中 创建与该数据D相同键值的数据组G(D)，并进行初始化；具体而言，本步 骤包括以下子步骤：

（4-1）获得数据D的键值D_key，对该键值进行哈希函数处理以获得一 个唯一组标识K；

（4-2）根据该唯一标识K在哈希表中进行查询，以判断是否有键值为 D_key的数据组G(D)，若有,则转入步骤（4-3），否则转入步骤（4-4）；

（4-3）将数据D插入具有键值D_key的数据组G(D)中，即完成了该数 据组G(D)在哈希表中哈希列表的更新，然后转入步骤（4-5）；

（4-4）创建一个键值为D_key的数据G(D)，并将数据D插入数据组G(D) 中，然后转向步骤(4-6)；

（4-5）采用以下公式更新哈希表中键值为D_key的数据组的权值， Pri(G(D))＝Pri(G(D))+Pri(D)，然后转向步骤（5）；

本子步骤的优点在于，通过计算数据组G(D)的权值，能够使得数据组 的权值Pri(G(D))在以前的基础上通过数据D的权值Pri(D)增量获得，有效 的获得数据组的实时权值。如此计算Pri(G(D))的原因会在后面解释。

（4-6）将数据组G(D)的权值设置为Pri(D)，然后转向步骤（5）；

（5）判断任务执行器是否空闲，如果是则进入步骤（6），否则返回步 骤(2)；

(6)从哈希表中选择权值最大的一个数据组，将该数据组对应的数据 传送给任务执行器处理，然后进入步骤(7)；

(7)判断任务执行器中运行的应用程序是否结束，如果是则过程结束， 否则转入步骤(8)；

(8)判断哈希表中是否还有未处理的数据组，如果有则返回步骤(5)， 否则返回步骤(2)。

下面解释按本方法所述方式计算Pri(D)和Pri(G(D))的原因。

在解释原因之前，我们首先给出如何定义一个组G(D)的权值Pri(G(D))， 在数据组的权值定义中，我们主要考虑这么两个因素。

因素一：ITC，一个拥有更大ITC值的组G(D)将会使迭代计算收敛的 更快，从而避免ITC值小的数据组触发大量后续冗余计算和通信开销。实 际上一个组的ITC值，也就是ITC(G(D))可以定义为： ITC(G(D))=∑_D∈G(D)ITC(D)。

因素二：CTG(Cost to firstly processing this group)，即首先处理此组数 据的开销，当一组数据被选择被处理时，其余将到达此组的数据将需要再 次被处理，并再次触发后续迭代中的一些计算和通信，而这些计算和通信 开销就是这组数据的CTG值，如果可以延迟那些CTG值大的组，而先处 理那些CTG小的组，那么CTG值大的组将会有更多机会收集更多的数据， 减少冗余开销，实际上，CTG就是用于提高所有组收集的平均数据量和收 集的数据们的重要性(引起触发越多的数据越重要)。在给出如何计算一个 组的CTG时，我们引入两个新的变量：1)Iteration Number(or IN)，这就 是被收集的数据所在的迭代层数；2)Completion Ratiof 0r CRl，这是在某 一迭代层次中据有键值n的所有已经被处理的数据占所有需要处理的数据 的比值,即CR(i,n)=Num_P(i,n)/Num_T(i,n),其中Num_P(i,n)和Num_T(i,n)是 在迭代层次为i时用于更新数据对象R(i）而已被处理的数据量和所有需要 被处理的数据量，由于Num_T(i,n)很难在提前知道,并且对于大多数数据对 象R(i）的Num_T(i,n)相同,所以近似Num_T(i,n)值为固定值T,那么有CR(i, n)=Num_P(i,n)/T。

现在我们给出组G(D)的CTG值,即CTG(G(D)),的计算方法，由于每 个组G(D)的CTG值依赖于将会到达此组的数据量和每个将到达的数据将 触发的计算和通信开销大小。由于在第ith迭代将会到达组G(D)的数据量依 赖于CR(i,D_key),达到数据组G(n)的数据D将会引起的触发量依赖于数据D 的IN值IN(D),所以CTG(G(D))＝-Σ_i∈Si×CR(i,D_key)，并且 S＝{n|D∈G(D)且IN(D)＝N}，D_key为数据D的键值，由于Pri(G(D))与 ITC(G(D))正相关,而与CTG(G(D))负相关,所以有：

Pri(G(D))＝t₁×ITC(G(D))-t₂×CTG(G(D))

为了实时有效获得每个组G(D)的权值Pri(G(D)),Pri(G(D))可以按如下 方式计算:

$\left(\begin{array}{c}\mathrm{Pri}\left(G\left(D\right)\right)=\mathrm{Pri}\left(G\left(D\right)\right)+\mathrm{Pri}\left(D\right)\\ \mathrm{Pri}\left(D\right)=t_1\times \mathrm{ITC}\left(D\right)+t_2\times \mathrm{IN}\left(D\right)/T\end{array},.\right)$

由此,每当一个数据D被调度器接收到时,就可以通过上述计算公式 增量地获得数据组G(D)的权值。

本发明的调度器，其分别与任务执行器和消息接收器通讯连接，并包 括：

第一模块，用于建立一个哈希表，每一表项对应一个数据组，其中每 一表项又包括三个域：第一个域用于存储数据组的键值，第二个域用于数 据组的权值，第三个域用于存储数据组中的数据列表，数据列表中包括数 据的值、以及数据所在的迭代层次；

第二模块，用于接收来自于消息接收器的数据D；

第三模块，用于根据该数据D的ITC值和IN值计算该数据D的权值 Pri(D)，具体包括以下子步骤：

第一子模块，用于计算数据D的ITC值ITC(D)和IN值IN(D)，其中 ITC(D)＝±D，IN(D)是记录在数据D中的信息，其具体为数据D的最初原 始数据变化到数据D期间所处理的次数；

第二子模块，用于根据ITC（D）和IN(D)并利用以下等式计算数据D 的权值Pri(D)：Pri(D)＝t₁×ITC(D)+t₂×IN(D)/T，其中t₁和t₂分别为表 示ITC（D）和IN(D)重要性的权重值，且其取值为0至1之间的小数，T 为调整IN(D)取值范围的值，其取值范围是大于1的整数；

第四模块，用于判断在哈希表中是否存在与该数据D具有相同键值的 数据组G(D)存在，若存在则更新该数据组G(D)的权值和数据列表，否则在 哈希列表中创建与该数据D相同键值的数据组G(D)，并进行初始化；第四 模块包括：

第三子模块，用于获得数据D的键值D_key，对该键值进行哈希函数处 理以获得一个唯一组标识K；

第四子模块，用于根据该唯一标识K在哈希表中进行查询，以判断是 否有键值为D_key的数据组G(D)，若有,则转入第五子模块，否则转入第六 子模块；

第五子模块，用于将数据D插入具有键值D_key的数据组G(D)中，然后 转入第七子模块；

第六子模块，用于创建一个键值为D_key的数据G(D)，并将数据D插入 数据组G(D)中，然后转向第八子模块；

第七子模块，用于采用以下公式更新哈希表中键值为D_key的数据组的 权值，Pri(G(D))＝Pri(G(D))+Pri(D)，然后转向第八子模块；

第八子模块，用于将数据组G(D)的权值设置为Pri(D)，然后转向步骤 第七子模块。

第五子模块，用于判断任务执行器是否空闲，如果是则进入第六模块， 否则返回第二模块；

第六模块，用于从哈希表中选择权值最大的一个数据组，将该数据组 对应的数据传送给任务执行器处理，然后进入第七模块；

第七模块，用于判断任务执行器中运行的应用程序是否结束，如果是 则过程结束，否则转入第八模块；

第八模块判断哈希表中是否还有未处理的数据组，如果有则返回第五 模块，否则返回第二模块。

本发明的调度器可存储在计算机可读介质中。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。