异步处理器架构上的死锁检测及同步感知优化的方法

摘要

本发明提供了一种用于提高在异步处理器架构中执行的应用程序的性能的方法。在一个实施例中，一种用于提高编译后的同步源代码在异步处理器架构上的执行性能的方法包括：处理系统接收包括同步指令的同步源代码，其中，所述同步指令用于在所述异步处理器架构的不同流水线上同步执行所述同步源代码。所述方法还包括：所述处理系统分析所述同步源代码以判断所述同步源代码是否包括异常代码条件。所述方法还包括：在确定所述同步源代码不包括异常代码条件之后，所述处理系统输出优化同步源代码，其中，所述优化同步源代码是通过对所述同步源代码执行校正动作生成的，所述校正动作用于校正所述同步源代码中的不准确、不一致或低效的同步指令。

说明书

技术领域

本发明一般涉及一种用于提高编译后的源代码在异步处理器架构上的执行性能的系统和方法。

背景技术

异步处理器架构由多个流水线(pipeline)组成，这些流水线通过共享内存进行通信并要求显式同步。源代码在由编译器转换(例如，编译)成目标代码以便在异步处理器架构上执行时，要求将同步指令插入到源代码中，以使得在编译源代码时生成的目标代码能够在异步处理器架构上正确执行。但是，将同步指令添加到源代码中以使得目标代码能够在异步处理器架构上执行，如果这些同步指令添加错误，则会导致死锁条件、未定义行为条件和数据竞争条件等异常代码(broken code)条件。对于复杂的源代码，同步指令添加错误的风险很大。例如，当线程正在等待特定的“事件”被设置或指示，而事件永远不会被设置或指示时，线程可能会无限期阻塞。这样一来，当在异步处理器架构上执行编译后的源代码时，将同步指令错误添加到源代码中会产生死锁条件。此外，即使同步指令添加正确(正确插入到源代码中，因此没有导致异常代码条件)，源代码在编译成目标代码以便在异步处理器架构上执行时，可能仍然是低效的，从而导致目标代码的执行时间超出所需时间。而且，源代码中存在同步指令可能会限制编译器对源代码的一些优化，当使用同步指令时，执行这些指令可能并不总是安全的。

发明内容

根据一个实施例，一种提高编译后的同步源代码在异步处理器架构上的执行性能的方法包括：处理系统接收包括同步指令的同步源代码，其中，所述同步指令用于在所述异步处理器架构的不同流水线上同步执行所述同步源代码。所述方法还包括：判断所述同步源代码是否包括异常代码条件。所述方法还包括：在确定所述同步的源代码不包括异常代码条件之后，所述处理系统根据所述同步源代码的优化分析，输出所述同步源代码中的不准确、不一致或低效指令的指示。

根据一个实施例，一种数据处理系统包括：存储指令的存储器；与所述存储器通信的一个或多个处理器。所述一个或多个处理器执行所述指令以：接收包括同步指令的同步源代码，其中，所述同步指令用于在流水线型异步处理器架构的不同流水线上同步执行所述同步源代码。所述一个或多个处理器还执行所述指令以：判断所述同步源代码是否包括异常代码条件。所述一个或多个处理器还执行所述指令以：在确定所述同步源代码不包括异常代码条件之后，根据所述同步源代码的优化分析输出所述同步源代码中的不准确、不一致或低效指令的指示。

根据一个实施例，一种数据处理系统包括：接收器，用于接收包含指令的软件程序，其中，所述指令包括同步指令，所述同步指令用于在异步计算架构的处理单元的不同流水线上同步执行所述指令。所述数据处理系统还包括：分析器，用于分析所述同步源代码中的同步指令以判断所述同步源代码是否包括死锁条件。所述数据处理系统还包括：优化器，用于：在确定所述同步源代码不包括异常代码条件之后，根据所述同步源代码的优化分析，输出所述同步源代码中的不准确、不一致或低效指令的指示。

在一个或多个上述方面中，所述方法还包括：在确定所述同步源代码包括异常源代码条件之后，所述处理系统输出报告，其中，所述报告包括指示所述异常源代码条件的信息。

在一个或多个上述方面中，输出指示包括：输出报告，其中，所述报告包括从所述优化分析中获取到的信息。

在一个或多个上述方面中，所述异常代码条件是死锁条件、未定义行为条件和数据竞争条件中的一种。

在一个或多个上述方面中，所述异常代码条件是根据所述同步源代码的所述同步指令中的不配对情况确定的死锁条件。

