Novel functionality, configurability and higher efficiency in automotive systems require sophisticated embedded software, as well as distributed software development between manufacturers and control unit suppliers. However, at least for engine control units, there exists today no well-defined software integration process that satisfies all key requirements of automotive manufacturers. We propose a methodology for safe integration of automotive software functions where required performance information is exchanged while each partner's IP is protected. We claim that in principle performance requirements and constraints (timing, memory consumption) for each software component and for the complete ECU can be formally validated, and believe that ultimately such formal analysis will be required for legal certification of an ECU.

Dual-band Infrared-based passive Missile Warning Sensors (MWS) are under development at USAF Wright Laboratory and other DoD labs to provide aircraft with cost-effective robust detection and tracking of Infrared Surface-to-Air Missile threats out to their maximum launch ranges. Typically, such sensors are limited by the presence of heavy background clutter, solar glints, and sensor noise which lower the likelihood of missile detection. The heavy background clutter may also cause non-missile objects such as flares, glints, and smokestacks to be improperly declared as missiles. The longer detection range of missiles by these sensors is also limited by sensor noise; most noticeably in tropical weather conditions. Atlantic Aerospace and USAF Wright Laboratory have demonstrated two robust algorithms: a Geometric Whitening Filter which enhances the signal-to-clutter ratio and a Morphological Track Before Detect algorithm which enhances the signal-to-noise ratio. Use of these two algorithms in tandem will extend current Advanced Developmental MWS prototype sensors to detect Infrare-guided Surface-to-Air Missiles in heavy urban clutter and tropical maritime weather conditions.

Most recent research in instruction-level parallelism has focused on general-purpose applications such as the SPEC benchmarks. Many quantitative experiments have been performed over the years measuring the impact of different execution models and optimization techniques on these applications. Recently, however, researchers have been developing various ILP architectures for media processors in order to exploit parallelism in audio, video, and graphics applications. It has been assumed that these applications contain far more potential parallelism than general-purpose code, but there have been few attempts to quantify the available parallelism. In this paper, we present a linear complexity global scheduling algorithm that can process vety long traces up to 1 billion operations. Therefore, traces of video applications such as MPEG1, MPEG2, MPEG4 and H.263 encoders and decoders can be analyzed. Using an idealized execution model, speedups of over 1000 have been found in some applications. The experiment shows that eliminating currently identifiable bottlenecks can allow the exploitation of huge amounts of ILP in audio and video applications.

We show that an optimal source code with cost function for code symbols can be regarded as a random number generator generating a random sequence (not necessarily a sequence of fair coin bits) as the target distribution in the sense that the normalized conditional divergence between the distribution of the generated codeword distribution and the target distribution vanishes as the block length tends to infinity.

For many embedded applications, program code size is a critic al design factor. One promising approach for reducing code size is to employ a dual instruction set, where processor architectures support a normal (usually 32 bit) Instruction Set, and a narrow, space efficient (usually 16 bit) Instruction Set with a limited set of opcodes and access to a limited set of registers. This feature, however, requires compilers that can reduce code size by compiling for both Instruction Sets. Existing compiler techniques operate at the function-level granularity and are unable to make the trade-off between increased register pressure (resulting in more spills) and decreased code size. We present a profitability based compiler heuristic that operates at the instruction-level granularity and is able to effectively take advantage of both Instruction Sets. We also demonstrate improved code size reduction, for the MIPS 32/16 bit ISA, using our technique. Our approach more than doubles the code size reduction achieved by existing compilers.

To meet the demands of modern architectures, optimizing compilers must incorporate an ever larger number of increasingly complex transformation algorithms. Since code transformations may often degrade performance or interfere with subsequent transformations, compilers employ predictive heuristics to guide optimizations by predicting their effects a priori. Unfortunately, the unpredictability of optimization interaction and the irregularity of today's wide-issue machines severely limit the accuracy of these heuristics. As a result, compiler writers may temper high variance optimizations with overly conservative heuristics or may exclude these optimizations entirely. While this process results in a compiler capable of generating good average code quality across the target benchmark set, it is at the cost of missed optimization opportunities in individual code segments. To replace predictive heuristics, researchers have proposed compilers which explore many optimization options, selecting the best one a posteriori. Unfortunately, these existing iterative compilation techniques are not practical for reasons of compile time and applicability. In this paper, we present the Optimization-Space Exploration (OSE) compiler organization, the first practical iterative compilation strategy applicable to optimizations in general-purpose compilers. Instead of replacing predictive heuristics, OSE uses the compiler writer's knowledge encoded in the heuristics to select a small number of promising optimization alternatives for a given code segment. Compile time is limited by evaluating only these alternatives for hot code segments using a general compiletime performance estimator. An OSE-enhanced version of Intel's highly-tuned, aggressively optimizing production compiler for IA-64 yields a signi?cant performance improvement, more than 20% in some cases, on Itanium for SPEC codes.

