Koder3's Technology Forum

Paper Review - Binary Translation Using Peephole Superoptimizers

2009-09-23T20:08:00.000-07:00

This post is a review of a paper that was published in the Operating Systems Design and Implementation conference (OSDI) 2008:

Binary Translation Using Peephole Superoptimizers
Sorav Bansal and Alex Aiken, Stanford University
URL: http://www.usenix.org/events/osdi08/tech/full_papers/bansal/bansal.pdf

This is one of my new favorite papers from OSDI. They propose a novel application of techniques found in superoptimizers: automatic learning of translation rules that can be used to construct binary translators. They provide a method of determining optimal register mappings between architectures, and implement their approach. They use the implementation to generate translation rules, thereby constructing a static binary translator. PowerPC is used as the source architecture, and the target instruction set is x86. Experimental results are shown, that measure the runtime of translated code, compared with the native execution. Micro-benchmarks (lmbench) and larger benchmarks (specint) are the experimental workloads.

The following are some rough notes that I made just after reading this paper. I'll try to tweak my original notes a little, so they seem more coherent to the reader:

One really interesting thing about this work is that they use qemu on a linux-x86 host to compare performance and results of instruction sequences executing on an emulated PowerPC platform. Although the paper didn't say much about how they actually ran their experiments, I assume that they batch two phases: 1) train with sequences found on the powerpc platform, and record all of the state change and performance results, 2) feed the results from (1) into the x86 half of their implementation, discovering the translation rules. They didn't say much about how certain information about the architectures is encoded, such as register layout, flags, but did mention how they handled the stack and heap. I'm assuming the architectural details and general info about the instruction set encoding could be represented in some high-level interpreted language or configuration file.

Their approach is computationally complex, so it takes about a week to get a good set of rules. One source for additional research would be to look into optimizations for the approach. Pruning the search tree of possible sequences and finding register mapping more efficiently are particular examples. However, once the translation rules are found, the binary translator can be used with minimal overhead (avg ~67% native in their case).

Interestingly, the translated code often performed better than the native on microbenchmarks. This, they mention, could be due the fact that code is fundamentally easier to optimize on a RISC architecture such as PowerPC. When that highly optimized code is then translated to x86, a CISC architecture, the translated code is better optimized than the native x86 instructions used in the benchmarks. One thing to note here is that it is very difficult to compare performance across different architectures, so in general, this is a touchy subject. However, the approach in this paper is using relative execution costs, to find the best possible translation sequence of instructions such that performance is optimized and correctness is ensured. Also, I'm assuming all comparisons are done between translated x86 code and native x86 code from the x86 versions of the benchmarks (with some unspecified level of optimization).

Experiments were only performed on a static translator, although they do explain that their method could be theoretically applied to a dynamic translator. They calculate the overhead that would result from dynamic translation, and try to compare, but I'm not quite sure their analysis is correct, have to check this. I think they are ignoring the fact that there will be repeated
invocations of the algorithm that determines the best register mapping, as the register mappings change with different sequences of instructions. It seems like a bad idea to keep changing the register mappings, because the memory layout of the translation cache and representation of the virtual cpu will change continuously. However from my experience implementing a dynamic translator, the translation overhead is typically very low compared to the overhead due to low instruction quality (execution time of the instructions from the cache). The only difference in my case was that my source and destination were the same architecture (roughly), so the translation module itself was very efficient, also since many of the instructions had identical translations (and it was a RISC architecture). The point here is, that I think it is an open problem whether or not a performant dynamic translator would result from this work, although I am optimistic.

What I mostly learned from this paper is the material on superoptimizers. It makes sense that this would be a natural application, and I think that it's a good overlap between OS and Programming Languages. Also, it was good to get a review on issues in binary translation, which I have a lot of knowledge of (certainly, from implementing a full-system dynamic binary translator from scratch!). The paper touched on a large numbers of the problems I had to deal with during implementation. They don't go into too much depth on any one of these, but it definitely jogged my memory and made me remember the additional things you have to worry about when the translator is dynamic.

