A System-C based Micro architectural Exploration Framework for Latency, Power and Performance Trade-offs of On-Chip Interconnection

We describe a System-C based framework we are developing, to explore the impact of various architectural and microarchitectural level parameters of the on-chip interconnection network elements on its power and performance. The framework enables one to choose from a variety of architectural options like topology, routing policy, etc., as well as allows experimentation with various microarchitectural options for the individual links like length, wire width, pitch, pipelining, supply voltage and frequency. The framework also supports a flexible traffic generation and communication model. We provide preliminary results of using this framework to study the power, latency and throughput of a 4x4 multi-core processing array using mesh, torus and folded torus, for two different communication patterns of dense and sparse linear algebra. The traffic consists of both Request-Response messages (mimicing cache accesses)and One-Way messages. We find that the average latency can be reduced by increasing the pipeline depth, as it enables higher link frequencies. We also find that there exists an optimum degree of pipelining which minimizes energy-delay product.

Performance Evaluation of Distance-Hop Proportionality on Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes on a region in Euclidean space, e.g., the unit square. After deployment, the nodes self-organise into a mesh topology. In a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this paper, we analyse the performance of this approximation. We show that nodes with a certain hop distance from a fixed anchor node lie within a certain annulus with probability approach- ing unity as the number of nodes n → ∞. We take a uniform, i.i.d. deployment of n nodes on a unit square, and consider the geometric graph on these nodes with radius r(n) = c q ln n n . We show that, for a given hop distance h of a node from a fixed anchor on the unit square,the Euclidean distance lies within [(1−ǫ)(h−1)r(n), hr(n)],for ǫ > 0, with probability approaching unity as n → ∞.This result shows that it is more likely to expect a node, with hop distance h from the anchor, to lie within this an- nulus centred at the anchor location, and of width roughly r(n), rather than close to a circle whose radius is exactly proportional to h. We show that if the radius r of the ge- ometric graph is fixed, the convergence of the probability is exponentially fast. Similar results hold for a randomised lattice deployment. We provide simulation results that il- lustrate the theory, and serve to show how large n needs to be for the asymptotics to be useful.

Combinatorial Representations of Block Codes

We look at graphical descriptions of block codes known as trellises, which illustrate connections between algebra and graph theory, and can be used to develop powerful decoding algorithms. Trellis sizes for linear block codes are known to grow exponentially with the code parameters. Of considerable interest to coding theorists therefore, are more compact descriptions called tail-biting trellises which in some cases can be much smaller than any conventional trellis for the same code . We derive some interesting properties of tail-biting trellises and present a new decoding algorithm.

Classical screw theory: A fresh look using dual eigenvalue approach

This paper presents a novel algebraic formulation of the central problem of screw theory, namely the determination of the principal screws of a given system. Using the algebra of dual numbers, it shows that the principal screws can be determined via the solution of a generalised eigenproblem of two real, symmetric matrices. This approach allows the study of the principal screws of the general screw systems associated with a manipulator of arbitrary geometry in terms of closed-form expressions of its architecture and configuration parameters. The formulation is illustrated with examples of practical manipulators.

On Pushing Multilingual Query Operators into Relational Engines

To effectively support today’s global economy, database systems need to manage data in multiple languages simultaneously. While current database systems do support the storage and management of multilingual data, they are not capable of querying across different natural languages. To address this lacuna, we have recently proposed two cross-lingual functionalities, LexEQUAL[13] and SemEQUAL[14], for matching multilingual names and concepts, respectively. In this paper, we investigate the native implementation of these multilingual functionalities as first-class operators on relational engines. Specifically, we propose a new multilingual storage datatype, and an associated algebra of the multilingual operators on this datatype. These components have been successfully implemented in the PostgreSQL database system, including integration of the algebra with the query optimizer and inclusion of a metric index in the access layer. Our experiments demonstrate that the performance of the native implementation is up to two orders-of-magnitude faster than the corresponding outsidethe- server implementation. Further, these multilingual additions do not adversely impact the existing functionality and performance. To the best of our knowledge, our prototype represents the first practical implementation of a crosslingual database query engine.

Phase relations in the system SrO-Y2O3-CuO-O2 and CaO-Y2O3-CuO-O2 at 1173 K