A binary decoder is a common component of software de- velopment tools such as instruction set simulators, disassemblers and debuggers. The efficiency of the decoder can have a significant impact on the efficiency of these software tools. Automated synthesis of efficient binary decoders is therefore necessary for retargetable software tool development frameworks targeting the rapidly growing field of application-specific processor design. This paper describes a decoder synthesis algorithm that translates a simple instruction pattern specification into efficient binary decoders in C under given memory constraints. The algorithm constructs a decision tree with carefully chosen decoding primitives and cost models. As demonstrated through two case studies, the synthesized decoders achieve efficiency comparable to hand-coded decoders with ensured correctness. The algorithm has no limitation on the input instruction patterns and it requires only the least amount of knowledge about the instruction encoding. Therefore it can be used with any machine description scheme containing instruction encoding information.

Given the growth in application-specific processors, there is a strong need for a retargetable modeling framework that is capable of accurately capturing complex processor behaviors and generating efficient simulators. We propose the operation state machine (OSM) computation model to serve as the foundation of such a modeling framework. The OSM model separates the processor into two interacting layers: the operation layer where operation semantics and timing are modeled, and the hardware layer where disciplined hardware units interact. This declarative model allows for direct synthesis of micro-architecture simulators as it encapsulates precise concurrency semantics of microprocessors. We illustrate the practical benefits of this model through two case studies - the StrongARM core and the PowerPC-750 superscalar processor. The experimental results demonstrate that the OSM model has excellent modeling productivity and model efficiency. Additional applications of this modeling framework include derivation of information required by compilers and formal analysis for processor validation.

Digital filtering algorithms are most commonly implemented using general purpose digital signal processing chips for audio applications, or special purpose digital filtering chips and application- specific integrated circuits (ASICs) for higher rates. This paper describes an approach to the implementation of digital filter algorithms based on field programmable gate arrays (FPGAs). The advantages of the FPGA approach to digital filter implementation include higher sampling rates than are available from traditional DSP chips, lower costs than an ASIC for moderate volume applications, and more flexibility than the alternate approaches. Since many current FPGA architectures are in-system programmable, the configuration of the device may be changed to implement different functionality if required. Our examples illustrate that the FPGA approach is both flexible and provides performance comparable or superior to traditional approaches. functionality.

This paper considers the problem of designing heterogeneous multiprocessor embedded systems. The focus is on a step of the design flow: the definition of innovative metrics for the analysis of the system specification to statically identify the most suitable processing elements class for each system functionality. Experimental results are also included, to show the applicability and effectiveness of the proposed methodology.

The analysis of the amount of human resources required to complete a project is felt as a critical issue in any company of the electronics industry. In particular, early estimating the effort involved in a development process is a key requirement for any cost-driven system-level design decision. In this paper, we present a methodology to predict the final size of a VHDL project on the basis of a high-level description, obtaining a significant indication about the development effort. The methodology is the composition of a number of specialized models, tailored to estimate the size of specific component types. Models were trained and tested on two disjoint and large sets of real VHDL projects. Quality-of-result indicators show that the methodology is both accurate and robust.

Complex embedded systems consist of hardware and software components from different domains, such as control and signal processing, many of them supplied by different internal and external source (e. g. IP). The system architect faces the challenge to integrate, optimize and validate the resulting heterogeneous systems. The analysis of the whole system is currently limited to simulation or emulation, since formal validation is only available for some subproblems. While simulation still seems viable for the validation of the system function, it can not be reliably applied to the validation of non-functional system properties, in particular timing. In this paper, we propose a validation methodology which augments existing cosimulation-based design approaches with formal timing analysis capabilities. This methodology is based on the decomposition of the validation task into the analysis of individual processes and resources for which formal analysis techniques are known and on the composition of the obtained results in order to obtain systemlevel timing information. Furthermore, it is shown how the analyzability of system timing can be systematically improved by slightly changing the system implementation.

Appeared on IEEE DESIGN & TEST OF COMPUTERS

Future wireless internet enabled devices will be increasingly powerful supporting many more applications including one of the most crucial, security. Although SoCs offer more resistance to bus probing attacks, power/EM attacks on cores and network snooping attacks by malicious code are relevant. This paper presents a methodology for security on NoC at both the network level (or transport layer) and at the core level (or application layer) is proposed. For the first time a low cost security wrapper design is presented, which prevents unencrypted keys from leaving the cores and NoC. This is crucial to prevent untrusted software on or off the NoC from gaining access to keys. At the core level (application layer) power analysis attacks are examined for the first time for parallel and adiabatic architectural cores. With the emergence of secure IP cores in the market, a security methodology for designing NoCs is crucial for supporting future wireless internet enabled devices.

