高度并发处理任务的记录和执行的制作方法
高度并发处理任务的记录和执行的制作方法
【专利摘要】一种依赖性数据结构描绘了处理任务。该依赖性数据结构包括多个部件，每个部件都封装代码单元。该依赖性数据结构可以包括针对部件间依赖性的依赖性弧线。并不被该依赖性数据结构内的部件所满足的依赖性可以被表示为伪部件。执行环境使用该依赖性数据结构和/或并发性状态元数据识别出能够执行（例如，具有满意依赖性）的部件。该执行环境能够识别并采用处理任务中的并发性，允许多个部件并行地执行。
【专利说明】高度并发处理任务的记录和执行
【技术领域】
[0001]本公开涉及并发处理并且，具体涉及高度并发处理任务的记录和执行。
【专利附图】
【附图说明】
[0002]图1描绘了依赖性数据结构的一个示例；
[0003]图2描绘了依赖性数据结构的另一个示例；
[0004]图3描绘了依赖性数据结构的另一个示例；
[0005]图4描绘了依赖性数据结构的另一个示例；
[0006]图5A描绘了依赖性数据结构的另一个示例；
[0007]图5B描绘了依赖性数据结构和并发性状态元数据的示例；
[0008]图5C描绘了依赖性数据结构和并发性状态元数据的另一个示例；
[0009]图6A描绘了从其提取子图形的依赖性数据结构；
[0010]图6B描绘了子图形的示例；
[0011]图6C描绘了包括伪部件的子图形的示例；
[0012]图6D描绘了具有输入参数依赖性的子图形的示例；
[0013]图6E描绘了被配置为产生输出的子图形的示例；
[0014]图6F描绘了依赖性数据结构内的子图形的示例；
[0015]图7描绘了依赖性数据结构；
[0016]图8是用于并发处理的方法的一个实施例的流程图；
[0017]图9是用于并发处理的另一种方法的一个实施例的流程图；和
[0018]图10是用于并发处理的系统的框图。
【具体实施方式】
[0019]许多处理任务包括未被加以利用的并发性。如这里所使用的，“并发性”是指能够同时或并行进行操作的两个或更多的处理任务(例如，期间没有相互依赖性)。研发人员可能由于潜在并发性的利用中所涉及的困难而并未对它们充分加以利用。通常，研发人员在设计时必须事先识别出并发性、创建定制代码(例如，多线程和/或线程间通信)等等，这导致了高成本并且向所产生的系统引入了潜在的问题。因此，需要一种用于记录处理并发性的系统且有效的方法以及一种被配置为有效利用那些并发性的执行管理器。
[0020]在一些实施例中，处理任务被安排为独立的“代码单元”。如这里所使用的，“代码单元”或“代码的单元”是指逻辑上有所不同的机器可执行指令的集合。代码单元可以是较大处理任务的一部分或部件。代码单元可以在非瞬时的机器可读存储介质上实现，诸如硬盘、非易失性存储、光学存储介质等。代码单元可以从非瞬时存储介质中进行加载以便由诸如通用处理器、应用特定集成电路(ASIC)、现场可编程门阵列(FPGA)等的计算设备来执行。
[0021]在代码单元之间可能存在着依赖性；例如，第一代码单元的输出可能是第二代码单元的所需输入。这些依赖性可以记录在依赖性数据结构中。如这里所使用的，依赖性数据结构是指在其中记录有代码单元间的依赖性的数据结构。依赖性数据结构可以被实施为图形，诸如有向无环图(DAG)、树、数组或任意适当的数据结构。代码单元可以被代表为该数据结构内的“部件”。如这里所使用的，部件是依赖性数据结构中封装代码单元并且允许其调用的节点。代码单元之间的依赖性可以被描绘成该数据结构中的部件之间的连接。如这里所使用的，当第一代码单元的输出被用来形成另一代码单元的所需输入时出现依赖性。在该数据结构中，“依赖部件”是指需要另一部件的输出的部件。相反地，“独立”代码单元是指并不需要另一部件的输出的代码单元。部件间的依赖性可以被描绘成部件之间的连接(例如，弧线)。
[0022]在一些实施例中，执行管理器实施依赖性数据结构所定义的处理任务。执行管理器使用依赖性数据结构而识别出能够执行的部件(例如，识别出其依赖性得以被满足的部件)。在一些情况下，代码单元可以具有由“外部”实体(例如，执行管理器以外的实体)所满足的依赖性。例如，部件可以依赖于单独I/o处理系统的输出、远程处理任务的输出等。外部实体可以在依赖性数据结构中被描绘成“伪部件”。如这里所使用的，伪部件代表依赖性数据结构之外的能够被该数据结构内的另一部件(或执行管理器)所满足的依赖性。相反地，对依赖性数据结构的其它部件(例如，数据结构的“内部部件”)的依赖性可以通过执行管理器执行与该部件相关联的代码单元而被解决。
[0023]如这里所使用的，“明确伪部件”是指被研发人员或其它实体明确添加至依赖性数据结构的伪部件。“隐含伪部件”是指在某型情况下，例如当该部件被指定为子图形(以下进行讨论)的入口部件时，被自动添加至依赖性数据结构(或者替代依赖性数据结构中的存在的部件)的伪部件。
[0024]图1描绘了依赖性数据结构100的一个示例。数据结构100可以在诸如硬盘、非易失性存储器、光学存储介质等的非瞬时的机器可读存储介质上实施。数据结构100也可以在诸如互联网协议(IP)网络、无线网络等的通信网络上进行通信。
[0025]在图1的示例中，数据结构100包括DAG;然而，本公开并不局限于此并且可以适于使用任意适当的数据结构。数据结构100包括独立部件110，其代表不依赖于数据结构100中的其它代码单元的代码单元。依赖部件112依赖于部件110的输出。该依赖性被描绘为部件110和部件112之间的依赖性弧线111。依赖性弧线111的“方向”表示部件110的输出是部件112的所需输入。
[0026]依赖性弧线111的“方向”表示部件112的代码单元不会被执行直至部件110产生了所需输出。弧线111可以包括描述该依赖性的元数据，诸如名称、数据类型、接口定义(例如，应用编程接口(API)、回叫记录等)、依赖性的“方向”，等等。
[0027]图2描绘了依赖性数据结构200的另一个示例，其中多个依赖部件212和214需要独立部件210的输出。这些依赖性由部件210以及部件212和214之间的依赖性弧线211所代表。如以上所描述的，弧线211可以包括与该依赖性的属性相关的元数据。
[0028]在图3所描绘的另一个示例中，依赖性数据结构包括依赖于多个部件(部件322和324)的输出的部件320。这些依赖性由相应的依赖性弧线321和323所代表。
[0029]图4描绘了包括伪部件(例如，外部依赖性)的依赖性数据结构400的示例。在图4的示例中，部件430依赖于外部的伪部件432的输出(由依赖性弧线431所代表)以及“非伪”部件434的输出(由依赖性弧线433所代表)。如以下所描述的，依赖性431可能无法由依赖性数据结构400的执行管理器所解决。相反地，依赖性433可以被执行部件434的代码单元以生成部件430所需的一个或多个输出的执行管理器所解决。
[0030]这里所公开的依赖性数据结果可以包括多个不同的“代(generation)”。如这里所使用，“代”是指部件之间的依赖性弧线的数量。第一代可以包括没有内部依赖性的独立部件。第二代可以包括依赖于来自第一代的输出的部件，等等。
[0031]图5A描绘了包括多个不同代的依赖性数据结构500。在图5A的示例中，数据结构500包括独立部件502、504和506，其可以包括数据结构500的“第一代”501。部件506代表伪部件。
[0032]独立部件的“第二代”(部件510、512和514)需要由第一代中的部件(部件502和/或504)生成的输出。部件512依赖于502和504两者的输出。
[0033]部件的“第三代”521 (包括部件520、522、524、526和528)需要由“第二代”中的部件所产生的输出。然而，依赖性可以跨越多个代。如图5A中所描绘的，部件524需要由处于“第二代”中的部件510所产生的输出以及由处于“第一代”中的部件502所生成的输出。因此，虽然在描述多级别依赖性数据结构时参考“代”可能是方便的，但是数据结构500中的部件之间的实际依赖性和/或与部件相关联的代码单元的并发执行并不局限于相邻的代。
[0034]依赖性数据结构500以(“第四代”531中的)一个或多个“输出”部件530和532“终止”。如这里所使用的，“输出”部件是指依赖性数据结构中产生不被该数据结构中的其它部件所需要的输出的部件。因此，输出部件可以是指产生依赖性数据结构自身的“输出”(例如，处理任务或子图形的输出)的部件。在图5A的示例中，部件530和532可以产生依赖性数据结构500的“输出”。
[0035]这里所描述的依赖性数据结构可以被用来对代码单元的并发执行进行管理。在一些实施例中，执行管理器(或其它实体)访问与处理任务相关联的依赖性数据结构。执行环境识别出能够执行(例如，具有“满意的”依赖性)的部件。最初，依赖性数据结构的独立(例如，叶子)部件可以是可执行的。独立(和其它)部件的执行可以满足依赖性数据结构中的其它部件的依赖性。如这里所使用的，“满意的部件”是指能够被执行的部件和/或其所需要的输入可用的部件。
[0036]执行环境可以保管依赖性数据结构的“并发性状态”。如这里所使用的，依赖性数据结构的“并发性状态”是指哪些部件已经被执行和/或哪些部件输出可用的“运行时间”代表形式。依赖性数据结构的并发性状态可以被保管在依赖性数据结构自身之中和/或另一单独数据结构中。当执行环境执行依赖性数据结构中的部件时，执行环境可以更新并发性状态以识别下一组能够执行的所满足的部件。
[0037]图5B描绘了已经适于包括并发性状态元数据的依赖性数据结构(图5A的依赖性数据结构500)的示例。并发性状态元数据表示部件502、504和510已经被执行(由部件502、504和510的“充满”状态所描绘)。可替换地或除此之外，并发性状态元数据可以包括那些依赖性弧线得到满足的指示(例如，指示出依赖性弧线541、542、543、544、545、551、552和553得到满足)。
[0038]使用依赖性数据结构503和/或并发性状态元数据，执行环境(或其它实体)可以识别出能够被执行的部件(其依赖性已经被满足的部件)。并发性状态元数据可以保管得到满足部件的指示。在图5B的示例中，并发性状态元数据包括识别出得到“满足”并且能够被执行的部件(例如，部件512、520、522和524)的相应指示符。并发性状态元数据还可以识别出其依赖性还没有得到满足的部件(例如，部件514、526、528、530和532)。
[0039]如图5B中所描绘的，一次可以有多于一个的可用于执行的部件。依赖性数据结构503 (和并发性状态元数据)表示部件512、520、522、524能够被执行。部件512、520、522和/或524的执行可以并行(并发地)进行。部件512、520、522和524之间的并行性由于依赖性数据结构中代码单元的代表以及并发性状态元数据的可用性而可以被轻易识别。
[0040]如图5B所示，并发操作的机会取决于依赖性得到满足的顺序。例如，部件514由于其对伪部件506的输出的依赖性还未得到满足而不可执行。然而，在其它实例下，部件可以以不同顺序完成执行，导致不同的并发性状态，并且不同的部件集合可用于并发操作。并发性状态的差异可能是由于许多不同的因素，其包括处理负载、通信延时、I/O时间等，但并不局限于此。例如，部件502可以对应于用于访问数据库中的数据的操作。在一些情况下(例如，当数据库上的负载很轻时)，该操作可以相对快速地完成。然而，在其它实例下(例如，当数据库被重度加载时)，部件的执行可能相对其它部件耗用更长时间。将部件部署到依赖性数据结构以及保管并发性状态允许对实时并发性加以利用而无论针对其中其它部件执行的顺序和/或速度的变量变化如何。
[0041]图5C描绘了包括并发性状态元数据的依赖性数据结构的另一个示例。在图5C的示例中，当部件被执行时，它们连同因此得到满足的依赖性弧线一起从数据结构505中被移除。因此，可用于执行的部件(例如，其依赖性得到满足的部件)被识别为数据结构505中的叶子节点。与图5B相同，图5C表示部件502、504和510已经被执行并且其输出可用于数据结构中的其它部件。这样，这些部件和相对应的依赖性弧线(图5B的弧线541、542、543、544、545、551、552和553)已经从数据结构505中移除。
[0042]可用于执行的部件(例如，其依赖性已经得到满足的部件)被识别为数据结构505中的叶子节点。在一些实施例中，并发性状态元数据可以进一步包括如以上所描述的相应指示符560。可替换地，可以通过遍历数据结构505以识别出(例如，独立于明确指示符560的)叶子节点来识别部件。
[0043]执行依赖性数据结构中的部件的代码单元所生成的输出可以被执行环境(或其它实体)所存储(或高速缓存)并且可被用作针对其它的依赖部件的输入。
[0044]在一些实施例中，可以从依赖性数据结构中提取出子图形。子图形可以包括一个或多个部件，包括“根”部件以及一个或多个“入口”部件。“根”部件(直接或间接)依赖于入口部件所产生的输出。“入口”部件是依赖于子图形之外所生成的输入的部件。在一些实施例中，子图形被构建为使得入口部件存在于源自于根部件的路径之上。因此，可以从根遍历子图形直至所有路径在叶子部件(没有依赖性的部件)或入口部件中终止。子图形可以被编码单元、部件等所封装和/或被暴露为代码单元、部件等，并且可以独立于从其中被提取出来的独立性数据结构而被执行。
[0045]图6A描绘了可以从其中提取出子图形的依赖性数据结构600的一个示例。依赖性数据结构600包括部件610、612、613、614、615、616、617和618，如以上所描述的，它们可以通过依赖性弧线进行互连。可以从依赖性数据结构600提取出包括“根”部件610和入口部件612的子图形620。部件613和616可以被包括在子图形中以满足根节点610的依赖性。图6B示出了如从依赖性数据结构600所提取出的子图形601。在一些实施例中，子图形的入口部件的依赖性可以被表式为伪部件。图6C描绘了包括代表部件612的依赖性的伪部件632。
[0046]如以上所讨论的，诸如伪部件632的伪部件代表外部依赖性(并未被特定依赖性数据结构或子图形内的部件所满足的依赖性)。因此，子图形(或者实施该子图形的执行环境)可以负责对依赖部件的输入/输出数据进行映射。
[0047]图6D图示了已经从图6C的子图形602所创建的函数。在图6D的示例中，伪部件632具有对可以代表子图形602的封装的函数“foo”的参数(argO)的逻辑依赖性。
[0048]在一些实施例中，子图形的“响应”或输出数值可以被返回和/或被用于其它处理任务和/或处理任务的输出。这样，子图形的封装代表形式可以被配置为捕捉其中部件的一个或多个输出并且使得这些输出可用于执行环境或其它实体。图6E图示了提供输出数据611的子图形602，可以使得该输出数据611可用于其它实体和/或部件。
[0049]如以上所讨论的，子图形可以被暴露为可执行代码单元。因此，在一些实施例中，子图形可以被封装在部件之内。图6F图示了包括封装以上所描述的子图形620的部件640的依赖性数据结构604。在图6F的示例中，部件640的执行使得封装在部件640内的子图形得以被执行，这导致了依赖性数据结构和/或子图形的分层或递归执行。
[0050]如以上所描述的，将处理任务表示为依赖性数据结构的部件允许执行环境(或其它实体)识别并发性并对其加以利用。此外，表现形式可以通过卸载并发性相关任务和/或将代码单元封装到单独部件中而简化代码开发。
[0051]以下示例说明了这里所教导的系统和方法如何对处理任务实施方式的复杂度进行简化。在该示例中，使用JavaScript定义了一组处理功能(或方法)。然而，本公开并不局限于此并且能够结合任意适当的编程语言或环境来实施。
[0052]var asyncGetRandomNum = function(callback) {
setTiineout(function() {
var nuin = Math.ceil(Math.randoiri() * 100)
callback(null，nuin);
1.250);
}；
var asyncDoubler = function(num9 callback) {
setTiineout(function() {
callback(null, nuin * 2);
1.250);
>.f
var asyncAdder = function(nuinl, num2, callback) {
setTimeout(function() {
callback(null9 numl+nuin2):
[0053]
},250);
}；
[0054]处理任务定义如下:
[0055]1.接受输入参数inValue;
[0056]2.调用 asyncGetRandomNum;
[0057]3.使用 inValue 和来自步骤 2 的 asyncGetRandomNum 的结果调用 asyncAdder;
[0058]4.使用来自步骤2的步骤asyncGetRandomNum的结果调用asyncDoubler;
[0059]5.使用步骤 2 和 3 的 asyncGetRandomNum 和 asyncAdder 的结果调用 asyncAdder;
[0060]6.使用步骤 5 的 asyncAdder 的结果调用 asyncDoubler;
[0061]7.使用步骤4和6的asyncDoubler的结果调用asyncAdder;以及
[0062]8.异步返回步骤7的asyncAdder的结果。
[0063]在第一方法中，处理任务依据以上所描述的处理步骤顺序实施:
[0064]II create our function
var func = function(inValue) {
asyncGetRandoinNuin(function(err, rndO) {
if(err) {
callback(err);
return;
}
asyncAdder(rnd(), inValue, function(err, addO) {
if (err) {
callback(err);
1eturn,
}
asyncDoubler(rnd(), function (err, dblO) {
[0065]
【权利要求】
1.一种用于高度并发处理的计算机实施的方法，包括: 执行以下步骤的计算机设备: 访问依赖性数据结构，所述依赖性数据结构包括: 多个部件，每个部件都代表相应代码单元，和连接所述部件的多条依赖性弧线，每条依赖性弧线都代表为了执行所述依赖性数据结构中的相对应的部件所要满足的依赖性， 保管并发性状态元数据以指示出得到满足的部件依赖性， 基于所述依赖性数据结构的所述并发性状态元数据识别所述依赖性数据结构中可用于执行的部件，以及 并发地执行所识别的部件。
2.根据权利要求1所述的方法，进一步包括，响应于执行所识别的部件而更新所述并发性状态元数据。
3.根据权利要求2所述的方法，其中，更新所述并发性状态元数据包括高速缓存通过执行所述依赖性数据结构的部件所生成的输出。
4.根据权利要求1所述的方法，进一步包括，在接收到来自所述依赖性数据结构以外的外部输入后更新所述并发性状态元数据，其中，所述外部输入不是通过执行所述依赖性数据结构的部件而生成的。
5.根据权利要求1所述的方法，其中，当部件的所有依赖性都满足时所述部件可用于执行。
6.根据权利要求1所述的方法，进一步包括: 响应于执行所识别部件而更新所述并发性状态元数据；以及 响应于所述更新，识别能够被用于执行的所述依赖性数据结构的部件并且执行所识别的部件直至所述依赖性数据结构中的每个部件都已经被执行。
7.根据权利要求1所述的方法，进一步包括: 响应于执行所识别部件更新所述并发性状态元数据；以及 响应于所述更新，识别能够被用于执行的所述依赖性数据结构的部件并且执行所识别的部件直至生成了所述依赖性数据结构的输出结果。
8.根据权利要求1所述的方法，其中，所述依赖性数据结构的执行生成输出结果，所述方法进一步包括如下之一:在人机界面设备上向用户显示输出结果、在网络上传送所述输出结果、以及在非瞬时计算机可读存储介质上存储所述输出结果。
9.根据权利要求1所述的方法，其中，使用执行平台执行所识别的部件，并且其中，所述执行平台是如下之一:虚拟机、线程、进程、脚本解释器、本地执行平台和仿真执行平台。
10.根据权利要求1所述的方法，进一步包括: 将处理任务的多个步骤封装至多个部件之中，每个部件包括相应代码单元以实施以下多个处理任务步骤之一； 识别部件依赖性，每个部件依赖性都代表为了执行所述部件中相应的一个所要满足的依赖性；以及 定义依赖性数据结构，所述依赖性数据结构包括: 所述多个部件，和 对所述部件进行互连的依赖性弧线，每条依赖性弧线都代表相应的所识别出的部件依赖性。
11.根据权利要求10所述的方法，其中，所识别的部件依赖性之一是没有被多个部件中的任何部件所满足的外部部件依赖性，所述方法进一步包括在所述依赖性数据结构中包括伪部件以代表所述外部依赖性。
12.—种非瞬时机器可读存储介质，包括使得机器执行一种用于高度并发处理的方法的指令，所述方法包括: 访问依赖性数据结构，所述依赖性数据结构包括: 多个部件，每个部件都代表相应的可执行代码单元，和连接所述部件的多条依赖性弧线，每条依赖性弧线都代表为了执行所述依赖性数据结构中的相对应的部件所要满足的依赖性， 保管并发性状态元数据以指示出得到满足的部件依赖性， 基于所述依赖性数据结构的所述并发性状态元数据识别所述依赖性数据结构中能够用于执行的多个部件，其中当所述并发性状态元数据指示出一部件的所有依赖性都得到满足时该部件能够用于执行；以及并发地执行多 个所识别的部件。
13.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括响应于执行所述多个所识别的部件而更新所述并发性状态元数据，其中，更新所述并发性状态元数据包括高速缓存一部件所生成的输出。
14.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括，在接收到来自所述依赖性数据结构以外的外部输入后更新所述并发性状态元数据，其中，所述外部输入不是通过执行所述依赖性数据结构的部件而生成的。
15.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括: 一旦通过执行所述依赖性数据结构内的一部件和接收外部输入之一而满足了所述依赖性数据结构内的依赖性，则更新所述并发性状态元数据； 响应于更新所述并发性状态元数据而识别能够用于执行的附加部件；以及 并发地执行所述附加的部件。
16.根据权利要求15所述的非瞬时机器可读存储介质，所述方法进一步包括: 更新所述并发性状态元数据，响应于所述更新，识别能够用于执行的附加部件，并且并发地执行所述附加部件直至生成所述依赖性数据结构的所识别的输出结果；以及 在人机界面设备上向用户显示所识别的输出结果，在网络上传送所识别的输出结果，并且将所识别的输出结果存储在非瞬时机器可读存储介质上。
17.根据权利要求12所述的非瞬时机器可读存储介质，其中，使用执行平台执行所识别的部件，并且其中，所述执行平台是如下之一:虚拟机、线程、进程、脚本解释器、本地执行平台和仿真执行平台。
18.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括: 将处理任务的多个步骤封装至多个部件之中，每个部件都包括相应的代码单元以实施所述多个处理任务步骤之一； 识别部件依赖性，每个部件依赖性都代表为了执行所述部件中相应的一个所要满足的依赖性；以及定义依赖性数据结构，所述依赖性数据结构包括 所述多个部件，和 对所述部件进行互连的依赖性弧线，每条依赖性弧线都代表相应的所识别出的部件依赖性。
19.根据权利要求18所述的非瞬时机器可读存储介质，其中，所识别出的部件依赖性之一是没有被所述多个部件中的任何部件所满足的外部部件依赖性，所述方法进一步包括在所述依赖性数据结构中包括伪部件以代表所述外部依赖性。
20.一种执行用于高度并发处理的方法的计算设备，包括: 存储器； 处理器；和在所述处理器上运行的执行环境，其中，所述执行环境被配置为: 访问在所述存储器上存储的依赖性数据结构，所述依赖性数据结构包括: 多个部件，每个部件都代表相应的可执行代码单元，和 连接所述部件的多条依赖性弧线，每条依赖性弧线都代表为了执行所述依赖性数据结构中的相应部件所要满足的依赖性，所述执行环境进一步被配置为: 保管指示出部件依赖性得到满足的并发性状态元数据， 基于所述依赖性数据结构的所述并发性状态元数据，识别所述依赖性数据结构中能够用于执行的多个部件，其中，当所述并发性状态元数据指示出一部件的所有依赖性都得到满足时所述部件能够用于执行， 在一个或多个执行平台内并发地执行多个所识别的部件，以及响应于生成相应输出的一个或多个所识别的部件而更新所述并发性状态元数据并且识别能够用于执行的附加部件。
【文档编号】G06F9/46GK103649907SQ201280021183
【公开日】2014年3月19日 申请日期:2012年2月24日 优先权日:2011年5月13日
【发明者】杰里米·D·马丁 申请人:益焦.com有限公司
【专利摘要】一种依赖性数据结构描绘了处理任务。该依赖性数据结构包括多个部件，每个部件都封装代码单元。该依赖性数据结构可以包括针对部件间依赖性的依赖性弧线。并不被该依赖性数据结构内的部件所满足的依赖性可以被表示为伪部件。执行环境使用该依赖性数据结构和/或并发性状态元数据识别出能够执行（例如，具有满意依赖性）的部件。该执行环境能够识别并采用处理任务中的并发性，允许多个部件并行地执行。
【专利说明】高度并发处理任务的记录和执行
【技术领域】
[0001]本公开涉及并发处理并且，具体涉及高度并发处理任务的记录和执行。
【专利附图】
【附图说明】
[0002]图1描绘了依赖性数据结构的一个示例；
[0003]图2描绘了依赖性数据结构的另一个示例；
[0004]图3描绘了依赖性数据结构的另一个示例；
[0005]图4描绘了依赖性数据结构的另一个示例；
[0006]图5A描绘了依赖性数据结构的另一个示例；
[0007]图5B描绘了依赖性数据结构和并发性状态元数据的示例；
[0008]图5C描绘了依赖性数据结构和并发性状态元数据的另一个示例；
[0009]图6A描绘了从其提取子图形的依赖性数据结构；
[0010]图6B描绘了子图形的示例；
[0011]图6C描绘了包括伪部件的子图形的示例；
[0012]图6D描绘了具有输入参数依赖性的子图形的示例；
[0013]图6E描绘了被配置为产生输出的子图形的示例；
[0014]图6F描绘了依赖性数据结构内的子图形的示例；
[0015]图7描绘了依赖性数据结构；
[0016]图8是用于并发处理的方法的一个实施例的流程图；
[0017]图9是用于并发处理的另一种方法的一个实施例的流程图；和
[0018]图10是用于并发处理的系统的框图。
【具体实施方式】
[0019]许多处理任务包括未被加以利用的并发性。如这里所使用的，“并发性”是指能够同时或并行进行操作的两个或更多的处理任务(例如，期间没有相互依赖性)。研发人员可能由于潜在并发性的利用中所涉及的困难而并未对它们充分加以利用。通常，研发人员在设计时必须事先识别出并发性、创建定制代码(例如，多线程和/或线程间通信)等等，这导致了高成本并且向所产生的系统引入了潜在的问题。因此，需要一种用于记录处理并发性的系统且有效的方法以及一种被配置为有效利用那些并发性的执行管理器。
[0020]在一些实施例中，处理任务被安排为独立的“代码单元”。如这里所使用的，“代码单元”或“代码的单元”是指逻辑上有所不同的机器可执行指令的集合。代码单元可以是较大处理任务的一部分或部件。代码单元可以在非瞬时的机器可读存储介质上实现，诸如硬盘、非易失性存储、光学存储介质等。代码单元可以从非瞬时存储介质中进行加载以便由诸如通用处理器、应用特定集成电路(ASIC)、现场可编程门阵列(FPGA)等的计算设备来执行。
[0021]在代码单元之间可能存在着依赖性；例如，第一代码单元的输出可能是第二代码单元的所需输入。这些依赖性可以记录在依赖性数据结构中。如这里所使用的，依赖性数据结构是指在其中记录有代码单元间的依赖性的数据结构。依赖性数据结构可以被实施为图形，诸如有向无环图(DAG)、树、数组或任意适当的数据结构。代码单元可以被代表为该数据结构内的“部件”。如这里所使用的，部件是依赖性数据结构中封装代码单元并且允许其调用的节点。代码单元之间的依赖性可以被描绘成该数据结构中的部件之间的连接。如这里所使用的，当第一代码单元的输出被用来形成另一代码单元的所需输入时出现依赖性。在该数据结构中，“依赖部件”是指需要另一部件的输出的部件。相反地，“独立”代码单元是指并不需要另一部件的输出的代码单元。部件间的依赖性可以被描绘成部件之间的连接(例如，弧线)。
[0022]在一些实施例中，执行管理器实施依赖性数据结构所定义的处理任务。执行管理器使用依赖性数据结构而识别出能够执行的部件(例如，识别出其依赖性得以被满足的部件)。在一些情况下，代码单元可以具有由“外部”实体(例如，执行管理器以外的实体)所满足的依赖性。例如，部件可以依赖于单独I/o处理系统的输出、远程处理任务的输出等。外部实体可以在依赖性数据结构中被描绘成“伪部件”。如这里所使用的，伪部件代表依赖性数据结构之外的能够被该数据结构内的另一部件(或执行管理器)所满足的依赖性。相反地，对依赖性数据结构的其它部件(例如，数据结构的“内部部件”)的依赖性可以通过执行管理器执行与该部件相关联的代码单元而被解决。
[0023]如这里所使用的，“明确伪部件”是指被研发人员或其它实体明确添加至依赖性数据结构的伪部件。“隐含伪部件”是指在某型情况下，例如当该部件被指定为子图形(以下进行讨论)的入口部件时，被自动添加至依赖性数据结构(或者替代依赖性数据结构中的存在的部件)的伪部件。
[0024]图1描绘了依赖性数据结构100的一个示例。数据结构100可以在诸如硬盘、非易失性存储器、光学存储介质等的非瞬时的机器可读存储介质上实施。数据结构100也可以在诸如互联网协议(IP)网络、无线网络等的通信网络上进行通信。
[0025]在图1的示例中，数据结构100包括DAG;然而，本公开并不局限于此并且可以适于使用任意适当的数据结构。数据结构100包括独立部件110，其代表不依赖于数据结构100中的其它代码单元的代码单元。依赖部件112依赖于部件110的输出。该依赖性被描绘为部件110和部件112之间的依赖性弧线111。依赖性弧线111的“方向”表示部件110的输出是部件112的所需输入。
[0026]依赖性弧线111的“方向”表示部件112的代码单元不会被执行直至部件110产生了所需输出。弧线111可以包括描述该依赖性的元数据，诸如名称、数据类型、接口定义(例如，应用编程接口(API)、回叫记录等)、依赖性的“方向”，等等。
[0027]图2描绘了依赖性数据结构200的另一个示例，其中多个依赖部件212和214需要独立部件210的输出。这些依赖性由部件210以及部件212和214之间的依赖性弧线211所代表。如以上所描述的，弧线211可以包括与该依赖性的属性相关的元数据。
[0028]在图3所描绘的另一个示例中，依赖性数据结构包括依赖于多个部件(部件322和324)的输出的部件320。这些依赖性由相应的依赖性弧线321和323所代表。
[0029]图4描绘了包括伪部件(例如，外部依赖性)的依赖性数据结构400的示例。在图4的示例中，部件430依赖于外部的伪部件432的输出(由依赖性弧线431所代表)以及“非伪”部件434的输出(由依赖性弧线433所代表)。如以下所描述的，依赖性431可能无法由依赖性数据结构400的执行管理器所解决。相反地，依赖性433可以被执行部件434的代码单元以生成部件430所需的一个或多个输出的执行管理器所解决。
[0030]这里所公开的依赖性数据结果可以包括多个不同的“代(generation)”。如这里所使用，“代”是指部件之间的依赖性弧线的数量。第一代可以包括没有内部依赖性的独立部件。第二代可以包括依赖于来自第一代的输出的部件，等等。
[0031]图5A描绘了包括多个不同代的依赖性数据结构500。在图5A的示例中，数据结构500包括独立部件502、504和506，其可以包括数据结构500的“第一代”501。部件506代表伪部件。
[0032]独立部件的“第二代”(部件510、512和514)需要由第一代中的部件(部件502和/或504)生成的输出。部件512依赖于502和504两者的输出。
[0033]部件的“第三代”521 (包括部件520、522、524、526和528)需要由“第二代”中的部件所产生的输出。然而，依赖性可以跨越多个代。如图5A中所描绘的，部件524需要由处于“第二代”中的部件510所产生的输出以及由处于“第一代”中的部件502所生成的输出。因此，虽然在描述多级别依赖性数据结构时参考“代”可能是方便的，但是数据结构500中的部件之间的实际依赖性和/或与部件相关联的代码单元的并发执行并不局限于相邻的代。
[0034]依赖性数据结构500以(“第四代”531中的)一个或多个“输出”部件530和532“终止”。如这里所使用的，“输出”部件是指依赖性数据结构中产生不被该数据结构中的其它部件所需要的输出的部件。因此，输出部件可以是指产生依赖性数据结构自身的“输出”(例如，处理任务或子图形的输出)的部件。在图5A的示例中，部件530和532可以产生依赖性数据结构500的“输出”。
[0035]这里所描述的依赖性数据结构可以被用来对代码单元的并发执行进行管理。在一些实施例中，执行管理器(或其它实体)访问与处理任务相关联的依赖性数据结构。执行环境识别出能够执行(例如，具有“满意的”依赖性)的部件。最初，依赖性数据结构的独立(例如，叶子)部件可以是可执行的。独立(和其它)部件的执行可以满足依赖性数据结构中的其它部件的依赖性。如这里所使用的，“满意的部件”是指能够被执行的部件和/或其所需要的输入可用的部件。
[0036]执行环境可以保管依赖性数据结构的“并发性状态”。如这里所使用的，依赖性数据结构的“并发性状态”是指哪些部件已经被执行和/或哪些部件输出可用的“运行时间”代表形式。依赖性数据结构的并发性状态可以被保管在依赖性数据结构自身之中和/或另一单独数据结构中。当执行环境执行依赖性数据结构中的部件时，执行环境可以更新并发性状态以识别下一组能够执行的所满足的部件。
[0037]图5B描绘了已经适于包括并发性状态元数据的依赖性数据结构(图5A的依赖性数据结构500)的示例。并发性状态元数据表示部件502、504和510已经被执行(由部件502、504和510的“充满”状态所描绘)。可替换地或除此之外，并发性状态元数据可以包括那些依赖性弧线得到满足的指示(例如，指示出依赖性弧线541、542、543、544、545、551、552和553得到满足)。
[0038]使用依赖性数据结构503和/或并发性状态元数据，执行环境(或其它实体)可以识别出能够被执行的部件(其依赖性已经被满足的部件)。并发性状态元数据可以保管得到满足部件的指示。在图5B的示例中，并发性状态元数据包括识别出得到“满足”并且能够被执行的部件(例如，部件512、520、522和524)的相应指示符。并发性状态元数据还可以识别出其依赖性还没有得到满足的部件(例如，部件514、526、528、530和532)。
[0039]如图5B中所描绘的，一次可以有多于一个的可用于执行的部件。依赖性数据结构503 (和并发性状态元数据)表示部件512、520、522、524能够被执行。部件512、520、522和/或524的执行可以并行(并发地)进行。部件512、520、522和524之间的并行性由于依赖性数据结构中代码单元的代表以及并发性状态元数据的可用性而可以被轻易识别。
[0040]如图5B所示，并发操作的机会取决于依赖性得到满足的顺序。例如，部件514由于其对伪部件506的输出的依赖性还未得到满足而不可执行。然而，在其它实例下，部件可以以不同顺序完成执行，导致不同的并发性状态，并且不同的部件集合可用于并发操作。并发性状态的差异可能是由于许多不同的因素，其包括处理负载、通信延时、I/O时间等，但并不局限于此。例如，部件502可以对应于用于访问数据库中的数据的操作。在一些情况下(例如，当数据库上的负载很轻时)，该操作可以相对快速地完成。然而，在其它实例下(例如，当数据库被重度加载时)，部件的执行可能相对其它部件耗用更长时间。将部件部署到依赖性数据结构以及保管并发性状态允许对实时并发性加以利用而无论针对其中其它部件执行的顺序和/或速度的变量变化如何。
[0041]图5C描绘了包括并发性状态元数据的依赖性数据结构的另一个示例。在图5C的示例中，当部件被执行时，它们连同因此得到满足的依赖性弧线一起从数据结构505中被移除。因此，可用于执行的部件(例如，其依赖性得到满足的部件)被识别为数据结构505中的叶子节点。与图5B相同，图5C表示部件502、504和510已经被执行并且其输出可用于数据结构中的其它部件。这样，这些部件和相对应的依赖性弧线(图5B的弧线541、542、543、544、545、551、552和553)已经从数据结构505中移除。
[0042]可用于执行的部件(例如，其依赖性已经得到满足的部件)被识别为数据结构505中的叶子节点。在一些实施例中，并发性状态元数据可以进一步包括如以上所描述的相应指示符560。可替换地，可以通过遍历数据结构505以识别出(例如，独立于明确指示符560的)叶子节点来识别部件。
[0043]执行依赖性数据结构中的部件的代码单元所生成的输出可以被执行环境(或其它实体)所存储(或高速缓存)并且可被用作针对其它的依赖部件的输入。
[0044]在一些实施例中，可以从依赖性数据结构中提取出子图形。子图形可以包括一个或多个部件，包括“根”部件以及一个或多个“入口”部件。“根”部件(直接或间接)依赖于入口部件所产生的输出。“入口”部件是依赖于子图形之外所生成的输入的部件。在一些实施例中，子图形被构建为使得入口部件存在于源自于根部件的路径之上。因此，可以从根遍历子图形直至所有路径在叶子部件(没有依赖性的部件)或入口部件中终止。子图形可以被编码单元、部件等所封装和/或被暴露为代码单元、部件等，并且可以独立于从其中被提取出来的独立性数据结构而被执行。
[0045]图6A描绘了可以从其中提取出子图形的依赖性数据结构600的一个示例。依赖性数据结构600包括部件610、612、613、614、615、616、617和618，如以上所描述的，它们可以通过依赖性弧线进行互连。可以从依赖性数据结构600提取出包括“根”部件610和入口部件612的子图形620。部件613和616可以被包括在子图形中以满足根节点610的依赖性。图6B示出了如从依赖性数据结构600所提取出的子图形601。在一些实施例中，子图形的入口部件的依赖性可以被表式为伪部件。图6C描绘了包括代表部件612的依赖性的伪部件632。
[0046]如以上所讨论的，诸如伪部件632的伪部件代表外部依赖性(并未被特定依赖性数据结构或子图形内的部件所满足的依赖性)。因此，子图形(或者实施该子图形的执行环境)可以负责对依赖部件的输入/输出数据进行映射。
[0047]图6D图示了已经从图6C的子图形602所创建的函数。在图6D的示例中，伪部件632具有对可以代表子图形602的封装的函数“foo”的参数(argO)的逻辑依赖性。
[0048]在一些实施例中，子图形的“响应”或输出数值可以被返回和/或被用于其它处理任务和/或处理任务的输出。这样，子图形的封装代表形式可以被配置为捕捉其中部件的一个或多个输出并且使得这些输出可用于执行环境或其它实体。图6E图示了提供输出数据611的子图形602，可以使得该输出数据611可用于其它实体和/或部件。
[0049]如以上所讨论的，子图形可以被暴露为可执行代码单元。因此，在一些实施例中，子图形可以被封装在部件之内。图6F图示了包括封装以上所描述的子图形620的部件640的依赖性数据结构604。在图6F的示例中，部件640的执行使得封装在部件640内的子图形得以被执行，这导致了依赖性数据结构和/或子图形的分层或递归执行。
[0050]如以上所描述的，将处理任务表示为依赖性数据结构的部件允许执行环境(或其它实体)识别并发性并对其加以利用。此外，表现形式可以通过卸载并发性相关任务和/或将代码单元封装到单独部件中而简化代码开发。
[0051]以下示例说明了这里所教导的系统和方法如何对处理任务实施方式的复杂度进行简化。在该示例中，使用JavaScript定义了一组处理功能(或方法)。然而，本公开并不局限于此并且能够结合任意适当的编程语言或环境来实施。
[0052]var asyncGetRandomNum = function(callback) {
setTiineout(function() {
var nuin = Math.ceil(Math.randoiri() * 100)
callback(null，nuin);
1.250);
}；
var asyncDoubler = function(num9 callback) {
setTiineout(function() {
callback(null, nuin * 2);
1.250);
>.f
var asyncAdder = function(nuinl, num2, callback) {
setTimeout(function() {
callback(null9 numl+nuin2):
[0053]
},250);
}；
[0054]处理任务定义如下:
[0055]1.接受输入参数inValue;
[0056]2.调用 asyncGetRandomNum;
[0057]3.使用 inValue 和来自步骤 2 的 asyncGetRandomNum 的结果调用 asyncAdder;
[0058]4.使用来自步骤2的步骤asyncGetRandomNum的结果调用asyncDoubler;
[0059]5.使用步骤 2 和 3 的 asyncGetRandomNum 和 asyncAdder 的结果调用 asyncAdder;
[0060]6.使用步骤 5 的 asyncAdder 的结果调用 asyncDoubler;
[0061]7.使用步骤4和6的asyncDoubler的结果调用asyncAdder;以及
[0062]8.异步返回步骤7的asyncAdder的结果。
[0063]在第一方法中，处理任务依据以上所描述的处理步骤顺序实施:
[0064]II create our function
var func = function(inValue) {
asyncGetRandoinNuin(function(err, rndO) {
if(err) {
callback(err);
return;
}
asyncAdder(rnd(), inValue, function(err, addO) {
if (err) {
callback(err);
1eturn,
}
asyncDoubler(rnd(), function (err, dblO) {
[0065]
【权利要求】
1.一种用于高度并发处理的计算机实施的方法，包括: 执行以下步骤的计算机设备: 访问依赖性数据结构，所述依赖性数据结构包括: 多个部件，每个部件都代表相应代码单元，和连接所述部件的多条依赖性弧线，每条依赖性弧线都代表为了执行所述依赖性数据结构中的相对应的部件所要满足的依赖性， 保管并发性状态元数据以指示出得到满足的部件依赖性， 基于所述依赖性数据结构的所述并发性状态元数据识别所述依赖性数据结构中可用于执行的部件，以及 并发地执行所识别的部件。
2.根据权利要求1所述的方法，进一步包括，响应于执行所识别的部件而更新所述并发性状态元数据。
3.根据权利要求2所述的方法，其中，更新所述并发性状态元数据包括高速缓存通过执行所述依赖性数据结构的部件所生成的输出。
4.根据权利要求1所述的方法，进一步包括，在接收到来自所述依赖性数据结构以外的外部输入后更新所述并发性状态元数据，其中，所述外部输入不是通过执行所述依赖性数据结构的部件而生成的。
5.根据权利要求1所述的方法，其中，当部件的所有依赖性都满足时所述部件可用于执行。
6.根据权利要求1所述的方法，进一步包括: 响应于执行所识别部件而更新所述并发性状态元数据；以及 响应于所述更新，识别能够被用于执行的所述依赖性数据结构的部件并且执行所识别的部件直至所述依赖性数据结构中的每个部件都已经被执行。
7.根据权利要求1所述的方法，进一步包括: 响应于执行所识别部件更新所述并发性状态元数据；以及 响应于所述更新，识别能够被用于执行的所述依赖性数据结构的部件并且执行所识别的部件直至生成了所述依赖性数据结构的输出结果。
8.根据权利要求1所述的方法，其中，所述依赖性数据结构的执行生成输出结果，所述方法进一步包括如下之一:在人机界面设备上向用户显示输出结果、在网络上传送所述输出结果、以及在非瞬时计算机可读存储介质上存储所述输出结果。
9.根据权利要求1所述的方法，其中，使用执行平台执行所识别的部件，并且其中，所述执行平台是如下之一:虚拟机、线程、进程、脚本解释器、本地执行平台和仿真执行平台。
10.根据权利要求1所述的方法，进一步包括: 将处理任务的多个步骤封装至多个部件之中，每个部件包括相应代码单元以实施以下多个处理任务步骤之一； 识别部件依赖性，每个部件依赖性都代表为了执行所述部件中相应的一个所要满足的依赖性；以及 定义依赖性数据结构，所述依赖性数据结构包括: 所述多个部件，和 对所述部件进行互连的依赖性弧线，每条依赖性弧线都代表相应的所识别出的部件依赖性。
11.根据权利要求10所述的方法，其中，所识别的部件依赖性之一是没有被多个部件中的任何部件所满足的外部部件依赖性，所述方法进一步包括在所述依赖性数据结构中包括伪部件以代表所述外部依赖性。
12.—种非瞬时机器可读存储介质，包括使得机器执行一种用于高度并发处理的方法的指令，所述方法包括: 访问依赖性数据结构，所述依赖性数据结构包括: 多个部件，每个部件都代表相应的可执行代码单元，和连接所述部件的多条依赖性弧线，每条依赖性弧线都代表为了执行所述依赖性数据结构中的相对应的部件所要满足的依赖性， 保管并发性状态元数据以指示出得到满足的部件依赖性， 基于所述依赖性数据结构的所述并发性状态元数据识别所述依赖性数据结构中能够用于执行的多个部件，其中当所述并发性状态元数据指示出一部件的所有依赖性都得到满足时该部件能够用于执行；以及并发地执行多 个所识别的部件。
13.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括响应于执行所述多个所识别的部件而更新所述并发性状态元数据，其中，更新所述并发性状态元数据包括高速缓存一部件所生成的输出。
14.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括，在接收到来自所述依赖性数据结构以外的外部输入后更新所述并发性状态元数据，其中，所述外部输入不是通过执行所述依赖性数据结构的部件而生成的。
15.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括: 一旦通过执行所述依赖性数据结构内的一部件和接收外部输入之一而满足了所述依赖性数据结构内的依赖性，则更新所述并发性状态元数据； 响应于更新所述并发性状态元数据而识别能够用于执行的附加部件；以及 并发地执行所述附加的部件。
16.根据权利要求15所述的非瞬时机器可读存储介质，所述方法进一步包括: 更新所述并发性状态元数据，响应于所述更新，识别能够用于执行的附加部件，并且并发地执行所述附加部件直至生成所述依赖性数据结构的所识别的输出结果；以及 在人机界面设备上向用户显示所识别的输出结果，在网络上传送所识别的输出结果，并且将所识别的输出结果存储在非瞬时机器可读存储介质上。
17.根据权利要求12所述的非瞬时机器可读存储介质，其中，使用执行平台执行所识别的部件，并且其中，所述执行平台是如下之一:虚拟机、线程、进程、脚本解释器、本地执行平台和仿真执行平台。
18.根据权利要求12所述的非瞬时机器可读存储介质，所述方法进一步包括: 将处理任务的多个步骤封装至多个部件之中，每个部件都包括相应的代码单元以实施所述多个处理任务步骤之一； 识别部件依赖性，每个部件依赖性都代表为了执行所述部件中相应的一个所要满足的依赖性；以及定义依赖性数据结构，所述依赖性数据结构包括 所述多个部件，和 对所述部件进行互连的依赖性弧线，每条依赖性弧线都代表相应的所识别出的部件依赖性。
19.根据权利要求18所述的非瞬时机器可读存储介质，其中，所识别出的部件依赖性之一是没有被所述多个部件中的任何部件所满足的外部部件依赖性，所述方法进一步包括在所述依赖性数据结构中包括伪部件以代表所述外部依赖性。
20.一种执行用于高度并发处理的方法的计算设备，包括: 存储器； 处理器；和在所述处理器上运行的执行环境，其中，所述执行环境被配置为: 访问在所述存储器上存储的依赖性数据结构，所述依赖性数据结构包括: 多个部件，每个部件都代表相应的可执行代码单元，和 连接所述部件的多条依赖性弧线，每条依赖性弧线都代表为了执行所述依赖性数据结构中的相应部件所要满足的依赖性，所述执行环境进一步被配置为: 保管指示出部件依赖性得到满足的并发性状态元数据， 基于所述依赖性数据结构的所述并发性状态元数据，识别所述依赖性数据结构中能够用于执行的多个部件，其中，当所述并发性状态元数据指示出一部件的所有依赖性都得到满足时所述部件能够用于执行， 在一个或多个执行平台内并发地执行多个所识别的部件，以及响应于生成相应输出的一个或多个所识别的部件而更新所述并发性状态元数据并且识别能够用于执行的附加部件。
【文档编号】G06F9/46GK103649907SQ201280021183
【公开日】2014年3月19日 申请日期:2012年2月24日 优先权日:2011年5月13日
【发明者】杰里米·D·马丁 申请人:益焦.com有限公司
最新回复(0)