Support Vector Machine (SVM) is a supervised machine learning model for classification tasks. Training SVM on a large number of data samples is challenging due to the high computational cost and memory requirement. Hence, model training is supported on a high-performance server which typically runs a sequential training algorithm on centralized data. However, as we move towards massive workloads, it will be impossible to store all the data in a centralized manner and expect such sequential training algorithms to scale on traditional processors. Moreover, with the growing demands of real-time machine learning for edge analytics, it is imperative to devise an efficient training framework with relatively cheaper computations and limited memory. Therefore, we propose and implement a first-of-its-kind system of multiple FPGAs as a distributed computing framework comprising up to eight FPGA units on Amazon F1 instances with negligible communication overhead to fully parallelize, accelerate, and scale the SVM training on decentralized data. Each FPGA unit has a pipelined SVM training IP logic core operating at 125 MHz with a power dissipation of 39 Watts for accelerating its allocated computations in the overall training process. We evaluate and compare the performance of the proposed system on five real SVM benchmarks.

Support Vector Machine (SVM) is a widely used supervised machine learning algorithm for classification. Training SVM is challenging due to high computational cost and memory requirements. More often such training is handled at back end servers leading to significant communication and energy overheads. This approach is unsuitable for edge analytics which is a growing trend with various IoT applications. Enabling efficient training on the edge requires a distributed computing approach that has negligible communication overhead and an energy-efficient hardware design to execute it. In this paper, we present a scalable FPGA-based design for distributed SVM training amenable for edge-based learning. Specifically, we implement a pipelined QRSVM IP logic on Xilinx Virtex UltraScale+ VU9P FPGA. Each synthesized IP core operates at 125 MHz with a power dissipation of 39 Watts. We evaluate the training time, parallel speedup, scalability, and energy efficiency of the proposed design on five SVM benchmarks on a multiple FPGA system comprising up to eight FPGA units. When compared with software implementation on the traditional embedded system edge processors like ARM Cortex-A15, the proposed FPGA implementation is around 3x to 24x faster and 2x to 8x more energy efficient on the above benchmarks.

Support Vector Machines (SVM) are widely used as supervised learning models to solve the classification problem in machine learning. Training SVMs for large datasets is an extremely challenging task due to excessive storage and computational requirements. To tackle so-called big data problems, one needs to design scalable distributed algorithms to parallelize the model training and to develop efficient implementations of these algorithms. In this paper, we propose a distributed algorithm for SVM training that is scalable and communication-efficient. The algorithm uses a compact representation of the kernel matrix, which is based on the QR decomposition of low-rank approximations, to reduce both computation and storage requirements for the training stage. This is accompanied by considerable reduction in communication required for a distributed implementation of the algorithm. Experiments on benchmark data sets with up to five million samples demonstrate negligible communication overhead and scalability on up to 64 cores. Execution times are vast improvements over other widely used packages. Furthermore, the proposed algorithm has linear time complexity with respect to the number of samples making it ideal for SVM training on decentralized environments such as smart embedded systems and edge-based internet of things, IoT.

Support Vector Machines (SVM) belong to a class of supervised machine learning algorithms with applications in classification and regression analysis. SVM training is modeled as a convex optimization problem that is computationally tedious and has large memory requirements. Specifically, it is a quadratic programming problem which scales rapidly with the training set size rather than the dimensionality of the feature space. In this work, we first present a novel QR decomposition framework (QRSVM) to efficiently model and solve a large scale SVM problem by capitalizing on low-rank representations of the full kernel matrix rather than solving the problem as a sequence of smaller sub-problems. The low-rank structure of the kernel matrix is leveraged to transform the dense matrix into one with a sparse and separable structure. The modified SVM problem requires significantly lesser memory and computation. Our approach scales linearly with the training set size which makes it applicable to large datasets. This motivates towards our another contribution; exploring a distributed QRSVM framework to solve large-scale SVM classification problems in parallel across a cluster of computing nodes. We also derive an optimal step size for fast convergence of the dual ascent method which is used to solve the quadratic programming problem.

