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.

Brief announcement: Maintaining large dense subgraphs on dynamic networks

In distributed networks, some groups of nodes may have more inter-connections, perhaps due to their larger bandwidth availability or communication requirements. In many scenarios, it may be useful for the nodes to know if they form part of a dense subgraph, e.g., such a dense subgraph could form a high bandwidth backbone for the network. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs (subgraphs that the member nodes are aware of). The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model in the sense that only messages of O(log n) size are permitted, where n is the number of nodes in the network. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that approximate both the densest subgraph, i.e., the subgraph of the highest density in the network, and the at-least-k-densest subgraph (for a given parameter k), i.e., the densest subgraph of size at least k. We give a (2 + e)-approximation algorithm for the densest subgraph problem. The at-least-k-densest subgraph is known to be NP-hard for the general case in the centralized setting and the best known algorithm gives a 2-approximation. We present an algorithm that maintains a (3+e)-approximation in our distributed, dynamic setting. Our algorithms run in O(Dlog n) time. © 2012 Authors.

The Forgiving Graph:A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network. © Springer-Verlag 2012.

Channel Time Allocation PSO for Gigabit Multimedia Wireless Networks

This article introduces a resource allocation solution capable of handling mixed media applications within the constraints of a 60 GHz wireless network. The challenges of multimedia wireless transmission include high bandwidth requirements, delay intolerance and wireless channel availability. A new Channel Time Allocation Particle Swarm Optimization (CTA-PSO) is proposed to solve the network utility maximization (NUM) resource allocation problem. CTA-PSO optimizes the time allocated to each device in the network in order to maximize the Quality of Service (QoS) experienced by each user. CTA-PSO introduces network-linked swarm size, an increased diversity function and a learning method based on the personal best, Pbest, results of the swarm. These additional developments to the PSO produce improved convergence speed with respect to Adaptive PSO while maintaining the QoS improvement of the NUM. Specifically, CTA-PSO supports applications described by both convex and non-convex utility functions. The multimedia resource allocation solution presented in this article provides a practical solution for real-time wireless networks.

Modified Thomson spectrometer design for high energy, multi-species ion sources

A modification to the standard Thomson parabola spectrometer is discussed, which is designed to measure high energy (tens of MeV/nucleon), broad bandwidth spectra of multi-species ions accelerated by intense laser plasma interactions. It is proposed to implement a pair of extended, trapezoidal shaped electric plates, which will not only resolve ion traces at high energies, but will also retain the lower energy part of the spectrum. While a longer (along the axis of the undeflected ion beam direction) electric plate design provides effective charge state separation at the high energy end of the spectrum, the proposed new trapezoidal shape will enable the low energy ions to reach the detector, which would have been clipped or blocked by simply extending the rectangular plates to enhance the electrostatic deflection.

The effect of the spectral distribution of wave energy on the performance of a bottom hinged flap type wave energy converter

The power output from a wave energy converter is typically predicted using experimental and/or numerical modelling techniques. In order to yield meaningful results the relevant characteristics of the device, together with those of the wave climate must be modelled with sufficient accuracy.

The wave climate is commonly described using a scatter table of sea states defined according to parameters related to wave height and period. These sea states are traditionally modelled with the spectral distribution of energy defined according to some empirical formulation. Since the response of most wave energy converters vary at different frequencies of excitation, their performance in a particular sea state may be expected to depend on the choice of spectral shape employed rather than simply the spectral parameters. Estimates of energy production may therefore be affected if the spectral distribution of wave energy at the deployment site is not well modelled. Furthermore, validation of the model may be affected by differences between the observed full scale spectral energy distribution and the spectrum used to model it.

This paper investigates the sensitivity of the performance of a bottom hinged flap type wave energy converter to the spectral energy distribution of the incident waves. This is investigated experimentally using a 1:20 scale model of Aquamarine Power’s Oyster wave energy converter, a bottom hinged flap type device situated at the European Marine Energy Centre (EMEC) in approximately 13m water depth. The performance of the model is tested in sea states defined according to the same wave height and period parameters but adhering to different spectral energy distributions.

The results of these tests show that power capture is reduced with increasing spectral bandwidth. This result is explored with consideration of the spectral response of the device in irregular wave conditions. The implications of this result are discussed in the context of validation of the model against particular prototype data sets and estimation of annual energy production.

Performance enhancement of a wideband spiral antenna using a stepped ground plane

This study presents the use of a stepped ground plane as a means to increase the gain and front-to-back ratio of an Archimedean spiral which operates in the frequency range 3–10 GHz. The backing structure is designed to optimize the antenna performance in discrete 1 GHz bands by placing each of the eight metal steps one quarter wavelength below the corresponding active regions of the spiral. Simulated and experimental results show that this type of ground plane can be designed to enhance the antenna performance over the entire 105% operating bandwidth of the spiral.

Voltage Controlled Intertwined Spiral Arrays for Reconfigurable Metasurfaces

Reconfigurable bistate metasurfaces composed of interwoven spiral arrays with embedded pin diodes are proposed for single and dual polarisation operation. The switching capability is enabled by pin diodes that change the array response between transmission and reflection modes at the specified frequencies. The spiral conductors forming the metasurface also supply the dc bias for controlling pin diodes, thus avoiding the need of additional bias circuitry that can cause parasitic interference and affect the metasurface response. The simulation results show that proposed active metasurfaces exhibit good isolation between transmission and reflection states, while retaining excellent angular and polarisation stability with the large fractional bandwidth (FBW) inherent to the original passive arrays. © 2014 A. Vallecchi et al.

