No description available.

The multi-net Global Routing Problem (GRP) in VLSI physical design is a problem of routing a set of nets subject to limited resources and delay constraints. Various state-of-the-art routers are available but their main focus is to optimize the wire length and minimize the over ow. However optimizing wire length do not necessarily meet timing constraints at the sink nodes. Also, in modern nano-meter scale VLSI process the consideration of process variations is a necessity for ensuring reasonable yield at the fab. In this work, we try to nd a fundamental strategy to address the timing-driven Steiner tree construction (i.e., the routing) problem subject to congestion constraints and process variation. For congestion mitigation, a gradient based concurrent approach (over all nets) of Erzin et. al., rather than the traditional (sequential) rip-and-reroute is adopted in or- der to propagate the timing/delay-driven property of the Steiner tree candidates. The existing sequential rip-up and reroute methods meet the over ow constraint locally but cannot propagate the timing constraint which is non-local in nature. We build on this approach to accommodate the variation-aware statistical delay/timing requirements. To further reduce the congestion, the cost function of the tree generation method is updated by adding history based congestion penalty to the base cost (delay). Iterative use of the timing-driven Steiner tree construction method and history based tree construction procedure generate a diverse pool of candidate Steiner trees for each net. The gradient algorithm picks one tree for each net from the pool of trees such that congestion is e ciently controlled. As the technology scales down, process variation makes process dependent param- eters like resistance, capacitance etc non-deterministic. As a result, Statistical Static Timing Analysis or SSTA has replaced the traditional static timing in nano-meter scale VLSI processes. However, this poses a challenge regarding the max/min-plus algebra of Dijkstra like approximation algorithm that builds the Steiner trees. A new approach based on distance between distributions for nding maximum/minimum at the nodes is presented in this thesis. Under this metric, the approximation algorithm for variation aware timing driven congestion constrained routing is shown to be provably tight and one order of magnitude faster than existing approaches (which are not tight) such as the MVERT. The results (mean value) of our variation aware router are quite close to the mean of the several thousand Monte Carlo simulations of the deterministic router, i.e the results converge in mean. Therefore, instead of running so many deterministic Monte Carlo simulations, we can generate an average design with a probability distribution reasonably close to that of the actual behaviour of the design by running the proposed statistical router only once and at a small fraction of the computational e ort involved in physical design in the nano regime VLSI. The above approximation algorithm is extended to local routing, especially non- Manhattan lambda routing which is increasingly being allowed by the recent VLSI tech- nology nodes. Here also, we can meet delay driven constraints better and keep related wire lengths reasonable.

Ultra Wideband (UWB) communication has recently drawn considerable attention from academia and industry. This is mainly owing to the ultra high speeds and cognitive features it could offer. The employability of UWB in numerous areas including but not limited to Wireless Personal Area Networks, WPAN's, Body Area Networks, BAN's, radar and medical imaging etc. has opened several avenues of research and development. However, still there is a disagreement on the standardization of UWB. Two contesting radios for UWB are Multiband Orthogonal Frequency Division Multiplexing (MB-OFDM) and DS-UWB (Direct Sequence Ultra Wideband). As nearly all of the reported research on UWB hasbeen about a very narrow/specific area of the communication system, this thesis looks at the end-to-end performance of an MB-OFDM approach. The overall aim of this project has been to first focus on three different aspects i.e. interference, antenna and propagation aspects of an MB-OFDM system individually and then present a holistic or an end-to-end system analysis finally. In the first phase of the project the author investigated the performance of MB-OFDM system under the effect of his proposed generic or technology non-specific interference. Avoiding the conventional Gaussian approximation, the author has employed an advanced stochastic method. A total of two approaches have been presented in this phase of the project. The first approach is an indirect one which involves the Moment Generating Functions (MGF's) of the Signal-to-Interference-plus-Noise-Ratio (SINR) and the Probability Density Function (pdf) of the SINR to calculate the Average Probabilities of Error of an MB-OFDM system under the influence of proposed generic interference. This approach assumed a specific two-dimensional Poisson spatial/geometric placement of interferers around the victim MB-OFDM receiver. The second approach is a direct approach and extends the first approach by employing a wider class of generic interference. In the second phase of the work the author designed, simulated, prototyped and tested novel compact monopole planar antennas for UWB application. In this phase of the research, compact antennas for the UWB application are presented. These designs employ low-loss Rogers duroid substrates and are fed by Copla-nar Waveguides. The antennas have a proposed feed-line to the main radiating element transition region. This transition region is formed by a special step-generating function-set called the "Inverse Parabolic Step Sequence" or IPSS. These IPSS-based antennas are simulated, prototyped and then tested in the ane-choic chamber. An empirical approach, aimed to further miniaturize IPSS-based antennas, was also derived in this phase of the project. The empirical approach has been applied to derive the design of a further miniaturized antenna. More-over, an electrical miniaturization limit has been concluded for the IPSS-based antennas. The third phase of the project has investigated the effect of the indoor furnishing on the distribution of the elevation Angle-of-Arrival (AOA) of the rays at the receiver. Previously, constant distributions for the AOA of the rays in the elevation direction had been reported. This phase of the research has proposed that the AOA distribution is not fixed. It is established by the author that the indoor elevation AOA distributions depend on the discrete levels of furnishing. A joint time-angle-furnishing channel model is presented in this research phase. In addition, this phase of the thesis proposes two vectorial or any direction AOA distributions for the UWB indoor environments. Finally, the last phase of this thesis is presented. As stated earlier, the overall aim of the project has been to look at three individual aspects of an MB-OFDM system, initially, and then look at the holistic system, finally. Therefore, this final phase of the research presents an end-to-end MB-OFDM system analysis. The interference analysis of the first phase of the project is revisited to re-calculate the probability of bit error with realistic/measured path loss exponents which have been reported in the existing literature. In this method, Gaussian Quadrature Rule based approximations are computed for the average probability of bit error. Last but not the least, an end-to-end or comprehensive system equation/impulse response is presented. The proposed system equation covers more aspects of an indoor UWB system than reported in the existing literature.