Hybrid aggregated-vector algorithm for efficient parallelization of fast multipole method

An efficient parallelization algorithm for the Fast Multipole Method which aims to alleviate the parallelization bottleneck arising from lower job-count closer to root levels is presented. An electrostatic problem of 12 million non-uniformly distributed mesh elements is solved with 80-85% parallel efficiency in matrix setup and matrix-vector product using 60GB and 16 threads on shared memory architecture.

Solving MIN ONES 2-SAT as fast as VERTEX COVER

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

Fast and efficient automatic memory management for GPUs using compiler-assisted runtime coherence scheme

Exploiting the performance potential of GPUs requires managing the data transfers to and from them efficiently which is an error-prone and tedious task. In this paper, we develop a software coherence mechanism to fully automate all data transfers between the CPU and GPU without any assistance from the programmer. Our mechanism uses compiler analysis to identify potential stale accesses and uses a runtime to initiate transfers as necessary. This allows us to avoid redundant transfers that are exhibited by all other existing automatic memory management proposals. We integrate our automatic memory manager into the X10 compiler and runtime, and find that it not only results in smaller and simpler programs, but also eliminates redundant memory transfers. Tested on eight programs ported from the Rodinia benchmark suite it achieves (i) a 1.06x speedup over hand-tuned manual memory management, and (ii) a 1.29x speedup over another recently proposed compiler--runtime automatic memory management system. Compared to other existing runtime-only and compiler-only proposals, it also transfers 2.2x to 13.3x less data on average.

Minimizing the Complexity of Fast Sphere Decoding of STBCs

Decoding of linear space-time block codes (STBCs) with sphere-decoding (SD) is well known. A fast-version of the SD known as fast sphere decoding (FSD) was introduced by Biglieri, Hong and Viterbo. Viewing a linear STBC as a vector space spanned by its defining weight matrices over the real number field, we define a quadratic form (QF), called the Hurwitz-Radon QF (HRQF), on this vector space and give a QF interpretation of the FSD complexity of a linear STBC. It is shown that the FSD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization) or the number of receive antennas. It is also shown that the FSD complexity is completely captured into a single matrix obtained from the HRQF. Moreover, for a given set of weight matrices, an algorithm to obtain an optimal ordering of them leading to the least FSD complexity is presented. The well known classes of low FSD complexity codes (multi-group decodable codes, fast decodable codes and fast group decodable codes) are presented in the framework of HRQF.

Fast-Decodable MIDO Codes With Large Coding Gain

In this paper, a new method is proposed to obtain full-diversity, rate-2 (rate of two complex symbols per channel use) space-time block codes (STBCs) that are full-rate for multiple input double output (MIDO) systems. Using this method, rate-2 STBCs for 4 x 2, 6 x 2, 8 x 2, and 12 x 2 systems are constructed and these STBCs are fast ML-decodable, have large coding gains, and STBC-schemes consisting of these STBCs have a non-vanishing determinant (NVD) so that they are DMT-optimal for their respective MIDO systems. It is also shown that the Srinath-Rajan code for the 4 x 2 system, which has the lowest ML-decoding complexity among known rate-2 STBCs for the 4x2 MIDO system with a large coding gain for 4-/16-QAM, has the same algebraic structure as the STBC constructed in this paper for the 4 x 2 system. This also settles in positive a previous conjecture that the STBC-scheme that is based on the Srinath-Rajan code has the NVD property and hence is DMT-optimal for the 4 x 2 system.

Capture-Induced, Fast, Distributed, Splitting Based Selection with Imperfect Power Control

Opportunistic selection selects the node that improves the overall system performance the most. Selecting the best node is challenging as the nodes are geographically distributed and have only local knowledge. Yet, selection must be fast to allow more time to be spent on data transmission, which exploits the selected node's services. We analyze the impact of imperfect power control on a fast, distributed, splitting based selection scheme that exploits the capture effect by allowing the transmitting nodes to have different target receive powers and uses information about the total received power to speed up selection. Imperfect power control makes the received power deviate from the target and, hence, affects performance. Our analysis quantifies how it changes the selection probability, reduces the selection speed, and leads to the selection of no node or a wrong node. We show that the effect of imperfect power control is primarily driven by the ratio of target receive powers. Furthermore, we quantify its effect on the net system throughput.

Nearly Constant Switching Frequency Hysteresis Current Controller with Fast Online Computation of Boundary for a 2-Level Induction Motor Drive

A nearly constant switching frequency current hysteresis controller for a 2-level inverter fed induction motor drive is proposed in this paper: The salient features of this controller are fast dynamics for the current, inherent protection against overloads and less switching frequency variation. The large variation of switching frequency as in the conventional hysteresis controller is avoided by defining a current-error boundary which is obtained from the current-error trajectory of the standard space vector PWM. The current-error boundary is computed at every sampling interval based on the induction machine parameters and from the estimated fundamental stator voltage. The stator currents are always monitored and when the current-error exceeds the boundary, voltage space vector is switched to reduce the current-error. The proposed boundary computation algorithm is applicable in linear and over-modulation region and it is simple to implement in any standard digital signal processor: Detailed experimental verification is done using a 7.5 kW induction motor and the results are given to show the performance of the drive at various operating conditions and validate the proposed advantages.

