Search

Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, we identify a second important measure of difficulty, which we call flux. We show that flux, like density, is a lower bound on channel width. In addition, we present a linear-time algorithm which routes any multipoint net Manhattan routing problem with density d and flux f in a channel of width 2d+O(f). (For 2-point net, the bound is d+O(f).) Thus we show that Manhattan routing is one of the NP-complete problems for which there is a provably good approximation algorithm.

This thesis is motivated by the need for a clearer understanding of various issues in VLSI layout. Within a formal setting, we identify critical properties of circuits that determine the quality of their layouts.

This paper introduces a new divide-and-conquer framework for VLSI graph layout. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configuration layouts, to assemble large networks of processors using restructurable chips, and to configure networks around faulty processors. it is also shown how good graph partitioning heuristics may be used to develop a provably good layout strategy.

Many researchers have proposed that ensembles of processing elements be organized as trees. This paper explores how large tree machines can be assembled efficiently from smaller components. A principal constraint considered is the limited number of external connections from an integrated circuit chip. We also explore the emerging capabilities of restructurable VLSI which allows a chip to be customized after fabrication. We give a linear-area chip of m processors and only four off-chip connections which can be used as the sole building block to construct an arbirtarily large complete binary tree. We also present a restructurable linear-areas layout of m processors with O(lg m) pins that can realize an arbitrary binary tree of any size. This layout is based on a solution to the graph-theoretic problem: Given a tree in which each vertex is either black or white, determine how many edges need to be cut in order to bisect the tree into equal-size components, each containing exactly half the black and half the white vertices. These ideas extend to more general graphs using separator theoerems and bifurcators.

This thesis deals with the structural complexity of swicthing networks which realize concentration and connection requests when operated in a rearrangeable or incremental manner. Some of the important results and constructions are briefly reviewed. On the basis of non-constructive proof techniques used to obtain linear upper bounds on the complexity of rearrangeable concentrators, it is shown that not only are certain random graphs very likely to be rearrangeably non-blocking concentrators, but that is a randomly constructed graph is not non-blocking, then, on the average, only a constant number of edges need by added to the graph to make it non-blocking. Although the problem of recognizing non-blocking networks appears to be a computationally hard problem, the extra edges may be added to the graph efficiently, during operation of the network. Finally, we obtain a constructive as well as an improved non-constructive upper bound on the complexity of incrementally non-blocking connection networks.

Remote sensing techniques are effectively used for measuring the overall loss of terrestrial ecosystem productivity and biodiversity due to forest fires. The current research focuses on assessing the impacts of forest fires on terrestrial ecosystem productivity in India during 2003–2017. Spatiotemporal changes of satellite remote sensing derived burn indices were estimated for both fire and normal years to analyze the association between forest fires and ecosystem productivity. Two Light Use Efficiency (LUE) models were used to quantify the terrestrial Net Primary Productivity (NPP) of the forest ecosystem using the open-source and freely available remotely sensed data. A novel approach (delta NPP/delta burn indices) is developed to quantify the effects of forest fires on terrestrial carbon emission and ecosystem production. During 2003–2017, the forest fire intensity was found to be very high (>2000) across the eastern Himalayan hilly region, which is mostly covered by dense forest and thereby highly susceptible to wildfires. Scattered patches of intense forest fires were also detected in the lower Himalayan and central Indian states. The spatial correlation between the burn indices and NPP were mainly negative (−0.01 to −0.89) for the fire-prone states as compared to the other neighbouring regions. Additionally, the linear approximation between the burn indices and NPP showed a positive relation (0.01 to 0.63), suggesting a moderate to high impact of the forest fires on the ecosystem production and terrestrial carbon emission. The present approach has the potential to quantify the loss of ecosystem productivity due to forest fires.