Although a data cache provides fast access latency, it degrades the timing predictability of real-time embedded systems due to misses which are difficult to predict. Scratch pad memory is accessed as fast as a data cache, but does not suffer from unpredicted misses thanks to its software-controlled mechanism. This study presents how scratch pad memory reduces data cache pollution and misses for preemptive real-time embedded systems, so that both of the fast memory subsystems can work together with synergy. First, by classifying data cache misses into intrinsic misses and interference misses we reveal previously hidden characteristics of the interactions between data in the cache. Second, we suggest a heuristic method of data allocation to scratch pad memory using the new perspective, which reduces the cache pollution and finally improve the cache performance. Third, we examine these concepts with several tasks running on a real hardware platform and a preemptive real-time operating system. In addition, we perform a supplementary case study which shows how sensitive the data cache is to small changes of data memory layout and its dynamic contents. Our proposed scheme guides us through the synergetic process by using scratch pad memory beyond the sensitive data cache. In our experiments, the proposed data allocation scheme significantly reduces inter-task cache pollution as well as the intrinsic cache misses of the tasks themselves.

Hardware-managed caches introduce large amounts of timing variability, complicating real-time system design. One alternative is a memory system with scratchpad memories which improve system performance while eliminating such timing variability. Prior work introduced the DARTS approach, which combines static allocation of data into scratchpad memories, with task scheduling for preemptive multi-threaded, hard real-time embedded systems.This study offers several significant contributions. First, it introduces a method to split a stack frame across multiple memory units, offering fine-grain allocation of automatic memory variables with very low run-time overhead. This enables more effective use of fast memory, improving run-times. Second, it introduces the completed tool-chain based on DARTS, which reallocates static and automatic variables across multiple memory banks and now targets the ARM7 architecture. Third, it evaluates the performance improvement from DARTS using experimental results from the code running on real hardware in a preemptively scheduled RTOS-based multi-tasking environment. This hands-on experimental approach ensures a high level of confidence in the results; previous studies have generally stopped at estimating performance rather than building and measuring a real implementation.In our experiments the execution time of each task is reduced up to 24% from the baseline external SRAM configurations. We show that our methods improve task execution time to achieve 37% to 99% of the performance improvement of an ideal unlimited-capacity scratchpad memory system. Finally, we find our allocations provide on average 2/3 of the performance enhancement of the equivalently-sized cache yet with easily-predicted performance.

Advances in microprocessors, memory, and radio technology have enabled the emergence of embedded systems that rely on communication systems to exchange information and coordinate their activities in spatially distributed applications. However, developing embedded communication systems that satisfy specific application requirements is a challenge due to the many tradeoffs imposed by different choices of underlying protocols and their parameters. Furthermore, evaluating the correctness and performance of the design and implementation before deploying it is a nontrivial task due to the complexity of the resulting system. This article presents the design and implementation of RaPTEX, a rapid prototyping tool for embedded communication systems, especially well suited for wireless sensor networks (WSNs), consisting of three major subsystems: a toolbox, an analytical performance estimation framework, and an emulation environment. We use a hierarchical approach in the design of the toolbox to facilitate the composition of the network stack. For fast exploration of the tradeoff space at design time, we build an analytical performance estimation model for energy consumption, delay, and throughput. For realistic performance evaluation, we design and implement a hybrid, accurate, yet scalable, emulation environment. Through three use cases, we study the tradeoff space for different protocols and topologies, and highlight the benefits of using RaPTEX for designing and evaluating embedded communication systems for WSNs.

Many wireless sensor nodes (motes) interface with slow peripheral devices, requiring the processor to wait. These delays waste time, energy and power, which are valuable but limited resources on many motes. This paper presents techniques to use software thread integration (STI) in TinyOS applications to recover the idle time for useful processing. We modify the TOS scheduler to support the selection and execution of integrated threads. We analyze the impact of integration on task response time. We demonstrate these methods by applying them to a microphone array sampling application to save computation time and energy. We find that the integrated tasks finish 17.7% faster, reducing application active time (and hence application energy) by 6.3%.

