On the Multiple Bridge Fault Diagnosis of Baseline Multistage Interconnection Networks (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
スポンサーリンク
概要
- 論文の詳細を見る
This paper proposes new algorithms for diagnosing (detection, identification and location) baseline multistage interconnection networks (MIN) as one of the basic units in a massively parallel system. This is accomplished in the presence of single and multiple faults under a new fault model. This model referred to as the geometric fault model, considers defective crossing connections which are located between adjacent stages, internally to the MIN (therefore, a fault corresponds to a physical bridge fault between two connections). It is shown that this type of fault affects the correct geometry of the network, thus requiring a different testing approach than previous methods. Initially, an algorithm which detects the presence of bridge faults (both in the single and multiple fault cases), is presented. For a single bridge fault, the proposed algorithm locates the fault except in an unique pathological case under which it is logically impossible to differentiate between two equivalent locations of the fault (however, the switching element affected by this fault is uniquely located). The proposed algorithm requires log_2 N test vectors to diagnose the MIN as fault free (where N is the number of input lines to the MIN). For fully diagnosing a single bridge fault, this algorithm requires at most 2 x log_2 N tests and terminates when multiple bridge faults are detected. Subsequently, an algorithm which locates all bridge faults is given. The number of required test vectors is O(N). Fault location of each bridge fault is accomplished in terms of the two lines in the bridge and the numbers of the stages between which it occurs. Illustrative examples are given.
- 社団法人電子情報通信学会の論文
- 1996-08-25
著者
-
Lombardi Fabrizio
Department Of Computer Science Texas Aampm University
-
Horiguchi Susumu
Graduate School Of Information Science Jaist
-
Park Nohpill
Department Of Computer Science Texas Aampm University
-
Horiguchi Susumu
Graduate School Of Computer Science Japan Advanced Institute Of Science And Technology
-
Horiguchi Susumu
Graduate School Of Information Science Japan Advanced Institute Of Science And Technology
関連論文
- A Nonblocking Optical Switching Network for Crosstalk-Free Permutation
- Crosstalk-Free Permutation in Photonic Rearrangeable Networks Built on a Combination of Horizontal Expansion and Vertical Stacking of Banyan Networks(Special Issue on Parallel and Distributed Computing, Applications and technologies)
- A Lightpath Restoration Method Using Multi-Backup Paths in WDM Networks
- Dynamic RWA Based on the Combination of Mobile Agents Technique and Genetic Algorithms in WDM Networks with Sparse Wavelength Conversion(Software Agent and Its Applications)
- MOBLE ROBOT LOCALIZATION USIGNG OMINI-DIRECTIONAL VIEW
- TTN : A High Performance Hierarchical Interconnection Network for Massively Parallel Computers
- High-Performance Training of Conditional Random Fields for Large-Scale Applications of Labeling Sequence Data
- A Structured Walking-1 Approach for the Diagnosis of Interconnects and FPICs
- Expected-Credibility-Based Job Scheduling for Reliable Volunteer Computing
- Robust Node Positioning in Wireless Sensor Networks
- Self-Routing Nonblocking WDM Switches Based on Arrayed Waveguide Grating
- Routing Algorithms for Packet/Circuit Switching in Optical Multi-log_2N Networks
- Hybrid Packet-Pheromone-Based Probabilistic Routing for Mobile Ad Hoc Networks
- Fair Scheduling for Delay-Sensitive VoIP Traffic
- Efficient Network Coding-Based Loss Recovery for Reliable Multicast in Wireless Networks
- A More Efficient COPE Architecture for Network Coding in Multihop Wireless Networks
- Breakage prediction-based route maintenance in ad hoc networks (インターネットアーキテクチャ)
- Modified Hierarchical 3D-Torus Network
- Dynamic Communication Performance of a Hierarchical Torus Network under Non-uniform Traffic Patterns(Computer Systems)
- New Bounds on the Feedforward Design of Optical Output Buffer Multiplexers and Switches
- Maintaining Packet Order in Reservation-Based Shared-Memory Optical Packet Switch
- Redundant Vias Insertion for Performance Enhancement in 3D ICs
- Efficient routing algorithms for feedforward output buffer queue switch (ネットワークシステム)
- Variant X-Tree Clock Distribution Network and Its Performance Evaluations(Low-Power and High-Performance VLSI Circuit Technology,VLSI Technology toward Frontiers of New Market)
- 無線アドホックネットワークにおける蟻の食性を利用したルーティング法(ユビキタス)
- Parallel Molecular Dynamics in a Parallelizing SML Compiler(Special Issue on Parallel and Distributed Computing, Applications and technologies)
- HTN : A New Hierarchical Interconnection Network for Massively Parallel Computers(Special Issue on Parallel and Distributed Computing, Applications and technologies)
- A Class of Benes-Based Optical Multistage Interconnection Networks for Crosstalk-Free Realization of Permutations(Fiber-Optic Transmission for Communications)
- A more accurate skew model for well-balanced H-tree clock distribution network (プロセス・デバイス・回路シミュレーション(統計モデリングも含む))
- A more accurate skew model for well-balanced H-tree clock distribution network (プロセス・デバイス・回路シミュレーション(統計モデリングも含む))
- Behavior of Active Lightpath Restoration in All-Optical WDM Networks
- An Upper Bound on Blocking Probability for Vertical Stacked Optical Banyan Networks with Extra Stage
- Performance Measurement of the Multi-backup paths Restoration Scheme under Capacity Constraint
- On the Multiple Bridge Fault Diagnosis of Baseline Multistage Interconnection Networks (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- A Probabilistic Sentence Reduction Using Maximum Entropy Model(Natural Language Processing)
- Multicasting in Multihop Optical WDM Networks with Limited Wavelength Conversion(Special Invited Survey)
- Load Balancing Based on Load Coherence between Continuous Images for an Object-Space Parallel Ray-Tracing System
- Special Issue on Parallel and Distributed Computing, Applications and Technologies