支援并行程序设计的装置以及设计并行程序的方法

摘要

一种用以支援并行程序设计的装置，它包括用以将具有并行结构的第一并行程序转换为能被顺序执行之串行程序的串行程序设计单元；用以为串行程序排除错误并形成排除错误信息的排除错误单元；以及根据该排除错误信息，对已排除错误的串行程序进行并行程序设计，将该串行程序转换为第二并行程序的并行程序的程序设计单元。上述装置中，排除错误单元包括用以将与并行有关的信息引入串行程序的单元。

说明书

本发明涉及并行程序的设计方法以及用于并行程序设计的支援装置。

随着半导体集成电路技术的最新进展，可以以较低的成本实现小尺寸的复杂处理器或大容量存储器，由此由大量处理器组成的并行处理系统或分布处理系统可获实际的应用。此类硬件需要配备专用的程序，即并行程序或分布处理程序(以下称为“并行程序”)。因此，在研究最佳算法时，并行程序的有效开发是一个重要因素。

在程序开发中，发现和纠正程序中错误(即排除错误)的步骤将大大影响程序开发的效率。然而，在并行程序开发中，必须考虑只有并行程序才有的，不同于串行程序开发的一个问题。这种只有并行程序才有的问题就是由组成处理的并行程序可能根据各处理之间交互时序的不同而呈现各种不同的行为，故整个并行程序工作会不协调。这一由于并行程序之性质而造成的问题通常称为“非确定性的”。

以下讨论图1A和1B所示的并行程序。

参见图1A，过程P1对共享存储器M进行初始化(init)，过程P2对共享存储器M进行读取(read)，过程P3对共享存储器M进行写入(Write)。当使用由不同处理器来执行这些处理的并行处理系统运行时，可以实现总共六种组合的控制(见图1B)。通常，系统用初始化开始处理。假设当程序按处理P1→P2→P3或P1→P3→P2的次序运行时可以得到正确的结果。在此情况下，对于其余四种组合(例如P2→P3→P1)，由于初始化并非首先进行，故不可能获得正确的结果。

只要在运行并行程序时，与处理行为有关的上述的非确定性将根据那一时刻的系统状态而改变结果。因此，除非解决该非确定性问题，否则，尽管并行程序以一种测试模式下正常运行，也不能始终保证并行程序的正常运行。

此外，与串行程序中的错误相比，与非确定性有关的错误难以检测。在顺序程序中，通过在测试/调试运行期间执行程序中的所有通路，可以确认一种操作。反之，在并行程序中，必须考虑到所有匹配路径(即不仅每个处理中的所有路径，而且包括各处理之间的各种行为)来执行路径。当如上例所示处理量较小时，可以较为方便地列出各处理之间的所有行为。然而，在实际程序开发中，处理量将会是很大的，由此而形成大量的组合。为此，要覆盖所有行为是不可能的。

如上所述，在并行程序开发中排除错误比之串行程序开发中排除错误更难，尤其是，程序本身近来变得非常大，以致于排除错误更困难。

本发明的目的在于提供一种设计并行程序的方法以及用于并行程序设计的支援装置，其中，并行程序可以方便地排除错误并可以高效率地开发。

本发明的要点是暂时将并行程序转换为串行程序，对串行程序完成测试和排除故障操作，并当完成测试/调试操作后恢复程序的并行性。原始并行程序按要求排除了故障。

并行程序设计之所以较困难的原因在于“由于人类的思路实质上是顺序的，故按其原始状态难以逻辑性的认识并行操作的事物。”在本发明中，并行程序暂时设计成串行程序，对串行程序完成程序设计和排除故障(这里所用的“排除故障”指的是包括测试操作在内的一种操作)。其难度是与传统的串行程序设计等同的。在完成排除故障后，利用排除故障信息自动恢复并行。

上述程序设计风格称为“超串行程序设计”。根据该“超串行程序设计”，可以解决因传统方法而引起的程序设计难度。本发明的基本思路包括以下三步(或装置)。

(1)进行并行程序的串行程序设计，合成一个超串行程序的步骤(装置)。

(2)为超串行程序完成各种操作(程序设计、排除故障和并行的应用)的步骤(装置)。

(3)当完成合成一个并行程序的操作时，对超串行程序进行并行程序设计的步骤(装置)。

这里的“超串行程序”指的是程序是按串行的，而与原始并行程序之并行结构有关的信息仍保持不变。

一种用以支援并行程序设计的装置，包括：

用以将具有并行结构的第一并行程序转换为能被顺序执行的一串行程序的串行程序设计装置；

用以排除该串行程序之错误并形成排除错误信息的排除错误装置；以及

用以根据该排除错误信息对已排除错误的串行程序进行并行程序设计，并将该串行程序转换为第二并行程序的并行程序设计装置。

一种用以支援并行程序设计的装置，包括：

测试执行装置，用以执行对具有并行结构的第一并行程序的测试；

第一执行记录累加装置，用以在通过所述测试执行装置执行测试时，累加判定为无错误的执行记录；

第二执行记录累加装置，用以在通过所述测试执行装置执行测试时，累加判定为有错误的执行记录；

校正装置，用以根据由所述第二执行记录累加装置累加的执行记录，校正第一并行程序；以及

并行程序程序设计装置，用以对所述第一执行记录累加装置累加的执行记录进行并行程序设计，将执行记录转换为第二并行程序。

本发明的较佳实施方案如下：

(1)产生与并行至串行程序有关的信息。该与并行有关的信息例如包括与好的非确定性有关的信息(以后介绍)。

(2)分析第一并行程序的并行结构，利用在并行结构和串行程序测试时所获得的执行结果进行串行程序的并行程序设计。

(3)分析一段(该段被转换为串行程序)第一并行程序的并行结构以及一段串行程序的串行结构，将与第一并行程序的并行结构有关的相关性以及与串行程序的串行结构有关的相关性作为图形信息显示。在图形信息显示中，在将预定的段定义为节点，将与并行结构有关的相关性定义为第一弧，并将与串行结构有关的相关性定义为第二弧时即显示图形信息。对所选段的串行程序进行并行程序设计，将该段转换为部分具有串行结构的部分串行程序。对部分串行程序进行并行程序设计，将部分串行程序转换为第二并行程序。

将第一并行程序转换为程序的步骤可以包括排除串行程序的故障直至获得所需串行程序执行结果的步骤。或者，将串行程序转换为部分串行程序的步骤可以包括排除部分串行程序的故障，直至获得所需执行结果的步骤。另外，这两个步骤还可以包括进行测试/调试操作的步骤。

将串行程序转换为部分串行程序的步骤可以包括分析部分串行程序之串行结构的步骤，同时，显示图形信息、选择已转换为并行程序的段以及将该段转换为部分串行程序的步骤可以按预定重复多次。

(4)在用以将第一并行程序转换为串行程序的串行程序设计中，第一并行程序被执行，并且在该步骤中存贮一个执行记录。对所贮存的执行记录和第一并行程序进行分析，根据分析结果重新排列所贮存的执行记录。在对执行记录和第一并行程序分析中，以所贮存的执行记录和第一并行程序中取出各处理之间的一种前导关系，作为前导关系信息存贮该前导关系。

(5)在引入与并行有关的信息时，串行程序的处理流程转换为包含约束和转移条件的字段，同时调整该字段。此外，显示表示该字段的字段数据。

(6)指定一组选作为串行程序的并行程序设计的处理。交换该处理组的执行次序，将串行程序转换为多个并行假程序。然后，该多个并行假程序转换为部分具有串行结构的部分串行程序，对部分串行程序进行并行程序设计，将部分串行程序转换为第二并行程序。

将第一并行程序转换为串行程序的步骤可以包括排除该串行程序的错误，直至获得所需串行程序之执行结果的步骤；或者，将多个并行假程序转换为部分串行程序的步骤可以包括排除多个并行假程序的错误，直至获得所需并行假程序组之执行结果的步骤。另外，该两个步骤可以包括进行测试/调试操作的步骤。在指定处理组作为并行程序设计选择用于串行程序过程中，可以分析第一并行程序，从一个分析结果中可以取出作为并行程序设计选择的处理组。将串行程序转换为多个并行假程序的步骤可以包括根据多个并行假程序的某些执行结果，消除已确定为不再需要的一个并行假程序的步骤。将多个并行假程序转换为部分串行程序的步骤，可以包括将处理组指定为用作部分串行程序的一个并行程序设计选择的步骤，以及将串行程序转换为多个并行假程序的步骤，上述将多个并行假程序转换为部分串行程序的步骤可以按预定重复若干次。

(7)当根据预定的串行规则将第一并行程序转换为串行程序时，通过修正该串行规则将与并行有关的信息引入串行程序。

(8)在用以支援并行程序设计的装置中，该装置支援用于一种执行环境的并行程序的程序设计，其中，一个处理组按并行的方式运行，而相应于并行程序处理组执行过程的交换消息信息、记录信息则被收集，并作为一种排序规则储存，所储存的记录信息可以被修正。处理组可以按串行启动，并根据所储存的记录信息进行控制，对所储存的记录信息进行并行程序设计，将记录信息转换为第二并行程序。

一种用以支援并行程序设计的装置，所述装置支援在执行环境中所用的并行程序的程序设计，所述环境中当交换消息信息时采用一并行方式运行一个处理组，包括：

记录信息采集装置，用以采集相应于所述第一并行程序之所述处理组的执行过程的记录信息，将其作为一种排序规则；

记录信息存储装置，用以存储由所述记录信息采集装置所采集的记录信息；

记录信息校正装置，用以校正存储于所述记录信息存储装置内的记录信息；

处理组控制装置，用以根据存储于所述记录信息存储装置内的记录信息，顺序地启动和控制所述处理组；

并行程序程序设计装置，用以对存储在所述记录信息存储装置内的记录信息进行并行程序设计。

如上述装置，所述记录信息校正装置包括：

显示装置，用以按时连续地显示存储在所述记录信息存储装置内的记录信息；

重新排列指定装置，用以指定由所述显示装置按时连续显示的记录信息中的数据次序的重新排列；以及

重写装置，用以根据所述重新排列指定装置的指定，重写存储在所述记录信息存储装置内的记录信息。

(9)在执行环境中根据执行次序定义信息运行处理组的系统中，其中处理组可以按并行方式运行，同时交换消息信息，执行次序定义信息被分流，处理组被启动并根据所分流的执行次序信息进行控制。

在此情况下，也可以提供用以保存分流标准指定装置的装置，该分流标准指定装置用以提供一个标准以分流执行次序定义信息。消息交换过程被用作执行次序定义信息，同时，消息中的目标处理信息被用作分流准则设定装置中的分流准则。消息交换过程被用作执行次序定义信息，消息中的设定处理信息被用作分流准则设定装置中的一个分流准则，同时还提供用以在处理单元内保持过程控制的装置。消息交换过程被用作执行次序定义信息，消息中的目标处理信息被用分流准则设定装置中的分流准则，同时，还提供在处理单元中用以保持过程控制装置的装置，以及分流执行次序信息存储装置，后者用以单独存储由执行次序信息分流装置所分流的执行次序信息。过程控制装置根据储存在对应于该处理的分流执行次序存储装置中的分流执行次序信息，启动和控制该处理。对应于处理组执行过程信息的记录信息可以作为执行次序定义信息用。

(10)执行对具有并行结构的第一并行程序的测试。将执行测试期间确定为无错误的执行记录累加起来，只对累加的无错误的执行记录进行并行程序设计，将执行记录转换为第二并行程序。此外，将执行测试期间确定为有错误的执行记录累加起来，根据累加的有错误的执行记录修正第一并行程序。

在本发明中，暂时对并行程序作串行处理，并对串行程序进行测试/调试。采用这种运行方式，可以按与串行程序设计中相同的难度对并行程序排除错误，而串行程序设计比之传统的并行程序设计来要容易得多。

并行信息和串行信息是同时通过图形信息向用户显示的。采用该运行方式，用户可以指定一个好的非确定性部分，而同时考虑第一并行程序的并行结构。此外，好的非确定部分不是在并行程序描述级作指定/取消，而是用于图形信息。为此，无需采用先进的并行程序设计技术就可以方便地开发一种并行程序。

在第一并行程序转换为串行程序的过程中，对第一并行程序及其执行记录进行分析，并且根据该分析结果对执行记录重新排列。根据该运行方式，向用户显示和表示重新排列的执行记录，由此便于了解并行程序的执行过程，并改进排除错误操作的效率。

将与并行程序有关的信息引入到串行程序后，将串行程序的处理流程转换为包含约束和转移条件的一个字段，并显示该字段数据。该字段经问答式和直观式的编辑，以有效地产生与并行有关的信息，由此可以有效地设计一个无任何错误的并行程序。

将作为并行程序设计选择的处理组指定用作按第一并行程序按串行方式的串行程序，交换处理组的执行次序，将串行程序转换为多个并行假程序。此后，将多个并行假程序转换为部分具有串行结构的部分串行程序，对部分串行程序进行并行程序设计，将部分串行程序转换为第二并行程序。采用此种运行方式，可以充分证实在部分串行程序上运行并行程序。此外，当把作为并行程序设计选择的处理组指定用作部分串行程序时，可以逐步将串行结构的程序转换为并行程序。再者，根据并行假操作系列，并行仅允许非确定性确认为适合运行于顺序执行中，通过引入一种与并行有关的信息，可以获得合适运行的平行程序。根据此种运行方式，可以简化并行程序的测试/调试操作。

在用以支援并行程序设计的装置中，该装置支援用于执行环境中的并行程序的程序设计，其中，第一并行程序的处理组按并行方式运行，同时交换消息信息，相应于处理组之执行过程的记录信息被采集并作为一种串行规则存储。该记录信息可以进行修正，同时，该处理组可以根据所存储的记录信息顺序地启动和控制，由此对所存储的记录信息进行并行程序设计，将记录信息转换为第二并行程序。

