Assembly Language Is Over (Converging Hardware and Software)

Spatial programming abstractions for performance tuning

I’ve been writing about how today’s standard computing abstractions are poor fits for helping humans or AI coding tools understand and improve the performance of programs. The potential for automated software engineering may be difficult to realize, if we don’t provide better languages for automated systems to “think in.” So far I covered software (low-level programming languages) and hardware (CPUs) separately. Now I want to turn to a synthesis that suggests a productive way forward.

Many programs aren’t subjected to direct performance optimization. Either they are needed for contexts where performance isn’t critical, or they are fed into automated systems that do the optimization, whether those be conventional compilers or AI coding tools. However, as in the last two posts, my focus here is on languages that we use to express the process of optimizing a program’s performance. Whatever tricks we want to apply for improving speed or memory usage, they need to be expressible as transformations in the chosen language. It needs to be tractable enough to predict a program’s performance from its source code. When we realize a given program has left performance on the table, we hope that the methods to improve performance can be expressed in the language.

The claim I want to make is that languages for hosting such optimization need to be explicitly spatial, representing something closer to hardware circuits than to the software programs we are used to. The last two articles emphasized how such a spatial model is fundamentally what physics gives us to work with, and performance depends critically on communication costs between nodes arranged in space. While we have tried hard to work with software notations that hide the spatial nature and hardware that scurries around understanding software well enough to make good spatial decisions, splitting the optimization problem between these two layers makes it too hard to solve well.

Another slogan I like to use for this message is assembly language is over. That is, going forward, we need to swap out the class of lowest-level software programming languages. It has the two main weaknesses I emphasized about low-level programming languages in general: sequentialized code and global shared memory. It’s a fine abstraction when we don’t want to get serious about performance optimization, but it’s totally unsuitable when we do, leaving us searching for a replacement or several of them that deserve similarly central places in computing stacks.

If we accept this principle, then the inevitable result is that performance-tuned software and performance-tuned hardware will converge, in terms of the kinds of abstractions used to describe them. In my own experience working with computer-science students, it’s very common for those who have focused on software to declare that they “aren’t hardware people” and don’t want to work on hardware projects; I’m sure the opposite pattern is common in the world, too. It’s my view that these two disciplines will need largely to merge, and let me sketch, coming at it from the two directions, first how software can become more like hardware and then vice versa.

How Software Should Become More Like Hardware (Getting Spatial)

Physical reality is pieces of computation and storage scattered through space, communicating with each other at cost proportional to distance. To support productive optimization of software, we need languages that expose enough of the physical reality, at a minimum with explicit communication and a good way of estimating its cost. A commonality we will see is switching from having hardware make spatial decisions at runtime, toward having compilers make spatial decisions in advance. We can afford to have automation “think harder” about spatial decisions when they are made before execution and then reused for many runs (though also some challenges of understanding execution grow, when we can’t simply observe actual values flowing through a system).

There is a long history of trying to boost performance by moving work from hardware to compilers. Very long instruction word (VLIW) systems are an example first developed in the 1980s, where a low-level software program specifies not just a sequence of basic instructions but instead a sequence of groups of instructions that should run simultaneously. It becomes an important part of the compiler’s job to understand instructions well enough to put them in parallel groups. A particularly infamous initiative in this direction was the Itanium architecture family, which Intel was predicting would supersede their conventional CPU designs for server workloads. Instead, the effort failed in the market, and the failure is often blamed on the difficulty of writing effective compilers. However, note that these efforts have generally assumed that software programming languages look just as we’re used to, retaining the weaknesses that I complained about recently, and my personal bet is that such obstacles can be overcome by making more sweeping changes across the whole stack of software and hardware. So much is changing with adoption of AI in software engineering that it’s a great time to imagine other changes, too.

So let me sketch some potential approaches. Ironically for the part of this article labeled as being about software, we’ll mostly be looking at hardware architectures. The point will be what software programming model each one exposes, as the lowest level of software coding for its stack. We will focus on how such software formats allow programmers to work hard enough to make the optimization choices that best exploit what is physically possible, rather than being limited by somewhat-arbitrary program formats. In some sense, responsibility is passed to compilers, but I’ll have to save for later posts some ideas of how these compilers ought to work.

