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.

Interpreting the near-infrared spectra of the 'golden standard' Type Ia supernova 2005cf

We present nine near-infrared (NIR) spectra of supernova (SN) 2005cf at epochs from -10 to +42d with respect to B-band maximum, complementing the existing excellent data sets available for this prototypical Type Ia SN at other wavelengths. The spectra show a time evolution and spectral features characteristic of normal Type Ia SNe, as illustrated by a comparison with SNe 1999ee, 2002bo and 2003du. The broad-band spectral energy distribution (SED) of SN 2005cf is studied in combined ultraviolet (UV), optical and NIR spectra at five epochs between ~8d before and ~10d after maximum light. We also present synthetic spectra of the hydrodynamic explosion model W7, which reproduce the key properties of SN 2005cf not only at UV-optical as previously reported, but also at NIR wavelengths. From the radiative-transfer calculations we infer that fluorescence is the driving mechanism that shapes the SED of SNe Ia. In particular, the NIR part of the spectrum is almost devoid of absorption features, and instead dominated by fluorescent emission of both iron-group material and intermediate-mass elements at pre-maximum epochs, and pure iron-group material after maximum light. A single P-Cygni feature of Mgii at early epochs and a series of relatively unblended Coii lines at late phases allow us to constrain the regions of the ejecta in which the respective elements are abundant. © 2012 The Authors Monthly Notices of the Royal Astronomical Society © 2012 RAS.

The principles and practice of interpreting cardiac rhythm strips: a seven-step model

This open learning zone article examines the cardiac cycle and the interpretation of cardiac rhythm strips. The article begins with a brief revision of related physiology followed by a description of normal sinus rhythm and the main cardiac rhythm abnormalities. The article concludes by providing easy to follow steps for use in the interpretation of cardiac rhythm strips with practice examples presented in the CPD task section.

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.

Interpreting A-level Mathematics grades – as easy as A, B, C?

Many concerns have been expressed that students’ basic mathematical skills have deteriorated during the 1990s and there has been disquiet that current A-level grading does not distinguish adequately between the more able students. This study reports the author’s experiences of teaching maths to large classes of first-year engineering students and aims to enhance understanding of levels of mathematical competence in more recent years. Over the last four years, the classes have consisted of a very large proportion of highly qualified students – about 91% of them had at least grade B in A-level Mathematics. With a small group of students having followed a non-traditional route to university (no A-level maths) and another group having benefitted through taking A-level Further Mathematics at school, the classes have contained a very wide range of mathematical backgrounds. Despite the introductory maths course at university involving mainly repetition of A-level material, students’ marks were spread over a very wide range – for example, A-level Mathematics grade B students have scored across the range 16 – 97%. Analytical integration is the topic which produced the largest variation in performance across the class but, in contrast, the A-level students generally performed well in differentiation. Initial analysis suggests some stability in recent years in the mathematical proficiency of students with a particular A-level Mathematics grade. Allowing choice of applied maths modules as part of the A-level maths qualification increases the variety of students’ mathematical backgrounds and their selection from mechanics, statistics or decision maths is not clear from the final qualification.

Four steps to interpreting arterial blood gases

This article examines acid-base balance and the interpretation of arterial blood gases (ABG). The
article begins with a brief revision of related physiology, followed by a description of the primary
disorders associated with acid-base imbalance. The normal ranges and the significance of
abnormal ABG results are explored. The article concludes by providing an easy to follow four-step
guide to ABG interpretation with practice examples presented in the CPD task section.

Interpreting pedestrian behaviour by visualising and clustering movement data

Recent technological advances have increased the quantity of movement data being recorded. While valuable knowledge can be gained by analysing such data, its sheer volume creates challenges. Geovisual analytics, which helps the human cognition process by using tools to reason about data, offers powerful techniques to resolve these challenges. This paper introduces such a geovisual analytics environment for exploring movement trajectories, which provides visualisation interfaces, based on the classic space-time cube. Additionally, a new approach, using the mathematical description of motion within a space-time cube, is used to determine the similarity of trajectories and forms the basis for clustering them. These techniques were used to analyse pedestrian movement. The results reveal interesting and useful spatiotemporal patterns and clusters of pedestrians exhibiting similar behaviour.

Finding the Most Descriptive Substructures in Graphs with Discrete and Numeric Labels

Many graph datasets are labelled with discrete and numeric attributes. Most frequent substructure discovery algorithms ignore numeric attributes; in this paper we show how they can be used to improve search performance and discrimination. Our thesis is that the most descriptive substructures are those which are normative both in terms of their structure and in terms of their numeric values. We explore the relationship between graph structure and the distribution of attribute values and propose an outlier-detection step, which is used as a constraint during substructure discovery. By pruning anomalous vertices and edges, more weight is given to the most descriptive substructures. Our method is applicable to multi-dimensional numeric attributes; we outline how it can be extended for high-dimensional data. We support our findings with experiments on transaction graphs and single large graphs from the domains of physical building security and digital forensics, measuring the effect on runtime, memory requirements and coverage of discovered patterns, relative to the unconstrained approach.