LRnLA

Материал из MediaWiki
Перейти к навигации Перейти к поиску

LRnLA (локально-рекурсивные нелокально-асинхронные) алгоритмы

разрабатываются В. Д. Левченко в ИПМ им. М. В. Келдыша с 1990-х годов.

LRnLA алгоритмы позволяют достигать почти 100%-й эффективности вычислений при численном моделировании задач с конечной скоростью распространения возмущений даже в тех случаях, когда размер задачи превышает размер ОЗУ, в том числе при распараллеливании на любом числе процессоров.

Здесь под эффективностью понимается степень загруженности процессора - отношение теоретически требуемого числа тактов для выполнения всех операций численной схемы к реально затраченному числу тактов. Из за особенностей работы подсистемы памяти современных компьютеров, для актуальных задач (размер которых приближается к размерам ОЗУ), эффективность традиционных подходов составляет не более нескольких процентов, поскольку подсиcтема памяти не успевает поставлять процессору данные для полноценной работы. Более развернуто об этом можно прочитать здесь http://a-iv.ru/LRnLA/capacity.pdf хотя Вадим Левченко с приведенным по ссылке текстом не согласен, считая его слишком упрощенным и во многом неправильным.

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

Основная идея LRnLA алгоритмов

Для моделирования D-мерной задачи Коши необходимо провести некоторое количество вычислений и перевести данные модели из начального состояния в нулевой момент времени, в конечное состояние в некоторый момент времени T в будущем (как правило речь идет о продвижении на достаточно большое число шагов). Промежуточные значения вычисляются, но не сбрасываются на диск и остаются в итоге неизвестными, сохраняются лишь конечные значения в момент T — для описания такой постановки задачи В. Д. Левченко ввел термин «модифицированная задача Коши». Сброс всех вычисленных (промежуточных) значений для задач актуального размера невозможен физически — ни по пропускной способности ни по размерам дисковой подсистемы.

Таким образом можно говорить об области в D+1 мерном пространстве операций, операции из области должны быть выполнены для перевода системы из нулевого момента времени в момент времени T. Традиционным решением является перевод системы с одного временного слоя на другой, то есть область разбивается на ряд «пластин» лежащих друг на друге (будем считать, что ось времени в пространстве операций направлена вверх). Такой подход не обеспечивает локальности данных, и при относительно небольшом числе операций на ячейку на шаг для больших задач приводит к существенному падению эффективности расчета (данные не успевают поступать в процессор). Существенно ухудшает ситуацию организация данных в традиционные многомерные массивы — для задач с D>1, ячейки расположенные рядом в пространстве находятся на большом удаление в памяти.

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

LRnLA алгоритмы постулируют разбиение пространства операций не на горизонтальные слои, а на пирамиды, наклон граней пирамид определяется скоростью распространения возмущений в решаемой задаче. Пример разбиения для одномерного случая можно увидеть на седьмом слайде вот этой http://grid2008.jinr.ru/pdf/vlevchenko.pdf презентации. Фактически, пирамиды являются конусами Минковского в дискретном пространстве. Операции в различных пирамидах могут выполнятся асинхронно (при условии, что готовы данные от которых пирамида зависит). Каждая пирамида разбивается на вдвое меньшие (по каждой из осей) пирамиды, разбиение осуществляется рекурсивно вплоть до одной ячейки сетки.

Выполнение вычислений в таком порядке обеспечивает:

  • выполнение принципа причинности;
  • высокую локальность данных и следовательно высокую эффективность (данные своевременно поступают в процессор);
  • автоматическую адаптацию кода к машинам с различными размерами кэшей подсистемы памяти.

При этом численная схема остается неизменной, меняется лишь порядок вычислений.

Разбиение на пирамиды, тривиальное для одномерных задач, существенно усложняется для двумерных и трехмерных случаев. В. Д. Левченко сумел решить задачу разбиения в самом общем случае, для любой размерности.

Практические задачи

В настоящий момент на основе LRnLA алгоритмов моделируются следующие задачи:

  • Уравнения Власова-Максвелла (метод PIC) для плазмы в Холловских двигателях, взаимодействия сверхмощного лазерного импульса с веществом;
  • Уравнения Максвелла (метод FDTD) для фотонных кристаллов, метаматериалов, устройств нанооптики;
  • Уравнения упругости (метод FDTD) для моделирования трехмерного волнового поля — синтетические сейсмограммы, разработка новых методов обработки данных сейсморазведки;
  • Уравнения Шрендингера — эффект Рашбы, задачи спинтроники (код заморожен, нет рабочих рук);
  • Обобщенные уравнения Ландау-Лифшица — спиновая динамика (микромагнитный подход), магнитные пленки, ГМС;
  • газо/гидродинамика.

Хотелось бы заняться, но пока не занялись (нет финансирования, готовых к сотрудничеству специалистов в предметной области, либо задача требует тщательной предварительной проработки):

  • МГД;
  • задачи фильтрации, моделирование резервуаров;
  • молекулярная динамика.