Phase relations in the systems SrO-Y2O3-CuO-O2 and CaO-Y2O3-CuO-O2 at 1173 K were established by equilibrating different compositions in flowing oxygen gas at a pressure of 1.01 × 105 Pa. The quenched samples were examined by optical microscopy, X-ray diffraction (XRD), energy dispersive analysis of X-rays (EDAX), and electron spin resonance (ESR). In the system SrO-Y2O3-CuO-O2, except for the limited substitution of Y3+ for Sr2+ ions in the ternary oxide Sr14Cu24O41, no new quaternary phase was found to be stable. The compositions corresponding to the solid solution Sr14−xYxCu24O41 and the compound SrCuO2+δ lie above the plane containing SrO, Y2O3, and CuO,displaced towards the oxygen apex. However, in the system CaO-Y203-CuO-O2 at 1173 K, all the condensed phases lie on the plane containing CaO, Y203, and CuO, and a new quaternary oxide YCa2Cu306.s is present. The quaternary phase has a composition that lies at the center of the nonstoichiometric field of the analogous phase YBa2Cu307_~ in the BaO-Y203-CuO-O2 system. The compound YCa2Cu306.s has the tetragonal structure and does not become superconducting at low temperature. Surprisingly, phase relations in the three systems CaO-Y203-CuO-O2, SrO-Y203-CuO-O2, and BaO-Y203-CuO-O2 are found to be quite different.

A simple numerical method for three-dimensional analysis of simple expansion chamber mufflers of rectangular as well as circular cross-section with a stationary medium

Three-dimensional effects are a primary source of discrepancy between the measured values of automotive muffler performance and those predicted by the plane wave theory at higher frequencies. The basically exact method of (truncated) eigenfunction expansions for simple expansion chambers involves very complicated algebra, and the numerical finite element method requires large computation time and core storage. A simple numerical method is presented in this paper. It makes use of compatibility conditions for acoustic pressure and particle velocity at a number of equally spaced points in the planes of the junctions (or area discontinuities) to generate the required number of algebraic equations for evaluation of the relative amplitudes of the various modes (eigenfunctions), the total number of which is proportional to the area ratio. The method is demonstrated for evaluation of the four-pole parameters of rigid-walled, simple expansion chambers of rectangular as well as circular cross-section for the case of a stationary medium. Computed values of transmission loss are compared with those computed by means of the plane wave theory, in order to highlight the onset (cutting-on) of various higher order modes and the effect thereof on transmission loss of the muffler. These are also compared with predictions of the finite element methods (FEM) and the exact methods involving eigenfunction expansions, in order to demonstrate the accuracy of the simple method presented here.

Design space exploration of systolic realization of QR factorization on a runtime reconfigurable platform

In the world of high performance computing huge efforts have been put to accelerate Numerical Linear Algebra (NLA) kernels like QR Decomposition (QRD) with the added advantage of reconfigurability and scalability. While popular custom hardware solution in form of systolic arrays can deliver high performance, they are not scalable, and hence not commercially viable. In this paper, we show how systolic solutions of QRD can be realized efficiently on REDEFINE, a scalable runtime reconfigurable hardware platform. We propose various enhancements to REDEFINE to meet the custom need of accelerating NLA kernels. We further do the design space exploration of the proposed solution for any arbitrary application of size n × n. We determine the right size of the sub-array in accordance with the optimal pipeline depth of the core execution units and the number of such units to be used per sub-array.

Distributed Function Computation over Fields and Rings via Linear Compression of Sources

The setting considered in this paper is one of distributed function computation. More specifically, there is a collection of N sources possessing correlated information and a destination that would like to acquire a specific linear combination of the N sources. We address both the case when the common alphabet of the sources is a finite field and the case when it is a finite, commutative principal ideal ring with identity. The goal is to minimize the total amount of information needed to be transmitted by the N sources while enabling reliable recovery at the destination of the linear combination sought. One means of achieving this goal is for each of the sources to compress all the information it possesses and transmit this to the receiver. The Slepian-Wolf theorem of information theory governs the minimum rate at which each source must transmit while enabling all data to be reliably recovered at the receiver. However, recovering all the data at the destination is often wasteful of resources since the destination is only interested in computing a specific linear combination. An alternative explored here is one in which each source is compressed using a common linear mapping and then transmitted to the destination which then proceeds to use linearity to directly recover the needed linear combination. The article is part review and presents in part, new results. The portion of the paper that deals with finite fields is previously known material, while that dealing with rings is mostly new.Attempting to find the best linear map that will enable function computation forces us to consider the linear compression of source. While in the finite field case, it is known that a source can be linearly compressed down to its entropy, it turns out that the same does not hold in the case of rings. An explanation for this curious interplay between algebra and information theory is also provided in this paper.

Studies on hydrogen-bonds .4. proposed working criteria for assessing qualitative strength of hydrogen-bonds

