Use of data dependence graphs in the design of bit-level systolic arrays

The use of bit-level systolic array circuits as building blocks in the construction of larger word-level systolic systems is investigated. It is shown that the overall structure and detailed timing of such systems may be derived quite simply using the dependence graph and cut-set procedure developed by S. Y. Kung (1988). This provides an attractive and intuitive approach to the bit-level design of many VLSI signal processing components. The technique can be applied to ripple-through and partly pipelined circuits as well as fully systolic designs. It therefore provides a means of examining the relative tradeoff between levels of pipelining, chip area, power consumption, and throughput rate within a given VLSI design.

DESIGNING VLSI SIGNAL PROCESSING CHIPS USING DATA DEPENDENCE GRAPHS.

The highly structured nature of many digital signal processing operations allows these to be directly implemented as regular VLSI circuits. This feature has been successfully exploited in the design of a number of commercial chips, some examples of which are described. While many of the architectures on which such chips are based were originally derived on heuristic basis, there is an increasing interest in the development of systematic design techniques for the direct mapping of computations onto regular VLSI arrays. The purpose of this paper is to show how the the technique proposed by Kung can be readily extended to the design of VLSI signal processing chips where the organisation of computations at the level of individual data bits is of paramount importance. The technique in question allows architectures to be derived using the projection and retiming of data dependence graphs.

Universal behaviour of shock precursors in the presence of efficient cosmic ray acceleration

The self-consistent interaction between energetic particles and self-generated hydromagnetic waves in a cosmic ray pressure dominated plasma is considered. Using a three-dimensional hybrid magnetohydrodynamics (MHD)-kinetic code, which utilizes a spherical harmonic expansion of the Vlasov-Fokker-Planck equation, high-resolution simulations of the magnetic field growth including feedback on the cosmic rays are carried out. It is found that for shocks with high cosmic ray acceleration efficiency, the magnetic fields become highly disorganized, resulting in near isotropic diffusion, independent of the initial orientation of the ambient magnetic field. The possibility of sub-Bohm diffusion is demonstrated for parallel shocks, while the diffusion coefficient approaches the Bohm limit from below for oblique shocks. This universal behaviour suggests that Bohm diffusion in the root-mean-squared field inferred from observation may provide a realistic estimate for the maximum energy acceleration time-scale in young supernova remnants. Although disordered, the magnetic field is not self-similar suggesting a non-uniform energy-dependent behaviour of the energetic particle transport in the precursor. Possible indirect radiative signatures of cosmic ray driven magnetic field amplification are discussed.

Implementing efficient graphs in connection networks

We consider the problem of sharing the cost of a network that meets the connection demands of a set of agents. The agents simultaneously choose paths in the network connecting their demand nodes. A mechanism splits the total cost of the network formed among the participants. We introduce two new properties of implementation. The first property, Pareto Nash implementation (PNI), requires that the efficient outcome always be implemented in a Nash equilibrium and that the efficient outcome Pareto dominates any other Nash equilibrium. The average cost mechanism and other asymmetric variations are the only mechanisms that meet PNI. These mechanisms are also characterized under strong Nash implementation. The second property, weakly Pareto Nash implementation (WPNI), requires that the least inefficient equilibrium Pareto dominates any other equilibrium. The egalitarian mechanism (EG) and other asymmetric variations are the only mechanisms that meet WPNI and individual
rationality. EG minimizes the price of stability across all individually rational mechanisms. © Springer-Verlag Berlin Heidelberg 2012

Using Graphs to Visualise and Detect Anomalies in Access Control System Transactions

Physical Access Control Systems are commonly used to secure doors in buildings such as airports, hospitals, government buildings and offices. These systems are designed primarily to provide an authentication mechanism, but they also log each door access as a transaction in a database. Unsupervised learning techniques can be used to detect inconsistencies or anomalies in the mobility data, such as a cloned or forged Access Badge, or unusual behaviour by staff members. In this paper, we present an overview of our method of inferring directed graphs to represent a physical building network and the flows of mobility within it. We demonstrate how the graphs can be used for Visual Data Exploration, and outline how to apply algorithms based on Information Theory to the graph data in order to detect inconsistent or abnormal behaviour.

AGWAN: A Generative Model for Labelled, Weighted Graphs

Real-world graphs or networks tend to exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Much effort has been directed into creating realistic and tractable models for unlabelled graphs, which has yielded insights into graph structure and evolution. Recently, attention has moved to creating models for labelled graphs: many real-world graphs are labelled with both discrete and numeric attributes. In this paper, we present AGWAN (Attribute Graphs: Weighted and Numeric), a generative model for random graphs with discrete labels and weighted edges. The model is easily generalised to edges labelled with an arbitrary number of numeric attributes. We include algorithms for fitting the parameters of the AGWAN model to real-world graphs and for generating random graphs from the model. Using the Enron “who communicates with whom” social graph, we compare our approach to state-of-the-art random labelled graph generators and draw conclusions about the contribution of discrete vertex labels and edge weights to the structure of real-world graphs.

