Switch Code Generation Using Program Synthesis

Xiangyu Gao, Taegyun Kim, Michael D. Wong, Divya Raghunathan, Aatish Kishan Varma, Pravein Govindan Kannan, Anirudh Sivaraman, Srinivas Narayana, Aarti Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

Writing packet-processing programs for programmable switch pipelines is challenging because of their all-or-nothing nature: a program either runs at line rate if it can fit within pipeline resources, or does not run at all. It is the compiler's responsibility to fit programs into pipeline resources. However, switch compilers, which use rewrite rules to generate switch machine code, often reject programs because the rules fail to transform programs into a form that can be mapped to a pipeline's limited resources-even if a mapping actually exists. This paper presents a compiler, Chipmunk, which formulates code generation as a program synthesis problem. Chipmunk uses a program synthesis engine, SKETCH, to transform high-level programs down to switch machine code. However, naively formulating code generation as program synthesis can lead to long compile times. Hence, we develop a new domain-specific synthesis technique, slicing, which reduces compile times by 1-387x and 51x on average. Using a switch hardware simulator, we show that Chipmunk compiles many programs that a previous rule-based compiler, Domino, rejects. Chipmunk also produces machine code with fewer pipeline stages than Domino. A Chipmunk backend for the Tofino programmable switch shows that program synthesis can produce machine code for high-speed switches.

Original languageEnglish (US)
Title of host publicationSIGCOMM 2020 - Proceedings of the 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication
PublisherAssociation for Computing Machinery
Pages44-61
Number of pages18
ISBN (Electronic)9781450379557
DOIs
StatePublished - Jul 30 2020
Event2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM 2020 - Virtual, Online, United States
Duration: Aug 10 2020Aug 14 2020

Publication series

NameSIGCOMM 2020 - Proceedings of the 2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication

Conference

Conference2020 Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM 2020
Country/TerritoryUnited States
CityVirtual, Online
Period8/10/208/14/20

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Programmable switches
  • code generation
  • packet processing pipelines
  • program synthesis
  • slicing

Fingerprint

Dive into the research topics of 'Switch Code Generation Using Program Synthesis'. Together they form a unique fingerprint.

Cite this