在一个或多个上述方面中，所述同步指令包括等待事件和设置事件，所述同步指令中的不配对情况包括等待事件没有对应的设置事件或设置事件没有对应的等待事件。

在一个或多个上述方面中，当所述同步源代码包括等待事件对应的缺失设置事件时，所述方法和数据处理系统发出所述同步源代码包括异常源代码条件的警告。

在一个或多个上述方面中，所述校正动作包括：提供报告，其中，所述报告包括建议程序员移除所述等待事件或插入所述对应的设置事件。

在一个或多个上述方面中，所述不准确、不一致或低效的同步指令包括冗余同步指令。

在一个或多个上述方面中，所述校正动作包括：移除所述冗余同步指令。

在一个或多个上述方面中，所述校正动作包括：减少所述同步源代码中的同步控制开销。

在一个或多个上述方面中，所述减少同步控制开销包括：合并所述同步源代码中的冗余同步指令。

在一个或多个上述方面中，所述减少同步控制开销包括：当所述同步源代码中的在等待事件或屏障占用的所述同步源代码中的第一位置与所述等待事件或所述屏障移动到的第二位置之间没有条件依赖所述等待事件时，在所述同步源代码中将所述等待事件或所述屏障上移。

在一个或多个上述方面中，所述减少同步控制开销包括：当所述同步指令中没有条件依赖位于所述同步源代码中的第一位置和所述同步源代码中的第二位置之间的设置事件时，将所述设置事件从所述第一位置下移到所述第二位置。

在一个或多个上述方面中，所述减少同步控制开销包括：当所述同步源代码中没有条件使用所述同步源代码中的一个循环内的同步指令时，将所述同步指令提升到所述循环之外。

在一个或多个上述方面中，所述方法和数据处理系统根据所述同步源代码生成阶段图，其中，所述分析所述同步源代码以判断所述同步源代码是否包括异常代码条件包括：根据所述阶段图判断所述同步源代码是否包括异常代码条件。

在一个或多个上述方面中，使用阶段图执行所述同步源代码的所述优化分析。

在一个或多个上述方面中，根据所述同步源代码的诊断分析判断所述同步源代码是否包括异常代码条件。

在一个或多个上述方面中，使用阶段图执行所述同步源代码的所述优化分析。

在一个或多个上述方面中，根据所述同步源代码的诊断分析判断所述同步源代码是否包括异常代码条件。

本发明的一个或多个实施例的优点是提供了一种改进系统。所述系统检测到同步源代码中的由于不正确同步而产生的异常代码条件，以及当未在所述同步源代码中检测到异常代码条件时，优化所述同步源代码，以便在特定的流水线型异步处理器架构上进行编译和执行。本发明的一个或多个实施例的另一个优点是减少了同步指令开销。减少所述同步指令开销会减少同步源代码中的控制流指令(例如，if条件句)，从而使编译后的同步源代码在流水线型异步处理器架构上的执行时间减少、能效提高。

附图说明

为了更完整地理解本发明及其优点，现在参考下文结合附图进行的描述，其中：

图1示出了通用异步处理器架构的一个示例；

图2是异步处理器架构的一个实施例；

图3示出了不包括同步指令的源代码的一个示例、图2中的异步处理器架构的各个流水线的对应示意表示，以及每个流水线呈现的冲突；

图4是正确同步源代码的一个示例的示意图，以及图2中的异步处理器架构的各个流水线的对应示意表示；

图5是包括死锁条件的源代码的一个示例的示意图；

图6是移除冗余同步指令的机会点的示例性阶段依赖关系图；

图7是同步下的相同代码合并优化的同步源代码的示意图；

图8是同步原语的循环提升的一个示例的示意图；

图9是示例性同步源代码以及同步源代码中包括的各个阶段的示意图；

图10是迭代空间中的示例性同步指令的示意图；

图11是异步处理器架构中的同步源代码的性能优化方法的一个实施例的流程图；

图12是阶段图的示例性实施例的示意图；

图13是阶段图的示例性实施例的示意图；

图14是代码语言如何暴露用于阶段图生成的阶段抽象的示意图；

图15是用于构建阶段图的示例性方法的流程图；

图16是用于使用阶段图检测不包括异常代码条件的同步源代码中的不准确、不一致和低效指令的示例性方法的流程图；

图17示出了用于检测同步源代码中的异常代码条件和优化同步源代码的示例性系统；

图18示出了可以安装在计算设备中的用于执行本文所述方法的示例性处理系统的框图。

具体实施方式

