TY - GEN
T1 - CaT
T2 - 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2023
AU - Gao, Xiangyu
AU - Raghunathan, Divya
AU - Fang, Ruijie
AU - Wang, Tao
AU - Zhu, Xiaotong
AU - Sivaraman, Anirudh
AU - Narayana, Srinivas
AU - Gupta, Aarti
N1 - Funding Information:
In additional experiments, we study the resource allocation time of switch.p4 as a function of the parameters of the Menshen back-end target. We vary the maximum number of entries per table, number of stages, and number of tables per stage, and plot the runtime of Gurobi in both optimal and feasible mode in Figures 9, 10, 11. A vertical line indicates the transition from infeasibility to feasibility for the constraint solver. Across a variety of hardware configurations, we find that the runtime of both modes are quite similar. Figure 9 shows that runtime increases as the maximum number of entries decreases because of an increase in the number of partitions of a table as the maximum number of entries decreases. Figure 10 shows that runtime increases as the number of stages increases because of the increase in the number of indicator variables tracking which stage a table belongs to. In Figure 11, the number of Gurobi variables is constant as we vary the number of tables per stage; The runtime is similar for optimal and feasible modes, but varies significantly depending on whether there is a solution. 8 CONCLUSION We introduce a new decomposition of the compilation problem for packet pipelines into 3 phases: resource transformation, resource synthesis, and resource allocation, where solver engines (e.g., ILP, SMT, program synthesis) are employed extensively within these phases. We prototype CaT, a compiler for P4 programs based on this decomposition. CaT can handle more programs, reduce pipeline resource usage, compile faster, and requires fewer compute resources than existing compilers. We hope our results encourage compiler engineers for such pipelines to adopt similar ideas. ACKNOWLEDGEMENTS We are grateful to the anonymous ASPLOS reviewers, Jiaqi Gao, and Aurojit Panda, for their valuable comments on previous drafts of this paper. We thank Tiancheng Hou, Danny (Xiaoqi) Chen, Sata Sengupta, Divyam Madaan, and Kexin Jin for their help with compiler improvement and providing motivating benchmarks. This work was supported in part by grants from the Network Programming Initiative and the National Science Foundation: NSF-2008048, NSF-1837030, NSF-2107138, NSF-2019302, NSF-1910796. DATA AVAILABILITY STATEMENT The source code and data are publicly available in the repository https://github.com/CaT-mindepth.
Publisher Copyright:
© 2023 ACM.
PY - 2023/3/25
Y1 - 2023/3/25
N2 - Compiling high-level programs to high-speed packet-processing pipelines is a challenging combinatorial optimization problem. The compiler must configure the pipeline's resources to match the semantics of the program's high-level specification, while packing all of the program's computation into the pipeline's limited resources. State of the art approaches tackle individual aspects of this problem. Yet, they miss opportunities to produce globally high-quality outcomes within reasonable compilation times. We develop a framework to decompose the compilation problem for such pipelines into three phases-making extensive use of solver engines (e.g., ILP, SMT, and program synthesis) to simplify the development of these phases. Transformation rewrites programs to use more abundant pipeline resources, avoiding scarce ones. Synthesis breaks complex transactional code into configurations of pipelined compute units. Allocation maps the program's compute and memory to the pipeline's hardware resources. We prototype these ideas in a compiler, CaT, which targets (1) the Tofino programmable switch pipeline and (2) Menshen, a cycle-accurate simulator of a Verilog description of the RMT pipeline. CaT can handle programs that existing compilers cannot currently run on pipelines and generates code faster than existing compilers, where the generated code uses fewer pipeline resources.
AB - Compiling high-level programs to high-speed packet-processing pipelines is a challenging combinatorial optimization problem. The compiler must configure the pipeline's resources to match the semantics of the program's high-level specification, while packing all of the program's computation into the pipeline's limited resources. State of the art approaches tackle individual aspects of this problem. Yet, they miss opportunities to produce globally high-quality outcomes within reasonable compilation times. We develop a framework to decompose the compilation problem for such pipelines into three phases-making extensive use of solver engines (e.g., ILP, SMT, and program synthesis) to simplify the development of these phases. Transformation rewrites programs to use more abundant pipeline resources, avoiding scarce ones. Synthesis breaks complex transactional code into configurations of pipelined compute units. Allocation maps the program's compute and memory to the pipeline's hardware resources. We prototype these ideas in a compiler, CaT, which targets (1) the Tofino programmable switch pipeline and (2) Menshen, a cycle-accurate simulator of a Verilog description of the RMT pipeline. CaT can handle programs that existing compilers cannot currently run on pipelines and generates code faster than existing compilers, where the generated code uses fewer pipeline resources.
KW - Programmable switches
KW - code generation
KW - integer linear programming
KW - packet processing pipelines
KW - program synthesis
UR - http://www.scopus.com/inward/record.url?scp=85159329296&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85159329296&partnerID=8YFLogxK
U2 - 10.1145/3582016.3582036
DO - 10.1145/3582016.3582036
M3 - Conference contribution
AN - SCOPUS:85159329296
T3 - International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS
SP - 72
EP - 88
BT - ASPLOS 2023 - Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
A2 - Aamodt, Tor M.
A2 - Jerger, Natalie Enright
A2 - Swift, Michael
PB - Association for Computing Machinery
Y2 - 25 March 2023 through 29 March 2023
ER -