DP-Fair: a unifying theory for optimal hard real-time multiprocessor scheduling

We consider the problem of optimal real-time scheduling of periodic and sporadic tasks on identical multiprocessors. A number of recent papers have used the notions of fluid scheduling and deadline partitioning to guarantee optimality and improve performance. This article develops a unifying theory with the DP-Fair scheduling policy and examines how it overcomes problems faced by greedy scheduling algorithms. In addition, we present DP-Wrap, a simple DP-Fair scheduling algorithm which serves as a least common ancestor to other recent algorithms. The DP-Fair scheduling policy is extended to address the problem of scheduling sporadic task sets with arbitrary deadlines.     

Bidirectional Grammars for Machine-Code Decoding and Encoding

Binary analysis, which analyzes machine code, requires a decoder for converting bits into abstract syntax of machine instructions. Binary rewriting requires an encoder for converting instructions to bits. We propose a domain-specific language that enables the specification of both decoding and encoding in a single bidirectional grammar. With dependent types, a bigrammar enables the extraction of an executable decoder and encoder as well as a correctness proof showing their consistency. The bigrammar DSL is embedded in Coq with machine-checked proofs. We have used the bigrammar DSL to specify the decoding and encoding of subsets of the x86-32 and MIPS instruction sets. We have also extracted an executable decoder and encoder from the x86 bigrammar with competitive performance.     

Regularity of bondgraphs and directed bondgraphs

This article concludes the presentation of a theory for the mathematical foundations that tacitly support the construction and manipulation of a bondgraph model (BGM) of a spatially discrete physical system. A di-bondgraph $\overline{B}$ consists of an underlying bondgraph B, a diagram with only junctions and bonds, and directions assigned to the bonds. $\overline{B}$ generates a pair of integral chain group representations of its dual cycle and cocycle matroids, which encapsulate the structural relationships in the system. The important class of regular (di-)bondgraphs can be identified using the concepts of regular matroids and chain groups. Bond and junction elimination operations are described to create a sub-diagram called a minor, reflecting the matroid operations of contraction and deletion of matroid elements. This provides a device for manipulating a (di-)bondgraph diagram to test for a redundant internal junction, or for a non-regular matroid. A di-bondgraph $\overline{B}$ induces an orientation on its cycle and cocycle matroid; if $\overline{B}$ is regular it has the same matroids as its underlying bondgraph B, and the orientation defined by $\overline{B}$ is a signing of these. In a BGM the integral cycles and cocycles obtained from the dual chain groups may be used to express spatial constraints between variables, signed quantities being essential to represent polarities required by physical measurements. A discussion is focused on several important issues: a rationale for excluding TF and GY elements in a purely combinatorial analysis, maintaining the symmetry of duality which is so central to the bondgraph concept; the independent influence of bond directions on structure (matroids) and orientation (chain groups); and the relevance of non-regular di-bondgraphs in practical modelling. In conclusion, an argument is made for the essential practical equivalence of bondgraph and graph-theoretic modelling (GTM). Any technique, formulation, computer software, algorithm, or application expressed in terms of one method will have a parallel version in terms of the other. Moreover, conversion between the BGM and GTM views ought to be a conceptually and computationally trivial exercise.     

Cost-driven autonomous mobility

Autonomous mobile programs (AMPs) offer a novel decentralised load management technology where periodic use is made of cost models to decide where to execute in a network. In this paper we demonstrate how sequential programs can be automatically converted into AMPs. The AMPs are generated by an automatic continuation cost analyser that replaces iterations with costed autonomous mobility skeletons (CAMS) that encapsulate autonomous mobility. The CAMS cost model uses an entirely novel continuation cost semantics to predict both the cost of the current iteration and the continuation cost of the remainder of the program. We show that CAMS convey significant performance advantages, e.g. reducing execution time by up to 53%; that the continuation cost models are consistent with the existing AMP cost models; and that the overheads of collecting and utilising the continuation costs are relatively small. We discuss example AMPs generated by the analyser and demonstrate that they have very similar performance to hand-costed CAMS programs.     

Blind camera fingerprinting and image clustering

Previous studies have shown how to "fingerprint" a digital camera given a set of images known to come from the camera. A clustering technique is proposed to construct such fingerprints from a mixed set of images, enabling identification of each image's source camera without any prior knowledge of source.     

Automatic high-dynamic range image generation for dynamic scenes.

Automatic high-dynamic range image generation from low-dynamic range images offers a solution to conventional methods, which require a static scene. The method consists of two modules: a camera-alignment module and a movement detector, which removes the ghosting effects in the HDRI created by moving objects.     

Solving polynomial systems via symbolic-numeric reduction to geometric involutive form

We briefly survey several existing methods for solving polynomial systems with inexact coefficients, then introduce our new symbolic-numeric method which is based on the geometric (Jet) theory of partial differential equations. The method is stable and robust. Numerical experiments illustrate the performance of the new method.     

Human Action Recognition by Semilatent Topic Models

We propose two new models for human action recognition from video sequences using topic models. Video sequences are represented by a novel “bag-of-words” representation, where each frame corresponds to a “word.” Our models differ from previous latent topic models for visual recognition in two major aspects: first of all, the latent topics in our models directly correspond to class labels; second, some of the latent variables in previous topic models become observed in our case. Our models have several advantages over other latent topic models used in visual recognition. First of all, the training is much easier due to the decoupling of the model parameters. Second, it alleviates the issue of how to choose the appropriate number of latent topics. Third, it achieves much better performance by utilizing the information provided by the class labels in the training set. We present action classification results on five different data sets. Our results are either comparable to, or significantly better than previously published results on these data sets.