Remote IoT devices face significant security risks due to their inherent physical vulnerability. An adversarial actor with sufficient capability can monitor the devices or exfiltrate data to access sensitive information. Remotely deployed devices such as sensors need enhanced resilience against memory leakage if performing privileged tasks. To increase the security and trust of these devices we present a novel framework implementing a privacy homomorphism which creates sensor data directly in an encoded format. The sensor data is permuted at the time of creation in a manner which appears random to an observer. A separate secure server in communication with the device provides necessary information which allows the device to perform processing on the encoded data but does not allow decoding of the result. The device transmits the encoded results to the secure server which maintains the ability to interpret the results. In this article, we show how this framework works for an image sensor calculating differences between a stream of images, with initial results showing an overhead as low as only 266% in terms of throughput when compared to computing on standard unencoded numbers such as two’s complement. We further show 5,000× speedup over a recent homomorphic encryption ASIC.

Deployed embedded devices face security risks due to increased ease of physical access to the devices by unauthorized users. Capable adversaries can intercept a device to recover the data in memory, including results of performed sensitive computations. Device owners require data confidentiality on their physically insecure devices. To satisfy this goal we implement a novel method, COPPER (Computation Obfuscation by Producing Permutations for Encoding Randomly), to create data which never exists on the device digitally in plaintext format and which is subsequently used for computation. In this paper we utilize COPPER to calculate a moving average computation on encoded data.1

This paper surveys some prior work regarding attack models in a cyber-physical system and discusses the potential benefits. For comparison, the full paper will model a bad data injection attack scenario in power grid using the surveyed prior work.

As CMOS technology driven by Moore's law has approached device sizes in the range of 5-20 nm, noise immunity of such future technology nodes is predicted to decrease considerably, eventually affecting the reliability of computations through them. A shift in the design paradigm is expected from 100% accurate computations to probabilistic computing with accuracy dependent on the target application or circuit specifications. One model developed for CMOS technology that emulates the erroneous behavior predicted is termed probabilistic CMOS (PCMOS). In this paper, we propose a PCMOS-based architecture implementation for traditional motion estimation algorithms and show that up to 57% energy savings are possible for different existing motion estimation algorithms. Furthermore, algorithmic modifications are proposed that can enhance the energy savings to 70% with a PCMOS architectural implementation. About 1.8-5 dB improvement in peak signal-to-noise ratio under energy savings of 57% to 70% for two different motion estimation algorithms is shown, establishing the resilience of the proposed algorithm to probabilistic computing over the comparable conventional algorithm.

No abstract available.

Quick and accurate error-rate prediction of Probabilistic CMOS (PCMOS) circuits is crucial for their systematic design and performance evaluation. While still in the early stage of research, PCMOS has shown potential to drastically reduce energy consumption at a cost of increased errors. Recently, a methodology has been proposed which could predict the error rates of cascade structures of blocks in PCMOS. This methodology requires error rates of unique blocks to predict the error rates of multiblock cascade structures composed of these unique blocks. In this article we present a new model for characterization of probabilistic circuits/blocks and present a procedure to find and characterize unique circuits/blocks. Unlike prior approaches, our new model distinguishes distinct filtering effects per output, thereby improving prediction accuracy by an average of 95% over the prior art by Palem and coauthors. Furthermore, we show two models where our new model with three stages is 18% more accurate, on average, than our simpler two-stage model. We apply our proposed models to Ripple Carry Adders and Wallace Tree Multipliers and show that using our models, the methodology of cascade structures can predict error rates of PCMOS circuits with reasonable accuracy (within 9%) in PCMOS for uniform voltages as well as multiple voltages. Finally, our approach takes seconds of simulation time whereas using HSPICE would take days of simulation time.

Highly scaled CMOS devices are predicted to show probabilistic behavior due to process variations or the presence of noise sources such as thermal noise. Past research dealing with characterizing CMOS devices with probabilistic behavior has shown that computing via these devices, termed probabilistic computing, can help realize highly efficient circuits in terms of energy consumption. In this paper, we explore low power motion estimation, specifically low power hierarchical search algorithms for motion estimation, in the context of probabilistic computing. With the fault tolerant algorithm design (MC-TSS) proposed in this paper, we show that energy savings that can be realized with probabilistic computing increase to 70% versus 57% with the conventional algorithm (TSS), with minor impact on the quality of motion estimation. Furthermore, a 1.8 dB improvement in PSNR under the same energy savings of 70% for both algorithms is shown establishing the superior resilience of the proposed algorithm to probabilistic computing over the conventional algorithm.

