The analysis and synthesis of efficient algorithm-based error detection schemes for hypercube multiprocessors
Balasubramanian, Vijay
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/21773
Description
Title
The analysis and synthesis of efficient algorithm-based error detection schemes for hypercube multiprocessors
Author(s)
Balasubramanian, Vijay
Issue Date
1991
Doctoral Committee Chair(s)
Banerjee, Prithviraj
Department of Study
Electrical and Computer Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Computer Science
Language
eng
Abstract
Numerous algorithms for computationally intensive tasks that are suitable for execution on hypercube multiprocessors have been developed by researchers. In this thesis, we look at parallel algorithm design from a different perspective: the provision of on-line detection of hardware errors using software techniques without any hardware modifications. This approach is called Algorithm-based error detection. We report on the implementation of system-level error detection mechanisms for four parallel applications on a 16-processor Intel iPSC-2/D4/MX hypercube multiprocessor: (1) matrix multiplication; (2) Fast Fourier Transform; (3) QR factorization; (4) singular value decomposition. We describe extensive studies of the error coverage of our system-level error detection schemes in the presence of finite precision arithmetic which affects our system-level encodings.
We also provide an in-depth study of the various issues and trade-offs available in Algorithm-based error detection. We illustrate the approach on an extremely useful computation in the field of numerical linear algebra: QR factorization. We discuss the implementation and investigation of numerous ways of applying Algorithm-based error detection using different system-level encoding strategies for QR factorization. Different schemes have been observed to result in varying error coverages and time overheads. We report the result of our studies performed on the Intel iPSC-2 hypercube.
Finally, we address the difficult task of synthesizing algorithm-based checking techniques for general applications. We approach the problem at the compiler level by identifying linear transformations in Fortran DO loops, restructuring program statements to convert nonlinear transformations to linear ones, and propose system-level checks based on this property. We discuss the implementation of a source-to-source restructuring compiler for the synthesis of low-cost system-level checks for general numerical Fortran programs, based on the above approach. We present the results of the application of this compiler to various routines from the LINPACK and EISPACK libraries, and from the Perfect Benchmark Suite. We also provide a detailed evaluation of compiler-assisted techniques for the LINPACK routine, DGEFA, and demonstrate the feasibility of our concept experimentally on the Intel iPSC-2 hypercube.
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.
