Static intelligent backtracking restricted and-parallelism execution model

摘要

A complete static intelligent backtracking restricted and-parallel (RAP) execution model with five new instructions and a modified backtracking algorithm is described. A RAP supporting static intelligent backtracking abstract machine simulator is discussed. The simulator generates run-time statistics such as total run-time steps and total number of failures, etc., and runs a program in a round-robin fashion as it simulates an instruction on each of the multiple processors. Simulation results show that the total number of execution steps is decreased. Some failures which send a remote message and interrupt their parents in the RAP execution model are more expensive than in the sequential model because of the cost of the interprocessor communication. The total number of failures is decreased, thereby minimizing interprocessor communication cost. The simulation results show that the performance of a RAP abstract machine is improved by static intelligent backtracking.