Complex systems such as social, biological and information networks, characterized by millions to billions of sub-entities and relationships between them are best represented by graphs. A distinguishing feature of such complex systems is the self-organization into dense clusters called communities. Detecting such communities in massive graphs is critical to the understanding of such complex systems. However community detection is non-trivial and is expensive due to a vast number of computations needed to fully realize the underlying relationships. While a number of near-exact and heuristic algorithms is available for community detection, parallelizing such algorithms to fully leverage the advantages of parallel hardware is still a challenging problem. Most presently available approaches attempt to optimize run-time complexities by scaling original serial community detection algorithms. Graph algorithms in general and existing community detection algorithms in particular are known for not being commensurate with linear scalability on parallel systems. Therefore, there is a need for a combination of high-performance software and a hardware platform that would support efficient parallel graph processing with respect to community detection. We present an Intel® Xeon Phi Label Propagation algorithm (PLPA) variant of community detection algorithm based on label propagation (LP). Our algorithm was tuned for the Intel® Xeon Phi platform a novel architecture that provides 50+ physical cores with simultaneous multithreading. We outline Phi architecture advantages and limitations for PLPA and massive graph processing in general. We present test results of running our algorithm on large real-world networks while achieving near linear speedups and improving the quality of the detected communities. We also analyze possibilities of processing massive networks that cannot fully fit in a Phi memory and hence we extend our initial solution to a modified PLPA (PLPA-M).

In this work a micro-scale generative model for simulating context-driven information cascades in online social networks is presented and analyzed. Activity cascades on online social networks are explained by the dynamic variation in the spectral radius of the sociologically derived local influence matrix. A stochastic discrete-event agent-based simulator working with synthesized graph topologies, that emulates people's behavior on online social networks is used in conjunction with time-varying local models to generate macro-level activity cascades.

This paper introduces PHYSENSE, a scalable framework for topic-dependent influence computation on large online social networks (OSNs) with application to generation of signatures of anomalous activity. PHYSENSE estimates and sets up sociological influence models to compute the diffusion of activity potential in the neighborhood of each of the nodes on the OSN. PHYSENSE then scales these to significant parts of the OSN by propagating the activity potentials through the graph topology, thereby generating the influence landscape in the form of an equivalent Green's function matrix. The computationally efficient dynamic update phase of PHYSENSE tracks the time and topic dependent changes in the influence landscape.

The explosion in social media adoption has opened up new opportunities for next-generation personalized web and information exchange in big data scenarios. Making sense of the massive number of overlapping streams of information generated by hundreds of millions of users on large social networks requires novel analytics and scalable computational techniques. This paper introduces PHYSENSE, a scalable framework for influence computation and activity prediction on large online social networks (OSNs). Drawing inspiration from the Friedkin-Johnsen model for opinion change, PHYSENSE estimates and sets up sociological influence models to compute the diffusion of activity potential in the neighborhood of each of the nodes. PHYSENSE then scales these to significant parts of the entire OSN by propagating these activity potentials through an equivalent Helmholtz Green's function. Examples to show the enhanced quality of PHYSENSE in influence detection over popular existing methods based on variations of PageRank are presented. Additionally, for enhanced speedup, the community structures found in the social graphs along with low-rank updates are exploited in the acceleration of both the setup and the dynamic update phases of the influence computation.

Parallel algorithms used in Very Large Scale Integration physical design bring significant challenges for their efficient and effective design and implementation. The rectangle intersection problem is a subset of the plane sweep problem, a topic of computational geometry and a component in design rule checking, parasitic resistance-capacitance extraction, and mask processing flows. A variant of a plane sweep algorithm that is embarrassingly parallel and therefore easily scalable on multicore machines and clusters, while exceeding the best-known parallel plane sweep algorithms on real-world tests, is presented in this letter.

Moore's Law has driven the semiconductor revolution enabling over four decades of scaling in frequency, size, complexity, and power. However, the limits of physics are preventing further scaling of speed, forcing a paradigm shift towards multicore computing and parallelization. In effect, the system is taking over the role that the single CPU was playing: high-speed signals running through chips but also packages and boards connect ever more complex systems. High-speed signals making their way through the entire system cause new challenges in the design of computing hardware. Inductance, phase shifts and velocity of light effects, material resonances, and wave behavior become not only prevalent but need to be calculated accurately and rapidly to enable short design cycle times. In essence, to continue scaling with Moore's Law requires the incorporation of Maxwell's equations in the design process. Incorporating Maxwell's equations into the design flow is only possible through the combined power that new algorithms, parallelization and high-speed computing provide. At the same time, incorporation of Maxwell-based models into circuit and system-level simulation presents a massive accuracy, passivity, and scalability challenge. In this tutorial, we navigate through the often confusing terminology and concepts behind field solvers, show how advances in field solvers enable integration into EDA flows, present novel methods for model generation and passivity assurance in large systems, and demonstrate the power of cloud computing in enabling the next generation of scalable Maxwell solvers and the next generation of Moore's Law scaling of systems. We intend to show the truly symbiotic growing relationship between Maxwell and Moore!