One common approach today, which already blurs the line between software and hardware, is field-programmable gate arrays (FPGAs). Basically, an FPGA has one circuit skeleton built into it – many computation nodes and many links between them. Programming an FPGA involves telling each node which logic gate to become (virtually speaking), using which of its links with other nodes. The nice thing about FPGAs is that they offer close to the optimal level of control over distribution of computation in (two-dimensional) space. One important downside is that they impose overheads over custom silicon, which isn’t surprising when we note that each node of an FPGA is programmed by filling in a literal truth table (though the FPGA term of art is “lookup table”), an exhaustive description of which output bits to generate for every set of possible input bits – which sounds kind of crazy to encode and execute directly. A widely cited study from 2006 establishes that using an FPGA instead of a custom chip usually slows down processing by a few times (referring to the wall-clock delay for the critical path), requires about 20 times as much physical area, and consumes about 10 times as much power. These particulars vary across designs, and the distribution has changed as FPGAs have evolved since 2006, but the quantitative orientation still seems about right. Such relatively modest costs may not be enough to deter usage in many important domains, but then the biggest issue is probably the complexity of programming FPGAs effectively, which we’ll get to in the second part of this article.

One way that FPGA overhead has improved, which is also highly relevant to hardware design in general, is through providing more special-purpose functional blocks. The general pattern is that specialization improves performance. The available programmable units need not have the full flexibility of Boolean truth tables, to provide a useful abstraction of reconfigurable circuits. Hardware dataflow architectures were developed starting in the 1970s, to work with software described explicitly in circuit-like form. However, these original systems didn’t have a spatial element to software programming. Compute nodes spread throughout the spatial area of a chip would dynamically choose circuit nodes to evaluate next, after noticing that their inputs had already been calculated. That dynamic scheduling mimicked the same two disadvantages that I described for the heroic efforts of CPUs (and indeed can be considered to have had direct influence on the modern development of out-of-order CPU execution).

Let’s consider one example of a hardware style that exposes more explicitly spatial programming. A line of 21st-century efforts has developed that kind of dataflow platform, hybridizing FPGAs and old-school dataflow machines. Like FPGAs, we have a grid of reconfigurable gates/nodes in a dataflow fabric. Like prior dataflow machines, the vocabulary of available operations is more similar to CPU instructions than truth tables. Each node is typically programmed with the equivalent of up to a handful of CPU instructions, allowing a silicon node implementation more like a mini-CPU than a sea of truth tables.

In this diagram, note how the CPU approach on the left (associated with the buzzword of a von Neumann architecture) involves physical circuitry that is program-independent, performing complex run-time analysis of a program, effectively building up and tearing down a sequence of spatial dataflow graphs. In contrast, in the coarse-grained reconfigurable array (CGRA) approach on the right, a program is mapped once into a configuration of each compute node in a grid. Then the computation can proceed without changing the role of each piece of silicon during execution.

Two main advantages (which we can imagine also applying to a variety of similar architectures) follow from the CGRA style.

1. We avoid the so-called von Neumann bottleneck, particularly the cost of continually fetching instructions from memory to reconfigure a silicon computation graph dynamically.

2. Probably more importantly, the lowest-level software format can talk directly about the two major factors that I derided low-level programming languages for not supporting. That is, computation can be laid out explicitly throughout space, with attention to the communication distances between nodes that talk to each other; and many memory operations can be performed on local memory nodes accessible only to their immediate neighbors, avoiding global memory with a hidden cache-coherence protocol and its complex performance model.

I found it fascinating to learn that this kind of architecture has been explored to optimize two very different classes of computing: high-performance servers and ultra-low-power embedded systems. High parallel performance motivated the design of the Plasticine academic prototype with an associated software compiler called Spatial, which led to the company SambaNova Systems. Later, targeting small embedded computers dependent on harnessing energy from their environments, for instance in space satellites, an academic prototype called Riptide was developed, which led to the Efficient Computer Company.

The design space is wide open, of the ideal languages to form the boundaries between hardware and software, and the class I’ve just sketched is just one example (though it’s one that I’ve become a fan of); we’ll cover a variety of ideas in later posts. Let me highlight already what I see as one major opportunity. Almost all full computing stacks of this kind maintain global shared memory, one of the two major performance misfeatures I highlighted in the last two posts. Much storage that would traditionally be maintained in shared memory is pushed off into elements of the programmable dataflow fabric. However, typically source code still uses shared memory explicitly, and those memory accesses are carried over into the generated code. As a result, we have the twin downsides of a complex model for software programmers and a hardware implementation with cache coherence that is very hard to scale to high parallelism. I argue that a major pending codesign challenge is creating programming languages and hardware models that allow full coordination across many parallel compute nodes without classic shared memory.

