1. Фрагментированное программирование
   • Система фрагментированного программирования
   • Реализация фрагментированных алгоритмов
   • Система управления распределенными структурами данных
2. Клеточно-автоматные модели диффузионного процесса
3. Гарантированная точность операции суммирования
4. Метод Годунова для численного моделирования газодинамических течений

"Фрагментированное программирование"

Положение дел в параллельном программировании таково, что большинство использующихся средств параллельного программирования соответствуют уровню ассемблера последовательного программирования, т.к. требуют явно программировать передачи данных и синхронизации параллельных процессов. Только для некоторых узких предметных областей существуют хорошие системные решения, позволяющие повысить уровень программирования. Но в общем случае программист должен хорошо знать Си/Фортран и некоторую коммуникационную библиотеку типа MPI, чтобы реализовать свою задачу на кластере.
Современные вычислительные задачи, как правило, имеют сложную структуру. Например, задача моделирования галактики может включать решение уравнений движения для звезд, газа, а также расчет их гравитационного взаимодействия. Она требует специфических методов программирования. Вычислительная нагрузка на элемент пространства моделирования определяется количеством вещества, находящимся в этом элементе пространства. Так как распределение вещества в пространстве постоянно меняется в ходе моделирования, требуется перебалансировка загрузки вычислительных узлов, обрабатывающих разные элементы пространства. Реализация подобной задачи с использованием низкоуровневых средств программирования типа Си+MPI потребует длительного времени и больших трудозатрат.
Для решения данной проблемы параллельного программирования была разработана специальная технология - технология фрагментированного программирования, которая позволяет автоматически или полуавтоматически конструировать программы. Суть этой технологии состоит в следующем:

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

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

"Система фрагментированного программирования"

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

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

1. знание Си и основ С++
2. для отдельных подпроектов может потребоваться знание Posix Threads или MPI

"Реализация фрагментированных алгоритмов"

Руководитель проекта: Киреев С.Е., м.н.с. ИВМ и МГ СО РАН

Описание проекта:
Участники проекта познакомятся с технологией фрагментированного программирования на ряде простых задач, научатся составлять фрагментированные алгоритмы. Кроме того, участники изучат несколько средств параллельного программирования, с помощью которых реализуют фрагментированные программы.

Требования к участникам проекта:

1. хорошее знание Cи

"Система управления распределенными структурами данных"

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

• Городничев М.А., м.н.с. ИВМ и МГ СО РАН
• Ларин В.В., магистрант ФПМИ НГТУ

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

Требования к участникам проекта:

1. знание Си
2. знание основ программирования

"Клеточно-автоматные модели диффузионного процесса"

Руководитель проекта: Медведев Ю.Г., к.т.н., н.с. ИВМ и МГ СО РАН

