The search functionality is under construction.

Keyword Search Result

[Keyword] system-level diagnosis(2hit)

1-2hit
  • Adaptive Diagnosis of Variants of the Hypercube

    Aya OKASHITA  Toru ARAKI  Yukio SHIBATA  

     
    PAPER-Graphs and Networks

      Vol:
    E88-A No:3
      Page(s):
    728-735

    System-level fault diagnosis deals with the problem of identifying faulty nodes (processors) in a multiprocessor system. Each node is faulty or fault-free, and it can test other nodes in the system, and outputs the test results. The test result from a node is reliable if the node is fault-free, but the result is unreliable if it is faulty. In this paper, we prove that four variants of the hypercube: the crossed cube, the twisted cube, the Mobius cube, and the enhanced cube, are adaptively diagnosed using at most 4 parallel testing rounds, with at most n faulty nodes (for the enhanced cube, with at most n + 1 faulty nodes), where each processor participates in at most one test in each round. Furthermore, we propose another diagnosis algorithm for the n-dimensional enhanced cube with at most n + 1 faulty nodes, and show that it is adaptively diagnosed with at most 5 rounds in the worst case, but with at most 3 rounds if the number of existing faulty nodes is at most n -log(n + 1).

  • An Optimal Adaptive Diagnosis of Butterfly Networks

    Aya OKASHITA  Toru ARAKI  Yukio SHIBATA  

     
    PAPER

      Vol:
    E86-A No:5
      Page(s):
    1008-1018

    System-level diagnosis is a very important technique for identifying faulty processors in a system with a large number of processors. Processors can test other processors, and then output the test results. The aim of diagnosis is to determine correctly the faulty/fault-free status of all processors. The adaptive diagnosis have been studied in order to perform diagnosis more efficiently. In this paper, we present adaptive diagnosis algorithms for a system modeled by butterfly networks. Our algorithms identify all faulty nodes in butterfly networks with the optimal number of tests. Then, we design another algorithm for diagnosis with very small constant number of rounds.