New techniques are presented for routing L-shaped channels, switchboxes and staircases in 2-layer Manhattan-diagonal (MD) model with tracks in horizontal, vertical and /spl plusmn/45/spl deg/ directions. First, a simple O(l.d) time algorithm is proposed which routes any L-shaped channel with length l, density d and no cyclic vertical constraints, in w (d/spl les/w/spl les/d+1) tracks. Next, an O(l.w) time greedy method for routing an L-shaped channel with cyclic vertical constraints, is described. Then, the switchbox routing problem in the MD model is solved elegantly. These techniques, easily extendible to the routing of staircase channels, yield efficient solutions to detailed routing in general floorplans. Experimental results show significantly low via-count and reduced wire length, thus establishing the superiority of MD-routing over classical strategies.
Memristors have shown significant promise both in logic synthesis and memory-subsystem design. A 2D-crossbar of memristors can be used to store multi-valued memory states by utilizing the analog variation of current-induced resistance through memristor cells. The integration of CMOS components with memristor cells can further widen their design space for handling various complex systems. A crossbar built with CMOS-memristor hybridization supports a potential platform that enables computation-in-memory (CIM). In this work we propose a logic system based on differential currents for implementing an ADDER and a MULTIPLIER on a hybrid-memristor crossbar network. Simulation studies demonstrate that the proposed design reduces both memristor cost and computation-cycle time compared to previous approaches.
Random via failure is a major concern for post-fabrication reliability and poor manufacturing yield. A demanding solution to this problem is redundant via insertion during post-routing optimization. It becomes very critical when a multi-layer routing solution already incurs a large number of vias. Very few global routers addressed unconstrained via minimization (UVM) problem, while using minimal pattern routing and layer assignment of nets. It also includes a recent floorplan based early global routability assessment tool STAIRoute \cite{karb2}.
This work addresses an early version of unconstrained via minimization problem during early global routing by identifying a set of minimal bend routing regions in any floorplan, by a new recursive bipartitioning framework. These regions facilitate monotone pattern routing of a set of nets in the floorplan by STAIRoute. The area/number balanced floorplan bipartitionining is a multi-objective optimization problem and known to be NP-hard \cite{majum2}. No existing approaches considered bend minimization as an objective and some of them incurred higher runtime overhead. In this paper, we present a Greedy as well as randomized neighbor search based staircase wave-front propagation methods for obtaining optimal bipartitioning results for minimal bend routing through multiple routing layers, for a balanced trade-off between routability, wirelength and congestion.
Experiments were conducted on MCNC/GSRC floorplanning benchmarks for studying the variation of early via count obtained by STAIRoute for different values of the trade-off parameters ($\gamma, \beta$) in this multi-objective optimization problem, using $8$ metal layers. We studied the impact of ($\gamma, \beta$) values on each of the objectives as well as their linear combination function $Gain$ of these objectives.
System-on-Chips (SoC) are being used to realize multipurpose devices such as mobile phones, consumer electronics which can connect over the internet. The design process including the physical design for an application specific SoC has become more complex due to large number of distinct functional modules. Existing physical design flow usually needs many iterations for successful design closure. In this paper, we propose a uniform wire distribution driven early global routing framework. The goal is to assist in obtaining an optimal routing solution for a given SoC floorplan such that the subsequent stages have fewer iterations. Based on the proposed congestion penalty, hierarchical routing order of the nets and a suitable routing region definition for a given floorplan, our method finds a solution with 100% routing completion, total wirelength within a constant bound of HPWL and no overflow in congestion for a given number of routing layers. We also estimate the number of vias incurred due to an existing minimal bend routing topology and uniform wire distribution for a set of routing layers. Experiments on IBM HB floorplanning benchmarks yield 45% improvement in average congestion with marginal increase in netlength, via count, and runtime for up to 8 layer HV routing. Congestion statistics for the critical routing layers such as M 1 and M 2 also show improvement.
With aggressively shrinking process nodes, physical design methods face severe challenges due to poor convergence and uncertainty in getting an optimal solution. An early detection of potential failures is thus mandated. This has encouraged to devise a feedback mechanism from a lower abstraction level of the design flow to the higher ones, such as placement driven synthesis, routability (timing) driven placement etc. Motivated by this, we propose an early global routing framework using pattern routing following the floorplanning stage. We assess feasibility of a floorplan topology of a given design by estimating routability, routed wirelength and vias count while addressing the global congestion scenario across the layout. Different capacity profiles for the routing regions, such as uniform or non-uniform different cases of metal pitch variation across the metals layers ensures adaptability to technology scaling. The proposed algorithm STAIRoute takes $O(n^2kt)$ time for a given design with $n$ blocks and $k$ nets having at most $t$ terminals. Experimental results on a set of floorplanning benchmark circuits show $100\%$ routing completion, with no over-congestion in the routing regions reported. The wirelength for the $t$-terminal ($t\geq$ 2) nets is comparable with the Steiner length computed by FLUTE. An estimation on the number of vias for different capacity profiles is also presented, along with congestion and runtime results.
Fossils undergo atypical taphonomic and diagenetic deformations while they are being formed. The internal structure of such deformities requires deep and thorough paleontological investigation, and hence demands a reliable digital reconstruction. However, non-destructive study of fossils using conventional medical imaging fails to preserve the internal tissue structure and suffers from slow computation. This has motivated us to pick up this maiden problem and come up with an efficient technique that can digitally reconstruct a fossil from a sequence of 2D micro computerized tomographic scan (micro-CT) slices. The proposed technique is marked with a couple of novel concepts. First, the components on each slice are represented by their encoded boundaries, which are smoothed to get rid of their jagged nature. For this, the notion of majority code is introduced, followed by bilinear interpolation to make up the inter-slice gaps. Second, for various tasks such as intersection, cutting, joining, and the like, we consider the thinnest digital plane. The reconstructed volume being a well-defined set of voxels, admits quick operations with such planes, thereby expediting the procedure invoked by the user. Furthermore, as the surface of the reconstructed volume is well-formed, the marching cube method can easily be used for 3D mesh creation and for visualization. The reconstruction algorithm runs in a time linear in the number of slices and is found to have 98% accuracy in reconstruction with preservation of both bone and tissue structures, as validated by professional paleontologists.
In nanometer-scale integrated circuits, simultaneous switching at gates in physical proximity may induce power supply droop, and thereby invoke timing faults, termed as droop faults. During at-speed testing of such chips, two test vectors in a test sequence may excite droop and, thus, cause test invalidation. Fast application of test vectors may be needed for high-speed testing or for built-in self-test systems. The occurrence of droop strongly depends on the sequence of test vectors applied. The effect of droop on fast testing of stuck-at faults is investigated. For combinational circuits, the droop sensitivity of a given test sequence is studied and a method of re-ordering to reduce this effect is proposed. Experimental results on benchmark circuits show that the increase in test length to achieve droop-insensitive re-ordering is low. Droop excitability in full-scan sequential circuits is also studied.
Quantum Boolean circuit synthesis issues are becoming a key area of research in the domain of quantum computing. For gate-level synthesis, minterm based and Reed- Muller canonical decomposition techniques are adopted as common approaches. Physical implementation of quantum circuits have inherent constraints and hence nearest neighbour template of input lines is gaining importance. In this work, we present a brief analysis of the various Fixed Polarity Reed Muller (FPRM) expressions for a given quantum Boolean circuit and also introduce the rules for the nearest neighbour template-based synthesis of these forms. The corresponding circuit costs are evaluated.
'%3e%3ccircle r='20' fill='%23008'/%3e%3ccircle r='17.5' fill='%23fff'/%3e%3ccircle r='3.5' fill='%23008'/%3e%3cg id='d'%3e%3cg id='c'%3e%3cg id='b'%3e%3cg id='a' fill='%23008'%3e%3ccircle r='.875' transform='rotate(7.5 -8.75 133.5)'/%3e%3cpath d='M0 17.5.6 7 0 2l-.6 5L0 17.5z'/%3e%3c/g%3e%3cuse xlink:href='%23a' transform='rotate(15)'/%3e%3c/g%3e%3cuse xlink:href='%23b' transform='rotate(30)'/%3e%3c/g%3e%3cuse xlink:href='%23c' transform='rotate(60)'/%3e%3c/g%3e%3cuse xlink:href='%23d' transform='rotate(120)'/%3e%3cuse xlink:href='%23d' transform='rotate(-120)'/%3e%3c/g%3e%3c/svg%3e)