On the granularity of events when modeling program executions

Abstract

In the context of parallel and distributed programming, program execution models are required to obtain a better understanding of the behavior, properties, and characteristics of parallel and distributed applications. One commonly adopted approach consists of representing an execution as a set of events and relations that capture the ordering of the events. The main disadvantages of most existing models are (1) the gap between the user's view of the execution and the program execution model, and (2) their inability to uniquely characterize an execution in terms of program behavior. The goal of this paper is to solve these two problems by first defining a new program execution model that enables more coarse-grained events to be considered, and then determining sufficient conditions for the model to uniquely identify the sequence of local states each process goes through. The essential result of our analysis is a better understanding of how instructions have to be grouped into events. To our knowledge, it is the first time that the problem of the granularity of the events is addressed in a formal way, and that a program execution model enables coarse-grained events to be considered while uniquely characterizing the behavior of the program. As a typical example, it is shown how to efficiently model collective communication operations, which are available in many current generation communication libraries, and which will be part of the future standard Message Passing Interface (MPI).