Unfortunately, I don't think their contribution can be applied to writing a same-architecture translator that includes translation of kernel code (full-system), with much reduction on the engineering effort. This is because much of the engineering complexity in this case has to do with branch handling, spilling/filling registers, exception handling and redirection, emulating memory accesses to protected data or memory mapped I/O, emulation of interrupt logic and low-level devices (ie, timer, serial port), and synchonizing resources among emulated threads. Additionally, a translator that translates between the same source and target instruction sets trivializes many of the translation rules, because many non-priveleged instructions will have identical translations. But, for a basic survey of fundamental binary translation issues for mostly user-level code between different instruction sets, this is a good paper.

Programming the Garcia Robot

2009-05-28T16:50:00.000-07:00

Over the past few years, I've received emails from various students at universities around the world, wanting to find out how to write software for their Garcia Robot. The product is made by Acroname, Inc. and comes with a wide variety of options. Most of what I focus on here is the software aspect of the system, which requires an embedded computing platform. Acroname ships the Garcia with a Stargate board, sold by Crossbow Solutions, equipped with a USB port, a PCMCIA slot for wireless networking, two serial ports for interfacing with sensors/actuators, and an ARMv5-based Intel XScale CPU.

Besides the main computer described above, the Garcia also includes a micro-controller board, called the Brainstem, that provides a serial interface for controlling 2 wheel motors and accessing data from infra-red sensors and the ledge detector. Knowing the various ways of interfacing with the Brainstem is key to being able to write complex programs to control every aspect of the robot's behavior.

The Stargate platform runs a provided distribution of Linux. It is therefore possible to develop applications using the system call APIs (ie, read()/write()) in order to receive and send data over a serial port to the Brainstem. This is a cumbersome but useful way to gain precise control over all of the operations of the Brainstem, but is usually only a good option if predictability is needed for timeliness experiments. Also, this method requires the developer to understand many details about the Brainstem architecture and configuration.

Included with the software is a cross-compiler toolchain. Various toolchains for ARM-based platforms can be downloaded from the web, but they all provide an assembler, compiler, linker and other tools for generating ARM binaries using an x86-based pc for the development environment. Once a program is compiled, it can be uploaded to the Stargate via a wireless network, and subsequently executed.

Brainstem Commands

A Brainstem command is a variable-length sequence of bytes, with the following format:

The module field specifies the address of one of the two available modules on the Brainstem: the GP and the MOTO. The MOTO controls the motors and some of the infra-red sensors, and the GP controls the rest of the sensors. Refer to manuals on Acroname's website for details on which module is associated with each of the sensors/actuators. By default, the module address of the GP is 2, and the MOTO is configured at address 4.

Following the module address, the second byte of the command specifies the length in bytes of the command packet, not including the first two bytes for the module and length. Next, the command field specifies one of the many possible commands to execute. Acroname maintains a list of these commands and their argument formats in their Brainstem reference. Each command has a different number of arguments with varying semantics, so following the command field there are zero or more argument bytes.

The following is an example of a command packet that tells the Brainstem to set the velocity of one of the motors to the value 10: 4 4 62 0 0 10. Here, the first byte of value 4 specifies that this packet is for the MOTO module. The third byte of value 62, specifies the command number that sets the motor velocity, and the following bytes are the command's arguments, which specify to set the motor with index 0 to a velocity of 10 units. The command and its arguments have a combined size of 4 bytes, thus 4 is specified as the length field in the second byte of the packet.

In many cases, after a command is sent to the Brainstem, a reply will be sent back through the serial port in the form a debug packet. For example, after informing the GP module to do an infra-red sensor reading, a debug packet containing the value read from the sensor can be obtained via a read() call on the serial port's file descriptor.

An Example Program

The code for a simple console program is listed below, as an example of how to send Brainstem commands over the Stargate's serial port. The code uses standard APIs and assumes that the serial port device file is located at /dev/cua0. This code is intended for illustrative purposes only, and may need to be tweaked for use in practice. The values for the command bytes are read from the standard input and sent in binary format using the write() system call on the file descriptor of the serial port.

#include <stdio.h>
#include <stdlib.h>

#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>

#define MAX_COMMAND_BYTES 50
#define SERIAL_PORT "/dev/cua0"

