UMD Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/3
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
2 results
Search Results
Item Random Routing and Concentration in Quantum Switching Networks(2008) Ratan, Rahul; Oruc, Ahmet Y; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Flexible distribution of data in the form of quantum bits or qubits among spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Accordingly, we consider the problem of dynamically permuting groups of quantum bits, i.e., qubit packets, using networks of reconfigurable quantum switches. We demonstrate and then explore the equivalence between the quantum process of creation of packet superpositions and the process of randomly routing packets in the corresponding classical network. In particular, we consider an n × n Baseline network for which we explicitly relate the pairwise input-output routing probabilities in the classical random routing scenario to the probability amplitudes of the individual packet patterns superposed in the quantum output state. We then analyze the effect of using quantum random routing on a classically non-blocking configuration like the Benes network. We prove that for an n × n quantum Benes network, any input packet assignment with no output contention is probabilistically self-routable. In particular, we prove that with random routing on the first (log n-1) stages and bit controlled self-routing on the last log n stages of a quantum Benes network, the output packet pattern corresponding to routing with no blocking is always present in the output quantum state with a non-zero probability. We give a lower bound on the probability of observing such patterns on measurement at the output and identify a class of 2n-1 permutation patterns for which this bound is equal to 1, i.e., for all the permutation patterns in this class the following is true: in every pattern in the quantum output assignment all the valid input packets are present at their correct output addresses. In the second part of this thesis we give the complete design of quantum sparse crossbar concentrators. Sparse crossbar concentrators are rectangular grids of simple 2 × 2 switches or crosspoints, with the switches arranged such that any k inputs can be connected to some k outputs. We give the design of the quantum crosspoints for such concentrators and devise a self-routing method to concentrate quantum packets. Our main result is a rigorous proof that certain crossbar structures, namely, the fat-slim and banded quantum crossbars allow, without blocking, the realization of all concentration patterns with self-routing. In the last part we consider the scenario in which quantum packets are queued at the inputs to an n × n quantum non-blocking switch. We assume that each packet is a superposition of m classical packets. Under the assumption of uniform traffic, i.e., any output is equally likely to be accessed by a packet at an input we find the minimum value of m such that the output quantum state contains at least one packet pattern in which no two packets contend for the same output. Our calculations show that for m=9 the probability of a non-contending output pattern occurring in the quantum output is greater than 0.99 for all n up to 64.Item ON ROUTING AND PERFORMANCE EVALUATION OF BUFFERED SPARSE CROSSBAR CONCENTRATORS(2002-12-10) Ratan, Rahul; Oruc, A. Yavuz; Electrical and Computer Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, MD.)We investigate the routing and performance of sparse crossbar packet concentrators under a buffered network model. The concentration property in packet switching concentrators is defined with respect to packets instead of input/output ports. This allows such concentrators to function as generalized connectors (with some constraints). This altered functionality for a packet concentrator over its circuit switched counterpart translates into differences in performance measures like complexity and delay. A model for constructing sparse crossbar packet switching concentrators with optimal cross point complexity has been introduced in literature. We use this construction to model the performance of a sparse crossbar packet concentrator and relate performance measures to its complexity, connectivity and buffer requirements. In this thesis, we address issues of routing and performance evaluation over such optimal sparse crossbar fabrics, in particular their relation to complexity and buffer requirements. We present an analysis of the packet loss suffered in such concentrators when excess packets are dropped. We go on to analyze the best performance possible when packets are stored and serviced in FIFO order. These results lead us to formulate a routing algorithm which tries to emulate the best case performance on the sparse crossbar. We present theoretical and simulation results for the best case performance and the algorithm. We find that the algorithm is efficient and allows concentration to be done with negligible loss of performance on the sparse crossbar.