Approximate arithmetic is a promising, new approach to low-energy designs while tackling reliability issues. We present a method to optimally distribute a given energy budget among adders in a dataflow graph so as to minimize expected errors. The method is based on new formal mathematical models and algorithms, which quantitatively characterize the relative importance of the adders in a circuit. We demonstrate this method on a finite impulse response filter and a Fast Fourier Transform. The optimized energy distribution yields 2.05X lower error in a 16-point FFT and images with SNR 1.42X higher than those achieved by the best previous approach.

The wide applications of cyber-physical systems (CPS) call for effective design strategies that optimize the performance of both computing units and physical plants.We study the task scheduling problem for a class of CPS whose behaviors are regulated by feedback control laws. We co-design the control law and the task scheduling algorithm for predictable performance and power consumption for both the computing and the physical systems. We use a typical example, multiple inverted pendulums controlled by one processor, to illustrate our method.

In this paper, we propose an approach to estimate the worst-case response time (WCRT) of each task in a preemptive multitasking single-processor real-time system utilizing an L1 cache. The approach combines intertask cache-eviction analysis and intratask cache-access analysis to estimate the number of cache lines that can possibly be evicted by the preempting task and also be accessed again by the preempted task after preemptions (thus requiring the preempted task to reload the cache line(s)). This cache-reload delay caused by preempting task(s) is then incorporated into WCRT analysis. Three sets of applications with up to six concurrent tasks running are used to test our approach. The experimental results show that our approach can tighten the WCRT estimate by up to 32% (1.4X) over prior state-of-the-art.

For the most recent CMOS feature sizes (e.g., 90nm and 65nm), leakage power dissipation has become an overriding concern for VLSI circuit designers. ITRS reports that leakage power dissipation may come to dominate total power consumption as presented in ITRS by Semiconductor Industry Association, 2005. We propose a novel approach, named "sleepy keeper," which reduces leakage current while saving exact logic state. Sleepy keeper uses traditional sleep transistors plus two additional transistors - driven by a gate's already calculated output - to save state during sleep mode. Dual Vthvalues can be applied to sleepy keeper in order to dramatically reduce subthreshold leakage current. In short, like the sleepy stack approach, sleepy keeper achieves leakage power reduction equivalent to the sleep and zigzag approaches but with the advantage of maintaining exact logic state (instead of destroying the logic state when sleep mode is entered). Based on experiments with a 4-bit adder circuit, sleepy keeper approach achieves up to 49% less delay and 49% less area than the sleepy stack approach. Unfortunately, sleepy keeper causes additional dynamic power consumption, approximately 15% more than the base case (no sleep transistors used at all). However, for applications spending the vast majority of time in sleep or standby mode while also requiring low area, high performance and maintenance of exact logic state, the sleepy keeper approach provides a new weapon in a VLSI designer's arsenal

This article proposes a novel O(n) Parallel Banker's Algorithm (PBA), which is a parallelized version of the Banker's Algorithm (BA), a well-known O(m\times n) deadlock avoidance algorithm. We implement the approach in hardware, which we call PBA Unit (PBAU). PBAU is not a mere Verilog HDL translation of BA, but a novel, fully hardware-oriented implementation exploiting maximum hardware parallelism of all computations in BA, resulting in O(1) runtime complexity in the best case and O(n) in the worst. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for Multiprocessor System-on-a-Chip (MPSoC), which we predict will be the mainstream of future high performance computing environments. Furthermore, our PBAU supports multiple instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (several orders of magnitude faster than BA in software), but also achieves, in a particular example, a 19 percent speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, less than 0.05 percent in our candidate MPSoC example.

Leakage power consumption of current CMOS technology is already a great challenge. International Technology Roadmap for Semiconductors projects that leakage power consumption may come to dominate total chip power consumption as the technology feature size shrinks. Leakage is a serious problem particularly for CMOS circuits in nanoscale technology. We propose a novel ultra-low leakage CMOS circuit structure which we call "sleepy stack". Unlike many other previous approaches, sleepy stack can retain logic state during sleep mode while achieving ultra-low leakage power consumption. We apply the sleepy stack to generic logic circuits. Although the sleepy stack incurs some delay and area overhead, the sleepy stack technique achieves the lowest leakage power consumption among known state-saving leakage reduction techniques, thus, providing circuit designers with new choices to handle the leakage power problem