在此情况下，可以修正记录信息而无需修正作为源程序的并行程序，来解决因处理时序的非确定性而产生的缺陷。根据该原理，可以简化并行/平行/分布程序的开发。此外，由于可以容易地引入用户想要的好的非确定性，故可以维持并行程序的灵活性、再利用和可扩展性。

在一个处于执行环境下(其中当交换消息信息时，处理组可以以一种并行方式在该执行环境中运行)根据执行级定义信息运行处理组的系统中，执行级定义信息被分流，即通过排序并行程序而获得的所有处理的集中记录信息在各个处理单元内分流，处理组根据分流的执行级信息被启动和控制。根据该原理，必然引入未受损害的非确定性，并且可以以更高的处理效率获得与根据集中记录信息的串行程序之执行相同的结果。

第一并行程序被测试，在执行测试期间作为其中之一被判定为无错误的执行记录被累加起来。只有具有累加的无错误的执行记录的并行程序设计才能用来将执行记录转换为第二并行程序。根据该原理，可以运行程序使之仅允许在测试中同步通过，由此防止因不执行测试而留下的错误，并改善可靠性。

本发明的其它目的和优点将在以下描述中得到反映，一部分可以从说明书中明显看出，或者也可以通过本发明的实践加深理解。尤其通过所附权利要求书记载的各种手段和组合，可以实现和获得本发明的各种目的和优点。

以下将结合附图说明本发明的几个较佳实施例，并连同上述一般描述和以下对较佳实施例的详细描述说明本发明的基本原理。

图1A和1B是用以解释现有技术中所存在问题的示意图；

图2是一个方框图，表示根据本发明用以实现一个并行程序设计支援装置的一个计算机系统的配置；

图3是示意性表示根据本发明第一个实施例的并行程序设计支援装置之配备的方框图；

图4是示意性表示根据本发明第一个实施例的并行程序设计方法之各个步骤的流程图；

图5是表示并行程序和排序规则的示意图，用以解释第一个实施例的原理；

图6是表示一个超串行程序原理的示意图，其中引入元级缺省顺序，用以解释第一个实施例的原理；

图7是表示测试/调试屏幕的示意图，用以说明第一个实施例的原理；

图8是表示引入与非确定性有关的信息的示意图，用以说明第一个实施例的原理；

图9是一个方框图，示意性地表示根据本发明第二个实施例的并行程序设计支援装置的配备；

图10是一个流程图，示意性地表示根据第二个实施例的并行程序设计方法的各个步骤；

图11是表示一个区段设置方法的示意图；

图12是表示串行程序设计方法的示意图；

图13是表示排序信息重写规则的示意图；

图14是表示并行程序的示意图；

图15是描述并行程序的示意图；

图16A至16C是分别表示区段信息、程序结构信息以及超串行程序之超排序信息的示意图；

图17是解释引入好的并行的示意图；

图18是表示由串行程序设计的一个并行程序的源码示意图，它自动设计为并行程序；

图19是表示超串行程序之程序结构信息的示意图；

图20是表示超串行程序之排序信息的示意图；

图21是一个流程图，它表示自动设计为一个并行程序的超串行程序的处理流程；

图22是一个方框图，示意性表示根据本发明第三个实施例的并行程序设计支援装置的配备；

图23是一个流程图，示意性表示根据第三个实施例的并行程序设计方法的各个步骤；

图24是表示作为一个源程序的并行程序的示意图，用以说明第三个实施例的原理；

图25A至25C是表示第三个实施例中并行程序设计的示意图；

图26是一个流程图，示意性地表示根据本发明第四个实施例的并行程序设计方法的各个步骤；

图27是表示第四个实施例中所用处理表的示意图；

图28是表示一个并行程序的示意图，用以说明第四个实施例的原理；

图29是表示图28所示并行程序之并行结构的原理的示意图；

图30A至30E是表示在分析第四个实施例中所用并行程序结构期间所形成之处理表的示意图；

图31是表示第四个实施例所用超时序图形的示意图；

图32是说明第四个实施例中超时序图形程序设计单元之操作过程的示意图；

图33是说明在第四个实施例中指定一个并行部分的方法的示意图；

图34是表示在第四个实施例中指定并行部分后之超时序图的示意图；

图35是表示具有成组节点之超时序图的示意图；

图36是表示在按优先级改变后一个超时序图的示意图；

图37是用以说明在三个处理之间引入好的非确定性部分的示意图；

图38是表示在引入好的非确定性部分之后的超时序图的示意图；

图39是一个方框图，示意性地表示根据本发明第五个实施例的并行程序设计支援装置的配置；

图40是表示作为源程序的一个并行程序，用以说明第五个实施例的原理；

图41是说明由图40所示并行程序执行的处理流程的示意图；

图42是表示第五个实施例中存储于排序处理文件内一个排序处理的示意图；

图43是表示在图42所示的排序处理内执行的处理流程的示意图；

图44是一个流程图，表示第五个实施例中在字段数据发生单元内执行的处理流程的示意图；

图45是表示由图44所示处理产生的一个区域之数据结构的示意图；

图46是表示第五个实施例中由字段数据发生单元所产生的字段数据的示意图；

图47是一个流程图，表示第五个实施例中在一个字段调整部分内执行的处理流程；

图48是详细表示图47一部分(步骤E9)的流程图；

图49是表示第五个实施例中字段变化的示意图，该变化因约束改变操作引起；

图50是详细表示图47所示另一部分(步骤E11)的流程图；

图51是表示第五个实施例中字段变化的示意图，该变化因约束改变操作引起；

图52是详细表示图47所示另一部分(步骤E13)的流程图；

图53是表示第五个实施例中字段变化的示意图，该变化因约束改变操作引起；

图54是表示用以检测明显约束的处理流程图，该约束在字段内产生抵触；

图55是表示一个字段包括明显约束的示意图；

图56是表示检测该明显约束的示意图；

图57至59是表示字段编辑显示屏幕的示意图；

图60至67是表示第五个实施例中用以调整字段数据之处理的示意图；

图68是一个流程图，表示第五个实施例中在一个字段变换单元内所执行的处理；

图69是表示第五个实施例中一个已修正的并行程序的示意图；

图70表示由图69所示并行程序所执行的处理流程的图像；

图71是一个方框图，示意性地表示根据本发明第六个实施例的一个并行程序设计支援装置的配置；

图72是一个流程图，表示根据第七个实施例的一个设计并行程序方法的主要步骤；

图73是由用户支援的一例并行程序；

图74是模拟由图73所示并行程序获得的一个超串行程序之执行系列的实例；

图75是一个流程图，表示根据第七个实施例，从超串行程序转换为部分并行程序的各个步骤；

图76A至79B表示用以将超串行程序转换为部分并行假模式的处理实例；

图80是表示根据本发明第八个实施例在各处理之间进行信息交换的示意图；

图81是一个方框图，示意性地表示根据本发明的第八个实施例的一个并行程序设计支援装置的设置；

图82是一个流程图，示意性地表示根据本发明第八个实施例的一个并行程序设计方法的各个步骤；

图83是表示第八个实施例中作为一消息执行过程的记录信息的示意图；

图84是一个方框图，示意性地表示根据第八个实施例，以记录信息为基础的一个并行程序排除故障单元的配置；

图85是表示第八个实施例中一个消息格式的示意图；

图86是表示第八个实施例中各处理之间信号交换的示意图；

图87是表示第八个实施例中记录信息的示意图；

图88是一个流程图，表示第八个实施例中处理组控制单元之各个处理步骤；

图89是表示第八个实施例中一个状态的示意图，其中指定一个替换目标来修正记录信息；

图90是表示第八个实施例中已修正的记录信息的示意图；

图91是表示第八个实施例中一个状态的示意图，其中，指定一个目标部分将好的非确定性引入记录信息；

图92A和92B是表示第八个实施例中，在引入好的非确定性之后的记录信息的示意图；

图93是一个方框图，表示第八个实施例中，以记录信息为基础的一个并行程序执行系统的配置；

图94是表示第八个实施例中各任务之间信息交换的示意图；

图95是表示第八个实施例中在引入好的非确定性内的记录信息的示意图；

图96是一个流程图，表示第八个实施例中一任务控制单元之处理步骤；

图97A至97D是表示第八个实施例中作为启动任务控制单元手段之程序的示意图；

图98是表示第八个实施例中每个任务之结构的示意图；

图99是一个流程图，表示第八个实施例中任务控制单元的处理步骤；

图100是表示第八个实施例中一个消息格式的示意图。

下面将结合附图描述本发明的较佳实施例。

在描述本发明的实施例之前，先来定义在本发明中所用的术语。

并行系统(Concurrent System)：具有逻辑并行性的系统。运行并行程序的系统是并行系统。并行计算机和分布处理系统都是并行系统。

并行程序(Concurrent Program，CP)：基于以并行方式操作的模型描述的程序。在并行程序中包括了在以多个CPU构成的并行计算机中以并行方式进行逻辑和实际操作的程序(并行程序)。在并行程序中甚至可以包括在单个CPU控制下以串行方式进行实际操作的程序，只要如在多任务系统中那样建立逻辑并行性。

串行程序(Sequential Program)：基于以顺序方式进行逻辑操作的模型描述的程序。

超串行程序(Hyper Sequential Program，HSP)：顺序操作但对并行程序增添元级(meta level)(执行管理级)控制的程序。例如，当对一描述成并行程序的程序增添执行管理级的调度程序以获得顺序操作程序时，所得到的程序称为超串行程序。由于超串行程序没有非决定性(下面将描述此术语)，因此当外部输入相同时，超串行程序将具有可再现性。

在超串行程序中，可部分引入并行性(非决定性)。部分引入并行性(非确定性)的超串行程序可特别称为部分超串行程序(PartialHyper Sequential Program，PHSP)，而没有并行性(非确定性)的程序可以称为完全超串行程序。

非确定性(Nondeterminism)：尽管输入相同，但取决于处理定时的系统性能的改变。在执行并行程序时，非确定性是一主要方面。在某种意义上说，没有非确定性的程序等价于逻辑串行程序。

良好非确定性(Good Nondeterminism)：用户想要的非确定性，即，包含于用户说明和其他实现请求中的非确定性。由于这种非确定性，程序能对一外部的(环境的)非确定的输入作出适当响应。

不良非确定性(Wrong Nondeterminism)：用户未预期的非确定性。由于用户的概念电路是顺序的，在实际执行一并行程序时，经常发生在设计时不想要的情况。

无害非确定性(Harmless Nondeteminism)：非确定性的选择不影响最后结果的非确定性。在“超串行编程”的并行程序综合装置中，进行并行编程的目标包括有“无害非确定性”。

缺省顺序性(Default Sequentiality)：在执行管理级的顺序控制。

并行假程序(Concurrent Dummy Program)：在一特定范围内产生的一并行假操作序列组，它用作并行编程的候选组。

并行假操作序列(Concurrent Dummy Operation Series)：在特定范围内产生的一操作序列，对一串行程序把并行程序操作以这样的方式模拟成并行编程候选序列，即顺序执行次序是任意改变或有意改变的。在一个并行程序编程范围内可以产生多个并行假操作序列。

一般，由于在一个并行编程候选范围内产生了多个并行假操作序列，把所有这些序列称为一个并行假程序。在整个超串行程序中将产生多个并行假程序。

图2是一方框图，示出按照本发明的一种计算机系统的安排，用以实现对并行程序编程的支持设备。参见图2，N个处理器1-1、1-2、…、1-N能同时执行一并行程序并通过输入输出接口访问一个共享存储器和外围设备。外围设备包括一输入装置4、一输出装置5以及一外部存储装置6。

输入装置4包括一键盘、一指示装置以及类似装置，用以输入各种指令和数据。输出装置5包括一阴极射线管(CRT)显示器以及类似装置，用以以文件或图形的形式向使用者显示源程序以及有关调试状态的信息。用户用输入装置4和输出装置5以询问的方式操作计算机。

外部存储装置6包括一磁盘、一磁光盘或类似装置，能对源程序和有关调试状态的信息进行读写。

如上描述的计算机系统的安排并不限于这一种。例如，可以用所谓分布式网络来安排计算机系统，在此系统中用一网络来连接多台计算机。

在具有上述安排的计算机系统中，按照本发明的并行编程可用下述办法来实现。第一个实施例

在第一个实施例中，测试/调试一种部分超串行程序。作为一个较佳实施例，把有关良好非确定性的信息引入部分超串行程序。在下述实施例中，将描述引入良好非确定性的一种情形。然而，并非必需引入良好非确定性。

图3是一方框图，示出按照第一个实施例支持对一并行程序编程的设备。

按照第一个实施例支持对并行程序编程的设备包括一串行程序综合装置12、一测试执行装置15、一调试装置16、一非确定性引入装置17以及一并行程序综合装置18。

串行程序综合装置12将一存储在第一并行程序(CP)文件存储装置11中的源程序(在下文中称为第一并行程序)根据存储在排序规则存储装置13中的排序规则变为一超串行程序，并将变换结果存储在一超串行程序(HSP)文件存储装置14中。在第一CP文件存储装置11中存储了用并行编程语言建模和描述的第一并行程序。第一并行程序可能有一故障。为描述第一并行程序，可用下述并行编程语言：

(a)并行PASCAL

(b)ADA

(c)GHC

(d)Modula3

(e)Occam

(f)cooC

测试执行装置15和调试装置16对存储在HSP文件存储装置14中的超串行程序进行测试和调试。

在把第一并行程序变为超串行程序的过程中，非确定性引入装置17引入良好非确定性。