In order to perform accurate parasitic extraction, foundries must provide the cross section profile of devices, and IP vendors must provide sufficient layout information. However, foundries and IP vendors are increasingly reluctant to reveal such sensitive information, especially for advanced devices. Therefore, the industry is faced with the following challenges: 1) foundries/IP vendors need to protect their trade secrets; 2) electronic design automation vendors need to integrate foundry data into extraction tools; and 3) IC designers need to have the accurate parasitic data. In this paper, we propose an innovative and practical solution to these challenges, by building a macro model around any region in 2-D/3-D on a circuit where foundries or IP vendors wish to hide information, yet the macro model allows accurate capacitance extraction inside and outside of the region. We first give algorithms to construct the macro model. Then, we describe how existing extraction algorithms can interface with the macro model to perform extraction for the entire circuit at the same accuracy as if complete information was given. The macro model can be used in finite difference method/finite element method and floating random walk, due to an equivalence theorem we proved. Finally, we propose the concept of equivalent profile and describe how to find one based on the macro model. Experimental results show the macro model can be efficiently constructed and used to produce accurate capacitance extraction.

As the size and complexity of current VLSI circuits grows, faster power grid simulation is becoming more and more desirable. In this article, we present a parallel iterative method for static VLSI power grid simulation. In the proposed enlarged-partition-based preconditioned conjugate gradient (EPPCG) power grid solver, the power grid is divided into disjoint partitions that are subsequently enlarged to obtain accurate solution within each partition. The global solution obtained by solving enlarged partition problems concurrently acts as a highly effective parallel preconditioner. The combination of effective preconditioning and efficient parallelization helps achieve very high performance. The experiments show that our parallel implementation can achieve significant speed improvement [61X--142X] over a state-of-the-art direct solver.

Preconditioned iterative solvers have the potential to solve very large sparse linear systems with a fraction of the memory used by direct methods. However, the effectiveness and performance of most preconditioners is not only problem dependent, but also fairly sensitive to the choice of their tunable parameters. As a result, a typical practitioner is faced with an overwhelming number of choices of solvers, preconditioners, and their parameters. The diversity of preconditioners makes it difficult to analyze them in a unified theoretical model. A systematic empirical evaluation of existing preconditioned iterative solvers can help in identifying the relative advantages of various implementations. We present the results of a comprehensive experimental study of the most popular preconditioner and iterative solver combinations for symmetric positive-definite systems. We introduce a methodology for a rigorous comparative evaluation of various preconditioners, including the use of some simple but powerful metrics. The detailed comparison of various preconditioner implementations and a state-of-the-art direct solver gives interesting insights into their relative strengths and weaknesses. We believe that these results would be useful to researchers developing preconditioners and iterative solvers as well as practitioners looking for appropriate sparse solvers for their applications.

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.

The existence of nonlinear magnetic materials poses a challenge to the interconnect inductance extraction for circuits in micromotors, radio-frequency identification, and magnetoresistive random access memory. In this paper, we present a fast algorithm to extract inductance in the presence of nonlinear magnetic materials. The new algorithm models the nonlinear magnetic characteristics by solving the Landau-Lifshitz-Gilbert equation, and the nonhomogeneous magnetic characteristics by introducing a fictitious magnetic charge. To speed up the algorithm, we apply a number of innovative techniques, including the approximation of magnetic charge effect and the modeling of currents with solenoidal basis. Experimental results demonstrate the accuracy and efficiency of the new algorithm. Its relative error with respect to the commercial tool is below 3%, while its speed is up to one magnitude faster.

Preconditioned iterative methods are often used to solve very large sparse systems of linear systems that arise in many scientific and engineering applications. The performance and robustness of these solvers is extremely sensitive to the choice of multiple preconditioner and solver parameters. Users of iterative methods often encounter an overwhelming number of combinations of choices for solvers, matrix preprocessing steps, preconditioners, and their parameters. The lack of a unified theoretical analysis of preconditioners coupled with limited knowledge of their interaction with linear systems makes it highly challenging for practitioners to choose good solver configurations. In this paper, we propose a novel, multi-stage learning based methodology for determining the best solver configurations to optimize the desired performance behavior for any given linear system. Empirical results over real performance data for the hyper iterative solver package demonstrate the efficacy and flexibility of the proposed approach.

This paper presents the first boundary element method (BEM) impedance extraction algorithm for interconnects with multiple dielectrics. Multiple dielectrics are common in integrated circuits and packages. However, previous BEM algorithms, including FastImp and FastPep, assume uniform dielectric due to their limitation, thus causing considerable errors. Our algorithm introduces a circuit formulation which makes it possible to utilize either multilayer Green's function or equivalent charge method to extract impedance in multiple dielectrics. The novelty of the formulation is the reduction of the unknowns and the application of hierarchical data structure. The hierarchical data structure permits efficient sparsification transformation and preconditioners to accelerate the linear equation solver. Experimental results demonstrate that the new algorithm is accurate and efficient. For uniform dielectric problems, our algorithm is more accurate than FastImp while its number of unknowns is ten times less than that of FastImp. For multiple dielectric problems, its relative error with respect to HFSS is below 3%.

