Platform Independent Analysis of Probabilities on Multithreaded Programs

Platform Independent Analysis of Probabilities on Multithreaded Programs

Yuting Chen
Copyright: © 2013 |Pages: 18
DOI: 10.4018/ijsi.2013070104
(Individual Articles)
No Current Special Offers


A concurrent program is intuitively associated with probability: the executions of the program can produce nondeterministic execution program paths due to the interleavings of threads, whereas some paths can always be executed more frequently than the others. An exploration of the probabilities on the execution paths is expected to provide engineers or compilers with support in helping, either at coding phase or at compile time, to optimize some hottest paths. However, it is not easy to take a static analysis of the probabilities on a concurrent program in that the scheduling of threads of a concurrent program usually depends on the operating system and hardware (e.g., processor) on which the program is executed, which may be vary from machine to machine. In this paper the authors propose a platform independent approach, called ProbPP, to analyzing probabilities on the execution paths of the multithreaded programs. The main idea of ProbPP is to calculate the probabilities on the basis of two kinds of probabilities: Primitive Dependent Probabilities (PDPs) representing the control dependent probabilities among the program statements and Thread Execution Probabilities (TEPs) representing the probabilities of threads being scheduled to execute. The authors have also conducted two preliminary experiments to evaluate the effectiveness and performance of ProbPP, and the experimental results show that ProbPP can provide engineers with acceptable accuracy.
Article Preview


A concurrent program with nondeterminism is intuitively associated with probability. A concurrent program can be nondeterministic in that races may exist in the program, each of which usually arises when separate threads are scheduled to execute sequentially on a single processor. When it happens, the execution steps of threads can be interleaved. Thus using an input to repeatedly execute the program can produce various program paths, each of which represents a sequence of program instructions executed.

A weak assumption is that the frequencies of all potential paths are uniformly distributed. For example, in the sample program shown in Figure 1, the ijsi.2013070104.m01 thread spawns the threads ijsi.2013070104.m02 and ijsi.2013070104.m03. Note that a data race exists in the program in the sense that after the program is executed, ijsi.2013070104.m04 can either be ijsi.2013070104.m05 or ijsi.2013070104.m06, and ijsi.2013070104.m07 can either be ijsi.2013070104.m08 or ijsi.2013070104.m09. Let the two threads ijsi.2013070104.m10 and ijsi.2013070104.m11 be executed in an interleaving manner, and each program statement be executed in an atomic manner. Six potential orders of the statements can be enumerated to represent six execution paths, each of which is denoted by using a sequence of pairs. A pair, say ijsi.2013070104.m12, is composed of a thread ijsi.2013070104.m13 and a statement ijsi.2013070104.m14.

Figure 1.

A simple program of two threads


Let ijsi.2013070104.m21 be the total number of program paths in the program, and ijsi.2013070104.m22 be the probability of a path ijsi.2013070104.m23. The weak assumption denotes that the frequencies of all execution paths are uniformly distributed, i.e.,

In this example, we have ijsi.2013070104.m25. However, the assumption is usually not true in practice. Running of the program for a number of times can inevitably find a fact that some program paths can be executed more frequently than the others.

Complete Article List

Search this Journal:
Volume 11: 1 Issue (2023)
Volume 10: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 9: 4 Issues (2021)
Volume 8: 4 Issues (2020)
Volume 7: 4 Issues (2019)
Volume 6: 4 Issues (2018)
Volume 5: 4 Issues (2017)
Volume 4: 4 Issues (2016)
Volume 3: 4 Issues (2015)
Volume 2: 4 Issues (2014)
Volume 1: 4 Issues (2013)
View Complete Journal Contents Listing