Multiple frameworks and optimizations have been proposed for accelerating Graph Neural Network (GNN) workloads over the years, achieving sizable runtime performance improvements. However, we notice that existing systems usually explore optimizing either at the intra-operator level or at the inter-operator level, missing synergies that exist due to their compositions. Further, most existing works focus primarily on optimizing the forward computation of GNNs, often overlooking opportunities for training-specific optimizations. To exploit these missed optimization opportunities, we introduce GALA, a domain-specific language (DSL) and a compiler that allows composing optimizations at different levels. The GALA DSL exposes intra-operator transformations as scheduling commands, while we introduce novel inter-operator transformations as part of the compiler. The composition of these transformations is made possible through the introduction of two novel intermediate representations (IR) in the GALA compiler that tracks and composes transformations at both the intra- and inter-operator levels. Further, the IRs maintain a global view of the GNN program, including its training process. This allows us to introduce training-specific transformations to aggressively optimize GNN training. Our evaluations show that GALA achieves a geo-mean speedup of 2.55× for inference and 2.52× for training across multiple systems, graphs, and GNN models. We also show that GALA performs well across different graph sizes and GNN model configurations, as well as allows users to explore different methods of performing similar optimizations leading to different tradeoff spaces.

Clock distribution networks have traditionally been optimized to minimize end-to-end delay of the distribution network. However, since most digital ICs have an on-chip PLL, a more relevant design goal is to minimize cycle-to-cycle jitter. In this paper, we present a novel low-jitter phase-locked clock generation and distribution methodology which uses resonant standing wave oscillators (SWOs). In contrast to traveling wave oscillator rings (TWOs or “rotary” clocks), our SWO achieves the same phase at every point in the ring, making it amenable to a synchronous design methodology. The standing wave oscillator is controlled by coarse as well as fine tuning. Coarse tuning is achieved by varying the ring inductance, while fine tuning is accomplished by varying the ring capacitance. Clock distribution is done by routing the resonant ring chip-wide in a “comb” like manner. Experimental results demonstrate that the cycle-to-cycle jitter and skew of our approach is dramatically lower than existing schemes, while the power consumption is significantly lower as well. These benefits occur due to the resonant nature of our SWO-based clock generation and distribution approach.

We have newly introduced the expert designer/user session (EDS) to ISPD in 2013, which is tailor-made for designers and users of physical design (PD) tools. Since ISPD is the premium PD-centric symposium, it is a great opportunity for designers, tools developers and PD researchers to interact and learn from each other. The benefit of including EDS in ISPD's program is twofold.

Leakage power currently comprises a large fraction of the total power consumption of an IC. Techniques to minimize leakage have been researched widely. However, most approaches to reducing leakage have an associated performance penalty. In this article, we present an approach which minimizes leakage by simultaneously modifying the circuit while deriving the input vector that minimizes leakage. In our approach, we selectively modify a gate so that its output (in sleep mode) is in a state which helps minimize the leakage of other gates in its transitive fanout. Gate replacement is performed in a slack-aware manner, to minimize the resulting delay penalty. One of the major advantages of our technique is that we achieve a significant reduction in leakage without increasing the delay of the circuit.

In this paper, we present a novel circuit design approach for radiation hardened digital electronics. Our approach is based on the use of shadow gates, whose task it is to protect the primary gate in case it is struck by a heavy cosmic ion. We locally duplicate the gate to be protected, and connect a pair of diode-connected transistors (or diodes) between the outputs of the original and shadow gates. These transistors turn on when the voltages of the two gates deviate during a radiation strike. Our experiments show that at the level of a single gate, our circuit structure has a delay overhead about 1.76% on average, and an area overhead of 277%. At the circuit level, however, we do not need to protect all gates. We present a methodology to selectively protect specific gates of the circuit in a manner that guarantees radiation tolerance for the entire circuit. With this methodology, we demonstrate that at the circuit level, the average delay overhead is about 3% and the average placed-and-routed area overhead is 28%, compared to an unprotected circuit (for delay mapped designs). We also propose an improved circuit protection algorithm to reduce the area overhead associated with our approach. With this approach for circuit protection, the area and delay overheads are further lowered.