下文将详细论述实施例的制作和使用。但应理解，本发明提供的许多适用发明概念可以体现在多种具体环境中。所论述的具体实施例仅仅说明用以制作和使用本发明，而不限制本发明的范围。

本发明通过提供一种处理系统解决同步源代码中的错误同步使用的问题。所述同步源代码被编译成目标代码以便在异步处理器架构上执行。所述处理系统分析所述同步源代码以检测所述源同步代码中的异常代码条件；当检测到异常源代码条件时，所述处理系统输出报告。程序员可以使用所述报告来校正(例如，重写)所述同步源代码，从而移除所述异常源代码条件。此外，当所述处理系统未检测到异常代码条件时，所述处理系统分析所述同步源，以识别所述同步源代码的同步指令中的低效、不一致或不准确指令；对所述同步源代码的同步指令执行校正动作，以生成所述同步源代码中的低效、不一致或不准确指令得到校正的优化同步源代码；输出所述优化同步源代码，其中，所述优化同步源代码可以被编译成目标代码以便在所述异步处理器架构上执行。本文所使用的术语“同步源代码”是指包括同步指令的源代码，这些同步指令由程序员手动插入或者自动生成，以确保编译后的同步源代码(例如，编译器从同步源代码中生成的目标代码)能够在特定的异步处理器架构上执行。术语“优化(optimize/optimized/optimizing/and optimization)”并不意味着得到的同步源代码必须是所得到的同步源代码中的同步指令的最佳组织，也不一定会使编译器从所得到的同步源代码中生成的目标代码在特定的异步处理器架构上的执行速度最快，而是仅仅意味着：相比于使用所公开的方法和处理系统之前的源代码，所述源代码在一个或多个方面(例如，速度、一些冗余同步语句的消除等)得到改进。

分析同步源代码以识别异常源代码条件对于确保可以对同步源代码执行不同的同步感知优化至关重要。具体地，如果优化包括移动或移除同步指令，则分析应该确认这种转换是安全的。此外，对于复杂的源代码，编写正确的同步指令可能会容易出错，导致同步源代码中的死锁条件、未定义行为条件或数据竞争条件等异常源代码条件。因此，分析同步源代码中的同步指令对于程序员了解潜在的异常代码条件很有用。

本文公开了用于分析同步源代码以检测异常源代码条件的方法和处理系统，以及用于对同步源代码执行同步感知优化的方法和系统。如本文所述，同步感知优化是只有在编译器的优化器理解同步源代码的同步指令(例如，理解源代码中同步事件的设置和等待事件之间的依赖关系)的时候才能对同步源代码进行的优化。同步源代码在被编译成目标代码以便在异步处理器架构上执行之前，可以静态地划分为不同的阶段，其中，不同的阶段之间需要显式同步。在大多数情况下，同步指令在迭代空间中表示，并且可以对其进行静态分析以反映阶段之间的运行依赖关系。因此，一方面，公开了一种数据结构，所述数据结构包括对同步源代码执行异常代码条件检测和/或同步感知优化所需要的信息。另一方面，还公开了一种从现有同步源代码中构建这种数据结构的方法，以及使用这种数据结构执行异常代码条件检测和多种同步感知优化的方法。

本发明的一个或多个实施例的优点是，通过提供一种处理系统提高难以对系统编程的可编程性。所述处理系统检测同步源代码中的由于将同步指令错误插入到源代码中产生的死锁条件、未定义行为条件或数据竞争条件等异常代码条件。本发明的一个或多个实施例的另一个优点是减少了同步指令开销。减少所述同步指令开销会减少同步源代码中的控制流指令(例如，if条件句)，从而缩短执行时间并提高能效。

图1示出了异步处理器架构100的一个示例。架构100包括多个流水线102和多个内存空间104。架构100支持对不同内存空间104的异步操作。这些异步操作可以是内存转移(通过直接内存访问(Direct Memory Access，DMA))或内存计算，其中，操作的源和目的地在内存104中。不同类型的操作属于不同的流水线102。在不同的流水线上执行的操作(也称为指令)可以并行发出。来自同一个流水线的操作可以背靠背发出，这样，一个操作在前一操作提交其结果之前开始执行。不同的流水线102可以通过共享内存空间104传送数据。

图2是异步处理器架构200的一个实施例。为了简单起见，示出了包括4个流水线的异步处理器架构200为例。架构200包括4个流水线202、206、208和212以及两个内存空间204和210。因为流水线202(流水线1)和流水线212(例如，流水线3)的操作都不依赖另一流水线获得的结果，所以流水线202和流水线212并行操作。类似地，流水线206(流水线4)和流水线208(流水线5)并行操作。因为流水线202使用由流水线206和208执行的操作的结果，所以流水线206和208与流水线202串行操作。