Вообще для молекулярной динамики LRnLA алгоритмы не нужны, там и так все хорошо с подсистемой памяти. Но если реализовать грамотное измельчение шага, то LRnLA алгоритмы могут оказаться очень востребованными.

Особенности

LRnLA алгоритмы обеспечивают:

  • качественный скачок производительности, на порядок-два по сравнению с традиционным подходом;
  • увеличение размеров решаемой задачи до размеров дисковой подсистемы без потери эффективности;
  • 100 % эффективность распараллеливания на любом числе процессоров.

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

Например, для моделирование трехмерного волнового поля (расчет синтетических сейсмограмм) в области размерами 1024x1204x1024 ячеек при традиционном подходе требуется довольно мощный кластер. При использовании LRnLA алгоритмов для этого достаточно хорошей персональной машины с высокой пропускной способностью дисковой подсистемы, при этом одна сейсмограмма (2048 отсчетов) занимает около суток машинного времени, что соответствует производительности в десятки тактов на ячейку на шаг или примерно 50 % от теоретически возможной производительности.

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


К недостаткам LRnLA алгоритмов относится высокая сложность, как для понимания, так и для реализации. LRnLA алгоритмы слишком нетрадиционны, и кардинально отличаются от общепринятых методов перевода данных с одного временного слоя на другой, что вызывает большие сложности для восприятия специалистами с уже сформировавшимися стереотипами мышления. В настоящий момент к сожалению ни автору LRnLA алгоритмов, ни мне, ни кому либо еще, не смотря на многочисленные попытки не удалось создать прозрачное описание LRnLA алгоритмов, что безусловно тормозит их «внедрение в массы». Наиболее подробное описание алгоритма можно посмотреть здесь http://a-iv.ru/LRnLA/LRnLA.pdf, однако многие (в том числе и я) считают его слишком сложным, кроме того с тех пор автор сумел продвинуться далеко вперед. Как только появится более внятный текст, я его обязательно тут выложу, а пока что если есть вопросы — пишите письма…

Реализация

Сложность реализации LRnLA алгоритмов обусловлена отсутствием в современных ЯП встроенных конструкций для локально-рекурсивного обхода области, хотя в ряде случаев такой обход куда более естественен, чем привычные всем циклы. Для достижения высокой производительности приходится прибегать к ряду ухищрений, что бы накладные расходы на локально-рекурсивный обход и реализацию граничных условий не съели весь выигрыш в скорости.

В настоящий момент LRnLA алгоритмы реализованы лишь В. Д. Левченко (о других реализациях нам неизвестно) на ЯП C++ и Python. Реализация состоит из

  • ядра алгоритма (С++), обеспечивающего локально-рекурсивный обход области и являющегося универсальным для широкого класса численных схем;
  • пользовательского кода, замыкающего рекурсию, реализующего конкретную численную схему и граничные условия.

Поскольку и ядро алгоритма и пользовательский код содержат большое количество однотипных функций с косметическими различиями, для их порождения используются кодогенераторы на ЯП Python. Кодогенератор для ядра алгоритма универсален и написан В. Д. Левченко, кодогенератор для пользовательского кода приходится писать пользователю. В настоящий момент у нас нет универсальных рецептов для пользовательского кодогенератора, хотя и ведется работа над системой компьютерной алгебры SYMBALG, которая по замыслу должна принимать численную схему на ЯП Python и генерировать пользовательский код для LRnLA алгоритма. Практика показывает, что активный студент МТФИ или МИФИ в состоянии за год-полтора овладеть навыками написания пользовательского кода для LRnLA алгоритмов и создавать программы, по производительности не имеющие мировых аналогов;-)

Кроме того, Python применяется для управления расчетом - С++ код компилируется и импортируется в виде библиотеки, все задание параметров, вызов различных методов и т. д. производится из Python. Такая архитектура на наш взгляд является оптимальной для задач численного моделирования, поскольку позволяет быстро создавать гибкие и высокопроизводительные программные комплексы, даже без использования LRnLA алгоритмов.

Созданные в настоящий момент на основе LRnLA алгоритмов коды (семейство кодов SUR) объективно являются самыми быстрыми в мире. С моей точки зрения это прекрасный контрпример для тех, кто утверждает что С++ априори медленный и неэффективный ЯП (на самом деле, на С++ очень просто писать медленные и неэффективные программы, отсюда и взялось это заблуждение). С другой стороны я не могу доказать, что LRnLA алгоритмы могут быть реализованы лишь на C++ и Python (Ruby, Java, Perl и тд). Тем не менее, для их реализации необходим эффективный оптимизирующий компилятор и возможность ручного управления памятью. В настоящий момент существенно используются шаблоны C++ (рекурсивно) и перегрузка функций, отказ от этого приведет к кардинальному и скорее всего неприемлемому усложнению кодогенератора. Я допускаю, что эта задача может быть эффективно решена на Лиспе, но у нас нет нужного уровня специалиста по Лиспу, знакомого с предметной областью.

