💾 Archived View for rosenzweig.io › gemlog › 2020-11-09-gemini-day-10.gmi captured on 2022-04-29 at 11:19:28. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
Heavens, I despise change. It isn't that I am not happy to finally have time to design a scheduler for the Bifrost compiler, a formidable task given the juxtaposition of unusual constraints and obscure performance characteristics layered onto a problem that is ordinarily NP-complete whose heuristics are an open research question. I am. I am just also extraordinarily tired from the abrupt shift in routine from writing LaTeX while studying mathematics to writing LaTeX while authoring a compiler.
In these turbulent times, the utility of LaTeX is a constant.
Bifrost is an "interesting" architecture to schedule for. Like other modern GPUs and unlike its predecessor (Midgard), it requires the compiler to construct an explicit scoreboard for scheduling high-latency instructions like memory accesses. This simplifies the hardware the expense of complicating the compiler. Unfortunately, it straps this scoreboarding mechanism to a vestigial "Slightly" Long Instruction Word model, a play off the Very Long Instruction Word (VLIW) model common with digital signal processors and used with Midgard, also designed to push scheduling complexity away from the hardware and into the compiler.. The interaction of these two mechanisms is mediated by a dizzying set of irregular encodings with seemingly arbitrary corner cases, requiring an all-in-one scheduler keeping track of multiple pages of constraints in order to merely produce a program that is _correct_, let alone optimal.
It's a fun challenge to think through, and I am making slow progress dividing into a sequence of sub-problems, many of which have off-the-shelf solutions. I've resorted to constructing a mathematical model of the architecture in the spirit of formal methods in the hopes of proving correctness of the final algorithm before burning weeks implementing it. I recall the pains implementing the Midgard scheduler in its current incarnation a bit more than a year ago, and that was for a significantly simpler problem domain. (Midgard still has a lot more scheduling quirks than any reasonable architecture should, but by Bifrost standards it is at least _regular_.) I don't really know any proof assistant languages (like Coq) nor modeling languages (like TLA+), although I've flirted with the documentation of each. I suspect the types of bugs I'll be facing will be uncovered by rigorous handwritten proof and some manual scripts to model check, but we'll see. I like proofs, what can I say?
When I do get around to implementing, I'm planning to prototype in Rust, since I suspect it'll have faster iteration time, and I'm not so secretly hoping to oxidize the Bifrost compiler in the long-term anyway. I realize integrating Rust in-tree for common code is a nonstarter for the near future due to portability concerns, but for a backend compiler that only needs to work on Arm CPUs, it should be tractable. Concerns around foreign function interfaces are also minimized since the backend compilers are very much "leaf nodes" for the tree with minimal API surface area.
On the other hand, if I am the one to check Rust code in-tree, Drew will never let me live it down ;-)
If needed, translating the working Rust code to working C will be easier than the other way around, given the conservative subset of Rust I gravitate towards anyway.
Anyway. Uh, the web sucks, yay Gemini, boo distractions, text consoles are cool. Sorry, I'm still remembering how to do this whole new routine thing. I hope I'll have more energy for a proper gemlog tomorrow, but for now, tata.