图3示出了由程序员编写的源代码302的一个示例。源代码302在被编译成目标代码时能够在图2中的异步处理架构200上执行。图3还示出了图2中的异步处理架构200的各个流水线202、212和206的对应示意表示304，以及由于源代码302不包括同步指令，每个流水线202、212和206呈现的数据冲突(hazard)。数据冲突由图3所示的箭头表示。图3所示的示例性源代码302包括语句(例如，for(int i＝0；i

如图3所示，由于在流水线开始其操作之前，流水线206(流水线4)执行与指令306相关联的机器指令的结果需要能够供流水线202使用，所以流水线206(流水线4)和流水线202(流水线1)之间以及流水线202(流水线1)和流水线212(流水线3)之间存在写后读(Read-After-Write，RAW)数据冲突。然而，由于上述语句(例如，上述for循环)，还存在其它数据冲突。例如，迭代“i”中的流水线206(流水线4)需要先全部完成其写入，然后，迭代“i+1”中的流水线206(流水线4)开始执行与指令308相关联的机器指令。因此，流水线308(流水线1)和流水线306(流水线4)存在写后写(Write-After-Write，WAW)数据冲突。此外，最好保证迭代“i+1”中的流水线306(例如，流水线4)只在迭代“i”中的流水线202(流水线1)执行完与指令相关联的机器指令之后执行与指令306相关联的机器指令(即，存在读后写(Write-After-Read，WAR)数据冲突)。因此，为使上文的源代码不存在上述冲突，需要使用异步处理器架构200支持的同步指令。

如图3所示，当程序员编写的源代码将由编译器编译成目标代码以便在架构100或200等特定的异步处理器架构上执行时，必须修改源代码以包括同步指令，以便加强数据依赖关系并避免数据冲突。修改源代码(以下简称原始源代码)，从而在以下一种场景下生成同步源代码：(1)当程序员将同步指令显式插入到原始源代码中(诊断信息和报告优化机会点在这些情况下有关联)时直接生成；(2)在(a)程序员只描述数据依赖关系并且同步指令自动插入到原始源代码中(在一些方面，后续的编译器优化对于使自动生成的同步源代码接近手动效率可能是必不可少的)；(b)源代码自动从所需功能的数学表示中生成(例如，自动库生成(auto-library-generation))(类似于前一情况，在一些方面，后续的编译器优化对于使自动生成的同步代码接近手动(优化)效率可能是必不可少的)时间接生成。

图4是不包括死锁条件、未定义行为条件和数据竞争条件等任何异常代码条件的同步源代码(例如，包括同步指令的源代码)的一个示例的示意图400。示意图400包括同步源代码402以及图2中的架构200的流水线202、206和212的示意图404。同步源代码402包括语句401、403、405、407和409，指令406、408和410以及同步指令A

图5是与图4所示的同步源代码402类似的同步源代码502的示意图500。然而，同步源代码502中移除了一个语句(图5中斜体所示的if(i>0))，这导致同步代码506存在死锁条件。由于编译后的同步源代码在异步处理架构上执行时不会终止，所以同步源代码502中的死锁条件使同步源代码502的优化对编译器无用。同步源代码502包括语句501、503、505、507、509和511，指令506、508个510以及同步指令A

同步源代码502中所示的死锁条件是由于同步指令的一对wait_event和set_event错误地插入到原始源代码中而引起的。例如，如果在运行时调用了wait_event，而之前没有调用对应的set_event，则会产生死锁条件。例如，图5所示的同步源代码502示出了由于同步指令对B

图5中的同步源代码502所说明的另一个问题是，同步源代码502包括不一致、不准确或低效的同步指令。具体而言，同步源代码502包括冗余同步指令(由程序员添加或如上所述自动添加)，同样增加了控制指令开销。例如，根据图5所示的同步源代码502，可以生成如图6所示的“happens before”关系图(或称为“阶段依赖关系(stage dependency)”图)。图6是示例性阶段依赖关系图600，示出了移除冗余同步指令的机会点。依赖关系图600示出了在同步源代码502的迭代i中执行与指令506相关联的机器指令的流水线206(流水线4)的表示602，在同步源代码502的迭代i中执行与指令508相关联的机器指令的流水线202(流水线1)的表示604，以及在源代码502的迭代i+1中执行与指令506相关联的机器指令的流水线206(流水线4)的表示606。同步指令A

图7是包括多个相同条件语句的同步源代码702的示意图700。可以合并这些条件语句以优化同步源代码502，从而移除(例如，校正)同步源代码的同步指令中的不一致、不准确或低效指令，以便提高编译后的同步源代码在异步处理器架构上的执行性能。由于图7所示的同步源代码不包括异常代码条件，所以可能得到优化。同步源代码702包括三个指令704、706和708，若干个条件语句(条件)710、712、714、716、718和720，以及同步指令。使用条件语句来保护同步指令是很常见的。在许多情况下，这些条件是常见的。因此，只要移动同步指令是安全的，就可以在相同条件下合并这些同步指令。所以本文公开了分析同步源代码以合并同步指令。在图7所示的示例中，条件710、712、714和716是相同条件，条件718和720是相同条件。因此，一方面，在安全的情况下，条件710、712、714和716可以合并为单个条件语句，条件718和720可以合并为单个条件语句。对于屏障等同步指令，只要支配方(dominating)同步指令和屏障当前位置之间的路径上不存在同一流水线的任何阶段，则认为将相同条件的同步指令合并为单个支配方同步指令是安全的。对于等待事件，只要之配方同步指令和wait_event的当前位置之间的路径上不存在用户流水线(包含与wait_event谓词相交的谓词)的阶段，则认为将条件合并为单个支配方同步指令是安全的。对于set_event，只要wait_event的当前位置和后支配方(post_domanating)同步指令之间的路径上不存在客户流水线(包含与set_event谓词相交的谓词)的阶段，则认为将条件合并为单个后支配方同步指令是安全的。

通常有可能提高同步源代码的效率的另一方式是将同步指令提升到循环之外。图8是同步指令的循环提升的一个示例的示意图。同步源代码802包括同步指令对：set_event(Pipe-1,Pipe-2,0)806和wait_event(Pipe-1,Pipe-2,0)808。同步源代码802中的wait_event(Pipe-1,Pipe-2,0)808位于循环810和812之内。由于set_event(Pipe-1,Pipe-2,0)806和wait_event(Pipe-1,Pipe-2,0)808之间不存在使用流水线2的同步指令，所以转换同步源代码802是安全的，从而将wait_event(Pipe-1,Pipe-2,0)808移出循环810、812之外，如转换后的同步源代码804所示。

图9是示例性同步源代码900和同步源代码900中包括的各种指令902、904和906的示意图。同步源代码900可以看作是一系列阶段902、904和906，其中，每个阶段包括指令，这些指令在编译时在架构200的特定流水线206、202和212上执行。在所述示例中，流水线206(流水线4)可以认为是阶段1，流水线292(流水线1)可以认为是阶段2，流水线212(流水线3)可以认为是阶段3。同步源代码900还包括语句(例如，“for循环”)，通常使用为归纳变量和循环不变参数的函数的条件来预测同步指令。另外，考虑到同步指令是迭代空间中的函数，同步指令(例如，屏障、等待事件和设置事件)的顺序可以认为是静态的。

图10是图9中的同步指令在迭代空间中帮助检测同步源代码中的死锁条件、未定义行为条件或数据竞争条件等异常代码条件的示意图1000。

图11是同步源代码优化方法1100的一个实施例的流程图。编译器可以编译同步源代码以便在架构100、200等异步处理器架构上执行。在步骤1102处，接收同步源代码。所述同步源代码包括同步指令，所述同步指令使得所述同步源代码在由编译器编译成目标代码时能够在异步处理器架构上执行。在步骤1104处，从所述接收到的同步源代码中生成阶段图，详见下文。在步骤1106，对所述同步源代码执行诊断分析，以判断所述同步源代码是否包括异常代码条件。异常代码条件可以是所述同步源代码中的死锁条件、所述同步源代码中的未定义行为条件或所述同步源代码中的数据竞争条件。在一些实施例中，根据所述生成的阶段图执行所述诊断分析。根据所述同步源代码中的所述同步指令生成所述阶段图。所述诊断分析判断是否存在可能导致死锁条件、未定义行为条件或数据竞争条件的不配对的设置事件和等待事件。所述诊断分析还可以从所述同步源代码中确定关键路径信息。所述关键路径信息是确定可以由于并行执行独立指令产生的总执行时间的依赖指令流。

如果在步骤1106处，方法1100确定所述同步源代码包括异常代码条件，则方法1100结束。否则，如果在步骤1106处，方法1100确定所述同步源代码不包括异常代码条件，则方法1100继续到步骤1108。在步骤1108处，执行同步感知优化分析(以下称为优化分析)，以判断所述同步源代码是否包括所述同步源代码的所述同步指令中的不准确、不一致或低效指令。所述优化分析判断所述同步源代码中是否存在可以移除的冗余同步指令、是否减少同步控制流、是否改进指令调度以及是否改善缓冲。可以使用所述生成的阶段图执行所述优化分析。

在步骤1110处，对所述同步源代码进行优化和/或根据步骤1108处的所述优化分析生成包含信息的报告。所述信息报告可以包括关于冗余同步指令可以合并为单个指令的建议、识别产生异常源代码条件的不配对设置事件和等待事件、移除冗余同步指令，以及在安全的情况下将设置事件或等待事件移出循环之外。在一些方面，除了生成报告或除生成报告之外，可以自动校正所述同步源代码中的不准确、不一致或低效指令。在其它方面，除了校正所述同步源代码中的不准确、不一致或低效指令，方法1100生成报告，所述报告为程序员提供建议以改进对所述同步源代码的同步并识别不配对设置语句和等待语句、冗余同步指令等不准确、不一致或低效指令的位置。

图12是阶段图生成方法的示例性实施例的示意图1200。示意图1200是一个实施例中包含两个阶段的阶段图的一个示例。示意图1200示出了包含同步指令的同步源代码的示意表示。示意图1200包括多个阶段1204和1208以及同步指令1202、1206、1208和1212。多个阶段1204和1208以及同步指令1202、1206、1208和1212是阶段图中的结点(vertex)。控制流边(edge)1216，同步指令对1218、1220和1222以及happens before关系1214是阶段图中的边。

图13是阶段图的示例性实施例的示意图1300。示意图1300示出了包含多个同步指令的同步源代码的示意表示。同步源代码在编译成目标代码时，能够在架构100、200等异步处理器架构上执行。示意图1300示出了包括多个阶段1306、1316和1324以及同步指令1302、1304、1308、1310、1312、1314、1318、1320、1322和1326的同步源代码。多个阶段1306、1316和1324以及同步指令1302、1304、1308、1310、1312、1314、1318、1320、1322和1326是阶段图中的结点。控制流边1340，同步指令对1342、1344、1346和1348以及happens before关系1328、1330、1332、1334、1336和1338是阶段图中的边。同步指令对1342、1344、1346、1348的边标签(label)包括同步指令对有效的迭代空间。表示阶段之间关系的happens before关系1328、1330、1332、1334、1336和1338的边标签包括happens before关系成立的迭代实例以及强制执行该关系的同步指令。

一方面，源代码的语言暴露了阶段抽象。如果语言已经暴露了阶段抽象和阶段依赖关系，则阶段边界由程序员定义，“happens before”关系由程序员定义，等待事件和设置事件等同步指令自动插入到源代码中以生成同步源代码(需要说明的是，插入技术不在本发明的范围内)。因此，编译器已知同步指令对。对于这种场景，阶段信息通过内联函数和/或元数据传送到编译器。如果存在影响阶段或同步指令的后续处理，则更新内联函数和/或元数据。如果这些数据不完整，则从头开始构建阶段图。

图14是源代码如何暴露阶段抽象以生成阶段图的示意图1400。在本示例中，源代码1402包括“for(int i＝0；i

在没有阶段抽象的第二种场景下，将同步指令插入到源代码中。阶段构造遵循下表1概述的步骤。

表1

信息还可以存储在元数据中，以在优化之后简化对阶段图的重建，这些优化可能会影响阶段图。

关于定义阶段边界，有一些关于如何划分阶段的其它方法，特别是标量代码可以属于任何阶段。下面的算法使一个阶段以非标量代码作为结束，因此标量代码通常位于阶段的起始处。

从内部循环开始向上：

迭代通过循环体：

跟踪每个阶段中的第一个和最后一个语句

还在最后一次非标量操作之后跟踪第一个标量指令。

同步语句终止前面的阶段。下一个阶段中的第一个指令是跟踪的标量指令。

单个流水线上的循环执行可以在一个阶段内。

下面的源代码是用来定义不存在阶段抽象时的同步对：

可以使用两种开箱即用(out of the box)方法。一种方法是用于不等式的符号求解器。第二种方法是符号执行，其中，对程序进行符号计算，直到完成一个周期，并且所有的执行路径被触发。这可以作为一个简单的解析器来解析指令对。

关于定义happens before关系，可以使用以下伪代码：

·对于每个同步语句/对：

如果stmt＝barrier:

由流水线P的屏障后支配的流水线P中的所有阶段在由屏障支配的或者通过边可达的流水线P中的所有阶段之前发生。

否则，如果stmt＝event_pair：

由set_event语句后支配的生产者流水线P1中的所有阶段在由wait_event.s支配的用户流水线P2中的所有阶段之前发生。

·优势度应当考虑谓词。此外，还应该考虑下一次迭代。

·运行(开箱即用)传递依赖关系移除，以消除冗余依赖性。

图15是用于生成阶段图的示例性方法1500的流程图。方法1500开始于步骤1502：执行同步源代码的虚拟预测。一方面，虚拟预测包括在同步源代码的循环中“虚拟”线性化控制流。本文所使用的“虚拟”线性化是指实际上没有执行同步源代码变换。相反，同步源代码变换的条件存储在单独的数据结构中，作为阶段图的一部分。不需要实际预测。更确切地说，将所有语句及其谓词添加到一个列表中就足够了。循环可以看作是复合语句。每个复合语句(即循环)都有自己的一列几乎是预测的指令。大多数内部循环只有简单的语句。

在步骤1504处，定义阶段边界。除了标量和控制流计算外，单入口单出口代码块还包含不会因同步指令而中断并且在同一个流水线上执行的指令，认为是单个阶段的一部分。一方面，可以合并来自同一流水线的仅通过屏障分隔的阶段。

在步骤1506处，识别和定义同步指令对。一方面，对于set_event同步指令S，排除所有无效同步指令(根据流水线和标识符(identifier，ID))，其中，有效指令表示为“VS”：求解以下内容：对于每个I∈predicate(S)，求解J＝min(J0,J1,...,Ji,JN)，其中，Ji＝min(j)，其中，j>I且j∈predicate(Si)，其中，Si∈VS。这可以通过符号(谓词)分析或符号执行来求解。

在步骤1508处，定义happens before关系。在步骤1510处，根据阶段、同步指令、控制流、同步指令对以及happens before阶段关系识别阶段图的结点和边。一方面，扩展优势分析，如下：

·以谓词为基础。

·以迭代空间为基础(即，好像循环是展开的)。

·支配barrier(P)的流水线(流水线P)中的阶段在后支配barrier(P)的流水线(流水线P)中的阶段之前发生。

支配set_event(P1,P2)的流水线P1中的阶段在后支配wait_event(P1,P2)的流水线P2中的阶段之前发生。

在步骤1512处，根据结点和边生成阶段图，之后，方法1500可以结束。

一旦生成了阶段图，就可以用于判断同步源代码中是否存在异常代码条件。所生成的阶段图还可以用于识别同步源代码中的不准确、不一致或低效指令。在识别同步源代码中的不准确、不一致或低效指令之后，可以自动优化同步源代码以移除(例如，校正)同步源代码中的不准确、不一致或低效指令，并生成优化同步源代码。这些优化同步源代码在编译成目标代码(或称为编译后的同步源代码)时，在异步处理器架构上高效执行。或者，在识别同步源代码中的不准确、不一致或低效指令之后，可以生成报告，并将所述报告提供给原始源代码的程序员。所述报告包括关于可能改进同步源代码的建议，以提高编译后的同步源代码的执行性能。阶段图使用概述见下表2。

表2

图16是优化不包括异常源代码条件的同步源代码以移除同步源代码中的不准确、不一致或低效指令的示例性方法1600的流程图。如上所述，可以通过生成和分析阶段图来分析同步源代码，以判断同步源代码是否包括死锁条件、未定义行为条件或数据竞争条件等异常代码条件。

在步骤1602处，合并同一循环级别和同一谓词内的同步指令。在安全的情况下，可以合并同一循环级别和同一谓词内的同步指令。在步骤1604处，将同步指令提升到循坏之外，在同步指令中，谓词只针对循环中的第一次迭代或最后一次迭代进行检查。在安全的情况下，可以将谓词只针对循环中的第一次迭代或最后一次迭代进行检查的同步指令移到循环之外。安全分析基于阶段流水线信息和控制流边。如上所述，对于屏障，只要支配方同步指令与屏障当前位置之间的路径上不存在同一流水线的阶段，则认为将条件合并为单个支配方同步指令是安全的。对于等待事件，只要支配方同步指令与wait_event的当前位置之间的路径上不存在用户流水线(包含与wait_event谓词相交的谓词)的阶段，则认为将条件合并为单个支配方同步指令是安全的。对于set_event，只要wait_event的当前位置与后支配方同步指令之间的路径上不存在用户流水线(包含与set_event谓词相交的谓词)的阶段，则认为将条件合并为单个后支配方同步指令是安全的。用户流水线是使用正在优化的流水线的结果的流水线。

在步骤1606处，通过生成“happens-before”图并分析所生成的“happens-before”图，从同步源代码中移除冗余指令。一方面，消除了在“happens-before”图中的传递依赖关系(在构建图时和/或作为对图的转换)。当有同步指令没有出现在任何“happens before”边上时，该同步指令是一个可以安全移除的冗余同步指令。一方面，根据步骤1602、1604和1606修改同步源代码。在其它方面，在步骤1602、1604、1606和1608处，生成报告并将所述报告提供给源代码的程序员。所述报告指示与同步源代码的同步指令相关的优化提升可以实现在异步处理器架构上执行编译后的同步源代码的更好性能。

图17示出了用于检测同步源代码中的异常代码条件和同步源代码的同步感知优化的示例性系统1700。系统1700可以执行上文公开的方法。系统1700包括接收器1702、分析器1704和优化器1706。在一些实施例中，系统1700可以包括未示出的其它组件。分析器1704和优化器1706可以包括可以由计算设备中的一个或多个处理器执行的指令。接收器1702用于接收包括同步指令的同步源代码，其中，所述同步指令用于在架构100、200等流水线型异步处理器架构的不同流水线上同步执行所述同步源代码中的指令。分析器1704用于通过生成阶段图来分析所述同步源代码，以判断所述同步源代码是否包括死锁条件、未定义行为条件或数据竞争条件等异常代码条件。优化器1706用于优化所述同步源代码以校正所述同步源代码中的不准确、不一致或低效指令，使得编译后的优化同步源代码在流水线型异步处理架构上高效执行。优化器1706用于输出报告，其中，所述报告包括指示死锁条件的信息。优化器1706还用于输出优化软件程序以校正软件程序的指令中的不准确、不一致或低效指令。

图18示出了用于执行本文所述方法的一个示例性数据处理系统1800的框图。如图所示，数据处理系统1800包括处理器1804、存储器1806和接口1810至1914，它们可以(或可以不)如图所示排列。处理器1804可以是任何用于执行计算和/或其它处理相关任务的组件或组件的集合，存储器1806可以是任何用于存储处理器1804执行的编程和/或指令的组件或组件的集合。在一个实施例中，存储器1806包括非瞬时性计算机可读介质。接口1810、1812和1814可以是任何使处理系统1800与其它设备/组件和/或用户进行通信的组件或组件的集合。例如，接口1810、1812和1814中的一个或多个可以用于将数据、控制或管理消息从处理器1804传送到安装在主机设备和/或远程设备上的应用程序。又例如，接口1810、1812和1814中的一个或多个可以用于使用户或用户设备(例如，个人计算机(personalcomputer，PC)等)与处理系统1800进行交互/通信。处理系统1800可以包括图中未示出的其它组件，例如，长期存储器(例如，非易失性存储器等)。

在其它实施例中，数据处理系统1800位于用于接入电信网络的移动站、用户装备(user equipment，UE)、个人计算机(personal computer，PC)、平板电脑、可穿戴通信设备(例如，智能手表等)或任何其它设备等计算设备中。

应理解，对应的单元或模块可以执行本文提供的示例性方法的一个或多个步骤。拆分单元或拆分模块或拆分器可以将同步源代码划分为多个阶段。同步分析单元或同步分析模块或分析器可以分析同步源代码中的同步指令。效率单元或效率模块或同步误差分析器确定可以同步源代码中的同步指令中的不准确、不一致或低效指令。校正单元或校正模块或代码校正器可以执行校正动作。其它单元或模块可以执行其它步骤。各个单元或模块可以是硬件、软件或其组合。例如，这些单元或模块中的一个或多个可以是集成电路，例如，现场可编程门阵列(field programmable gate array，FPGA)或专用集成电路(application-specific integrated circuit，ASIC)。应理解，如果这些模块是软件，则这些模块可以由处理器根据需要全部或部分检索，单独或集体检索用于处理，根据需要在一个或多个实例中检索，并且这些模块本身可包括关于进一步部署和实例化的指令。

虽然已参考说明性实施例描述了本发明，但此描述并不旨在限制本发明。本领域技术人员在参考此描述后，将会明白说明性实施例的各种修改和组合，以及本发明其它实施例。因此，所附权利要求书意在包括任何此类修改或实施例。