マルチプロセッサシステムの逐次診断について

概要

論文の詳細を見る
N個のプロセッサから成る任意のシステムの逐次診断可能次数は少なくともΩ(√^3<N>)であることが知られている.また, N個のプロセッサから成るハイパーキューブの逐次診断可能次数の下界と上界がそれぞれΩ(N log log N / log N)とO(N log log N / √<logN>)であること, CCCの逐次診断可能次数の下界と上界がそれぞれΩ(N log log N / log^2 N)とO(N log log N / √<logN>)であることも知られている.小文では, N個のプロセッサから成る任意のシステムの逐次診断可能次数は少なくともΩ(√<N>)であること, ハイパーキューブの逐次診断可能次数のが少なくともΩ(N / √〓<log N>)であること, CCCの逐次診断可能次数が⊝(N / log N)であることを示す.また, N個のプロセッサから成るシャッフル交換ネットワークとdeBruijnネットワークの逐次診断可能次数が⊝(N / log N)であることも示す.
社団法人電子情報通信学会の論文
2000-11-02