根据存储在HSP文件存储装置14中的超串行程序测试/调试信息，并行程序综合装置18完成超串行程序的并行编程，以综合出第二并行程序。把这个第二并行程序存储在一第二并行程序(CP)文件存储装置19中。

图4是一流程图，示出按照第一个实施例对一并行程序编程的方法的主要步骤。

(1)步骤A1：建模

对于一目标并行系统利用并行性进行自然建模。确定并行系统的每个过程结构。此外，在每个过程中，把按照用一并行程序的编程具有一并行结构的并行程序作为一源程序来描述。注意到并行程序具有“并行结构”，因为，通常，一并行程序并不总是完全由一并行结构组成的。如果建模时用串行化更自然，则相应的部分可具有一顺序结构。注意，在此源程序中可能会有一隐藏的错误。

(2)步骤A2：排序

引入缺省顺序性，把第一并行程序变为具有一顺序结构的超串行程序。在本实施例中，在元级上引入顺序性。元级不是定义为源程序本身(即第一并行程序)的级，而是定义为处理源程序执行的级。例如，把以并行程序描述的一源程序变为这样一个源程序，它用一与源程序无关的调度程序来确保程序的顺序执行。

(3)步骤A3：超串行程序的测试/调试操作

对一超串行程序进行测试/调试。根据由测试执行装置得到的串行程序测试结果，用调试装置从超串行程序中排除一错误。可以用与串行程序中的普通的测试/调试方法相同的方式来完成测试/调试。重复测试/调试操作，直至确保串行程序得以正常运行。

(4)步骤4：为超串行程序引入非确定性

把有关良好非确定性的信息(有关并行性的信息)赋给已测试/调试的超串行程序。由这一操作，使超串行程序部分地具有与非确定性有关的信息而变为部分超串行程序。后面将描述引入与良好非确定性有关的信息的方法。

(5)步骤A5：部分超串行程序的测试/调试

对于在步骤A4中得到的部分超串行程序进行测试/调试。即，对在步骤A4中引入与良好非确定性有关的信息的超串行程序进行测试/调试。

(6)步骤A6：对部分超串行程序引入并扩展良好非确定性

再把与良好非确定性有关的信息加至已在步骤A5中测试/调试的部分超串行程序。把步骤A5和A6重复预定数目的次数以逐渐扩展良好非确定性。

(7)步骤A7：并行编译

从部分超串行程序中提取一无害非确定性部分，在该程序中引入过与良好非确定性有关的信息。对非确定部分以并行方式编程，以把整个的部分超串行程序变为一并行程序。在元级上由缺省排序给出的顺序性在并行程序上反映出来(例如，含于源程序本身)，而取消元级的缺省排序。

下面参见图5至8更详地描述本发明。

图5示出一简单的并行程序。

图5中的并行程序由过程1和过程2组成。只有当在计算机中执行一执行程序块时，这些过程才能作为实体实现，该程序块是对并行程序的源码进行编译得出的。分别相应于过程P1和P2的并行程序不需相互无关地存储在存储介质中。这里用一共享存储器M来代表一外部存储器。根据并行程序的存取指令，共享存储器可进行写/读访问。图5中的实线箭头表示在执行过程P1和P2时对共享存储器M的访问。

根据用户从输入装置4输入的命令，读出存储在CP文件存储装置11中的第一并行程序，并把它输入至串行程序综合装置12。根据存储在排序规则存储装置13中的排序规则，对于输入至串行程序综合装置12的第一并行程序在元级引入缺省顺序性，从而把第一并行程序变为超串行程序(HSP)。把这个超串行程序存储在HSP文件存储装置14中。

典型的排序规则是如下的那些规则：

(a)把优先级引入过程的规则；

(b)在一过程中把优先级引入处理装置(面向目标的方法)的规则；

(c)基于实际执行记录的排序规则；

(d)对于信息目的地作优先执行的排序规则；以及

(e)对于信息源作优先执行的排序规则。

在图5下部示出的“P1》P2”是对于图5的并行程序的排序规则。这条规则指出，过程P1优先于过程P2执行。这条规则对应于规则(a)。这条排序规则要在第一并行程序的开头就要提出并且将它与过程体一起编译，由此把优先级引入过程。或者，在不同于并行程序的一个文件中描述这条排序规则，而在执行并行程序时对它进行解释并引入它。在本实施例中，排序规则用“》”表示，当然也可以用除“》”之外的任何符号。

图6示出在元级引入缺省顺序性的超串行程序HSP的概念。过程P1和P2由调度程序S来管理。参见图6，虚线箭头表示调度程序S根据图5所示的排序规则(“P1》P2”)先执行过程P1再执行过程P2。注意，在图5中表示此超串行程序HSP的概念在图6的下部作了描述，即

HP＝P1｜P2｜

这表明此超串行程序HSP由过程P1和P2以及调度程序S组成。在此情形下，排序规则相应于调度程序的调度规则。

用户可在输出装置5处检查此超串行程序。根据来自输入装置4的用户命令，把超串行程序输入至测试执行装置15并由此装置测试。测试执行装置15输出一测试执行结果(执行记录)至输出装置5。用户根据此测试执行结果，用输入装置4作为调试装置16以对超串行程序作一预定的测试/调试操作。可以用下述测试/调试技术：

(a)源码跟踪程序；

(b)断点；以及

(c)动画制作。

图7示出此时的测试/调试图像。参见图7，在输出装置5的测试/调试屏60上开有各种窗口61至65，并显示各种信息。窗口61至65能适当地开/关。注意，在这一测试/调试操作中，可主要采用一已知的调试装置。更具体些说，UNIX工作站上的dbxtool是已知的调试装置(见UNIX用户手册)。

当用户对超串行程序做完预定的测试/调试操作后，他从输入装置4输入一个命令以再次执行一测试。把已测试/调试的超串行程序HSP输入至测试执行装置15，而再执行一测试。重复这种测试/调试操作直至超串行程序HSP正常工作为止。当用户在测试/调试操作中确信超串行程序正常运行，就用非确定性引入装置17把有关非确定性的信息部分地引入超串行程序。由非确定性引入装置17引入的有关良好非确定性的信息反映在超串行程序HSP上，并记录在HSP文件存储装置14中。注意，非确定性引入装置17将在后面描述。

图8示出把有关良好非确定性的信息引入一超串行程序的状态。在此情况中，如果把一并行程序的每个程序的执行单位称为一“段”，则图8示出这样一种状态，即S2段与S3段具有同样的优先级(过程P1分为S1段和S2段，而过程2分为S3段和S4段)。

说得更具体些，把与良好非确定性有关的信息指派给用以在执行单位中指定不同优先级的排序规则(设置得具有相同优先级的过程由一鼠标器点中)。并行操作可在这样的假设下执行，即，相应的部分具有相同的优先级。在图8中，表示{作为4段S1至S4中的S2段的“write1”被设置成与作为S3段的“read2”具有相同的优先级)的信息是作为良好非确定性引入的。由于具有相同优先级的任一过程都可首先执行，因此这些过程具有非确定性。

由非确定性引入装置17把有关良好非确定性的信息引入的超串行程序(部分超串行程序)由测试执行装置15测试，而根据用户命令由调试装置16测试/调试。在此情形下，因为在引进有关良好非确定性信息的部分，部分超串行程序PHSP的行为是非确定性的，最好对所有的行为进行测试/调试。用这种方式，重复测试/调试操作以及有关良好非确定性信息的引入，以逐加入有关非确定性的信息。

根据用户命令把通过逐渐引入有关良好非确定性信息而得到的部分超串行程序PHSP输入至并行程序综合装置18。并行程序综合装置18从部分超串行程序PHSP中提取一无害非确定性部分，并把所有的部分超串行程序PHSP综合为一个并行程序。说得更具体些，并行程序综合装置18消除有关引入的良好非确定性和无害非确定性的缺省顺序性，并把所得的程序作为并行程序CP(第二并行程序)记录在一文件中。在文件中，除了良好非确定性和无害非确定性之外，由缺省排序给出的顺序性被反映至并行程序CP。用户可在输出装置5处检查此第二并行程序，同时可进行最终测试/调试操作。

第一个实施例是本发明的基本的实施例，而下面将描述更详细的实施例。在下面的实施例中，与第一个实施例相同的标号表示相同或相应的部分，而简化或省略对它们的详细描述。下面将主要描述第一个实施例与下面的实施例之间的不同点。第二个实施例

如在第一个实施例中那样第二个实施例具有下述目标并行程序。并行程序由多个过程组成。由共享存储器型的多处理器执行并行程序。把处理器(CPU)分派给每个过程。由一条基本的同步指令和共享存储器实现过程之间的同步。

下面将描述把本发明用于上述并行程序的实施例。

图9是一方框图，它示出了按照第二个实施例的并行编程支持设备的布置。图10是一流程图，它示出按照第二个实施例的并行编程方法的运行过程。

图9与图3的不同之处在于设置了一个段设定装置7，把一测试执行装置15和一调试装置16更明确地定义为一测试执行装置15，还设置了一校正装置9、一分析装置10以及用来存储由分析装置10分析的分析信息的分析信息存储装置20。分析装置10分析一超串行程序，并提取一在先的约束(后面将描述)作为分析信息。其余的构成部件与第一个实施例中的那些相同，因而省略对这些部件的描述。注意，图9还包括了一个用以存储并行规则的并行规则存储装置21，当将一超串行程序用一并行程序综合装置18编程为一并行程序时，将用到这一装置。

段设定装置7将第一并行程序的每个过程分成几段(程序单位)。

如果在由测试执行装置15所作的一测试中检测出一错误，则用校正装置9来校正。

测试执行装置如在第一个实施例中那样来测试一超顺序程序。

分析信息存储装置20存储由分析装置10分析的信息。

下面将结合图10的流程图来描述第二个实施例的操作。与图4的流程图中相同的步骤标号在图10中表示相同的操作。

(1)步骤A1：建模

对于一目标并行系统利用并行性进行自然建模。确定并行系统的每个过程结构。此外，按照用一并行程序的编程，把具有一并行结构的并行程序作为一源程序来描述。注意，在此源程序中可能有一隐藏的错误。

(2)步骤B1：设置段

程序员用段设置装置7把第一并行程序的每个过程分成几段(单位)。把第一并行程序中的同步指令自动地定为单独的一段。段是过程的单位。在下面的步骤中，将以段为单位来进行顺序编程和并行编程。在此情形中，程序员不需设置段。在此情形中，自动地把按照同步指令划分而得到的间隔规定为段。

通过划分每个过程的源码和在每个划分的间隔内设置一个段标识符(ID)可以实现段的设置。在划分源码时，插入分隔点以规定一个分隔点到下一个分隔点的过程为一段。如图11所示。在此情形下，如上所述，分隔点将自动地插在一同步指令的前后。

(3)步骤A2：排序

由串行程序综合装置根据排序规则把第一并行程序编程为一串行程序。作为一条排序规则，将优先级引入过程中。根据优先级执行的程序可视为一超串行程序，这是由于在执行中不出现非确定性。把一个变为串行程序又保存有关并行结构程序信息的程序定义为一超串行程序。

一种基于“过程的优先级”的方法可以用作一种顺序编程方法。根据这种方法，预先对这些过程设置一固定的优先级，并优先执行过程中具有较高优先级的那些段。用这一操作，可以得到不受非确定性影响的一顺序执行次序。

图12示出的是另一种可用的顺序编程方法，它是“优先执行同步指令等待侧(排序规则1)的方法”或“优先执行同步指令发送侧(排序规则2)的方法”。

一个超串行程序包括三种程序信息(即，段信息、程序结构信息和排序信息)。

段信息包括一个段标识符(ID)以及段所属的一个源码。程序结构信息包括在原先的并行程序中对于每个过程的段执行次序信息以及不同过程的段之间的数据依从关系。排序信息包括由串行程序综合而得到的综合段执行次序信息以及与良好并行性有关的信息。作为一个例子，顺序信息可以用对一并行系统建模用的皮特里(Petri)网来表示。

(4)步骤A3：超串行程序的测试/调试操作

由测试执行装置15对超串行程序进行测试。如果检测得一个错误，则由校正装置9进行调试/校正。如果在程序的校正中包括了同步指令的并行结构的改变或类似情况，则流程返回步骤A1，再次进行用程序综合装置8的建模、设置段以及顺序编程。由于已把一程序编程为一串行程序，如同在一串行程序中那样便于进行测试/调试操作。

(5)步骤A4：为超串行程序引入非确定性

超串行程序的结构由一非确定性引入装置17在输出装置5处示出。程序员在检查该结构时可以用非确定性引入装置17把具有良好非确定性的并行性明确地引入。此时，由分析装置10提取的超串行程序的程序信息支持程序员引入良好非确定性。如果不必引入良好非确定性，则流程进至步骤B2。

在一种引入良好非确定性的方法中，当用皮特里网来表示超串行程序的排序信息时，皮特里网将在保持程序结构的范围内重写，由此引入良好非确定性。

(6)步骤A5：测试/调试操作

如在步骤A3中那样，由测试执行装置15对已引入良好非确定性的超串行程序进行测试。如果检测出一个错误，则由校正装置9进行测试/调试操作。如果程序的校正包括一同步指令的并行结构的改变或类似情况，则流程返回步骤A1以再进行由程序综合装置作的校正、设置段以及顺序编程。将并行地执行引入并行性的部分。

如果超串行程序的排序信息用皮特里网来表示，则采用皮特里网模拟器来执行与具有一标志的处所相应的段，由此实现对超串行程序的测试。

(7)步骤A6：对部分超串行程序引入/扩展良好非确定性

对已在步骤A5中测试/调试的超串行程序加入有关良好非确定性的信息。把步骤A5至A6重复预定数目的次数以逐渐扩展良好非确定性。

