Visible to the public CPS Foundations in Computation and Communication


Modern processor architectures sacrifice timing predictability for increased average computational throughput. Branch prediction, multi-level memory hierarchies, out-of-order execution, and data forwarding all make accurate execution time predictions impossible. As accurate timing predictions are required for task scheduling, our goal is the development of a Precision Timed (PRET) processor, along with the inter-process communication methods and operating system services, which remove many of the sources of timing indeterminacy.

Our PRET architecture retains the deep pipelines of existing architectures, but the data hazards resulting from these pipelines are removed by interleaving instructions from multiple threads. This approach has been implemented in a variant of the OpenFire soft processor, itself an open source clone of the MicroBlaze architecture popular in programmable logic devices. Implementation of the architecture indicates that the PRET modifications increase overall throughput by 70% with only a 35% increase in area. This architecture permits up to 16 threads to time share the processor with scheduling possible on a cycle-by-cycle basis. Scheduling is handled within hardware to dynamically react to changing conditions within a single cycle. Being released open source, it is envisioned that once completed the processor and associated tools will be used by the CPS community in a variant of manners.

CPS applications will require a network consisting of multiple computational-sensing nodes scattered throughout an area of interest. We proposed a secure, power efficient, and latency-limited communication scheme for CPS networks. This communication scheme consists of 1) a multipath multicast algorithm that efficiently relays information to a group of CPS nodes and 2) a data acquisition technique that performs in-network processing to reduce large streams of raw data into useful aggregated information. Our proposed algorithm was designed with simplicity, energy efficiency, and reliability in mind. The proposed multipath multicast algorithm combines the best of multicasting, which we have based on multi- path MAODV, with the best of distributed source coding (DSC) which incorporates and uses ideas from rateless coding. By adding DSC using rateless codes on top of multi-path MAODV, the transmission load is distributed more evenly among the CPS nodes and the communication is more robust against link losses.

For data aggregation, we have developed a distributed compression technique that has low decoding and encoding computational complexity. The proposed scheme exploits both temporal and spatial correlations between nodes in distributed sensor networks. For spatial correlation, we propose a compressive sensing (CS) technique that uses rateless coding and random walk. The rateless coding generates a random measuring matrix that is independent of routing algorithms and is incoherent with any sparsity matrix with high probability. Equipping the CS-based algorithm with random walk helps collecting sufficient number of sensor readings while combining them together without significantly increasing the inter-communication cost.

In case of events occurring, the values of both spatial and temporal might change and the compression technique needs to adjust its rate to the changes automatically. Our proposed algorithm reactively changes its compression rate to adapt to the variations in the correlations. The number of measurements is adjusted based on the temporal correlations among sensors. When sensor readings are changing slowly, the compression rate is improved by reducing the number of measurements. In case of any event that significantly changes the signal readings, the algorithm generates more measurements to guarantee recovery of signal at the base station. The experimental results done over data gathered by 64 temperature sensors and also Matlab simulation results reveal that our algorithm is flexible to adapt the variations in the sensor readings, while it keeps the compression rate the minimum. The focus of our work other than exploiting the spatial and temporal correlations is to achieve a high compression rate while keeping the decoding computational complexity. In addition to the above findings, we have also investigated the application of our proposed CS scheme in the following fields: Image processing, Smart healthcare (monitoring well-being of post-stroke patients), and Cognitive radio.

Award ID:

Creative Commons 2.5

Other available formats:

CPS Foundations in Computation and Communication