Машинная точность вычислений | Machine-Precision Numbers in computations

English text below

Сложные расчёты обычно эффективнее вести на многих отдельных процессорах, чем на одном. Разделение нагрузки между процессорами называется параллелизацией. Важно распределять задачи так, чтобы одни процессоры не простаивали, ожидая данных от других процессоров.

В одной из моделей мы видели абсолютно неадекватное поведение расчётов (сразу скажу, это весьма специфическая задача, а я, фактически, первый человек, который вообще пытается её решать в параллельных вычислениях). Сказать, что именно не так, было крайне сложно: на каждом отдельном маленьком шаге всё хорошо, а вот когда смотришь, что произошло за тысячи шагов, выясняется, что всё ушло куда-то совсем не туда.

Расчёты так распределялись между процессорами, что на часть из них приходилось в 2-4 раза больше нагрузки, чем на другие. Это полностью объяснимо физикой (то есть сложностью расчётов), но некорректно с точки зрения рационального использования компьютерного времени. Кроме того, из-за этого появлялись очевидные (хотя и несущественные) погрешности в решении. Ну и в принципе, с некоторых философских и интуивных позиций (возможно, на это повлиял когда-то читанный "Капитал" Карла Маркса) мне казалось сильно неправильным, что на разных процессорах находятся столь разные по сложности задачи.

Полгода назад я спросил начальника, имеет ли смысл перераспределить расчёты между процессорами. Он сказал, что точно нет, потому что математика и так правильная. Ну, у меня и без того хлопот хватало. А недели две назад "дело было вечером, делать было нечего", и я решил попробовать. Нашёл место распределения расчётов и убрал нарезку по одному из пространственных направлений.

Суть на пальцах: мы рассчитываем температуру у стены комнаты. Внизу находится батарея, наверху - окно. Оба - во всю стену. Раньше нарезка была по квадратам "верх-лево", "низ-лево", "низ-право", "верх-право". Я запретил разрезать эту стену по горизонтали (на холодные и горячие квадраты), так что получились вертикальные полосы (как обои), которые включили весь разброс температур.

Собрал программу. Запустил.

Ускорение в 200 раз (!). Проблемы пропали.

Вскрытие показало, что у нас использовался перепад значений одной из величин (теплопроводности) в 15-17 порядков. При точности 64-битных расчётов (которые ограничены, в том числе, и используемыми сторонними библиотеками математики) - 15-17 десятичных знаков. Хождение по лезвию бритвы.

Особенность старой нарезки сетки состояла в том, что на разные процессоры "уходили" пространственные области с сильно разными значениями этого параметра. Казалось бы, так даже лучше - везде будет хорошая точность.

Однако практика показала, что гладкость решения, то есть отсутствие "изломов" на поле значений температуры, куда как важнее "точности" решения в каждой из областей расчёта.

То есть все уравнения верны, а вот машинная точность вычислений оказалась ключевым фактором.

---

Usually it is more effective to perform complicated computations on multiple processors rather than on one, but powerful. Such splitting of computations is called parallelization. An important part of it is to divide the load uniformly between the cores.   

One pretty special setup of initial parameters resulted in very inadequate computational results (and I'm almost the first guy to solve it in parallel mode). The issue was that on each single computational step everything works fine. Only after thousands of steps one can actually realize that something went too far in a wrong direction.

Load was split between the cores in such a way that half of processors were doing 2-4 times less computations than other. That's comes directly from the physics (difficulty of calculations), but it is not a rational way to use computers. Also it resulted in some other (minor) issues in the quality of computations. All together, I was thinking it is deeply incorrect to split the load between cores in such a way (probably, my opinion is affected hardly by Marx's "Capital").

Half a year ago I asked my boss shall I change the load splitting between the cores to provide them with similar load. He said that since math equation are all correct, it isn't so necessary. Since I had a handful of things to do (probably, a Titan's one), I hadn't tried it. Only two weeks ago I had a couple of hours when I decided to try this. I found a place where computations are divided between cores, and removed grid division in one of spatial directions.

Nuts and bolts. We need to compute a temperature distribution along a wall. And there is a heater near the floor, and a window on the top, both are as long as the wall is.  The old splitting divided the wall to "up-left", "down-left", "down-right", "up-right". I prohibited to split the wall in horizontal direction (to cold and hot blocks), so that I obtained vertical "wallpaper" stripes, which included all the range of temperatures.

I compiled the code and ran it.

Acceleration by 200 times (!). And no more problems.

Transection revealed that we had one value (thermal conductivity) differing by 15-17 orders of magnitude. With 64-bit machinery variables (which is limited also by math libraries we use), we obtain 15-17 significant decimal digits. Pretty rough deal.

Old numerical grid splitting provided different cores with sufficiently different parts of the range for this quantity. From one point of view, it is even better, because allows to compute each subdomain with high precision.
In the real world, "kinks" at subdomain boundaries became much more important in terms of quality of the solution. So how smooth is the solution is more valuable, than its single-step precision.

So all the equations were correct, but machine precision is insufficient.