Ko, Tsz-Mei (1993) On the VLSI decompositions for complete graphs, DeBruijn graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-08302007-094049
A C-chip VLSI decomposition of a graph G is a collection of C vertex-disjoint subgraphs of G which together contain all of G's vertices and a subset of its edges. If the vertex-disjoint subgraphs are isomorphic to each other, we call one of these isomorphic subgraphs a building block. The efficiency of a VLSI decomposition is defined to be the fraction of edges of G that are in the subgraphs. In this thesis, motivated by the need to construct large Viterbi decoders, we study VLSI decompositions for deBruijn graphs. We obtain some strong necessary conditions for a graph to be a building block for a deBruijn graph, and some slightly more restrictive sufficient conditions which allow us to construct some efficient building blocks for deBruijn graphs. By using the methods described in this thesis, we have found a 64-chip VLSI decomposition of the deBruijn graph B13 with efficiency 0.754. This decomposition is being used by JPL design engineers to build a single-board Viterbi decoder for the K = 15, rate 1/4 convolutional code which will be used on NASA's Galileo mission.
Furthermore, we study VLSI decompositions for the families of complete graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs. In each of these cases, we obtain very efficient or even optimal decompositions. We also prove several general theorems that can be applied to obtain bounds on the efficiencies for VLSI decompositions of other complex graphs. In general, the results presented in this thesis are useful for implementing massively parallel computers.
|Item Type:||Thesis (Dissertation (Ph.D.))|
|Degree Grantor:||California Institute of Technology|
|Division:||Engineering and Applied Science|
|Major Option:||Electrical Engineering|
|Thesis Availability:||Restricted to Caltech community only|
|Defense Date:||3 August 1992|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||31 Aug 2007|
|Last Modified:||26 Dec 2012 02:58|
- Final Version
Restricted to Caltech community only
See Usage Policy.
Repository Staff Only: item control page