指令级并行程序执行模型

THE MODEL OF INSTRUCTION LEVEL PARALLEL PROGRAM EXECUTION

提出了一种形式化的指令级并行程序执行模型（Ｉｎｓｔｒｕｃｔｉｏｎ－ＬｅｖｅｌＰａｒａｌｅｌＰｒｏｇｒａｍＥｘｅｃｕｔｉｏｎＭｏｄｅｌ，ＩＬＰＰＥＭ）．ＩＬＰＰＥＭ不仅可以描述程序实际执行过程的行为，也可以描述编译和执行时不确定的时间变化所造成的可行执行过程的行为；同时提出了程序执行的同构概念，并证明了可行程序执行必与一个实际程序执行同构，从而为并行程序编译和验证提供了理论依据．

This paper presents a formal instruction level parallel program execution model, ILPPEM. ILPPEM can describe not only behaviors of actual program executions, but also behaviors of feasible program executions resulted from compiling or nondeterministic timing variations during run time. This paper introduces a new concept, isomorphism of program executions, and proves that a feasible program execution is isomorphic with an actual program execution, which provides theoretical foundations for compiling and verifying parallel programs.