Files in this item

FilesDescriptionFormat

application/pdf

application/pdf9305536.pdf (7MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs
Author(s):Ghosh, Sanjoy
Doctoral Committee Chair(s):Padua, D.A.; Emrath, P.A.,
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
Abstract:Parallel programs are significantly different from sequential programs in the sense that they can exhibit timing-dependent behaviour. The same program with the same input data can produce different results on different executions. This is unacceptable for a large number of programs. The main focus of this thesis is techniques to automatically detect such situations. Since nondeterminacy is intimately related to the ordering between operations executed by the program, the main problem studied is that of computing ordering between operations. The ordering is determined by the synchronization operations used.
The computation of ordering can be done either at compile time, or execution time and later. We describe techniques for both. Static analysis is applicable to every input data set, but is approximate due to the incompleteness of information available at compile time. Execution time analysis, on the other hand, has complete information about the execution, but may be applicable only for the input data set used on that execution. The approach advocated is a combination of compile time and execution time analysis.
The feasibility of these ideas is demonstrated by the implementation of a tool that detects nondeterminacy in the parallel programs available to us. Detection is practical with a combination of aggressive compile time analysis and execution time checking.
As an extension of the work on detecting ordering, a technique is described to perform dataflow analysis of parallel programs in order to effect scalar optimizations such as conditional constant propagation. The new dataflow framework reflects the fact that in parallel programs a number of threads can execute simultaneously.
Issue Date:1992
Type:Text
Description:150 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.
URI:http://hdl.handle.net/2142/72065
Other Identifier(s):(UMI)AAI9305536
Date Available in IDEALS:2014-12-17
Date Deposited:1992


This item appears in the following Collection(s)

Item Statistics