DNS: Prototype for how to implement inherited FP accuracy tests #1402

zoddicus · 2022-05-12T19:19:36Z

I have re-expressed our fundamental accuracies, i.e. correctly
rounded, absolute, and ULP, in terms of intervals. Then built up a
framework to express other functions' accuracies in terms of these
building blocks.

This allows for composition of various blocks to express complex
accuracies like inherited accuracies.

I have shown how cos, sin, and / tests can be rewritten using
this framework, and implemented tan tests which our current
framework does not support.

As is, all of the cases I have implemented are monotonic. I believe
this framework can be extended to support non-monotonic functions via
custom impl/range implementations in a straightforward manner.

There is a bunch of duplicated patterns that I could refactor, and the
specific usage of inheritance can be revisited in a productionized
version of this.

A production version of this would probably involve a significant revamp
of the existing test runner/comparator code, since this supplants a lot
of the functionality in there and I just kinda bodge them together.

This does not handle accepting both rounding modes for quantization, I
have just forced quantization before sending it off, but our current
implementation doesn't actually handle this consistently either
as-is. I think adding this handling into my prototype would be easier,
since it would just be expanding out how normal vs subnormal is
handled.

I have re-expressed our fundamental accuracies, i.e. correctly rounded, absolute, and ULP, in terms of intervals. Then built up a framework to express other functions' accuracies in terms of these building blocks. This allows for composition of various blocks to express complex accuracies like inherited accuracies. I have shown how cos, sin, and / can be rewritten using this framework, and implemented tan which our current framework does not support. As is, all of the cases I have implemented are montonic, I believe this framework can be extended to support non-monotic functions via custome impl/range implementations in a straight forward manner. There is a bunch of duplicated patterns that I could refactor, and the specific usage of inheritence can be revisited ina productionized version of this. A production version of this would probably involve a signicant revamp of the existing test runner/compartor code, since this supplants a lot of the functionality in there and I just kinda bodge them together. This does not handle accepting both rounding modes for quantization, I have just forced quantization before sending it off, but our current implementation doesn't actually handle this consistently either as-is. I think adding this handling into my prototype would be easier, since it would just be expanding out how normal vs subnormal is handled.

src/webgpu/util/fp_interval.ts

dneto0

I think this hangs together really well. It's a nice framing of the problem: separating concerns and making good abstractions.

I was slowed down by lack of comments but I think I pieced it together.

I'm confused by the Abs builder's impl implementation.... Seems wrong. I think the others look good/ reasonable.

@ben-clayton should comment on how this replaces existing float comparator infra. I'm less familiar (i think it's evolved a lot).

src/webgpu/util/fp_interval.ts

dneto0 · 2022-05-13T15:40:18Z

src/webgpu/util/fp_interval.ts

+  private readonly builder;
+
+  public constructor() {
+    this.builder = new ULPFPIntervalBuilder(2.5);


It's a detail, but the ULP only applies in a certain range. (I think it's the range of normal values?)

The WGSL definition of ulp I don't think restricts to normal values. It just says floating point numbers.

src/webgpu/util/compare.ts

zoddicus

Thank for the comments @dneto0
Given that overall approach appears to be sound, I will start working on a more formal design doc.

src/webgpu/util/fp_interval.ts

zoddicus · 2022-05-16T13:58:10Z

src/webgpu/util/fp_interval.ts

