4 ms·

Are there researchers interested in accelerating these algorithms while also keeping the maximum accuracy of the results ? This and others optimizations are tra

Are there researchers interested in accelerating these algorithms while also keeping the maximum accuracy of the results ? This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Also using FMA fused multiply add operations would be beneficial.

constantcrying 1y ago
The question of stability of the algorithm is interesting, the paper does not seem to discuss it though. You are correct that we should expect the algorithms to deliver different results. >This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Certainly not true. In general different orders of magnitude are a problem. With multiplication and division these are more serve problems, as they lead to greater changes in magnitude, although even that is a generalization.
- wizzwizz4 1y ago
  Different orders of magnitude aren't a problem when multiplying floats, because the order-of-magnitude portion gets translated into addition of exponents. They're a problem with fixed point: might you have been thinking of that?
  - Dylan16807 1y ago
    We're not looking at instructions in a vacuum. No matter what you have both multiplications and additions happening. So they're making a point that if you apply more multiplications before the inevitable addition, you are likely increasing the danger levels of that addition.
    - wizzwizz4 1y ago
      Oh, if one of the multiplications yields a positive number, and another yields a negative number of similar magnitude? That makes sense; I forgot linear spaces were over fields.
almostgotcaught 1y ago
> while also keeping the maximum accuracy of the results All of these papers/algos are for the ML hype-train. ML algos are approximate anyway so no one cares about absolute accuracy, only the precision of the overall pipeline (class labels shouldn't change, at least not too much). Consider that very many papers/techniques quantize down to 8 or even 4 bits (yes sometimes even during training) for the purposes of perf. This whole research area should just be renamed to something like approximate computing so that people don't confuse it (and the goals) with classical numerical analysis.
- saagarjha 1y ago
  Surely nobody is tiling 4x4 blocks for ML training
  - almostgotcaught 1y ago
    Why surely? Eg on GPU style chips today you'd tile to warpsize (or half or something like that) to target warp cooperative primitives (so called tensor cores). On AMD and NV that's like 16x16 or 32x32 depending on the data type. That's not that far from 4x4 and it's not like all chips in the world have 32-lane warps. Anyway if a trick is good enough and people start trying to shoehorn it into everything (not saying this one is) then the next gen (or the one after that or after) will just have units to support the trick (it's an expensive way to gain ground on mlperf rankings).
    - saagarjha 1y ago
      Blackwell is doing matrix multiplies across thread blocks these days, and doesn’t understand anything smaller than 64x16x16. I assume large matrix multiples are using the bigger sizes like 128x256x16 or whatever.
- ttoinou 1y ago
  I get your point, neural networks could be some kind of black boxes and how the sequence of operations evolves might not be so dependent on the accuracy of each operations -- at least, it would be a good intuition to believe "accuracy at each step matters" but it's not rigorously proven ? We could empirically check this by training a neural net and adding some random noise at each step
HappyPanacea 1y ago
Yes see this: https://arxiv.org/abs/1507.00687 https://arxiv.org/abs/1507.00687 . There is also this answer ( https://mathoverflow.net/a/421380 https://mathoverflow.net/a/421380 ) in MathOverflow which state that you can't do better than cubic time if you want strong form of numerical stability.
- ttoinou 1y ago
  Wow thank you I do not understand everything written and didn't take time to do so (and can't even find reference 23 paper on Brent stability), but I was thinking we don't necessarily need a new algorithm, we could tweak existing ones. For example swapping columns and rows before applying a product, so that accuracy is best kept (then reswapping back at the end of the operation). It seems to me the Strassen-like algorithm choose arbitrarily some elements of the matrices over others to make their temporary sum-products variables, so we could exploit this asymmetry (not sure if it's the correct word here) to choose which elements are to be chosen
  - HappyPanacea 1y ago
    This sounds like interesting topic to investigate which I don't remember seeing but I don't think this will gain much. I think asymmetry is completely fine in this context.
lanstin 1y ago
Additions are ok, it's subtraction when they might be close in value that is deadly.
- convolvatron 1y ago
  additions arent strictly ok. if the two addends arent close together in magnitude, then one of them is going to lose some bits
  - lanstin 1y ago
    The result won't be far off from the correct answer, however.
    - amelius 1y ago
      Consider (A+B)-A, where A>>B.
      - lanstin 1y ago
        That has a substraction where the 2 values are nearly equaly, which is the dangerous op as I said.