Описание проекта: Как только не имеющие в своем распоряжении компьютерной техники Ньютон и Лейбниц придумали дифференциальное исчисление, многие ученые стали создавать на его основе математические модели различных процессов, происходящих в природе и изучаемых физикой и другими науками, и весьма преуспели в этом. Такие модели работают с аналоговыми величинами, то есть с величинами, плавно, без скачков меняющими свои значения в пространстве и во времени. Дифференциальные уравнения удобно записывать и решать на бумаге, а вот компьютеру они не по зубам. Дело в том, что компьютеры работают с дискретными величинами (целыми числами), и чтобы заставить их обрабатывать вещественные числа, приходится идти на хитрость. Непрерывный диапазон очень плотно заполняют целыми числами, и с ними работают. Но очень часто значения физических величин, которые получаются при вычислениях, попадают между двух соседних чисел, как бы близко друг к другу эти числа ни находились. Приходится округлять, а так как количество операций измеряется многими миллионами и миллиардами, то ошибка округления накапливается и порой становится больше, чем результат вычислений. Такой результат никому не нужен. Это только одна из проблем, возникающих при решении дифференциальных уравнений на компьютере.
Со времен Ньютона прошло уже несколько столетий, и даже полвека прошло с тех пор как изобрели компьютер, но многие продолжают пользоваться моделями на дифференциальных уравнениях и другими аналоговыми моделями. Дело в том, что сейчас накоплено много знаний в этой области, а дискретные модели только-только начинают развиваться. Дискретное моделирование - это принципиально новый способ моделирования. В нем значения модельных величин - целые числа, которые изменяются в пространстве и во времени скачками, сразу, а не плавно, постепенно. Изменения, естественно, происходят по своим правилам, принципиально отличающимся от используемых в аналоговых моделях. Это новый вид науки, как сказал Стефан Вольфрам, автор ряда научных результатов и известного пакета "Математика". Тут мы сами контролируем, насколько детально следует разбивать шкалу, и уж, конечно же, ничего не округляем. За подобными моделями будущее, так как они предназначены для компьютера, а не для пера и чернильницы.
Одной из основных дискретных моделей является клеточный автомат, который впервые предложил в 1948 году Джон фон Нейман для описания самовоспроизводящихся структур. Затем была Конвейевская игра "Жизнь" - пример клеточного автомата, ставший уже классическим. В настоящее время клеточные автоматы активно изучаются в качестве средства моделирования различных процессов из физики, химии, биологии и других предметных областей. Клеточными автоматами моделируют потоки жидкостей и газов, распространение звуковых волн, рост кристаллов, химические реакции, и многое другое. Некоторые клеточно-автоматные модели описывают процессы, для которых дифференциальные уравнения не написаны и вряд ли когда-либо будут найдены.
Клеточные автоматы относятся к классу моделей мелкозернистого параллелизма. Это свойство позволяет получать простые и эффективные параллельные реализации, а это очень актуально сейчас, когда даже в персональном компьютере может быть не один десяток ядер, не говоря уже о мощных суперкомпьютерах с сотнями тысяч ядер. Заставить считать этого монстра одну задачу, да чтобы еще и скорость вычислений была почти во столько же раз выше, чем на одном ядре, сколько ядер в системе - задача чрезвычайно сложная (гораздо сложнее, чем понять эту фразу). Клеточно-автоматные модели позволяют эффективно загрузить самый мощный суперкомпьютер.
Из клеточных автоматов легко строить композиции. Во многие из таких композиций входит модель диффузионного процесса. Диффузия - пожалуй, самый простой и, в то же время, самый распространенный из моделируемых процессов. На ее примере легко понять принципы "нового вида науки" и научиться создавать и использовать дискретные модели для описания природных явлений. В проекте будут рассмотрены две известные клеточно-автоматные модели на булевом алфавите (синхронная (автор - Норман Марголус) и асинхронная (автор - Томассо Тоффоли)) и их обобщения до целочисленного алфавита, называемые многочастичными моделями, разработанные в ИВМиМГ СО РАН и не имеющие аналогов в мире.
Проект разбит на следующие четыре части:

• Реализация многочастичной синхронной клеточно-автоматной диффузии
• Реализация многочастичной асинхронной клеточно-автоматной диффузии
• Реализация булевой синхронной клеточно-автоматной диффузии на суперкомпьютере
• Реализация системы диффузионной обработки изображений на примере булевой асинхронной клеточно-автоматной диффузии

1. знание Cи/С++
2. свобода от стереотипов

"Гарантированная точность операции суммирования"

Руководитель проекта: Куликов И.М., к.ф.-м.н., м.н.с. ИВМ и МГ СО РАН

Описание проекта:

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

• начиная с некоторого номера, очередное слагаемое становится на уровне погрешности накопленной суммы, например, при суммировании миллиарда единиц с одинарной точностью
• случайное появление, а затем сокращение слагаемых высокого порядка приводит к катастрофической потери точности искомой суммы, например, (10^20 - 10^20) + 1 = 1 и 10^20 + (- 10^20 + 1 ) = 0 в случае двойной точности вычислений.

1. знание Си

"Метод Годунова для численного моделирования газодинамических течений"

Руководитель проекта: Куликов И.М., к.ф.-м.н., м.н.с. ИВМ и МГ СО РАН

Описание проекта:

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

Требования к участникам проекта:

1. знание Си
2. знание уравнений математической физики