The realization of functions such as log() and antilog() in hardware is of considerable relevance, due to their importance in several computing applications. In this paper, we present an approach to compute log() and antilog() in hardware. Our approach is based on a table lookup, followed by an interpolation step. The interpolation step is implemented in combinational logic, in a field-programmable gate array (FPGA), resulting in an area-efficient, fast design. The novelty of our approach lies in the fact that we perform interpolation efficiently, without the need to perform multiplication or division, and our method performs both the log() and antilog() operation using the same hardware architecture. We compare our work with existing methods, and show that our approach results in significantly lower memory resource utilization, for the same approximation errors. Also our method scales very well with an increase in the required accuracy, compared to existing techniques.

In a typical clock distribution scheme, a central clock signal is distributed to several sites on the integrated circuit (IC). Local regenerators at these sites buffer the clock signal for the logic in regions close to the regenerator. Minimizing the skew between the clocks at these regeneration sites is critical. In recent times, this is becoming harder due to increasing intra-die processing variations. In this paper, we describe a novel technique to distribute a clock signal from a central location to several sites on a VLSI IC. Our technique uses a buffered H-tree and includes circuitry to dynamically remove any skew that may result due to intra-die processing variations. While existing approaches to deskewing a clock tree have utilized several phase detection circuits (number of phase detectors dependent on the number of clock regenerators), our method requires only one phase detector. Also, in our approach, the resolution of the phase detector is inconsequential unlike existing techniques. Our deskewing technique can be applied dynamically, either at boot time or periodically during the operation of the IC. Using a six-level H-tree clock distribution network with process variations deliberately included, we demonstrate that our technique can reduce skews as high as 300 ps down to just 3 ps. We compare our clock tree with traditional buffered and unbuffered H-tree networks.

Leakage power currently comprises a large fraction of the total power consumption of an IC. Techniques to minimize leakage have been researched widely. In this paper, the authors present an approach which minimizes leakage by simultaneously modifying the circuit while deriving the input vector that minimizes leakage. In this approach, the authors selectively modify a gate so that its output (in sleep mode) is in a state which helps minimize the leakage of other gates in its transitive fanout. Gate replacement is performed in a slack-aware manner, to minimize the resulting delay penalty

In this paper, we describe a structured ASIC design methodology which utilizes a regular, pre-fabricated array of pass transistor logic based if-then-else (ITE) cells as the building block for the circuit. Given a logic netlist, we first construct reduced order binary decision diagrams (ROBDDs) for the circuit in a partitioned manner, thereby allowing the approach to handle large designs. We place the ITE cells corresponding to the ROBDD nodes in a manner that minimizes crossings in the ROBDD graph. Our placement also effectively 'folds' the ITE cells of different variables into a single row, so as to obtain a layout with a more uniform distribution of ITE cells along each physical row of ITE cells. The design methodology has been demonstrated to implement sequential as well as combinational designs, by customizing the lowest 4 METAL layers along with their associated VIA layers. A low area and delay overhead is achieved, in comparison with an ASIC approach. In particular, the average delay (area) overhead is 1.5 times (3.41 times) for combinational designs and 2 times (6 times) for sequential designs

In this paper, we describe a new low-leakage standard cell based application-specific integrated circuit (ASIC) design methodology. This design is based on the use of modified standard cells, designed to reduce leakage currents (by almost two orders of magnitude) in standby mode and also allow precise estimation of leakage current. For each cell in a standard cell library, two low-leakage variants of the cell are designed. If the inputs of a cell during the standby mode of operation are such that the output has a high value, we minimize the leakage in the pull-down network, and similarly we minimize leakage in the pull-up network if the output has a low value. In this manner, two low-leakage variants of each standard cell are obtained. While technology mapping a circuit, we determine the particular variant to utilize in each instance, so as to minimize leakage of the final mapped design. We have performed experiments to compare placed-and-routed area, leakage and delays of this new methodology against Multithreshold CMOS (MTCMOS) and a regular standard cell based design style. The results show that our new methodology (which we call the "HL" methodology) has better speed and area characteristics than MTCMOS implementations. The leakage current for HL designs can be dramatically lower than the worst-case leakage of MTCMOS based designs, and two orders of magnitude lower than the leakage of traditional standard cells. An ASIC design implemented in MTCMOS would require the use of separate power and ground supplies for latches and combinational logic, while our methodology does away with such a requirement. Another advantage of our methodology is that the leakage is precisely estimable, in contrast with MTCMOS. Our primary contribution in this paper is a new low leakage design style for static CMOS designs. In addition, we also discuss techniques to reduce leakage in dynamic (domino logic) designs

