Introduction

Image compression, whether for still pictures or motion pictures (e.g., video), plays an important role in internet and multimedia applications, digital appliances such as HDTV, and handheld devices such as digital cameras and mobile phones. Compression allows one to represent images and video with a much smaller amount of data and negligible quality loss. The reduction in data decreases storage requirements (important for embedded devices) and provides higher effective transmission rates (important for internet enabled devices).

Unfortunately, implementing a compression scheme can be especially difficult. For performance reasons, implementations are typically not portable as they are tuned to specific architectures. And while image and video compression is needed on embedded systems, desktop PCs, and high end servers, writing a separate implementation for every architecture is not cost effective. Furthermore, compression standards are also continuously evolving, and thus compression programs must be easy to modify and update.

A typical compression algorithm involves three types of operations: data representation, lossy compression, and lossless compression. These operations are semi-autonomous, data-parallel, and easily fit into a sequence of distinct processing steps. As such, image and video compression is a good match for the streaming model of computation, which affords certain advantages in terms of programmability, robustness, and achieving high performance. Our goal is to implement well-known still image and motion picture compression standards---such as JPEG and MPEG-2---in StreamIt[1], a high-level architecture-independent language for the streaming domain. This will result in clean, malleable, and portable codes. In addition, using the stream-aware StreamIt compiler, we will produce highly optimized codes that are competitive with hand-tuned implementations. Our architecture targets include conventional processors, as well as new and emerging wire exposed[2] and multi-core architectures.

Approach

This work is in the context of the StreamIt programming language[1], an architecture-independent stream language that aims to improve programmer productivity within the streaming domain. StreamIt provides an intuitive programming model, allowing the programmer to build an application by connecting components together into a stream graph, where the nodes represent actors that carry out the computation, and edges represent FIFO communication channels between actors. As a result, the parallelism and communication topology of the application are exposed, empowering the compiler to perform many stream-aware optimizations[3,4] that elude other languages.

While StreamIt formerly required every execution of an actor to consume and produce a constant number of items from its input and output channels, recent extensions of the language allow for variability of the I/O rates. For example, the rate at which items are produced or consumed may now be a function of the input data. This extension allows StreamIt to extend to a whole new class of data-dependent applications, including graphics, encryption, and data compression.

We have chosen to build both a JPEG and an MPEG-2 encoder/decoder in StreamIt. In these applications, there are several processing steps that can run in parallel. For example, the processing of YUV color channels, which represent the luminance and chrominance, are independent. In StreamIt, this type of parallelism is trivial (and natural) to express. In addition, when compressing several still images at a time, or during motion picture compression (which is substantially more involved), the task level parallelism between the various parts of the coders naturally follows from the organization of the application. Thus there exists a lot of flexibility in compiling the coders to yield high-performance implementations.

Progress

We have completed an implementation of a JPEG encoder/decoder, and an implementation of an MPEG encoder/decoder is underway. The former is concerned with still image processing, whereas the latter is for motion pictures. However, they share many similar structures related to compression and data transformation. We have two sample JPEG applications: one decodes a baseline, photo quality JPEG image and re-encodes it as a highly compressed, low-quality JPEG image. Another application converts a file from JPG to BMP. These two applications let us test both encoding and decoding, and represent typical usage examples.

Figure 1. JPEG decoder front-end. The YUV color channels can be processed in parallel.

Future Work

Image compression, and other streaming programs with variable rate I/O, are challenging from a compiler point of view. With static I/O rates, the compiler can fully orchestrate the execution of the actors in the stream program and achieve very high performance[5]. By contrast, with dynamic I/O rates, the compiler cannot statically schedule the execution of actors, since some necessary details aren't known until runtime. Our compiler effort is geared toward efficiently compiling streaming programs with dynamic behavior. This effort is two-pronged, in that not only are we planning to investigate new compilation strategies, but also, we will investigate language-level primitives that will lessen the burden on the compiler to carry out heroic feats.

Research Support

The StreamIt project is supported by DARPA grants PCA-F29601-03-2-0065 and HPCA/PERCS-W0133890; NSF awards CNS-0305453 and EIA-0071841; and the MIT Oxygen Alliance.

References

[1] William Thies, Michal Karczmarek, and Saman Amarasinghe. StreamIt: A Language for Streaming Applications. In Proceedings of the 2002 International Conference on Compiler Construction. Grenoble, France, April, 2002.

[2] Michael Taylor, Walter Lee, Jason Miller, David Wentzlaff, Ian Bratt, Benjamin Greenwald, Henry Hoffman, Paul Johnson, Jason Kim, James Psota, Arvind Saraf, Nathan Shnidman, Volker Strumpen, Matthew Frank, Saman Amarasinghe, and Anant Agarwal. Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams. In Proceedings of the 31st Annual International Symposium on Computer Architecture, Munich, Germany, June, 2004.

[3] Andrew Lamb, William Thies, and Saman Amarasinghe. Linear Analysis and Optimization of Stream Programs. In Proceedings of the SIGPLAN '03 Conference on Programming Language Design and Implementation, San Diego, California, June, 2003.

[4]Janis Sermulins, William Thies, Rodric Rabbah, and Saman Amarasinghe. Cache Aware Optimization of Stream Programs. In Proceedings of the 2005 Conference on Languages, Compilers, and Tools for Embedded Systems, Chicago, Illinois, June 2005.

[5] Michael Gordon, William Thies, Michal Karczmarek, Jasper Lin, Ali Meli, Andrew Lamb, Chris Leger, Jeremy Wong, Henry Hoffmann, David Maze, and Saman Amarasinghe. In Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, California, October 2002.