Pipelined ring algorithm for matrix multiplication on transputer networks: performance analysis and estimation

A parallel matrix multiplication algorithm is presented, and studies of its performance and estimation are discussed. The algorithm is implemented on a network of transputers connected in a ring topology. An efficient scheme for partitioning the input matrices is introduced which enables overlapping computation with communication. This makes the algorithm achieve near-ideal speed-up for reasonably large matrices. Analytical expressions for the execution time of the algorithm have been derived by analysing its computation and communication characteristics. These expressions are validated by comparing the theoretical results of the performance with the experimental values obtained on a four-transputer network for both square and irregular matrices. The analytical model is also used to estimate the performance of the algorithm for a varying number of transputers and varying problem sizes. Although the algorithm is implemented on transputers, the methodology and the partitioning scheme presented in this paper are quite general and can be implemented on other processors which have the capability of overlapping computation with communication. The equations for performance prediction can also be extended to other multiprocessor systems.

An Efficient Robust Algorithm for the Surface-Potential Calculation of Independent DG MOSFET

Although the recently proposed single-implicit-equation-based input voltage equations (IVEs) for the independent double-gate (IDG) MOSFET promise faster computation time than the earlier proposed coupled-equations-based IVEs, it is not clear how those equations could be solved inside a circuit simulator as the conventional Newton-Raphson (NR)-based root finding method will not always converge due to the presence of discontinuity at the G-zero point (GZP) and nonremovable singularities in the trigonometric IVE. In this paper, we propose a unique algorithm to solve those IVEs, which combines the Ridders algorithm with the NR-based technique in order to provide assured convergence for any bias conditions. Studying the IDG MOSFET operation carefully, we apply an optimized initial guess to the NR component and a minimized solution space to the Ridders component in order to achieve rapid convergence, which is very important for circuit simulation. To reduce the computation budget further, we propose a new closed-form solution of the IVEs in the near vicinity of the GZP. The proposed algorithm is tested with different device parameters in the extended range of bias conditions and successfully implemented in a commercial circuit simulator through its Verilog-A interface.

PocketAlign A Novel Algorithm for Aligning Binding Sites in Protein Structures

A fundamental task in bioinformatics involves a transfer of knowledge from one protein molecule onto another by way of recognizing similarities. Such similarities are obtained at different levels, that of sequence, whole fold, or important substructures. Comparison of binding sites is important to understand functional similarities among the proteins and also to understand drug cross-reactivities. Current methods in literature have their own merits and demerits, warranting exploration of newer concepts and algorithms, especially for large-scale comparisons and for obtaining accurate residue-wise mappings. Here, we report the development of a new algorithm, PocketAlign, for obtaining structural superpositions of binding sites. The software is available as a web-service at http://proline.physicslisc.emetin/pocketalign/. The algorithm encodes shape descriptors in the form of geometric perspectives, supplemented by chemical group classification. The shape descriptor considers several perspectives with each residue as the focus and captures relative distribution of residues around it in a given site. Residue-wise pairings are computed by comparing the set of perspectives of the first site with that of the second, followed by a greedy approach that incrementally combines residue pairings into a mapping. The mappings in different frames are then evaluated by different metrics encoding the extent of alignment of individual geometric perspectives. Different initial seed alignments are computed, each subsequently extended by detecting consequential atomic alignments in a three-dimensional grid, and the best 500 stored in a database. Alignments are then ranked, and the top scoring alignments reported, which are then streamed into Pymol for visualization and analyses. The method is validated for accuracy and sensitivity and benchmarked against existing methods. An advantage of PocketAlign, as compared to some of the existing tools available for binding site comparison in literature, is that it explores different schemes for identifying an alignment thus has a better potential to capture similarities in ligand recognition abilities. PocketAlign, by finding a detailed alignment of a pair of sites, provides insights as to why two sites are similar and which set of residues and atoms contribute to the similarity.

STEM+: A Fair and Efficient Algorithm for Scheduling on the DSCH in UMTS Networks

In Universal Mobile Telecommunication Systems (UMTS), the Downlink Shared Channel (DSCH) can be used for providing streaming services. The traffic model for streaming services is different from the commonly used continuously- backlogged model. Each connection specifies a required service rate over an interval of time, k, called the "control horizon". In this paper, our objective is to determine how k DSCH frames should be shared among a set of I connections. We need a scheduler that is efficient and fair and introduce the notion of discrepancy to balance the conflicting requirements of aggregate throughput and fairness. Our motive is to schedule the mobiles in such a way that the schedule minimizes the discrepancy over the k frames. We propose an optimal and computationally efficient algorithm, called STEM+. The proof of the optimality of STEM+, when applied to the UMTS rate sets is the major contribution of this paper. We also show that STEM+ performs better in terms of both fairness and aggregate throughput compared to other scheduling algorithms. Thus, STEM+ achieves both fairness and efficiency and is therefore an appealing algorithm for scheduling streaming connections.

Determinant: Old algorithms, new insights (Extended Abstract)

In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coefficients of the characteristic polynomial, in terms of walks and closed walks of different kinds in the underlying graph. We develop algorithms based on these characterizations, and show that they tally with well-known algorithms arrived at independently from considerations in linear algebra.

A robust three phase power flow algorithm for radial distribution systems

An efficient load flow solution technique is required as a part of the distribution automation (DA) system for taking various control and operations decisions. This paper presents an efficient and robust three phase power flow algorithm for application to radial distribution networks. This method exploits the radial nature of the network and uses forward and backward propagation to calculate branch currents and node voltages. The proposed method has been tested to analyse several practical distribution networks of various voltage levels and also having high R/X ratio. The results for a practical distribution feeder are presented for illustration purposes. The application of the proposed method is also extended to find optimum location for reactive power compensation and network reconfiguration for planning and day-to-day operation of distribution networks.

