{"id":15038,"date":"2022-06-16T20:06:32","date_gmt":"2022-06-17T00:06:32","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15038"},"modified":"2022-06-16T20:06:32","modified_gmt":"2022-06-17T00:06:32","slug":"tr-204-recognition-of-catastrophic-faults-in-reconfigurable-arrays-with-arbitrary-link-redundancy","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/tr-204-recognition-of-catastrophic-faults-in-reconfigurable-arrays-with-arbitrary-link-redundancy\/","title":{"rendered":"TR-204: Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-204<\/strong>
\nMarch 1992<\/p>\n

Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy<\/h2>\n
Amiya Nayak, Linda Pagli, Nicola Santoro<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n

Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have severe impact on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire system unusable regardless of its component redundancy and of its reconfiguration capabilities. The characterization of such patterns is crucial for the identification and detection of such catastrophic events. A complete characterization was given for reconfigurable systolic arrays with 2-link redundancy; i.e., a bypass link of fixed length is provided to each element of the array in addition to the regular link. In this paper, we study the more general case of arbitrary (but regular) link re\u00addundancy. In particular, we focus on the problem of deciding whether a pattern of k faults is catastrophic for a k-link redundant system; i.e., in addition to the regular link of length g1 = 1, each element of the array is provided with k-1 bypass links of length. g2, g3, … , 9k, respectively.
\nWe study this problem and prove some fundamental properties which any catas\u00adtrophic fault pattern must satisfy. We then show that these properties together consti\u00adtute a necessary and sufficient condition for a fault pattern to be catastrophic for k-link redundant system. As a consequence, we derive a provably correct recognition algo\u00adrithm whose worse-case time complexity is O(kgk)i this also improves on the previous algorithm for k = 2.<\/p>\n

<\/div>\n

TR-204.pdf<\/a><\/p>\n