用Petri网分析循环程序的并行性

ANALYSIS OF THE PARALLELISM OF LOOP PROGRAM THROUGH PETRI NET

为分析循环程序的并行性,最重要且最基本的工作是数据相关性分析,而数据相关性分析最主要的内容之一是循环程序中数组元素间的数据相关性分析。传统的分析方法是通过数组的下标进行分析计算,但这种计算每次只能对两个语句间的相关性作出结论,而无法知道是否有第三个或更多的语句在这同一数据处相关,从而很难确定这两个语句是否可以并行。将Petri网用于数据相关性分析理论中,可以从全局的观点分析出同一数据处所有语句的相关性,从而可以提出将循环程序转换为并行程序的有效方法。

In analysing the parallelism of loop program the analysis of data dependency, which mainly concerns the analysis of a set of elements in loop program is the most important and fundamental.The method commonly used in analysing data dependency is by analysis and calculation through the footmark index.It cannot be decided whether a third or more statements can be involved in the calculation, because by this method we can only draw a conclusion on the relativity of two statements. So it is difficult to decide whether the two statements can run simultaneously. If Petri net is used in analysing data dependency,the relativities of all statements on the same base from the overall perspective viewpoint will be analysed, therefore an effective method for converting loop program into parallel program is provided.