Research in TIBBIT(Timing Insensitive Binary to Binary Translation) proposed a methodology to provide timing equivalence as well as semantic equivalence in binary­to• binary translation of real•time applications by inserting synchronization at regular intervals. However, the timing equivalence of programs generated by TIBBIT is not guaranteed. In this dissertation, we provide a method to guarantee the timing equivalence of the generated target binary programs.

We use an interval-based approach, first invented by Allen and Cocke, to test timing equivalence of a translated target binary program with respect to a source binary program. We introduce the concept of timing sensitivity, the maximum timing difference between the source and target programs, to judge how closely the target program will mimic the source program's timing.

We say that a target program is executable with timing equivalence if the timing sensitivity can be reduced to zero, and with timing invariance if the timing sensitivity can be bounded by a constant. We have discovered necessary and sufficient conditions to provide timing equivalence and invariance for target programs.

If a target program is executable with timing equivalence or invariance, it must be enforced by a synchronization scheme. When the target program is executable with timing invariance, the timing sensitivity depends on how and where the target program is synchronized. We use a local synchronization scheme that removes local timing error to provide timing invariance. We develop a static method to measure timing sensitivity with the local synchronization scheme. We also develop optimiza­tion techniques to minimize timing sensitivity.

In summary, the main research contributions of this dissertation are 1) necessary and sufficient conditions for timing equivalent and invariant translation 2) an algo­rithm to find timing sensitivity of the target program and 3) techniques to minimize timing sensitivity of the target program.