{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/21773"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/21773","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The analysis and synthesis of efficient algorithm-based error detection schemes for hypercube multiprocessors","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Balasubramanian, Vijay"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Banerjee, Prithviraj"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:18:43Z","date_published":"2011-05-07T13:18:43Z","updated_at":"2026-07-22T22:25:18Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Balasubramanian, Vijay"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9136536","(UMI)AAI9136536"],"render_values":[{"text":"AAI9136536","href":null,"code":true},{"text":"(UMI)AAI9136536","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/21773","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Banerjee, Prithviraj"]},{"key":"dc:creator","label":"Author","values":["Balasubramanian, Vijay"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:18:43Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Balasubramanian, Vijay"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9136536","(UMI)AAI9136536","http://hdl.handle.net/2142/21773"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T13:18:43Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9136536.pdf: 5736334 bytes, checksum: d52e3b2f1328ed4df845e4c378d8ed87 (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:53:06Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:24:31-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["The analysis and synthesis of efficient algorithm-based error detection schemes for hypercube multiprocessors"]}]}],"canonical_facts":{"dc:contributor":["Banerjee, Prithviraj"],"dc:creator":["Balasubramanian, Vijay"],"dc:date":["2011-05-07T13:18:43Z","10000-01-01","1991"],"dc:description":["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.","Made available in DSpace on 2011-05-07T13:18:43Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9136536.pdf: 5736334 bytes, checksum: d52e3b2f1328ed4df845e4c378d8ed87 (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:53:06Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:24:31-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9136536","(UMI)AAI9136536","http://hdl.handle.net/2142/21773"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Balasubramanian, Vijay"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["The analysis and synthesis of efficient algorithm-based error detection schemes for hypercube multiprocessors"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:18Z"}