3 ms·
You can't have an executable test if your objective is to get from not having an executable platform to having an executable platform. The best you can do is a
by kragen 4y ago
You can't have an executable test if your objective is to get from not having an executable platform to having an executable platform. The best you can do is a set of (cart, expected output) pairs; the CBV UM published three carts — http://www.boundvariable.org/sandmark.umz http://www.boundvariable.org/sandmark.umz, http://www.boundvariable.org/codex.umz http://www.boundvariable.org/codex.umz, and http://www.boundvariable.org/um.um http://www.boundvariable.org/um.um — and the expected output for one of them, http://www.boundvariable.org/sandmark-output.txt http://www.boundvariable.org/sandmark-output.txt. They also had an online test oracle, in the form of their scoring server, but that didn't become relevant until after you already had the UM running well enough to run the Codex, or most of it.
However, the third cart was a metacircular interpreter, so in some sense it potentially represents a kind of reference implementation — just, one you couldn't use until your UM was running well enough to run it.
This may not be the perfect strategy but it worked well enough for 365 teams to submit a proof witness for at least one of the challenges in the Codex. And, importantly, it isn't very dependent on the hardware you're implementing the machine on, and in particular it doesn't require you to be able to run an external test suite.
— ⁂ —
You may be right about 128-bit Wasm SIMD.
When you say, "thread counts for single socket systems are already at 256", do you mean you need 256 threads to hit 100% utilization of the AVX units? Or are you talking about a chip with 64 or 128 cores with 2-way or 4-way "hyperthreading"? On https://www.tomshardware.com/reviews/cpu-hierarchy,4312.html#section-multi-threaded-cpu-benchmarks-rankings-2022 https://www.tomshardware.com/reviews/cpu-hierarchy,4312.html... the highest number I see is 64 cores with 128 threads on the AMD Threadripper 3990X. Are you talking about the Tera MTA or Tilera or Altra or Parallela or something?
I'm not sure if mere vector operations scripted by a single control thread (SIMD, but in a broader sense than SIMD intrinsics, including things like RVV) can approach the level of parallelism needed.
Suppose you have 64 cores with 256-bit AVX2, like the 2.9GHz Threadripper 3990X, which Donald Kinghorn benchmarked at 1.57 teraflops on HPLinpack, and (optimistically) you're doing double-precision floating-point. In theory each core can do up to 4 flops per cycle (right?) and thus 740 gigaflops; perhaps he's counting FMA as two flops instead of one, because on the Cray-1 it would have been two flops. Without any parallelism, the max you get is 2.9 Gflops (or 5.8 if you count FMA as two), and if you have an additional 40× slowdown from naïve bytecode interpretation like CPython you get 73 megaflops, 0.01% or 0.005% of theoretical. This is maybe comparable to a Pentium MMX, Pentium Pro, or Pentium II; according to Greer and Henry's SC97 "Micro-Ops to TeraFLOPS" technical paper, matrix blocking boosted ASCI Option Red's Linpack scores from about 10 megaflops per 300 MHz Pentium Pro to about 160 megaflops per.
(This is perfectly adequate for Quake III, but maybe not at 60 fps.)
For our naïve interpreter to hit the 1.6% of maximum performance, 11.6 gigaflops, that you could get from single-threaded AVX assembly on that chip, you need an average vector length of 158 (11.6 ÷ .073). For it to approach 100% of maximum performance we need an average vector length of 10100 (740 ÷ .073). I am not convinced that you can reliably get such large vector lengths in most pixel pushing.
Even with a naïve JIT compiler with, say, 4 clock cycles per bytecode instruction, you need an average vector length of 1010 (≈1024) to get close to maximum performance, or 256 to be only two Moore generations behind (≈02018, or maybe ≈02016 given that the 3990X came out in 02020).
And the situation is 8× worse if you're alpha-compositing pixels or something; an AVX256 register holds 32 8-bit color components rather than just 4.
I think that usually you will need both SIMD and more flexible forms of parallelism to extract that much parallelism.
— ⁂ —
Why does this matter for reproducible software? Because if the forever-platform imposes a 10100× or a 1024× slowdown then we'll only use it when we really have to, and most of our software will fail to be reproducible, and we'll be back to directories full of screenshots of things we can no longer do.
— ⁂ —
Yes, 4% difference is three weeks of Moore's Law. But perhaps Moore's Law has already ended?
To, "no amount of concrete performance gains will allow them to have safety or correctness," I would add, "or durability". Modern software is not just a ghetto but a shantytown slum built from cardboard: it collapses after a few good rains.
- sitkack 4y agoYou need a high level relational projection system that can operate on multiple dimensions simultaneously, shaders or SQL are ideal for taking advantage of parallelism. Esp if you can operate symbolically, think triple nested loops where the inner loop is some expensive projection, if it is over a regular space, and can be decomposed as a tree. I think this language could be represented as a Wasm DAG of functions, map/pmap/apply/tree_call/reduce Having a spec and a body of software to run but no test oracles for how that software runs feels contrived. If you have megabytes or gigabytes of code but not even screenshots of how it should it should look when it runs isn't the same as having a book in a dead language and not knowing what it should sound like. > However, the third cart was a metacircular interpreter, so in some sense it potentially represents a kind of reference implementation — just, one you couldn't use until your UM was running well enough to run it. This is a great example of a test oracle. Fixed-point correctness.
- kragen 4y agoHmm, I understand a "test oracle" to be a thing where, if you submit any arbitrary input to it, it will tell you what the correct output should be. The metacircular interpreter isn't such a thing: you can submit an input to it, and if its output is different from the output of the implementation it's running on, you know that implementation has a bug. Say my implementation is P and the metacircular interpreter (presumed correct) is M. If P[M[X]] outputs "foo", while P[X] outputs "bar", we know there is a bug in I. This is similar to a test oracle in some ways: given a test oracle O, if O[X] outputs "foo" and P[X] outputs "bar", we know I has a bug. The difference is that in the metacircular case, the correct output might actually be "foo". Worse, if P[M[Y]] outputs "baz" and P[Y] also outputs "baz", it does not therefore follow that "baz" is the correct output, as it would if O[Y] outputs "baz". It might just be that P has a bug that flows through to the metacircular interpreter. Maybe it rounds division the wrong way, or incorrectly considers negative zero to be unequal to positive zero. I agree that screenshots would be very useful, but a static repository of screenshots is also not a test oracle, for a slightly different reason: you cannot submit a novel input to it and find out what the correct screenshot would be. I agree that a DAG of functions is a useful representation that preserves significant degrees of parallelism that conventional machine-code representations expunge. However, Wasm also expunges them. The idea of using a relational rather than functional or imperative computing paradigm for archival is interesting. We should probably discuss this in a more amenable format.