The RASSP Digest - Vol. 3, September 1996

Timing Insensitive Binary-to-Binary Translation (TIBBIT)

by Bryce Cogswell and Zary Segall

Abstract

TIBBIT provides technologies that automate the migration of legacy embedded software systems to model-year platforms while preserving their semantic and timing properties. A working demonstration system is complete and has been modeled and validated for software running on a number of source and target architectures.

1. Objectives

The majority of software for embedded systems is developed for a specific processor and platform environment. In addition to being targeted toward a specific instruction set architecture (ISA), such software typically incorporates hard-coded knowledge of the system’s I/O ports, timing facilities, interrupt mechanism, etc. In many instances, the code may also take advantage of the programmer’s knowledge of processor timing information, i.e., either the minimum or maximum time a given code fragment may require to execute. Upgrading a legacy system designed these assumptions to model year hardware typically requires a complete rewrite of the software, foremost to achieve ISA compatibility, but also because locating and correcting every instance of reliance upon the original specification is a daunting task. The TIBBIT project aims to provide an automated migration path for software developed on legacy hardware to model year hardware. Instances of program reliance upon source-hardware features are automatically detected and modified to reflect the target-hardware environment.

The goals of the TIBBIT methodology are as follows:

Semantic equivalence: The resultant program is semantically equivalent to the original program.
External timing equivalence: The timing of the program on the target is equivalent to the source platform within some predictable error bound.
Processor independence: The scheme should be effective across a wide range of processor architectures.
Use existent I/O architecture: The interfaces to external devices to which the source processor is attached are preserved.
Quantifiable performance: The success of a translation can be predicted prior to translation, and the degree of timing equivalence can be quantified.
Automated translation: The translation process should be nearly or entirely automated.

2. Technical Approach

TIBBIT builds upon previous work in binary-to-binary translation (BBT), where the object code of an application is analyzed using control and dataflow analysis, and instruction sequences (e.g., basic blocks) are then translated from the source ISA to the target ISA, preserving the semantics of the program. TIBBIT extends this process by determining not only the semantic properties of the program, but also the timing properties. During translation the time required to execute each basic block is computed for the source ISA, and this is used to modulate the speed at which the application executes on the target ISA. At regular intervals the target processor compares its progress with what would be achieved by the source ISA, and adjusts the amount of processing time dedicated to the task accordingly. Scheduling on the target can be done two different ways: to maximize the degree of timing equivalence a dedicated target processor is used; otherwise, the application is scheduled on the target under rate monotonic scheduling. Using RMS allows multiple TIBBIT- translated and native applications to be executed concurrently.

To facilitate the creation of binary translators for new architectures, an automated translator generator, called Astra, has been created. Astra takes as input a machine description file which specifies the syntax and semantics of a source ISA's binary format, and produces a binary translator capable of decompiling applications into an intermediate representation that is subsequently compiled using gcc. This translation approach eases ports to new source ISA's and yields target ISA independence.

3. Technical Contributions

The TIBBIT project has yielded a methodology and prototype translation system capable of migrating applications from legacy to model-year hardware while maintaining all semantic and timing characteristics. Sample translators have migrated applications from the M68000 and TMS320C30 architectures to MIPS, PowerPC, Sparc and Pentium based systems. Translated systems retain timing equivalence with the original systems to within 80 microseconds while scheduled under the Rate Monotonic Scheduling algorithm on the target with other tasks (Figure 1), and within 25 microseconds when executing on a dedicated processor. Processor utilization overhead incurred by the timing instrumentation is about 20%.

A model predicting the degree of timing equivalence achievable for a given translation has been developed and validated. The model uses characteristics of the source and target ISA timing, as well as the application being translated, to compute the timing accuracy that can be achieved by the translation software. Current work builds on this foundation to further reduce timing error by reordering instructions during the translation to minimize “trouble spots” in the code.

Table 1 specifies the factors affecting TIBBIT schedulability while Table 2 specifies the greatest amount by which timing on the target processor can become out of sync with the source. The precondition column specifies the condition that must hold for the task to be schedulable under TIBBIT, while the max behind and max ahead columns bound the maximum timing error that can occur.

4. Deliverables

The following deliverables have been produced in the course of the TIBBIT project. Basic methods and techniques for semantic and timing equivalent legacy migration were developed. A working implementation used to translate monolithic applications and executives on uniprocessor systems is complete, and has been validated using real-world programs. The retargetability of the system has been demonstrated on numerous platforms.

Finally, the Astra translator generator has been demonstrated for translating from both CISC and DSP architectures to various RISC platforms.

5. Technical Papers

Further details on the implementation and results of the TIBBIT project are available in a number of technical papers. The fundamental concepts of the system are first proposed in “Timing Insensitive Binary to Binary Translation of Real Time Systems” (Cogswell and Segall, Carnegie Mellon Tech Report, March ’93). Initial results for the timing equivalence implementation are described in “Timing Insensitive Binary to Binary Translation” (Cogswell and Segall, Real-time workshop ISCA ’94). “Performance Impact of Architectural Features During Binary Translation” (Cogswell and Segall, PACT ’95) analyses the architectural features in the source and target ISAs that contribute to overhead incurred during the translation process, quantifying the features that make a target ISA a good “match” for a legacy system. The feasibility and limitations of supporting multiprocess architectures, as either a source or target platform, are examined in “Timing Insensitive Binary-to-Binary Migration Across Multiprocessor Architectures” (Cogswell and Segall, WPDRTS, ’95). Finally, a comprehensive look at the modeling, implementation and results of the project is provided in “Timing Insensitive Binary to Binary Translation” (Cogswell, Carnegie Mellon Ph.D. thesis, ’95).

Bryce Cogswell
Computer and Information Science
University of Oregon
Eugene, OR 97403
cogswell@cs.uoregon.edu

Zary Segall
Computer and Information Science
University of Oregon
Eugene, OR 97403
zs@cs.uoregon.edu

Newsletter Index

The RASSP Digest - Vol. 3, September 1996
newsletter/html/96sep/news_13.html