The data obtained in the earlier parts of this series for the donor and acceptor end parameters of N-H. O and O-H. O hydrogen bonds have been utilised to obtain a qualitative working criterion to classify the hydrogen bonds into three categories: “very good” (VG), “moderately good” (MG) and weak (W). The general distribution curves for all the four parameters are found to be nearly of the Gaussian type. Assuming that the VG hydrogen bonds lie between 0 and ± la, MG hydrogen bonds between ± 1s̀ and ± 2s̀, W hydrogen bonds beyond ± 2s̀ (where s̀ is the standard deviation), suitable cut-off limits for classifying the hydrogen bonds in the three categories have been derived. These limits are used to get VG and MG ranges for the four parameters 1 and θ (at the donor end) and ± and ± (at the acceptor end). The qualitative strength of a hydrogen bond is decided by the cumulative application of the criteria to all the four parameters. The criterion has been further applied to some practical examples in conformational studies such as α-helix and can be used for obtaining suitable location of hydrogen atoms to form good hydrogen bonds. An empirical approach to the energy of hydrogen bonds in the three categories has also been presented.

Noncommutative vortices and instantons from generalized Bose operators

Generalized Bose operators correspond to reducible representations of the harmonic oscillator algebra. We demonstrate their relevance in the construction of topologically non-trivial solutions in noncommutative gauge theories, focusing our attention to flux tubes, vortices, and instantons. Our method provides a simple new relation between the topological charge and the number of times the basic irreducible representation occurs in the reducible representation underlying the generalized Bose operator. When used in conjunction with the noncommutative ADHM construction, we find that these new instantons are in general not unitarily equivalent to the ones currently known in literature.

A computational procedure to generate difference equations from differential equations

In this paper we have developed methods to compute maps from differential equations. We take two examples. First is the case of the harmonic oscillator and the second is the case of Duffing's equation. First we convert these equations to a canonical form. This is slightly nontrivial for the Duffing's equation. Then we show a method to extend these differential equations. In the second case, symbolic algebra needs to be used. Once the extensions are accomplished, various maps are generated. The Poincare sections are seen as a special case of such generated maps. Other applications are also discussed.

Interaction of guar gum with hydrophobic solids

The interaction of guar gum with the hydrophobic solids namely talc, mica and graphite has been investigated through adsorption, electrokinetic and flotation experiments. The adsorption densities of guar gum onto the above hydrophobic minerals show that they are more or less independent of pH. The adsorption isotherms of guar gum onto talc, mica and graphite indicate that the adsorption densities increase with increase in guar gum concentration and all the isotherms follow the as L1 type according to Giles classification. The magnitude of the adsorption density of guar gum onto the above minerals may be arranged in the following sequence: talc > graphite > mica The effect of particle size on the adsorption density of guar gum onto these minerals has indicated that higher adsorption takes place in the coarser size fraction, consequent to an increase in the surface face-to-edge ratio. In the case of the talc and mica samples pretreated with EDTA and the leached graphite sample, a decrease in the adsorption density of guar gum is observed, due to a reduction in the metallic adsorption sites. The adsorption densities of guar gum increase with decrease in sample weight for all the three minerals. Electrokinetic measurements have indicated that the isoelectric points (iep) of these minerals lie between pH 2-3, Addition of guar gum decreases the negative electrophoretic mobility values in proportion to the guar gum concentration without any observable shift in the iep values, resembling the influence of an indifferent electrolyte. The flotation recovery is diminished in the presence of guar gum for all the three minerals, The magnitude of depression follows the same sequence as observed in the adsorption studies. The floatability of EDTA treated talc and mica samples as well as the leached graphite sample is enhanced, complementing the adsorption data, Possible mechanisms of interaction between the hydrophobic minerals and guar gum are discussed.

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.

Contractive Hilbert modules and their dilations

In this note, we show that a quasi-free Hilbert module R defined over the polydisk algebra with kernel function k(z,w) admits a unique minimal dilation (actually an isometric co-extension) to the Hardy module over the polydisk if and only if S (-1)(z, w)k(z, w) is a positive kernel function, where S(z,w) is the Szego kernel for the polydisk. Moreover, we establish the equivalence of such a factorization of the kernel function and a positivity condition, defined using the hereditary functional calculus, which was introduced earlier by Athavale [8] and Ambrozie, Englis and Muller [2]. An explicit realization of the dilation space is given along with the isometric embedding of the module R in it. The proof works for a wider class of Hilbert modules in which the Hardy module is replaced by more general quasi-free Hilbert modules such as the classical spaces on the polydisk or the unit ball in a'', (m) . Some consequences of this more general result are then explored in the case of several natural function algebras.