Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/11151
Title: A New Approach to Stable Matching and Networks on Chip Problem
Researcher: Nitin
Guide(s): Chauhan, Durg Singh
Keywords: Networks on Chip
Systems on Chip
Upload Date: 13-Sep-2013
University: Jaypee University of Information Technology, Solan
Completed Date: 09/09/2008
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.
Pagination: 
URI: http://hdl.handle.net/10603/11151
Appears in Departments:Department of Computer Science Engineering

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File89.46 kBAdobe PDFView/Open
02_certificate.pdf16.67 kBAdobe PDFView/Open
03_acknowledgement.pdf18.02 kBAdobe PDFView/Open
04_contents.pdf32.35 kBAdobe PDFView/Open
05_list of tables figures.pdf32.14 kBAdobe PDFView/Open
06_chapter 1.pdf41.44 kBAdobe PDFView/Open
07_chapter 2.pdf1.29 MBAdobe PDFView/Open
08_chapter 3.pdf3.33 MBAdobe PDFView/Open
09_chapter 4.pdf10.47 MBAdobe PDFView/Open
10_chapter 5.pdf311.74 kBAdobe PDFView/Open
11_chapter 6.pdf26.28 kBAdobe PDFView/Open
12_references.pdf34.32 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.