Sequential measurement-based quantum computing with memories

We introduce a general scheme for sequential one-way quantum computation where static systems with long-living quantum coherence (memories) interact with moving systems that may possess very short coherence times. Both the generation of the cluster state needed for the computation and its consumption by measurements are carried out simultaneously. As a consequence, effective clusters of one spatial dimension fewer than in the standard approach are sufficient for computation. In particular, universal computation requires only a one-dimensional array of memories. The scheme applies to discrete-variable systems of any dimension as well as to continuous-variable ones, and both are treated equivalently under the light of local complementation of graphs. In this way our formalism introduces a general framework that encompasses and generalizes in a unified manner some previous system-dependent proposals. The procedure is intrinsically well suited for implementations with atom-photon interfaces.

Universal tight binding model for chemical reactions in solution and at surfaces. II. Water

A revised water model intended for use in condensed phase simulations in the framework of the self consistent polarizable ion tight binding theory is constructed. The model is applied to water monomer, dimer, hexamers, ice, and liquid, where it demonstrates good agreement with theoretical results obtained by more accurate methods, such as DFT and CCSD(T), and with experiment. In particular, the temperature dependence of the self diffusion coefficient in liquid water predicted by the model, closely reproduces experimental curves in the temperature interval between 230 K and 350 K. In addition, and in contrast to standard DFT, the model properly orders the relative densities of liquid water and ice. A notable, but inevitable, shortcoming of the model is underestimation of the static dielectric constant by a factor of two. We demonstrate that the description of inter and intramolecular forces embodied in the tight binding approximation in quantum mechanics leads to a number of valuable insights which can be missing from ab initio quantum chemistry and classical force fields. These include a discussion of the origin of the enhanced molecular electric dipole moment in the condensed phases, and a detailed explanation for the increase of coordination number in liquid water as a function of temperature and compared with ice-leading to insights into the anomalous expansion on freezing. The theory holds out the prospect of an understanding of the currently unexplained density maximum of water near the freezing point. 

Universal tight binding model for chemical reactions in solution and at surfaces. III. Stoichiometric and reduced surfaces of titania and the adsorption of water

We demonstrate a model for stoichiometric and reduced titanium dioxide intended for use in molecular dynamics and other atomistic simulations and based in the polarizable ion tight binding theory. This extends the model introduced in two previous papers from molecular and liquid applications into the solid state, thus completing the task of providing a comprehensive and unified scheme for studying chemical reactions, particularly aimed at problems in catalysis and electrochemistry. As before, experimental results are given priority over theoretical ones in selecting targets for model fitting, for which we used crystal parameters and band gaps of titania bulk polymorphs, rutile and anatase. The model is applied to six low index titania surfaces, with and without oxygen vacancies and adsorbed water molecules, both in dissociated and non-dissociated states. Finally, we present the results of molecular dynamics simulation of an anatase cluster with a number of adsorbed water molecules and discuss the role of edge and corner atoms of the cluster. (C) 2014 AIP Publishing LLC.

Universal tight binding model for chemical reactions in solution and at surfaces. I. Organic molecules

As is now well established, a first order expansion of the Hohenberg-Kohn total energy density functional about a trial input density, namely, the Harris-Foulkes functional, can be used to rationalize a non self consistent tight binding model. If the expansion is taken to second order then the energy and electron density matrix need to be calculated self consistently and from this functional one can derive a charge self consistent tight binding theory. In this paper we have used this to describe a polarizable ion tight binding model which has the benefit of treating charge transfer in point multipoles. This admits a ready description of ionic polarizability and crystal field splitting. It is necessary in constructing such a model to find a number of parameters that mimic their more exact counterparts in the density functional theory. We describe in detail how this is done using a combination of intuition, exact analytical fitting, and a genetic optimization algorithm. Having obtained model parameters we show that this constitutes a transferable scheme that can be applied rather universally to small and medium sized organic molecules. We have shown that the model gives a good account of static structural and dynamic vibrational properties of a library of molecules, and finally we demonstrate the model's capability by showing a real time simulation of an enolization reaction in aqueous solution. In two subsequent papers, we show that the model is a great deal more general in that it will describe solvents and solid substrates and that therefore we have created a self consistent quantum mechanical scheme that may be applied to simulations in heterogeneous catalysis.