sunilkhatri at tamu.edu In this paper, we present a novel circuit design approach for radiation hardened digital electronics. Our approach is based on the use of shadow gates, whose task it is to protect the primary gate in case it is struck by a heavy cosmic ion. We locally duplicate the gate to be protected, and connect a pair of transistors (or diodes) between the outputs of the original and shadow gates. These transistors turn on when the voltages of the two gates deviate during a radiation strike. Our experiments show that at the level of a single gate, our circuit structure has a delay overhead of about 4% on average, and an area overhead of over 100%. At the circuit level, however, we do not need to protect all gates. We present a methodology to selectively protect specific gates of the circuit in a manner that guarantees radiation tolerance for the entire circuit. With this methodology, we demonstrate that at the circuit level, the delay overhead is about 4 % and the placed-and-routed area overhead is 30%, compared to an unprotected circuit (for delay mapped designs)

Power consumption is a dominant issue in contemporary circuit design. Sub-threshold circuit design is an appealing means to dramatically reduce this power consumption. However, sub-threshold designs suffer from the drawback of being significantly slower than traditional designs. To reduce the speed gap between sub-threshold and traditional designs, we propose a sub-threshold circuit design approach based on asynchronous micropipelining of a levelized network of PLAs. We describe the handshaking protocol, circuit design and logic synthesis issues in this context. Our preliminary results demonstrate that by using our approach, a design can be sped up by about 7x, with an area penalty of 47%. Further, our approach yields an energy improvement of about 4x, compared to a traditional network of PLA design. Our approach is quite general, and can be applied to traditional circuits as well.

This paper presents a design flow that optimizes a standard cell based circuit for performance by implementing critical paths in a Programmable Logic Array (PLA). Given a standard-cell based circuit as input, our approach iteratively extracts critical paths from this circuit, which are then implemented using a PLA circuit. PLAs are a good candidate for such an approach, since they exhibit a gradual increase in delay as additional vectors are added. In subsequent iterations, these critical paths are treated as don't cares, allowing the standard cell based design to be simplified after each iteration. The final design consists of a portion which is implemented using a PLA, and another portion which is implemented using standard cells. We demonstrate that on average, our approach can achieve about 22.5% improvement in the SPICE based delay of a design, along with a placed-and-routed area improvement of 11%.

This paper presents a VLSI implementation of a Low-Density Parity Check (LDPC) decoder that achieves 2.4 Gbps throughput yet permits real-time configuration of (1) rate, (2) code length, and (3) the parity equations. This decoder can be programmed in the field, much like an FPGA. We describe the architectural, circuit-level and layout-level details of our implementation. Our design can handle variable rate codes of length up to 1024, and is implemented in a 0.1 μm VLSI fabrication process. Our design has a die size of 12mm by 8mm and a power consumption of 7W. This implementation can extended to handle longer codes in a partially parallel manner, and allow for on-the-fly modification of the code.

With the standard approach for establishing multicast connections over a network, network nodes are utilized to forward and duplicate the packets received over the incoming links. Recently, there has been a significant interest in a novel paradigm of network coding. Network coding generalizes the traditional routing approach by allowing the network nodes to generate new packets by performing algebraic operations on packets received over the incoming links. It has been shown that network coding can increase the throughput of multicast communication. In this paper, we explore the benefits of network coding for improving the routing characteristics of VLSI designs. We demonstrate that when data has to be routed across the IC, it is often beneficial to perform network coding. Initial results demonstrate that network coding can result in a healthy reduction in wire length, wire area, interconnect power as well as the active area associated with the interconnects. This comes at a small delay penalty.

As the minimum feature sizes of VLSI fabrication processes continue to shrink, the impact of process variations is becoming increasingly significant. This has prompted research into extending traditional static timing analysis so that it can be performed statistically. However, statistical static timing analysis (SSTA) tends to be quite pessimistic. In this paper we present a sensitizable statistical timing analysis (StatSense) technique to overcome the pessimism of SSTA. Our StatSense approach implicitly eliminates false paths, and also uses different delay distributions for different input transitions for any gate. These features enable our StatSense approach to perform less conservative timing analysis than the SSTA approach. Our results show that on average, the worst case (mu + 3sigma) circuit delay reported by StatSense is about 20% lower than that reported by SSTA.