The increasing need for more computing power, the integration of multiple functionalities and the trends towards miniaturization of electronic systems have all contributed to rapid advancement in semiconductor and associated technologies. Higher frequencies of operation together with non-negligible coupling arising from form-factor size constraints, and inability to ignore parasitics imply that full-wave EM (Electromagnetic) simulation is an essential part of electronic system design.

Large-scale computations required in the analysis and design of social network interactions and internet search have traditionally had a flavor distinct from EDA. With scale, density, and personalization on the web, the picture is changing. We show early evidence here that EDA-based methodologies in field simulation may show new techniques for search, relevance in online advertising, and social network simulation.

The next generation internet will be the internet of things (and not just of computing devices like PCs, PDAs); this is presumed to be enabled by integrating simple computing plus communications capabilities into common objects of everyday use. Radio-frequency identification (RFID) is a compelling technology for creation of such pervasive sensor networks due to its potential for ubiquitous, low-cost/low-maintenance use. However, the current drivers for RFID deployment emphasize supply chain management using passive tags, implying that RFID sensor nets require advances beyond the components and system designs aimed at supply chain applications. This work provides a glimpse of how this may be achieved.

Synthesis of multi-GigaHertz radio frequency circuits brings together difficult challenges related to simulation, extraction and multidimensional space search. The standard approach of mapping all electromagnetic parasitics into parametric RLC models prior to synthesis is extremely restrictive especially when broadband and full-wave models with high accuracy are needed. In the presented approach, a two-stage macromodel that creates broadband, accurate parametric representations of passives, in particular spiral inductors, is developed. The broadband nature is captured through the Vector Fitting algorithm. The macromodels are implemented via efficient nonlinear, multidimensional regression using Relevance Vector Machine, and are coupled into circuit simulators through admittance parameters. Subsequently, optimization on both active and passive parameters are carried out simultaneously, thereby bypassing the ad hoc nature of two stage (actives and passives) approximate optimization. Two standard low-noise amplifier topologies are synthesized with tight performance constraints at center frequencies 5, 10 and 12 GigaHertz in order to demonstrate the frequency scalability of the methodology.

With continuing trends towards miniaturization of circuits and inclusion of multiple, complex functionalities on a single chip, the effect of process variations on circuit performance is assuming critical importance. In view of increasing frequency of operation, accurate variability analysis of RF/Microwave circuits would require modeling of the variability in the passive elements through a field solver. In this paper, a method for enabling accurate statistical analysis of a low noise amplifier and its differential version is proposed. The on-chip spiral inductors are modeled through an EM (Electromagnetic) solver, while the circuit part is modeled through SPICE. The proposed approach relies on application of the RS (Response Surface) methodology to the y-parameters of both the circuit and the inductors independently and expressing the eventual performance measures through a suitable combination of these y-parameters. The eventual performance measures are expressed through a hierarchical approach in terms of the underlying Gaussian random variables representing both the circuit and EM process parameters. An RSMC (Rapid Response Surface Monte Carlo) analysis on these derived response surfaces furnishes the PDFs and can also be used to predict the yield based on different qualifying criteria and objective functions. Several advantages of this method are outlined.

As technologies continue to shrink in size, modeling the effect of process variations on circuit performance is assuming profound significance. Process variations affect the onchip performance of both active and passive components. This necessitates the inclusion of the effect of these variations on distributed interconnect structures in modeling overall circuit performance. In this work, first it is shown through field-solver simulations that larger process variations lead to non-Gaussian PDFs (Probability Density Functions) for the circuit equivalent parameters of distributed passives. Next, a method for accurate statistical analysis of coupled circuit-EM (Electromagnetic) systems without computing the equivalent circuit parameters of EMmodeled objects is demonstrated. This method also obviates the need to generate random variables representing the equivalent circuit parameters, from distributions which are correlated, non- Gaussian and non-closed-form. The proposed approach relies on application of the Response Surface (RS) methodology to the y-parameters of both the circuit and the distributed structures independently and expressing the eventual performance measures through a suitable combination of the y-parameters. The eventual performance measures are expressed through a hierarchical approach in terms of the underlying Gaussian random variables representing the process parameters. A rapid Response Surface Monte Carlo (RSMC) analysis on these derived response surfaces furnishes the PDFs and can also be used to predict the yield based on different qualifying criteria and objective functions.