main()
{
   int i;

   int fd;
   size_t bytes_written;
   char command_bytes[MAX_COMMAND_BYTES];

   // Open the serial port for writing
   fd = open(SERIAL_PORT, O_RDWR | O_SYNC);

   if(fd < 0)
   {
      printf("Failed to open serial port\n");
      exit(1);
   }

   while(1)
   {
      // Collect command byte values from user
      printf("Enter Command >> ");

      scanf("%d %d", &command_bytes[0], &command_bytes[1]);

      for(i = 0; i < command_bytes[1]; i++)

         scanf("%d", &command_bytes[i+2]);

      // Send command packet to serial port
      bytes_written = 0;

      do
      {
         bytes_written = write(fd, (void *)(command_bytes + bytes_written),
                               (size_t)(command_bytes[1] + 2) - bytes_written);

         if(bytes_written < 0)
         {
            printf("Error writing to serial port: %d\n", bytes_written);

            exit(1);
         }
      } while(bytes_written < (size_t)(command_bytes[1] + 2));

      printf("Sent command to module %d, length %d:", command_bytes[0],
             command_bytes[1]);

      for(i = 2; i < (command_bytes[1] + 2); i++)

         printf(" %d", command_bytes[i]);
      printf("\n");
   }
}

References

Acroname, Inc.: http://www.acroname.com
Crossbow Solutions XScale Platform: http://blog.xbow.com/xblog/stargate_xscale_platform/
Stargate Resources: http://platformx.sourceforge.net/Links/resource.html

A Real-time Systems Tutorial

2009-05-14T18:09:00.000-07:00

Real-time systems design is an increasingly important topic in systems research communities as well as the software industries. Real-time applications and their requirements can be found in almost every area of operating systems and networking research. An incomplete list of such domains includes distributed systems, embedded systems, network protocol processing, aircraft design, spacecraft design..., and the list goes on. This page is intended to give the reader a brief, however incomplete, introduction to the concept of real-time tasks and their implications in the design of operating systems.

Real-time Task Models

In order to understand the functions of a real-time system, it is necessary to develop models of real-time activities and study their characteristics.
In this section, two fundamental real-time task models are described: periodic and aperiodic real-time tasks.

Periodic Real-time Tasks

In general, a real-time task requires a specified amount of particular resources during specified periods of time. A periodic task is a task that requests resources at time values representing a periodic function. That is, there is a continuous and deterministic pattern of time intervals between requests of a resource. In addition to this requirement, a real-time periodic task must complete processing by a specified deadline relative to the time that it acquires the processor (or some other resource).

For simplicity, assume that a real-time task has a constant request period (ie, must begin execution on the processor every n milliseconds). We can characterize such tasks as a tuple of values, (C, T), where T denotes the request period, which corresponds to the amount of time between temporally adjacent requests, and C represents the service time, or the amount of time for which the task must execute (in total) before a deadline, which is typically assumed to occur at the start of the next request period.

For example, a robotics application may consist of a number of periodic real-time tasks, which perform activities such as sensor data collection or regular network transmissions. Suppose the robot runs a task that must collect infrared sensor data to determine if a barrier is nearby at regular time intervals. If the configuration of this task requires that every 5 milliseconds it must complete 2 milliseconds of collecting and processing the sensor data, then the task is a periodic real-time task, and can be characterized in this model as the tuple: (C=2ms, T=5ms).

Aperiodic Real-time Tasks

The aperiodic real-time task model involves real-time activities that request a resource during non-deterministic request periods. There may either be no bound or only a statistical bound on the arrival period of
individual requests (task instances). Each task instance is also associated with a specified deadline, which represents the time necessary for it to complete its execution.

Examples of aperiodic real-time tasks are found in event-driven real-time systems, such as ejection of a pilot seat when the command is given to the navigation system in a jet fighter. Many, less time-sensitive, applications also arise in distributed systems involving real-time streaming media (ie, end-host routing over a logical overlay).

Real-time Scheduling

One of the most important responsibilities of a real-time system is to schedule tasks according to their deadlines in order to guarantee that all real-time activities achieve the required service level. Many scheduling algorithms exist for a variety of task models, but fundamental to many of these are the earliest deadline first (EDF) and rate-monotonic (RM) scheduling policies. A schedule for a set of tasks is said to be feasible if a proof exists that every task instance in the set will complete processing by its associated deadline.
Also, a task set is schedulable if there exists a feasible schedule for the set. The utilization associated with a given task schedule and resource (ie, CPU) is the fraction of time that the resource is allocated over the time that the scheduler is active.