"Parking" a circuit in a minimum leakage state during its standby mode of operation is one of the techniques of reducing leakage power consumption in a circuit. However, the problem of finding this minimum leakage state is NP-hard. In this paper, we present a heuristic approach to determine the input vector which minimizes leakage for a combinational design. Our approach utilizes approximate signal probabilities of internal nodes to aid in finding the minimum leakage vector. We use a probabilistic heuristic to select the next gate to be processed, as well as to select the best state of the selected gate. A fast SAT solver is employed to ensure the consistency of the assignments that are made in this process. Experimental results indicate that our method has very low run-times, with excellent accuracy, compared to existing approaches

Reverse body biasing (RBB) is often used to reduce the leakage power of a device. However, recent research has shown that if this applied RBB is too high, the leakage power can actually increase due to the contribution of Band-to-Band Tunneling (BTBT) currents. Hence, there exists an optimal RBB value at which the leakage is minimum. This optimum point can vary with temperature and process variations. In this paper we show that it is desirable to operate at the optimal RBB point which minimizes total leakage. We present a scheme that monitors the total leakage current (the sum of the sub-threshold, BTBT and gate leakage) of an IC with a representative leaking device and, using this monitored value, automatically finds the optimum RBB value across temperature and process corners, using a self-adjusting circuit. Our approach has a modest placed-and-routed area utilization, and a low power consumption.

Due to their extreme low power consumption, sub-threshold design approaches are appealing for a widening class of applications which demand low power consumption and can tolerate larger circuit delays. However, sub-threshold circuits are extremely sensitive to variations in supply, temperature and processing factors. In this paper, we present a sub-threshold design methodology which dynamically self-adjusts for inter and intra-die process, supply voltage and temperature (PVT) variations. This adjustment is achieved by performing bulk voltage adjustments in a closed-loop fashion, using a charge pump and a phase-detector.

Clock skew is becoming increasingly difficult to control due to variations. Link based non-tree clock distribution is a cost-effective technique for reducing clock skew variations. However, previous works based on this technique were limited to unbuffered clock networks and neglected spatial correlations in the experimental validation. In this work, we overcome these shortcomings and make the link based non-tree approach feasible for realistic designs. The short circuit risk and multi-driver delay issues in buffered non-tree clock networks are investigated. Our approach is validated with SPICE based Monte Carlo simulations, considering spatial correlations among variations. The experimental results show that our approach can reduce the maximal skew by 47%, improve the skew yield from 15% to 73% on average with a decrease on the total wire and buffer capacitance.

In deep sub-micron (DSM) technologies, wire delays comprise a dominant fraction of the total delay of a design. As a consequence, routing techniques which reduce the total wire length of a design are highly relevant to such technologies. One such approach which holds promise is that of non-Manhattan routing (or X routing). In this paper, we describe a technique to perform non-Manhattan routing by combining the results of two related Manhattan routing instances. The first is a regular, unrotated routing instance. The second routing instance is derived from the first by rotating the coordinate system by 45/spl deg/. Both instances are routed on the same pair of metal layers. By selectively combining the results of the two instances, we obtain a final routing result that contains non-Manhattan wire segments. Our approach utilizes a powerful Floyd-Warshall based engine to combine the results of the two instances. We demonstrate that our router produces highly efficient results, reducing the total wire length by an average of about 20% (31%) over the unrotated (rotated) results, with a via-count decrease of between 4% (43%).

In recent times, there has been a significant growth in applications for battery powered portable electronics, as well as low power sensor networks. While sub-threshold circuit design approaches can reduce the power consumption significantly, a design operating at sub-threshold voltages is not necessarily optimal in terms of energy consumption. In this paper, we describe a technique to find the energy optimum VDD value for a design, and show that for minimum energy consumption, the circuit should be operated at VDD values which are above the NMOS threshold voltage value. We study this problem in the context of designing a circuit using a network of dynamic NOR-NOR PLAs.

In this paper, we present an Algebraic Decision Diagram (ADD) based approach to determine and implicitly represent the leakage value for all input vectors of a combinational circuit. In its exact form, our technique can compute the leakage value of each input vector. To broaden the applicability of our technique, we present an approximate version of our algorithm as well. The approximation is done by limiting the total number of discriminant nodes in any ADD. Previous sleep vector computation techniques can find either the maximum or minimum sleep vector. Our technique computes the leakages for all vectors, storing them implicitly in an ADD structure. We experimentally demonstrate that these approximate techniques produce results which have reasonable errors. We also show that limiting the number of discriminants to a value between 12 and 16 is practical, allowing for good accuracy and lowered memory utilization

