Algorithms for embedding binary trees into hypercubes
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Smedley, Garth Peter
issued: 2010-08-23T13:46:14Z
issued: 1989
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: The problem of embedding a guest graph G into a host graph H arises in the process of mapping a parallel program to a multicomputer. The communication structure of the program is represented by G, the interconnection network of the multicomputer is represented by H and the goal is to embed G into H such that some measure of the communication cost is minimized. In general, this problem is N P-complete and several types of approximation algorithms have been proposed. We evaluate these algorithms empirically using hypercube host graphs and binary tree guest graphs. These families of graphs are interesting because of the existence of both heuristic techniques and theoretical algorithms for this problem. Although for general trees the problem is N P-complete, for binary trees the complexity remains open. We have implemented and experimented with several different algorithms and discovered variations of a greedy approach which produce close to optimal solutions in a reasonable amount of time.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/27635
note: ALGORITHMS FOR EMBEDDING BINARY TREES INTO HYPERCUBES By GARTH PETER SMEDLEY B.Sc, University of British Columbia, Canada, 1989 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September 1989 © Garth Peter Smedley, 1989 6 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract The problem of embedding a guest graph G into a host graph H arises in the process of mapping a parallel program to a multicomputer. The communication structure of the program is represented by G, the interconnection network of the multicomputer is represented by H and the goal is to embed G into H such that some measure of the communication cost is minimized. In general, this problem is ./VP-complete and several types of approximation algorithms have been proposed. We evaluate these algorithms empirically using hypercube host graphs and binary tree guest graphs. These families of graphs are interesting because of the existence of both heuristic techniques and theoretical algorithms for this problem. Although for general trees the problem is ./VP-complete, for binary trees the complexity remains open. We have implemented and experimented with several different algorithms and discovered variations of a greedy approach which produce close to optimal soluti…
has type: Thesis/Dissertation
is shown at: 10.14288/1.0051922
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/27635