9 ms·

Math Breakthrough Speeds Supercomputer Simulations

106 points by EndXA 7y ago

marmaduke 7y ago
The article doesn't seem to say what achieved the speed up. If they take a larger time step, they've used a special feature of molecular dynamics or some other assumption to achieve that ('no free lunch' or some such)
- bonoboTP 7y ago
  It doesn't say anything concrete because its purpose isn't to inform the reader. This is a PR marketing press release by the university advertising their impact.
- garganzol 7y ago
  I presume that instead of calculating each and every "point" and "particle" in discreet form, they find the statistically correct result instead. Probably something similar to Vitter algorithm https://getkerf.wordpress.com/2016/03/30/the-best-algorithm-no-one-knows-about/ https://getkerf.wordpress.com/2016/03/30/the-best-algorithm-...
mjsaah 7y ago
anybody got a few sentence explanation of the new method? I worked in a lab that did MD in college, so I'm kinda curious.
- comicjk 7y ago
  They're adjusting the integration method (used to calculate positions given forces) to take into account the properties of the thermostat (used to maintain a roughly-constant temperature in the simulation). This allows bigger timesteps. In particular, they studied the Langevin thermostat, in which all the atoms are subject to small random forces that smooth out their average temperature. By adding a term to the integrator that includes the magnitude of the random forces, it is possible to widen the stability bounds of the integration. The caveat is that the proof is only for simple potential energy surfaces. They haven't given a lot of evidence, even empirically, that this works for the potential energy surfaces we really care about, like protein binding calculations. We already have many empirical tricks for increasing timesteps for these simulations, like freezing bond lengths for hydrogen. Any new method has to beat these empirical methods, not just beat a naive approach.
  - cwingrav 7y ago
    This is a great example of why someone else should write the high level description for somebody else's work. Without the baggage of what was hard, fun, easy, interesting (and the desire to sell/market), an outsider can focus on the importance and utility of a work. Thanks for the description.
  - l33tman 7y ago
    Yeah I've worked a lot with this and was also curious as the thermo distribution is just one part, you also have a lot of short range forces that explode if you increase the timestep by too much and I didn't see any tricks around that (except the usual like freezing the fastest degrees of freedom, completely removing hydrogens with virtual sites etc).
