《Compiling Packet Programs to Reconfigurable Switches》改编演讲PPT

Compiling Packet Programs to Reconfigurable SwitchesLavanya Jose, Lisa Yan,Nick McKeown, and George Varghese1Research funded by AT&T, Intel, Open Networking Research Center.2Author Lavanya Jose Lisa Yan Nick McKeown George Varghese3Author Lavanya Jose Lisa Yan Nick McKeown George Varghese4The Mckeown Group5http:/yuba.stanford.edu/group_wp/Author Lavanya Jose Lisa Yan Nick McKeown George Varghese6In the next 20 minutes Fixed-function switch chips will be replaced by reconfigurable switch chips We will program them using languages like P4 We need a compiler to compile P4 programs to reconfigurable switch chips.7Fixed-Function Switch ChipsQueuesL2 StageIPv4StageParserIPv6 StageACL StageL3L2PacketPacket8L2v4v6ACLControl Flow GraphSwitch PipelineControl Flow GraphSwitch PipelineFixed-Function Switch ChipsQueuesL2 StageIPv4StageParserIPv6 StageACL StageL2 TableIPv4 TableIPv6 TableACL TableFixed ActionFixed ActionActionFixed ActionL2v4v6ACLControl Flow GraphSwitch PipelineMyEncapMyEncap910Fixed-Function Switch Chips Are Limited1. Cant add new forwarding functionality2. Cant add new monitoring functionality3. Cant move resources between functionsQueuesL2 StageIPv4StageParserIPv6 StageACL StageFixed ActionFixed ActionActionL2 TableFixed ActionIPv4 TableIPv6 TableACL TableControl Flow GraphSwitch PipelineReconfigurable Switch ChipsQueuesParserFixed ActionFixed ActionFixed ActionL2 TableFixed ActionIPv4 TableIPv6 TableACL TableMatch TableMatch TableMatch TableMatch TableL2v4v6ACLAction MacroAction MacroAction MacroAction Macro11Protocol Independent SwitchControl Flow GraphSwitch PipelineReconfigurable Switch ChipsQueuesParserL2 TableIPv4 TableACL TableIPv6MyEncapL2v4v6ACLMyEncapL2 Action Macrov4 Action MacroACL Action MacroActionMyEncapActionIPv4ActionIPv4Action12IPv6IPv4ActionRMT & Intels FlexPipeReconfigurable chips are inevitable.13QueuesParserFixed ActionFixed ActionFixed ActionL2 TableFixed ActionIPv4 TableIPv6 TableACL TableMatch TableMatch TableMatch TableMatch TableP4 (http:/p4.org/)parser parse_ethernet extract(ethernet);select(latest.etherType) 0 x800 : parse_ipv4; 0 x86DD : parse_ipv6; table ipv4_lpm reads ipv4.dstAddr : lpm; actions set_next_hop; drop; control ingress apply(l2_table); if (valid(ipv4) apply(ipv4_table); if (valid(ipv6) apply(ipv6_table); apply (acl);L2v4v6ACLAction MacroAction MacroAction MacroAction Macro14(ANCS13)ParserMatch ActionTablesControl Flow GraphConfiguring Switch ChipsP4 codeCompilerCompiler TargetQueuesParserFixed ActionFixed ActionFixed ActionL2 TableFixed ActionIPv4 TableIPv6 TableACL TableMatch TableMatch TableMatch TableMatch TableAction MacroAction MacroAction MacroAction Macro15Control Flow GraphL2Table Dependency Graph (TDG)v4v6ACLL2v4v6ACLTable Dependency Graph16Step 1: P4 ProgramStep 2: Control Flow GraphL2v4v6ACL17Step 3: Table Dependency GraphL2v4v6ACLStep 4: Table Configuration18Header widthsAction ALU inputMemory TypeTable parallelismMore resource constraintsAction MemoryMap match action tables in a TDG to a switch pipeline while respecting dependency and resource constraints.The Compiler Problem19Two Switches We Studied123432RMT32 Stages(SIGCOMM 2013)20Memory information for RMTTwo Switches We Studied14352FlexPipe5 Stages(Intel FM6000)21Memory information for FlexPipeTwo Switches We Studied12343214352RMT32 Stages(SIGCOMM 2013)FlexPipe5 Stages(Intel FM6000)2223Two Switches We Studiedword-packingFirst approach: Greedy Prioritize one constraint Sort tables Map tables one at a timeQueuesParser241234Sort by # dependenciesFirst approach: GreedyQueuesParser1 Prioritize one constraint Sort tables Map tables one at a time23411Sort by match width25 FFLFirst Fit by Level FFDFirst Fit Decreasing FFLSFirst Fit by Level and Size MCFMost Constrained First 26First approach: GreedyToo many constraints for Greedy Any greedy must sort tables based on a metric that is a fixed function of constraints. As the number of constraints gets larger, its harder for a fixed function to represent the interplay between all constraints. Can we do better than greedy?27Second approach:Integer Linear Programming (ILP)Find an optimal mapping.Pros: Takes in all constraints Different objectives Solvers exist (CPLEX)28Cons: Blackbox solver Encoding is an art SlowILP Setupmin # stagessubject to: dependency constraints29table sizes assigned memoriesassignedtable sizes specified memories inphysical stageExperiment Setup30Greedy vs ILPA Typical TDG31IPv6-McastEG-ACL1EG-Phy-MetaIG-Agg-IntfIG-DmacIPv4-McastIPv4-NexthopIPv6-NexthopIG-PropsIG-Router-MacIpv4-EcmpIG-SmacIpv4-Ucast-LPMIpv4-Ucast-HostIpv6-Ucast-HostIpv6-Ucast-LPMIpv6-EcmpIG_ACL2IG_Bcast_StormIpv4_UrpfIpv6_UrpfIG_ACL1EG_PropsIG_Phy_MetaMetrics: Greedy vs ILP1. Ability to fit program in chip1. Optimality2. Runtime32Experiment Results335-stage FlexPipeRMT for L2L3-ComplexGreedy vs ILPs34Greedy vs ILP35ILP solution(16 stages)Greedy vs ILP36FFL-16 solution(19 stages)Greedy vs ILPs37Comparing greedy heuristics38TDG for L2L3-MtagComparing greedy heuristics39FFLS solution (21 stages).FFL solution (19 stages).Comparing greedy heuristics40FFLS solution (21 stages).Comparing greedy heuristics41FFL solution (19 stages).Comparing greedy heuristics42TDG for L2L3-MtagPrioritize dependencies, not table size!Sensitivity Experiments To improve ILP running time To improve Greedy Optimality Original ILP solution 16 stages in12.13s 104 cycles in233.84s ILP Improvement 12.13s to 7.1s 233.84s to 66.29s43Use ILP to suggest best Greedy for program type.44Critical constraints Dependency critical: 16 13 stages Additional resource constraints less importantCritical resources TCAM memories critical: 16 14 stages Results for one of our datacenter L2/L3 use casesILP Run time Number of constraints? Not obvious. E.g., RMT Min. stage: few secs. Min. power: few secs. Min. pipeline latency 10 x slower Number of variables? How fine-grained is the resource assignment? E.g., FlexPipe One match entry at a time: many days. 100-500 match entries at a time: 1 hrConclusion Challenge: Parallelism and constraints in reconfigurable chips makes compiling difficult. TDG: highlights parallelism in program. ILP: better if enough time, fitting is critical, or objectives are complicated. Best Greedy: ILP can choose via notion of critical constraints and critical resources.46Thank you!47Research funded by AT&T, Intel, Open Networking Research Center.