TL;DR
This paper presents automated system-level design techniques for mapping applications onto complex network processor architectures. By employing Integer Linear Programming (ILP) and heuristic approaches, the authors tackle the challenges of process allocation and data mapping to maximize application throughput, achieving significant performance improvements.
What Problem Does This Paper Address?
Modern network processors (NPs) are incredibly powerful, featuring symmetric multiprocessing (SMP), block multithreading, and multiple memory hierarchies. These architectures are designed to handle the ever-increasing demands of network traffic. However, programming these complex systems is a significant challenge. Developers must manually partition applications, assign tasks to processors, and manage data placement across various memory elements. This low-level, manual approach is time-consuming, error-prone, and hinders design reuse. The paper aims to automate this process, providing techniques that can automatically map applications to NP architectures to achieve optimal performance.
Methods
The authors propose a two-stage system-level design methodology:
- Process to Processor Assignment: This stage focuses on mapping application processes to the available processors. It integrates two key transformations:
- Merge Transformation: Combines high-throughput processes to create a more uniform workload distribution.
-
Replicate Transformation: Creates additional copies of low-throughput processes to improve overall performance. These transformations are applied using both ILP formulations (for optimal solutions) and heuristic techniques (for faster, near-optimal solutions). The ILP approach uses a "batching" strategy to group processes before assigning them to processors.
-
Multithreading-Aware Data Mapping and Thread Selection: This stage maps data items (scalars, aggregates, FIFOs, shared memories) to the NP's memory hierarchy and determines the optimal number of threads to run on each processor. The goal is to exploit multithreading to hide memory access latencies, considering tradeoffs between memory capacity, access time, and hardware multithreading support. This stage also uses both ILP and heuristic approaches.
Datasets
The authors evaluated their techniques on three representative network processing applications: AH authentication, Diffserv conditioning, and IPv4 forwarding. These applications were implemented using a process-network model. The paper also describes the generation of synthetic applications with varying numbers of processes (25 and 50) to test scalability.
Key Insights and Ideas
- Multithreading and Data Mapping are Interdependent: The effectiveness of multithreading in hiding memory latency is heavily dependent on how data is mapped to memory. Optimizing one without considering the other leads to suboptimal results.
- Process Transformations are Crucial: Merging and replicating processes can significantly alter the application's structure and improve its overall throughput by balancing workloads and addressing bottlenecks.
- Automated Design is Essential: The complexity of modern NP architectures necessitates automated tools to manage the design space exploration and achieve high-performance mappings efficiently.
- Heuristics Offer a Practical Alternative: While ILP provides optimal solutions, its computational complexity grows exponentially with problem size. Heuristic techniques offer a polynomial-time alternative that can generate high-quality solutions for larger, more complex applications.
Key Results
- The proposed techniques achieved significant performance improvements, with an average speedup of up to 6.0x compared to a base case without optimizations.
- Applying multithreading-aware data mapping and process transformations individually yielded improvements of 2.0x and 1.2x, respectively.
- The combined application of both optimizations resulted in a synergistic effect, leading to much greater speedups than simply multiplying individual gains.
- The performance model used for optimization was found to be accurate, with predicted throughput within 10% of actual observed throughput.
- For larger applications (e.g., 50 processes), the heuristic approach generated solutions in under a second, achieving throughput within 15% of the ILP solutions, which could not complete within 12 hours.
Limitations and Future Work
- Performance Model Simplifications: The current performance model accounts for only one context switch overhead per thread execution and does not explicitly consider memory contention or queuing delays. While this provides a good compromise between accuracy and ease of use, it could be refined.
- Worst-Case vs. Average-Case Performance: The optimization goal is to maximize worst-case throughput. However, different packets might take different paths through the network, leading to variations in average-case performance. Future work could address this by weighting processes based on packet path probabilities.
- Dynamic/Runtime Variations: The current approach focuses on static mapping. Future work could explore handling dynamic variations in process execution times or packet paths.
- Hardware Coprocessors and CAM: The authors suggest extending their techniques to incorporate specialized hardware coprocessors and Content Addressable Memory (CAM), which are common in network processors.
- Stochastic Optimization: Exploring stochastic optimization approaches like genetic algorithms or simulated annealing for solving the integrated process and data mapping problem is a promising direction.
- Multimedia Applications: Adapting the techniques for multimedia applications on multicore embedded processors is also identified as future work.
Summary updated