源代码处理方法、系统及程序的制作方法
专利名称：源代码处理方法、系统及程序的制作方法
技术领域：
本发明涉及在多处理器系统中使程序的执行高速化的技术。
背景技术：
近年来，在科学技术计算和仿真等领域中使用具有多个处理器的所谓多处理器系统。在这样的系统中，应用程序生成多个进程来对各个处理器分配进程。这些处理器例如利用共享的存储器空间来一边相互通信一边进行处理。最近，作为尤其盛行研发的仿真领域，有机器人、汽车、飞行器等的机械电子学的设备仿真用软件。得益于电子零部件和软件技术的发展，在机器人、汽车和飞行器等领域中，大部分的控制利用象神经一样遍布的电线接线、无线LAN等以电子方式进行。这就意味着要对原来的机械装置内置大量的控制软件。因此，在研发产品时，需要在控制程序的研发及其测试方面投入大量的时间、巨额的费用和许多人员。为了进行这样的测试，以往所采用的技术有HILS (Hardware In the Loop Simulation:半实物仿真)。尤其是测试汽车整体的电子控制单元(ECU)的环境被称为整车性能HILS。在整车性能HILS中，在实验室内，将真车的ECU连接在仿真发动机、传动机构等的专用的硬件装置上，按照规定的脚本进行测试。来自ECU的输出被输入到监视用的计算机，进而显示在显示器，测试担当者一边注视显示器，一边确认是否有异常动作。但是，HILS必须使用专用的硬件装置，并在其与真车的E⑶之间进行物理配线，因此准备非常麻烦。而且，要替换其他ECU进行测试，需要重新进行物理连接，因此花费功夫。 而且，由于是使用真车的ECU进行的测试，测试需要实时。因此，在测试许多脚本时，花费庞大的时间。HILS的仿真用硬件装置通常价格非常高。因此，近年来，提出不使用高价的仿真用硬件装置，而是由软件构成的方法。该方法被称为SILS (Software In the Loop Simulation)，是将搭载于ECU上的微型计算机、输入输出电路、控制的脚本、发动机、传动系统等设备全部用软件仿真构成的技术。据此，即使不存在ECU的硬件，也能执行测试。作为这样的支援SILS构筑的系统，例如有可从CYBERNET SYSTEMS CO.，LTD获得的仿真建模系统即MATLAB(R)/Simulink㈨。当使用MATLAB(R)/Simulink(R)时，如图1所示，在画面上由图形界面配置功能模块A、B、…J，如箭头那样指定其处理流程，据此能够做成仿真程序。这样在MATLAB (R)/Simulink(R)上做成模块A、B、’"J等的方框图时，能够利用 Real-Time Workshop (R)的功能转换为等价功能的C语言的源代码。通过对该C语言的源代码进行编译，能够在其他的计算机系统中也能执行作为SILS的仿真。特别是其他的计算机系统使多处理器系统时，在可能的情况下对处理进行分割， 对各个处理器分配不同的进程进行并行处理，这样有利于提高处理速度。为此，以往公知有CP调度方法。在此，CP是指关键路径(Critical Path)。当利用CP调度方法时，图1所示的方框图变换为图2所示的任务图表。从图可知，图2的任务图表是纵四列，将各个列的处理并行地分配给不同的4个CPU，与用1个CPU进行处理时相比，实质上能够达到2倍的处理速度。但是，图2中B — D —冊一J这一路径是关键路径，不能将整体的处理时间缩短少于处理该关键路径的CPU的时间。在日本特开平6-83608号公报中公开如下内容利用关键路径解析部找出并行计算机中程序执行的成为瓶颈的部位。在日本特开平7-21240号公报中公开由如下装置构成的系统关键路径提取装置，关于逻辑电路的布局设计，为了在缩短关键路径的同时使横切切分线的网络数最小，而提取关键路径；做成切分线的切分线作成装置；合并对象选择装置，根据各模块的结合度和关键路径信息来决定各模块的合并对象；合并装置，根据由合并对象选择装置求出的各模块的合并对象进行模块的合并；为了使横切切分线的网络数最小而进行对偶交换的对偶 (pair-wise)装置。在日本特开平8-180100号公报中公开了如下内容针对随着机械分配产生的作业调度问题，通过生成高效率的邻域，与近似解法组合，从而来高速求出最优解。在日本特开平6-83608号公报及日本特开平8-180100号公报中只不过公开了任务调度的概要。在日本特开平7-21240号公报中对在逻辑电路的布局设计中缩短关键路径的技术进行了说明，但这是物理布局上的关键路径，不能适用于软件的逻辑上的关键路径的处理。专利文献1 日本特开平6-83608号公报专利文献2 日本特开平7-21240号公报专利文献3 日本特开平8-180100号公报
发明内容
因此，本发明的目的在于提供一种在多处理器系统中通过并行化来使程序的执行高速化的技术。通过将想要高速化的程序的关键路径适当切分、分为其他进程，并分配给各个处理器，从而来达到上述目的。据此，能够输出用于仿真的投机执行的最优代码。S卩，本发明的处理程序读取由多个处理块构成的、想要高速化的程序源代码，通过对关键路径的可能的切分全部进行测试来找出作为结果的切分后处理块的流程的处理时间最短的切分。为了可实现这样的处理时间的估计，预先将处理程序编译，进行测量各处理块的执行时间及其他值的阶段。此时测量的值也包括如下这样的测量数据在跨越进行不同处理的处理器时的信息传递成本、用于投机执行所必须的处理、投机失败时的重算的成本以及对各模块的输入预测命中何种程度(即投机成功概率)。对切分结果的路径递归地应用关键路径的可切分处理。于是，虽然进一步切分，但加上处理器之间的通信时间等，有时整体的处理时间反而变长，在这种情况下停止切分。据此，得到多个处理块的组。尤其是在本说明书的说明中，将各处理块的组称为模块组(block chunk)ο
若这样分割生成的模块组的个数与多处理器系统的处理器的个数相同或少于处理器的个数，则各个模块组直接被编译而按执行环境被分别分配给各个处理器。但是，若模块组的个数多于处理器的个数，则本发明的处理程序，尝试将模块组结合，以使模块组的个数等于处理器的个数。此时，优选是选择结果结合成的模块组中的关键路径的处理时间的最大值为最小这样的结合。这样结果的模块组被编译而在实际环境下分别分配给各个处理器。这样一来，对所有模块组的每一个模块组分配一个处理器，进行最优的并行处理。如上所述，根据本发明，在多处理器环境中，可实现对关键路径的长度和处理器分配这两方面均改善了的高速的程序执行。能够输出用于仿真的投机执行的最优代码。
图1是表示仿真建模工具的方框图的例子的图。图2是表示CP调度方法的例子的图。图3是用于实施本发明的硬件的框图。图4是本发明一实施例的功能框图。图5是表示本发明一实施例的处理流程的图。图6是切分关键路径的处理的流程图。图7是切分关键路径的处理的流程图。图8是切分关键路径的处理的例子的示意图。图9是表示包括投机时的期待执行时间的图。图10是模块组形成处理的例子的示意图。图11是CPU分配用代码生成处理的流程图。图12是CPU分配用代码生成处理的流程图。图13是模块组结合处理的例子的示意图。图14是模块组结合处理的例子的示意图。图15是用于说明模块之间的依存关系的图。附图标记的说明404源代码406、422 编译器
412 “关键路径的切分”模组416 "CPU分配用代码生成”模组418 CPU 代码420依存关系信息
具体实施例方式以下，参照附图来说明本发明一实施例的构成及处理。在以下的说明中，只要没有特别否定，在附图中对同样构件标注相同附图标记用来参考。在此说明的构成和处理是作为一实施例来说明，应理解到不是想要将本发明的保护范围限定解释为该实施例。接着，参照图3，说明用于实施本发明所使用的计算机的硬件。在图5中，主机总线302上连接有多个CPUl 304a、CPU2 304b、CPU3304c、…CPUn 304η。主机总线502上还连接有用于进行CPUl 304a、CPU2 304b、CPU3 304c,…CPUn 30 的运算处理的主存储器 306。另一方面，I/O总线308上连接有键盘310、鼠标312、显示器314及硬盘驱动器 316。I/O总线308经由I/O桥318与主机总线302连接。键盘310及鼠标312是为了操作者敲入指令、单击菜单等进行操作而使用的。显示器314是为了根据需要显示用于用GUI 操作后述的本发明的程序的菜单而使用的。作为为了该目的使用的优选的计算机系统的硬件，有IBM(R)System X。此时， CPUl 304a、CPU2 304b、CPU3 304c、... CPUn304n 例如是因特尔(R) Xeon (R)，操作系统是 Windows (商标)Server 2003。操作系统存储于硬盘驱动器316中，在计算机系统启动时， 从硬盘驱动器316读取到主存储器306。另外，为了实施本发明可使用的计算机系统的硬件，不限于IBM(R)System X，至少能运行本发明的仿真程序，可以使用任意计算机系统。操作系统也不限于Windows(R),可以使用Linux(R)、Mac OS(R)等任意操作系统。而且，为了使仿真程序高速工作，也可以使用 POWER (商标)6为基础，操作系统为AIX (商标)的IBM(R)System P等的计算机系统。在硬盘驱动器316中还存储有MATLAB (R)/Simulink (R)、C编译器或C++编译器、 用于切分本发明的关键路径的模组、CPU分配用代码生成模组、用于测量处理块的期待执行时间的模组等，响应操作者的键盘或鼠标操作而载入到主存储器306来执行。另外，可使用的仿真建模工具不限于MATLAB (R) /Simulink(R)，可以使用开放源的 Scilab/Scicos等任意的仿真建模工具。或者，根据情况，可以不使用仿真建模工具，而直接用C、C++写出仿真系统的源代码，在该情况下也可应用本发明。图4是本发明的实施例的功能框图。各个框基本上与存储在硬盘驱动器316中的模组对应。在图4 中，仿真建模工具 402 可以是 MATLAB (R)/Simulink(R)、kilab/Scicos 等现有的任意工具。仿真建模工具402基板上具有如下功能操作者在显示器314上以⑶I 方式配置功能模块，记述数学式等必要的属性，根据需要可以在功能模块之间施加关联地记述方框图。仿真建模工具402还具有如下功能输出用于记述与所记述的方框图等效功能的C的源代码。除了 C之外，也可以使用C++、Fortran等。另外，仿真建模工具也可以导入到其他个人计算机，将在此生成的源代码经由网络等下载到硬盘驱动器316。如此输出的源代码404被保存于硬盘驱动器316。源代码404在编译器406被编译，作为编译结果的可执行的程序被送至测试模组408。测试模组408具有进行执行测试的功能和进行投机测试的功能。在执行测试中， 根据规定的脚本，测量图1所示的各模块的平均处理时间、处理器之间通信时间及投机成功概率。为了测量平均时间，优选采用同一脚本执行多次。其测量结果410为了在后面使用而保存于硬盘驱动器316。在投机测试中根据其他的规定脚本投机执行作为编译结果的可执行程序。通过重复其脚本，测量如下时间投机准备的处理时间，即，在投机失败进行重算时，用于进行保存预测的输入值这样处理的时间；投机成功与否确认的处理时间，即，进行在实际的数据到来时确认其是否与预测的数据一致的处理的时间；重算处理时间，即，得知投机失败即预测的输入与实际值不同时，进行停止基于错误输入进行的处理、删除数据等后续处理所需要的时间。这样的值也作为测量结果410，为了在后面使用而保存于硬盘驱动器316。关于投机成功概率，其实不实际进行投机执行也能算出该投机成功概率。在投机执行中，在本来要到来的输入到来之前执行处理，因此预测该输入执行处理。因此，投机成功的概率等于针对输入的预测命中的概率。若规定了预测其输入的算法，则实际不进行投机执行(即不进行基于预测的输入数据的模块处理)，仅从实际的输入数据也能算出预测算法的预测成功概率。即，仅是在“执行测试”中记录对各模块的输入，根据该输入数据序列算出输入预测算法的预测成功率，从而能够求出投机成功概率。另一方面，在进行了投机执行时，或者投机执行失败了时会花费怎样程度的时间，不实际进行投机执行时不知道的。 因此，为了得到这些信息而进行投机测试。但是，若规定投机执行的安装，则可预想到投机准备、投机的成功与否确认、投机失败时的重算所需的处理时间是与输入数据量成正比的处理时间。因此，在“投机测试”中，可以不对所有模块进行投机执行，通过对尝试对几个输入数据量不同的模块进行投机执行，来得到输入数据量与投机关联处理时间的关系，可以基于此算出所有情况的成本。“关键路径的切分”模组412具有如下功能原则上按模块单位对源代码404进行处理，找出关键路径，进行切分，找出成为最优执行时间的切分。此时，使用测量结果410的信息。模组412还递归地应用关键路径的切分功能，得到如图10所示的分成小块的模块组。 这样生成的模块组的信息414为了在后面使用而保存于硬盘驱动器316。关于关键路径的切分功能，后面参照流程图详细说明。"CPU分配用代码生成”模组416使用模块组的信息414和测量结果410生成分配给CPUl CPUn的代码418a、418b、…418m。如果模块组的个数少于或等于CPUl CPUn 的个数，则各模块组的代码直接分配给CPUl CPUn。但是，如果模块组的个数多于CPUl CPUn的个数，则如图14示意所示，将模块组彼此结合，以使得模块组的个数等于CPUl CPUn的个数。但是，此时的结合优选是以使作为结果的关键路径的期待执行时间为最少的方式最优选择。关于CPU分配用代码生成功能，也是后面参照流程图详细说明。结果所生成的是分配给CPUl CPUn的代码418a、418b、…418m和依存关系信息420。依存关系信息420是必须的，其理由如下所示。即，如图10所示，原本的处理流程被关键路径的切分功能分断，则有时原本的模块之间的依存关系被切断。为了对其补偿，模组416也提供例如分配给CPUl CPUn的代码418a、418b、…418m中的某个代码返回到在其他某一代码所使用的变量、等这样的依存关系信息420。实际上，依存关系信息420是由 “关键路径的切分”模组412在切分时作出的，因此“CPU分配用代码生成”模组416利用该 fn息ο这样生成的代码418a、4imK…418m在编译器422被分别编译成可执行的程序， 在执行环境424以在对应的CPUl CPUn上并行执行的方式被分别分配。依存关系信息 420以可被CPUl CPUn共用参照的方式配置在主存储器306的共用存储器区域，CPUl CPUn执行代码418a、418b、…418m时，根据需要，为了参照在其他CPU上执行的代码的信息而使用上述依存关系信息。图5表示该实施例的整体处理流程。应理解到，这是表示作业顺序的流程，未必是与计算机的处理流程一一对应的。在图5中，在步骤502中，开发者或作业者使用MATLAB(R)/Simulink(R)等仿真建模工具402，在图3所示的系统上或其他计算机上做成特定仿真对象的方框图。在步骤504，开发者或作业者使用仿真建模工具402的功能生成与作成的方框图对应的源代码404，并保存于硬盘驱动器316。在步骤506，开发者或作业者使用编译器406编译源代码404。编译出的可执行的程序未图示，暂时保存于硬盘驱动器316。在步骤508，开发者或作业者使用编译出的执行程序在测试模组408进行执行测试。结果得到的模块的平均处理时间、处理器之间通信时间以及投机成功概率的执行时间的测量数据在步骤510作为测量结果410而保存于硬盘驱动器316。在步骤512，开发者或作业者使用编译出的执行程序在测试模组408进行投机测试。结果得到的投机准备的处理时间、投机成功与否确认的处理时间以及重算处理时间的测量数据在步骤514作为测量结果410而保存于硬盘驱动器316。在步骤516，响应开发者或作业者的操作而开始计算机的处理。即，基本上从步骤 516到步骤524自动进行计算机的处理。在步骤516，由“关键路径的切分”模组412处理源代码404。具体的处理将后述，通过算法找出源代码404记述的整体处理流程中的关键路径，按照处理时间将其最优切分， 在切分后的处理流程中递归地进行切分关键路径这样的处理。此时，使用测量结果410。结果，得到图10所示的多个模块组，因此在步骤518，与其相关的信息作为模块组 414被保存于硬盘驱动器316。此时保存的数据构造，可以使用XML等计算机可读的、可表现出源代码和内容和连结关系(链接)这两方面内容的任意的数据构造。在步骤520，使用模块组414的信息，“CPU分配用代码生成”模组416生成用于分别分配给CPUl CPUn的代码。即，如果模块组的个数少于CPUl CPUn的个数，则直接将代码逐个地分配给CPUl CPUn。而如果模块组的个数多于CPUl CPUn的个数，则将模块组以执行时间上成为最短的方式结合成与CPUl CPUn的个数相等。此时，使用测量结果 410。在步骤522，由模组416生成的代码被编译器422编译，在步骤5 中，分别将代码分配给对应的处理器CPUl CPUn，分别执行。参照图6和图7的流程图，说明与图5的步骤516对应的、关键路径的切分的处理。在步骤602，进行找出关键路径的最优切分这样的处理。在此，为了说明最优切分是指什么，参照图8。在图8表示由模块A I构成的处理的流程。在此，利用找出关键路径的算法， 特定了 B-C-D-E-F为关键路径，则在步骤602，“关键路径的切分”模组412依次尝试沿 B-C-D-E-F的可进行的切分cl、c2、c3、c4。例如，尝试切分c3是指在c3处将关键路径切分，如图8所示，逻辑上将切分下来的流程移至旁边。于是，成为2个流程并置。在此评价切分c3。评价切分c3是指若假定投机成功概率为100%，则比较并置的2个流程的期待执行时间，评价时间较长一方的值T。。但是，通常投机成功概率低于100%，因此如图9所说
10明的那样，考虑到投机成功概率来评价T。。将使这样的T。成为最短的切分成为最优切分。用于找出最优切分的更详细处理(子程序)在后面参照图7的流程图进行说明。另外，在图5的步骤508所示的执行测试中预测各模块的期待执行时间，作为测量结果410保存于硬盘驱动器316。应注意到在计算所要的流程的期待执行时间时使用这样的测量结果410。实际上，为了估计执行时间，仅是单纯地沿流程执行模块的期待执行时间是不够的。参照图9说明该问题。在此，定义如下的变量。在此，成本可以视作时间。MSCxy 模块X与模块Y被切分时的、从模块X到模块Y的消息发送成本。MRCxy 模块X与模块Y被切分时的、从模块X到模块Y的信息接收成本。SCxy 从模块X到模块Y的投机成本。SCCxy 从模块X到模块Y的投机确认成本。RBCxy 从模块X到模块Y的投机失败了时的重算成本。这些模块之间的成本也是在图5的步骤508所示的执行测试及步骤512所示的投机测试中预测，作为测量结果410而保存于硬盘驱动器316。于是，在关键路径B-C-D-E-F的C和D之间插入切分c，需要如图9所示那样根据投机成功时和投机失败时的期待值估计结果的期待执行时间。在投机成功时，切分的结果的2个流程的较长一方的执行时间成为结果的期待时间，为Tcs = ID I +1E I +1FI +SCcd+MRCif+MRCcd+SCCcd在此，例如ID I表示模块D的执行时间。另外，在投机失败了时，B-C和D-E-F是串联执行的，因此期待时间是Tcf = IB I +1 CI +1D I +1E I +1FI +MRCac+MSCcd+MRCcd+RBCcd+MRCif但是，这样的投机的成功概率ρ。在图5的步骤508所示的执行测试中预测，作为测量结果410保存于硬盘驱动器316。使用该结果，计算结果的期待执行时间为T。= PcTcs+(I-Pc) Tcf。返回图6的流程图，利用步骤602的处理结果，在步骤604“关键路径的切分”模组 412判断是否存在最优切分。存在最优切分是指切分的结果缩短了整体的期待处理时间。 在任何情况下切分未必都缩短处理时间。即，鉴于上述的发送成本、接收成本及投机成本， 有时即使切分也不能缩短处理时间。在这样的情况下，在步骤604判断为不存在最优切分， 在步骤606中，将当前评价的模块组的信息优选保存于硬盘驱动器316。另一方面，在步骤604判断为存在最优切分时，“关键路径的切分”模组412在步骤 608移动切分后的模块。这是图8所示的处理。在步骤610，对于切分后而成的路径的整个集合，递归地调出图6的流程图的处理。用图8的框图进行说明，首先对于模块A、B、C、D、E、F、G、H、I应用图6的流程图的处理，结果分成模块A、B、C、D、E、F和模块G、H、I，因此，递归地调出图6的流程图的处理。接着，参照图7的流程图更详细说明图6的步骤602的处理。在步骤702，进行找出关键路径的处理。对于处理流程找出关键路径的处理本身是公所周知的，例如可使用http//www. koRures. com/hitoshi/webtext/pt~pert/index, html 中记载的PERT的方法等。在步骤704，设置为tmin =沿关键路径的期待时间，Cmin = null, C =关键路径的可切分的集合。在步骤706，判断C是否为空，若不为空，则进入步骤708，从C取出切分C。在步骤710，计算切分c的期待执行时间，将其代入t。。在此的执行时间的计算包括与图9相关的说明的、投机执行的情况。在步骤712，判断是否是 tc < tmin，若 tc < tmin，则在步骤 714，设 tmin = tc, Cfflin =
Co这样一来，对于C的所有切分，执行步骤708、710、712及714，结果的Cmin返回图6 的步骤602。此时，存在C中某种切分使处理时间不短于tmin =沿关键路径的期待时间的情况。这样的情况下，在步骤712的判断不是肯定，因此不执行步骤714，因此Cmin = null保持不变。于是，图6的步骤604的判断为否定。图10示意地表示这样的处理的结果。图10的左侧所示的模块的处理流程被图6 的流程图所示的处理的递归过程在多个部位切分，如图10的右侧所示，得到细分化的多个模块组。接着，参照图11和图12的流程图说明与图5的步骤520对应的CPU分配代码生成的处理。这是由图4的“CPU分配用代码生成”模组416执行的。在步骤1102，设置p =处理器(CPU)的个数，b =模块组的个数。在步骤1104，判断是否是ρ <b。若其结果是否定的，即ρ彡b，则具有可以直接将模块组分别分配的个数的处理器，因此，在步骤1106中，适当地将各个模块组分配给各个处理器，结束处理。在步骤1104，若判断是？ < b，则表示要直接将模块组分别分配，处理器的个数不够，因此在步骤1108将2个模块组结合，进行减少1个模块组的个数的处理。将2个模块组结合，有时存在在结合的模块组处关键路径延长而期待处理时间变长的情况。因此，在步骤1108中，找出将2个模块组结合的结果的期待处理时间成为最短这样的最优的组合方式。图14示意地表示这样的处理。在步骤1110中，b减去1，返回步骤1104的判断。这样一来，直到ρ = b，反复进行步骤1108和步骤1110。当ρ = b时，步骤1104为否定。于是表示现在具有直接将模块组分别分配的个数的处理器，在步骤1106中，将在该时刻保存的结果的各个模块组分配于各个处理器，结束处理。另外，有时在想要将几个CPU保留用于其它处理时，进一步减少模块组的个数，直到 b < ρ。图12是更详细地表示图11的步骤1108的处理的流程图。在图12中，在步骤1202 中，设置S1 =当前的模块组的集合，tmin = -，Ufflin = c ，I3l = Id2 = null。在此，①是指在该状况下比实际上假定的个数大很多的适当的常数。在步骤1204中，判断S1是否为空，如果为空，则处理完成，返回图11的流程图的步骤1108。若S1不为空，则在步骤1206，从S1取出1个模块组Sl。在步骤1208中，设置& =当前的模块组的集合。在步骤1210，判断&是否为空，如果为空，则返回步骤1204。若&不为空，则在步骤1212，从&取出1个模块组&。在步骤1214中，使用图4所示的各模块的测量结果410来计算将S2结合到S1之下时的执行时间，并将其代入Tsls2。在此，^ = S1的情况省略。哪个模块组都是原文的模块的流程的一部分，因此有时在任意2个模块组之间，能够决定哪一方原本就位于上游。因此，优选是在步骤1214，若能够判定原文的上下游关系，则以维持其上下游关系的方式将2 个模块组结合。在步骤1216中，判断Tsls2是否等于Tmin。如果相等，则在步骤1218，计算将S2结合在S1下方时的期待成本，并代入usls2。在此，成本是指在对各模块的执行时间、跨过不同处理器的模块之间的信息收发成本、投机成本、投机确认成本、投机失败时的重写成本每次组合可投机成功与否时按投机成功概率赋予权重而算出的、所有CPU消耗时间的期待值。接着，在步骤1220中，判断是否是Usls2 < Umin，若是，则在步骤1222，在Tmin = Tsls2, bi = Si、b2 = S2^ufflin中代入将&结合于S1之下时的期待成本。从步骤1222返回步骤1210 的判断。另一方面，在步骤1216中，若Tsls2不等于Tmin，则进入步骤1224，因此，判断是否是八132<!1_。如果是则执行步骤1222，然后返回步骤1210的判断。若不是则直接从步骤 12M返回步骤1210的判读。图13表示模块组的结合例。在该例子中，如图所示，有模块组bcl、bc2、bc3、bc4 这4个模块组。于是，若不管原文的流程的上下游，则可有12种结合，但若将所有结合罗列说明太冗长，因此代表性地说明左下所示的、将bc3结合于bc2之下的情况和右下所示的将 bc4结合于bcl之下的情况。首先，将bc3结合于bc2之下时，期待执行时间tb。2b。3和期待成本ub。2b。3分别如下这样计算。tbc2bc3 = IB I +1 CI +1D I +1E I +1FI +MRCac+MRCifUbc2bc3 = AI +1B I +1 CI +1D I +1E | +1F | +1GI +1HI + 111 +MRCac+MRCif+MSCac+MSCif另一方面，将bc4结合于bcl之下时，期待执行时间tb。lb。4和期待成本ub。lb。4分别如下这样计算。tbclbc4 = P1P2 (ID I +1E I +1F | +SCcd+SCif+MRcd+SCCcd+MRCif+SCCif) +P1 (l_p2) (| A | + GI +1HI +111 +1 FI +MSAac+MSCif+MRCif+SCCif+RBCif) + (I-P1) (| B | +1 C | +1D | +1 E | +1 F | +MRC
ac+MSCcd+MRCcd+SCCcd+RBCcd+MRCif)Ubclbc4 = AI +1B I +1 CI +1D | +1E | +1F | +1G | +1H | +111 +P1P2 (SCcd+SCif+MRcd+SCCcd+M RCif+SCCif) +P1 (l-p2) (MSAac+MSCif+MRCif+SCCif+RBCif) + (I-P1) (MRCac+MSCcd+MRCcd+S CCcd+RBCcd+MRCif)在此，P1和p2是图示的路径中的投机成功概率。上述各个值都根据测量结果410而取得。图14是表示如下处理的图，具有模块组bcl、bc2、bc3、bc4、bc5、bc6这6个，在 CPU只有5个时，为了减少1个模块组，"CPU分配代码生成”模组416尝试将2个模块组结合时的处理。图14的左下表示bc6结合于bc4之下，其结果bc3给予整体最长的执行时间tsls2。图14的右下表示bc5结合于bcl之下，其结果bcl给予整体最长的执行时间tsls2。
"CPU分配代码生成”模组416对可能的所有模块组的组合计算最长的执行时间
tsls2，其结果是选出表示最短的tsls2的模块组的结合。如此生成的每个CPU的代码分别由编译器422编译而转换为可执行的代码时，暂时保存于硬盘驱动器316。但是，若在原本相连的模块的流程中插入切分，则有时切分的结果是各个模块之间的依存关系被切断，因此需要补偿这样的信息。图15是用于说明这样的依存关系的示意图。在图15中，设由模块A及模块C构成的代码成为codel、由模块B及模块D构成的代码成为code2、由模块F、模块H及模块J构成的代码成为Code3、由模块E、模块G及模块 I构成的代码成为code4。codel、code2、code3及code4的中段如图15所示。于是，可以看出，分别使用 codel、code2及code4的最初的还原值作为code3的参数。该情况例如下述所记述。1st output of codel- > 1st argument of code31st output of code2- > 2nd argument of code31st output of code3- > 3rd argument of code3"CPU分配代码生成”模组416在生成各个CPU分配用代码时，一并生成这样的信
肩、ο依存关系信息包括各个CPU分配用代码，可对编译器422通知，但优选是直接配置的执行环境424的共享存储器上等，CPUl CPUn执行所分配的代码时，能够参照依存关系
fn息ο这样一来，通过操作者的操作，开始仿真动作时，被编译的各CPU用的可执行程序依次被执行环境似4读取到主存储器306，执行环境似4对各个处理器分配关于各个可执行程序生成的进程。这样一来，由各个处理器并行执行被分割为多个可执行程序的仿真程序。在以上的实施例中，说明了基于使用仿真建模工具生成的程序源代码，分配到多个CPU进行并行处理，但本发明不限于这样的仿真程序源代码，如果能够特定处理块单位、 或记述其流程，就能应用任意的源代码。
权利要求
1.一种源代码处理方法，其通过计算机处理来生成用于在多处理器系统中能够并行执行的源代码，其特征在于，包括输入程序源代码的步骤；通过上述计算机处理来找出上述程序源代码的处理的关键路径的步骤；以及对上述关键路径进行切分来与上述多处理器系统的各个处理器对应而分割上述源代码的步骤。
2.根据权利要求1所述的源代码处理方法，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的步骤，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
3 根据权利要求2所述的源代码处理方法，其特征在于，包括还测量跨不同处理的处理器时的信息传递成本、用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录的步骤。
4.根据权利要求2所述的源代码处理方法，其特征在于，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
5.根据权利要求1所述的源代码处理方法，其特征在于，还包括输出包含上述所分割的源代码之间的变量和参数的依存关系信息在内的信息的步骤。
6.根据权利要求2所述的源代码处理方法，其特征在于，还包括以下步骤比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
7.根据权利要求6所述的源代码处理方法，其特征在于，在上述结合所分割的源代码的步骤中，使用上述所记录的处理时间来按以下方式进行结合使所结合的源代码中的期待处理时间最长的期待处理时间为最短。
8.根据权利要求1所述的源代码处理方法，其特征在于，上述源代码是利用仿真建模工具的功能来生成的，上述源代码的处理块单位与仿真建模工具上的方框图的模块对应。
9.一种源代码处理系统，其通过计算机处理来生成用于在多处理器系统中能够并行执行的多个源代码，其特征在于，包括记录单元，其保存程序源代码；找出单元，其通过上述计算机处理来读取上述程序源代码，从而找出该源代码的处理的关键路径；以及分割单元，其切分上述关键路径来与上述多处理器系统的各个处理器对应而分割上述源代码。
10.根据权利要求9所述的源代码处理系统，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的单元，上述分割源代码的单元使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
11.根据权利要求10所述的源代码处理系统，其特征在于，上述测量处理时间来进行记录的单元还测量跨不同处理的处理器时的信息传递成本、 用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录。
12.根据权利要求10所述的源代码处理系统，其特征在于，上述分割源代码的系统使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
13.根据权利要求9所述的源代码处理系统，其特征在于，还包括输出包含上述所分割的源代码之间的变量和参数的依存关系信息在内的信息的单元。
14.根据权利要求10所述的源代码处理系统，其特征在于，还包括结合单元，该结合单元比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，并响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
15.根据权利要求14所述的源代码处理系统，其特征在于，上述结合所分割的源代码的结合单元使用上述所记录的处理时间来按以下方式进行结合使所结合的源代码中的期待处理时间最长的期待处理时间为最短。
16.根据权利要求9所述的源代码处理系统，其特征在于，上述源代码是利用仿真建模工具的功能来生成的，上述源代码的处理块单位与仿真建模工具上的方框图的模块对应。
17.一种计算机系统，其通过多处理器系统来执行能够并行执行的多个程序，其特征在于，包括记录单元，其保存程序源代码；找出单元，其通过上述计算机处理来读取上述程序源代码，从而找出该源代码的处理的关键路径；分割单元，其切分上述关键路径来与上述多处理器系统的各个处理器对应而分割上述源代码，编译单元，其对上述所分割的源代码进行编译；分配单元，其将上述所编译的能够执行的程序分配给上述多处理器系统的各个处理器。
18.根据权利要求17所述的计算机系统，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的单元，上述分割源代码的单元使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
19.根据权利要求18所述的计算机系统，其特征在于，上述测量处理时间来进行记录的单元还测量跨不同处理的处理器时的信息传递成本、 用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录。
20.根据权利要求18所述的计算机系统，其特征在于，上述分割源代码的系统使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
21.根据权利要求17所述的计算机系统，其特征在于， 还包括输出包含上述所分割的源代码之间的变量和参数的依存关系信息在内的信息的单元；和使上述多处理器系统的各个处理器能够参照上述依存关系信息来进行载入的单元。
22.根据权利要求17所述的计算机系统，还包括结合单元，该结合单元比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，并响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
23.一种程序，其通过计算机处理来生成用于在多处理器系统中能够并行执行的源代码，其特征在于，使上述计算机执行输入程序源代码的步骤；通过上述计算机处理来找出上述程序源代码的处理的关键路径的步骤；以及切分上述关键路径来与上述多处理器系统的各个处理器对应而分割上述源代码的步骤。
24.根据权利要求1所述的程序，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的步骤，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
25.根据权利要求M所述的程序，其特征在于，包括还测量跨不同处理的处理器时的信息传递成本、用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录的步骤。
26.根据权利要求M所述的程序，其特征在于，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
27.根据权利要求M所述的程序，其特征在于，还包括以下步骤比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
全文摘要
本发明提供一种源代码处理方法、系统及程序。本发明为了提供在多处理器系统中通过并行化来使程序的执行高速化的技术而对想要高速化的程序的关键路径适当进行切分，分成其他进程来分配给各个处理器。本发明的处理程序读取由多个处理块构成的想要高速化的程序源代码，并对关键路径的所有可能的切分进行测试，找出使作为结果的所切分处理块的流程的处理时间最短的切分。据此获得多个处理块组。如此分割生成的各个模块组被编译而按执行环境被分配给各个处理器。
文档编号G06F9/45GK102197376SQ20098014251
公开日2011年9月21日 申请日期2009年8月24日 优先权日2008年10月24日
发明者吉泽武朗, 小松秀昭 申请人:国际商业机器公司
技术领域：
本发明涉及在多处理器系统中使程序的执行高速化的技术。
背景技术：
近年来，在科学技术计算和仿真等领域中使用具有多个处理器的所谓多处理器系统。在这样的系统中，应用程序生成多个进程来对各个处理器分配进程。这些处理器例如利用共享的存储器空间来一边相互通信一边进行处理。最近，作为尤其盛行研发的仿真领域，有机器人、汽车、飞行器等的机械电子学的设备仿真用软件。得益于电子零部件和软件技术的发展，在机器人、汽车和飞行器等领域中，大部分的控制利用象神经一样遍布的电线接线、无线LAN等以电子方式进行。这就意味着要对原来的机械装置内置大量的控制软件。因此，在研发产品时，需要在控制程序的研发及其测试方面投入大量的时间、巨额的费用和许多人员。为了进行这样的测试，以往所采用的技术有HILS (Hardware In the Loop Simulation:半实物仿真)。尤其是测试汽车整体的电子控制单元(ECU)的环境被称为整车性能HILS。在整车性能HILS中，在实验室内，将真车的ECU连接在仿真发动机、传动机构等的专用的硬件装置上，按照规定的脚本进行测试。来自ECU的输出被输入到监视用的计算机，进而显示在显示器，测试担当者一边注视显示器，一边确认是否有异常动作。但是，HILS必须使用专用的硬件装置，并在其与真车的E⑶之间进行物理配线，因此准备非常麻烦。而且，要替换其他ECU进行测试，需要重新进行物理连接，因此花费功夫。 而且，由于是使用真车的ECU进行的测试，测试需要实时。因此，在测试许多脚本时，花费庞大的时间。HILS的仿真用硬件装置通常价格非常高。因此，近年来，提出不使用高价的仿真用硬件装置，而是由软件构成的方法。该方法被称为SILS (Software In the Loop Simulation)，是将搭载于ECU上的微型计算机、输入输出电路、控制的脚本、发动机、传动系统等设备全部用软件仿真构成的技术。据此，即使不存在ECU的硬件，也能执行测试。作为这样的支援SILS构筑的系统，例如有可从CYBERNET SYSTEMS CO.，LTD获得的仿真建模系统即MATLAB(R)/Simulink㈨。当使用MATLAB(R)/Simulink(R)时，如图1所示，在画面上由图形界面配置功能模块A、B、…J，如箭头那样指定其处理流程，据此能够做成仿真程序。这样在MATLAB (R)/Simulink(R)上做成模块A、B、’"J等的方框图时，能够利用 Real-Time Workshop (R)的功能转换为等价功能的C语言的源代码。通过对该C语言的源代码进行编译，能够在其他的计算机系统中也能执行作为SILS的仿真。特别是其他的计算机系统使多处理器系统时，在可能的情况下对处理进行分割， 对各个处理器分配不同的进程进行并行处理，这样有利于提高处理速度。为此，以往公知有CP调度方法。在此，CP是指关键路径(Critical Path)。当利用CP调度方法时，图1所示的方框图变换为图2所示的任务图表。从图可知，图2的任务图表是纵四列，将各个列的处理并行地分配给不同的4个CPU，与用1个CPU进行处理时相比，实质上能够达到2倍的处理速度。但是，图2中B — D —冊一J这一路径是关键路径，不能将整体的处理时间缩短少于处理该关键路径的CPU的时间。在日本特开平6-83608号公报中公开如下内容利用关键路径解析部找出并行计算机中程序执行的成为瓶颈的部位。在日本特开平7-21240号公报中公开由如下装置构成的系统关键路径提取装置，关于逻辑电路的布局设计，为了在缩短关键路径的同时使横切切分线的网络数最小，而提取关键路径；做成切分线的切分线作成装置；合并对象选择装置，根据各模块的结合度和关键路径信息来决定各模块的合并对象；合并装置，根据由合并对象选择装置求出的各模块的合并对象进行模块的合并；为了使横切切分线的网络数最小而进行对偶交换的对偶 (pair-wise)装置。在日本特开平8-180100号公报中公开了如下内容针对随着机械分配产生的作业调度问题，通过生成高效率的邻域，与近似解法组合，从而来高速求出最优解。在日本特开平6-83608号公报及日本特开平8-180100号公报中只不过公开了任务调度的概要。在日本特开平7-21240号公报中对在逻辑电路的布局设计中缩短关键路径的技术进行了说明，但这是物理布局上的关键路径，不能适用于软件的逻辑上的关键路径的处理。专利文献1 日本特开平6-83608号公报专利文献2 日本特开平7-21240号公报专利文献3 日本特开平8-180100号公报
发明内容
因此，本发明的目的在于提供一种在多处理器系统中通过并行化来使程序的执行高速化的技术。通过将想要高速化的程序的关键路径适当切分、分为其他进程，并分配给各个处理器，从而来达到上述目的。据此，能够输出用于仿真的投机执行的最优代码。S卩，本发明的处理程序读取由多个处理块构成的、想要高速化的程序源代码，通过对关键路径的可能的切分全部进行测试来找出作为结果的切分后处理块的流程的处理时间最短的切分。为了可实现这样的处理时间的估计，预先将处理程序编译，进行测量各处理块的执行时间及其他值的阶段。此时测量的值也包括如下这样的测量数据在跨越进行不同处理的处理器时的信息传递成本、用于投机执行所必须的处理、投机失败时的重算的成本以及对各模块的输入预测命中何种程度(即投机成功概率)。对切分结果的路径递归地应用关键路径的可切分处理。于是，虽然进一步切分，但加上处理器之间的通信时间等，有时整体的处理时间反而变长，在这种情况下停止切分。据此，得到多个处理块的组。尤其是在本说明书的说明中，将各处理块的组称为模块组(block chunk)ο
若这样分割生成的模块组的个数与多处理器系统的处理器的个数相同或少于处理器的个数，则各个模块组直接被编译而按执行环境被分别分配给各个处理器。但是，若模块组的个数多于处理器的个数，则本发明的处理程序，尝试将模块组结合，以使模块组的个数等于处理器的个数。此时，优选是选择结果结合成的模块组中的关键路径的处理时间的最大值为最小这样的结合。这样结果的模块组被编译而在实际环境下分别分配给各个处理器。这样一来，对所有模块组的每一个模块组分配一个处理器，进行最优的并行处理。如上所述，根据本发明，在多处理器环境中，可实现对关键路径的长度和处理器分配这两方面均改善了的高速的程序执行。能够输出用于仿真的投机执行的最优代码。
图1是表示仿真建模工具的方框图的例子的图。图2是表示CP调度方法的例子的图。图3是用于实施本发明的硬件的框图。图4是本发明一实施例的功能框图。图5是表示本发明一实施例的处理流程的图。图6是切分关键路径的处理的流程图。图7是切分关键路径的处理的流程图。图8是切分关键路径的处理的例子的示意图。图9是表示包括投机时的期待执行时间的图。图10是模块组形成处理的例子的示意图。图11是CPU分配用代码生成处理的流程图。图12是CPU分配用代码生成处理的流程图。图13是模块组结合处理的例子的示意图。图14是模块组结合处理的例子的示意图。图15是用于说明模块之间的依存关系的图。附图标记的说明404源代码406、422 编译器
412 “关键路径的切分”模组416 "CPU分配用代码生成”模组418 CPU 代码420依存关系信息
具体实施例方式以下，参照附图来说明本发明一实施例的构成及处理。在以下的说明中，只要没有特别否定，在附图中对同样构件标注相同附图标记用来参考。在此说明的构成和处理是作为一实施例来说明，应理解到不是想要将本发明的保护范围限定解释为该实施例。接着，参照图3，说明用于实施本发明所使用的计算机的硬件。在图5中，主机总线302上连接有多个CPUl 304a、CPU2 304b、CPU3304c、…CPUn 304η。主机总线502上还连接有用于进行CPUl 304a、CPU2 304b、CPU3 304c,…CPUn 30 的运算处理的主存储器 306。另一方面，I/O总线308上连接有键盘310、鼠标312、显示器314及硬盘驱动器 316。I/O总线308经由I/O桥318与主机总线302连接。键盘310及鼠标312是为了操作者敲入指令、单击菜单等进行操作而使用的。显示器314是为了根据需要显示用于用GUI 操作后述的本发明的程序的菜单而使用的。作为为了该目的使用的优选的计算机系统的硬件，有IBM(R)System X。此时， CPUl 304a、CPU2 304b、CPU3 304c、... CPUn304n 例如是因特尔(R) Xeon (R)，操作系统是 Windows (商标)Server 2003。操作系统存储于硬盘驱动器316中，在计算机系统启动时， 从硬盘驱动器316读取到主存储器306。另外，为了实施本发明可使用的计算机系统的硬件，不限于IBM(R)System X，至少能运行本发明的仿真程序，可以使用任意计算机系统。操作系统也不限于Windows(R),可以使用Linux(R)、Mac OS(R)等任意操作系统。而且，为了使仿真程序高速工作，也可以使用 POWER (商标)6为基础，操作系统为AIX (商标)的IBM(R)System P等的计算机系统。在硬盘驱动器316中还存储有MATLAB (R)/Simulink (R)、C编译器或C++编译器、 用于切分本发明的关键路径的模组、CPU分配用代码生成模组、用于测量处理块的期待执行时间的模组等，响应操作者的键盘或鼠标操作而载入到主存储器306来执行。另外，可使用的仿真建模工具不限于MATLAB (R) /Simulink(R)，可以使用开放源的 Scilab/Scicos等任意的仿真建模工具。或者，根据情况，可以不使用仿真建模工具，而直接用C、C++写出仿真系统的源代码，在该情况下也可应用本发明。图4是本发明的实施例的功能框图。各个框基本上与存储在硬盘驱动器316中的模组对应。在图4 中，仿真建模工具 402 可以是 MATLAB (R)/Simulink(R)、kilab/Scicos 等现有的任意工具。仿真建模工具402基板上具有如下功能操作者在显示器314上以⑶I 方式配置功能模块，记述数学式等必要的属性，根据需要可以在功能模块之间施加关联地记述方框图。仿真建模工具402还具有如下功能输出用于记述与所记述的方框图等效功能的C的源代码。除了 C之外，也可以使用C++、Fortran等。另外，仿真建模工具也可以导入到其他个人计算机，将在此生成的源代码经由网络等下载到硬盘驱动器316。如此输出的源代码404被保存于硬盘驱动器316。源代码404在编译器406被编译，作为编译结果的可执行的程序被送至测试模组408。测试模组408具有进行执行测试的功能和进行投机测试的功能。在执行测试中， 根据规定的脚本，测量图1所示的各模块的平均处理时间、处理器之间通信时间及投机成功概率。为了测量平均时间，优选采用同一脚本执行多次。其测量结果410为了在后面使用而保存于硬盘驱动器316。在投机测试中根据其他的规定脚本投机执行作为编译结果的可执行程序。通过重复其脚本，测量如下时间投机准备的处理时间，即，在投机失败进行重算时，用于进行保存预测的输入值这样处理的时间；投机成功与否确认的处理时间，即，进行在实际的数据到来时确认其是否与预测的数据一致的处理的时间；重算处理时间，即，得知投机失败即预测的输入与实际值不同时，进行停止基于错误输入进行的处理、删除数据等后续处理所需要的时间。这样的值也作为测量结果410，为了在后面使用而保存于硬盘驱动器316。关于投机成功概率，其实不实际进行投机执行也能算出该投机成功概率。在投机执行中，在本来要到来的输入到来之前执行处理，因此预测该输入执行处理。因此，投机成功的概率等于针对输入的预测命中的概率。若规定了预测其输入的算法，则实际不进行投机执行(即不进行基于预测的输入数据的模块处理)，仅从实际的输入数据也能算出预测算法的预测成功概率。即，仅是在“执行测试”中记录对各模块的输入，根据该输入数据序列算出输入预测算法的预测成功率，从而能够求出投机成功概率。另一方面，在进行了投机执行时，或者投机执行失败了时会花费怎样程度的时间，不实际进行投机执行时不知道的。 因此，为了得到这些信息而进行投机测试。但是，若规定投机执行的安装，则可预想到投机准备、投机的成功与否确认、投机失败时的重算所需的处理时间是与输入数据量成正比的处理时间。因此，在“投机测试”中，可以不对所有模块进行投机执行，通过对尝试对几个输入数据量不同的模块进行投机执行，来得到输入数据量与投机关联处理时间的关系，可以基于此算出所有情况的成本。“关键路径的切分”模组412具有如下功能原则上按模块单位对源代码404进行处理，找出关键路径，进行切分，找出成为最优执行时间的切分。此时，使用测量结果410的信息。模组412还递归地应用关键路径的切分功能，得到如图10所示的分成小块的模块组。 这样生成的模块组的信息414为了在后面使用而保存于硬盘驱动器316。关于关键路径的切分功能，后面参照流程图详细说明。"CPU分配用代码生成”模组416使用模块组的信息414和测量结果410生成分配给CPUl CPUn的代码418a、418b、…418m。如果模块组的个数少于或等于CPUl CPUn 的个数，则各模块组的代码直接分配给CPUl CPUn。但是，如果模块组的个数多于CPUl CPUn的个数，则如图14示意所示，将模块组彼此结合，以使得模块组的个数等于CPUl CPUn的个数。但是，此时的结合优选是以使作为结果的关键路径的期待执行时间为最少的方式最优选择。关于CPU分配用代码生成功能，也是后面参照流程图详细说明。结果所生成的是分配给CPUl CPUn的代码418a、418b、…418m和依存关系信息420。依存关系信息420是必须的，其理由如下所示。即，如图10所示，原本的处理流程被关键路径的切分功能分断，则有时原本的模块之间的依存关系被切断。为了对其补偿，模组416也提供例如分配给CPUl CPUn的代码418a、418b、…418m中的某个代码返回到在其他某一代码所使用的变量、等这样的依存关系信息420。实际上，依存关系信息420是由 “关键路径的切分”模组412在切分时作出的，因此“CPU分配用代码生成”模组416利用该 fn息ο这样生成的代码418a、4imK…418m在编译器422被分别编译成可执行的程序， 在执行环境424以在对应的CPUl CPUn上并行执行的方式被分别分配。依存关系信息 420以可被CPUl CPUn共用参照的方式配置在主存储器306的共用存储器区域，CPUl CPUn执行代码418a、418b、…418m时，根据需要，为了参照在其他CPU上执行的代码的信息而使用上述依存关系信息。图5表示该实施例的整体处理流程。应理解到，这是表示作业顺序的流程，未必是与计算机的处理流程一一对应的。在图5中，在步骤502中，开发者或作业者使用MATLAB(R)/Simulink(R)等仿真建模工具402，在图3所示的系统上或其他计算机上做成特定仿真对象的方框图。在步骤504，开发者或作业者使用仿真建模工具402的功能生成与作成的方框图对应的源代码404，并保存于硬盘驱动器316。在步骤506，开发者或作业者使用编译器406编译源代码404。编译出的可执行的程序未图示，暂时保存于硬盘驱动器316。在步骤508，开发者或作业者使用编译出的执行程序在测试模组408进行执行测试。结果得到的模块的平均处理时间、处理器之间通信时间以及投机成功概率的执行时间的测量数据在步骤510作为测量结果410而保存于硬盘驱动器316。在步骤512，开发者或作业者使用编译出的执行程序在测试模组408进行投机测试。结果得到的投机准备的处理时间、投机成功与否确认的处理时间以及重算处理时间的测量数据在步骤514作为测量结果410而保存于硬盘驱动器316。在步骤516，响应开发者或作业者的操作而开始计算机的处理。即，基本上从步骤 516到步骤524自动进行计算机的处理。在步骤516，由“关键路径的切分”模组412处理源代码404。具体的处理将后述，通过算法找出源代码404记述的整体处理流程中的关键路径，按照处理时间将其最优切分， 在切分后的处理流程中递归地进行切分关键路径这样的处理。此时，使用测量结果410。结果，得到图10所示的多个模块组，因此在步骤518，与其相关的信息作为模块组 414被保存于硬盘驱动器316。此时保存的数据构造，可以使用XML等计算机可读的、可表现出源代码和内容和连结关系(链接)这两方面内容的任意的数据构造。在步骤520，使用模块组414的信息，“CPU分配用代码生成”模组416生成用于分别分配给CPUl CPUn的代码。即，如果模块组的个数少于CPUl CPUn的个数，则直接将代码逐个地分配给CPUl CPUn。而如果模块组的个数多于CPUl CPUn的个数，则将模块组以执行时间上成为最短的方式结合成与CPUl CPUn的个数相等。此时，使用测量结果 410。在步骤522，由模组416生成的代码被编译器422编译，在步骤5 中，分别将代码分配给对应的处理器CPUl CPUn，分别执行。参照图6和图7的流程图，说明与图5的步骤516对应的、关键路径的切分的处理。在步骤602，进行找出关键路径的最优切分这样的处理。在此，为了说明最优切分是指什么，参照图8。在图8表示由模块A I构成的处理的流程。在此，利用找出关键路径的算法， 特定了 B-C-D-E-F为关键路径，则在步骤602，“关键路径的切分”模组412依次尝试沿 B-C-D-E-F的可进行的切分cl、c2、c3、c4。例如，尝试切分c3是指在c3处将关键路径切分，如图8所示，逻辑上将切分下来的流程移至旁边。于是，成为2个流程并置。在此评价切分c3。评价切分c3是指若假定投机成功概率为100%，则比较并置的2个流程的期待执行时间，评价时间较长一方的值T。。但是，通常投机成功概率低于100%，因此如图9所说
10明的那样，考虑到投机成功概率来评价T。。将使这样的T。成为最短的切分成为最优切分。用于找出最优切分的更详细处理(子程序)在后面参照图7的流程图进行说明。另外，在图5的步骤508所示的执行测试中预测各模块的期待执行时间，作为测量结果410保存于硬盘驱动器316。应注意到在计算所要的流程的期待执行时间时使用这样的测量结果410。实际上，为了估计执行时间，仅是单纯地沿流程执行模块的期待执行时间是不够的。参照图9说明该问题。在此，定义如下的变量。在此，成本可以视作时间。MSCxy 模块X与模块Y被切分时的、从模块X到模块Y的消息发送成本。MRCxy 模块X与模块Y被切分时的、从模块X到模块Y的信息接收成本。SCxy 从模块X到模块Y的投机成本。SCCxy 从模块X到模块Y的投机确认成本。RBCxy 从模块X到模块Y的投机失败了时的重算成本。这些模块之间的成本也是在图5的步骤508所示的执行测试及步骤512所示的投机测试中预测，作为测量结果410而保存于硬盘驱动器316。于是，在关键路径B-C-D-E-F的C和D之间插入切分c，需要如图9所示那样根据投机成功时和投机失败时的期待值估计结果的期待执行时间。在投机成功时，切分的结果的2个流程的较长一方的执行时间成为结果的期待时间，为Tcs = ID I +1E I +1FI +SCcd+MRCif+MRCcd+SCCcd在此，例如ID I表示模块D的执行时间。另外，在投机失败了时，B-C和D-E-F是串联执行的，因此期待时间是Tcf = IB I +1 CI +1D I +1E I +1FI +MRCac+MSCcd+MRCcd+RBCcd+MRCif但是，这样的投机的成功概率ρ。在图5的步骤508所示的执行测试中预测，作为测量结果410保存于硬盘驱动器316。使用该结果，计算结果的期待执行时间为T。= PcTcs+(I-Pc) Tcf。返回图6的流程图，利用步骤602的处理结果，在步骤604“关键路径的切分”模组 412判断是否存在最优切分。存在最优切分是指切分的结果缩短了整体的期待处理时间。 在任何情况下切分未必都缩短处理时间。即，鉴于上述的发送成本、接收成本及投机成本， 有时即使切分也不能缩短处理时间。在这样的情况下，在步骤604判断为不存在最优切分， 在步骤606中，将当前评价的模块组的信息优选保存于硬盘驱动器316。另一方面，在步骤604判断为存在最优切分时，“关键路径的切分”模组412在步骤 608移动切分后的模块。这是图8所示的处理。在步骤610，对于切分后而成的路径的整个集合，递归地调出图6的流程图的处理。用图8的框图进行说明，首先对于模块A、B、C、D、E、F、G、H、I应用图6的流程图的处理，结果分成模块A、B、C、D、E、F和模块G、H、I，因此，递归地调出图6的流程图的处理。接着，参照图7的流程图更详细说明图6的步骤602的处理。在步骤702，进行找出关键路径的处理。对于处理流程找出关键路径的处理本身是公所周知的，例如可使用http//www. koRures. com/hitoshi/webtext/pt~pert/index, html 中记载的PERT的方法等。在步骤704，设置为tmin =沿关键路径的期待时间，Cmin = null, C =关键路径的可切分的集合。在步骤706，判断C是否为空，若不为空，则进入步骤708，从C取出切分C。在步骤710，计算切分c的期待执行时间，将其代入t。。在此的执行时间的计算包括与图9相关的说明的、投机执行的情况。在步骤712，判断是否是 tc < tmin，若 tc < tmin，则在步骤 714，设 tmin = tc, Cfflin =
Co这样一来，对于C的所有切分，执行步骤708、710、712及714，结果的Cmin返回图6 的步骤602。此时，存在C中某种切分使处理时间不短于tmin =沿关键路径的期待时间的情况。这样的情况下，在步骤712的判断不是肯定，因此不执行步骤714，因此Cmin = null保持不变。于是，图6的步骤604的判断为否定。图10示意地表示这样的处理的结果。图10的左侧所示的模块的处理流程被图6 的流程图所示的处理的递归过程在多个部位切分，如图10的右侧所示，得到细分化的多个模块组。接着，参照图11和图12的流程图说明与图5的步骤520对应的CPU分配代码生成的处理。这是由图4的“CPU分配用代码生成”模组416执行的。在步骤1102，设置p =处理器(CPU)的个数，b =模块组的个数。在步骤1104，判断是否是ρ <b。若其结果是否定的，即ρ彡b，则具有可以直接将模块组分别分配的个数的处理器，因此，在步骤1106中，适当地将各个模块组分配给各个处理器，结束处理。在步骤1104，若判断是？ < b，则表示要直接将模块组分别分配，处理器的个数不够，因此在步骤1108将2个模块组结合，进行减少1个模块组的个数的处理。将2个模块组结合，有时存在在结合的模块组处关键路径延长而期待处理时间变长的情况。因此，在步骤1108中，找出将2个模块组结合的结果的期待处理时间成为最短这样的最优的组合方式。图14示意地表示这样的处理。在步骤1110中，b减去1，返回步骤1104的判断。这样一来，直到ρ = b，反复进行步骤1108和步骤1110。当ρ = b时，步骤1104为否定。于是表示现在具有直接将模块组分别分配的个数的处理器，在步骤1106中，将在该时刻保存的结果的各个模块组分配于各个处理器，结束处理。另外，有时在想要将几个CPU保留用于其它处理时，进一步减少模块组的个数，直到 b < ρ。图12是更详细地表示图11的步骤1108的处理的流程图。在图12中，在步骤1202 中，设置S1 =当前的模块组的集合，tmin = -，Ufflin = c ，I3l = Id2 = null。在此，①是指在该状况下比实际上假定的个数大很多的适当的常数。在步骤1204中，判断S1是否为空，如果为空，则处理完成，返回图11的流程图的步骤1108。若S1不为空，则在步骤1206，从S1取出1个模块组Sl。在步骤1208中，设置& =当前的模块组的集合。在步骤1210，判断&是否为空，如果为空，则返回步骤1204。若&不为空，则在步骤1212，从&取出1个模块组&。在步骤1214中，使用图4所示的各模块的测量结果410来计算将S2结合到S1之下时的执行时间，并将其代入Tsls2。在此，^ = S1的情况省略。哪个模块组都是原文的模块的流程的一部分，因此有时在任意2个模块组之间，能够决定哪一方原本就位于上游。因此，优选是在步骤1214，若能够判定原文的上下游关系，则以维持其上下游关系的方式将2 个模块组结合。在步骤1216中，判断Tsls2是否等于Tmin。如果相等，则在步骤1218，计算将S2结合在S1下方时的期待成本，并代入usls2。在此，成本是指在对各模块的执行时间、跨过不同处理器的模块之间的信息收发成本、投机成本、投机确认成本、投机失败时的重写成本每次组合可投机成功与否时按投机成功概率赋予权重而算出的、所有CPU消耗时间的期待值。接着，在步骤1220中，判断是否是Usls2 < Umin，若是，则在步骤1222，在Tmin = Tsls2, bi = Si、b2 = S2^ufflin中代入将&结合于S1之下时的期待成本。从步骤1222返回步骤1210 的判断。另一方面，在步骤1216中，若Tsls2不等于Tmin，则进入步骤1224，因此，判断是否是八132<!1_。如果是则执行步骤1222，然后返回步骤1210的判断。若不是则直接从步骤 12M返回步骤1210的判读。图13表示模块组的结合例。在该例子中，如图所示，有模块组bcl、bc2、bc3、bc4 这4个模块组。于是，若不管原文的流程的上下游，则可有12种结合，但若将所有结合罗列说明太冗长，因此代表性地说明左下所示的、将bc3结合于bc2之下的情况和右下所示的将 bc4结合于bcl之下的情况。首先，将bc3结合于bc2之下时，期待执行时间tb。2b。3和期待成本ub。2b。3分别如下这样计算。tbc2bc3 = IB I +1 CI +1D I +1E I +1FI +MRCac+MRCifUbc2bc3 = AI +1B I +1 CI +1D I +1E | +1F | +1GI +1HI + 111 +MRCac+MRCif+MSCac+MSCif另一方面，将bc4结合于bcl之下时，期待执行时间tb。lb。4和期待成本ub。lb。4分别如下这样计算。tbclbc4 = P1P2 (ID I +1E I +1F | +SCcd+SCif+MRcd+SCCcd+MRCif+SCCif) +P1 (l_p2) (| A | + GI +1HI +111 +1 FI +MSAac+MSCif+MRCif+SCCif+RBCif) + (I-P1) (| B | +1 C | +1D | +1 E | +1 F | +MRC
ac+MSCcd+MRCcd+SCCcd+RBCcd+MRCif)Ubclbc4 = AI +1B I +1 CI +1D | +1E | +1F | +1G | +1H | +111 +P1P2 (SCcd+SCif+MRcd+SCCcd+M RCif+SCCif) +P1 (l-p2) (MSAac+MSCif+MRCif+SCCif+RBCif) + (I-P1) (MRCac+MSCcd+MRCcd+S CCcd+RBCcd+MRCif)在此，P1和p2是图示的路径中的投机成功概率。上述各个值都根据测量结果410而取得。图14是表示如下处理的图，具有模块组bcl、bc2、bc3、bc4、bc5、bc6这6个，在 CPU只有5个时，为了减少1个模块组，"CPU分配代码生成”模组416尝试将2个模块组结合时的处理。图14的左下表示bc6结合于bc4之下，其结果bc3给予整体最长的执行时间tsls2。图14的右下表示bc5结合于bcl之下，其结果bcl给予整体最长的执行时间tsls2。
"CPU分配代码生成”模组416对可能的所有模块组的组合计算最长的执行时间
tsls2，其结果是选出表示最短的tsls2的模块组的结合。如此生成的每个CPU的代码分别由编译器422编译而转换为可执行的代码时，暂时保存于硬盘驱动器316。但是，若在原本相连的模块的流程中插入切分，则有时切分的结果是各个模块之间的依存关系被切断，因此需要补偿这样的信息。图15是用于说明这样的依存关系的示意图。在图15中，设由模块A及模块C构成的代码成为codel、由模块B及模块D构成的代码成为code2、由模块F、模块H及模块J构成的代码成为Code3、由模块E、模块G及模块 I构成的代码成为code4。codel、code2、code3及code4的中段如图15所示。于是，可以看出，分别使用 codel、code2及code4的最初的还原值作为code3的参数。该情况例如下述所记述。1st output of codel- > 1st argument of code31st output of code2- > 2nd argument of code31st output of code3- > 3rd argument of code3"CPU分配代码生成”模组416在生成各个CPU分配用代码时，一并生成这样的信
肩、ο依存关系信息包括各个CPU分配用代码，可对编译器422通知，但优选是直接配置的执行环境424的共享存储器上等，CPUl CPUn执行所分配的代码时，能够参照依存关系
fn息ο这样一来，通过操作者的操作，开始仿真动作时，被编译的各CPU用的可执行程序依次被执行环境似4读取到主存储器306，执行环境似4对各个处理器分配关于各个可执行程序生成的进程。这样一来，由各个处理器并行执行被分割为多个可执行程序的仿真程序。在以上的实施例中，说明了基于使用仿真建模工具生成的程序源代码，分配到多个CPU进行并行处理，但本发明不限于这样的仿真程序源代码，如果能够特定处理块单位、 或记述其流程，就能应用任意的源代码。
权利要求
1.一种源代码处理方法，其通过计算机处理来生成用于在多处理器系统中能够并行执行的源代码，其特征在于，包括输入程序源代码的步骤；通过上述计算机处理来找出上述程序源代码的处理的关键路径的步骤；以及对上述关键路径进行切分来与上述多处理器系统的各个处理器对应而分割上述源代码的步骤。
2.根据权利要求1所述的源代码处理方法，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的步骤，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
3 根据权利要求2所述的源代码处理方法，其特征在于，包括还测量跨不同处理的处理器时的信息传递成本、用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录的步骤。
4.根据权利要求2所述的源代码处理方法，其特征在于，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
5.根据权利要求1所述的源代码处理方法，其特征在于，还包括输出包含上述所分割的源代码之间的变量和参数的依存关系信息在内的信息的步骤。
6.根据权利要求2所述的源代码处理方法，其特征在于，还包括以下步骤比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
7.根据权利要求6所述的源代码处理方法，其特征在于，在上述结合所分割的源代码的步骤中，使用上述所记录的处理时间来按以下方式进行结合使所结合的源代码中的期待处理时间最长的期待处理时间为最短。
8.根据权利要求1所述的源代码处理方法，其特征在于，上述源代码是利用仿真建模工具的功能来生成的，上述源代码的处理块单位与仿真建模工具上的方框图的模块对应。
9.一种源代码处理系统，其通过计算机处理来生成用于在多处理器系统中能够并行执行的多个源代码，其特征在于，包括记录单元，其保存程序源代码；找出单元，其通过上述计算机处理来读取上述程序源代码，从而找出该源代码的处理的关键路径；以及分割单元，其切分上述关键路径来与上述多处理器系统的各个处理器对应而分割上述源代码。
10.根据权利要求9所述的源代码处理系统，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的单元，上述分割源代码的单元使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
11.根据权利要求10所述的源代码处理系统，其特征在于，上述测量处理时间来进行记录的单元还测量跨不同处理的处理器时的信息传递成本、 用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录。
12.根据权利要求10所述的源代码处理系统，其特征在于，上述分割源代码的系统使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
13.根据权利要求9所述的源代码处理系统，其特征在于，还包括输出包含上述所分割的源代码之间的变量和参数的依存关系信息在内的信息的单元。
14.根据权利要求10所述的源代码处理系统，其特征在于，还包括结合单元，该结合单元比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，并响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
15.根据权利要求14所述的源代码处理系统，其特征在于，上述结合所分割的源代码的结合单元使用上述所记录的处理时间来按以下方式进行结合使所结合的源代码中的期待处理时间最长的期待处理时间为最短。
16.根据权利要求9所述的源代码处理系统，其特征在于，上述源代码是利用仿真建模工具的功能来生成的，上述源代码的处理块单位与仿真建模工具上的方框图的模块对应。
17.一种计算机系统，其通过多处理器系统来执行能够并行执行的多个程序，其特征在于，包括记录单元，其保存程序源代码；找出单元，其通过上述计算机处理来读取上述程序源代码，从而找出该源代码的处理的关键路径；分割单元，其切分上述关键路径来与上述多处理器系统的各个处理器对应而分割上述源代码，编译单元，其对上述所分割的源代码进行编译；分配单元，其将上述所编译的能够执行的程序分配给上述多处理器系统的各个处理器。
18.根据权利要求17所述的计算机系统，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的单元，上述分割源代码的单元使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
19.根据权利要求18所述的计算机系统，其特征在于，上述测量处理时间来进行记录的单元还测量跨不同处理的处理器时的信息传递成本、 用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录。
20.根据权利要求18所述的计算机系统，其特征在于，上述分割源代码的系统使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
21.根据权利要求17所述的计算机系统，其特征在于， 还包括输出包含上述所分割的源代码之间的变量和参数的依存关系信息在内的信息的单元；和使上述多处理器系统的各个处理器能够参照上述依存关系信息来进行载入的单元。
22.根据权利要求17所述的计算机系统，还包括结合单元，该结合单元比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，并响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
23.一种程序，其通过计算机处理来生成用于在多处理器系统中能够并行执行的源代码，其特征在于，使上述计算机执行输入程序源代码的步骤；通过上述计算机处理来找出上述程序源代码的处理的关键路径的步骤；以及切分上述关键路径来与上述多处理器系统的各个处理器对应而分割上述源代码的步骤。
24.根据权利要求1所述的程序，其特征在于，还包括对上述源代码进行编译并执行，且测量上述源代码的处理块单位的处理时间来进行记录的步骤，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间至少比原来的源代码的处理时间短。
25.根据权利要求M所述的程序，其特征在于，包括还测量跨不同处理的处理器时的信息传递成本、用于执行投机所需的处理、投机失败时的重算成本、以及对各模块的输入预测的准确率是多少这样的投机成功概率的数据来进行记录的步骤。
26.根据权利要求M所述的程序，其特征在于，在上述分割源代码的步骤中，使用上述所记录的处理时间来按以下方式进行分割使所分割的源代码中的期待处理时间最长的期待处理时间为最短。
27.根据权利要求M所述的程序，其特征在于，还包括以下步骤比较上述多处理器系统的处理器的个数与上述所分割的源代码的个数，响应上述所分割的源代码的个数多于处理器的个数的情况来结合上述所分割的源代码，以使上述所分割的源代码的个数等于或少于处理器的个数。
全文摘要
本发明提供一种源代码处理方法、系统及程序。本发明为了提供在多处理器系统中通过并行化来使程序的执行高速化的技术而对想要高速化的程序的关键路径适当进行切分，分成其他进程来分配给各个处理器。本发明的处理程序读取由多个处理块构成的想要高速化的程序源代码，并对关键路径的所有可能的切分进行测试，找出使作为结果的所切分处理块的流程的处理时间最短的切分。据此获得多个处理块组。如此分割生成的各个模块组被编译而按执行环境被分配给各个处理器。
文档编号G06F9/45GK102197376SQ20098014251
公开日2011年9月21日 申请日期2009年8月24日 优先权日2008年10月24日
发明者吉泽武朗, 小松秀昭 申请人:国际商业机器公司
最新回复(0)