如果需再引入良好非确定性，则如在步骤A5中那样，由非确定性引入装置17加入并行性，而流程返回至步骤A6。否则，流程进至步骤B2。

(8)步骤B2：自动并行

从超串行程序中自动提取容许并行编程的那一部分，在该程序中，已由程序员根据超串行程序的分析信息12引入了良好非确定性，提取是由分析装置10作的。由并行程序综合装置18用并行规则可以自动地扩展超串行程序的并行操作。

并行规则如下：

由分析装置10从程序信息中提取基于数据依从关系和控制依从关系的在先约束，而可将不具有在先约束的一段编程为一并行程序。可以用预定的并行规则作并行编程处理。如图13所示，对于用皮特里网表示的排序信息的重写规则可以用作为一条并行规则。数据依从关系和控制依从关系是公知的。

(9)步骤B3：并行编程

并行程序综合装置18对一并行程序15进行综合，在该程序中，由于自动扩展了超串行程序的并行性，因此超串行程序的程序信息被反映在源码上。

并行程序的测试/调试操作一般要比串行程序的测试/调试操作困难得多。这些由于因并行性产生的程序的非确定性使程序呈现了在某一时刻处理程序员未预料的特性。在并行程序的测试/调试中，程序员未预料的由并行性产生的错误(不良非确定性)在测试中一一被检测出来并加以排除。然而，在此方法中，很难完全排除错误，而且要花费更多的劳动。

在本发明的超顺序编程中，把一个并行程序编程为一个串行程序，而把程序员想要的并行性逐渐引入程序中。最后，把一个容许自动并行编程的部分编程为一并行程序，由此恢复并行程序。

更明确些说，在本发明的超顺序编程中，不是从一并行程序中消除不良非确定性，而是在串行程序中引入良好并行性，在超顺序编程中，从一个串行程序出发以由底向上的方式对一个并行程序进行编程。由于这个原因，在一未预料的时刻，不能产生出错误，使所需编的程序是高度可靠的程序。此外，大大改善了测试/调试操作。在顺序编程中，由顺序编程可能引起性能的降低。然而，由于可以采用一种自动并行编程技术(诸如在超大型计算机或类似计算机场合中的FORTRAN)，因而在许多情形中并没有被实际问题难住。

上面已经描述了第二个实施例的基本安排和操作。下面将描述第二个实施例的详细例子。

(a)第一个例子

图14是表示一并行程序的图。以并行的方式运行过程P1和P2。过程P1和P2访问共享存储器M。

(1)步骤A1：建模

如图15那样描述一并行程序P

(2)步骤B1：设置段

在本情形中，假设每个指令只形成一段。为简化描述，段ID定义为指令本身。

(3)步骤A2：排序

由引入过程优先级进行串行程序的编程。更明确些说，P1》P2(过程P1要优先于过程P2执行)。此时，排序段的执行次序表示如下：

init1→read1→write1→read2→write2

如图16A至16C所示，由顺序编程而得到的一超串行程序由段信息、程序信息和超串行信息组成。排序信息是由皮特里网表示的执行次序。

(4)步骤A3：超串行程序的测试/调试操作

执行超串行程序。如果检测出一个错误，就对每一段的源码或一原先的并行程序进行校正。在本情形中，假设未曾检测出错误。

(5)步骤A4：为超串行程序引入良好非确定性

在显示装置上显示排序信息的皮特里网，并把顺序关系切断以进行并行编程。在本情形中，断开write1和read2之间的顺序关系(图17(a))。可以断开write1和read2，因为在程序结构信息中它们没有执行次序关系。在这一步骤中，根据分析信息20(后面描述)可以提供这样一个信息，它关系到顺序关系应断开还是不应断开。

(3)步骤A5：测试/调试操作

执行已引入并行性的超串行程序。在本情形中，可以这样来执行程序，使得

init1→read1→write1→read2→write2，或者

init1→read1→read2→write1→write2。

如果在执行中检测出一个错误，就对程序进行校正。在本情形中，假设未曾有错误被检测出来。

(7)步骤B2：自动并行编程

从超串行程序的排序信息和程序信息之间的数据依从关系由分析信息20可得到段间的在先约束。这个在先约束是分析信息。在先约束是对具有数据依从关系的段之间的执行次序的限制。更明确些说，在具有数据依从关系的段之间，根据执行的次序，计算结果可能改变。因此，应该保持由排列信息决定的次序。在本情形中，有下述三种在先约束：

init1→read2

init1→write2

read1→write2

例如，由过程P1在read1读得的一个值要看过程P2的write2是发生在read1之前还是在read1之后，而受影向。在排序信息中，设置read1→write2为一在先约束。

对于没有在先约束的那些段，可以进行并行编程，并根据并行规则可以进行自动并行编程。因为在read1和read2之间没有在先约束，如图17(b)，可以用并行规则1(图13)。

(8)步骤B3：并行编程

并行程序的源码可以从已得的串行程序以自动并行编程得出。在本例中，为实现图11中的排序信息1和排序信息2的同步指令(发送和等待)嵌在源码中。其余的排序信息是原先的并行程序的排序信息(执行次序)。经变换的程序示于图18。

在具有如图14所示的结构的并行计算机上执行并行程序。

(b)第二个例子

第二个例子表示进行的超顺序编程，其时并行程序有一条同步指令、一个循环结构和一个条件分支。

(1)步骤A1中的建模和步骤B2中的设置段都省略了。假设已经给出了一并行程序，该程序的段执行次序(程序结构信息)如图19所示。注意，该并行程序有同步指令(发送和等待)和一数据依从关系(S13和S22)以及一循环结构和一条件分支。

(2)步骤A2：排序

通过把优先级(过程P1比过程P2有较高的优先级，即，P1》P2)引入过程中，可以进行串行程序的编程。顺序编程的结果如图20所示。即，超串行程序具有图19和20中的程序结构信息和排序信息(段信息省略)。注意，根据同步指令，过程执行次序改变了。例如，由于等待指令，P2的S21要在P1的S12执行后再执行。循环和分支结构也用皮特里网来表示。

(3)步骤A3：超串行程序的测试/调试操作

执行超串行程序。如果检测出一个错误，对每段的源码或原先的并行程序进行校正。在本情形中，假设未曾检测出错误。

(4)步骤A4：对超串行程序引入良好非确定性

在显示装置上显示排序信息的皮特里网，再断开顺序关系，由此进行并行编程。这里明确地假设未曾引入良好非确定性。

(5)步骤B2：自动并行编程

从超串行程序的排序信息和程序信息之间的数据依从关系中可以得出段间的在先约束。在本情形中，只有一条在先约束S22→S13。对于循环结构，可在在先关系下构造循环。在本情形中，只有在一循环中的在先关系值得注意。对于没有在先约束的那些段，可以进行并行编程，并可根据并行规则进行自动并行编程。用图13中的并行规则1和并行规则2可以最终得到图21中的并行程序。

(6)步骤B3：并行程序的变换

如在第一个例子中那样，可以采取把同步指令嵌在其余的排序信息中的做法来对并行程序进行编程。第三个实施例

图22是示出按照第三个实施例的并行编程支持设备安排的方框图。图23是示出按照第三个实施例的并行编程方法的步骤的流程图。

在本实施例中，串行程序综合装置12由测试执行装置401和测试情形存储装置402构成。由前面的实施例不同，串行程序综合装置12不采用特殊的排序规则而是进行随机顺序编程。下面将详细描述此实施例。

在本实施例中，并行编程是用下述步骤实现的。在此情形中，如象第一并行程序那样，考虑由独立运行的过程P1和P2组成的一个简单并行程序。

(1)步骤A1：建模

对于一目标并行系统利用并行性进行自然建模。确定并行系统的每个过程结构。此外，按照用一并行程序的编程，把具有一并行结构的并行程序作为一源程序来描述。在此源程序中可能有一隐藏的错误。在本情形中，对二个过程P1和P2编程，如图24所示。

(2)步骤C1：测试

测试情形从测试情形存储装置402用测试执行装置401读出。执行来自CP文件存储装置11的第一并行程序，而把执行结果显示在一输出装置5上，由此完成一随机测试。

在本情形中，假设执行记录如下：

log1＝job11→job12→job21→job22

(3)步骤C2：确定错误

作为步骤C1中的测试结果，如果没有检测出错误，流程就进到C4，否则，把执行记录存储在一执行记录存储装置403中，而流程进至步骤C3。如果检测到一错误，则流程进至步骤C3。在本情形中，假设没有检测到错误，而流程进至步骤C4。

(4)步骤C3：测试/调试操作

根据存储在执行记录存储装置403中的执行记录，用输出装置5检测到一个错误，而存储在CP文件存储装置11中的第一并行程序用调试装置16来校正以排除错误。在测试/调试操作完成后，流程返回至步骤C1。

(5)步骤C4：积累执行记录

作为步骤C1中的测试结果，如果确定在步骤C2中不出现错误，把执行记录log1累加到执行记录数据库404中。执行记录是一超串行执行序列，并作为超串行程序的一种特殊方式来估计。

(6)步骤C5：确定其余测试情形的有/无

确定在测试情形存储装置402中是否保留有任何测试情形。如果在步骤C5中为YES，则流程返回步骤C1以继续进行测试。如果在步骤C5中为NO，则流程进至步骤A7。

在此步骤中，流程返回至步骤C1以检查另一测试情形并继续进行测试。假设，在此第二次测试中，把下面所示的执行记录log2存储在执行记录数据库404中：

log2＝job11→job21→job12→job22

(7)步骤A7：并行编程

由存储在CP文件存储装置11中的第一并行程序和存储在执行记录数据库404中的执行记录，由并行程序综合装置18对并行程序进行编程，并存储在第二CP文件存储装置19中，该程序只执行通过测试的路径。

在此步骤中，将按照下面的过程来对一个并行程序进行编程，该程序只执行存储在执行记录数据库404中的二个执行记录log1和log2。

(A)把所有的执行记录合一起以产生一全局转变系统(globaltransition systen，GTS)(图25A).

(B)把全局转变系统GTS投射在二个过程P1和P2上。此时，嵌入用来对过程的行为进行识别和同步的同步指令。经过综合的程序规定为P1′和P2′(图28B)。

(C)由于程序P1′和P2′的同步指令有一冗余度，故冗余度被消除。消除了冗余度最后的得到的过程规定为P1″和P2″(图25C)。

采用上述步骤，可对由二个过程P1″和P2″组成的一个并行程序CP″进行编程。在这个并行程序CP″中，可执行在适当运行的测试中确认的执行记录log1和log2。然而，不执行下面的未被测试的情形：

log3＝job21→job11→job12→job22

如上面所描述的，由于未被测试的情形不能执行，因此它是一个高度安全的程序。

根据第三个实施例，可以用对一串行程序编程几乎相同的难度对一个并行程序编程，因此用户能有效地进行测试。此外，因为未被测试的部分不能运行，因而能得到第二个效果如高可靠性等。第四个实施例

图26是示出按照第四个实施例的并行编程方法的步骤的流程图。

(1)步骤A1：建模

(2)步骤A2：排序

(3)步骤A3：超串行程序的测试/调试操作

上述步骤A1至A3与示于图4的那些步骤相同，因而省略对它们的详细描述。

(4)步骤A4：为超串行程序引入良好非确定性

通过一非确定性引入装置17，用户对一在步骤A3中已测试/调试的超串行程序指出其非确定性地运行的部分(将该部分称为“良好非确定性部分”)。由非确定性引入装置17指出的良好非确定性部分作为与良好非确定性相关的信息反映在超串行程序上。经过这一处理，把超串行程序变为具有一良好非确定性部分的部分超串行程序。指出良好非确定性部分的一种方法将在后面描述。

(5)步骤A5：部分超串行程序的测试/调试操作

对在步骤A4中得到的部分超串行程序进行测试/调试。更明确些说，对在步骤A4中引入良好非确定性部分的部分超串行程序进行测试/调试。在此情形中，当把部分超串行程序变为一执行形式并加以执行时，只有在步骤A4中引入的良好非确定性部分被变为具有并行结构的执行形式并加以执行，而对于没有引入良好非确定性的部分被变为具有原先的顺序结构的执行形式并加以执行。在此执行结果的基础上，对超串行程序进行测试/调试。如果变为执行形式的程序不能合适地运行，则要把在转换前引入至串行程序的良好非确定性部分视为实质上不须非确定性地运行的部分，因而取消并行编程。

(6)步骤A6：在超串行程序中扩展良好非确定性部分

在步骤A5中，把有关良好非确定性的信息加至部分超串行程序。把步骤A4至A6重复一预置的次数以逐渐扩展良好非确定性。

(7)步骤A7：并行编译

由元级缺省顺序性加以处理的部分超串行程序的缺省顺序性被取消(例如，直接把排序信息和并行信息嵌在源程序中)。此时，从部分超串行程序中提取出一无害非确定性部分(在该程序中，未引入有关良好非确定性的信息)。检查对于这部分作的并行编程以增加部分超串行程序的并行性。例如，由于分析了未引入有关良好非确定性信息的部分的过程之间的依从关系，因而取得了源程序的确定为没有依从关系的那一部分的顺序性。注意，要参照在步骤A2的顺序编程中分析的并行信息来完成无害非确定性部分的提取。

下面将详细描述按照第四个实施例的并行编程方法并行编程支持设备。

本实施例的特点在于使用显示在输出装置5上的超时序图来实现非确定部分的可视引入。超时序图是表示超串行程序的过程处理次序的转变图，在该超串行程序中，对于具有一并行结构的一并行程序引入了缺省顺序性。根据排序信息来显示超时序图。排序信息是在用串行程序综合装置12把并行程序变为超串行程序时产生的。

更具体些说，排序信息是具有预定字段的称为进程表的数据串组。图27示出了这种进程表的结构。

