Type of Document	Master's Thesis
Author	Rengan, Divya
Author's Email Address	drenga1@lsu.edu
URN	etd-11172006-113518
Title	Mapping a Weak Hypercube on an Optical Slab Waveguide
Degree	Master of Science in Electrical Engineering (M.S.E.E.)
Department	Electrical & Computer Engineering
Advisory Committee	Advisor Name Title R. Vaidyanathan Committee Chair Ahmed A. El-Amawy Committee Member Jerry Trahan Committee Member
Keywords	Hypercube Slab Waveguide Standard Mapping Weak Communication
Date of Defense	2006-11-14
Availability	unrestricted
Abstract The communication fabric of a parallel processing system is represented as a directed graph. In a weak topology a processor uses at most one incoming edge or one outgoing edge for communication at any given point in time. Currently, the data rate that can be supported on electronic interconnects is reaching its limits. Optical interconnects have been identified as one of the most promising approaches to the growing demands for today's systems. The “medium bandwidth” of an optical waveguide is huge (order of petabits per second for a 1mm2 cross-section optical slab). The challenge lies in utilizing as much of this medium bandwidth as possible. We address this problem by exploiting knowledge of the communication patterns. Key to our approach is a method to map communications to optical channels. This thesis deals with the mapping of a d-dimensional weak hypercube on to an optical slab waveguide. The weak topology helps reduce the cost of optical components used by allowing component reuse across different channels. We present two mappings, the dense and sparse mappings. The dense mapping for a d-dimensional weak hypercube packs all communication channels into a d X 2d array of optical channels and uses (d-2)2d+4 lasers and 2d detectors (or vice-versa). The sparse mapping uses a 2d-1X 2d channel array, but does not use all channels to map hypercube edges. We show that this mapping requires 2d lasers and 2d detectors. We also define a supergraph of the hypercube, called the extended hypercube, that maximally utilizes the empty channels in a sparse mapping. We establish that the extended hypercube is the largest supergraph of the hypercube that utilizes all available channels, without increasing the number of lasers and detectors used. The mappings defined for both these sparse cases are optimal. They use N lasers and N detectors, where N is the number of nodes in the topology. We also derive lower bounds on the number of lasers and detectors needed for a “standard" mapping of a hypercube to an optical slab waveguide. We show that the costs of all the dense and sparse mappings proposed in this thesis match these lower bounds.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    Rengan_Thesis.pdf 475.95 Kb 00:02:12 00:01:07 00:00:59 00:00:29 00:00:02