Frankenstein's program, or abstracting domain knowledge
Why program from scratch when it's easier and faster to use existing parts?
Today I’m going to stitch together a couple different posts and see if something happens…
RELAXed Traversers win SSSP track at FCPC
Congratulations to RELAXed Traversers for a dominating win in Track 1 (SSSP) at last month’s Fastcode Programming Challenge (FCPC). The team’s overall edges-per-second score was almost triple that of the second-place team.
150.89M — RELAXed Traversers
52.56M — UMD PASTEL
38.65 — Dumbledore’sArmy
10.57M — LoneStar Graph UTA
The RELAXed Traversers team featured PhD students Marco D'Antonio from Queen’s University Belfast and Kåre von Geijer from Chalmers University of Technology. (Check out Kåre’s blog!)
A couple weeks after the competition, I spoke with Hans Vandierendonck, who mentored the students along with Thai Son Mai and Philippas Tsigas. Hans told me the backstory of their team:
It was really prompted by the RELAX doctoral network, which teaches 12 PhD students in 5 different institutions across Europe. Our network had been running for a few years when we decided it would be good to collaborate a bit closer—to bring the students together and to see what they could be doing together. We had a number of online meetings with students and supervisors to hash out a few ideas. This became really exciting when, suddenly, we saw the call for the FCPC, and the students said, “Can we do this?” And we said, “Yeah. Go!” And that was it.
As consolation to the other FCPC Track 1 teams, I pass along Hans’s comment that the SSSP challenge matched precisely with what the RELAXed Traversers were already doing. So you might say they had a head start! But still, the RELAXed Traversers worked hard to assemble their submission for the competition, as Hans explained:
The submission is basically a hybrid solution between two different schedulers, or two different solutions to SSSP. One of them is something Marco has been working on during his PhD, which is mostly good for low-diameter graphs. And we put that together with Kåre’s work on relaxed concurrent data structures, which was better for high-diameter graphs. So they brought their two programs together along with a decision rule that determines which is the best scheduler to use and how to configure it.
Creating new DSLs made easy with BuildIt
In other news, Saman Amarasinghe talked about BuildIt at this month’s Fastcode Seminar. BuildIt is a framework for rapidly developing high-performance Domain Specific Languages (DSLs) without knowing about compilers. To connect Saman’s talk with the top half of this post, you can recognize SSSP as a specific domain.
I liked how Saman explained the two top ingredients of a DSL:
An algorithm language, which describes problem instances at a high level
A scheduling language, which describes how to map problems to machine architecture.
As shown below, target machine architectures are downstream from the algorithm and scheduling languages, and in the middle of it all is domain knowledge.
Saman motivated BuildIt by observing how much work is required by the traditional approach to building a DSL, diagrammed above. As he put it, “Each DSL requires sacrificing one PhD student.” This level of sacrifice is especially frustrating when a relevant domain-specific library already exists. You’d think it would be much easier to build a DSL from an existing library, but that isn’t the case — or it wasn’t the case, until BuildIt!
Saman’s overarching theme was how BuildIt makes it easy for a domain expert with an existing domain-specific library to build a DSL. In essence, the aim is to abstract the expert’s domain knowledge out of the compiler weeds, so that the domain knowledge resides top-level with the algorithm and scheduling languages. Saman described several different DSLs and libraries “built with BuildIt,” and I was impressed by how much smaller a high-performing program can be with the BuildIt approach. In one case, a master’s student built a regex library with 1,562 lines of code, and it competes effectively against state-of-the-art “programmed from scratch” systems with 100,000+ lines of code. This is even more impressive when you know that BuiltIt itself is under 10,000 lines of code.
Along the way, Saman asked, “What is domain knowledge?” As he illustrated with a few examples, I was reminded of the FCPC talks at PPoPP25. Domain knowledge is (for example) how you know that low-diameter instances of SSSP need one algorithm (like Marco’s), and high-diameter instances need another (like Kåre’s); and it’s how you configure a boundary between the low- and high-diameter algorithms.
You can see the recording of Saman’s talk here.
Closing thoughts
Combining the above two posts, I wonder what would happen if we invited people to use BuildIt to compete against the programs submitted to FCPC? How much can the fastest programs be simplified without sacrificing performance? This question interests me because it reminds me of another recent conversation I had with Yihan Sun and Nelson Amaral — about the co-evolution of algorithms and compilers. Essentially, the observation is that software innovations start as bespoke algorithms, but later may be standardized and incorporated into the optimizing powers of compilers. This sets up the co-evolution, because programmers need to work with (not against) their compilers. I will return to this topic another time.