参见图27，名字段F1用于给出识别各个过程的名。指示字字段F2用于给出目标调用过程表(未示出)的指示字，用以存储一些过程中要被调用的一个过程(以后称为“目标调用过程”)的名。目标调用过程表是独立地安排的。过程优先级次序是由串行程序综合装置12在具有原先的并行结构(在某一过程点处，可执行多个过程)的一个程序的基础上确定的，而结果在此字段内描述。优先级次序字段F3的值由非确定性引入装置17改变，这将在后面描述。由于这一原因，优先级次序缓冲字段给出改变前的优先级次序，由使可以使改变前的状态复原。分组信息字段F5用以给出当形成特殊的节点组时识别各组的信息。把相应于已分组的节点组的过程组中被首先执行的过程的名写在分组信息字段F5中。

本实施例的串行程序综合装置12将在下面描述。

假设把示于图28的一个并行程序读入串行程序综合装置12。串行程序综合装置12分析此并行程序的并行结构。分析得示于图串行程序综合装置12分析此并行程序的并行结构。分析得示于图28的并行程序从概念上说具有如图29所示的并行结构。例如可以用树结构搜索算法来实现这种分析。串行程序综合装置12把分析结果写入进程表。更明确些说，串行程序综合装置12把优先级次序写入示于图27的进程表的优先级次序字段F3以引入缺省顺序性，由此把该程序变为一超串行程序。即，参见图29，在过程B被处理后，例如要根据该时刻系统的环境确定对过程C或D进行处理。在本情形中，串行程序综合装置12根据一预定的规则(排序规则)单独确定优先级。注意，虽然可以根据过程读次序或随机数来确定优先级，预定规则可以根据各种情况由用户自由设置。注意，本实施例中的超串行程序在概念上由一源程序和在元级处理源程序的排序信息组成。

假设根据预定的规则，过程C要优先于过程D被处理。在此情形中，在过程C的进程表的优先级字段F3中写入“1”，而在过程D的进程表的优先级字段F3中写入“2”。至于不需确定优先级的那些过程，在优先级字段F3中的连续地设置“0”。要在相同的分层级上在过程之间确定优先级。举例来说，图29中的过程C、G和I以及过程D、H和J是在相同级上的过程。而过程E和F的分层级要低一级。

用这种方式，串行程序综合装置12分析并行程序的并行结构以产生排序信息(进程表)并将信息记录在文件中。

图30A至30E示出由串行程序综合装置12对并行程序的结构进行分析而形成的进程表。图30A至30E示出相应于过程A至K的各个记录的字段的内容。更明确些说，过程B继过程A之后被调用，而过程A的优先级是“0”。在过程B中，指出随后调用过程C或D，而过程C和D基本上是非确定性的。由串行程序综合装置12分别派给过程C和D以优先级“1”和“2”。这意味着过程C要比过程D优先被调用(执行)。

下面将描述引入有关良好非确定性信息(即，指出良好非确定性部分的方法)。用户使用示于图3的非确定性引入装置17以交互操作进行良好非确定性部分的引入。更明确些说，非确定性引入装置17将一超时序图显示在输出装置5上。用户用一输入装置4来对超时序图引入/取消良好非确定性部分。

图31示出一超时序图。参见图31，每个节点表示一相应的过程，而用虚线箭头指出的弧线代表原先并行程序的并行结构。实线箭头指出过程的顺序结构，它是由串行程序综合装置12引入缺省顺序性得出的。过程执行次序根据顺序结构由连续的数字指定。在原先的并行程序中，过程C→G→I和过程D→E→F→H→J原先描述为以并行方式处理。然而，在超串行程序中，过程C→G→I是顺序处理的，然后再处理过程D和随后的过程。

用户可以用输出装置5以可见方式掌握这一超时序图。当由串行程序综合装置12把并行程序变为串行程序以产生排序信息后，用户通过指出显示超时序图也能在输出装置5处以可见方式掌握超时序图。在本实施例中，由非确定性引入装置17的超时序图显示控制装置30来显示此超时序图。在此用户接收到显示超时序图的指示后，超时序图显示控制装置30根据预定的已做在内的程序开始显示超时序图。

图32示出超时序图显示控制装置30的安排的功能方框图。

根据存储在排序信息存储装置31中的排序信息，超时序图显示控制装置30确定相应于各个过程的节点以及相对于并行结构和顺序结构的弧线(这些弧线代表了节点之间的调用关系)。一图像数据综合装置35将这些信息转变为在输出装置5处显示所需的图像数据。

顺序信息读出装置32从顺序信息存储装置31读出排序信息并将排序信息送至一并行结构分析装置33和一顺序结构分析装置并行结构分析装置33和顺序结构分析装置34根据排序信息来分析并行结构。更明确些说，并行结构分析装置33查询由指示字字段F2指出的目标调用进程表，由此在能被在名字段F1描述的过程调用的过程名之间规定一调用关系。除了此字段外，顺序结构分析装置34还查询在优先级字段F3描述的优先级，由此规定顺序结构。将并行结构分析装置33和顺序结构分析装置34得出的分析结果送至图像数据处理装置35。图像数据处理装置35根据接收到的分析结果，为显示相应于各个过程的节点综合图像数据，并为显示在过程间连接调用关系的二种弧(即，一种相应于并行结构，另一种相应于顺序结构)综合图象数据，并把图像数据输出至输出装置5。输出装置5根据图像数据显示转变图(即，超时序图)。

在显示超时序图中，最好这样来综图像数据，即把由顺序结构分析装置34分析的具有顺序结构的那些节点之间的连接关系加至由并行结构分析装置33分析的具有并行结构的那些节点之间的连接关系。换句话说，超时序图最好包含原先并行程序的并行结构。经这一处理，用户在识别原先的并行程序的并行结构时可为处理串行程序的流程(过程)引入良好非确定性部分。

当在输出装置5上显示超时序图时，图3中的非确定性引入装置17将由用户设置在等待输入良好非确定性部分的状态。在开始(部分)超串行程序的测试/调试时，没有引入非确定性部分。因此，在输出装置5上对所有的节点提供用于顺序结构的弧线，而不显示并行信息。并行信息是指加至引入良好非确定性的节点的信息。根据良好非确定性是否引入，可以在显示器由视觉来辨别(例如，由明暗或色彩的密度)并显示。对于具有层次结构的良好非确定性部分，其并行信息也可由视觉来辨别和显示。

用户用输入装置4可以进行良好非确定性部分的引入。稍后将详细描述引入良好非确定性部分的方法。对此作简要的描述，就是可详细描述引入良好非确定性部分的方法。对此作简要的描述，就是可以用输入装置在4在节点之间把反映顺序结构的连接关系(弧线)断开或连接起来。结果果，顺序信息存储装置31的内容由顺序信息改变装置36改变。改变后的内容由顺序信息读出装置再次读出并显示在输出装置5上。

下面将描述一个引入良好非确定部分的详细的操作例。

图33是说明引入良好非确定性部分的一种方法用的图。

当要对多个过程引入良好不确定性时，连续地指定这些过程相应的所要节点处于良好不确定性引模式。良好非确定性引入模式例如可由指定操作菜单选择并设置。

参见图33，如果在过程E和F之间允许有并行性，则节点E和F连续地用一由输入装置4操作的光标P来指定。被指定的节点变暗就可由视觉辨别出使它与其余未被指定的节点的区别。当完成指定所有的目标节点时，用户将它通知非确定引入装置17。经过这一操作，顺序信息改变装置36使顺序信息存储装置31中的进程表中相应过程的优先级次序字段F3的当前值相应于优先级次序缓冲字段F4，并同时将优先级字段F3的值改变至“0”。

即，在此实施例中，使在优先级次序字段F3中过程E和F的值“1”和“2”相应于优先级次序缓冲字段F4，与此同时，把这些过程的优先级次序字段F3的值改变至“0”。在由排序信息改变装置36对排序信息存储装置31更新后，再次将超时序图显示在输出装置上。此时，在过程E和F之间不设置优先级，因而不显示相应的顺序结构的弧线。即，在输出装置5上确认，过程E和F以并行方式工作。

图34示出一超时序图，在该图中，良好非确定性按上述情形引入。

以上述方式引入良好非确定性部分的程序(部分串行程序)用一测试执行装置15变为一执行形式，并执行一测试。用户根据测试执行装置15的执行结果来确认程序是否会合适地运行。应根据并行性对所有的路径执行这种运行确认。如果测试执行装置15不能合适地运行，则引入良好非确定性部分的部分可以认为是基本上不允许并行编程的部分。由于这一原因，由用户指定取消并行编程。

如引入良好非确定性部分那样，可以用指定的办法在非确定性部分取消模式中取消并行编程。用这一操作，顺序信息改变部分36使存储在排序信息存储装置31中的进程表中的优先级次序缓冲字段F4中的值返回至优先次序字段F3。

在此实施例中，由引入良好非确定性部分，也可进行在每一层次的分组。

举例来说，由于过程C、G和I的组(称为第1组)和过程D、H和J的组(称为第2组)处于同一层次，可以用并行的方式对这些组进行操作。当对这些过程独立地进行操作时，其可操作性很小。因此，将这些过程分组很有效。由选择一个分组模式来作这样的分组。说得更明确些，在分组模式中，当顺序选择目标节点，并询问选择是否完成时，把目标节点分组并作为一个新的单个节点来显示。

图35是一示出具有分组节点的超时序图。

参见图35，第1组节点和第2组节点用椭圆指出，它们可由视觉与其余未分组的节点相辨别。第2组具有较低的层次(过程E和F)，因而以不同的亮度来表示。用户可对这一超时序图指定一良好非确定性部分。注意，即使把一良好非确定性部分引入分组的超时序图，只需进行改变超始过程(过程C和D)的优先级次序字段F3的操作。

如上所述，当对一超时序图的节点引入一良好非确定性部分时，用输入装置4直接指出所需的节点。除这种方法之外，还可以用圈起一特定节点组的办法或用覆盖一特定节点组的区域的办法来指出。

因为由许多个过程和许多个相应的节点，有时可能难于在输出装置上达到一致。在此情形下，解决这一些问题的办法是只显示节点组。

在此实施例中，过程之间的优先级(由串行程序综合装置12确定)可以改变。更明确些说，通过在优先级次序改变模式中指出一所需的节点，可以改变目标节点之间的优先级次序。

假设图33中的超时序图中的过程E和F之间的优先级次序要在优先级次序改变模式下改变。如上所述，用户用输入装置4来指出节点E和F，并对非确定性引入装置17询问指出是否完成。经这一操作，排序信息改变装置36将排序信息存储装置31中的进程表中过程E的优先级次序字段的值改为“2”，而把过程F的优先级次序字段F3值改为“1”。经这一操作，在显示装置5上显示一新的超时序图。图36示出此时的超顺序图。如图36所示，在优先级次序改变后，顺序结构用的弧线也改变了。

可以有效地利用过程间优先级顺序的这种变化引入良好非确定性部分，因为可以保证用户所期望的过程间操作。更明确地说，用户用测试执行装置15将图33中的超串行程序转换成可执行形式并进行测试。接着，在改变优先级顺序以后用户对图36中的超串行程序进行类似的测试。通过该操作，如果肯定两者测试执行结果都与用户预计的相同，则可以认为能先执行过程E和F中的任一个。由此，能够引入一个良好非确定性部分。

本实施例中，已经描述了两个过程间非确定性的引入。对于三个或更多的过程，也可进行相同的操作。

图37说明了三个过程间良好非确定性部分的引入。在具有并行结构的过程B、C和D之间允许进行并行程序设计。然而，在图37中，只允许在过程B和C之间进行并行程序设计。通过良好非确定性部分的引入，获得图38中所示的超串行程序。更具体地说，图38所示的超串行程序指出，在两个过程B和C都执行之后再执行过程D。

如上所述，根据本实施例，显示在输出装置5上的超时序图同时将并行信息和排序信息呈现给用户。为此，用户可以在考虑到原始并行结构时选定良好非确定性部分。另外，良好非确定性部分并不在并行程序描述层次上选定/取消，而是对超时序图进行选定/取消。因此，能够容易地开发并行程序，而不需要高级的并行程序设计技术。第五个实施例

图39是第五实施例的并行程序设计支援设备的方框图，其中尤其详细示出了图3中的超串行程序(HSP)文件存储装置14和非确定性引入装置17。

参看图39，与上述实施例一样，存储在并行程序(CP)文件存储装置11中的第一个并行程序通过串行程序综合装置12进行顺序编程。将所获得的超串行程序存储在HSP文件存储装置14中的顺序过程表存储装置51中。注意，超串行程序在被存入顺序过程表存储装置51中之前，总是由调试装置(图39中未画出)在有序状态对其调试。

字段数据生成装置53将程序化超串行程序(顺序过程)转换成字段数据并将其存储在字段数据存储装置52中。将顺序过程表存储装置51和字段数据装置52的信息段作为中间文件存储在HSP文件存储装置14中。字段编辑程序55通过字段调整部分对取自字段数据存储装置52的字段数据进行编辑。

非确定性引入装置17由字段数据生成装置53、字段调整部分54和字段编辑程序55组成。将字段编辑程序55所编辑的字段数据转换成由并行程序综合装置18(字段数据转换装置)校正的并行程序并将其存储在第二个CP文件存储装置19中。

图40示出了存储在图39的CP文件存储装置11中的第一个并行程序，为便于描述，其中故意注入了一个错误。由于存在一个错误，故在以并行方式错误地执行过程P4和P5的同时，能以并行的方式执行过程P2和P6。图67中显示了正确的并行程序(以后再描述)。图41示出了图40中第一个并行程序所执行的过程流图，其中以并行方式分别执行过程P4和P5以及过程P7和P8。图42示出了一例存储在图39中顺序过程表存储装置51中的顺序过程。在串行程序综合装置12中以一定次序给在图40中第一个并行程序的并行部分赋值，从而进行串行程序设计。

