On the VLSI decompositions for complete graphs, DeBruijn graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs

Citation

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. doi:10.7907/s7w7-a995. https://resolver.caltech.edu/CaltechETD:etd-08302007-094049

Abstract

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.

Thesis Files