Abstract
dc:descriptionThe 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 1989
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Smedley, Garth Peter
Rights
dc:rights- Statement dc: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.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/27635