This paper proposes a novel O(n) Parallel Banker's Algorithm (PBA) with a best-case run-time of O(1), reduced from an O(mn2) run-time complexity of the original Banker's Algorithm. We implemented the approach in hardware, which we call PBA Unit (PBAU), using Verilog HDL and verified the run-time complexity. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for a MultiProcessor System-on-a-Chip (MPSoC, which we predict will be the mainstream of future high performance computing environments). Moreover, our PBA supports multiple-instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (1600X faster than the Banker's Algorithm in software) but also achieves in a particular example a 19% speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, under 0.05% in our candidate MPSoC example.

In this paper, we investigate the problem of inter-task cache interference in preemptive multi-tasking real-time systems. A prioritized cache is used to reduce cache conflicts among tasks by partitioning the cache. Cache partitions are assigned to tasks according to their priorities. We extend a known tool, SYMTA, in order to estimate the Worst Case Execution Time of tasks executing on a uniprocessor with a unified prioritized L1 cache. Furthermore, we apply a formal timing analysis approach to estimate the Worst Case Response Time of tasks using the prioritized cache. The prioritized cache is compared to a conventional set associative cache of the same size. Our experiments show that the WCRT estimate can be reduced up to 50% when a prioritized cache is used.

This article presents a novel Parallel Deadlock Detection Algorithm (PDDA) and its hardware implementation, Deadlock Detection Unit (DDU). PDDA uses simple Boolean representations of request, grant, and no activity so that the hardware implementation of PDDA becomes easier and operates faster. We prove the correctness of PDDA and that the DDU has a runtime complexity of O ( min ( m , n )), where m is the number of resources and n is the number of processes. The DDU reduces deadlock detection time by 99%, (i.e., 100X) or more compared to software implementations of deadlock detection algorithms. An experiment involving a practical situation with an early deadlock condition showed that the time measured from application initialization to deadlock detection was reduced by 46% by employing the DDU as compared to detecting deadlock in software.

In this paper, we propose an approach to estimate the worst case response time (WCRT) of tasks in a preemptive multi-tasking single-processor real-time system with a set associative cache. The approach focuses on analyzing the cache reload overhead caused by preemptions. We combine inter-task cache eviction behavior analysis and path analysis of the preempted task to reduce, in our analysis, the estimate of the number of cache lines that can possibly be evicted by the preempting task (thus requiring a reload by the preempted task). A mobile robot application which contains three tasks is used to test our approach. The experimental results show that our approach can tighten the WCRT estimate by up to 73% over prior state-of-the-art.

This paper introduces a methodology for estimation of energy consumption in peripherals such as audio and video devices. Peripherals can be responsible for significant amount of the energy consumption in current embedded systems. We introduce a cycle-accurate energy simulator and profiler capable of simulating peripheral devices. Our energy estimation tool for peripherals can be useful for hardware and software energy optimization of multimedia applications and device drivers. The simulator and profiler use cycle-accurate energy and performance models for peripheral devices with the cycle-accurate energy and performance models for computing, storage and power devices created in previous work. We also implemented I/O communication protocols such as polling, I/O interrupts and direct memory access (DMA). Using our energy simulator and estimator, we optimized an audio driver for an MP3 (MPEG-2 Layer 3) audio decoder application. Our optimization results show 44% reduction in the total system energy consumption for the MP3 audio decoder when optimized audio driver is used.

One of the most time consuming parts of debugging is trying to locate a bug. In this context, there are two powerful debugging aids which shorten debug time considerably: reverse execution and dynamic slicing. Reverse execution eliminates the need for repetitive program restarts every time a bug location is missed. Dynamic slicing, on the other hand, isolates code parts that influence an erroneous variable at a program point. In this paper, we present an approach which provides assembly level reverse execution along a dynamic slice. In this way, a programmer not only can find the instructions relevant to a bug, but also can obtain runtime values of variables in a dynamic slice while traversing the slice backwards in execution history. Reverse execution along a dynamic slice skips recovering unnecessary program state; therefore, it is potentially faster than full-scale reverse execution. The experimental results with four different benchmarks show a wide range of speedups from 1.3X for a small program with few data inputs to six orders of magnitude (1,928,500X) for 400x400 matrix multiply. Furthermore, our technique is very memory efficient. Our benchmark measurements show between 3.4X and 2240X memory overhead reduction as compared to our implementation of the same features using traditional approaches.

The performance of a multiprocessor system heavily depends upon the efficiency of its bus architecture. This paper presents a methodology to generate a custom bus system for a multiprocessor system-on-a-chip (SoC). Our bus-synthesis tool, which we call BusSynth, uses this methodology to generate five different bus systems as examples: 1) bidirectional first-in first-out bus architecture; 2) global bus architecture (GBA) version I; 3) GBA version III; 4) hybrid bus architecture (Hybrid); and 5) split bus architecture. We verify and evaluate the performance of each bus system in the context of three applications: an orthogonal frequency division multiplexing wireless transmitter, an MPEG2 decoder, and a database example. Our methodology gives the designer a great benefit in the fast-design space exploration of bus architectures across a variety of performance impacting factors such as bus types, processor types, and software programming style. In this paper, we show that BusSynth can generate buses that, when compared to a typical general GBA, achieve superior performance (e.g., 41% reduction in execution time in the case of a database example). In addition, the bus architecture generated by BusSynth is designed in a matter of seconds instead of weeks for the hand design of a custom bus system.

