With the development of high-performance computing and the expansion of large-scale multiprocessor systems, it is significant to study the reliability of systems. Probabilistic fault diagnosis is of practical value to the reliability analysis of multiprocessor systems. In this paper, we design a linear time diagnosis algorithm with the multiprocessor system whose threshold is set to 3, where the probability that any node is correctly diagnosed in the discrete state can be calculated. Furthermore, we give the probabilities that all nodes of a d-regular and d-connected graph can be correctly diagnosed in the continuous state under the Weibull fault distribution and the Chi-square fault distribution. We prove that they approach to 1, which implies that our diagnosis algorithm can correctly diagnose almost all nodes of the graph.

The 3-ary n-cube, denoted as $Q_n^3$, is an important interconnection network topology proposed for parallel computers, owing to its many desirable properties such as regular and symmetrical structure, and strong scalability, among others. In this paper, we first obtain an exact formula for the minimum wirelength to embed $Q_n^3$ into grids. We then propose a load balancing algorithm for embedding $Q_n^3$ into a square grid with minimum dilation and congestion. Finally, we derive an O(N²) algorithm for embedding $Q_n^3$ into a gird with balanced communication, where N is the number of nodes in $Q_n^3$. Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.