图43示出了图42中所执行的过程流图。在该例中，由于是按过程P4和P5的次序附带进行了串行程序设计，所以与该点相关的错误被排除。如果按过程P5和P4的次序进行串行程序设计，则必须用通常的排错方法检查上述错误。所以可以在串行程序设计时排除错误的并行程序设计(错误的非确定性)。

图44是显示了在图39中的字段数据生成装置53中所执行的过程流的流程图。在该情况中，认为由一个过程到另一个过程的进程是出现一定约束和转换条件范围(区域)，从而将超串行程序(顺序过程)转换成字段数据。

如图44所示，步骤1中生成一个起始域，而步骤D3至D9被重复执行，直至最后的进程。在最后进程中，执行步骤E10至E12中的过程，然后结束处理。图45示出了由图44中所示的处理生成的通用域的数据结构。将该域连接起来组成总的结构而形成一个字段。

下面描述域A(i)中的信息。

(1)在域A(i)中，存在“constraint”中描述的约束(例如，P(x1)在P(x2)之前优先执行)。

(2)“transition”中描述了从域A(i)到另一个域的转换所需要的转换条件(例如，完成了P(z1)后允许转换至域A(j))。

(3)允许从域A(i)转换的域是域A(j)。

(4)转换至域A(i)之前的状态是域A(k)。

图46示出了一种状态，该状态中，通过图44所示的处理将图42中描述的程序转换成由一组域组成的字段。

该字段中的最强的约束是二个过程之间的次序关系。改变或解除该约束能够实现非确定性的引入。更准确地说，通过字段调整引入非确定性，从而进行并行程序设计。由于一般来说是根据约束来进行该调整，所以把约束和转换条件提给用户。

图47是在图39中的字段调整部分54中所执行的处理的流程图。步骤E1选择字段数据。步骤E2中，分析字段数据的域之间的耦合信息，以生成一个可视的字段，并且将字段显示在字段编辑程序55上。步骤E3中，用户输入一条命令，同时检查字段编辑程序55的显示，从而进行字段调整。

在步骤E5中，存储编辑期间的字段。如果结束了编辑，则通过步骤E17结束处理。注意，在步骤E14至E16中检查编辑中所引起的矛盾约束。

步骤E9是与约束重写处理相关的子程序。步骤E11是与约束加法处理相关的子程序。步骤E13是与约束删除处理相关的子程序。

图48是显示图47中进行步骤E9中处理的子程序的流程图。

对于在步骤E9-1中编辑的约束，步骤E9-2检查明显约束是否存在/不存在。如果存在明显约束，则在步骤E9-9中，告诉用户在约束重写处理中存在一个错误。步骤E9-10中使重写无效。如果不存在明显约束，则如在步骤E9-4所示重写字段。步骤E9-5至E9-8，进行字段检查。

图49示出了一种字段的变化，它由图48中步骤E9-4的约束改变操作的算法而产生。图49示出了将“before Pi Pj”转换成“beforePl Pj”的情形。图49中字段由(a)转换成(b)。在该情况下，域A(y)与域A(a)的“下一个”相连，并且域的属性作相应的改变。

图50是显示进行图47中步骤E11的处理的子程序的流程图。关于步骤E11-1中编辑的约束，步骤E11-2检查一明显约束是否存在/不存在。如果明显约束存在，则在步骤E11-9中告诉用户约束重写处理中存在一个错误。步骤E11-10中，使附加约束失效。如果不存在明显约束，如步骤E11-4所示重写场。步骤E11-5至E11-8中，进行字段检查。

图51显示了一种字段的变化，它由图50中步骤E11-4的约束加法操作的算法产生。图51显示了将“before Pj Pk”加至域A(y)中的情形。图51中字段由(a)改变为(b)。在这种情况下，域A(y)被加至域A(x2)的下一个域，并且域的属性作相应的变化。

图52是显示进行图48中步骤E13的处理的子程序的流程图。

由于一个域中至少必须有一个约束，所以在步骤E13-1中检测指定域A(y)中约束的数目。如果数目是一，则在步骤E13-8中显示出错信息，从而结束处理。如果存在多个约束，则删除用户指定的约束，并且如步骤E13-3重写字段。在步骤E13-4至E13-7中，进行字段检查，以防止生成明显约束。

图53显示了一种字段的变化，它由图52中步骤E13的约束删除操作的算法产生。

图53显示了一种情形，其中“before Pj Pk”被删除，并且图53中字段由(a)变成了(b)。在这种情况下，域A(x2)与域A(z)的前一个域相连，并且域的属性作相应的变化。

图54是显示用来检测引起字段中矛盾的明显约束的处理的流程图。图48中的步骤E9-2和E9-5、图50中的步骤E11-2和E11-5以及图52中的步骤E13-4共同执行该子程序。在这种情况下，尽管存在“before A B”和“before B C”，但检测出诸如“before A C”等明显约束。

参看图54，重复步骤E9-2-3至E9-2-6以生成一个明显约束，并且在步骤E9-2-7检测约束集的公共元，从而完成处理。例如，假设一个包含明显约束“before A D”的字段。在这种情况下，按图56中暂时集(a)、暂时集(b)和暂时集(c)的顺序执行上述处理，从而检测公共元“before A D”。

图57给出了字段编辑程序55上的显示。在字段编辑程序55中，通过指定菜单71进行字段的读和存储、约束编辑和显示模式的改变。当选择由矩形所指示的区域72时，将出现编辑屏73。图58示出了一例将“二维-显示模式”选为显示模式时的字段显示。在该模式中，字段被二维地显示。图59示出了一例将“三维-显示模式”选为显示模式时的字段显示。在该模式中，字段被三维地显示。由此，如果字段变得非常大，或者存在许多并行处理部分，则能容易地监视整个字段。

图60至67显示了图47中的算法对图45所示的字段数据逐步调整的情况。

在图60中，假设用户规定过程P5和P6之间不存在因果关系，并且过程P6在过程P2之后，不呈现错误的非确定性行为。在这种情况下，如图60所示，当进行重写约束的编辑时，将获得图61中所示的显示。在图61中，假设用户规定过程P6和P4之间不存在因果关系，并且正确的顺序只存在于过程P4和P3之间。在这种情况下，如图61所示，当进行删除约束的编辑(“before P6P4”)时，将获得图62中所示的显可。类似地，当用户检查域中的约束并逐步编辑字段时，字段数据如图63→图64→……图67般变化。

图68是显示了图39中通过并行程序综合装置(字段数据转换装置)18所执行的处理的流程图。如图68所示，并行程序综合装置18从字段数据存储装置52中读取字段数据(步骤F1)；分析域间的图形结构以生成过程流(步骤F2)；分析所得的过程流，以生成只引入非确定性的并行程序源；以及将该并行程序源存储在第二个CP文件存储装置19中(步骤F4)。

图69显示了通过使并行程序综合装置18分析并转换图67所示状态下的字段而获得的并行程序。如图69所示，对过程P4和P5的并行执行作校正，在图40的第一个并行程序曾假设它为一个错误。取而代之，进行具有良好非确定性的过程P3和P6的并行程序设计。

图70显示了图69中并行程序所执行的过程流图。

根据本实施例，将有序并行程序的过程流称为由约束和转换条件组成的字段。对字段进行调整以引入良好的非确定性，从而有效地生成高质量的、没有任何错误的并行程序。在本实施例中，当有序程序取消约束而开始并行程序设计时，图形拉长的字段垂直延伸。由此，可直观地看到并行程序设计有利于方便操作。第六个实施例

在根据本实施例设计并行程序及其程序设计支援设备的方法中，测试/调试了超串行程序。另外，在超串行程序中引入了与良好的非确定性相关的信息。

图71是显示第六实施例并行程序设计支援设备安排的方框简图。参看图71，根据用户命令从输入装置4读出存储在CP文件存储装置11中的第一个并行程序并将其输入串行程序综合装置12。根据存储在排序规则存储装置13中的排序规则将输入至串行程序综合装置12中的第一个并行程序转换成完全超串行程序HSP，并且将该完全超串行程序HSP存储在能存储多个超串行程序的HSP文件存储装置14中。

用测试执行装置15测试完全超串行程序HSP。如果在完全超串行程序HSP中发现错误，则用调试装置16校正错误。当完成测试/调试操作时，将作为结果的完全超串行程序HSP存储在HSP文件存储装置14中。HSP的执行顺序，以生成另一个完全超串行程序HSP。反复测试/调试该完全超串行程序HSP，并将作为结果的完全超串行程序HSP存储在HSP文件存储装置14中。那就是说，良好的非确定性表现为多个完全超串行程序，而不是部分超串行程序。如果非确定性引入装置17完成了良好非确定性的引入，则并行程序综合装置18根据最终存储在HSP文件存储装置14中的一组完全超串行程序HSP生成并行程序，并将其存储在第二个CP文件存储装置19中。第七个实施例

本实施例的组件与第六实施例(图71)中的相同，所不同的是其程序设计过程，所以将省略其详细描述。图72是显示第七实施例中关于并行程序设计方法主程序的流程图。

(1)步骤A1：建立模型

用并行性对目标并行系统进行自然建模。确定并行系统的每个过程结构。另外，每一过程中，根据运用并行程序的程序设计将具有并行结构的并行程序称为源程序。潜在的错误可能存在于该源程序中。

(2)步骤A2：排序

引入缺省顺序性，将第一个并行程序转换成具有顺序结构的超串行程序。在本实施例中，在元级上引入顺序性。元级并非定义成源程序本身(即，第一个并行程序)，而是定义为源程序执行管理级。例如，用源程序的独立管理调度程序将并行程序中描述的源程序转换成能保证顺序执行的源程序。

(3)步骤A3：超串行程序的测试/调试操作

测试/调试超串行程序。在由测试执行装置获得的超串行程序测试结果的基础上，用调试装置从超串行程序中排除错误。能够同串行程序中常规的测试/调试方法所采用的方式一样进行测试/调试操作。重复测试/调试操作，直至保证了串行程序的常规运行。作。重复测试/调试操作，直至保证了串行程序的常规运行。

(4)步骤G1：并行假程序设计

为步骤A3中的超串行程序测试/调试引入成为并行候选的过程组，并且变换装置20综合多个并行假操作序列。在本实施例中，在元级上引入并行假操作序列。

(5)步骤G2：执行/检查并行假操作序列

在步骤A3中的测试/调试超串行程序上执行步骤G1所获得的并行假操作序列，并检查执行结束。该执行再次在超串行程序上产生一个程序并行操作的假状态。用户将每个操作结果正确与否记录到并行假执行装置(未示出)中。

(6)步骤G3：选择良好的非确定性进行部分排序

引入非确定性，它允许正确执行并行假操作序列并排除并行假操作序列的不正确执行，表现为良好的非确定性。步骤G1至G3进行预定次数以逐渐扩大良好的非确定性。

(7)步骤A7：并行编译

从引入了有关良好非确定性信息的部分超串行程序中抽取无害的非确定部分。并行地对非确定部分编程，以便将所有的部分超串行程序转换成一个并行程序。将位于元级上的缺省排序所给出的顺序性反射(例如，嵌在源程序本身之中)到并行程序上，并取消元级的缺省排序。

图73是一例用户假设的并行程序。P1、P2、P3等等代表程序的执行单位，并称之为过程。图73显示出过程P3、P4和P5是并行执行的，而过程P7、P8和P9是顺序执行的。另外，由过程P2、P3、P4、P5和P6组成的过程组以及由过程P7、P8和P9组成的过程组可以并行执行。

按并行模型中过程的剩余次序将所有过程排队，从而获得超串行程序HSP。

图74是一个为由图73中并行程序所获得的超串行程序执行序列建立模型的例子。在排序模型中，根据具体情况，按一定的顺序或相隔一定距离放置并行执行的过程P3、P4、P5等等。把它们之前执行的过程P1和P2放在过程P3、P4和P5中任何一个之前。把在它们之后执行的过程P6和P10放在过程P3、P4和P5中任何一个之后。在对由过程P2、P3、P4、P5和P6组成的过程组和由过程P7、P8和P9组成的过程组排序时，组与组之间的前后顺序是供选择的项，然后根据具体情况交替出现两个组中的过程。

用户从输入装置14发出指令，将超串行程序HSP输入测试执行装置15并且进行测试。测试执行装置15将测试执行结果送至输出装置。用户可以根据测试执行结果借助输入装置4对超串行程序进行预定的调试。用户在对超串行程序进行预定调试之后，从输入装置4给出进行再测试的指令。通过该过程，将已调试的超串行程序输入测试执行装置15并再次测试。通过测试/调试检查超串行程序操作是否正常，并且用非确定性输入装置17将超串行程序转换成部分超串行程序。首先，将超串行程序转换成多个并行假程序，并且从并行假程序的执行结果中将有关良好非确定性的信息累加起来。该过程如图75所示。根据图75的过程，图76A至79B的例子显示了将图74的顺序模型转换成并行假模型并获得部分顺序模型的过程。

现将说明本例的过程。

在图76A中，利用诸如指针器等将P3、P4和P5选为并行假选择(步骤H1)。另外，每一过程都单独指定单位并行性(步骤H2)。在图76A至76C中，用不同的颜色来区分并行单位。在超串行程序中，按P3、P4和P5的顺序执行并行假选择内部的过程。

在图76B中，交换P4和P5，作为并行单位的一置换(步骤H3)，并获得并行假操作序列。在并行假操作序列中，按P3、P4和P5的顺序执行并行假选择内部的过程。如果执行该程序能保证执行结果(步骤H4)，则能获得如图76C所示的程序(步骤H5)。在超串行程序中，在执行了并行假选择内部的过程P3之后再并行执行过程P4和P5。