In this paper, we present the first BEM impedance extraction algorithm for multiple dielectrics. The effect of multiple dielectrics is significant and efficient modeling is challenging. However, previous BEM algorithms, including Fastlmp and EastPep, assume uniform dielectric, thus causing considerable errors. The new algorithm introduces a circuit formulation which makes it possible to utilizes either multilayer Green's function or equivalent charge method to extract impedance in multiple dielectrics. The novelty of the formulation is the reduction of the number of unknowns and the application of the hierarchical data structure. The hierarchical data structure permits efficient sparsification transformation and preconditioners to accelerate the linear equation solver. Experimental results demonstrate that the new algorithm is accurate and efficient. For uniform dielectric problems, the new algorithm is one magnitude faster than Fastlmp, while its results differ from Fastlmp within 2%. For multiple dielectrics problems, its relative error with respect to HFSS is below 3%.

Inductance extraction involves estimating the mutual inductance in a VLSI circuit. Due to increasing clock speed and diminishing feature sizes of modern VLSI circuits, the effects of inductance are increasingly felt during the testing and verification stages. Hence, there is a need for fast and accurate inductance extraction software. A generalized approach for inductance extraction requires the solution of a dense complex symmetric linear system that models mutual inductive effects among circuit elements. Iterative methods are used to solve the system without explicit computation of the matrix itself. Fast hierarchical techniques are used to compute approximate matrix-vector products with the dense system matrix. This work presents an overview of a new parallel software package for inductance extraction of large VLSI circuits. The technique uses a combination of the solenoidal basis method and effective preconditioning schemes to solve the linear system. Fast multipole method (FMM) is used to compute approximate matrix-vector products with the inductance matrix. By formulating the pre-conditioner as a dense matrix similar to the coefficient matrix, we are able to use FMM for the preconditioning step as well. A two-tier parallelization scheme allows an efficient parallel implementation using both OpenMP and MPI directives simultaneously. The experiments conducted on various multiprocessor machines demonstrate the portability and parallel performance of the software.

Capacitance-extraction algorithms based on the boundary element method (BEM) have to solve large linear systems. The number of unknowns equals the number of discretization panels n, which is much greater than the number of conductors m. The authors present a capacitance-extraction algorithm RedCap that first reduces the BEM system of size n into a small system of size O(m) and then solves the small system to compute the capacitances. RedCap uses a number of techniques, including the hierarchical-refinement technique of HiCap [Shi, 2002], the dense-to-sparse transformation of PHiCap [Yan, 2005], a reordering of the sparse linear system, and an incomplete LU factorization, to obtain the reduced system. RedCap achieves a significant speed improvement over previous methods. On benchmark problems with conductors in uniform and multilayer dielectrics, RedCap is up to 100 times faster than FastCap [Nabors and White, 1991] and up to four times faster than PHiCap [Yan, 2005], while restricting error to within 2% of FastCap

Three-dimensional (3-D) capacitance-extraction algorithms are important due to their high accuracy. However, the current 3-D algorithms are slow and thus their application is limited. In this paper, we present a novel method to significantly speed up capacitance-extraction algorithms based on boundary element methods (BEMs), under uniform and multiple dielectrics. The n/spl times/n coefficient matrix in the BEM is dense, even when approximated with the fast multipole method or hierarchical-refinement method, where n is the number of panels needed to discretize the conductor surfaces and dielectric interfaces. As a result, effective preconditioners are hard to obtain and iterative solvers converge slowly. In this paper, we introduce a linear transformation to convert the n/spl times/n dense coefficient matrix into a sparse matrix with O(n) nonzero entries, and then use incomplete factorization to produce a very effective preconditioner. For the k/spl times/k bus-crossing benchmark, our method requires at most four iterations, whereas previous best methods such as FastCap and HiCap require 10-20 iterations. As a result, our algorithm is up to 70 times faster than FastCap and up to 2 times faster than HiCap on these benchmarks. Additional experiments illustrate that our method consistently outperforms previous best methods by a large magnitude on complex industrial problems with multiple dielectrics.

