A New Approach to Stable Matching and Networks on Chip Problem

Abstract

This thesis emphasizes that the Stable Matching problems are the same as the problems of stable configurations of Multi stage Interconnection Networks (MIN). Author has provided solution to Regular and Irregular MINs Stability Problems using the algorithms and solutions provided by the Stable Matching Problem and specifically present Stable Marriage Problem as an example of stable matching. To solve the following problem a pair of algorithms is proposed. The first algorithm generates the MIN Preference Lists in O(n^2) time and other algorithm produces a set of most Optimal (Stable) Pairs of the Switching Elements (SE), derived from the MIN Preference Lists in O(n) time. Consequences include new algorithms for finding a Stable Matching between the SEs. An understanding of the difference between MINs Stability and Unstability problems. Moreover, the thesis also solves the problem of Ties that occurs between the Optimal pairs. The results are promising as the comparison of the MINs based on their stability shows that the fault tolerant irregular Quad tree Network (QTN) and Hybrid ZETA Network (HZTN) are less stable in comparison to Augmented Shuffle Exchange Network (ASEN) and Augmented Baseline Network (ABN). In conclusion, it is established that regular class of MINs are more stable than irregular class of MINs. newlineThe recent applications of the MINs include fault tolerant packet switches, designing multicast, broadcast router fabrics while Systems on Chip (SoC) and Networks on Chip (NoC) and are still in attention of researchers. Therefore, it is accept that intra (global) parallel communication among Application Specific NoCs in Networks in Package (NiP) remains an open problem, which shifts our focus from stability problems of MINs, application to provide global communication. Hence, the emphasis is laid on fault tolerant parallel algorithms to provide parallel communication among NoCs in NiP that can tolerate faults.