用户在同一选择中指示扩大非确定性(步骤H6)，在图77A中置换P3和P4&P5对(步骤H3)，以获得另一个并行假操作序列。在并行假操作序列中，执行了并行假选择内部的过程P4和P5之后再执行过程P3。通过执行该程序检验正确性(步骤H4)，从而获得具有图77B非确定性的程序(步骤H5)。在部分超串行程序中，在并行假选择的内部并行执行过程P3、P4和P5。由于并行假选择内部的非确定性变得很充分，所以通过该操作，过程由步骤H6进行至步骤H7。当用户指示扩大并行选择时(步骤H7)，则如图78A至79B所示返回步骤H1重复同一过程。

通过用户发出的指令将由不断引入有关良好非确定性的信息所获得的部分超串行程序输入并行程序综合装置18。并行程序综合装置18将只具有良好非确定性的部分超串行程序PHSP作为第二个并行程序记录在第二个CP文件存储装置19中。用户能用输出装置5观察第二个并行程序，并最后能进行测试/调试。

根据本实施例，在超串行程序上能够充分检验并行程序的操作。通过为超串行程序指出并行候选选择可以一步步地将超串行程序转换成并行程序。另外，通过引入并行性能够获得可被正确操作的并行程序，所述并行性只允许对非确定性检验是否根据并行假操作序列按顺序进行正确的操作。由此，并行程序的测试/调试就更为容易了。第八个实施例

根据本实施例，如图80所示，在如图2安排的计算机系统中，至少将一个过程(即，过程A至D)寄存在处理器1-1至1-N中。在过程执行环境中(其中每一个过程均按同时并行/并行方式进行的，并采用过程交换消息以完成信息的交换和处理)，对并行程序进行程序

在本实施例中，运用并行程序测试对超串行程序进行测试。当超串行程序中存在一个错误时，不是去纠正作为源代码的并行程序，而是纠正排序规则以测试/调试超串行程序。

图81是显示本实施例并行程序设计支援设备安装的方框简图。

参看图81，串行程序综合装置12根据存储在排序规则存储装置13中的排序规则从CP文件存储装置11中将元级上的缺省顺序性引入第一个并行程序，从而将第一个并行程序转换超串行程序(HSP)，然后将该超串行程序记录在HSP文件存储装置14中。排序规则变成了由于执行执行装置22中的源程序(CP文件)而获得的执行记录信息。HSP文件存储装置14存储一对CP文件和用作排序规则的执行记录信息。用户可以在输出装置5上检验该超串行程序HSP。根据用户的命令从输入装置4将该超串行程序输入测试执行装置15中，并在测试执行装置中对其进行测试。

测试执行装置15将测试执行结果(执行记录)输出到输出装置5。用户根据该测试执行结果运用排序规则校正装置21在排序规则存储装置13中校正排序规则，从而对超串行程序HSP进行预定的测试/调试操作。

当在校正排序规则后完成了对超串行程序HSP的预定测试/调试操作时，从输入装置4输入再次执行测试的命令。测试/调试过的超串行程序HSP被输入测试执行装置15中并再对其进行测试。重复该测试/调试操作，直至超串行程序HSP肯定能正常运行为止。

当通过测试/调试操作以后能确定对超串行程序进行正常的运行时，用排序规则校正装置21校正存储在排序规则存储装置13中的排序规则。将校正了的排序规则重新存储在排序规则存储装置13中。通过该排序规则的校正，在超串行程序中部分引入与非确定性相关的信息。将超串行程序HSP转换成部分超串行程序PHSP。

为了使无害的并行性潜藏在部分超串行程序PHSP中，串行程

为了使无害的并行性潜藏在部分超串行程序PHSP中，串行程序综合装置18按划分标准选定装置23将对应于部分串行程序PH-SP的一部分排序规则划分成过程单位。然后将部分超串行程序PH-SP转换成允许起始命令按过程单位控制的第二个并行程序19。

图82是一流程简图，说明本实施例中并行程序设计方法的顺序。

(1)步骤A1：建立模型

用并行性对一目标并行系统进行自然建模。确定并行系统的每一过程结构。另外，每一过程中根据用第一个并行程序进行的程序设计把具有并行结构的并行程序称为源程序。该源程序中可能隐含着错误。

(2)步骤A2：排序

引入缺省顺序性，将第一个并行程序转换成具有顺序结构的超串行程序。在本实施例中，在元级上引入缺省顺序性。元级并非定义为源程序本身的级，而是用来管理源程序执行的级。例如，所谓排序是指用源程序独立管理的调度程序顺序执行并行程序中描述的第一并行程序。也就是说，排序是使CP文件存储装置11与排序规则存储装置13相对应。因此，作为结果的顺序程序由一对第一个并行程序和排序规则组成。

(3)步骤A3：超串行程序的测试/调试操作

执行已在步骤A2中排序过的超串行程序，以便进行测试。在该情况下，测试执行是根据排序规则来运行第一个并行程序的。如果存在功能错误，则校正第一个并行程序，且流程返回至步骤A2。如果存在定时错误，则流程行至步骤G1。如果不存在定时错误，则存储该排序规则，且流程行至步骤A4。

(4)步骤G1：校正排序规则

如果步骤A3中存在定时错误，则校正排序规则，且流程返回步骤A2。

(5)步骤A4：引入良好的非确定性

如果需要添加良好的非确定性，则校正排序规则，且流程返回步骤A2。如果不需要添加良好的非确定性，则流程行至步骤A7。

(6)步骤A7：并行编译

从存储在步骤A3中的排序规则中抽取无害的非确定部分，且并行设计被抽取的部分，从而将所有部分超串行程序转换成第二个并行程序。

图83显示了记录信息，它代表在执行具有图80中所示的进程间通信的并行程序时的执行历程，其中在元级上引入缺省顺序性。

用户能在输出装置5上检验该记录信息。参看图83，用垂直滚动杆滚动显示信息，以随时检验记录信息，如果引入良好的非确定性且有多个可执行的候选有效，则用水平滚动杆检验候选信息。通过使用垂直和水平滚动杆，能够检验所有记录信息中的任一位置。当选定相应的操作(以后描述)时，可以选择显示在荧屏上部的“校正次序”，和“非确定性引入”，以选定处理方法。

另外，可以通过输入装置4输入用户命令，从而将存储在HSP文件存储装置14中的第一个并行程序和执行记录信息文件输入到测试执行装置15中，将结果程序作为超串行程序HSP来测试。

测试执行装置15将测试执行结果输出至输出装置5。用户可以运用输入装置4根据该测试执行结果对超串行程序HSP进行预定的测试/调试操作。如果存在功能错误，则在校正CP文件存储装置11中的第一个并行程序时可以进行测试/调试操作。如果存在定时错误，则校正排序规则存储装置13中的执行记录信息，以使经校正的第一个并行程序与执行记录信息相对应，从而再次设计超串行程序。

当用户对超串行程序进行了测试/调试操作之后，他再从输入装置4输入进行测试的命令。将测试/调试过的超串行程序HSP输入测试执行装置15中，再次进行测试。重复进行该测试/调试操作，直至肯定了能正常操作超串行程序HSP。

当通过测试/调试操作肯定了能正常操作程序HSP时，用排序规则校正装置21在超串行程序中部分引入与良好的非确定性相关的信息。由排序规则校正装置21引入的与良好的非确定性相关的信息被影射在记录信息上并记录在HSP文件存储装置14中。根据用户命令，用测试执行装置15测试具有由排序规则校正装置21引入的有关良好非确定性的信息的超串行程序(部分超串行程序PHSP)，从而进行测试/调试操作。在这种情况下，部分超串行程序PHSP的行为在引入了与良好非确定性相关的信息的部分是非确定的。为此，最好测试/调试所有的行为。用这种方式，反复进行测试/调试操作和引入与良好的非确定性相关的信息，逐步加入与良好的非确定性相关的信息。

根据用户指令将通过连续引入与良好的非确定性相关的信息而获得的部分超串行程序PHSP输入并行程序综合装置18。并行程序综合装置18从部分超串行程序PHSP中抽取无害的非确定部分并将所有部分超串行程序合并成一个并行程序。更具体地说，按过程单位划分综合记录信息，以便定义一个起始顺序并按过程单位进行起始控制，从而取消缺省顺序性。将部分超串行程序转换成并行程序，然后将其记录在第二个CP文件存储装置19中。用户在输出装置上检验该并行程序，从而进行最后的测试/调试操作。

图84显示了设计与步骤A2至A4中的过程相关的部分超串行程序的配置。以下将描述实现各组成部分功能的方法。

图85显示了在过程中交换的消息的格式。在“目的信息”中设置用来选定诸如目的过程名等信息目的的信息，并且在“源信息”中设置定义诸如源过程名等源的信息。在“消息体”中设置将要在过程中交换的数据。

用图85中消息格式中的目的信息和源信息生成作为记录信息存储起来的信息。在以下的描述中，作为记录信息，只有目的过程名被用作目的信息，而且只有源程序名被用作源信息。然而，当多次进行一个过程时，由于无法相互区分相同过程的个数，因此可以以{过程名、过程起始计数}的形式扩展源信息。另外，假设在给定过程的一个操作期间多次传送消息。在这种情况下，为了指定专用的传送操作的个数，可以以{过程名、过程起始计数、消息传送计数}的形式扩展源信息。如果每个过程具有一个多个处理操作的单位(以下称之为方法)，则也添加其信息，从而以{过程名、方法名、消息传送计数}的形式获得源信息。

不需要将目的信息限制为目的过程名，它还可以呈{目的过程名、方法名}的形式。由于按照执行形式组合目的信息和源信息，因此所有八种组合都是有效的。

首先，将详细描述执行装置22。

如上所述，随机地执行第一个并行程序。在这种情况下，执行记录用作排序规则，将所有进程间通信作为排序规则发送给过程组控制装置203并将其存储在接收消息保持装置204中。过程组控制装置203按序从消息保持装置204中抽取消息，并再次将它们发送给正式的目的地。为此，由过程组控制装置203按序控制所有过程的起始操作，从而顺序地处理第一个并行程序。

这时，记录信息获取装置202将过程组控制装置203按序处理的消息作为记录信息按时序保持在记录信息存储装置201中。该记录信息足以构成排序规则存储装置13，并成为接下来顺序执行中的执行限制条件。

图86显示了通过过程组控制装置203进行进程间通信的状态。假设从过程A和B将消息传送给过程C。再假设存在良好的非确定性，它表示能够将过程A和B中任何一个的消息首先发送给过程C。在这种情况下，当执行中偶然将过程A的消息早于过程B发送出去时，首先将{过程A→过程C}存储在记录信息中，然后将{过程B→过程C}存储在记录信息中。图87中显示了作为排序规则的记录信息。

在串行程序综合装置12中，使存储在CP文件存储装置11中的第一个并行程序对应于用作如上所获得的排序规则的记录信息。将具有并行性的第一个并行程序转换成添加了排序信息的超串行程序。

在进行测试/调试操作时，过程组控制装置203暂时接收进程间交换的消息，并根据存储在记录信息存储装置201中的记录信息所代表的顺序将交换消息传送至可靠的目的地。为此，过程组控制装置203具有一个从保持在接收消息保持装置204中的消息中抽取消息且传送被抽取消息的装置。

如上所述，由于过程组控制装置203是按记录信息选定的顺序传送消息的，所以能够解决处理顺序的非确定性这个并行程序中的一大困难，从而实现良好的处理再现性。更具体地说，图86中，在给定的一个测试中，即使过程B早于过程A将消息发送给过程C，则可以进行下述操作，即，如图87所示，只要过程组控制装置203在记录信息中指定首先将过程A的消息发送给过程B。将过程B的消息保持在接收消息保持装置204中。当接收到过程A的消息并将其传送给过程C之后，再将保持在接收消息保持装置204中的过程B的消息发送给过程C。

图88显示了过程组控制装置203的处理流。

如果存在功能错误，则在校正源程序之后必须再从步骤A2开始进行超串行程序的测试/调试操作，该超串行程序的执行顺序仅仅根据存储在记录信息存储装置201中的记录信息来确定。然而，如果存在定时错误，则容易进行测试/调试操作。更具体地说，校正用作排序规则的记录信息，重写记录信息，从而代表预计中的顺序。

排序规则校正装置21中的记录信息校正装置205根据用户指令校正用作排序规则的记录信息。如图83所示，记录信息校正装置205具有能按处理顺序(时序地)显示记录信息的显示部分。如图89所示，想要校正定时错误的用户开始操作置换部分，以置换记录信息或改变记录信息的顺序，并且选定将改变其处理顺序的消息。图89中，提出了两个消息的顺序的置换，但可以改变多个消息的顺序。至少可以将一个消息定义为一个集合，而集合的顺序可以改变。记录信息校正装置205具有一个能够根据置换部分的选定将记录信息重写在记录信息存储装置201中的重写部分。如图90所示，重写图89中的信息。可以将用指针器选定消息的方法、在屏幕上输入消息的行数的方法或者类似的方法来作为选定这个将被置换的消息的方法。

当如上所述将记录信息按预计的顺序置换时，过程组控制装置203在执行测试过程中改变接收消息的顺序，以将其传送给可靠的目的过程，从而容易地校正定时错误。

例如，参看图86，假设过程B处理过程B的消息早于处理过程A的消息。在这种情况下，如图89所示，如果记录信息表示先处理了过程A的消息，则如图90所示根据上述过程校正记录信息。因此改变过程组控制装置203的消息处理顺序，以排除定时错误。

通过运用定时错误排除方法，改变了过程的处理顺序，从而无需校正源程序就能容易地进行测试/调试操作，从而在程序开发中提高生产率。