Capacitance extraction is an important problem that has been extensively studied. This paper presents a significant improvement for the fast multipole accelerated boundary element method. We first introduce an algebraic transformation to convert the n x n dense capacitance coefficient matrix into a sparse matrix with O(n) nonzero entries. We then use incomplete Cholesky factorization or incomplete LU factorization to produce an effective preconditioner for the sparse linear system. Simulation results show that our algorithm drastically reduces the number of iterations needed to solve the linear system associated with the boundary element method. For the k x k bus crossing benchmark, our algorithm uses 3-4 iterations, compared to 10-20 iterations used by the previous algorithms such as FastCap [1] and HiCap [2]. As a result, our algorithm is 2-20 times faster than those algorithms. Our algorithm is also superior to the multi-scale method [3] because our preconditioner reduces the number of iterations further and applies to multiple dielectrics.

The next generation VLSI circuits will be designed with millions of densely packed interconnect segments on a single chip. Inductive effects between these segments begin to dominate signal delay as the clock frequency is increased. Modern parasitic extraction tools to estimate the onchip inductive effects with high accuracy have had limited impact due to large computational and storage requirements. This work describes a parallel software package for inductance extraction called ParIS, which is capable of analyzing interconnect configurations involving several conductors within reasonable time. The main component of the software is a novel preconditioned iterative method that is used to solve a dense complex linear system of equations. The linear system represents the inductive coupling between filaments that are used to discretize the conductors. A variant of the fast multipole method is used to compute dense matrix-vector products with the coefficient matrix. ParIS uses a two-tier parallel formulation that allows mixed mode parallelization using both MPIand OpenMP. An MPI process is associated with each conductor. The computation within a conductor is parallelized using OpenMP. The parallel efficiency and scalability of the software is demonstrated through experiments on the IBM p690 and Intel and AMD Linux clusters. These experiments highlight the portability and efficiency of the software on multiprocessors with shared, distributed, and distributed-shared memory architectures.

Dense operators for preconditioning sparse linear systems have traditionally been considered infeasible due to their excessive computational and memory requirements. With the emergence of techniques such as block low-rank approximations and hierarchical multipole approximations, the cost of computing and storing these preconditioners has reduced dramatically. In our prior work [15], we have demonstrated the use of multipole-based techniques as effective parallel preconditioners for sparse linear systems. At one extreme, multipole-based preconditioners behave as dense (bounded interaction) matrices (multipole degree 0), while at the other extreme, they are represented entirely as series expansions. In this paper, we show that: (i) merely truncating the kernel of the integral operator generating the preconditioner leads to poor convergence properties; (ii) far-field interactions, in the form of multipoles, are critical for rapid convergence; (iii) the importance and required accuracy of far-field interactions varies with the complexity of the problem; and (iv) the preconditioner resulting from a judicious mix of near and far-field interactions yields excellent convergence and parallelization properties. Our experimental results are illustrated on the Poisson problem and the generalized Stokes problem arising in incompressible fluid flow simulations.

The ability to compute the parasitic inductance of the interconnect is critical to the timing verification of modern VLSI circuits. A challenging aspect of inductance extraction is the solution of large, dense, complex linear systems of equations via iterative methods. Accelerating the convergence of the iterative method through preconditioning is made difficult due to the non-availability of the system matrix. This paper presents a novel algorithm to solve these linear systems by restricting current to a discrete solenoidal subspace in which Kirchoff's law is obeyed, and solving a reduced system via an iterative method such as GMRES. A preconditioner based on the Green's function is used to achieve near-optimal convergence rates in several cases. Experiments on a number of benchmark problems illustrate the advantages of the proposed method over FastHenry.

This article presents an analytical and computational framework for the compression of particle data resulting from hierarchical approximate treecodes such as the Barnes--Hut and Fast Multipole Methods . Due to approximations introduced by hierarchical methods, various parameters (such as position, velocity, acceleration, potential) associated with a particle can be bounded by distortion radii. Using this distortion radii, we develop storage schemes that guarantee error bounds while maximizing compression. Our schemes make extensive use of spatial and temporal coherence of particle behavior and yield compression ratios higher than 12:1 over raw data, and 6:1 over gzipped (LZ) raw data for selected simulation instances. We demonstrate that for uniform distributions with 2M particles, storage requirements can be reduced from 24 MB to about 1.8 MB (about 7 bits per particle per timestep) for storing particle positions. This is significant because it enables faster storage/retrieval, better temporal resolution, and improved analysis. Our results are shown to scale from small systems (2K particles) to much larger systems (over 2M particles). The associated algorithm is asymptotically optimal in computation time ( O ( n )) with a small constant. Our implementations are demonstrated to run extremely fast---much faster than the time it takes to compute a single time-step advance. In addition, our compression framework relies on a natural hierarchical representation upon which other analysis tasks such as segmented and window retrieval can be built.