Using preemption threshold scheduling (PTS) in a multi-threaded real-time embedded system reduces system preemptions and hence reduces run-time overhead while still ensuring real-time constraints are met. However, PTS offers other valuable benefits. In this paper we investigate the use of PTS for hard real-lime system with limited RAM. Our primary contribution is to prove the optimality of PTS among all preemption-limiting methods for minimizing a system's total stack memory requirements. We then discuss characteristics of PTS and show how to reduce average worst-case response times. We also introduce a unified framework for using PTS with existing fixed-priority (e.g. rate-or deadline-monotonic), or dynamic-priority scheduling algorithms ( e.g. earliest-deadline first). We evaluate the performance of PTS and our improvements using synthetic workloads and a real-time workload. We show PTS is extremely effective at reducing slack memory requirements. Our enhancements to PTS Improve worst-case, response-times as well

Many real-time (RT) embedded systems can benefit from a memory hierarchy to bridge the processor/memory speed gap. These RT embedded systems usually utilize a cacheless architecture to avoid the time variability which complicates the timing analysis essential for RT systems. In the absence of a cache the burden of allocating the data objects to the memory hierarchy is on the programmer/compiler. There has been much research into allocating data objects into the memory hierarchy for efficient execution. However, existing methods have limited scope and ignore some aspects of RT multitasking embedded systems. In this paper we propose a synergistic, optimal approach to allocating data objects and scheduling real-time tasks for embedded systems. We allocate data using integer linear programming (ILP) to minimize each task's worst-case execution time (WCET), then perform preemption threshold scheduling (PTS) on the tasks to reduce stack memory requirements while still meeting hard RT deadlines. The memory reduction of PTS allows these steps to be repeated. The data objects now require less memory, so more can fit into faster memory, further reducing WCET. The increased slack time can be used by PTS to reduce preemptions further, until a fixed point is reached. We evaluate the technique with several levels of data object granularity using both synthetic workloads and a real-time benchmark and find it to be highly effective

The overhead of context switching limits efficient scheduling of multiple concurrent threads on a uniprocessor when real-time requirements exist. A software-implemented protocol controller may be crippled by this problem. The available idle time may be too short to recover through context switching, so only the primary thread can execute during message activity, slowing the secondary threads and potentially missing deadlines. Asynchronous software thread integration (ASTI) uses coroutine calls and integration, letting threads make independent progress efficiently, and reducing the needed context switches. We demonstrate the methods with a software implementation of an automotive communication protocol (J1850) and several secondary threads.

When integrating software threads together to boost performance on a processor with instruction-level parallel processing support, it is rarely clear which code regions should be aligned and integrated, and which regions should be left alone. This problem grows even worse on a modern VLIW DSP due to complicating factors in both the hardware and compiler: software pipelining, predication, branch delay slots, load delay slots and limited resources. As a result, finding an effective integration strategy requires extensive iteration through the integrate/compile/analyze sequence.In this paper we introduce methods to quantitatively estimate the performance benefit from the integration of multiple software threads. We use resource modeling, consider register pressure and compensate for compiler optimizations. This enables different scenarios to be compared and ranked. We then use these estimates to guide integration by concentrating on the most beneficial scenario. Information from each iteration of compilation is used to update the rankings of scenarios. We find that our modeling methods combined with limited compilation quickly find the best integration scenario without requiring exhaustive integration.

Embedded systems require control of many concurrent real-time activities, leading to system designs that feature a variety of hardware peripherals, with each providing a specific, dedicated service. These peripherals increase system size, cost, weight, and design time. Software thread integration (STI) provides low-cost thread concurrency on general-purpose processors by automatically interleaving multiple threads of control into one. This simplifies hardware to software migration (which eliminates dedicated hardware) and can help embedded system designers meet design constraints, such as size, weight and cost. We have developed concepts for performing STI and have implemented many in our automated postpass compiler Thrint. Here we present the transformations and examine how well the compiler integrates threads for two display applications. We examine the integration procedure, the processor load, and code memory expansion. Integration allows reclamation of CPU idle time, allowing run-time speedups of 1.6x to 3.6x.

