Analysis of Dependence Tracking Algorithms for Task Dataflow Execution

Processor architectures has taken a turn towards many-core processors, which integrate multiple processing cores on a single chip to increase overall performance, and there are no signs that this trend will stop in the near future. Many-core processors are harder to program than multi-core and single-core processors due to the need of writing parallel or concurrent programs with high degrees of parallelism. Moreover, many-cores have to operate in a mode of strong scaling because of memory bandwidth constraints. In strong scaling increasingly finer-grain parallelism must be extracted in order to keep all processing cores busy.

Task dataflow programming models have a high potential to simplify parallel program- ming because they alleviate the programmer from identifying precisely all inter-task de- pendences when writing programs. Instead, the task dataflow runtime system detects and enforces inter-task dependences during execution based on the description of memory each task accesses. The runtime constructs a task dataflow graph that captures all tasks and their dependences. Tasks are scheduled to execute in parallel taking into account dependences specified in the task graph.

Several papers report important overheads for task dataflow systems, which severely limits the scalability and usability of such systems. In this paper we study efficient schemes to manage task graphs and analyze their scalability. We assume a programming model that supports input, output and in/out annotations on task arguments, as well as commutative in/out and reductions. We analyze the structure of task graphs and identify versions and generations as key concepts for efficient management of task graphs. Then, we present three schemes to manage task graphs building on graph representations, hypergraphs and lists. We also consider a fourth edge-less scheme that synchronizes tasks using integers. Analysis using micro-benchmarks shows that the graph representation is not always scalable and that the edge-less scheme introduces least overhead in nearly all situations.

Algorithms for Self-Healing Networks

Many modern networks are \emph{reconfigurable}, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company's organizational chart; infrastructure networks, such as an airline's transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks. We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call \emph{self-healing}. Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of gaurantees and limitations. We also discuss future directions and theoretical questions we would like to answer. %in the final dissertation that this document is proposed to lead to.

Characterisation of pavement profile heights using accelerometer readings and a combinatorial optimisation technique

Pavement surface profiles induce dynamic ride responses in vehicles which can potentially be used to classify road surface roughness. A novel method is proposed for the characterisation of pavement roughness through an analysis of vehicle accelerations. A combinatorial optimisation technique is applied to the determination of pavement profile heights based on measured accelerations at and above the vehicle axle. Such an approach, using low-cost inertial sensors, would provide an inexpensive alternative to the costly laser-based profile measurement vehicles. The concept is numerically validated using a half-car roll dynamic model to infer measurements of road profiles in both the left and right wheel paths.

Combinatorial Frequency Generation in Quasi-Periodic Stacks of Nonlinear Dielectric Layers

Three-wave mixing in quasi-periodic structures (QPSs) composed of nonlinear anisotropic dielectric layers, stacked in Fibonacci and Thue-Morse sequences, has been explored at illumination by a pair of pump waves with dissimilar frequencies and incidence angles. A new formulation of the nonlinear scattering problem has enabled the QPS analysis as a perturbed periodic structure with defects. The obtained solutions have revealed the effects of stack composition and constituent layer parameters, including losses, on the properties of combinatorial frequency generation (CFG). The CFG features illustrated by the simulation results are discussed. It is demonstrated that quasi-periodic stacks can achieve a higher efficiency of CFG than regular periodic multilayers.