SUCCESSFUL PERCENTAGES OF EMBEDDING SUBSYSTEMS INTO HYPERCUBES

In this papers, we will discuss the different percentages of embedding certain subsystems successfully into a ncube according to the fault m odel used. We will discuss two fault models: the first one assumes tha t, in a faulty node, the computational function of the node is lost wh ile the communication function of the faulty node remains intact, and, in the second, the communication function is also lost. In this paper , 2 types of fault tolerable subsystem embedding schemes will be intro duced. The first one embeds a complete binary tree into a n-cube with faulty nodes, and the second embeds two (n-1)-subcubes whose total num ber of faulty nodes is less than half the number of nodes. These schem es are divided into 4 types based on the above two models. First, we w ill discuss how different the successful percentages of embedding are for 2 of the different types of embedded binary trees that are based o n the above two models. Then, we will analyze the possibility that the component nodes of an embedded binary tree can communicate via the fa ulty nodes that are located in the embedded binary tree. In the embedd ing process, each faulty node was replaced with a nonfaulty node that was located on another (n-1)-subcube and al a Hamming distance of 1 fr om the faulty node. The number of faults that led to the successful pe rcentage of embedding will be presented as an upper bound. Next, we wi ll discuss how different the successful embedding percentages are for the 2 types of irregular (n-1)-subcubes based on the two models; that is, if 2(n-2) +1 or more of the nonfaulty nodes in both of the (n-1)-s ubcubes can communicate or not via faulty nodes. Here also, the number of faults that led to a successful embedding percentage will be prese nted as a critical value.