Approximate Performance Evaluation of Parallel Processing Systems Based on Reducible State Spaces Computation

摘要

To evaluate the performance of parallel processing systems with a set of concurrent programs, several methods have been proposed such as decomposition approximation technique, which is applicable to only fixed concurrent programs. On the other hand, this paper will propose an innovative approach considering a more flexible set of concurrent programs. To avoid the state space explosion when the approximation is applied, the average concurrency is determined which is the average of the overall concurrency. The results apparently indicate that this proposed method can reduce the number of states from the exponential increment of power of N to the increment of power of average concurrency. This results a faster computational achievement as well as comes across a computational complexity. For various examples, the proposed method is compared with the result of simulation running on a mainframe computer. It is shown that the evaluation can be made by the proposed method with an error falling in the range below 10%. The paper also compares the relation between percentages of error against the standard deviation of concurrent programs.