How Hardware Should Become More Like Software (Strengthening Modularity)

Whether we think of spatial programs as describing software or hardware, coding them up in the traditional hardware way leaves much to be desired. Hardware development is traditionally done in terms of register-transfer level (RTL) languages, which basically identify the key pieces of evolving state in a program (registers) and associate each one with a circuit that computes its new value based on prior values of registers. Such a program can be run repeatedly to evolve register values, one clock cycle at a time. This abstraction provides great control over what’s possible to implement with physical circuits, but it’s challenging to program correctly, accounting for a large fraction of the expense of developing new digital hardware.

One alternative that has become popular is high-level synthesis (HLS), which compiles programs in low-level programming languages into RTL. It suffers from the same challenges that plagued the Itanium project and its cousins, though it has been much more successful, probably because engineers who use it have been more willing to change their programming conventions to enable it. Other approaches to higher-level hardware programming include Chisel and a broader family of metaprogramming techniques it represents, where programs in various languages are written to generate RTL code. This style of tool offers weak modularity for metaprogrammed components, making it easy for a bug in the program that computes one module to cause trouble for a different module. I would argue that HLS is too hard to pull off because it doesn’t offer a spatial abstraction, while metaprogramming systems don’t help enough because they expose a spatial abstraction that is too low-level, lacking in both structure and guarantees.

An alternative abstraction that has greatly influenced my research is associated with the Bluespec hardware language developed at MIT starting around the year 2000.

The left pane of the diagram shows the standard RTL approach, where a complex spatial computation is one big circuit with all kinds of winding wire paths within it. The right pane, for the Bluespec style, exposes more of the modularity that software programmers are used to, for instance in object-oriented programming. The circuit is broken into modules, each with a well-defined purpose. Every module has private, encapsulated state, exposed to other modules only through explicit method calls.

In the more-modular style on the right, the modules can be handled separately in a variety of appealing dimensions.

1. Different teams can build different modules.

2. Each module can have its own formal specification, which need not mention anything about other modules.

3. Each module can be formally verified separately against its own local specification.

4. Yet there are streamlined principles for reasoning about what happens when separately verified modules are brought together into one system.

The other crucial ingredient is compiler technology that can turn such high-level descriptions into RTL automatically, reprising our theme of moving decisions about spatial arrangement to happen in advance. Through static analysis of a design, that style of compilation can understand possibilities to run different modules simultaneously and generate circuits to arbitrate the decisions, often coming very close to the performance of hand-written RTL, if not matching it (or exceeding it, in cases where engineers were confused by all the concurrency and missed optimization opportunities). Muddying the terminological waters is the hardware world’s convention of calling that process not compilation but synthesis, not to be confused with program synthesis (automatically writing software from specifications, a topic we’ll spend plenty of words on in later posts). This service of automatically interconnecting modules for performance is very different from what RTL tools can do with the lower-level notion of module that they have long supported, where module couplings are general wires rather than anything so high-level as method calls.

I’ve been involved in a series of projects developing Bluespec-inspired languages with strong connections to machine-checked proofs, including Kami, Kôika, and Fjfj. Some previous posts have used examples from formal-verification projects that have drawn on these frameworks, including for end-to-end integration verification across hardware and software and for proof that hardware systems don’t leak secrets through timing.

Again, the Bluespec style is just one example of raising the level of abstraction in hardware programming. I’ll explain it in more detail in later posts, and I also plan to cover some other abstractions that depart even further from industry practice.

Conclusion

There is always a tension in the design of abstractions for programming, whether by people or AI. I think of the programming process as a structured search through the space of possible programs, informed by a specification (formal or informal). On the one hand, making abstractions higher-level allows single steps in the search space to accomplish more-interesting changes, which accelerates search. It is also easier to apply formal verification to validate new variants against requirements. On the other hand, lower-level abstractions typically provide more control over performance. I’ve argued here that, first, those lower-level abstractions at the hardware-software boundary need to be more spatial to support continued performance scaling; and, second, that we needn’t accept industry’s standard hardware-description languages as our spatial-programming playground, with opportunities to raise the abstraction level while still maintaining good control of performance.

The next post will be the last in this series on abstractions for performance, covering where GPUs line up with these principles and where they diverge, especially when it comes to supporting efficient formal verification. Then we’ll change gears to discussing how higher-level engineering workflows should change with increased automation.