A fast NMR method for resonance assignments: application to metabolomics

We present a new method for rapid NMR data acquisition and assignments applicable to unlabeled (C-12) or C-13-labeled biomolecules/organic molecules in general and metabolomics in particular. The method involves the acquisition of three two dimensional (2D) NMR spectra simultaneously using a dual receiver system. The three spectra, namely: (1) G-matrix Fourier transform (GFT) (3,2)D C-13, H-1] HSQC-TOCSY, (2) 2D H-1-H-1 TOCSY and (3) 2D C-13-H-1 HETCOR are acquired in a single experiment and provide mutually complementary information to completely assign individual metabolites in a mixture. The GFT (3,2)D C-13, H-1] HSQC-TOCSY provides 3D correlations in a reduced dimensionality manner facilitating high resolution and unambiguous assignments. The experiments were applied for complete H-1 and C-13 assignments of a mixture of 21 unlabeled metabolites corresponding to a medium used in assisted reproductive technology. Taken together, the experiments provide time gain of order of magnitudes compared to the conventional data acquisition methods and can be combined with other fast NMR techniques such as non-uniform sampling and covariance spectroscopy. This provides new avenues for using multiple receivers and projection NMR techniques for high-throughput approaches in metabolomics.

Pure shift NMR approach for fast and accurate extraction of heteronuclear couplings

The direct and accurate determination of heteronuclear ((n)J(HX), X = F-19, P-31) couplings from the one dimensional H-1-NMR spectrum is severely hampered due to the simultaneous presence of large numbers of (n)J(HH). The present study demonstrates the utility of the pure shift NMR approach for spectral simplification, and precise and direct measurement of heteronuclear couplings. As a consequence of refocusing of homonuclear couplings ((n)J(HH)) by the pure shift NMR, only heteronuclear couplings ((n)J(HX)) appear as simple multiplets at the resonance position of each chemically non-equivalent proton, enabling their direct measurement from the 1D-H-1 spectrum. The experiment is demonstrated on a number of molecules containing either F-19 or P-31, where (n)J(HF) and (n)J(HP) could be precisely measured in a straightforward manner. The distinct advantage of the experiment is demonstrated on molecules containing more than one fluorine atom, where most of the available NMR experiments fail or have restricted utility.

Controlling the cross-section of waveguides inscribed on bulk chalcogenide glasses using fast laser

Waveguides have been fabricated on melt-quenched, bulk chalcogenide glasses using the femto-second laser inscription technique at low repetition rates in the single scan regime. The inscribed waveguides have been characterized by butt-coupling method and the diameter of the waveguide calculated using the mode-field image of the waveguide. The waveguide cross-section symmetry is analyzed using the heat diffusion model by relating the energy and translation speed of the laser. The net-fluence and symmetry of the waveguides are correlated based on the theoretical values and experimental results of guiding cross-section.

Calcium Permeable AMPA Receptor-Dependent Long Lasting Plasticity of Intrinsic Excitability in Fast Spiking Interneurons of the Dentate Gyrus Decreases Inhibition in the Granule Cell Layer

The local fast-spiking interneurons (FSINs) are considered to be crucial for the generation, maintenance, and modulation of neuronal network oscillations especially in the gamma frequency band. Gamma frequency oscillations have been associated with different aspects of behavior. But the prolonged effects of gamma frequency synaptic activity on the FSINs remain elusive. Using whole cell current clamp patch recordings, we observed a sustained decrease of intrinsic excitability in the FSINs of the dentate gyrus (DG) following repetitive stimulations of the mossy fibers at 30 Hz (gamma bursts). Surprisingly, the granule cells (GCs) did not express intrinsic plastic changes upon similar synaptic excitation of their apical dendritic inputs. Interestingly, pairing the gamma bursts with membrane hyperpolarization accentuated the plasticity in FSINs following the induction protocol, while the plasticity attenuated following gamma bursts paired with membrane depolarization. Paired pulse ratio measurement of the synaptic responses did not show significant changes during the experiments. However, the induction protocols were accompanied with postsynaptic calcium rise in FSINs. Interestingly, the maximum and the minimum increase occurred during gamma bursts with membrane hyperpolarization and depolarization respectively. Including a selective blocker of calcium-permeable AMPA receptors (CP-AMPARs) in the bath; significantly attenuated the calcium rise and blocked the membrane potential dependence of the calcium rise in the FSINs, suggesting their involvement in the observed phenomenon. Chelation of intracellular calcium, blocking HCN channel conductance or blocking CP-AMPARs during the experiment forbade the long lasting expression of the plasticity. Simultaneous dual patch recordings from FSINs and synaptically connected putative GCs confirmed the decreased inhibition in the GCs accompanying the decreased intrinsic excitability in the FSINs. Experimentally constrained network simulations using NEURON predicted increased spiking in the GC owing to decreased input resistance in the FSIN. We hypothesize that the selective plasticity in the FSINs induced by local network activity may serve to increase information throughput into the downstream hippocampal subfields besides providing neuroprotection to the FSINs. (c) 2014 Wiley Periodicals, Inc.

