Show simple item record

dc.contributor.authorArabpour Niasari, Mehrdad
dc.date.accessioned2016-11-30T18:05:16Z
dc.date.available2016-11-30T18:05:16Z
dc.identifier.urihttp://hdl.handle.net/10464/10728
dc.description.abstractInterconnection networks are widely used in parallel computers. There are many topologies for interconnection networks and the hypercube is one of the most popular networks. There are a variety of different routing paradigms that need to be investigated on the hypercube. In this thesis we investigate the shortest path routing between two nodes on the hypercube when some nodes are faulty and cannot be used. In this thesis the shortest path between two nodes is considered as the Hamming distance of them. Regarding the shortest path problem in a faulty hypercube, some efficient algorithms have been proposed when each processor (node) has limited information regarding the status of other processors (whether they are faulty or not). There are also some proposed algorithms for the case where there is no limitation on the data of each processor but they are not efficient and are exponential in terms of number of faulty nodes and dimension of the hypercube. To check whether there is a shortest path between two given nodes in a faulty hypercube, we propose a polynomial algorithm with time complexity of O(n^2 * m^2) where n is the dimension of the hypercube and m is the number of faulty nodes. Our algorithm only requires the source node to know the state of all other nodes. The proposed algorithm first checks whether there is a shortest path from the source node to the target node and then it can construct it efficiently. Our idea is based on a so-called ordering and permutation model of paths in the hypercube. We use a constructive approach to find the path which is a permutation as well. We then use inclusion-exclusion and dynamic programming techniques to make our method efficient. We also propose an algorithm for counting all possible shortest paths in the hypercube.en_US
dc.language.isoengen_US
dc.publisherBrock Universityen_US
dc.subjectParallel Computingen_US
dc.subjectHypercubeen_US
dc.subjectShortest Pathen_US
dc.subjectFaulty Hypercubeen_US
dc.subjectRoutingen_US
dc.titleShortest Path Routing on the Hypercube with Faulty Nodesen_US
dc.typeElectronic Thesis or Dissertationen_US
dc.degree.nameM.Sc. Computer Scienceen_US
dc.degree.levelMastersen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.degree.disciplineFaculty of Mathematics and Scienceen_US
refterms.dateFOA2021-08-05T01:30:48Z


Files in this item

Thumbnail
Name:
Brock_Arabpour_Niasari_Mehrdad ...
Size:
2.405Mb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record