amelius 7y ago
> three or four times the performance Back in my time computer scientists were'nt typically impressed much by a constant reduction of compute complexity. Has this attitude changed somehow?
- mooman219 7y ago
  To some degree it breaks down when writing for the hardware. For example, using an accumulation buffer for vector graphic filling is O(n²), while traditional methods are O(n). However, the accumulation buffer saves an order of magnitude of time (even at large N's!) as it takes advantage of prefetching, cachelines, and branch prediction.
  - djmips 7y ago
    Do you have some references?
    - mooman219 7y ago
      Yes https://medium.com/@raphlinus/inside-the-fastest-font-renderer-in-the-world-75ae5270c445 https://medium.com/@raphlinus/inside-the-fastest-font-render...
- tehjoker 7y ago
  From a computer science perspective, a constant factor reduction isn't that interesting but it appears that what happened here is that the bottleneck part of the simulation can now be computed independent of time step (which is huge, algorithmicly speaking). When working on the cutting edge of computing science problems, constant factor reductions can matter a lot. It can mean the difference between being able to do an experiment or not. If an experiment costs $10,000 of computation and your budget is $5,000, finding a 2x improvement is the difference between night and day. That said, there are many situations where you need to do much better to make the impractical practical. However, problems are often chosen because they are just on the brink of tractibility, so the constant factor improvements matter more than you'd think especially in fields where the problems are chosen for e.g. biological interestingness vs computational interestingness.
boulos 7y ago
I only read the abstract from the most recent linked article [1], but it sounds like the results are statistically correct. For this field, that makes a lot of sense, rather than computing strictly “accurate” velocity/acceleration from finite differences (see [2] for the basics on this integration method / domain). Edit (to make my comment clearer): they came up with a method to calculate the velocities they need for solving these equations with a new closed-form solution that doesn’t depend on the timestep size. This lets the author combine the new calculation with previous work to take big steps, yet still converge. [1] https://www.tandfonline.com/doi/figure/10.1080/00268976.2019.1662506?scroll=top&needAccess=true https://www.tandfonline.com/doi/figure/10.1080/00268976.2019... which is actually also https://arxiv.org/abs/1909.04380 https://arxiv.org/abs/1909.04380 [2] https://en.m.wikipedia.org/wiki/Verlet_integration https://en.m.wikipedia.org/wiki/Verlet_integration
unnouinceput 7y ago
Nooo, please don't make your research for free. Do a patent first, then you can make it free for fellow researchers while heavily tax any commercial company using this. I am sick and tired to see research published for free to use by everybody only a few months later a micro-increment of said research is done by a big pharma company who of course now will patent it and boom, none will be able to freely build upon that because "hey, we're a big company and we want our mighty $$$ in our pockets". And when finally a new application of said simulation will hit the market will cost an arm and a leg - see current insulin prices for example.
- knolan 7y ago
  How can they patent if the researcher publishes the work? Any patent search would show this to be prior art.
  - deleted 7y ago
    [deleted]
  - unnouinceput 7y ago
    If the initial research is not patented and the big company makes a tiny research on top of it just to have a small innovation then they can patent the new research any way they want and in the process they will legally own the old research too. Just look at how the entire patent litigation is right now and is full of trolls that will patent anything they can think about and later will hit real work later.

106 points by EndXA 7y ago

The article doesn't seem to say what achieved the speed up. If they take a larger time step, they've used a special feature of molecular dynamics or some other assumption to achieve that ('no free lunch' or some such)

bonoboTP 7y ago
It doesn't say anything concrete because its purpose isn't to inform the reader. This is a PR marketing press release by the university advertising their impact.
garganzol 7y ago
I presume that instead of calculating each and every "point" and "particle" in discreet form, they find the statistically correct result instead. Probably something similar to Vitter algorithm https://getkerf.wordpress.com/2016/03/30/the-best-algorithm-no-one-knows-about/ https://getkerf.wordpress.com/2016/03/30/the-best-algorithm-...

mjsaah 7y ago

anybody got a few sentence explanation of the new method? I worked in a lab that did MD in college, so I'm kinda curious.

comicjk 7y ago
They're adjusting the integration method (used to calculate positions given forces) to take into account the properties of the thermostat (used to maintain a roughly-constant temperature in the simulation). This allows bigger timesteps. In particular, they studied the Langevin thermostat, in which all the atoms are subject to small random forces that smooth out their average temperature. By adding a term to the integrator that includes the magnitude of the random forces, it is possible to widen the stability bounds of the integration. The caveat is that the proof is only for simple potential energy surfaces. They haven't given a lot of evidence, even empirically, that this works for the potential energy surfaces we really care about, like protein binding calculations. We already have many empirical tricks for increasing timesteps for these simulations, like freezing bond lengths for hydrogen. Any new method has to beat these empirical methods, not just beat a naive approach.
- cwingrav 7y ago
  This is a great example of why someone else should write the high level description for somebody else's work. Without the baggage of what was hard, fun, easy, interesting (and the desire to sell/market), an outsider can focus on the importance and utility of a work. Thanks for the description.
- l33tman 7y ago
  Yeah I've worked a lot with this and was also curious as the thermo distribution is just one part, you also have a lot of short range forces that explode if you increase the timestep by too much and I didn't see any tricks around that (except the usual like freezing the fastest degrees of freedom, completely removing hydrogens with virtual sites etc).

amelius 7y ago

> three or four times the performance Back in my time computer scientists were'nt typically impressed much by a constant reduction of compute complexity. Has this attitude changed somehow?

mooman219 7y ago
To some degree it breaks down when writing for the hardware. For example, using an accumulation buffer for vector graphic filling is O(n²), while traditional methods are O(n). However, the accumulation buffer saves an order of magnitude of time (even at large N's!) as it takes advantage of prefetching, cachelines, and branch prediction.
- djmips 7y ago
  Do you have some references?
  - mooman219 7y ago
    Yes https://medium.com/@raphlinus/inside-the-fastest-font-renderer-in-the-world-75ae5270c445 https://medium.com/@raphlinus/inside-the-fastest-font-render...
tehjoker 7y ago
From a computer science perspective, a constant factor reduction isn't that interesting but it appears that what happened here is that the bottleneck part of the simulation can now be computed independent of time step (which is huge, algorithmicly speaking). When working on the cutting edge of computing science problems, constant factor reductions can matter a lot. It can mean the difference between being able to do an experiment or not. If an experiment costs $10,000 of computation and your budget is $5,000, finding a 2x improvement is the difference between night and day. That said, there are many situations where you need to do much better to make the impractical practical. However, problems are often chosen because they are just on the brink of tractibility, so the constant factor improvements matter more than you'd think especially in fields where the problems are chosen for e.g. biological interestingness vs computational interestingness.

boulos 7y ago

I only read the abstract from the most recent linked article [1], but it sounds like the results are statistically correct. For this field, that makes a lot of sense, rather than computing strictly “accurate” velocity/acceleration from finite differences (see [2] for the basics on this integration method / domain). Edit (to make my comment clearer): they came up with a method to calculate the velocities they need for solving these equations with a new closed-form solution that doesn’t depend on the timestep size. This lets the author combine the new calculation with previous work to take big steps, yet still converge. [1] https://www.tandfonline.com/doi/figure/10.1080/00268976.2019.1662506?scroll=top&needAccess=true https://www.tandfonline.com/doi/figure/10.1080/00268976.2019... which is actually also https://arxiv.org/abs/1909.04380 https://arxiv.org/abs/1909.04380 [2] https://en.m.wikipedia.org/wiki/Verlet_integration https://en.m.wikipedia.org/wiki/Verlet_integration

unnouinceput 7y ago

Nooo, please don't make your research for free. Do a patent first, then you can make it free for fellow researchers while heavily tax any commercial company using this. I am sick and tired to see research published for free to use by everybody only a few months later a micro-increment of said research is done by a big pharma company who of course now will patent it and boom, none will be able to freely build upon that because "hey, we're a big company and we want our mighty $$$ in our pockets". And when finally a new application of said simulation will hit the market will cost an arm and a leg - see current insulin prices for example.

knolan 7y ago
How can they patent if the researcher publishes the work? Any patent search would show this to be prior art.
- deleted 7y ago
  [deleted]
- unnouinceput 7y ago
  If the initial research is not patented and the big company makes a tiny research on top of it just to have a small innovation then they can patent the new research any way they want and in the process they will legally own the old research too. Just look at how the entire patent litigation is right now and is full of trolls that will patent anything they can think about and later will hit real work later.