Platform Independent Analysis of Probabilities on Multithreaded Programs

Platform Independent Analysis of Probabilities on Multithreaded Programs

Yuting Chen (School of Software, Shanghai Jiao Tong University, Shanghai, China & Shanghai Key Laboratory of Computer Software Testing & Evaluating, Shanghai, China )
Copyright: © 2013 |Pages: 18
DOI: 10.4018/ijsi.2013070104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

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

Introduction

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 thread spawns the threads and . Note that a data race exists in the program in the sense that after the program is executed, can either be or , and can either be or . Let the two threads and 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 , is composed of a thread and a statement .

Figure 1.

A simple program of two threads

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

In this example, we have . 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:
Reset
Open Access Articles: Forthcoming
Volume 6: 4 Issues (2018): 1 Released, 3 Forthcoming
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