Back to search

NJIT

Work-preserving real-time emulation of meshes on butterfly networks

Abstract

dc:description.abstract

<p>The emulation of a guest network G on a host network H is work-preserving and real-time if the inefficiency, that is the ratio W<sub>G</sub>/W<sub>H</sub> of the amounts of work done in both networks, and the slowdown of the emulation are O(1).</p><p>In this thesis we show that an infinite number of meshes can be emulated on a butterfly in a work-preserving real-time manner, despite the fact that any emulation of an s x s-node mesh in a butterfly with load 1 has a dilation of Ω(logs).</p><p>The recursive embedding of a mesh in a butterfly presented by Koch et al. (STOC 1989), which forms the basis for our work, is corrected and generalized by relaxing unnecessary constraints. An algorithm determining the parameter for each stage of the recursion is described and a rigorous analysis of the resulting emulation shows that it is work-preserving and real-time for an infinite number of meshes.</p><p>Data obtained from simulated embeddings suggests possible improvements to achieve a truly work-preserving emulation of the class of meshes on the class of butterflies.</p>

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Science - (M.S.)
Discipline thesis:degree_discipline
Computer and Information Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Achilles, Alf-Christian
Contributors dc:contributor
  • Bruce David Parker

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/theses/2351

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Achilles, Alf-Christian. Work-preserving real-time emulation of meshes on butterfly networks. https://digitalcommons.njit.edu/theses/2351