Assembly instruction level reverse execution provides a programmer with the ability to return a program to a previous state in its execution history via execution of a "reverse program." The ability to execute a program in reverse is advantageous for shortening software development time. Conventional techniques for recovering a state rely on saving the state into a record before the state is destroyed. However, state-saving causes significant memory and time overheads during forward execution.The proposed method introduces a reverse execution methodology at the assembly instruction level with low memory and time overheads. The methodology generates, from a program, a reverse program by which a destroyed state is almost always regenerated rather than being restored from a record. This significantly reduces state-saving.The methodology has been implemented on a PowerPC processor with a custom made debugger. As compared to previous work, all of which heavily use state-saving techniques, the experimental results show from 2X to 2206X reduction in run-time memory usage, from 1.5X to 403X reduction in forward execution time overhead and from 1.2X to 2.32X reduction in forward execution time for the tested benchmarks. Furthermore, due to the reduction in memory usage, our method can provide reverse execution in many cases where other methods run out of available memory. However, for cases where there is enough memory available, our method results in 1.16X to 1.89X slow down in reverse execution.

In this paper, we show the performance comparison and analysis result among three RTOSes: the Real-Time Unit (RTU) hardware RTOS, the pure software Atalanta RTOS and a hardware/software RTOS composed of part of Atalanta interfaced to the System-on-a-Chip Lock Cache (SoCLC) hardware. We also present our RTOS configuration framework that can automatically configure these three RTOSes. The average-case simulation result of a database application example on a three-processor system running thirty tasks with RTU and the same system with SoCLC showed 36% and 19% overall speedups, respectively, as compared to the pure software RTOS system.

Previous work has shown that a system-on-a-chip lock cache (SoCLC) reduces on-chip memory traffic, provides a fair and fast lock hand-off, simplifies software, increases the real-time predictability of the system and improves performance. In this research work, we extend the SoCLC mechanism with a priority inheritance support implemented in hardware. Priority inheritance provides a higher level of real-time guarantees for synchronizing application tasks. Experimental results indicate that our SoCLC hardware mechanism with priority inheritance achieves a 36% speedup in lock delay, 88% speedup in lock latency, and 15% speedup in the overall execution time when compared to its software counterpart. The cost in terms of additional hardware area for the SoCLC with priority inheritance is approximately 10000 NAND2 gates.

The ability to execute a program in reverse is advantageous for shortening debug time. This paper presents a reverse execution methodology at the assembly instruction-level with low memory and time overheads. The core idea of this approach is to generate a reverse program able to undo, in almost all cases, normal forward execution of an assembly instruction in the program being debugged. The methodology has been implemented on a PowerPC processor in a custom made debugger. Compared to previous work -- all of which use a variety of state saving techniques -- the experimental results show 2.5X to 400X memory overhead reduction for the tested benchmarks. Furthermore, the results with the same benchmarks show an average of 4.1X to 5.7X time overhead reduction.

Intertask/interprocess synchronization overheads may be significant in a multiprocessor-shared memory System-on-a-Chip implementation. These overheads are observed in terms of lock latency, lock delay and memory bandwidth consumption in the system. It has been shown that a hardware solution brings a much better performance improvement than the synchronization algorithms developed in software [3]. Our previous work presented a SoC Lock Cache (SoCLC) hardware mechanism which resolves the Critical Section (CS) interactions among multiple processors and improves the performance criteria in terms of lock latency, lock delay and bandwidth consumption in a shared memory multi-processor SoC for short CSes [1]. This paper extends our previous work to support long CSes as well. This combined support involves modifications both in the RTOS kernel level facilities (such as support for preemptive versus non-preemptive synchronization, interrupt handling and RTOS initialization) and in the hardware mechanism. The worst-case simulation results of a database application model with client-server pair of tasks on a four-processor system showed that our mechanism achieved a 57% improvement in lock latency, 14% speed up in lock delay and a 35% overall speedup in total execution time.

