Design insights for programmable, high performance datapaths

This post does not reflect the views of current, past, or future employers. The opinions in this article are my own.

If you follow my blogs, we’ve already discussed a lot of the pieces of datapath design to meet the seemingly contradictory requirements of programmability with high performance. Today I’d like to uplevel things a bit and present the insights driving this design.

#1 All hail Domain Specific Architecture

IMO, the biggest advancement in Computer Science, or at least Computer Architecture, in the last ten years is *Domain Specific Architecture*. Per Wikipedia: “A domain-specific architecture (DSA) is a programmable computer architecture specifically tailored to operate very efficiently within the confines of a given application domain”. Colloquially, this is saying we need to tailor the solution for the problem domain. The concept is brilliant! It’s an answer to the end of Moore’s Law and Dennard Scaling, and explains the rise of GPUs as the powerhouse behind AI and ML.

The “domain” in domain specific architecture can be ascertained by the nature of input data. For instance, the data processed by GPUs can be characterized as high volume, multi-dimensional data which is highly parallelizable. Denoising an image can be done in GPUs by breaking the picture into little chunks that are processed in parallel per an algorithm. In datapath processing, the input is serial data containing objects to be processed in order, like packets received on a network interface or protocol headers in a packet. The nature of this data is fundamentally different compared to GPUs and even CPUs. This motivates our domain specific architecture with specialized features for parallelism and CPU-in-the-datapath that are geared towards efficiently processing serial data.

Domain Specific Architecture for datpaths. This gives a high level overview of a domain specific architecture for a fully programmable, high performance datapath featuring CPU-in-the-datapath and accelerators.

#2 SW/HW co-design is downright necessity

I would call 2005–2020 the Golden age of networking software. The community produced a whole bunch of innovations including new TCP congestion control algorithms, QUIC protocol, stack parallelism, network virtualization, and XDP/eBPF. These were all done in software and didn’t require special hardware. But the times, they are a-changin’! We’ve reaped the low hanging fruit from software, and to meet the ever demanding requirements of modern workloads it’s clear that we need to integrate advanced hardware features in the datapath. But, this is easier said than done. For instance, in “The Fundamental Theorem of Offloads” we talked about the difficulties of software even trusting simple offloads.

All this leads to the conclusion that software/hardware co-design is essential going forward. Software/hardware co-design is a top-down process where software workloads drive hardware architecture. To me, this means that software and hardware engineers need to work together in unison to solve problems. If I had my way, hardware and software engineers would literally be sitting in the same room! I suppose in the post-Covid era the room might be virtual, but I think you get the point. In any case, mastering hardware/software co-design is going to be a work in progress for a while, but is essential and worth the effort!

#3 Overcoming the oxymoron

I always love a good oxymoron (who doesn’t!), and parallelism in serial data processing is a good one! Serial data wants to be processed in order or sequentially — as we said that is its nature. On the other hand parallelism, is one of the pillars for performance in computing so we’ll go to great lengths to leverage it wherever we can. The goal is to “find” parallelism in serial data processing that keeps the data happy!

Fortunately, we have a “get out of jail free card”. As long as the output of processing just matches that had the processing been done strictly in order, we can parallelize processing however we want! It’s kind of like how long division is taught in elementary school: there’s several techniques and they’re all considered valid if they always give the right answer.

This observation motivated the design for horizontal and vertical parallelism. Dependencies synchronization is the glue that ensures that the proper effects of in order processing of serial data is maintained. As an added bonus, deadlock with dependencies is impossible — try getting that with of conventional locks :-). To be fair, this is just a consequence of exploiting the unique attributes of the domain which is what domain specific architecture encourages us to do!

Horizontal and Vertical parallelism. This shows how eight packets might be processed in horizontal and vertical parallelism. These flavors of parallelism are aimed at parallelizing serial data processing.

#4 Constraints can be a good thing (really!)

Believe it or not, one of the things that make our design remotely feasible is a whole bunch of constraints. Consider that we endeavour to build a solution for CPU-in-the-datapath that can process upwards of a billion packets per second. To meet our power budget, we may be able to squeeze out 128 RISC-V running at 2Ghz. Assume an Instructions Per Cycle (IPC) of 1.5, that gives us a budget of about 380 instructions per packet. That’s not a lot! Processing a packet through the Linux stack can need thousands of instructions. So this is a tight constraint on the solution.

To meet the requirements, we can’t afford to mess around in the CPU! This leads to an apparent paradox: we want the CPU for programmability, but we also want to avoid it like the plague! The solution is to move whatever we can out of the CPU to accelerators. This includes data transforms (CRCs, crypto, compression), lookups (like for protocol control blocks), and pretty much any function operating on large amounts of memory. So what’s left for the CPU to do? Well, I think of the CPU as the orchestra conductor of datapath processing. It looks at small amounts of data, like packet headers, and just directs the operation and dataflow for the rest of processing. The result is that the processing in the CPU has to be super simple. The upshot is that constraints like this behoove us to obsessively pursue simplicity in design — fine by me, I love simplicity ! :-)