Adaptive Mesh Refinement for Fast Convergence of EFIE-Based 3-D Extraction

3-D full-wave method of moments (MoM) based electromagnetic analysis is a popular means toward accurate solution of Maxwell's equations. The time and memory bottlenecks associated with such a solution have been addressed over the last two decades by linear complexity fast solver algorithms. However, the accurate solution of 3-D full-wave MoM on an arbitrary mesh of a package-board structure does not guarantee accuracy, since the discretization may not be fine enough to capture spatial changes in the solution variable. At the same time, uniform over-meshing on the entire structure generates a large number of solution variables and therefore requires an unnecessarily large matrix solution. In this paper, different refinement criteria are studied in an adaptive mesh refinement platform. Consequently, the most suitable conductor mesh refinement criterion for MoM-based electromagnetic package-board extraction is identified and the advantages of this adaptive strategy are demonstrated from both accuracy and speed perspectives. The results are also compared with those of the recently reported integral equation-based h-refinement strategy. Finally, a new methodology to expedite each adaptive refinement pass is proposed.

Effect of ultra-fast mixing in a microchannel due to a soft wall on the room temperature synthesis of gold nanoparticles

The room-temperature synthesis of mono-dispersed gold nanoparticles, by the reduction of chlorauric acid (HAuCl4) with tannic acid as the reducing and stabilizing agent, is carried out in a microchannel. The microchannel is fabricated with one soft wall, so that there is a spontaneous transition to turbulence, and thereby enhanced mixing, when the flow Reynolds number increases beyond a critical value. The objective of the study is to examine whether the nanoparticle size and polydispersity can be modified by enhancing the mixing in the microchannel device. The flow rates are varied in order to study nanoparticle formation both in laminar flow and in the chaotic flow after transition, and the molar ratio of the chlorauric acid to tannic acid is also varied to study the effect of molar ratio on nanoparticle size. The formation of gold nanoparticles is examined by UV-visual spectroscopy and the size distribution is determined using scanning electron microscopy. The synthesized nanoparticles size decreases from a parts per thousand yen6 nm to a parts per thousand currency sign4 nm when the molar ratio of chlorauric acid to tannic acid is increased from 1 to 20. It is found that there is no systematic variation of nanoparticle size with flow velocity, and the nanoparticle size is not altered when the flow changes from laminar to turbulent. However, the standard deviation of the size distribution decreases by about 30% after transition, indicating that the enhanced mixing results in uniformity of particle size.

Investigation of schemes for incorporating generator Q limits in the fast decoupled load flow method

Fast Decoupled Load Flow (FDLF) is a very popular and widely used power flow analysis method because of its simplicity and efficiency. Even though the basic FDLF algorithm is well investigated, the same is not true in the case of additional schemes/modifications required to obtain adjusted load flow solutions using the FDLF method. Handling generator Q limits is one such important feature needed in any practical load flow method. This paper presents a comprehensive investigation of two classes of schemes intended to handle this aspect i.e. the bus type switching scheme and the sensitivity scheme. We propose two new sensitivity based schemes and assess their performance in comparison with the existing schemes. In addition, a new scheme to avoid the possibility of anomalous solutions encountered while using the conventional schemes is also proposed and evaluated. Results from extensive simulation studies are provided to highlight the strengths and weaknesses of these existing and proposed schemes, especially from the point of view of reliability.

A Fast and Fault-Tolerant Distributed Algorithm for Near-Optimal TDMA Scheduling in WSNs

The time division multiple access (TDMA) based channel access mechanisms perform better than the contention based channel access mechanisms, in terms of channel utilization, reliability and power consumption, specially for high data rate applications in wireless sensor networks (WSNs). Most of the existing distributed TDMA scheduling techniques can be classified as either static or dynamic. The primary purpose of static TDMA scheduling algorithms is to improve the channel utilization by generating a schedule of smaller length. But, they usually take longer time to schedule, and hence, are not suitable for WSNs, in which the network topology changes dynamically. On the other hand, dynamic TDMA scheduling algorithms generate a schedule quickly, but they are not efficient in terms of generated schedule length. In this paper, we propose a novel scheme for TDMA scheduling in WSNs, which can generate a compact schedule similar to static scheduling algorithms, while its runtime performance can be matched with those of dynamic scheduling algorithms. Furthermore, the proposed distributed TDMA scheduling algorithm has the capability to trade-off schedule length with the time required to generate the schedule. This would allow the developers of WSNs, to tune the performance, as per the requirement of prevalent WSN applications, and the requirement to perform re-scheduling. Finally, the proposed TDMA scheduling is fault-tolerant to packet loss due to erroneous wireless channel. The algorithm has been simulated using the Castalia simulator to compare its performance with those of others in terms of generated schedule length and the time required to generate the TDMA schedule. Simulation results show that the proposed algorithm generates a compact schedule in a very less time.