Communication-centric Multiprocessor Systems-on-Chip (MpSoC) will dominate future chip architectures. They will be built from heterogeneous HW and SW components integrated around a complex communication infrastructure. Already today, performance verification is a major challenge that simulation can hardly meet, and formal techniques have emerged as a serious alternative. The article presents a new technology that extends known approaches to real-time system analysis to heterogeneous MpSoC using event model interfaces and a novel event flow mechanism.

This paper addresses the problem of estimating cost and development effort of a system, starting from its complete or partial high-level description. In addition, some modifications to evaluate the cost-effectiveness of reusing VHDL-based designs, are presented. The proposed approach has been formalized using an approach similar to the COCOMO analysis strategy, enhanced by a project size prediction methodology based on a VHDL function point metric. The proposed design size estimation methodology has been validated through a significant benchmark, the LEON-1 microprocessor, whose VHDL description is of public domain.

When applying optimizations, a number of decisions are made using fixed strategies, such as always applying an optimization if it is applicable, applying optimizations in a fixed order and assuming a fixed configuration for optimizations such as tile size and loop unrolling factor. While it is widely recognized that these fixed strategies may not be the most appropriate for producing high quality code, especially for embedded systems, there are no general and automatic strategies that do otherwise. In this paper, we present a framework that enables these decisions to be made based on predicting the impact of an optimization, taking into account resources and code context. The framework consists of optimization models, code models and resource models, which are integrated for predicting the impact of applying optimizations. Because data cache performance is important to embedded codes, we focus on cache performance and present an instance of the framework for cache performance in this paper. Since most opportunities for cache improvement come from loop optimizations, we describe code, optimization and cache models tailored to predict the impact of applying loop optimizations for data locality. Experimentally we demonstrate the need to selectively apply optimizations and show the performance benefit of our framework in predicting when to apply an optimization. We also show that our framework can be used to choose the most beneficial optimization when a number of optimizations can be applied to a loop nest. And lastly, we show that we can use the framework to combine optimizations on a loop nest.

For real time systems not only the logical function is important but also the timing behavior, e. g. hard real time systems must react inside their deadlines. To guar- antee this it is necessary to know upper bounds for the worst case execution times (WCETs). The accuracy of the prediction of WCETs depends strongly on the ability to model the features of the target processor. Cache memories, pipelines and parallel functional units are architectural components which are respon- sible for the speed gain of modern processors. It is not trivial to determine their influence when predicting the worst case execution time of programs. This paper describes a method to predict the be- havior of pipelined superscalar processors and reports initial results of a prototypical implementation for the SuperSPARC I processor.

More and more devices contain computers with limited amounts of memory. As a result, code compaction techniques are gaining popularity, especially when they also improve performance and power consumption, or at least not degrade it. This paper quantifies the side-effects of code abstraction on performance using extensive measurements and simulations on the SPECint2000 benchmark suite and some additional C++ programs. We show how to use profile information in order to obtain almost all the code size reduction benefits of code abstraction, yet experience almost none of its disadvantages.

More and more devices contain computers with limited amounts of memory. As a result, code compaction techniques are gaining popularity, especially when they also improve performance and power consumption, or at least not degrade it. This paper quantifies the side-effects of code abstraction on performance using extensive measurements and simulations on the SPECint2000 benchmark suite and some additional C++ programs. We show how to use profile information in order to obtain almost all the code size reduction benefits of code abstraction, yet experience almost none of its disadvantages.

In the embedded domain, memory usage and energy consumption are critical constraints. Dual width instruction set embedded processors such as the ARM provide a 16-bit instruction set in addition to the 32-bit instruction set to address these concerns. Using 16-bit instructions one can achieve code size reduction and I-cache energy savings at the cost of performance. We have observed that throughout 16-bit Thumb code there exist Thumb instruction pairs that are equivalent to a single ARMinstruction. We have developed an approach which uses combination of compiler and architectural support to exploit the above property for improving performance of 16-bit code. We enhance the Thumb instruction set by incorporating Augmenting eXtensions (AX). The task of the compiler is to identify pairs of Thumb instructions that can be safely combined and executed as single ARM instructions. The compiler replaces such pairs of Thumb instructions by AX+Thumb instruction pairs. The AX instruction is coalesced with the immediately following Thumb instruction to generate a single ARM instruction at decode time. Thus, using AX instructions, the compiler can both generate compact 16-bit code and provide hardware with information needed to produce better performing 32-bit code.

Slide-show presented at CODES-ISSS 2003 Merged conference.