constantcrying 1y ago

The question of stability of the algorithm is interesting, the paper does not seem to discuss it though. You are correct that we should expect the algorithms to deliver different results. >This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Certainly not true. In general different orders of magnitude are a problem. With multiplication and division these are more serve problems, as they lead to greater changes in magnitude, although even that is a generalization.

wizzwizz4 1y ago
Different orders of magnitude aren't a problem when multiplying floats, because the order-of-magnitude portion gets translated into addition of exponents. They're a problem with fixed point: might you have been thinking of that?
- Dylan16807 1y ago
  We're not looking at instructions in a vacuum. No matter what you have both multiplications and additions happening. So they're making a point that if you apply more multiplications before the inevitable addition, you are likely increasing the danger levels of that addition.
  - wizzwizz4 1y ago
    Oh, if one of the multiplications yields a positive number, and another yields a negative number of similar magnitude? That makes sense; I forgot linear spaces were over fields.

almostgotcaught 1y ago

> while also keeping the maximum accuracy of the results All of these papers/algos are for the ML hype-train. ML algos are approximate anyway so no one cares about absolute accuracy, only the precision of the overall pipeline (class labels shouldn't change, at least not too much). Consider that very many papers/techniques quantize down to 8 or even 4 bits (yes sometimes even during training) for the purposes of perf. This whole research area should just be renamed to something like approximate computing so that people don't confuse it (and the goals) with classical numerical analysis.

saagarjha 1y ago
Surely nobody is tiling 4x4 blocks for ML training
- almostgotcaught 1y ago
  Why surely? Eg on GPU style chips today you'd tile to warpsize (or half or something like that) to target warp cooperative primitives (so called tensor cores). On AMD and NV that's like 16x16 or 32x32 depending on the data type. That's not that far from 4x4 and it's not like all chips in the world have 32-lane warps. Anyway if a trick is good enough and people start trying to shoehorn it into everything (not saying this one is) then the next gen (or the one after that or after) will just have units to support the trick (it's an expensive way to gain ground on mlperf rankings).
  - saagarjha 1y ago
    Blackwell is doing matrix multiplies across thread blocks these days, and doesn’t understand anything smaller than 64x16x16. I assume large matrix multiples are using the bigger sizes like 128x256x16 or whatever.
ttoinou 1y ago
I get your point, neural networks could be some kind of black boxes and how the sequence of operations evolves might not be so dependent on the accuracy of each operations -- at least, it would be a good intuition to believe "accuracy at each step matters" but it's not rigorously proven ? We could empirically check this by training a neural net and adding some random noise at each step

HappyPanacea 1y ago

Yes see this: https://arxiv.org/abs/1507.00687 https://arxiv.org/abs/1507.00687 . There is also this answer ( https://mathoverflow.net/a/421380 https://mathoverflow.net/a/421380 ) in MathOverflow which state that you can't do better than cubic time if you want strong form of numerical stability.

ttoinou 1y ago
Wow thank you I do not understand everything written and didn't take time to do so (and can't even find reference 23 paper on Brent stability), but I was thinking we don't necessarily need a new algorithm, we could tweak existing ones. For example swapping columns and rows before applying a product, so that accuracy is best kept (then reswapping back at the end of the operation). It seems to me the Strassen-like algorithm choose arbitrarily some elements of the matrices over others to make their temporary sum-products variables, so we could exploit this asymmetry (not sure if it's the correct word here) to choose which elements are to be chosen
- HappyPanacea 1y ago
  This sounds like interesting topic to investigate which I don't remember seeing but I don't think this will gain much. I think asymmetry is completely fine in this context.

lanstin 1y ago

Additions are ok, it's subtraction when they might be close in value that is deadly.

convolvatron 1y ago
additions arent strictly ok. if the two addends arent close together in magnitude, then one of them is going to lose some bits
- lanstin 1y ago
  The result won't be far off from the correct answer, however.
  - amelius 1y ago
    Consider (A+B)-A, where A>>B.
    - lanstin 1y ago
      That has a substraction where the 2 values are nearly equaly, which is the dangerous op as I said.