Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs
Ghosh, Sanjoy
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/72065
Description
Title
Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs
Author(s)
Ghosh, Sanjoy
Issue Date
1992
Doctoral Committee Chair(s)
Padua, D.A.
Emrath, P.A.,
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
