Search

Graph spectral sparsification aims to find a ultra-sparse subgraph which can preserve the spectral properties of the original graph. The subgraph can be leveraged to construct a preconditioner to speed up the solution of the original graph’s Laplacian matrix. In this work, we propose feGRASS, a fast and effective graph spectral sparsification approach for the problem of large-scale power grid analysis and other problems with similar graphs. The proposed approach is based on two novel concepts: 1) effective edge weight and 2) spectral edge similarity. The former takes advantage of node degrees and breadth-first-search (BFS) distances, which leads to a scalable algorithm for generating low-stretch spanning trees (LSSTs). Then, the latter concept is leveraged during the recovery of spectrally-critical off-tree edges to produce spectrally-similar subgraphs. Compared with the most recent competitor feng2019grass, the proposed approach is much faster for producing high-quality spectral sparsifiers. Extensive experimental results have been demonstrated to illustrate the superior efficiency of a preconditioned conjugate gradient (PCG) algorithm based on the proposed approach, for solving large power grid problems and many other real-world graph Laplacians. For instance, a power grid matrix with 60 million unknowns and 260 million nonzeros can be solved (at a 1E-3 accuracy level) within 196 seconds and 12 PCG iterations, on a single CPU core.

We present a novel spectrum-preserving sparsification algorithm for visualizing big graph data. Although spectral methods have many advantages, the high memory and computation costs due to the involved Laplacian eigenvalue problems could immediately hinder their applications in big graph analytics. In this paper, we introduce a practically efficient, nearly-linear time spectral sparsification algorithm for tackling real-world big graph data. Besides spectral sparsification, we further propose a node reduction scheme based on intrinsic spectral graph properties to allow more aggressive, level-of-detail simplification. To enable effective visual exploration of the resulting spectrally sparsified graphs, we implement spectral clustering and edge bundling. Our framework does not depend on a particular graph layout and can be integrated into different graph drawing algorithms. We experiment with publicly available graph data of different sizes and characteristics to demonstrate the efficiency and effectiveness of our approach. To further verify our solution, we quantitatively compare our method against different graph simplification solutions using a proxy quality metric and statistical properties of the graphs.

Autonomous Underwater Helicopter (AUH) is a novel dish-shaped multi-functional submersible vehicle in the autonomous underwater vehicle (AUV) family. Numerical study of launch and recovery system for AUVs from a research vessel is significant in the overall design. Single-arm crane and air-launch way are the important ways of launching AUVs with the high expertise and security. However, AUVs are still easily subject to a huge impact load which can cause the body damage, malfunction of electronic components, and other serious accidents when AUVs are launching into water. In this paper, unsteady, incompressible, two-phase flow with identified boundary conditions was modeled in the computational domain using Volume of Fluid (VOF) technology, and different overset-grid sizes were set and analyzed to ascertain the accuracy of computational fluid dynamics (CFD) simulation first due to the setting of the grid which will directly affect the accuracy of the calculation results, especially the overset-grid convergence validation. Then, the change of water-entry impact force and velocity of AUH with different water-entry velocities and angles were calculated by CFD analysis software STAR-CCM + solver. The proper immersion angle of the AUH should be 75° under comprehensive analysis and comparison. Besides, the variations of pressure distribution of the AUH in the whole water-entry process were also obtained, which provides reference for the shape optimization in the future work.

This paper proposes a scalable multilevel framework for the spectral embedding of large undirected graphs. The proposed method first computes much smaller yet sparse graphs while preserving the key spectral (structural) properties of the original graph, by exploiting a nearly-linear time spectral graph coarsening approach. Then, the resultant spectrally-coarsened graphs are leveraged for the development of much faster algorithms for multilevel spectral graph embedding (clustering) as well as visualization of large data sets. We conducted extensive experiments using a variety of large graphs and datasets and obtained very promising results. For instance, we are able to coarsen the "coPapersCiteseer" graph with 0.43 million nodes and 16 million edges into a much smaller graph with only 13K (32X fewer) nodes and 17K (950X fewer) edges in about 16 seconds; the spectrally-coarsened graphs allow us to achieve up to 1,100X speedup for multilevel spectral graph embedding (clustering) and up to 60X speedup for t-SNE visualization of large data sets.

This work introduces a highly scalable spectral graph densification framework for learning resistor networks with linear measurements, such as node voltages and currents. We prove that given $O(\log N)$ pairs of voltage and current measurements, it is possible to recover ultra-sparse $N$-node resistor networks which can well preserve the effective resistance distances on the graph. Also, the learned graphs preserve the structural (spectral) properties of the original graph, which can potentially be leveraged in many circuit design and optimization tasks. We show that the proposed graph learning approach is equivalent to solving the classical graphical Lasso problems with Laplacian-like precision matrices. Through extensive experiments for a variety of real-world test cases, we show that the proposed approach is highly scalable for learning ultra-sparse resistor networks without sacrificing solution quality., Comment: 2021 ACM/IEEE Design Automation Conference (DAC)

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.