Density matrix renormalization group algorithm for Bethe lattices of spin-1/2 or spin-1 sites with Heisenberg antiferromagnetic exchange

A density matrix renormalization group (DMRG) algorithm is presented for the Bethe lattice with connectivity Z = 3 and antiferromagnetic exchange between nearest-neighbor spins s = 1/2 or 1 sites in successive generations g. The algorithm is accurate for s = 1 sites. The ground states are magnetic with spin S(g) = 2(g)s, staggered magnetization that persists for large g > 20, and short-range spin correlation functions that decrease exponentially. A finite energy gap to S > S(g) leads to a magnetization plateau in the extended lattice. Closely similar DMRG results for s = 1/2 and 1 are interpreted in terms of an analytical three-site model.

Algorithm for Autonomous Reorganization of Mobile Wireless Camera Sensor Networks to Improve Coverage

In this paper, sensing coverage by wireless camera-embedded sensor networks (WCSNs), a class of directional sensors is studied. The proposed work facilitates the autonomous tuning of orientation parameters and displacement of camera-sensor nodes in the bounded field of interest (FoI), where the network coverage in terms of every point in the FoI is important. The proposed work is first of its kind to study the problem of maximizing coverage of randomly deployed mobile WCSNs which exploits their mobility. We propose an algorithm uncovered region exploration algorithm (UREA-CS) that can be executed in centralized and distributed modes. Further, the work is extended for two special scenarios: 1) to suit autonomous combing operations after initial random WCSN deployments and 2) to improve the network coverage with occlusions in the FoI. The extensive simulation results show that the performance of UREA-CS is consistent, robust, and versatile to achieve maximum coverage, both in centralized and distributed modes. The centralized and distributed modes are further analyzed with respect to the computational and communicational overheads.

Hybrid Working Set Algorithm for SVM Learning With a Kernel Coprocessor on FPGA

Support vector machines (SVM) are a popular class of supervised models in machine learning. The associated compute intensive learning algorithm limits their use in real-time applications. This paper presents a fully scalable architecture of a coprocessor, which can compute multiple rows of the kernel matrix in parallel. Further, we propose an extended variant of the popular decomposition technique, sequential minimal optimization, which we call hybrid working set (HWS) algorithm, to effectively utilize the benefits of cached kernel columns and the parallel computational power of the coprocessor. The coprocessor is implemented on Xilinx Virtex 7 field-programmable gate array-based VC707 board and achieves a speedup of upto 25x for kernel computation over single threaded computation on Intel Core i5. An application speedup of upto 15x over software implementation of LIBSVM and speedup of upto 23x over SVMLight is achieved using the HWS algorithm in unison with the coprocessor. The reduction in the number of iterations and sensitivity of the optimization time to variation in cache size using the HWS algorithm are also shown.

A Monte Carlo expectation maximisation algorithm for multiple target tracking

In this paper, we present an expectation-maximisation (EM) algorithm for maximum likelihood estimation in multiple target models (MTT) with Gaussian linear state-space dynamics. We show that estimation of sufficient statistics for EM in a single Gaussian linear state-space model can be extended to the MTT case along with a Monte Carlo approximation for inference of unknown associations of targets. The stochastic approximation EM algorithm that we present here can be used along with any Monte Carlo method which has been developed for tracking in MTT models, such as Markov chain Monte Carlo and sequential Monte Carlo methods. We demonstrate the performance of the algorithm with a simulation. © 2012 ISIF (Intl Society of Information Fusi).

Classical two-site fidelity and quantum phase transitions in the Ising model and the extended Hubbard model

In this Letter, the classical two-site-ground-state fidelity (CTGF) is exploited to identify quantum phase transitions (QPTs) for the transverse field Ising model (TFIM) and the one-dimensional extended Hubbard model (EHM). Our results show that the CTGF exhibits an abrupt change around the regions of criticality and can be used to identify QPTs in spin and fermionic systems. The method is especially convenient when it is connected with the density-matrix renormalization group (DMRG) algorithm. (C) 2008 Elsevier B.V. All rights reserved.

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.

An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer

Amorphous computing is the study of programming ultra-scale computing environments of smart sensors and actuators cite{white-paper}. The individual elements are identical, asynchronous, randomly placed, embedded and communicate locally via wireless broadcast. Aggregating the processors into groups is a useful paradigm for programming an amorphous computer because groups can be used for specialization, increased robustness, and efficient resource allocation. This paper presents a new algorithm, called the clubs algorithm, for efficiently aggregating processors into groups in an amorphous computer, in time proportional to the local density of processors. The clubs algorithm is well-suited to the unique characteristics of an amorphous computer. In addition, the algorithm derives two properties from the physical embedding of the amorphous computer: an upper bound on the number of groups formed and a constant upper bound on the density of groups. The clubs algorithm can also be extended to find the maximal independent set (MIS) and $Delta + 1$ vertex coloring in an amorphous computer in $O(log N)$ rounds, where $N$ is the total number of elements and $Delta$ is the maximum degree.

A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Analysis of Extended Partial Least Squares for Monitoring Large-Scale Processes

This paper theoretically analysis the recently proposed "Extended Partial Least Squares" (EPLS) algorithm. After pointing out some conceptual deficiencies, a revised algorithm is introduced that covers the middle ground between Partial Least Squares and Principal Component Analysis. It maximises a covariance criterion between a cause and an effect variable set (partial least squares) and allows a complete reconstruction of the recorded data (principal component analysis). The new and conceptually simpler EPLS algorithm has successfully been applied in detecting and diagnosing various fault conditions, where the original EPLS algorithm did only offer fault detection.