The partial element equivalent circuit (PEEC) approach has been used in different forms for the computation of equivalent circuit elements for quasi-static and full-wave electromagnetic models. In this paper, we focus on the topic of large scale inductance computations. For many problems as part of PEEC modeling, partial inductances need to be computed to model interactions between a large numbers of objects. These computations can be very time and memory consuming. To date, several techniques have been devised to reduce the memory and time required to compute the partial inductance entities, as well as the time required to use them in a circuit analysis compute step. Some of the existing methods use hierarchical compression while some others are based on issues like properties of the inverse of the partial inductance matrix. However, because of inherent limitations, most of these methods are less suitable for PEEC applications. In this paper, we present an approach which is based on the compression of the partial inductance matrix utilizing the QR decomposition of the far coefficients submatrices. The QR-decomposed form is represented as a compressed SPICE-compatible circuit. This yields an efficient and mathematically consistent approach for reducing the storage and time requirements

Simulation of distributed electromagnetic effects of electrically large structures is no longer a luxury but a necessity in the accurate prediction of modern day circuit performance. In this regard, integral equation based methods have steadily gained in popularity but suffer from the time and memory bottlenecks arising from the resultant dense matrix. Fast linear complexity solvers have been introduced in the past but with the growing complexity of circuit layouts parallel implementations are the only viable options in addressing practical circuit layouts. In this paper, we present a parallel implementation of the low-rank compression based fast solver with linear cost reduction capacity with respect to the number of processors. The main problems in parallelizing a hierarchical algorithm are discussed and the advantages of the implemented scheme are highlighted. The new solver enables the simulation of full-chip problems consisting of millions of unknowns with acceptable accuracy and modest time and memory requirements.

This paper proposes improvements in the row and column samplings of the multilevel QR factorization method known as IES/sup 3/, a fast integral equation solver previously proposed for efficient three-dimensional (3-D) parameter extraction. First, a rigorous Gram-Schmidt row sampling is developed to replace the row sampling algorithm in IES/sup 3/, leading to a more stable algorithm. Second, to further enhance the efficiency of column sampling, a new scheme based on the idea of locating the interpolation points is presented. Error analyses indicate that the proposed schemes have higher accuracies than the original sampling in IES/sup 3/, especially when the number of sampled points is small. The IES/sup 3/ that uses one of these improved algorithms is called improved multilevel matrix QR factorization (IMLMQRF). These IMLMQRFs are applied in the magnetoquasistatic analysis of printed circuits on multilayered lossy medium for extractions of inductances and resistances. The frequency dependency of such parameters is also illustrated.

Boundary element methods are being successfully used for modeling parasitic effects in cutting-edge circuit design. The dense system matrix generated therein presents a time and memory bottleneck. Fast iterative solver techniques, developed to address the problem, suffer from convergence issues which become pronounced for large number of right hand sides as is the case for massively coupled systems. In this paper an iteration free solution scheme is presented. The dense matrix is rendered sparse by applying multilevel multipole expansions, and the resultant sparse matrix is solved by a traditional sparse matrix solver. The accuracy and time and memory requirements for the solver are compared against the regular methods. The advantage of the presented method over the corresponding iterative scheme is also demonstrated.

Parasitic parameter extraction is a crucial issue in Integrated Circuit design. Integral equation based solvers, which guarantee high accuracy, suffer from a time and memory bottleneck arising from the dense matrices generated. .

Fast parasitic extraction is an integral part of high-speed microelectronic simulation at the package and on-chip level. Integral equation methods and related fast solvers for the iterative solution of the resulting dense matrix systems have enabled linear time complexity and memory usage. However, these methods tend to have large disparities between setup and matrix-vector product times that affect their efficiency when applied to multiple excitation problems, i.e., problems with a large number of nets. For example, FastCap, which is based on the fast multipole method, has a significantly faster setup time than the multilevel QR decomposition-based IES/sup 3/, but relatively slow matrix-vector products. In this paper, we present a novel oct-tree-based QR compression technique for fast iterative solution. The regular cube structure of the fast multipole method and the QR compression scheme for interaction submatrices as in IES/sup 3/ are combined to achieve a predetermined compressible matrix-block structure and, consequently, superior memory, setup, and solve time efficiencies.