Device-Free Person Detection and Ranging in UWB Networks

We present a novel device-free stationary person detection and ranging method, that is applicable to ultra-wide bandwidth (UWB) networks. The method utilizes a fixed UWB infrastructure and does not require a training database of template waveforms. Instead, the method capitalizes on the fact that a human presence induces small low-frequency variations that stand out against the background signal, which is mainly affected by wideband noise. We analyze the detection probability, and validate our findings with numerical simulations and experiments with off-the-shelf UWB transceivers in an indoor environment. © 2007-2012 IEEE.

Hybrid address spaces: A methodology for implementing scalable high-level programming models on non-coherent many-core architectures

This paper introduces hybrid address spaces as a fundamental design methodology for implementing scalable runtime systems on many-core architectures without hardware support for cache coherence. We use hybrid address spaces for an implementation of MapReduce, a programming model for large-scale data processing, and the implementation of a remote memory access (RMA) model. Both implementations are available on the Intel SCC and are portable to similar architectures. We present the design and implementation of HyMR, a MapReduce runtime system whereby different stages and the synchronization operations between them alternate between a distributed memory address space and a shared memory address space, to improve performance and scalability. We compare HyMR to a reference implementation and we find that HyMR improves performance by a factor of 1.71× over a set of representative MapReduce benchmarks. We also compare HyMR with Phoenix++, a state-of-art implementation for systems with hardware-managed cache coherence in terms of scalability and sustained to peak data processing bandwidth, where HyMR demon- strates improvements of a factor of 3.1× and 3.2× respectively. We further evaluate our hybrid remote memory access (HyRMA) programming model and assess its performance to be superior of that of message passing.

Millimeter-wave communications for 5G: fundamentals: Part I [Guest Editorial]

The widespread availability and demand for multimedia capable devices and multimedia content have fueled the need for high-speed wireless connectivity beyond the capabilities of existing commercial standards. While fiber optic data transfer links can provide multigigabit- per-second data rates, cost and deployment are often prohibitive in many applications. Wireless links, on the contrary, can provide a cost-effective fiber alternative to interconnect the outlining areas beyond the reach of the fiber rollout. With this in mind, the ever increasing demand for multi-gigabit wireless applications, fiber segment replacement mobile backhauling and aggregation, and covering the last mile have posed enormous challenges for next generation wireless technologies. In particular, the unbalanced temporal and geographical variations of spectrum usage along with the rapid proliferation of bandwidth- hungry mobile applications, such as video streaming with high definition television (HDTV) and ultra-high definition video (UHDV), have inspired millimeter-wave (mmWave) communications as a promising technology to alleviate the pressure of scarce spectrum resources for fifth generation (5G) mobile broadband.

Periodic Arrays of Interwoven Quadrifilar Spirals on Ferrite Substrates

The properties of metasurfaces composed of doubly periodic arrays of interwoven quadrifilar spiral conductors on magnetized ferrite substrates have been investigated with the aid of the full-wave electromagnetic simulator. The effects of incident wave polarization and ferrite magnetization on the scattering characteristics have been analysed at both normal and in-plane dc magnetic bias. The features of the fundamental topological resonances in the interwoven spiral arrays on ferrite substrates are illustrated by the simulation results and the effects of ferrite gyrotropy and dispersion on the array resonance response and fractional bandwidth are discussed.

Difference equation approach to two-thermocouple sensor characterization in constant velocity flow environments

Thermocouples are one of the most popular devices for temperature measurement due to their robustness, ease of manufacture and installation, and low cost. However, when used in certain harsh environments, for example, in combustion systems and engine exhausts, large wire diameters are required, and consequently the measurement bandwidth is reduced. This article discusses a software compensation technique to address the loss of high frequency fluctuations based on measurements from two thermocouples. In particular, a difference equation (DE) approach is proposed and compared with existing methods both in simulation and on experimental test rig data with constant flow velocity. It is found that the DE algorithm, combined with the use of generalized total least squares for parameter identification, provides better performance in terms of time constant estimation without any a priori assumption on the time constant ratios of the thermocouples.

Polarisation independent resistively loaded frequency selective surface absorber with optimum oblique incidence performance

This study presents the design of a thin electromagnetic absorber which exhibits radar backscatter suppression that is independent of the wave polarisation at large incidence angles. The structure consists of a metal backed printed frequency selective surface (FSS), with resistors placed across narrow gaps inserted in the middle of each of the four sides of the conductor loops. The geometry of the periodic array and the value of the vertical and horizontal resistor pairs are carefully chosen to present a real impedance of 377 Ω at the centre operating frequency for both TE and TM polarised waves. Angular sensitivity and reflectivity bandwidth have been investigated for FSS absorber designs with thicknesses of 1, 2 and 3 mm. Each of the three structures was optimised to work at a centre frequency of 10 GHz and an incident angle of 45°. The design methodology is verified by measuring the radar backscatter suppression from a 3 mm (l / 10) thick screen in the frequency range 8–12 GHz. The absorber construction was simplified by filling the four metal gaps in each unit cell with shielding paint, and selecting the ink thickness to give the two required surface resistance values.

Ultrasensitive non-resonant detection of ultrasound with plasmonic metamaterials

Optical sensors for ultrasound detection provide high sensitivity and bandwidth, essential for photoacoustic imaging in clinical diagnostics and biomedical research. Implementing plasmonic metamaterials in a non-resonant regime facilitates sub-nanosecond, highly sensitive detectors while eliminating cumbersome optical alignment necessary for resonant sensors.