In this paper, an efficient, fully-parallel network of programmable logic array (NPLA)-based realization of iterative decoders for structured LDPC codes is presented. The LDPC codes are developed in tandem with the underlying VLSI implementation technique, without compromising chip design constraints. The codes are based on a novel modification of array codes. This design methodology results in reduced routing congestion, a major problem in prior approaches. The operating power, delay and chip-size of the circuits are estimated, indicating that this implementation significantly outperforms presently used standard-cell based architectures. The described LDPC design method can accommodate widely different requirements, such as those arising from recording and wireless channel applications.

In recent times there has been a substantial increase in the cost and complexity of fabricating a VLSI chip. The lithography masks themselves can cost between /spl epsi/ and /spl ges/. It is conjectured that due to these increasing costs, the number of ASIC starts in the last few years has declined. We address this problem by using an array of dynamic PLAs which require only metal and via mask customization in order to implement a new design. This would allow several similar-sized designs to share the same base set of masks (right up to the metal layers) and only have different metal and via masks. We have implemented our methodology for both combinational and sequential designs, and demonstrate that our approach strikes a reasonable compromise between ASIC and field programmable design methodologies in terms of placed-and-routed area and delay. Our method has a 2.89/spl times/ (3.58/spl times/) delay overhead and a 4.96/spl times/ (3.44/spl times/) area overhead compared to standard cells for combinational (sequential) designs.

In present day VLSI ICs, intra-die processing variations are becoming harder to control, resulting in a large skew in the clock signals at the end of the clock distribution network. We describe a buffered H-tree technique to distribute the clock signal and to de-skew a clock network. The clock shielding wires (which are connected to GND in normal operation) are, in de-skewing mode, used to selectively return the clock signal for de-skewing, and for serial communication with the clock distribution sites for skew adjustment. Our forward and return clock networks are buffered, with identically sized and co-located wires and buffers. This results in both these networks exhibiting identical delay characteristics in the presence of intra-die process variations. Unlike existing approaches, our method utilizes a single phase detection circuit, and can achieve a very low maximum chip-level clock skew. This skew value is not dependent on the resolution of the phase detector. Further, our technique can be applied dynamically, either at boot time or periodically during the operation of the IC, as necessary. Additionally, our buffered H-tree enables us to implement efficient clock gating by allowing the user to turn off clocks in the distribution network itself, thus disabling entire sections of the clock network. We demonstrate the utility of our technique on a 6-level H-tree clock distribution network. In a clock distribution network which is initially skewed by up to 300ps, our technique can de-skew signals to within 4ps of each other. We show that the total wiring area of our clock distribution and de-skewing methodology is about 35% higher than a traditional H-tree (which does not have a deskewing functionality), while the active logic area overhead is about 25%. The power consumption of our network is 5% lower than that of a traditional H-tree network with no de-skewing functionality.

Coverage estimation for model checking quantifies the completeness of a set of properties. We present an improved version of the algorithm of Hoskote et al. [7] that applies to a larger subset of CTL; we prove properties of the algorithm and apply it to three case studies. From these case studies we derive recommendations for an effective use of coverage estimation.

In this paper we introduce a low-leakage standard cell based ASIC design methodology which is based on the use of modified standard cells. These cells are designed to consume extremely low and predictable leakage currents in standby mode. For each cell in a standard cell library, we design two low-leakage variants of the cell. If the inputs of a cell during the standby mode of operation are such that the output has a high value, we minimize the leakage in the pull-down network, and vice versa. While technology mapping a circuit, we determine the particular variant to utilize in each instance, so as to minimize leakage of the final mapped design.We have designed and laid out our modified standard cells, and have performed experiments to compare placed-and-routed area, leakage and delays of our method against MTCMOS and a straightforward ASIC flow. Each design style we compare utilizes the same base standard cell library.Our results show that designs obtained using our methodology have better speed and area characteristics than designs implemented in MTCMOS. The exact leakage current obtained for MTCMOS is highly unpredictable, while our method exhibits leakage currents which are precisely estimable. The leakage current for HL designs can be dramatically lower than the worst-case leakage of MTCMOS based designs, and two orders of magnitude compared to traditional standard cells. Also, a design implemented in MTCMOS would require the use of separate power and ground supplies for latches and combinational logic, while our methodology does away with such a requirement.