Результаты, достигнутые на летней школе по параллельному программированию

Война роботов

Руководители проекта:

• Городничев М.А., м.н.с. ИВМ и МГ СО РАН
• Дубовик А.С., студент НГТУ
• Киреев С.Е., н.с. ИВМиМГ СО РАН
• Перепелкин В.А., м.н.с. ИВМиМГ СО РАН
• Щукин Г.А., аспирант НГТУ

Достигнутые результаты:

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

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

Сравнение методов вычисления корня из матрицы

Руководители проекта:

• Фатьянов А.Г., д.ф-м.н., с.н.с. ИВМиМГ СО РАН
• Киреев С.Е., н.с. ИВМиМГ СО РАН

Достигнутые результаты:

Были реализованы три метода вычисления корня из матрицы: прямой (через диагонализацию матрицы), итерационный (Denman-Beavers iteration) и через разложение в ряд Тейлора. При реализации били использованы различные последовательные и параллельные разновидности библиотеки LAPACK: fortran77 lapack, atlas, mkl, plasma. Кроме того, для распараллеливания были использованы средства OpenMP.

Был реализован генератор для матриц с заданными свойствами (симметричность, положительная определенность, матрицы с особенностями) с использованием библиотеки ALGLIB.

Выполнено сравнение реализованных методов и различных реализаций библиотеки LAPACK.

По результатам сделаны выводы:

1. На одном потоке итерационный и прямой методы вычисляют корень из матрицы за примерно одинаковое время. Итерационный метод лучше поддается распараллеливанию, чем прямой.
2. Метод, основанный на разложении в ряд Тейлора, оказался наиболее медленным из реализованных, но наиболее хорошо поддающимся распараллеливанию.
3. Прямой и итерационный методы имеют ограничения на исходную матрицу. Использование разложения в ряд Тейлора формально применимо к любым матрицам, однако скорость его сходимости очень низкая на матрицах большого размера (~ 500)

Пользовательский интерфейс для NumGRID

Руководитель проекта:

• Городничев М.А., м.н.с. ИВМ и МГ СО РАН

Достигнутые результаты:

Приложение-интерфейс может теперь отключаться от запущенных в системе задач при том, что они продолжают выполняться. Исполнитель будет развивать проекта в форме бакалаврской работы.

Система управления задачами в NumGRID на основе веб-сайта

Руководитель проекта:

• Городничев М.А., м.н.с. ИВМ и МГ СО РАН

Достигнутые результаты:

Реализован прототип системы с регистрацией пользователей и конструированием объединения кластеров. Исполнитель будет развивать проекта в форме бакалаврской работы.

Фрагментированные структуры данных

Руководитель проекта:

• Городничев М.А., м.н.с. ИВМ и МГ СО РАН

Достигнутые результаты:

Сформулированы требования к реализации распределенного массива, выработан план реализации, представлен прототип библиотеки. Исполнитель будет развивать проект в форме бакалаврской работы.