+  private readonly builder;
+
+  public constructor() {
+    this.builder = new ULPFPIntervalBuilder(2.5);


The WGSL definition of ulp I don't think restricts to normal values. It just says floating point numbers.

src/webgpu/util/fp_interval.ts

- Renamed FPInterval to F32Interval - Integrated functional changes from Ben - Implemented handling of undefined accuracy per discussion with David - Added a bit of documentation

zoddicus · 2022-05-17T21:17:48Z

I have done a major rewrite of this, integrating in Ben's change to functional coding as well as other things that we discussed like handling inputs where accuracy isn't defined. PTAL

src/webgpu/shader/execution/expression/binary/f32_arithmetic.spec.ts

ben-clayton

Design is looking much nicer! Thank you for the changes!

src/webgpu/util/compare.ts

src/webgpu/util/f32_interval.ts

github-actions · 2022-05-25T17:43:39Z

Previews, as seen when this build job started (3843173):
Run tests | View tsdoc

zoddicus · 2022-05-25T18:00:22Z

PTAL, I have done a major update of this prototype, porting over all of the existing FP tests to use the interval mechanism and refactoring/reorganizing the code.

I am going to start working on converting the test runner/float match code to be orientated around intervals, so we can get rid of the 'cute' interval comparator hacks. That I expect to be the last update for this prototype, other than maybe responses to review comments.

For actually productionizing/landing this giant blob, I plan to break this up into a series of PRs and have them review separately. Specifically I am expecting to first land a patch with the core framework code + unit tests. Then a series of patches that convert tests and add unittests to the helpers, then finally a patch that removes the old framework code and replaces it with the interval-specific code. Then I can work on adding new tests.

github-actions · 2022-05-25T19:01:41Z

Previews, as seen when this build job started (b631343):
Run tests | View tsdoc

This removes a bunch of dead code/logic related to floating point tests that is not needed when using intervals.

zoddicus · 2022-05-26T19:04:23Z

I removed FloatMatch and related complexity, still need to still promote intervals as a direct expectation, so that the IntervalComparator can be removed.

dneto0

I looked in detail at f32_interval.ts, compare.ts, and spot checked a bunch of other things.

Overall this looks very good to me.

+1

src/webgpu/util/fp_interval.ts

src/webgpu/util/f32_interval.ts

dneto0 · 2022-05-26T19:00:52Z

src/webgpu/util/f32_interval.ts

+}
+
+/** Convert a point to an interval of absolute error around the point */
+export function absoluteErrorInterval(n: number, rng: number): F32Interval {


nit: Please explain the 'rng'. I don't understand the mnemonic.
It's the absolute error.

Will do when productionizing

dneto0 · 2022-05-26T19:03:30Z

src/webgpu/util/f32_interval.ts

+}
+
+/** For a point operation run its impl over the input that may be an interval */
+function runPointImpl(x: F32Interval, impl: PointToInterval): F32Interval {


It's worth noting that using this function on an interval only makes sense when the impl function is monotonic over the input interval.

Will do when productionizing

github-actions · 2022-05-26T19:11:37Z

Previews, as seen when this build job started (8e367da):
Run tests | View tsdoc

This allows for specifying test cases using a bare interval instead of having to wrap it with a comparator. This also reduces the number of comparators implemented to just anyOf and implicit ones used for packing test cases.

zoddicus · 2022-05-26T20:36:44Z

PTA(final)L, I have moved intervals up to being a type of expectation, so that they don't need to be wrapped in a comparator.

This I think is more or less the final form that I expect the production version of this to look like before I start adding in new tests and handling of non-monotonic functions.

I am going to start breaking this up into reviewable/landable PRs, unless there is any significant objections.

github-actions · 2022-05-26T20:39:31Z

Previews, as seen when this build job started (298f3c4):
Run tests | View tsdoc

ben-clayton

Done a few skims over this, and I like it. Good job!
One question about quantizing.

ben-clayton · 2022-05-30T15:06:26Z

src/webgpu/shader/execution/expression/call/builtin/ceil.spec.ts

-
    const makeCase = (x: number): Case => {
-      return makeUnaryF32Case(x, Math.ceil);
+      return makeUnaryF32IntervalCase(x, ceilInterval);


Do we need to quantize to f32 here?

No, makeUnaryF32IntervalCase is responsible for quantizing to f32. I moved the quantization to the builders, since it needs to be done for every case for all of the test types, and made it explicit in the framework where/how the conversion is done.
This is also done right before calculating the acceptance interval, so we get rid of situations where we were actually calculating the interval for the non-quanitized input, which implementation will never actually see and getting subtle bugs.

Adds in machinary for specifying where extrema occur for non-monotonic functions. This is achieved via seperating the API that is called by tests and the implementation to allow for an additional optional extrema function to be defined. This allows moving the atan2 complexity related to multiple return values @ y = 0 from the test into the framework implementation, which will help when using atan2 to declare other tests. I also cleaned up a bunch of little naming things that my IDE was bugging me about.

zoddicus · 2022-05-30T21:00:28Z

Added one last change that adds support for non-monotonic functions

github-actions · 2022-05-30T21:06:56Z

Previews, as seen when this build job started (2e732de):
Run tests | View tsdoc

src/webgpu/util/f32_interval.ts

dneto0 · 2022-05-30T21:21:43Z

src/webgpu/util/f32_interval.ts

-function runBinaryImpl(x: F32Interval, y: F32Interval, impl: BinaryToInterval): F32Interval {
+function runBinaryOp(x: F32Interval, y: F32Interval, op: BinaryToIntervalOp): F32Interval {
+  if (op.extrema !== undefined) {
+    [x, y] = op.extrema(x, y);


I guess I'm confused. For atan2, when the passed-in y interval contains 0, the resulting y interval is just [0,0].
I'm not sure how that percolates through the rest of the calculation. Do we get the span over undefined values?

{[0,0], x} will be passed into atan2, which will hit the special case for y === 0, which will create a span of {4096 * ulp(π), 4096 * ulp(0), 4096 * ulp(π)} (The zero term could be dropped since the other terms are on either side)

So the acceptance interval will be [-π, π].

Honestly atan2 is a hot mess of a trig function.

Taking a look at what Vulkan does. It looks like they are differentiating between the different quadrants based on the signs of y & x, and considering [0, 0] as undefined.

I think I need to rewrite this a bit given what Vulkan is doing and looking at the definition of atan2, I will put up another patch with corrected calculations that we can discuss in detail.

I think I have this cleaned up now. I have ended up implementing:
y != 0 && x != 0 -> 4096 * ulp(Math.atan2(y, x))
y == 0 && x == 0 -> Infinite (undefined)
y == 0 && x != 0 -> [-π, π]

I think in theory we should be able to use x > 0 vs x < 0 to distinguish between positive/negative π cases, but everytime I try that either SwiftShader or Nvidia will start failing tests due to having the other sign for some x values.

github-actions · 2022-05-31T16:51:57Z

Previews, as seen when this build job started (05cde31):
Run tests | View tsdoc

This implements the F32Interval class and fundamental accuracy functions described in my prototype for reworking, gpuweb#1402, how floating point tests are written. This also adds in testing that did not appear in my prototype. There are a couple of functions that are not currently used that I have included in this patch that have suppressions for unused-vars on them. I included them in this patch since they are logically grouped with this code. These supressions will be removed in future patches. Issue gpuweb#792

This implements the F32Interval class and fundamental accuracy functions described in my prototype, #1402, for reworking how floating point tests are written. This also adds in testing that did not appear in my prototype. There are a couple of functions that are not currently used that I have included in this patch that have suppressions for unused-vars on them. I included them in this patch since they are logically grouped with this code. These surpressions will be removed in future patches. Review discovered a bug in oneULP's implementation, which is fixed in this PR. Issue #792

zoddicus · 2022-07-18T19:18:57Z

This has been fully implemented in main, so no longer needed for reference.

zoddicus requested review from ben-clayton, dj2 and dneto0 May 12, 2022 19:19

oops, didn't mean to delete those

91aa72d

zoddicus commented May 12, 2022

View reviewed changes

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

zoddicus commented May 12, 2022

View reviewed changes

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

zoddicus commented May 12, 2022

View reviewed changes

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

zoddicus commented May 12, 2022

View reviewed changes

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

zoddicus commented May 12, 2022

View reviewed changes

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

dneto0 reviewed May 13, 2022

View reviewed changes

zoddicus commented May 16, 2022

View reviewed changes

dneto0 marked this pull request as draft May 16, 2022 14:08

Restrict tan tests to input range of defined accuracy

a08ece9

ben-clayton reviewed May 16, 2022

View reviewed changes

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

src/webgpu/util/fp_interval.ts Outdated Show resolved Hide resolved

Bunch of work to make this more like production code

4ed2acd

- Renamed FPInterval to F32Interval - Integrated functional changes from Ben - Implemented handling of undefined accuracy per discussion with David - Added a bit of documentation

zoddicus requested review from ben-clayton and dneto0 May 17, 2022 21:16

zoddicus commented May 17, 2022

View reviewed changes

src/webgpu/shader/execution/expression/binary/f32_arithmetic.spec.ts Outdated Show resolved Hide resolved

Merge branch 'gpuweb:main' into newIntervalPrototype

b3c947a

ben-clayton reviewed May 19, 2022

View reviewed changes

src/webgpu/util/compare.ts Outdated Show resolved Hide resolved

src/webgpu/util/f32_interval.ts Outdated Show resolved Hide resolved

Replacing existing tests with new interval based ones

3843173

zoddicus marked this pull request as ready for review May 25, 2022 18:00

zoddicus requested a review from ben-clayton May 25, 2022 18:00

Convert missed inverseSqrt tests

b631343

Excise FloatMatch and reduce Compartor usage to AnyOf & Interval

8e367da

This removes a bunch of dead code/logic related to floating point tests that is not needed when using intervals.

dneto0 reviewed May 26, 2022

View reviewed changes

Promote intervals to expectation type

298f3c4

This allows for specifying test cases using a bare interval instead of having to wrap it with a comparator. This also reduces the number of comparators implemented to just anyOf and implicit ones used for packing test cases.

ben-clayton reviewed May 30, 2022

View reviewed changes

zoddicus requested review from ben-clayton and dneto0 May 30, 2022 20:59

dneto0 reviewed May 30, 2022

View reviewed changes

Update comments and cleanup atan2 impl

05cde31

zoddicus mentioned this pull request Jun 1, 2022

Implement new F32Interval class for floating point tests #1500

Merged

7 tasks

zoddicus closed this Jul 18, 2022

zoddicus deleted the newIntervalPrototype branch July 27, 2022 03:09

DNS: Prototype for how to implement inherited FP accuracy tests #1402

DNS: Prototype for how to implement inherited FP accuracy tests #1402

Uh oh!

Conversation

zoddicus commented May 12, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

dneto0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

zoddicus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

zoddicus commented May 17, 2022

Uh oh!

Uh oh!

ben-clayton left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

github-actions bot commented May 25, 2022

Uh oh!

zoddicus commented May 25, 2022

Uh oh!

github-actions bot commented May 25, 2022

Uh oh!

zoddicus commented May 26, 2022

Uh oh!

dneto0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented May 26, 2022

Uh oh!

zoddicus commented May 26, 2022

Uh oh!

github-actions bot commented May 26, 2022

Uh oh!

ben-clayton left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!