This paper presents an analytical and computational framework for the compression of particle data resulting from hierarchical approximate treecodes such as the Barnes-Hut and Fast Multipole Methods.Due to the approximations introduced by hierarchical methods, the position (as well as velocity and acceleration) of a particle can be bounded by a distortion radius.We develop storage schemes that maintain this distortion radii while maximizing compression.Our schemes make extensive use of spatial and temporal coherence of particle behavior and yield compression ratios higher than 12:1 over raw data, and 6:1 over gzipped (LZ78) raw data.We demonstrate that for uniform distributions with 100K particles, storage requirements can be reduced from 1200KB (100K × 12B) to about 99KB (under 1 byte per particle per timestep).This is significant because it enables faster storage/retrieval, better temporal resolution, and improved analysis.Our results are shown to scale from small systems (2K particles) to much larger systems (over 100K particles).The associated algorithm is optimal (O(n)) in both storage and computation with small constants.1

Rapid evaluation of potentials in particle systems is an important and time-consuming step in many physical simulations. Over the past decade (1988-98), the development of treecodes such as the Fast Multipole Method (FMM) and the Barnes-Hut method has enabled large scale simulations in domains such as astrophysics, molecular dynamics, and material science. FMM and related methods rely on fixed degree polynomial (p) approximations of the potential of a set of points in a hierarchy. We present a sequence of results to illustrate that keeping the multipole degree constant can lead to large aggregate errors. An alternate strategy based on a careful selection of the multipole degree leads to asymptotically lower errors; while incurring minimal computation overhead for practical problem sizes. The paper presents theoretical results for computing the degree of a particle cluster interaction, the error associated with the interaction, the error associated with a particle for all of its interactions, and the computational complexity of the new method. These results show that it is possible to reduce the simulation error asymptotically while incurring minimal computational overhead. The paper also presents experimental validation of these results on a 32 processor Origin 2000 in the context of problems ranging from astrophysics to boundary element solvers. In addition to verifying theoretical results, we also show that it is possible to achieve excellent parallel speedup for the treecode.

Abstract: The problem of evaluating the potential due to a set of particles is an important and time- consuming one. The development of fast treecodes such as the Barnes-Hut and Fast Multipole Methods for n-body systems has enabled large scale simulations in astrophysics [9, 10, 13] and molecular dynamics [1]. Coupled with efficient parallel processing, these treecodes are capable of yielding several orders of magnitude improvement in performance [6, 14, 15]. In addition, treecodes have applications in the solution of dense linear systems arising from boundary element methods [3, 4, 5, 11, 12]. Using a p-term multipole expansion, the FMM reduces the complexity of a single timestep from O(n2) to O(p2n) and Barnes-Hut method reduces it to O(p2log n) for a uniform distribution. In this paper, we analyze the approximations introduced by these methods. We describe an algorithm that reduces the error significantly by selecting the multipole degree appropriately for different clusters. Furthermore, we show that for practical problem sizes, this increases the computational complexity marginally. We support our theoretical result with experiments in the context of particle simulations as well as boundary element methods. Our POSIX threads-based treecode yields excellent speedups on a 32 processor SGI Origin 2000, even for relatively small problems.

. Iterative schemes for solving sparse linear systems arising from elliptic PDEs are very suitable for efficient implementation on large scale multiprocessors. However, these methods rely heavily on effective preconditioners which must also be amenable to parallelization. In this paper, we present a novel method to obtain a preconditioned linear system which is solved using an iterative method. Each iteration comprises of a matrix-vector product with k sparse matrices (k log n), and can be computed in O(n) operations where n is the number of unknowns. The numerical convergence properties of our preconditioner are superior to the commonly used incomplete factorization preconditioners. Moreover, unlike the incomplete factorization preconditioners, our algorithm affords a higher degree of concurrency and doesn't require triangular system solves, thereby achieving the dual objective of good preconditioning and efficient parallel implementation. We describe our scheme for certain linear sy...