Much of my research efforts have been driven by open problems that I have encountered in my consulting practice. In fact this research originated with a Bell Labs research and development project involving signal processing applications developed with the U.S. Navy's Processing Graph Method (PGM) [18]. I was asked to create an on-line algorithm that would allocate these real-time applications to processors in a distributed network. Although the problem is NP-hard, I had hoped some simple heuristic techniques would provide a reasonable (albeit not optimal) solution. Unfortunately, I found that there did not even exist a framework from which I could analytically evaluate possible allocations. The state-of-the art was to simulate execution scenarios -- an extremely time consuming and untenable option. Moreover, I found that there was no way to bound latency or memory requirements in the applications. Before I could evaluate heuristic allocation algorithms, a framework for evaluating processor demand, latency, and memory requirements of the applications was needed. This line of research is briefly described below.
The Synthesis of Real-Time Systems from Processing Graphs. Processing graphs are a standard design aid in the development of complex digital signal processing systems. These directed graphs consist of nodes and graph edges depicting the flow of data from one node to the next. When sufficient data arrives, a node executes its function from start to finish in isolation (i.e., without synchronization).
Processing graphs provide a natural description of signal processing applications with each node representing a mathematical function to be performed on a stream of data that flows on the arcs of the graph. The streams of input data are typically generated by sensors sampling the environment at periodic rates and sending the samples to the signal processor via an external channel. The processing graph methodology allows one to easily understand the signal processing performed by graphically depicting the structure of the algorithm. An important advantage of the graphical representation is that portions of the signal processing application (i.e., subgraphs) can be understood in the absence of the rest of the algorithm. Unfortunately, it is difficult to analyze the performance and processing requirements of applications developed with processing graph methodologies.
In my experience with clients, the primary problem in developing embedded signal processing applications with a processing graph methodology is building a predictable real-time system in which one can determine if the graph ``fits'' on a processor. A graph ``fits'' on a processor if enough processing capacity is available to guarantee a temporally correct execution. Typically a processing graph is mapped to a set of tasks accourding to a model of real-time execution (e.g.,[4, 10, 15, 16, 19, 24, 22, 23]). The schedulability conditions for the model are used to see if the graph ``fits'' on the processor by verifying processor capacity. Unfortunately for general processing graph methodologies, such as PGM, there is no obvious task model that efficiently describes the execution characteristics of nodes in the processing graph. Without a real-time task model and its schedulability conditions, the latency and memory requirements of an application cannot be evaluated.
The overall goal of my work is to create a synthesis method for building distributed real-time applications from processing graphs. As discussed below, I have already made significant progress towards this goal.
Mapping Nodes to Real-Time Tasks. The synthesis method begins with the creation of a PGM graph. Once a processing graph has been created, the nodes must be mapped to real-time tasks to provide temporal correctness. Therefore, the first problem to solve is identifying when nodes will execute so that the correct task model can be used. The most natural representation of node execution is achieved using the concept of node execution rates [7]. In [7, 8, 9], new theorems are presented that characterize the node execution rate of every node in a PGM graph. The synthesis of real-time systems from cyclic processing graphs is achieved by mapping the graph to real-time tasks according to the Rate Based Execution (RBE) model developed by Jeffay [11], and the RBE schedulability condition is used to verify processor capacity.
Once the processing graph has been mapped to a set of real-time tasks and a scheduling algorithm selected, issues such as latency and memory requirements can be addressed. Latency is the interval between the time when a signal arrives from the external sensor and the time when the processed signal is available to the output device. The memory requirements of a graph are dependent on the amount of buffering required by the graph edges during graph execution. Although system engineers have been unable to analyze the properties of latency and memory requirements in PGM graphs, we have shown that this is not an intrinsic property of the methodology. Moreover, by applying existing scheduling theory to PGM graphs, we have developed a framework for quantifying and managing both the latency and memory requirements of processing graphs.
Latency Analysis. There has always been a trade-off between latency and throughput in embedded signal processing applications. Prior to [5, 9], however, there has not been an analytical method for quantifying this tradeoff. We have identified two sources of latency in real-time systems created from processing graphs. The first, called inherent latency, is latency defined by the processing graph parameters. The second source of latency, called imposed latency, comes from the scheduling and execution of nodes in the graph. In [9], a framework is developed for evaluating latency using equations that provide upper and lower bounds for both types of latency. The trade-off between latency and throughput can now be quantified by evaluating latency and processor utilization using our equations.
Memory Requirements. Sizing the system to fit memory requirements is another major concern in embedded signal processing applications. An important aspect in controlling memory usage is the node execution schedule since this impacts the buffer requirements of the edges in the graph. The state of the art in minimizing the memory requirements of a signal processing graph is to create a node execution schedule off-line [14, 20, 25, 21, 3]. In contrast, our approach is to use a dynamic, on-line scheduler for graph execution. It is shown in [8] that preemptive earliest deadline first (EDF) scheduling can achieve near optimal memory usage and often requires less memory than static schedules created by off-line schedulers designed to minimize memory usage. Moreover, dynamic, rate-based scheduling has less imposed latency and can provide more control over deterministic response times of selected processing paths than static scheduling.
Applying the Theory. I am interested primarily in the practical application of research. As such, I have been continually applying and evaluating these research results in my consulting work. Moreover, to illustrate results from our research, we have used portions of actual applications to quantify the memory savings achievable and the latency incurred using our synthesis method.
For example, in [7] a Synthetic Aperture Radar (SAR) Application was used as the motivating problem. SAR data can be used to identify man-made objects on the ground or in the air by producing high-resolution, all-weather images in real-time, but it requires a tremendous amount of processing capacity [26]. Using the SAR graph, we have shown that on-line dynamic scheduling can be achieved with minimal imposed latency.
The memory requirements of an International Maritime Satellite (INMARSAT) mobile satellite receiver application was evaluated in [8]. INMARSAT is a global maritime communication and navigational system. For many acoustic signal processing applications, such as the INMARSAT mobile satellite receiver, memory requirements are more of a concern than processor capacity. We have shown that for these applications, dynamic, on-line scheduling can be achieved with near minimal buffer requirements using a fixed buffer for each queue and a simple EDF scheduler. When a shared buffer implementation is used, the buffer requirements of the graph are reduced below those of a comparable implementation scheduled off-line.
I have also evaluated the latency requirements of the distributed Directed Low Frequency Analysis and Recording acoustic signal processing application from the Airborne Low Frequency Sonar subsystem of the Block II upgrade to LAMPS MK III helicopters. This is one of several signal processing applications that must execute on a new distributed signal processing system being developed by General Dynamics. The latency bounds developed in [9] are being used to determine the number of processors and the amount of memory required in the new system for the application to meet its mission requirements.
Continuing Research. The current synthesis method uses uses a work-conserving scheduler -- a scheduler that never idles the processor when nodes are eligible for execution. I am investigating the use of a non-work-conserving scheduler that deliberately idles the processor at times when nodes are eligible for execution. Such a scheduler increases imposed latency, but may provide tighter bounds on the memory requirements of processing graphs. This line of research may also be of use when the operating system's scheduling algorithm cannot be modified since my non-work-conserving scheduling model can be used without changing the existing scheduling algorithm.
There are numerous practical problems still open, such as scheduling the rate based network traffic in a distributed system and the problem of allocating graphs to processors. A related research area that has gained considerable attention in recent years is the analysis and implementation of multimedia systems. Multimedia systems are often described using simple processing graphs [1, 12], and the RBE task model was created to support multimedia computing [11]. Thus, my research also provides a framework for analyzing latency in distributed multimedia systems.