In the numerical Maxwell-equation model (NMM3D) of rough-surface scattering, we solve Maxwell equations in three dimensions to calculate emissivities for applications in passive microwave remote sensing of soil and ocean surfaces. The difficult cases for soil surfaces are with exponential correlation functions when the surfaces have fine-scale structures of large slopes. The difficulty for ocean surfaces is that because the emissivities are close to that of a flat surface, the emissivities have to be calculated accurately to correctly assess the rough-surface effects. In this paper, the accuracies of emissivity calculations are improved by using Rao-Wilton-Glisson basis functions. We further use sparse matrix canonical method to solve the matrix equation of Poggio-Miller-Chang-Harrington-Wu integral equations. Energy conservation checks are provided for the simulations. Comparisons are made with results from the pulse basis function. Numerical results are illustrated for soil and ocean surfaces respectively with exponential correlation function and ocean spectrum. The emissivities of soil are illustrated at both L- and C-bands and at multiple incidence angles for the same physical roughness parameters. The brightness temperatures for ocean surfaces are illustrated for cases with various wind speeds. We compare results with those from the sparse matrix methods. Comparisons are also made with experimental emissivity measurements of soil surfaces. Parallel computation is also implemented. Lookup tables of emissivities based on NMM3D are provided.

Numerical simulation of passive microwave remote sensing of ocean surfaces has a strict requirement of accuracy. This is because the key output of the simulations is the difference of brightness temperature between a rough surface and a flat surface. Since the difference can be as small as 0.5 K, it is important to simulate the scattering and emission accurately. The authors perform accurate simulations of transverse electric (TE) and transverse magnetic (TM) waves for ocean surfaces with relative permittivity=28.9541/spl plusmn/i36.8430 at 19 GHz. Because ocean permittivity is large, the authors used up to 80 points per free space wavelength. Furthermore, accurate numerical integration is also performed to obtain accurate impedance matrix elements. To ensure accuracy, a matrix equation obtained from the surface integral equation formulation is solved by matrix inversion. Conservation of energy is required to be accurate to a relative error of 0.001, which corresponds to 0.3 K in brightness temperature. Numerical results are illustrated for rough surfaces with Gaussian spectrum and bandlimited ocean spectrum and bandlimited fractal surfaces. The authors show convergence with respect to the density of sampling points and with respect to raising the upper limit of the bandlimited ocean spectrum. Comparisons are also made with results with an impedance boundary condition approximation. Numerical results indicate that fine discretization is required for ocean-like surfaces with fine scale roughness.

Article Free Access Share on Efficient capacitance computation for structures with non-uniform adaptive surface meshes Authors: Vikram Jandhyala Ansoft Corporation, Four Station Square, Pittsburgh, PA Ansoft Corporation, Four Station Square, Pittsburgh, PAView Profile , Scott Savage Ansoft Corporation, Four Station Square, Pittsburgh, PA Ansoft Corporation, Four Station Square, Pittsburgh, PAView Profile , Eric Bracken Ansoft Corporation, Four Station Square, Pittsburgh, PA Ansoft Corporation, Four Station Square, Pittsburgh, PAView Profile , Zoltan Cendes Ansoft Corporation, Four Station Square, Pittsburgh, PA Ansoft Corporation, Four Station Square, Pittsburgh, PAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 543–548https://doi.org/10.1145/309847.309995Published:01 June 1999Publication History 1citation256DownloadsMetricsTotal Citations1Total Downloads256Last 12 Months6Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A new technique, the steepest descent-fast multipole method (SDFMM), is developed to efficiently analyze scattering from perfectly conducting random rough surfaces. Unlike other prevailing methods, this algorithm has linear computational complexity and memory requirements, making it a suitable candidate for analyzing scattering from large rough surfaces as well as for carrying out Monte Carlo simulations. The method exploits the quasiplanar nature of rough surfaces to efficiently evaluate the dyadic Green's function for multiple source and observation points. This is achieved through a combination of a Sommerfeld steepest descent integral and a multilevel fast multipole-like algorithm based on inhomogeneous plane wave expansions. The fast evaluation of the dyadic Green's function dramatically speeds up the iterative solution of the integral equation for rough surface scattering. Several numerical examples are presented to demonstrate the efficacy and accuracy of the method in analyzing scattering from extremely large finite rough surfaces.