Files in this item

FilesDescriptionFormat

application/pdf

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

Description

Title:Reconfiguration of Fault-Tolerant VLSI Systems
Author(s):Libeskind-Hadas, Ran
Doctoral Committee Chair(s):Liu, C.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Engineering, Electronics and Electrical
Computer Science
Abstract:Advances in VLSI (Very Large Scale Integration) allow increasingly larger and more complex systems to be fabricated on a single chip or wafer. As the number of elements in these systems increases, the problem of tolerating faulty elements becomes more and more important. This thesis addresses reconfiguration problems for several important fault tolerant architectures. We show that for some fault tolerant architectures the corresponding reconfiguration problems can be solved in polynomial time while for other related architectures reconfiguration is NP-hard. For those reconfiguration problems that can be solved in polynomial time, we present fast (and in many cases asymptotically optimal) algorithms. For the NP-hard reconfiguration problems, we propose several strategies. For some problems, polynomial time approximation algorithms are presented that yield provably good, but not necessarily optimal, solutions. For some reconfiguration problems, however, approximation algorithms are not meaningful. For these problems effective search strategies and heuristics are proposed.
Issue Date:1993
Type:Text
Description:150 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
URI:http://hdl.handle.net/2142/72094
Other Identifier(s):(UMI)AAI9411689
Date Available in IDEALS:2014-12-17
Date Deposited:1993


This item appears in the following Collection(s)

Item Statistics