Ссылки

Описание алгоритма от автора: http://a-iv.ru/LRnLA/LRnLA.pdf

Попытка примитивного описания, почему LRnLA алгоритмы так хорошо работают, от меня: http://a-iv.ru/LRnLA/capacity.pdf

Некоторые ссылки на презентации и препринты о применении LRnLA алгоритмов (в том числе и описание алгоритмов, наиболее свежая информация):

Статьи, содержащие описание LRnLA алгоритмов, либо как минимум результаты полученные на LRnLA кодах:

  • ВЫЧИСЛЕНИЕ ПОЛНОГО СЕЙСМИЧЕСКОГО ВОЛНОВОГО ПОЛЯ В ГЕОСРЕДЕ НА ОСНОВЕ НОВОГО МЕТОДА РЕШЕНИЯ ПРЯМЫХ ЗАДАЧ СЕЙСМОАКУСТИКИ. Иванов А. В., Каплан С. А., Каракин А. В., Левченко Т. В., Левченко В. Д., Рок В. Е. Геоинформатика / Geoinformatika. 2006. № 3. С. 59-61.
  • Левченко В. Д. Информационные технологии и вычислительные системы. 2005. № 1. С. 68.
  • Левченко В. Д. Информационные технологии и вычислительные системы. 2006. № 1. С. 1.
  • ДИНАМИЧЕСКОЕ МОДЕЛИРОВАНИЕ РАСПРОСТРАНЕНИЯ НИЗКОЧАСТОТНЫХ СЕЙСМОАКУСТИЧЕСКИХ ПОЛЕЙ В ОКЕАНИЧЕСКОЙ СРЕДЕ Левченко Д. Г., Левченко В. Д., Закиров А. В. Доклады Академии наук. 2010. Т. 435. № 4. С. 544—547.
  • ДИНАМИЧЕСКОЕ ПОЛНОВОЛНОВОЕ МОДЕЛИРОВАНИЕ РАСПРОСТРАНЕНИЯ ШТОРМОВЫХ МИКРОСЕЙСМ В ОКЕАНИЧЕСКОЙ СРЕДЕ Левченко Д. Г., Левченко В. Д., Закиров А. В. Океанология. 2011. Т. 51. № 4. С. 723—733.
  • МОДЕЛИРОВАНИЕ ВОЗБУЖДЕНИЯ КВАЗИПЛОСКИХ КИЛЬВАТЕРНЫХ ВОЛН В ПЛАЗМЕ РЕЗОНАНСНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ ЛАЗЕРНЫХ ИМПУЛЬСОВ С ИЗМЕНЯЕМОЙ ФОРМОЙ ОГИБАЮЩЕЙ Калинникова Е. И., Левченко В. Д. Физика плазмы. 2008. Т. 34. № 4. С. 324—329.
  • ОЦЕНКА ИНФОРМАТИВНОСТИ ДАННЫХ СЕЙСМОРАЗВЕДКИ МВС НА ОСНОВЕ 3D МОДЕЛИРОВАНИЯ ПОЛНОГО ВОЛНОВОГО ПОЛЯ Каплан С. А., Левченко В. Д., Рок В. Е., Глубоковских С. М., Титова Ю. А. Геоинформатика / Geoinformatika. 2011. № 1. С. 49-55.
  • DYNAMIC MODELING OF THE PROPAGATION OF LOW-FREQUENCY SEISMIC ACOUSTIC FIELDS IN THE OCEANIC MEDIUM Levchenko D.G., Levchenko V.D., Zakirov A.V. Doklady Earth Sciences. 2010. Т. 435. № 2. С. 1623—1626.
  • SIMULATION OF THE EXCITATION OF QUASI-PLANE WAKE WAVES IN A PLASMA BY A RESONANT SEQUENCE OF LASER PULSES WITH A VARIABLE ENVELOPE Kalinnikova E.I., Levchenko V.D. Plasma Physics Reports. 2008. Т. 34. № 4. С. 290—295.
  • A.Yu Perepelkina, I.A. Goryachev, V.D. Levchenko. Validation with 3D3V Weibel Instability Simulation

http://dx.doi.org/10.1088/1742-6596/441/1/012014 Journal of Physics: Conference Series. — 2013. — Vol. 441, no. 1. — P. 012014.

  • А. Ю. Перепёлкина, В. Д. Левченко, И. А. Горячев Трехмерный кинетический код CFHall для моделирования замагниченной плазмы // Математическое моделирование. — 2013. — Т. 25, No 11. — С. 98-110.
  • Б. А. Корнеев, В. Д. Левченко Моделирование уравнений газовой динамики разрывным методом Галёркина с помощью алгоритмов LRnLА Препринт ИПМ — 2013. — No 28. — С. 20.
Источник — http://lorwiki.zhbert.ru/index.php?title=LRnLA&oldid=117