Dynamic frequency scaling and dynamic voltage scaling have been developed to save power and/or energy for general purpose computing platforms and high-end embedded systems. This paper examines the practicality of using these advanced techniques to save power and energy for commodity 8-bit microcontrollers while leveraging their built-in low-power modes. The benefits of the techniques are weighed against their complexity and cost. First, we mathematically model the power dissipation characteristics of 11 popular 8-bit microcontrollers. We then simulate their power dissipation with different power management techniques being applied. The role of the power scheduler, the power supply, and the frequency divider circuit are also described and analyzed. We find that although dynamic voltage scaling renders the lowest energy dissipation for most microcontrollers, it is not always dramatically better than using a combination of dynamic frequency scaling and the built in power down modes, which is much less expensive to implement.

This paper makes two contributions to Asynchronous Software Thread Integration (ASTI). First, it presents methods to calculate worst-case secondary thread performance statically. This will enable real-time performance guarantees for the system in future work. Second, it improves the run-time performance of integrated threads by partitioning the register file, allowing faster coroutine calls. Determining the ideal partitioning of the register file is non-trivial if the registers are heterogeneous, which is a common case. We use an exhaustive search to explore the limits of performance possible.We have implemented these analyses in our research compiler Thrint and a shell script to create an automated system for design space exploration. We present experimental results showing the secondary thread performance attainable on an 8-bit embedded microcontroller of the AVR architecture. We automatically integrate two embedded protocols (CAN and MIL-STD-1553B) and two secondary threads (PID controller and serial host interface) and find that in most cases the AVR's 32 registers are adequate for both threads with no slowdown. In two cases slowdowns reach 1.8%, a negligible penalty.

Software thread integration (STI) (Dean, A.G., Proc. 23rd IEEE Real-Time Systems Symp., 2002) and asynchronous STI (ASTI) (Kumar, N.J. et al., Proc. 2004 ACM SIGPLAN/SIGBED Conf. on Languages, Compilers and Tools for Embedded Systems, 2004) are compiler techniques which interleave functions from separate program threads at the assembly language level, creating implicitly multithreaded functions which provide low-cost concurrency on generic hardware. This extends the reach of software and reduces the need to rely upon dedicated hardware. We target applying STI and ASTI to 8 and 16 bit microcontrollers. STI and ASTI extend the performance of commodity low-end microcontrollers through static scheduling techniques, potentially avoiding the need for dedicated hardware or faster clock speeds.

Software pipelining is a critical optimization for producing efficient code for VLIW/EPIC and superscalar processors in high-performance embedded applications such as digital signal processing. Software thread integration (STI) can often improve the performance of looping code in cases where software pipelining performs poorly or fails. This paper examines both situations, presenting methods to determine what and when to integrate.We evaluate our methods on C-language image and digital signal processing libraries and synthetic loop kernels. We compile them for a very long instruction word (VLIW) digital signal processor (DSP) -- the Texas Instruments (TI) C64x architecture. Loops which benefit little from software pipelining (SWP-Poor) speed up by 26% (harmonic mean, HM). Loops for which software pipelining fails (SWP-Fail) due to conditionals and calls speed up by 16% (HM). Combining SWP-Good and SWP-Poor loops leads to a speedup of 55% (HM).

Software thread integration (STI) is a compilation technique which enables the efficient use of an application's fine-grain idle time on generic processors without special hardware support. With STI, a primary function is automatically interleaved with a secondary function to create a single implicitly multithreaded function which minimizes context switching and, hence, both improves performance and also offers very fine-grain concurrency. In this work, we extend STI techniques to address two challenges. First, we reduce response time for interrupts or other high-priority threads by introducing polling servers into integrated threads. Second, we enable integration with long host threads, expanding the domain of STI. We derive methods to evaluate the response time for threads in systems with and without these new integration methods. We demonstrate these concepts with the integration of various threads in a sample hard-real-time system on a highly-constrained microcontroller. We use an inexpensive 20 MHz AVR 8-bit microcontroller to generate monochrome NTSC video while servicing a high-speed (115,2 kbaud) serial communication link. We have built and tested this system, achieving graphics rendering speed-ups of 3.99/spl times/ to 13.5/spl times/.

