Value Prediction for MPI Message-Passing Systems

The predictability of various types of program information has been the subject of a plethora of work aimed to facilitate performance increases through latency reduction and speculation. Most past studies on prediction have been in the area of microarchitecture. This paper attempts to characterize the predictability of data in messages exchanged in parallel applications that use MPI message-passing protocol. Value predictors are used, drawn from the area of microarchitecture. The prediction of data in messages can enhance the performance of message passing parallel programs through speculative execution. This hypothesis is based on the dominance of communication latency in the overall execution time of parallel programs. An infrastructure based on code instrumentation was developed to investigate this predictability and results are pre-sented for five benchmarks. The results show that predictability varies depending on the program and predictor. Some programs exhibit virtually no predictability whereas others 57–94%. Predictability is found at different levels: within a message, across messages of the same process and across messages in different processes. The most influential- both con-structive and destructive- component of the information vector used to predict a value in a message buffer is the offset of the value in the buffer. The results indicate that data in MPI messages display mainly last-value and/or regularly-repeating behavior. The data suggest that most of the observed predictability can be captured with relatively small predictors.