A deadlock-free routing algorithm for dynamically reconfigurable Networks-on-Chip

We address routing in Networks-On-Chip (NoC) architectures that use irregular mesh topologies with Long-Range Links (LRL). These topologies create difficult conditions for routing algorithms, as standard algorithms assume a static, regular link structure and exploit the uniformity of regular meshes to avoid deadlock and maintain routability. We present a novel routing algorithm that can cope with these irregular topologies and adapt to run-time LRL insertion and topology reconfiguration. Our approach to accommodate dynamic topology reconfiguration is to use a new technique that decomposes routing relations into two stages: the calculation of output ports on the current minimal path and the application of routing restrictions designed to prevent deadlock. In addition, we present a selection function that uses local topology data to adaptively select optimal paths.The routing algorithm is shown to be deadlock-free, after which an analysis of all possible routing decisions in the region of an LRL is carried out. We show that the routing algorithm minimises the cost of sub-optimally placed LRL and display the hop savings available. When applied to LRLs of less than seven hops, the overall traffic hop count and associated routing energy cost is reduced. In a simulated 8 × 8 network the total input buffer usage across the network was reduced by 6.5%.     

Modeling the glucose regulatory system in extreme preterm infants

Background

Premature infants represent a significant proportion of the neonatal intensive care population. Blood glucose homeostasis in this group is often disturbed by immaturity of endogenous regulatory systems and the stress of their condition. Hypo- and hyperglycemia are frequently reported in very low birth weight infants, and more mature infants often experience low levels of glycemia. A model capturing the unique fundamental dynamics of the neonatal glucose regulatory system could be used to develop better blood glucose control methods.

Methods

A metabolic system model is adapted from adult critical care to the unique physiological case of the neonate. Integral-based fitting methods were used to identify time-varying insulin sensitivity and non-insulin mediated glucose uptake profiles. The clinically important predictive ability of the model was assessed by assuming insulin sensitivity was constant over prediction intervals of 1, 2 and 4 h forward and comparing model-simulated versus actual clinical glucose values for all recorded interventions. The clinical data included 1091 glucose measurements over 3567 total patient hours, along with all associated insulin and nutritional infusion data, for N = 25 total cases. Ethics approval was obtained from the Upper South A Regional Ethics Committee for this study.

Results

The identified model had a median absolute percentage error of 2.4% [IQR: 0.9-4.8%] between model-fitted and clinical glucose values. Median absolute prediction errors at 1-, 2- and 4-h intervals were 5.2% [IQR: 2.5-10.3%], 9.4% [IQR: 4.5-18.4%] and 13.6% [IQR: 6.3-27.6%] respectively.

Conclusions

The model accurately captures and predicts the fundamental dynamic behaviors of the neonatal metabolism well enough for effective clinical decision support in glycemic control. The adaptation from adult to a neonatal case is based on the data from the literature. Low prediction errors and very low fitting errors indicate that the fundamental dynamics of glucose metabolism in both premature neonates and critical care adults can be described by similar mathematical models.     

Subgraphs of 4-Regular Planar Graphs

We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^2.5) and can be used to find an explicit 4-regular planar graph G⊃H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.     

From individuals to populations: A mean field semantics for process algebra

A new semantics in terms of mean field equations is presented for WSCCS (Weighted Synchronous Calculus of Communicating Systems). The semantics captures the average behaviour of the system over time, but without computing the entire state space, therefore avoiding the state space explosion problem. This allows easy investigation of models with large numbers of components. The new semantics is shown to be equivalent to the standard Discrete Time Markov Chain semantics of WSCCS as the number of processes tends to infinity. The method of deriving the semantics is illustrated with examples drawn from biology and from computing.     

Decision-Centric Information Monitoring

We are interested in information management for decision support applications, especially those that monitor distributed, heterogeneous databases to assess time-critical decisions. Users of such applications can easily be overwhelmed with data that may change rapidly, may conflict, and may be redundant. Developers are faced with a dilemma: either filter out most information and risk excluding critical items, or gather possibly irrelevant or redundant information, and overwhelm the decision maker. This paper describes a solution to this dilemma called decision-centric information monitoring (DCIM). First, we observe that decision support systems should monitor only information that can potentially change some decision. We present an architecture for DCIM that meets the requirements implied by this observation. We describe techniques for identifying the highest value information to monitor and techniques for monitoring that information despite autonomy, distribution, and heterogeneity of data sources. Finally, we present lessons learned from building LOOKOUT, which is to our knowledge the first implementation of a top-to-bottom system performing decision-centric information monitoring.     

A forward-constrained regression algorithm for sparse kernel density estimation.

Using the classical Parzen window (PW) estimate as the target function, the sparse kernel density estimator is constructed in a forward-constrained regression (FCR) manner. The proposed algorithm selects significant kernels one at a time, while the leave-one-out (LOO) test score is minimized subject to a simple positivity constraint in each forward stage. The model parameter estimation in each forward stage is simply the solution of jackknife parameter estimator for a single parameter, subject to the same positivity constraint check. For each selected kernels, the associated kernel width is updated via the Gauss-Newton method with the model parameter estimate fixed. The proposed approach is simple to implement and the associated computational cost is very low. Numerical examples are employed to demonstrate the efficacy of the proposed approach.     

A comparison of the perceptual benefits of linear perspective and physically-based illumination for display of dense 3D streamtubes

Large datasets typically contain coarse features comprised of finer sub-features. Even if the shapes of the small structures are evident in a 3D display, the aggregate shapes they suggest may not be easily inferred. From previous studies in shape perception, the evidence has not been clear whether physically-based illumination confers any advantage over local illumination for understanding scenes that arise in visualization of large data sets that contain features at two distinct scales. In this paper we show that physically-based illumination can improve the perception for some static scenes of complex 3D geometry from flow fields. We perform human-subjects experiments to quantify the effect of physically-based illumination on participant performance for two tasks: selecting the closer of two streamtubes from a field of tubes, and identifying the shape of the domain of a flow field over different densities of tubes. We find that physically-based illumination influences participant performance as strongly as perspective projection, suggesting that physically-based illumination is indeed a strong cue to the layout of complex scenes. We also find that increasing the density of tubes for the shape identification task improved participant performance under physically-based illumination but not under the traditional hardware-accelerated illumination model.     

Graphical histories for visualization: supporting analysis, communication, and evaluation

Interactive history tools, ranging from basic undo and redo to branching timelines of user actions, facilitate iterative forms of interaction. In this paper, we investigate the design of history mechanisms for information visualization. We present a design space analysis of both architectural and interface issues, identifying design decisions and associated trade-offs. Based on this analysis, we contribute a design study of graphical history tools for Tableau, a database visualization system. These tools record and visualize interaction histories, support data analysis and communication of findings, and contribute novel mechanisms for presenting, managing, and exporting histories. Furthermore, we have analyzed aggregated collections of history sessions to evaluate Tableau usage. We describe additional tools for analyzing users’ history logs and how they have been applied to study usage patterns in Tableau.     

Rapid graph layout using space filling curves

Network data frequently arises in a wide variety of fields, and node-link diagrams are a very natural and intuitive represen- tation of such data. In order for a node-link diagram to be effective, the nodes must be arranged well on the screen. While many graph layout algorithms exist for this purpose, they often have limitations such as high computational complexity or node colocation. This paper proposes a new approach to graph layout through the use of space filling curves which is very fast and guarantees that there will be no nodes that are colocated. The resulting layout is also aesthetic and satisfies several criteria for graph layout effectiveness.