Earliest Deadline First

The EDF scheduling algorithm is a preemptive and dynamic priority scheduler that executes tasks in order of the time remaining before their corresponding deadlines. Tasks with the least time remaining before their deadline are executed before tasks with more remaining time. At each invocation of the scheduler, the remaining time is calculated for each waiting task, and the task with the least remaining time is dispatched. If a task set is schedulable, the EDF algorithm results in a schedule that achieves optimal resource utilization. However, EDF is shown to be unpredictable if the required utilization exceeds 100%, known as an overload condition. EDF is useful for scheduling aperiodic tasks, since the dynamic priorities of tasks do not depend on the determinism of request periods.

Rate Monotonic

Recall the parameterization of a real-time periodic task as a tuple (C, T). Under the static-priority rate monotonic scheduling algorithm, tasks are ordered according to the value of their request period, T. Tasks with shorter request periods are assigned higher priority than those with longer periods. Liu and Layland proved that a feasible schedule is found under rate monotonic scheduling if the total requested utilization is less than or equal to ln(2), which is approximately 69.3%.

RM scheduling is optimal with respect to maximum utilization over all static-priority schedulers. However, this scheduling policy only supports tasks that fit the periodic task model, since priorities depend upon request periods. Because the request times of aperiodic tasks are not always predictable, these tasks are not supported by the RM algorithm, but are instead typically scheduled using a dynamic priority scheduler such as EDF.

Hard vs. Soft Real-time

The issue of predictability is of key concern in real-time systems. In fact, the term "predictable" can often be found in the multitude of definitions of real-time in the literature. Both periodic and aperiodic tasks have strict timing requirements in the form of deadlines. That is, the scheduler must be able to guarantee that each task is allocated a resource by a particular point in time, based on the task's parameters. In order to accomplish this, every allocation of any resource to any task must incur a latency that is deterministic or that can at least be predicted within a statistical margin of error.

Hard real-time tasks are required to meet all deadlines for every instance, and for these activities the failure to meet even a single deadline is considered catastrophic. Examples are found in flight navigation, automobile, and spacecraft systems. In contrast, soft real-time tasks allow for a statistical bound on the number of deadlines missed, or on the allowable lateness of completing processing for an instance in relation to a deadline. Soft real-time applications include media streaming in distributed systems and non-mission-ciritical tasks in control systems.

Real-time Networking

The growth in number of real-time distributed applications has fueled interest in methods for providing predictable communication-related services. Consider a wireless sensor network designed to locate injured civilians in disaster areas, or a networked application that allows a surgeon to control medical instruments from a distance. Many researchers are developing real-time network protocols and operating system mechanisms to ensure predictability of data distribution for such applications.

The real-time transport protocol (RTP) is a protocol based on UDP and is typically used in video/audio streaming applications in which there is a high tolerance for packet loss and low tolerance for delay variation. RTP is used in both multicast and unicast scenarios along with RTCP for transmission of control messages that carry quality feedback data.

Even if real-time networking protocols are employed, predictable service may not be possible unless end-host operating systems are equipped with appropriate mechanisms for processing incoming/outgoing network packets. These services typically dispatch event handlers in interrupt context in order to respond to events on the network, such as a packet received or ready for transmission. Systems such as RTLinux and RTAI, when used in conjunction with extensions like RTNet, provide deterministic timing guarantees on network packet processing and thus allow for real-time communication assuming that the low level network protocols in use are sufficiently predictable.

A Survey of Real-time Systems

The following is a list of some well-known real-time systems and links to more information:

QNX Neutrino Realtime Operating System

VxWorks RTOS

RTLinuxPro
and RTLinuxFree at FSMLabs

RTAI - the RealTime Application Interface for Linux

Montavista Real-time Linux

Xenomai - Real-time framework for Linux

RTnet - Hard Real-Time Networking for Real-Time Linux

Conclusion

As real-time applications become ubiquitous in various areas of computing research, there is motivation to extend existing systems with the mechanisms and policies necessary for providing predictable service. Also, many new real-time task models are being investigated in order to devise suitable scheduling algorithms for these new applications. Computer scientists will continue to analyze these new methods and apply them in situations where predictability and timeliness is of key consideration. Real-time systems is a rich domain for further study and will most likely continue to thrive for years to come.