Existing chip thermal analysis and verification methods require detailed distribution of power densities or modeling of underlying input workloads (vectors), which may not always be feasible at early-design stage. This paper introduces the first vectorless thermal integrity verification framework that allows computing worst-case temperature (gradient) distributions across the entire chip under a set of local and global workload (power density) constraints. To address the computational challenges introduced by the large 3D mesh-structured thermal grids, we propose a novel spectral approach for highly-scalable vectorless thermal verification of large chip designs. Our approach is based on emerging spectral graph theory and graph signal processing techniques, which consists of a thermal grid topology sparsification phase, an edge weight scaling phase, as well as a solution refinement procedure. The effectiveness and efficiency of our approach have been demonstrated through extensive experiments.

Spectral graph sparsification aims to find ultra-sparse subgraphs whose Laplacian matrix can well approximate the original Laplacian eigenvalues and eigenvectors. In recent years, spectral sparsification techniques have been extensively studied for accelerating various numerical and graph-related applications. Prior nearly-linear-time spectral sparsification methods first extract low-stretch spanning tree from the original graph to form the backbone of the sparsifier, and then recover small portions of spectrally-critical off-tree edges to the spanning tree to significantly improve the approximation quality. However, it is not clear how many off-tree edges should be recovered for achieving a desired spectral similarity level within the sparsifier. Motivated by recent graph signal processing techniques, this paper proposes a similarity-aware spectral graph sparsification framework that leverages efficient spectral off-tree edge embedding and filtering schemes to construct spectral sparsifiers with guaranteed spectral similarity (relative condition number) level. An iterative graph densification scheme is also introduced to facilitate efficient and effective filtering of off-tree edges for highly ill-conditioned problems. The proposed method has been validated using various kinds of graphs obtained from public domain sparse matrix collections relevant to VLSI CAD, finite element analysis, as well as social and data networks frequently studied in many machine learning and data mining applications. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory., 14 pages, 13 figures. arXiv admin note: substantial text overlap with arXiv:1711.05135