It is widely acknowledged that even as VLSI technology advances, there is a looming crisis that is an important obstacle to the widespread deployment of mobile embedded devices, namely that of power. This problem can be tackled at many levels like devices, logic, operating systems, micro-architecture and compiler. While there have been various proposals for specific compiler optimizations for power, there has not been any attempt to systematically map out the space for possible improvements. In this paper, we quantitatively characterize the limits of what a compiler can do in optimizing for power using precise modeling of a state-of-the-art embedded processor in conjunction with a robust compiler. We provide insights to how compiler optimizations interact with the internal workings of a processor from the perspective of power consumption. The goal is to point out the promising and not so promising directions of work in this area, to guide the future compiler designer.

For scalable-shared memory multiprocessor System-on-a-Chip implementations, synchronization overhead may cause catastrophic stalls in the system. Efficient improvements in the synchronization overhead in terms of latency, memory bandwidth, delay and scalability of the system involve a solution in hardware rather than in software. This paper presents a novel, efficient, small and very simple hardware unit that brings significant improvements in all of the above criteria: in an example, we reduce time spent for lock latency by a factor of 4.8, the worst-case execution of lock delay in a database application by a factor of more than 450. Furthermore, we developed a software architecture together with RTOS support to leverage our hardware mechanism. The worst-case simulation results of a client-server example on a four-processor system showed that our mechanism achieved an overall speedup of 27%.

In this paper, we present a mechanism for runtime updating of all kernel modules of a highly modular dynamic real-time operating system. Our approach can help solve the lack of adaptability, extensibility and flexibility of existing real-time operating systems. The dynamic real-time operating system will efficiently support a wide range of applications since any kernel module can be dynamically loaded at runtime to exactly suit the applications without necessitating a reboot of the system.

The performance of a system, especially multiprocessor system, heavily depends upon the efficiency of its bus architecture. In System-on-a-Chip (SoC), the bus architecture can be devised with advantages such as shorter propagation delay (resulting in a faster bus clock), larger bus width, and multiple buses. This paper presents five different SoC bus architectures for a multiprocessor system: Global Bus I Architecture (GBIA), Global Bus II Architecture (GBIIA), Bi-FIFO Bus Architecture (BFBA), Crossbar Switch Bus Architecture (CSBA), and CoreConnect Bus architecture (CCBA). The performance of these architectures is evaluated using applications from wireless communications-an Orthogonal Frequency Division Multiplexing (OFDM) transmitter-and from video processing-an MPEG2 decoder. To increase performance, these bus architectures employ a pipelined scheme, resulting in improved throughput. While all five bus architectures perform well, we find that BFBA and CSBA perform the best for the OFDM transmitter and the MPEG2 decoder, respectively.

Dealing with global on-chip memory allocation/de-allocation in a dynamic yet deterministic way is an important issue for upcoming billion transistor multiprocessor System-on-a-Chip (SoC) designs.To achieve this, we propose a new memory management hierarchy called Two-Level Memory Management.To implement this memory management scheme -which presents a paradigm shift in the way designers look at on-chip dynamic memory allocation -we present a System-on-a-Chip Dynamic Memory Management Unit (SoCDMMU) for allocation of the global on-chip memory, which we refer to as level two memory management (level one is the operating system management of memory allocated to a particular on-chip processor).In this way, heterogeneous processors in an SoC can request and be granted portions of the global memory in twenty clock cycles in the worst case for a four-processor SoC, which is at least an order of magnitude faster than software-based memory management.We present a sample implementation of the SoCDMMU and compare hardware and software implementations.

We present a tool that performs real time analysis and priority assignment for software tasks in a mixed hardware software system with a custom run time scheduler. The tasks in hardware and software have precedence constraints, resource constraints, relative timing constraints, and a rate constraint. A dynamic programming formulation assigns the static priorities such that a hard real time rate constraint can be predictably met. We describe the task control/data flow extraction, runtime scheduler implementation, real time analysis and priority scheduler template. We show how our approach fits into an overall tool flow and target architecture. Finally, we conclude with a sample application of the system to a design example.