Asynchronous Software Thread Integration (ASTI) provides fine-grain concurrency in real-time threads by statically scheduling (integrating) code from primary threads into secondary threads, reducing the context switching needed and allowing recovery of fine-grain idle time. Unlike STI, ASTI allows asynchronous thread progress.Current ASTI techniques do not support procedure calls in the secondary thread because they lead to timing conflicts during static scheduling. ASTI requires knowing the secondary thread's instruction execution schedule to guide placement of real-time instructions from the primary thread. A secondary thread procedure called from multiple sites will have ambiguous timing at compile time.In this paper we remove this constraint using both procedure inlining and cloning. We present a formal approach to choosing a subset of calls to inline and to remove the timing conflicts in the remaining call sites in an efficient fashion. Excessive inlining and cloning both lead to code size explosion, while poor choices in timing conflict elimination slow program execution. The cloned threads show a significant speedup when compared to non-cloned versions yet have low code expansion. The techniques presented here have been implemented in our post-pass compiler Thrint and demonstrated on a benchmark suite of secondary threads representative of low-end embedded systems.

The overhead of context-switching limits efficient scheduling of multiple concurrent threads on a uniprocessor when real-time requirements exist. Existing software thread integration (STI) methods reduce context switches, but only provide synchronous thread progress within integrated functions. For the remaining, non-integrated portions of the secondary threads to run and avoid starvation, the primary thread must have adequate amounts of coarse-grain idle time (longer than two context-switches). We have developed asynchronous software thread integration (ASTI) methods which address starvation through the efficient use of coroutine calls and integration. ASTI allows threads to make independent progress efficiently and reduces the number of context switches needed through integration.Software-implemented protocol controllers are crippled by this problem; the primary thread "bit-bangs" each bit of a message onto or off of the bus, leaving only fragments of idle time shorter than a bit time. This fragmented time may be too short to recover through context switching, so only the primary thread can execute during message transmission or reception, slowing the secondary threads and potentially making them miss their deadlines. ASTI simplifies the implementation of embedded communication protocols on low-cost, moderate speed (1 - 100 MHz, 8- and 16-bit) microcontrollers. We demonstrate ASTI by replacing a standard automotive communication protocol controller (J1850) with software and generic hardware. Secondary thread performance improves significantly when compared with a traditional interrupt-based software approach.

We present methods to add efficient cryptographic support to low-performance embedded processors with embedded networks (e.g. sensor networks). Software thread integration (STI) is used to create efficient threads which can perform cryptographic operations during time-slice (TDMA) communication, eliminating most context-switching overhead. The AvrX kernel is enhanced to automatically select the most efficient threads based upon available work, saving processor cycles and power. The results show that an STI-based implementation enables communication at higher rates while also performing more cryptographic work compared with traditional ISR (interrupt service routine) or busy-wait schemes. Significant performance improvements are found for both the RC4 and RC5 ciphers. First, STI enables cryptographic processing to occur during communication at a bit rate of f/sub cpu//8, which is not possible with an ISR approach. Second, cryptographic throughput at lower communication rates increases by up to 200% for both RC4 and RC5.

Recent research in sensor networks has raised issues of security for small embedded devices. Security concerns are motivated by the deployment of a large number of sensory devices in the field. Limitations in processing power, battery life, communication bandwidth and memory constrain the applicability of existing cryptography standards for small embedded devices. A mismatch between wide arithmetic for security (32 bit word operations) and embedded data bus widths (often only 8 or 16 bits) combined with lack of certain operations (e.g., multiply) in the ISA present other challenges.This paper offers two contributions. First, a survey investigating the computational requirements for e a number of common cryptographic algorithms and embedded architectures is presented. The objective of this work is to cover a wide class of commonly used encryption algorithms and to determine the impact of embedded architectures on their performance. This will help designers predict a system's performance for cryptographic tasks. Second, methods to derive the computational overhead of embedded architectures in general for encryption algorithms are developed. This allows one to project computational limitations and determine the threshold of feasible encryption schemes under a set of the constraints for an embedded architecture.Experimental measurements indicate uniform cryptographic cost for each encryption class and each architecture class and negligible impact of caches. RC4 is shown to outperform RC5 for the Atmega platform. But when message authentication is required in addition to encryption, hash or block ciphers, such as RC5, have the advantage of providing support for both authentication and encryption. The analytical model allows to assess the impact of arbitrary embedded architectures as a multi-variant function for each encryption scheme. Overall, our results are not only valuable to assess the feasibility of encryption schemes for existing embedded architectures, they also extend to assess the feasibility of encryption methods for new algorithms and architectures for sensor systems.

