Graduate Thesis Or Dissertation
 

Processor allocation & communication in networks

Öffentlich Deposited

Herunterladbarer Inhalt

PDF Herunterladen
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/tx31qn41x

Descriptions

Attribute NameValues
Creator
Abstract
  • We will describe two known strategies for static processor allocation in an n-cube multiprocessor, namely the buddy system strategy and the gray code strategy, and then propose a new strategy that outperforms the first by (n-k+1) and the second by (n-k+1)/2 in cube recognition. Furthermore, our strategy is suitable for static as well as dynamic processor allocation and results in less system fragmentation, more subcubes recognition and higher fault tolerance. We also introduce an extension to our strategy that will enhance the performance drastically so that our algorithm, together with the extension, will outperform the buddy system by a factor of [k(n-k)+1] and the gray strategy by [k(n-k)+1]/2 in cube recognition. The implementation details of these algorithms are also described. The cube-connected cycles network is an attractive alternative for the n-cube, since it overcomes the degree problem by limiting it to 3. However, there are large gaps in the size of systems that can be built. We propose and study cube-connected cycles networks that are missing some of their cycles, called incomplete cube-connected cycles networks. These incomplete cube-connected cycles networks can be used to interconnect systems with any number of processors, thus overcoming the severe restriction of the complete cube-connected cycles networks. In incomplete cube-connected networks the processors are well utilized, routes are shorter and the layout area is a lot smaller. We develop efficient routing and broadcasting algorithms and show how to lay this network on a chip. Broadcasting is a procedure by which a processor can pass a message to all other processors in the network nonredundantly. It is extremely important for diagnosis of the network, distribution agreement and clock synchronization. We briefly describe the algorithm for broadcasting in the hypercube developed by Sullivan and Bashkow, then we develop a simple yet efficient fault tolerant broadcasting algorithm for the hypercube in the presence of some faulty processors. We develop an efficient algorithm for broadcasting in the cube-connected cycles network. Another broadcasting algorithm for cube-connected cycles networks with faulty cycles is also developed.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Urheberrechts-Erklärung
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Beziehungen

Parents:

This work has no parents.

In Collection:

Artikel

Miniaturansicht Titel Hochladedatum Sichtbarkeit Aktionen
file details AlDhelaanAbdullahM1989.pdf 2017-08-22 Öffentlich Herunterladen