An effective and robust time synchronization scheme is essential for many wireless sensor network (WSN) applications. Conventional synchronization methods assume the use of highly accurate crystal oscillators (10-100 ppm) for synchronization, only correcting for small errors. This paper suggests a novel method for time synchronization in a multihop, fully-distributed WSN using imprecise CMOS oscillators (up to 15 000 ppm). The DiStiNCT technique is power-efficient, computationally simple, and robust to packet loss and complex topologies. Effectiveness has been demonstrated in simulations of fully connected, grid, and unidirectional ring topologies. The method has been validated in hardware on a grid of nine sensor nodes, synchronizing to within a mean error of 6.6 ms after 40 iterations.

SpiNNaker is a multi-core computing engine, with a bespoke and specialised communication infrastructure that supports almost perfect scalability up to a hard limit of 216× 18 = 1,179,648 cores. This remarkable property is achieved at the cost of ignoring memory coherency, global synchronisation and even deterministic message passing, yet it is still possible to perform meaningful computations. Whilst we have yet to assemble the full machine, the scalability properties make it possible to demonstrate the capabilities of the machine whilst it is being assembled; the more cores we connect, the larger the problems become that we are able to attack. Even with isolated printed circuit boards of 864 cores, interesting capabilities are emerging. This paper is the third of a series charting the development trajectory of the system. In the first two, we outlined the hardware build. Here, we lay out the (rather unusual) low-level foundation software developed so far to support the operation of the machine.

In this work, we present the design, development, and evaluation of a real-time target tracking system for wireless embedded nodes, capable of effectively tracking manoeuvring targets. The proposed tracking system is designed to operate solely on range measurements obtained with the use of a two-way time-of-flight method without the need for additional hardware being incorporated in the nodes. To address the challenge of coping with manoeuvring targets, the tracking problem is formulated as a dynamical estimation problem where an adaptive multiple-model approach is employed to represent the motion pattern of manoeuvring targets. The ranging observations are produced in real time and used as inputs to a particle filter algorithm that produces the estimates of the target's kinematic variables. Simulations are provided to assess the effect of several factors on the system's performance. Ultimately, the entire system is implemented on commercially available hardware and tested in an outdoor deployment. A total of 25 experiments demonstrate an average RMS accuracy of 2.6 m for position and 1.9 m/s for velocity, in a 15 m × 15 m area. Such performance, which is additionally confirmed from simulation results, reveals the potential of the proposed range-only system in application scenarios where real-time tracking of mobile targets is needed.

As part of our effort to parallelised SPICE simulations over multiple FPGAs, we present a parallel FPGA implementation for a sparse matrix solver optimised for execution on a single FPGA node. Our approach combines static pivoting with symbolic analysis to compute an accurate task flow-graph which efficiently exploits parallelism at multiple granularities and sustains high floating-point data rates. The sparse matrix solver is tested with circuit simulation matrices from the University of Florida matrix collection. We report a 10-30× speedup compared to a 2.4 GHz Intel Core Duo processor running UMFPACK, a state-of-the-art sparse matrix solver.

In this paper we propose a tracking system for wireless sensor networks, which operates on accumulated ranging data from a number of anchor sensor nodes in order to infer the trace and other kinematic characteristics of a mobile target. The nonlinear nature of the “tracking with range-only measureme

We present a parallel version of Viterbi's decoding procedure, for which we are able to demonstrate that the resultant task graph has a restricted complexity in the number of communications to or from and the processor cannot exceed 4 for BCH codes. The resulting algorithm works in lock step making it suitable for implementation on a systolic processor array, which we have implemented on a field programmable gate array and demonstrate the perfect scaling of the algorithm for two exemplar BCH codes. The parallelisation strategy is applicable to all cyclic codes and convolution codes. We also present a novel method for generating the state transition diagrams for these codes.

Abstract In this paper we express the Viterbi algorithm as a matrix–vector reduction in which multiplication is replaced by addition and addition by minimization. The resulting algorithm is then readily parallelized in a form suitable for implementation on a systolic processor array. We describe the algorithm for Bose–Chaudhuri–Hocquenghem (BCH) codes which have a task graph with its valence restricted to four inputs and four outputs. The method is also applicable to convolution codes, but the complexity of the task graph increases with the number of input bits for these codes. Results for BCH codes are given for two general purpose parallel machines, an IBM SP2 and a Meiko CS2. Copyright © 2001 John Wiley & Sons, Ltd.

Abstract In this paper, we describe various methods of deriving a parallel version of Stone's Strongly Implicit Procedure (SIP) for solving sparse linear equations arising from finite difference approximation to partial differential equations (PDEs). Sequential versions of this algorithm have been very successful in solving semi‐conductor, heat conduction and flow simulation problems and an efficient parallel version would enable much larger simulations to be run. An initial investigation of various parallelizing strategies was undertaken using a version of high performance Fortran (HPF) and the best methods were reprogrammed using the MPI message passing libraries for increased efficiency. Early attempts concentrated on developing a parallel version of the characteristic wavefront computation pattern of the existing sequential SIP code. However, a red‐black ordering of grid points, similar to that used in parallel versions of the Gauss–Seidel algorithm, is shown to be far more efficient. The results of both the wavefront and red‐black MPI based algorithms are reported for various size problems and number of processors on a sixteen node IBM SP2. Copyright © 2001 John Wiley & Sons, Ltd.

In the paper the authors present the defininition and implementation of a concurrent language MP (message passer) which is aimed at programming embedded multi-microprocessor systems. The novel features of the language include the ability to program and develop the entire distributed system as a single unit, and the provision of simple restricted concurrency constructs that make such systems modular and deadlock free. MP programs are invariant with respect to the characteristics of a particular target machine, for instance, the number of processors, and their mutual connectivity. Programs written in MP can be transformed to a restricted set of communicating sequential processes (CSP), in which particular specifications can be shown to be satisfied. The restricted model of concurrency does not prevent the language being able to express all of the known course-grained parallel programming paradigms. However, the structured nature of the code makes the model particularly attractive in concurrent embedded systems, where deadlock freedom and program correctness are prime issues. An MP program is a collection of objects which execute concurrently, maintain their own local state and connect with other objects via bound variables. Explicit communication between objects is totally transparent to the application programmer. A compiler for the language has been built and a multiprocessor run-time environment has been established for any system with a C compiler and the message-passing standard MPI library. Several applications have been tested, ranging from a clocked digital circuit simulation, to a simple event-driven process controller.