以下将描述引入良好的非确定性的方法。

记录信息校正装置205中的非确定性引入部分中的校正记录信息引入良好的非确定性。这暗示着用户企图将良好的非确定性引入超串行程序。在图86所示的处理中，如果过程A和B中的一个能首图92A和92B所示，非确定性引入部分以取消被选消息的顺序限制的形式来校正存储在记录信息存储装置201中的记录信息。图92B显示了通过利用水平滚动杆使图92A中的信息右移而选定的记录信息。在这种情况下，引入两个消息顺序的非确定性。另外，为了引入大量消息的顺序，按序移动信息，以检查消息表。

参看图92A和92B，如果是过程A或过程B的消息，翻译消息，然后发送给过程C。即使在下一个定时，如果是过程A或过程B的消息，则翻译消息，然后传送给过程C。当过程组控制装置203如上所述翻译记录信息时，就能实现良好非确定性的操作。可以实现如下。在过程组控制装置203进行处理的步骤K3(图88)中，可以将检验是否与消息源一致的目标从一个检验目标扩大到多个检验目标。当引入该良好的非确定性时，程序可以对外部非确定刺激作出正确的反应，从而实现过程的灵活性、再用性和扩展性。

当过程C连续接收过程A或过程B的消息时，上述实施例在处理两个消息时存在问题。通过删除一个在下面的启动候选中应被删除的消息即可容易地避免该问题。在本实施例中，为便于说明，只用过程名作为目的信息来指出将要删除的消息。由于只能在目的信息说明中被说明时才能指定被删除的消息，所以未经处理的消息不被删除。

因此，良好的非确定性与两个消息的输入顺序有关。然而，可以将良好的非确定性引入三个或更多个消息的输入顺序中。即使在这种情况下，过程组控制装置203检验图88中步骤K3里的目标，判断能否通过将目标从一个目标扩展至多个目标来解决其与消息的一致。因此，显然能够正确地操作程序。

以下将详细描述图82步骤A7中并行编译的阶段和并行程序综合装置18。综合记录信息存储装置301是一个用来在引入存储在HSP文件存储装置14中的良好非确定性之后存储执行记录信息的HSP文件存储装置14中的良好非确定性之后存储执行记录信息的存储装置。假设综合记录信息存储装置301将其中引入有良好非确定性的综合记录信息(如图95所示)存储起来，该信息为超串行程序在图80中的过程组交换消息(如图94所示)时由综合记录信息转换而来(图83)。

在如下的描述中，将参看图93、95和96描述按过程单位划分已引入良好的非确定性的综合记录信息。用划分标准选定装置23中的划分标准选定部件选定划分综合记录信息的标准。例如，该标准是一目的过程名或一目的计算机编号。在如下的描述中，标准是目的过程名。如果把方法名也添加至目的名，则能以{目的过程名、方法名}设置划分标准，以按目的方法的单位划分记录信息，从而获得分区记录。划分标准选定部件303保持该划分标准。

为根据用户指令划分综合记录信息，启动记录信息划分部件302。记录信息划分部件302根据图96所示的过程用划分标准选定部件303所选定的标准划分综合记录信息。

当启动记录信息划分部件302时，从划分标准选定部件303读取划分标准值(步骤L1)，从而获得划分标准。读取存储在综合记录信息存储部件301中的一个记录信息记录(步骤L2)，以确定读取的记录是否最终记录(步骤L3)。在这种情况下，如图95所示，由于综合记录信息的第一个记录是一个由过程A传至过程D的消息，因此，可以确定该记录不是最后一个记录。根据划分标准(目的过程名＝过程D)将该记录存储在相应的划分记录信息存储部件(在该情况，是划分记录信息存储部件D)中(步骤L4)。重复该操作，直至将记录信息的最后部分存入综合记录信息存储部件301中。结果，如图97A至97D所示，按目的过程单位划分的记录信息块被分别存储在划分记录信息存储部件A、B和C，以及划分记录信息存储部件D中。

图97A说明了过程A处理过程C的消息，然后再处理过程D的消息的情况。图97C中的过程C是引入了所谓良好非确定性的过程。图97C说明了首先处理来自过程A和B中一个过程的消息，然后处理过程A和B中一个过程的消息。换句话说，该过程指出良好的非确定性代表可以先输入过程A和B中一个过程的消息。该例示范了取消对两个消息的次序的限制。为了取消对多个信息的次序的限制并引入良好的非确定性，可以将所需的消息排成同一个队。

对目的过程划分记录信息，从而省略划分记录信息中的目的过程名。  

以下将描述根据按过程单位划分的记录信息操作每一过程的流程图。例如，如图98所示当接收到一个消息时，在开始启动处理之前，每一过程调用过程控制装置305，然后如图99所示进行处理。可以以这样的方式调用过程控制装置，即重写源程序以便将位于每个过程处理开始的调用过程作为并行程序综合装置18的一部分插入第一个并行程序中。也就是说，如图100所示，每一过程由过程固有的处理部分组成，另外还包含过程控制装置305、划分记录信息存储装置306和接收消息保持装置306。

过程控制装置305参照存储在包括在该过程的划分记录信息存储部件304中的记录信息处理一条消息。如果该消息不是要被处理的消息，则将消息存储在接收消息保持装置306中。

现将参看图97A至97D和99描述过程控制装置305的处理。

例如，在图94中的进程流中，过程A并未确定是先接收过程C的消息还是先接收D的消息，并且这里存在处理定时的非确定性。然而，在该情况下，在超顺序处理中执行的执行记录(对应于图83)规定先处理过程C的消息，然后再处理过程C的消息。即使引入了无害的非确定性，也必须保留关于消息处理顺序的规定。

第一次操作时，假设在接收到过程C的消息时首先启动过程A。当过程A接收到过程C的消息并被启动时，调用过程控制装置以获得用以启动过程A的消息的源信息(步骤M1)。在这种情况下，源信息Is＝{过程C}。接着，获得必须首先从划分记录信息存储部件输入的消息信息Ir1(步骤M2)，在该情况中，Ir1＝{过程C}。

为了检验当前接收到的消息顺序是否与存储在划分记录信息中的顺序一致，则要确定Ir1中是否包括Is(步骤M3)。在本情况下，过程C中的顺序相互一致，从而允许根据接收到的消息进行处理。为此，使为进行下一个启动检验需从划分记录信息存储部件中读取的记录加1(步骤M4)。在开始过程体处理之前，如果在接收消息保持装置中存在执行等待消息，则要确定能否启动被保持的消息。也就是，从存储在划分记录信息存储装置中的信息里抽取出将在下一步处理的消息信息Ir2(步骤M5)，并确定包括在其中的消息是否存在于过程等待消息保持装置中(步骤M6)。在本情况中，Ir2{过程D}。然而，由于接收消息保持装置中不存在任何消息，因此结束处理而进行基于过程C的消息的主处理。

当过程A接收到过程D的消息时，如上所述，以相同的方式进行处理，从而获得Is＝{过程D}和Ir1＝{过程D}。集合Is等于或包含在集合Ir1中。由于不存在Ir2，所以不需要检验过程等待消息保持装置中的消息，并结束处理。进行基于过程D消息的过程。

相反地，这里显示了当过程A首先接收到过程D的消息时的进程流。也就是，在先接收到过程D的消息而启动过程A时，调用过程控制装置以获得用来启动过程A的消息的源信息(步骤M1)。在本情况中，Is＝{过程D}。获取下一步将从划分记录信息存储装置中输入的消息信息Ir1(步骤M2)，在本情况中，Ir1＝{过程D}。

为了检验当前接收到的消息顺序是否与存储在划分记录信息中的一致，需要确定Is是否包括在Ir1(步骤M3)中，在本情况中，由于Is不包括在Ir1中，因此不能立即处理过程D的消息。将过程D的消息保持在接收消息保持装置306中(步骤M8)，并强行结束过程A的处理(步骤M9)。也就是，结束过程A的处理，除了进行基于过程D的消息的处理。

当把过程C的消息输入到过程A时，如上所述，以相同的方式进行处理，从而获得Is＝{过程C}和{Ir1＝过程C}。由于Is包括于Ir1中，从而允许立即进行基于接收消息的处理。对为进行下一个启动检验而从划分记录信息存储部件读取的记录增1(步骤M4)。在开始过程体处理之前，如果接收消息保持装置中存在执行等待消息，则判断能否启动保持消息。也就是，从存储在划分记录信息存储装置中的消息中抽取下一步将要处理的消息信息Ir2(步骤M5)，并判断包括其中的消息是否存在于过程等待消息保持装置中(步骤M6)。在本情况中，Ir2＝{过程D}。在前保持在过程等待消息保持装置中的消息是存在的。为了处理消息使其能够执行，将源信息或类似信息(本例中为过程D)不加修改地传送给目的地(本例中，为过程A)(步骤M7)。过程A完成过程控制装置的处理，从而根据过程C作为接收消息发送的消息来进行处理。

过程A接收从接收消息保持装置抽取并传送的消息，并如上所述以相同的方式进行处理，从而获得Is＝{过程D}和Ir1＝{过程D}。Is变成Ir1。由于Ir2不再存在，因此无需检验接收消息保持装置中的消息就可以完成处理。根据过程D的消息进行处理。

即使消息输入的顺序不同于执行记录中描述的顺序，也按执行记录中描述的顺序进行处理，从而保证非确定处理的再现性。

过程C的操作将作为引入良好非确定性时的处理操作来举例说明。当先接收到过程A的消息而启动过程C时，调用过程控制装置，以获得用以启动过程C的消息的源信息(步骤M1)。在本例中，源信息Is＝{过程A}。获得首先由划分记录信息存储部件输入的消息信息Ir1(步骤M2)。在本例中，Ir1＝{过程A，过程B}。首先接收过程A和B中一个过程的消息。

为了检验当前接收到的消息顺序是否与存储在划分记录信息中的一致，需要判断Is是否包括在Ir1中(步骤M3)。在本例中，由于集合Is等于或包括在集合Ir1中，所以允许立即根据接收到的消息进行处理。为此，对为进行下一个启动检验而从划分记录信息存储部件中读取的记录增1(步骤M4)。在开始过程体处理之前，如果接收消息保持装置中存在执行等待消息，则需要判断能否启动保持消息。也就是，从存储在划分记录信息存储装置中的消息中抽取下一步将要处理的消息信息Ir2(步骤M5)，并且判断包括在其中的消息是否存在于处理等待消息保持装置中(步骤M6)。在本例中，Ir2＝{过程A，过程B}。由于接收消息保持装置中不存在消息，所以结束处理，而根据过程A的消息进行主处理。

接着当把过程B的消息输入到过程C时，如上所述以相同的方式进行处理，以获得Is＝{过程B}和Ir1＝{过程A，过程B}。Is等于或包括在Ir1中。由于Ir2不存在，故无需检验接收消息保持装置中的消息而进行处理，并且根据过程B的消息进行处理。

关于引入良好的非确定性情况，可以用如上相同的方法处理按相反的次序输入消息的情况。也就是说，即使先将过程B的消息输入到过程C，然后再将过程A的消息输入到过程C，也还可如上所述进行相同的处理。

上述实施例具有处理两个消息的问题，即过程C连续接收过程A或过程B的消息。该问题可以容易地通过删除将从下个启动候选中删除的消息来避免。在本实施例中，为便于说明，只用作为目的信息的过程名提出将要删除的消息。由于要删除的消息可以在目的信息说明中唯一地说明，所以未处理的消息是不会被删除的。

如上所述，按目标单位划分执行记录信息。为此，当使无害的非确定性隐藏在并行程序中时，保留超串行程序所抽取的顺序。保持处理的再现性，并用较高的处理性能获得与超串行程序执行中相同的结果。

上例中按两个消息的输入顺序表现良好的非确定性。然而，可以将良好的非确定性赋于三个或更多消息的输入顺序。即使在本例中，可以通过使Ir1或Ir2具有多个因子进行上述处理。因此，理所当然，可以正确地进行处理。

上例举例说明了在每一过程或方法启动时调用过程控制装置以实现过程或方法的实施例。然而，每个计算机操作系统也可能为每个目的过程设有一个接收消息保持装置，并且每次消息处理参照相应的划分信息来启动相应的过程或在接收消息保持装置中保持该过程。

本例中，可以将一个过程作为可以连续启动的过程从执行等待状态转变为调度目标，而无需传送将在图99中的步骤M7中处理的消息。

根据本实施例，无需校正源程序就能重写作为排序规则的记录信息，从而很容易地解决处理定时的非确定性所引起的缺陷。能够简化固有处理定时非确定性的同时并行/并行/分布式程序的开发，从而提高生产率。

本实施例中，由于只有用户期望的良好非确定性才能方便地引入，所以并行程序能够保持灵活性，再用性和扩展性。

另外，按过程单位划分通过对并行程序排序而获得的所有过程的综合记录信息。根据分区记录信息控制每一过程以自然引入无害的非确定性，并且用较高的处理效率获得与根据综合记录信息执行超串行程序时相同的结果。

注意，如下是本发明计算机系统可能的配置，见图2：

(a)不存在共享存储器3的配置；

(b)通过用作总线的I/O接口2致密地连接处理器1-1至1-N的并行计算机；

(c)通过用作通信线的I/O接口稀疏地连接处理器的分布式网络计算机系统；及

(d)由单一处理器构成的配置，和这类配置的组合。

可以不脱离本发明的精神和范围进行各种变化和改进。

那些本领域中的熟练技术人员将容易地发现其他的好处和改进方法。因此，本发明在其较广泛的方面，不限于特别的详细说明、代表性的装置和这里所显示和描述的有图解的例子。由此，可以不脱离附加权项及其等价含义所限定的一般发明的概念的精神或范围进行各种改进。