Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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%. [ABSTRACT FROM AUTHOR]

It is known that the classical multilevel fast multipole method is a good technique for accelerating the iterative solution of integral equations with the Green's function kernel 1/r. However, few methods have been proposed for problems in molecular dynamics and computational chemistry where the Green's function is of the form r-λ, λ≥1. In this paper, we describe an efficient algorithm for computing potentials in which the integral equations have r-λ kernels. We propose a treecode algorithm which uses spherical harmonics to compute multipole coefficients that are used to evaluate these potentials. The key idea in this algorithm is the use of ultraspherical polynomials to represent r-λ in a manner analogous to the use of Legendre polynomials for the expansion of the Coulomb potential r-1. We exploit the relationship between ultraspherical and Legendre polynomials to develop a natural generalization of the multipole expansion theorem which was used in the multilevel fast multipole method. This theorem is used along with a hierarchical scheme to compute potentials of the form r-λ. The complexity of the algorithm is O(p3Nlog N) where N is the number of interacting particles and p is a small constant. We discuss the advantages of our algorithm over existing single level methods based on Cartesian coordinate expansion schemes. The efficiency of the algorithm is illustrated with numerical experiments. [ABSTRACT FROM AUTHOR]

Parasitic extraction techniques are used to estimate signal delay in VLSI circuits. Inductance extraction is a critical component of the parasitic extraction process that involves estimation of on-chip inductive effects with high accuracy. The problem requires the solution of a large, dense, complex linear system of equations, where the unknown current must satisfy the constraint imposed by Kirchoff's current law. In this paper, we describe a solenoidal basis method to transform the constrained linear system into an unconstrained one. The method uses discrete local solenoidal flows to represent the unknown current, and to obtain a reduced linear system. The paper proposes preconditioning techniques that do not require explicit construction of the reduced system. Numerical experiments are presented to illustrate the effectiveness of the preconditioning approach. Comparisons with a well-known inductance extraction package are provided to highlight the advantages of the proposed scheme. [ABSTRACT FROM AUTHOR]

Presents an analytical and computational framework for the compression of particle data resulting from hierarchical approximate treecodes such as Barnes-Hut and Fast Multipole Methods. Development of computer storage schemes that guarantee error bound while maximizing compression; Framework for bounded distortion multidimensional quantization.

A parallel algorithm is proposed for the solution of narrow banded non-symmetric linear systems. The linear system is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can then be solved by a direct or iterative method. A projection based extension to this approach is also proposed for computing the reduced system implicitly, which gives rise to an inner–outer iteration method. In addition, the product of a vector with the reduced system matrix can be computed efficiently on a multiprocessor by concurrent projections onto subspaces of block rows. Scalable implementations of the algorithm can be devized for hierarchical parallel architectures by exploiting the two-level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a robust and competitive alternative to existing methods, particularly for difficult problems with strong indefinite symmetric part. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Rapid evaluation of potentials in particle systems is an important, time-consuming step in many physical simulations. Over the past decade, the development of treecodes, such as the fast multipole method and Barnes-Hut method, has enabled large scale simulations in astrophysics, molecular dynamics, material science, etc. These methods use fixed-degree polynomial approximations of the potential at a point, due to a set of particles in a hierarchical representation of the particle system. In this paper, we present analysis and experiments to illustrate that fixed-degree multipole approximations can lead to large aggregate errors. We describe an alternate strategy based on careful selection of the multipole degree that leads to asymptotically lower errors while incurring minimal computation overhead. First, we estimate the error associated with each particle-cluster interaction and the aggregate error for each particle. Then we describe a technique for computing the multipole degree of each interaction with a view to reducing aggregate error, and establish the computational complexity of the new method. Following this, we discuss numerical experiments that demonstrate favorable error properties of the new method at the expense of marginal increase in computation. Finally, we report a parallel implementation on the SGI Origin 2000 that achieves excellent speedup for problems from domains such as astrophysics and boundary element solvers. [ABSTRACT FROM AUTHOR]

The generalized Stokes problem, which arises frequently in the simulation of timedependent Navier-Stokes equations for incompressible fluid flow, gives rise to symmetric linear systems of equations. These systems are indefinite due to a set of linear constraints on the velocity, causing difficulty for most preconditioners and iterative methods. This paper presents a novel method to obtain a preconditioned linear system from the original one which is then solved by an iterative method. This new method generates a basis for the velocity space and solves a reduced system which is symmetric and positive definite. Numerical experiments indicating superior convergence compared to existing methods are presented. A natural extension of this method to elliptic problems is also proposed, along with theoretical bounds on the rate of convergence, and results of experiments demonstrating robust and effective preconditioning. [ABSTRACT FROM AUTHOR]