This paper proposes a scalable algorithmic framework for effective-resistance preserving spectral reduction of large undirected graphs. The proposed method allows computing much smaller graphs while preserving the key spectral (structural) properties of the original graph. Our framework is built upon the following three key components: a spectrum-preserving node aggregation and reduction scheme, a spectral graph sparsification framework with iterative edge weight scaling, as well as effective-resistance preserving post-scaling and iterative solution refinement schemes. By leveraging recent similarity-aware spectral sparsification method and graph-theoretic algebraic multigrid (AMG) Laplacian solver, a novel constrained stochastic gradient descent (SGD) optimization approach has been proposed for achieving truly scalable performance (nearly-linear complexity) for spectral graph reduction. We show that the resultant spectrally-reduced graphs can robustly preserve the first few nontrivial eigenvalues and eigenvectors of the original graph Laplacian and thus allow for developing highly-scalable spectral graph partitioning and circuit simulation algorithms.ACM Reference Format:Zhiqiang Zhao and Zhuo Feng. 2019. Effective-Resistance Preserving Spectral Reduction of Graphs. In The 56th Annual Design Automation Conference 2019 (DAC '19), June 2–6, 2019, Las Vegas, NV, USA. ACM, New York, NY, USA, 6 pages. https://doi.org/10.1145/3316781.3317809

On account of complex, dangerous and limited area are urgently explored, an underwater machine which can substitute for people to complete the underwater detection is needed imminently. Autonomous underwater vehicles (AUVs) have been developed to accomplish the tasks of resource exploration in the sea. However, much higher requirements of mobility and maneuverability are of great concern with the accelerated development of AUV. Recently, vectorial thrusters have been applied to ships and offshore platforms, which can increase propulsion efficiency and flexibility. In this paper, a novel small scale AUV with vectorial thrusters is designed, the hydrodynamic performance, pressure distribution, resistance under different angles of attack (AOAs) in vertical plane motion are calculated by Computer Fluid Dynamics (CFD). The numerical simulation suggests the best underwater gesture of the new-type AUV, beyond that the content of this article will provide a basic reference for the further research of motion control.

This paper studies on a new disk-shaped AUV namely “Autonomous Underwater Helicopter” proposed at the Ocean College of Zhejiang University. The reliability of the numerical method is verified by comparison with the experimental data, in which the additional mass of the ellipsoid similar to that of the autonomous underwater helicopter is calculated. Based on the overlapping grid technology of fluid simulation software STAR-CCM+, the hydrodynamic performances of autonomous underwater helicopter in heaving motion and swaying motion are calculated under different inlet velocities and different frequencies, which provides an important references for the subsequent research and design of submarines.

To improve the efficiency of direct solution methods in SPICE-accurate integrated circuit (IC) simulations, preconditioned iterative solution techniques have been widely studied in the past decades. However, it is still an extremely challenging task to develop robust yet efficient general-purpose preconditioning methods that can deal with various types of large-scale IC problems. In this paper, based on recent graph sparsification research we propose circuit-oriented general-purpose support-circuit preconditioning (GPSCP) methods to dramatically improve the sparse matrix solution time and reduce the memory cost during SPICE-accurate IC simulations. By sparsifying the Laplacian matrix extracted from the original circuit network using graph sparsification techniques, general-purpose support circuits can be efficiently leveraged as preconditioners for solving large Jacobian matrices through Krylov-subspace iterations. Additionally, a performance model-guided graph sparsification framework is proposed to help automatically build nearly-optimal GPSCP solvers. Our experiment results for a variety of large-scale IC designs show that the proposed preconditioning techniques can achieve up to $18 {\times }$ runtime speedups and $7 {\times }$ memory reduction in DC and transient simulations when compared to state-of-the-art direct solution methods.

In recent years, spectral graph sparsification techniques that can compute ultra-sparse graph proxies have been extensively studied for accelerating various numerical and graph-related applications. Prior nearly-linear-time spectral sparsification methods first extract low-stretch spanning tree from the original graph to form the backbone of the sparsifier, and then recover small portions of spectrally-critical off-tree edges to the spanning tree to significantly improve the approximation quality. However, it is not clear how many off-tree edges should be recovered for achieving a desired spectral similarity level within the sparsifier. Motivated by recent graph signal processing techniques, this paper proposes a similarity-aware spectral graph sparsification framework that leverages efficient spectral off-tree edge embedding and filtering schemes to construct spectral sparsifiers with guaranteed spectral similarity (relative condition number) level. An iterative graph densification scheme is introduced to facilitate efficient and effective filtering of off-tree edges for highly ill-conditioned problems. The proposed method has been validated using various kinds of graphs obtained from public domain sparse matrix collections relevant to VLSI CAD, finite element analysis, as well as social and data networks frequently studied in many machine learning and data mining applications.

Vectorless integrity verification is becoming increasingly critical to robust design of nanoscale power delivery networks (PDNs). To dramatically improve efficiency and capability of vectorless integrity verifications, this paper introduces a scalable multilevel integrity verification framework by leveraging a hierarchy of almost linear-sized spectral power grid sparsifiers that can well retain effective resistances between nodes, as well as a recent graph-theoretic algebraic multigrid (AMG) algorithmic framework. As a result, vectorless integrity verification solution obtained on coarse level problems can effectively help find the solution of the original problem. Extensive experimental results show that the proposed vectorless verification framework can always efficiently and accurately obtain worst-case scenarios in even very large power grid designs.

Realizable power grid reduction becomes a key to efficient design and verification of nowadays large-scale power delivery networks. Existing state-of-the-art realizable reduction techniques for interconnect circuits, such as the TICER algorithm, cannot be well suited for effective power grid reductions, since reducing the mesh-structured power grids by TICER's nodal elimination scheme may introduce excessive number of new edges in the reduced grids that can be even harder to solve than the original grid due to the drastically increased sparse matrix density. In this paper, we present a novel geometric template-based reduction technique for reducing large-scale flip-chip power grids. Our method first creates geometric template according to the original power grid topology and then performs novel iterative grid corrections to improve the accuracy by matching the electrical behaviors of the reduced template grid with the original grid. In addition, a multilevel grid correction scheme has been proposed to achieve faster convergence during the grid reduction process, which allows for effectively handling very large-scale power grids with millions of parasitics components and thousands of ports. Our experimental results show that the proposed reduction method can reduce industrial power grid designs by up to 95% with a very satisfactory solution quality obtained in dc and transient analysis.

In this paper, we formulate and analyse a long-term multi-objective dynamic model for controlling invasive species. This optimization framework is then applied to the case of buffelgrass control in the Arizona desert. The proposed model simultaneously optimizes three objectives corresponding to three different valued and threatened resources including saguaros (a native cactus species), buildings and vegetation. The model is used to decide the optimal allocation of labour to these resources to control the population of the species in a multi-period planning horizon. The computational method to solve this problem is based on multi-objective integer programming.

Effective thermal management for 3D integrated circuits (3D ICs) is becoming increasingly challenging due to the ever-increasing power density and chip design complexity; traditional heat sinks are expected to quickly reach their limits for meeting the cooling needs of 3D ICs. Alternatively, the integrated liquid-cooled microchannel heat sink has become one of the most effective solutions. In this paper, we present fast multigrid and block tridiagonally preconditioned graphics processing unit (GPU) based thermal simulation algorithms for 3D ICs. Unlike the CPU-based solver development in which existing sophisticated numerical simulation tools (matrix solvers) can be readily adopted and implemented, GPU-based thermal simulation demands more effort in the algorithm and data structure design phase, and requires careful consideration of GPU's thread/memory organization, data access/communication patterns, arithmetic intensity, as well as its hardware occupancies. As shown by various experimental results, our GPU-based 3D thermal simulation solvers can achieve more than 360× speedups over the best available direct solvers and more than 35× speedups over the CPU-based iterative solvers, without loss of accuracy.

With the current aggressive integrated circuit technology scaling, vectorless power grid voltage integrity verification becomes key to designing reliable power delivery networks. To address the challenges of existing vectorless power grid verification methods that suffer from excessively long optimization time and poor scalability to large power grid designs, in this paper, we present a scalable multilevel vectorless power grid verification method which can efficiently tackle very large scale power grid verifications. By taking advantage of a series of coarsest to coarser grid verifications, the finest power grid verification can be accomplished in a more efficient way. To gain good efficiency, global and local “critical regions” for power grid verification are introduced, while power grid structure and electrical properties are exploited to facilitate identifying the worst case voltage drops across the entire chip. The proposed multilevel power grid verification algorithm allows more flexible tradeoffs between verification cost and solution quality, while providing the desired conservative upper/lower bounds for worst case voltage drops. Extensive experimental results show that our approach can efficiently handle very large power grid designs without sacrificing the final power grid verification accuracy. For example, finding the worst voltage drop for a flip-chip power grid design with one million nodes takes less than two hours.

Social media shatters the barrier to communicate anytime anywhere for people of all walks of life. The publicly available, virtually free information in social media poses a new challenge to consumers who have to discern whether a piece of information published in social media is reliable. For example, it can be difficult to understand the motivations behind a statement passed from one user to another, without knowing the person who originated the message. Additionally, false information can be propagated through social media, resulting in embarrassment or irreversible damages. Provenance data associated with a social media statement can help dispel rumors, clarify opinions, and confirm facts. However, provenance data about social media statements is not readily available to users today. Currently, providing this data to users requires changing the social media infrastructure or offering subscription services. Taking advantage of social media features, research in this nascent field spearheads the search for a way to provide provenance data to social media users, thus leveraging social media itself by mining it for the provenance data. Searching for provenance data reveals an interesting problem space requiring the development and application of new metrics in order to provide meaningful provenance data to social media users. This lecture reviews the current research on information provenance, explores exciting research opportunities to address pressing needs, and shows how data mining can enable a social media user to make informed judgements about statements published in social media. Table of Contents: Information Provenance in Social Media / Provenance Attributes / Provenance via Network Information / Provenance Data

TinySPICE was a SPICE simulator on GPU developed to achieve dramatic speedups in statistical simulations of small nonlinear circuits, such as standard cell designs and SRAMs. While TinySPICE can perform circuit simulations much faster than traditional SPICE tools for small circuits, it may not be efficient for handling relatively large logic/memory circuit designs due to the embedded dense MNA matrix solver that can result in fast growing memory cost with increasing matrix size. In this work, we present TinySPICE Plus, a full-blown statistical SPICE simulation engine on GPU platform that integrates a highly-optimized shared-memory based sparse matrix solver that is capable of dealing with much larger circuits than TinySPICE while achieving orders of magnitude speedup over traditional CPU-based SPICE simulation engine. Extensive experimental results show that TinySPICE Plus can achieves over 70X speedups for parametric yield analysis of SRAM arrays and variation-aware logic circuit characterizations.

Since the first peer-reviewed journal appeared in the late 17th century, journals have been the most important platform for scientists to publish articles. Over the last decade, the fast growth of online social networking and media services has brought us numerous valuable data and several applications to track the topic trends in a held and facilitate collaborations between scientists, thus making Web 2.0 and the emerging Web 3.0 as essential as electronic and paper formats for managing scientific journals. In this paper, we propose a working prototype for an intelligent journal system (IJS) for intelligent transportation systems based on the idea of Web 3.0-based next generation of journal systems: IJSs. Some preliminary results are presented to show the validity of our system.

The challenging task of analyzing on-chip power (ground) distribution networks with multimillion node complexity and beyond is key to today's large chip designs. For the first time, we show how to exploit recent massively parallel single-instruction multiple-thread (SIMT)-based graphics processing unit (GPU) platforms to tackle large-scale power grid analysis with promising performance. Several key enablers including GPU-speciflc algorithm design, circuit topology transformation, workload partitioning, performance tuning are embodied in our GPU-accelerated hybrid multigrid (HMD) algorithm (GpuHMD) and its implementation. We also demonstrate that using the HMD solver as a preconditioner, the conjugate gradient solver can converge much faster to the true solution with good robustness. Extensive experiments on industrial and synthetic benchmarks have shown that for DC power grid analysis using one GPU, the proposed simulation engine achieves up to 100× runtime speedup over a state-of-the-art direct solver and more than 50× speedup over the CPU based multigrid implementation, while utilizing a four-core-four-GPU system, a grid with eight million nodes can be solved within about 1 s. It is observed that the proposed approach scales favorably with the circuit complexity, at a rate about 1 s per two million nodes on a single GPU card.

Large VLSI on-chip Power Delivery Networks (PDNs) are challenging to analyze due to the sheer network complexity. In this article, a novel parallel partitioning-based PDN analysis approach is presented. We use the boundary circuit responses of each partition to divide the full grid simulation problem into a set of independent subgrid simulation problems. Instead of solving exact boundary circuit responses, a more efficient scheme is proposed to provide near-exact approximation to the boundary circuit responses by exploiting the spatial locality of the flip-chip-type power grids. This scheme is also used in a block-based iterative error reduction process to achieve fast convergence. Detailed computational cost analysis and performance modeling is carried out to determine the optimal (or near-optimal) number of partitions for parallel implementation. Through the analysis of several large power grids, the proposed approach is shown to have excellent parallel efficiency, fast convergence, and favorable scalability. Our approach can solve a 16-million-node power grid in 18 seconds on an IBM p5-575 processing node with 16 Power5+ processors, which is 18.8X faster than a state-of-the-art direct solver.

Diffusion of biological compounds, including nutrients, oxygen, and chemoattractants, is a common component of biomedical engineering models. Conventional numerical schemes, such as alternating direction implicit (ADI) for diffusion, are frequently the computational bottleneck. Our study employs graphics processing unit (GPU) technology to accelerate the diffusion model simulation. We tailor, implement, analyze, and test several parallel ADI algorithms on the highly parallel computational and data architecture of the GPU. Our study confirms that the proposed algorithms provide fast, high-quality simulation results suitable for inclusion in numerous bioengineering simulations. Copyright © 2011 John Wiley & Sons, Ltd.

Leveraging the power of nowadays graphics processing units for robust power grid simulation remains a challenging task. Existing preconditioned iterative methods that require incomplete matrix factorizations cannot be effectively accelerated on graphics processing unit (GPU) due to its limited hardware resource as well as data parallel computing. This paper presents an efficient GPU-based multigrid preconditioning algorithm for robust power grid analysis. By combining the fast geometric multigrid solver with the robust Krylov-subspace iterative solver, power grid DC and transient analysis can be performed efficiently on GPU without loss of accuracy (largest errors

To better understand the authors and studies in IEEE Intelligent Systems, the authors conducted a bibliographic study on its publications. Specifically, they focus on the most productive and highly cited authors and institutions in IS, the authors and institutions most cited in IS, and the journals and institutions that cited IS articles the most.

This article looks at IEEE Intelligent Systems' 25-year history and studies the evolution of scientific collaboration among IS authors through coauthorship network analysis.

This first comprehensive empirical study of a search function that originated in China examines its tremendous growth in recent years and its uniquely rich online/offline interactions.

To account for the growing process variability in modern VLSI technologies, circuit models parameterized in a multitude of parametric variations are becoming increasingly indispensable in robust circuit design. However, the high parameter dimensionality can introduce significant complexity and may even render variation-aware performance analysis and optimization completely intractable. We present a performance-oriented parameter dimension reduction framework to reduce the modeling complexity associated with high parameter dimensionality. Our framework has a theoretically sound statistical basis, namely, reduced rank regression (RRR) and its various extensions that we have introduced for more practical VLSI circuit modeling. For a variety of VLSI circuits including interconnects and CMOS digital circuits, it is shown that this parameter reduction framework can provide more than one order of magnitude reduction in parameter dimensionality. Such parameter reduction immediately leads to reduced simulation cost in sampling-based performance analysis, and more importantly, highly efficient parameterized sub-circuit models that are instrumental in tackling the complexity of variation-tolerance VLSI system design.

Increasing variability in modern manufacturing processes makes it important to predict the yields of chip designs at early design stage. In recent years, a number of statistical static timing analysis (SSTA) and statistical circuit optimization techniques have emerged to quickly estimate the design yield and perform robust optimization. These statistical methods often rely on the availability of statistical process variation models whose accuracy, however, is severely hampered by the limitations in test structure design, test time, and various sources of inaccuracy inevitably incurred in process characterization. To consider model characterization inaccuracy, we present an efficient importance sampling based optimization framework that can translate the uncertainty in process models to the uncertainty in circuit performance, thus offering the desired statistical best/worst case circuit analysis capability accounting for the unavoidable complexity in process characterization. Furthermore, our new technique provides valuable guidance to process characterization. Examples are included to demonstrate the application of our general analysis framework under the context of SSTA.

Harmonic Balance (HB) analysis is key to efficient verification of large post-layout RF and microwave integrated circuits (ICs). This paper introduces a novel transient-simulation guided graph sparsification technique, as well as an efficient runtime performance modeling approach tailored for heterogeneous manycore CPU-GPU computing system to build nearly-optimal subgraph preconditioners that can lead to minimum HB simulation runtime. Additionally, we propose a novel heterogeneous parallel sparse block matrix algorithm by taking advantages of the structure of HB Jacobian matrices as well as GPU's streaming multiprocessors to achieve optimal work load balancing during the preconditioning phase of HB analysis. We also show how the proposed preconditioned iterative algorithm can efficiently adapt to heterogeneous computing systems with different CPU and GPU computing capabilities. Extensive experimental results show that our HB solver can achieve up to 20X speedups and 5X memory reduction when compared with the state-of-the-art direct solver highly optimized for eight-core CPUs.

Unlike traditional fast SPICE simulation techniques that rely on a variety of approximation approaches to trade off simulation accuracy for greater speed, SPICE-accurate integrated circuit (IC) simulations can truthfully predict circuit electrical behaviors, and therefore become indispensable for verification of large IC designs. Post-layout SPICE-accurate simulation should be able to encapsulate multi-million or even multi-billion devices that are coupled through complex parasitics and become an essential procedure for verification of nowadays nano-scale IC designs. Although many efficient numerical methods have been developed and adopted in the state-of-the-art SPICE-accurate circuit simulators for solving large sparse matrices involved in IC simulations, existing simulators may not be capable of handling extremely large-scale post-layout ICs in that the computation and memory cost can increase exponentially with the increase of circuit sizes and parasitics components. This paper introduces our recent effort in developing “truly scalable” SPICE-accurate nonlinear circuit simulation methods that can scale comfortably with extremely large-scale post-layout IC designs without sacrificing accuracy.

In recent years, social media has changed the way we interact and communicate. Although the existing structure of social media allows users to easily create, receive, and propagate pieces of information, many a time, users do not have background knowledge about the received information, including the provenance (sources or originators) of information, and other recipients who may have retransmitted or modified the information. Providing such additional context to the received information can help users know how much value, trust, and validity should be placed in received information. To judge the credibility of the received piece of information, it is vital to know who are its sources, and how information propagates from sources to other social media users. In this paper, we are studying a novel research problem that facilitates a few known recipients to recover other unknown recipients, and seek the provenance of information. The experimental results with Facebook and Twitter datasets show that the proposed algorithm is effective in correctly recovering the unknown recipients and seeking the provenance of information.

In recent years, social media sites have provided a large amount of information. Recipients of such information need mechanisms to know more about the received information, including the provenance. Previous research has shown that some attributes related to the received information provide additional context, so that a recipient can assess the amount of value, trust, and validity to be placed in the received information. Personal attributes of a user, including name, location, education, ethnicity, gender, and political and religious affiliations, can be found in social media sites. In this paper, we present a novel web-based tool for collecting the attributes of interest associated with a particular social media user related to the received information. This tool provides a way to combine different attributes available at different social media sites into a single user profile. Using different types of Twitter users, we also evaluate the performance of the tool in terms of number of attribute values collected, validity of these values, and total amount of retrieval time.

In nowadays variation-aware IC designs, cell characterizations and SRAM memory yield analysis require many thousands or even millions of repeated SPICE simulations for relatively small nonlinear circuits. In this work, we present a massively parallel SPICE simulator on GPU, TinySPICE, for efficiently analyzing small nonlinear circuits, such as standard cell designs, SRAMs, etc. In order to gain high accuracy and efficiency, we present GPU-based parametric three-dimensional (3D) LUTs for fast device evaluations. A series of GPU-friendly data structures and algorithm flows have been proposed in TinySPICE to fully utilize the GPU hardware resources, and minimize data communications between the GPU and CPU. Our GPU implementation allows for a large number of small circuit simulations in GPU's shared memory that involves novel circuit linearization and matrix solution techniques, and eliminates most of the GPU device memory accesses during the Newton-Raphson (NR) iterations, which enables extremely high-throughput SPICE simulations on GPU. Compared with CPU-based TinySPICE simulator, GPU-based TinySPICE achieves up to 138X speedups for parametric SRAM yield analysis without loss of accuracy.

To deal with the growing phenomenon of electromigration (EM), power grid current integrity verification becomes indispensable to designing reliable power delivery networks (PDNs). Unlike previous works that focus on vectorless voltage integrity verification of power grids, in this work, for the first time we present a scalable vectorless power grid current integrity verification framework. By taking advantage of multilevel power grid verifications, large-scale power grid current integrity verification tasks can be achieved in a very efficient way. Additionally, a novel EM-aware geometric power grid reduction method is proposed to well preserve the similar geometric and electrical properties of the original grid on the coarse-level power grids, which allows to quickly identify the potential "hot wires" that may carry greater-than-desired currents in a given power grid design. The proposed multilevel power grid verification algorithm provides flexible tradeoffs between the current integrity verification cost and solution quality, while the desired upper/lower bounds for worst case currents flowing through a wire can also be computed efficiently. Extensive experimental results show that our current integrity verification approach can efficiently handle very large power grid designs with good solution quality.

Social media propagates breaking news and disinformation alike fast and on an unsurpassed scale. Because of its democratizing nature, social media users can easily produce, receive, and propagate a piece of information without necessarily providing traceable information. Thus, there are no means for a user to verify the provenance (aka sources or originators) of information. The disinformation can cause tragic consequences to society and individuals. This work aims to take advantage of characteristics of social media to provide a solution to the problem of lacking traceable information. Such knowledge can provide additional context to received information such that a user can assess how much value, trust, and validity should be placed in it. In this paper, we are studying a novel research problem that facilitates the seeking of the provenance of information for a few known recipients (less than 1% of the total recipients) by recovering the paths it has taken from its originators. The proposed methodology exploits easily computable node centralities of a large social media network. The experimental results with Facebook and Twitter datasets show that the proposed mechanism is effective in correctly identifying the additional recipients and seeking the provenance of information.

SPICE-accurate simulation of present-day large-scale nonlinear integrated circuit (IC) systems with millions of linear/nonlinear components can be prohibitively expensive, and thus extremely challenging. In this paper, we present a novel support-circuit preconditioning (SCP) technique for tackling large-scale nonlinear circuit simulations by exploiting sparsified graphs of a given circuit network. By extracting support graphs (SGs) from the original linear circuit networks, and combining them with nonlinear devices, support-circuit preconditioner can be efficiently computed using existing matrix solvers, allowing for on-the-fly updates during transient simulations when adopted in Krylov-subspace iterative solvers. Experimental results for a variety of large-scale circuit designs show that the proposed method achieves up to 22X speedups in solving the matrices involved in DC and transient (TR) simulations, and up to 8X reduction in memory usage, when compared with the simulator powered by the state-of-the-art direct solver KLU.

To facilitate full chip capacitance extraction, field solvers are typically deployed for characterizing capacitance libraries for various interconnect structures and configurations. In the past decades, various algorithms for accelerating boundary element methods (BEM) have been developed to improve the efficiency of field solvers for capacitance extraction. This paper presents the first massively parallel capacitance extraction algorithm FMMGpu that accelerates the well-known fast multipole methods (FMM) on modern Graphics Processing Units (GPUs). We propose GPU-friendly data structures and SIMD parallel algorithm flows to facilitate the FMM-based 3-D capacitance extraction on GPU. Effective GPU performance modeling methods are also proposed to properly balance the workload of each critical kernel in our FMMGpu implementation, by taking advantage of the latest Fermi GPU's concurrent kernel executions on streaming multiprocessors (SMs). Our experimental results show that FMMGpu brings 22X to 30X speedups in capacitance extractions for various test cases. We also show that even for small test cases that may not well utilize GPU's hardware resources, the proposed cube clustering and workload balancing techniques can bring 20% to 60% extra performance improvements.

Multi-core architecture has emerged as the primary architectural choice to achieve power-efficient computing in microprocessors and SoCs. Power gating is indispensable for system power and thermal management and well suited for multi-core architectures. However, checking the power integrity (such as electromigration and voltage drop) of large gated power delivery networks (PDNs) presents a significant challenge due to the sheer die-package network complexity and the existence of an extremely large number of possible gating and operation configurations. We propose a simulation-based checking methodology that encompasses a comprehensive set of essential checking tasks. We tackle the challenges brought by the large checking space by developing strategies that efficiently identify top-ranked worst-case operating conditions, which are sequentially analyzed through a well-controlled number of full simulations for fidelity. We demonstrate the superior performance of the proposed approach on large power gating checking problems that are completely intractable to brute-force methods.

Leveraging the power of nowadays graphics processing units for robust power grid simulation remains a challenging task. Existing preconditioned iterative methods that require incomplete matrix factorizations can not be effectively accelerated on GPU due to its limited hardware resource as well as data parallel computing. This work presents an efficient GPU-based multigrid preconditioning algorithm for robust power grid analysis. An ELL-like sparse matrix data structure is adopted and implemented specifically for power grid analysis to assure coalesced GPU device memory access and high arithmetic intensity. By combining the fast geometrical multigrid solver with the robust Krylov-subspace iterative solver, power grid DC and transient analysis can be performed efficiently on GPU without loss of accuracy (largest errors < 0.5 mV). Unlike previous GPU-based algorithms that rely on good power grid regularities, the proposed algorithm can be applied for more general power grid structures. Experimental results show that the DC and transient analysis on GPU achieves more than 25X speedups over the best available CPU-based solvers. An industrial power grid with 10.5 million nodes can be accurately solved in 12 seconds.

Decoupling capacitor (decap) placement has been widely adopted as an effective way to suppress dynamic power supply noise. Traditional decap budgeting algorithms usually explore the sensitivity-based nonlinear optimizations or conjugate gradient methods, which can be prohibitively expensive for large-scale decap budgeting problems. We present a hierarchical cross entropy (CE) optimization technique for solving the decap budgeting problem. CE is an advanced optimization framework which explores the power of rare-event probability theory and importance sampling. To achieve high efficiency, a sensitivity-guided cross entropy (SCE) algorithm is proposed which integrates CE with a partitioning-based sampling strategy to effectively reduce the dimensionality in solving the large scale decap budgeting problems. Extensive experiments on industrial power grid benchmarks show that the proposed SCE method converges 2X faster than the prior methods and 10X faster than the standard CE method, while gaining up to 25% improvement on power grid supply noise. Importantly, the proposed SCE algorithm is parallel-friendly since the simulation samples of each SCE iteration can be independently obtained in parallel. We obtain up to 1.9X speedup when running the SCE decap budgeting algorithm on a dual-core-dual-GPU system.

Large VLSI on-chip power distribution networks (PDN) are challenging to analyze due to the sheer network complexity. In this paper, a novel parallel partitioning based PDN analysis approach is presented. We use the boundary circuit responses of each partition to divide the full grid simulation problem into a set of independent sub grid simulation problems. Instead of solving exact boundary circuit responses, a more efficient scheme to provide near exact approximation to the boundary circuit responses by exploiting the spatial locality of the flip-chip type power grids is proposed, in which only several small sub power grids need to be solved. This scheme is also used in a block based iterative error reduction process to improve the convergence. Through the analysis of several large power grids, the proposed approach, which can be fully parallelizable, is shown to have great runtime efficiency, fast convergence, and favorable scalability. Our approach can solve a 7.2 million-node power grid in 26 seconds, which is 18 times faster than a state of the art direct solver.

The growing need for an integrated view of information from different sources has led to the concept of information resource integration. In this paper, a Service Oriented approach for Information Resource Integration called SOIRI is introduced. Information services are put forward as basic elements in the SOIRI approach to realize information resource integration. A design method for information services is put forward, the metadata based management of information services is discussed, and a mediation way for information services access is given, also the SOIRI system for the approach is implemented, all of which contribute to the SOIRI approach. A real project utilizing the SOIRI approach is also discussed in the paper.

In recent years, a large body of statistical static timing analysis and statistical circuit optimization techniques have emerged, providing important avenues to account for the increasing process variations in design. The realization of these statistical methods often demands the availability of statistical process variation models whose accuracy, however, is severely hampered by limitations in test structure design, test time and various sources of inaccuracy inevitably incurred in process characterization. Consequently, it is desired that statistical circuit analysis and optimization can be conducted based upon imprecise statistical variation models. In this paper, we present an efficient importance sampling based optimization framework that can translate the uncertainty in the process models to the uncertainty in parametric yield, thus offering the very much desired statistical best/worst-case circuit analysis capability accounting for unavoidable complexity in process characterization. Unlike the previously proposed statistical learning and probabilistic interval based techniques, our new technique efficiently computes tight bounds of the parametric circuit yields based upon bounds of statistical process model parameters while fully capturing correlation between various process variations. Furthermore, our new technique provides valuable guidance to process characterization. Examples are included to demonstrate the application of our general analysis framework under the context of statistical static timing analysis.

Parameterized circuit models are desired at various VLSI design stages to account for the increasing process-induced performance variations. However, the large number of process variation sources encountered in modern VLSI technologies often lead to overly complex parameterized models whose generation as well as application is computationally expensive. In this paper, we address this challenge by proposing a general VLSI parameter dimension reduction technique that can produce more compact parameterized models in a compressed set of variation variables. Unlike the widely used principle component analysis (PCA), our new approach is based upon the powerful reduced rank regression (RRR) theory and can lead to a much greater reduction of the parameter space due to the consideration of design-specific structural information. The application of our parameter reduction technique is demonstrated under the context of digital circuit timing simulation and analog macromodeling. Our experimental results have indicated an up to 10times reduction of the parameter space. The application of these compact parameterized models is also outlined under the context of system-level analysis

The ability to account for the growing impacts of multiple process variations in modern technologies is becoming an integral part of nanometer VLSI design. Under the context of timing analysis, the need for combating process variations has sparkled a growing body of statistical static timing analysis (SSTA) techniques. While first-order SSTA techniques enjoy good runtime efficiency desired for tackling large industrial designs, more accurate second-order SSTA techniques have been proposed to improve the analysis accuracy, but at the cost of high computational complexity. Although many sources of variations may impact the circuit performance, considering a large number of inter-die and intra-die variations in the traditional SSTA analysis is very challenging. In this paper, we address the analysis complexity brought by high parameter dimensionality in static timing analysis and propose an accurate yet fast second-order SSTA algorithm based upon novel parameter dimension reduction. By developing reduced-rank regression based parameter reduction algorithms within block-based SSTA flow, we demonstrate that accurate second order SSTA analysis can be extended to a much higher parameter dimensionality than what is possible before. Our experimental results have shown that the proposed parameter reduction can achieve up to 10X parameter dimension reduction and lead to significantly improved second-order SSTA analysis under a large set of process variations.