Modern network processors employs parallel processing engines (PEs) to keep up with explosive internet packet processing demands. Most network processors further allow processing engines to be organized in a pipelined fashion to enable higher processing throughput and flexibility. In this paper, we present a novel program transformation technique to exploit parallel and pipelined computing power of modern network processors. Our proposed method automatically partitions a sequential packet processing application into coordinated pipelined parallel subtasks which can be naturally mapped to contemporary high-performance network processors. Our transformation technique ensures that packet processing tasks are balanced among pipeline stages and that data transmission between pipeline stages is minimized. We have implemented the proposed transformation method in an auto-partitioning C compiler product for Intel Network Processors. Experimental results show that our method provides impressive speed up for the commonly used NPF IPv4 forwarding and IP forwarding benchmarks. For a 9-stage pipeline, our auto-partitioning C compiler obtained more than 4X speedup for the IPv4 forwarding PPS and the IP forwarding PPS (for both the IPv4 traffic and IPv6 traffic).

Effective compilation of packet processing applications onto the Intel IXP network processors requires, among other things, the automatic use of multiple threads on one or more processing elements, and the automatic introduction of synchronization as required to correctly enforce dependences between such threads. We describe the program transformation that is used in the Intel Auto-partitioning C Compiler for IXP to automatically multithread/multi-process a program for the IXP. This transformation consists of steps that introduce inter-thread signaling to enforce dependences, optimize the placement of such signaling, reduce the number of signals in use to the number available in hardware, and transform the initialization code for correct execution in the multithreaded version. Experimental results show that our method provides impressive speedup for six PPSes (Packet Processing Stages) in the widely used NPF IP forwarding benchmarks. For most packet processing stages, our algorithms can achieve almost linear performance improvement after automatic multi-threading transformation. The automatic multi-processing transformation help further boost the speedup of two PPSes.

In recent work, we have described a data prefetch mechanism for pointer-intensive and numeric computations, and presented detailed measurements on a suite of benchmarks to quanti~its performance potential] [HM94, Meh96].In this paper we review a simple classification for memory access patterns on which the prefetch mechanism is based, and then take a close look at two codes from our suite.Focusing on just two programs allows us to display a wide range of slmulauon data.Results from this study several additional optimizations for future data prefetch mechanisms,

Two economic methods (Markov chain method and filtering method) which estimate the average working set size of a program on the fly are presented. Both methods are simple enough to be implemented inside a VLSI processor chip with small space requirements, or outside the chip to probe the memory reference traffic. The on-the-fly circuit tools that can estimate the average working set size of a program without much loss of accuracy make unnecessary the problematic and expensive procedures (hardware monitoring or simulation) of collecting the reference traces. Such tools can be used in all studies that require program locality measurements, including the study of a program locality, the effectiveness study of locality improvement techniques, and the study of optimizing compiler's effect on program locality. Since both methods require only one comparison and an increment of one or two counters per memory reference, they can be easily implemented as circuits to probe the reference traffic between the processor and the main memory.>

Parcel (Project for the Automatic Restructuring and Concurrent Evaluation of Lisp) is an investigation of the problem of compiling Lisp for evaluation on a shared memory multiprocessor. In this paper, we present an overview of the process of compilation in Parcel. This process consists, broadly, of an interprocedural analysis, followed by a function-level restructuring of the lambda expressions that constitute a program. We discuss both of these phases, and illustrate the steps of restructuring with a few examples. A novel representation for s-expressions is employed in Parcel, to facilitate the parallel creation and access of lists; we review this representation, and discuss its implications for the compilation process. We conclude with some preliminary performance measurements of the prototypes of the Parcel compiler and run-time system.