More Like this

1. SF-GRASS: solver-free graph spectral sparsification

   https://doi.org/10.1145/3400302.3415629  

   Zhang, Ying; Zhao, Zhiqiang; Feng, Zhuo (November 2020, International Conference on Computer-Aided Design)

   null (Ed.)

   Recent spectral graph sparsification techniques have shown promising performance in accelerating many numerical and graph algorithms, such as iterative methods for solving large sparse matrices, spectral partitioning of undirected graphs, vectorless verification of power/thermal grids, representation learning of large graphs, etc. However, prior spectral graph sparsification methods rely on fast Laplacian matrix solvers that are usually challenging to implement in practice. This work, for the first time, introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing (GSP) techniques. We introduce a local spectral embedding scheme for efficiently identifying spectrally-critical edges that are key to preserving graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. Since the key kernel functions in SF-GRASS can be efficiently implemented using sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is simple to implement and inherently parallel friendly. Our extensive experimental results show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks when compared with prior state-of-the-art spectral methods. 

   more » « less
2. A Zero-Cost Detection Approach for Recycled ICs using Scan Architecture

   https://doi.org/10.1109/VTS48691.2020.9107583  

   Wang, Wendong; Guin, Ujjwal; Singh, Adit (April 2020, 2020 IEEE 38th VLSI Test Symposium (VTS))

   null (Ed.)

   The recycling of used integrated circuits (ICs) has raised serious problems in ensuring the integrity of today's globalized semiconductor supply chain. This poses a serious threat to critical infrastructure due to potentially shorter lifetime, lower reliability, and poorer performance from these counterfeit new chips. Recently, we have proposed a highly effective approach for detecting such chips by exploiting the power-up state of on-chip SRAMs. Due to the symmetry of the memory array layout, an equal number of cells power-up to the 0 and 1 logic states in a new unused SRAM; this ratio gets skewed in time due to uneven NBTI aging from normal usage in the field. Although this solution is very effective in detecting recycled ICs, its applicability is somewhat limited as a large number older designs do not have large on-chip memories. In this paper, we propose an alternate approach based on the initial power-up state of scan flip-flops, which are present in virtually every digital circuit. Since the flip-flops, unlike SRAM cells, are generally not perfectly symmetrical in layout, an equal number of scan cells will not power-up to 0 or 1 logic states in most designs. Consequently, a stable time zero reference of 50% logic 0s and 1s cannot be used for determining the subsequent usage of a chip. To overcome this key limitation, we propose a novel solution in this paper that reliably identifies used ICs from testing the part alone, without the need for any additional reference data or even the netlist of the circuit. Through scan testing of the IC, we first identify a significant number of asymmetrically stressed flip-flops in the design, divided into two groups. One group of flip-flops is selected such that it mostly experiences the 1 logic state during functional operation, while the other group mostly experiences the 0 state. The resulting differential stress during operation causes growing disparity over time in the number of 0s (and 1s) observed in these two groups at power-up. When new and unaged, these two groups behave similarly, with similar percentage of 1s (or 0s). However, over time the differential stress makes these counts diverge. We show that this changing count can be a measure of operational aging. Our simulation results show that it is possible to reliably detect used ICs after as little as three months of operation. 

   more » « less
3. Analyzing the Impact of Electric Vehicles on Power Losses and Voltage Profile in Power Distribution Systems

   Majumdar, Maitreyee; Spencer, Delton; Arefifar, S. A. (April 2022, 2022 WCX™ World Congress Experience - SAE International)

   As the number of electric vehicles (EVs) within society rapidly increase, the concept of maximizing its efficiency within the electric smart grid becomes crucial. This research presents the impacts of integrating EV charging infrastructures within a smart grid through a vehicle to grid (V2G) program. It also observes the circulation of electric charge within the system so that the electric grid does not become exhausted during peak hours. This paper will cover several different case studies and will analyze the best and worst scenarios for the power losses and voltage profiles in the power distribution system. Specifically, we seek to find the optimal location as well as the ideal number of EVs in the distribution system while minimizing its power losses and optimizing its voltage profile. Verification of the results are primarily conducted using GUIs created on MATLAB. These simulations aim to develop a better understanding of the potential impacts of electric vehicles in smart grids, such as power quality and monetary benefits for utility companies and electric vehicle users 

   more » « less
4. Silicon validation of LUT-based logic-locked IP cores

   https://doi.org/10.1145/3489517.3530606  

   Kolhe, Gaurav; Sheaves, Tyler; Gubbi, Kevin Immanuel; Kadale, Tejas; Rafatirad, Setareh; PD, Sai Manoj; Sasan, Avesta; Mahmoodi, Hamid; Homayoun, Houman (July 2022, DAC '22: Proceedings of the 59th ACM/IEEE Design Automation Conference)

   Modern semiconductor manufacturing often leverages a fabless model in which design and fabrication are partitioned. This has led to a large body of work attempting to secure designs sent to an untrusted third party through obfuscation methods. On the other hand, efficient de-obfuscation attacks have been proposed, such as Boolean Satisfiability attacks (SAT attacks). However, there is a lack of frameworks to validate the security and functionality of obfuscated designs. Additionally, unconventional obfuscated design flows, which vary from one obfuscation to another, have been key impending factors in realizing logic locking as a mainstream approach for securing designs. In this work, we address these two issues for Lookup Table-based obfuscation. We study both Volatile and Non-volatile versions of LUT-based obfuscation and develop a framework to validate SAT runtime using machine learning. We can achieve unparallel SAT-resiliency using LUT-based obfuscation while incurring 7% area and less than 1% power overheads. Following this, we discuss and implement a validation flow for obfuscated designs. We then fabricate a chip consisting of several benchmark designs and a RISC-V CPU in TSMC 65nm for post functionality validation. We show that the design flow and SAT-runtime validation can easily integrate LUT-based obfuscation into existing CAD tools while adding minimal verification overhead. Finally, we justify SAT-resilient LUT-based obfuscation as a promising candidate for securing designs. 

   more » « less
5. Incremental topological ordering and cycle detection with predictions

   Mccauley, Samuel; Moseley, Benjamin; Niaparast, Aidin; Singh, Shikha (January 2025, PMLR)

   Salakhutdinov, Ruslan; Kolter, Zico; Heller, Katherine; Weller, Adrian; Oliver, Nuria; Scarlett, Jonathan; Berkenkamp, Felix (Ed.)

   This paper leverages the framework of algorithms-with-predictions to design data structures for two fundamental dynamic graph problems: incremental topological ordering and cycle detection. In these problems, the input is a directed graph on n nodes, and the m edges arrive one by one. The data structure must maintain a topological ordering of the vertices at all times and detect if the newly inserted edge creates a cycle. The theoretically best worst-case algorithms for these problems have high update cost (polynomial in n and m). In practice, greedy heuristics (that recompute the solution from scratch each time) perform well but can have high update cost in the worst case. In this paper, we bridge this gap by leveraging predictions to design a learned new data structure for the problems. Our data structure guarantees consistency, robustness, and smoothness with respect to predictions--that is, it has the best possible running time under perfect predictions, never performs worse than the best-known worst-case methods, and its running time degrades smoothly with the prediction error. Moreover, we demonstrate empirically that predictions, learned from a very small training dataset, are sufficient to provide significant speed-ups on real datasets. 

   more » « less