#5 Bucking conventional wisdom

Right off the bat, the whole concept of CPU-in-the-datapath runs contrary to conventional wisdom. I get why people are skeptical. After all relative to fixed function hardware, CPUs can be underperforming by at least an order of magnitude. But that’s thinking in terms of commodity CPUs. Domain specific architecture says we can tailor the CPU around the problem. Seamless use of parallelism is one way, but we can also streamline the CPU itself — no cache misses, no OS (run in bare metal), no interrupts, new specialized instructions, and a super fast context switch. After explaining the nuances, most people seem to get CPU-in-the-datapath. But there’s another thing lurking in our design that’s maybe even more controversial — we want to eliminate affinity!

Affinity is the “go to” mechanism to promote cache locality in scheduling parallel processing. For example, RSS steers packets belonging to the same TCP connection to the same CPU so that we don’t thrash the connection’s protocol control block between CPUs. RSS works great if there’s plenty of flows for good entropy. But with just a few flows that give low entropy, performance falls off a cliff. Ironically, I’ve spent much of my career promoting the cause of affinity (the first patch set I ever got into Linux was RPS which is a software analogue of RSS), but now I think affinity needs to go the way of the dodo bird! This topic, including mitigations for the loss of locality, warrants a separate article in itself and I really look forward to discussions with the community on this!

Effects of affinity in mutli-queue. In this example, a host receives six packets for each of three flows with four receive queues. The left side shows packet steering with affinity (RSS), two flows are hashed to the second queue and the other hashes to the third queue creating a visible load imbalance. On the right horizontal parallelism is used that disregards affinity, the load on the queues tends to a uniform distribution as shown.

#6 Amdahl’s Law: friend or foe?

Amdahl’s Law is one of the few true laws in Computer Science. It puts hard limits on how much benefit we get from performance improvements. It’s not just conventional wisdom, it’s the law! The gist of the Amdahl’s Law is that the overall improvement of a system is proportional to the portion of the system improved. Amdahl’s Law also predicts diminishing returns as more improvements are made.

There’s a cruel reality in Amdahl’s Law. I’ve seen many a project, including some of my own, where we put a lot of effort optimizing some algorithm or layer in the stack, only to find that there’s little or no measurable gain in production. That’s an effect of Amdahl’s law, and yes, it can be sobering and demoralizing at times.

On the other hand, I like to think of Amdahl’s Law as more of a compass (or maybe GPS) that tells us where to put our efforts. For instance, the law is used to predict the potential performance improvement of parallelism. The formula for that is:

S = 1 / (1 — P + (P / N))

Where:

S is the speedup of the system P is the proportion of the system that can be improved N is the number of processors in the system

For example, if we optimize 50% of the processing path by running it in parallel in four threads, but the other 50% is processed without parallelism then the speedup is 1.6. If we double the number of threads to eight the speedup is 1.77, and with sixteen threads the speedup is 1.88 which starts to show the effects of diminishing returns. Amdahl’s Law tells us that more time in parallel processing and more parallel processors are better, but it can also provide quantitative guidance on what to focus on. Should we work to parallelize the serial portions of a workload, or add more parallelism to the parts already parallelizable? — just plug in the numbers and find out!

Amdahl’s Law and vertical parallelism. In this example we show the time for processing a packet in vertical parallelism using 1, 2, and 4 threads. We assume that 50% of the processing must be serialized (the orange blocks) and 50% can be parallelized (blue blocks). The runtime and speedup is shown for the different number of threads (the 100 usecs runtime is just a baseline for demonstration purposes).

#7 It’s all about ease-of-use, stupid!

It’s not enough to build a programmable datapath solution, it has to be easily programmable. To me, that means that the programmer expresses what they want to do in a manner that’s convenient to them. It’s up to the compiler to do the hard work and translate that expression to a runnable image for some target. The question is: how easy can we make this?

On one extreme, we could try to make it so the programmer doesn’t need to do anything. They would just reuse the datapath code that they may have been running in production for years, and magically that same code would run on specialized hardware. Of course, that’s what everybody wants, but it’s next to impossible to pull off. It’s just not practical to take arbitrary code and make it run optimally on a specialized target. On the other extreme, we could mandate a new Domain Specific Language (DSL) for programming the datapath. P4 is a good example. The problem is that this can be akin to “boiling the ocean”. It requires new tool chains, practices, education, and considerations for maintainability, portability, and support. Worse yet, it raises the specter that outfits may need to hire engineering staff with a specialized skill set to support the language (i.e. the talent pool is small).

Our design takes a middle-of-the-road approach. We created a new programming model called PANDA. The model is language agnostic, and is supportable in any reasonably Turing complete language. PANDA employs data structures and functional APIs that are mapped to target hardware by a smart compiler. This is along the same lines as how CUDA does it. And in the same way that there’s CUDA-C and CUDA-Python, we can have PANDA-C, PANDA-Python, and PANDA-P4. The goal is to let the programmer use the language of their choice, but we ask them to use a straightforward API in their program. We’ll dive deeper into PANDA in some future articles.