Software thread integration (STI) is a compilation technique which enables the efficient use of an application's fine-grain idle time on generic processors without special hardware support. With STI, a primary function (with real-time requirements on specific instructions) is automatically interleaved with a secondary function to create a single implicitly multithreaded function which minimizes context switching and hence both improves performance and also offers very fine-grain concurrency.In this paper we extend STI techniques to address two challenges. First, we reduce response time for interrupts or other high-priority threads by introducing polling servers into integrated threads. Currently integrated threads disable interrupts, delaying all other work until their completion. Second, we enable integration with long host threads, expanding the domain of STI. With current techniques, if there are frequent interrupts, only host threads which can finish execution before the next interrupt can be integrated. We derive methods to evaluate the response time for threads in systems with and without these new integration methods.We demonstrate these concepts with the integration of various threads in a sample hard-real-time system on a highly-constrained microcontroller. We use an inexpensive 20 MHz AVR 8-bit microcontroller to generate monochrome NTSC video while servicing a high-speed (115.2 kbaud) serial communication link. We have built and tested this system and demonstrate graphics rendering speed-ups of 3.99x to 13.5x.

Embedded systems require control of many concurrent real-time activities, leading to system designs which feature multiple hardware peripherals with each providing a specific, dedicated service. These peripherals increase system size, cost, weight, power and design time. Software thread integration (STI) provides low-cost thread concurrency on general-purpose processors by automatically interleaving multiple (potentially real-time) threads of control into one. This simplifies hardware to software migration (which eliminates dedicated hardware) and can help embedded system designers meet design constraints. This paper introduces automated methods for planning and performing the code transformations needed for integration of functions with more sophisticated control flows than in previous work. We demonstrate the methods by using Thrint, our post-pass thread-integrating compiler, to automatically integrate multiple threads for a sample real-time embedded system with fine-grain concurrency. The sample application generates an NTSC monochrome video signal (sending out a stream of pixels to a video DAC) with STI to replace a video refresh controller IC Using Thrint reduces integration time from days to minutes and, by reclaiming idle time, speeds up graphics rendering by 3.2/spl times/ to 3.8/spl times/ in the three functions examined.

Software thread integration provides low-cost concurrency on general-purpose processors by automatically interleaving multiple threads of control into one. This simplifies hardware to software migration and can help embedded system designers meet design constraints. Previous work describes how to efficiently integrate threads. In this paper we demonstrate how to link trigger events with guest thread execution and how to analyze an application to determine which threads to integrate. The analysis involves timing measurement and prediction to identify the amount of easily accessible temporally deterministic code within each function. This information is used to predict quantitatively the impact of design decisions on system efficiency and help guide integration. To illustrate this process we evaluate an application predicted for the year 2005, when $20 buys a 2000 MIPS embedded processor-a software-based high-resolution MPEG video player.

This paper presents details of how to perform thread integration to provide low-cost concurrency for general-purpose microcontrollers and microprocessors. A post-pass compiler interleaves multiple threads of control at the machine instruction level for concurrent execution on a uniprocessor and provides very fine-grain multithreading without context switching overhead. Such efficient concurrency allows implementation of real-time functions in software rather than dedicated peripheral hardware. We investigate a set of code transformations which allow systematic integration of a real-time guest thread into a host thread, producing an integrated thread which meets all real-time requirements. The thread integration concept and the associated code transformations have been applied to example functions chosen from three application domains to evaluate the method's feasibility.