Параллельные вычисления в WinNT. Методы параллельных вычислений Области применения параллельных расчётов на графических ускорителях

Транскрипт

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

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

3 передачи сообщений. В дополнение, на этой модели может быть показано распределение процессов по процессорам вычислительной системы, если количество подзадач превышает число процессоров см. рис процесс - канал - операции приема (передачи) - входные (выходные) каналы для взаимодействия процессов Рис Модель параллельной программы в виде графа "процессы-каналы" Использование двух моделей параллельных вычислений 2) позволяет лучше разделить проблемы, которые проявляются при разработке параллельных методов. Первая модель граф "подзадачи - сообщения" позволяет сосредоточиться на вопросах выделения подзадач одинаковой вычислительной сложности, обеспечивая при этом низкий уровень информационной зависимости между подзадачами. Вторая модель граф "процессы каналы" концентрирует внимание на вопросах распределения подзадач по процессорам, обеспечивая еще одну возможность снижения трудоемкости информационных взаимодействий между подзадачами за счет размещения на одних и тех же процессорах интенсивно взаимодействующих процессов. Кроме того, эта модель позволяет лучше анализировать эффективность разработанного параллельного метода и обеспечивает возможность более адекватного описания процесса выполнения параллельных вычислений. Дадим дополнительные пояснения для используемых понятий в модели "процессы-каналы": Под процессом в рамках данного учебного материала будем понимать выполняемую на процессоре программу, которая использует для свой работы часть локальной памяти процессора и которая содержит ряд операций приема/передачи данных для организации информационного взаимодействия между выполняемыми процессами параллельной программы, Канал передачи данных с логической точки зрения может рассматриваться как очередь сообщений, в которую один или несколько процессов могут отправлять пересылаемые данные и из которой процесс-адресат может извлекать сообщения, отправляемые другими процессами. В общем случае, можно считать, что каналы возникают динамически в момент выполнения первой операции приема/передачи с каналом. По степени общности, канал может соответствовать одной или нескольким командам приема данных процесса-получателя; аналогично при передаче сообщений канал может использоваться одной или несколькими командами передачи данных одного или нескольких процессов. Для снижения сложности моделирования и анализа параллельных методов будем предполагать, что емкость каналов является неограниченной и, как результат, операции передачи данных выполняются практически без задержек простым копированием сообщений в канал. С другой стороны, операции приема сообщений могут приводить к задержкам (блокировкам), если запрашиваемые из канала данные еще не были отправлены процессами-источниками сообщений. Следует отметить важное достоинство рассмотренной модели "процессы-каналы" в этой модели проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и 2) В Foster (1995) рассматривается только одна модель модель "задача-канал" для описания параллельных вычислений, которая занимает некоторое промежуточное положение по сравнению с изложенными здесь моделями. Так, в модели "задачаканал" не учитывается возможность использования одного процессора для решения нескольких подзадач одновременно. 3

4 действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ Этапы разработки параллельных алгоритмов Рассмотрим более подробно изложенную выше методику разработки параллельных алгоритмов. В значительной степени данная методика опирается на подход, впервые рассмотренный в Foster (1995), и, как отмечалось ранее, включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы (см. рис. 6.1). Для демонстрации приводимых рекомендаций далее будет использоваться учебная задача поиска максимального значения среди элементов матрицы A (такая задача возникает, например, при численном решении систем линейных уравнений для определения ведущего элемента метода Гаусса): y = max a. 1 i, j N i j Такая задача носит полностью иллюстративный характер, и после рассмотрения этапов разработки в оставшейся части раздела будет приведен более полный пример использования данной методики для разработки параллельных алгоритмов. Кроме того, данная схема разработки будет применена и при изложении всех далее рассматриваемых методов параллельных вычислений Разделение вычислений на независимые части Выбор способа разделения вычислений на независимые части основывается на анализе вычислительной схемы решения исходной задачи. Требования, которым должен удовлетворять выбираемый подход, обычно состоят в обеспечении равного объема вычислений в выделяемых подзадачах и минимума информационных зависимостей между этими подзадачами (при прочих равных условиях нужно отдавать предпочтение редким операциям передачи большего размера сообщений по сравнению с частыми пересылками данных небольшого объема). В общем случае, проведение анализа и выделение задач представляет собой достаточно сложную проблему ситуацию помогает разрешить существование двух часто встречающихся типов вычислительных схем: а) б) Рис Разделение данных для матрицы A: а) ленточная схема, б) блочная схема Для большого класса задач вычисления сводятся к выполнению однотипной обработки элемент элементов большого набора данных к такому виду задач относятся, например, матричные вычисления, численные методы решения уравнений в частных производных и др. В этом случае говорят, что существует параллелизм по данным, и выделение подзадач сводится к разделению имеющихся данных. Так, например, для нашей учебной задачи поиска максимального значения при формировании подзадач исходная матрица A может быть разделена на отдельные строки (или последовательные группы строк) ленточная схема разделения данных (см. рис. 6.3) или на прямоугольные наборы элементов блочная схема разделения данных. Для большого количества решаемых задач разделение вычислений по данным приводит к порождению одно-, двух- и трех- мерных наборов подзадач, для которых информационные связи существуют только между ближайшими соседями (такие схемы обычно именуются сетками или решетками), 4

5 Рис Регулярные одно-, двух- и трех- мерные структуры базовых подзадач после декомпозиции данных Для другой части задач вычисления могут состоять в выполнении разных операций над одним и тем же набором данных в этом случае говорят о существовании функционального параллелизма (в качестве примеров можно привести задачи обработки последовательности запросов к информационным базам данных, вычисления с одновременным применением разных алгоритмов расчета и т.п.). Очень часто функциональная декомпозиция может быть использована для организации конвейерной обработки данных (так, например, при выполнении каких-либо преобразований данных вычисления могут быть сведены к функциональной последовательности ввода, обработки и сохранения данных). Важный вопрос при выделении подзадач состоит в выборе нужного уровня декомпозиции вычислений. Формирование максимально возможного количества подзадач обеспечивает использование предельно достижимого уровня параллелизма решаемой задачи, однако затрудняет анализ параллельных вычислений. Использование при декомпозиции вычислений только достаточно "крупных" подзадач приводит к ясной схеме параллельных вычислений, однако может затруднить эффективное использование достаточно большого количества процессоров. Возможное разумное сочетание этих двух подходов может состоять в использовании в качестве конструктивных элементов декомпозиции только тех подзадач, для которых методы параллельных вычислений являются известными. Так, например, при анализе задачи матричного умножения в качестве подзадач можно использовать методы скалярного произведения векторов или алгоритмы матрично-векторного произведения. Подобный промежуточный способ декомпозиции вычислений позволит обеспечить и простоту представления вычислительных схем, и эффективность параллельных расчетов. Выбираемые подзадачи при таком подходе будем именовать далее базовыми, которые могут быть элементарными (неделимыми), если не допускают дальнейшего разделения, или составными в противном случае. Для рассматриваемой учебной задачи достаточный уровень декомпозиции может состоять, например, в разделении матрицы A на множество отдельных строк и получении на этой основе набора подзадач поиска максимальных значений в отдельных строках; порождаемая при этом структура информационных связей соответствует линейному графу см. рис Для оценки корректности этапа разделения вычислений на независимые части можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Выполненная декомпозиция не увеличивает объем вычислений и необходимый объем памяти? Возможна ли при выбранном способе декомпозиции равномерная загрузка всех имеющихся процессоров? Достаточно ли выделенных частей процесса вычислений для эффективной загрузки имеющихся процессоров (с учетом возможности увеличения их количества)? Выделение информационных зависимостей При наличии вычислительной схемы решения задачи после выделения базовых подзадач определение информационных зависимостей между подзадачами обычно не вызывает больших затруднений. При этом, однако, следует отметить, что на самом деле этапы выделения подзадач и информационных зависимостей достаточно сложно поддаются разделению. Выделение подзадач должно происходить с учетом возникающих информационных связей; после анализа объема и частоты необходимых информационных обменов между подзадачами может потребоваться повторение этапа разделения вычислений. При проведении анализа информационных зависимостей между подзадачами следует различать (предпочтительные формы информационного взаимодействия выделены подчеркиванием): Локальные и глобальные схемы передачи данных для локальных схем передачи данных в каждый момент времени выполняются только между небольшим числом подзадач (располагаемых, как 5

6 правило, на соседних процессорах), для глобальных операций передачи данных в процессе коммуникации принимают участие все подзадачи, Структурные и произвольные способы взаимодействия для структурных способов организация взаимодействий приводит к формированию некоторых стандартных схем коммуникации (например, в виде кольца, прямоугольной решетки и т.д.), для произвольных структур взаимодействия схема выполняемых операций передач данных не носит характер однородности, Статические или динамические схемы передачи данных для статических схем моменты и участники информационного взаимодействия фиксируются на этапах проектирования и разработки параллельных программ, для динамического варианта взаимодействия структура операции передачи данных определяется в ходе выполняемых вычислений, Синхронные и асинхронные способы взаимодействия для синхронных способов операции передачи данных выполняются только при готовности всех участников взаимодействия и завершаются только после полного окончания всех коммуникационных действий, при асинхронном выполнении операций участники взаимодействия могут не дожидаться полного завершения действий по передаче данных. Для представленных способов взаимодействия достаточно сложно выделить предпочтительные формы организации передачи данных: синхронный вариант, как правило, более прост для использования, в то время как асинхронный способ часто позволяет существенно снизить временные задержки, вызванные операциями информационного взаимодействия. Как уже отмечалось в предыдущем пункте, для учебной задачи поиска максимального значения при использовании в качестве базовых элементов подзадач поиска максимальных значений в отдельных строках исходной матрицы A структура информационных связей имеет вид, представленный на рис Рис Структура информационных связей учебной задачи Как и ранее, для оценки правильности этапа выделения информационных зависимостей можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Соответствует ли вычислительная сложность подзадач интенсивности их информационных взаимодействий? Является ли одинаковой интенсивность информационных взаимодействий для разных подзадач? Является ли схема информационного взаимодействия локальной? Не препятствует ли выявленная информационная зависимость параллельному решению подзадач? Масштабирование набора подзадач Масштабирование разработанной вычислительной схемы параллельных вычислений проводится в случае, если количество имеющихся подзадач отличается от числа планируемых к использованию процессоров. Для сокращения количества подзадач необходимо выполнить укрупнение (агрегацию) вычислений. Применяемые здесь правила совпадают с рекомендациями начального этапа выделения подзадач определяемые подзадачи, как и ранее, должны иметь одинаковую вычислительную сложность, а объем и интенсивность информационных взаимодействий между подзадачами должны оставаться на минимально-возможном уровне. Как результат, первыми претендентами на объединение являются подзадачи с высокой степенью информационной взаимозависимости. При недостаточном количестве имеющегося набора подзадач для загрузки всех доступных к использованию процессоров необходимо выполнить детализацию (декомпозицию) вычислений. Как 6

7 правило, проведение подобной декомпозиции не вызывает каких-либо затруднений, если для базовых задач методы параллельных вычислений являются известными. Выполнение этапа масштабирования вычислений должно свестись, в конечном итоге, к разработке правил агрегации и декомпозиции подзадач, которые должны параметрически зависеть от числа процессоров, применяемых для вычислений. Для рассматриваемой учебной задачи поиска максимального значения агрегация вычислений может состоять в объединении отдельных строк в группы (ленточная схема разделения матрицы см. рис. 6.3а), при декомпозиции подзадач строки исходной матрицы A могут разбиваться на несколько частей (блоков). Список контрольных вопросов, предложенный в Foster (1995) для оценки правильности этапа масштабирования, выглядит следующим образом: Не ухудшится ли локальность вычислений после масштабирования имеющегося набора подзадач? Имеют ли подзадачи после масштабирования одинаковую вычислительную и коммуникационную сложность? Соответствует ли количество задач числу имеющихся процессоров? Зависят ли параметрически правила масштабирования от количества процессоров? Распределение подзадач между процессорами Распределение подзадач между процессорами является завершающим этапом разработки параллельного метода. Надо отметить, что управление распределением нагрузки для процессоров возможно только для вычислительных систем с распределенной памятью, для мультипроцессоров (систем с общей памятью) распределение нагрузки обычно выполняется операционной системой автоматически. Кроме того, данный этап распределения подзадач между процессорами является избыточным, если количество подзадач совпадает с числом имеющихся процессоров, а топология сети передачи данных вычислительной системы представляет собой полный граф (т.е., все процессоры связаны между собой прямыми линиями связи). Основной показатель успешности выполнения данного этапа эффективность использования процессоров, определяемая как относительная доля времени, в течение которого процессоры использовались для вычислений, связанных с решением исходной задачи. Пути достижения хороших результатов в этом направлении остаются прежними как и ранее, необходимо обеспечить равномерное распределение вычислительной нагрузки между процессорами и минимизировать количество сообщений, передаваемых между процессорами. Точно так же, как и на предшествующих этапах проектирования, оптимальное решение проблемы распределения подзадач между процессорами основывается на анализе информационной связности графа "подзадачи - сообщения". Так, в частности, подзадачи, между которыми имеются информационные взаимодействия, целесообразно размещать на процессорах, между которыми существуют прямые линии передачи данных. Следует отметить, что требование минимизации информационных обменов между процессорами может противоречить условию равномерной загрузки процессов. Так, мы можем разместить все подзадачи на одном процессоре и полностью устранить межпроцессорную передачу сообщений, однако, понятно, загрузка большинства процессоров в этом случае будет минимальной. Для нашей учебной задачи поиска максимального значения распределение подзадач между процессорами не вызывает каких-либо затруднений достаточно лишь обеспечить размещение подзадач, между которыми имеются информационные связи, на процессорах, для которых существуют прямые каналы передачи данных. Поскольку структура информационной связей учебной задачи имеет вид линейного графа, выполнение данного требования может быть обеспечено практически при любой топологии сети вычислительной системы. Решение вопросов балансировки вычислительной нагрузки значительно усложняется, если схема вычислений может изменяться в ходе решения задачи. Причиной этого могут быть, например, неоднородные сетки при решении уравнений в частных производных, разреженность матриц и т.п. 3). Кроме того, используемые на этапах проектирования оценки вычислительной сложности решения подзадач могут иметь приближенный характер и, наконец, количество подзадач может изменяться в ходе вычислений. В таких ситуациях может потребоваться перераспределение базовых подзадач между 3) Можно отметить, что даже для нашей простой учебной задачи может наблюдаться различная вычислительная сложность сформированных базовых задач. Так, например, количество операций при поиске максимального значения для строки, в которой максимальное значение имеет первый элемент, и строки, в которой значения являются упорядоченными по возрастанию, будет различаться в два раза. 7

8 процессорами уже непосредственно в процессе выполнения параллельной программы (или, как обычно говорят, придется выполнить динамическую балансировку вычислительной нагрузки). Данные вопросы являются одними из наиболее сложных (и наиболее интересных) в области параллельных вычислений к сожалению, рассмотрение данных вопросов выходит за рамки данного учебного материала (дополнительная информация может быть получена, например, в Buyya (1999) и Wilkinson and Allen (1999)). В качестве примера дадим краткую характеристику широко используемого способа динамического управления распределением вычислительной нагрузки, обычно именуемого схемой "менеджер - исполнитель" (manager-worker scheme). При использовании данного подхода предполагается, что подзадачи могут возникать и завершаться в ходе вычислений, при этом информационные взаимодействия между подзадачами либо полностью отсутствует, либо минимальны. В соответствии с рассматриваемой схемой для управления распределением нагрузки в системе выделяется отдельный процессор-менеджер, которому доступна информация обо всех имеющихся подзадачах. Остальные процессоры системы являются исполнителями, которые для получения вычислительной нагрузки обращаются к процессору-менеджеру. Порождаемые в ходе вычислений новые подзадачи передаются обратно процессору-менеджеру и могут быть получены для решения при последующих обращениях процессоров-исполнителей. Завершение вычислений происходит в момент, когда процессорыисполнители завершили решение всех переданных им подзадач, а процессор-менеджер не имеет какихлибо вычислительных работ для выполнения. Предложенный в Foster (1995) перечень контрольных вопросов для проверки этапа распределения подзадач состоит в следующем: Не приводит ли распределение нескольких задач на один процессор к росту дополнительных вычислительных затрат? Существует ли необходимость динамической балансировки вычислений? Не является ли процессор-менеджер "узким" местом при использовании схемы "менеджерисполнитель"? 6.3. Параллельное решение гравитационной задачи N тел Многие вычислительные задачи в области физики сводятся к операциям обработки данных для каждой пары объектов имеющейся физической системы. Такой задачей является, в частности, проблема, широко известная в литературе как гравитационная задача N тел (или просто задача N тел) см., например, Andrews (2000) В самом общем виде, задача может быть описана следующим образом. Пусть дано большое количество тел (планет, звезд и т.д.), для каждого из которых известна масса, начальное положение и скорость. Под действием гравитации положение тел меняется, и требуемое решение задачи состоит в моделировании динамики изменения системы N тел на протяжении некоторого задаваемого интервала времени. Для проведения такого моделирования заданный интервал времени обычно разбивается на временные отрезки небольшой длительности и далее на каждом шаге моделирования вычисляются силы, действующие на каждое тело, а затем обновляются скорости и положения тел. Очевидный алгоритм решения задачи N тел состоит в рассмотрении на каждом шаге моделирования всех пар объектов физической системы и выполнении для каждой получаемой пары всех необходимых расчетов. Как результат, при таком подходе время выполнения одной итерации моделирования будет составлять 4) T = τ N(N 1) / 2, 1 где τ есть время перевычисления параметров одной пары тел. Как следует из приведенного описания, вычислительная схема рассмотренного алгоритма является сравнительно простой, что позволяет использовать задачу N тел в качестве еще одной наглядной демонстрации применения методики разработки параллельных алгоритмов. 4) Следует отметить, что для решения задачи N тел существует и более эффективные последовательные алгоритмы, однако их изучение может потребовать достаточно больших усилий. С учетом данного обстоятельства для дальнейшего рассмотрения выбирается именно данный "очевидный" (но не самый быстрый) метод, хотя, в общем случае, безусловно, для распараллеливания следует выбирать наилучшие схемы выполнения расчетов. 8

9 Разделение вычислений на независимые части Выбор способа разделения вычислений не вызывает каких-либо затруднений - очевидный подход состоит в выборе в качестве базовой подзадачи всего набора вычислений, связанных с обработкой данных одного какого-либо тела физической системы Выделение информационных зависимостей Выполнение вычислений, связанных с каждой подзадачей, становится возможным только в случае, когда в подзадачах имеются данные (положение и скорости передвижения) обо всех телах имеющейся физической системы. Как результат, перед началом каждой итерации моделирования каждая подзадача должна получить все необходимые сведения от всех других подзадач системы. Такая процедура передачи данных, как отмечалось в разделе 3, именуется операцией сбора данных (single-node gather). В рассматриваемом алгоритме данная операция должна быть выполнена для каждой подзадачи такой вариант передачи данных обычно именуется как операция обобщенного сбора данных (multi-node gather or all gather). Определение требований к необходимым результатам информационного обмена не приводит к однозначному установлению нужного информационного обмена между подзадачами достижение требуемых результатов может быть обеспечено при помощи разных алгоритмов выполнения операции обобщенного сбора данных. Наиболее простой способ выполнения необходимого информационного обмена состоит в реализации последовательности шагов, на каждом из которых все имеющиеся подзадачи разбиваются попарно и обмен данными осуществляется между подзадачами образовавшихся пар. При надлежащей организации попарного разделения подзадач (N-1)-кратное повторение описанных действий приведет к полной реализации требуемой операции сбора данных. Рассмотренный выше метод организации информационного обмена является достаточно трудоемким для сбора всех необходимых данных требуется (N-1) итераций, на каждой из которых выполняется одновременно (N/2) операций передачи данных. Для сокращения требуемого количества итераций можно обратить внимание на факт, что после выполнения первого шага операции сбора данных подзадачи будут уже содержать не только свои данные, но и данные подзадач, с которыми они образовывали пары. Как результат, на второй итерации сбора данных можно будет образовывать пары подзадач для обмена данными сразу о двух телах физической системы тем самым, после завершения второй итерации каждая подзадача будет содержать сведения о четырех телах системы и т.д. Как можно заметить, данный способ реализации обменов позволяет завершить необходимую процедуру за log 2 N итераций. Следует отметить, что при этом объем пересылаемых данных в каждой операции обмена удваивается от итерации к итерации на первой итерации между подзадачами пересылаются данные об одном теле системы, на второй итерации о двух телах и т.д. Использование рассмотренного способа реализации операции обобщенного сбора данных приводит к определению структуры информационных связей между подзадачами в виде N-мерного гиперкуба Масштабирование и распределение подзадач по процессорам Как правило, число тел физической системы N значительно превышает количество процессоров p. Как результат, рассмотренные ранее подзадачи следует укрупнить, объединив в рамках одной подзадачи вычисления для группы (N/p) тел. После проведения подобной агрегации число подзадач и количество процессоров будет совпадать, и при распределении подзадач между процессорами останется лишь обеспечить наличие прямых коммуникационных линий между процессорами с подзадачами, между которыми имеются информационные обмены при выполнении операции сбора данных Анализ эффективности параллельных вычислений Оценим эффективность разработанных способов параллельных вычислений для решения задачи N тел. Поскольку предложенные варианты отличаются только методами выполнения информационных обменов, для сравнения подходов достаточно определить длительность операции обобщенного сбора данных. Используем для оценки времени передачи сообщений модель, предложенную Хокни (см. раздел 3), тогда длительность выполнения операции сбора данных для первого варианта параллельных вычислений может быть выражена как 1 T p (comm) = (p 1)(α + m (N / p) / β), где α, β есть параметры модели Хокни (латентность и пропускная способность сети передачи данных), а m задает объем пересылаемых данных для одного тела физической системы. 9

10 Для второго способа информационного обмена, как уже отмечалось ранее, объем пересылаемых данных на разных итерациях операции сбора данных различается. На первой итерации объем пересылаемых сообщений составляет (mn/p), на второй итерации этот объем увеличивается вдвое и оказывается равным 2(mN/p) и т.д. В общем случае, для итерации с номером i объем сообщений оценивается как 2 i-1 (mn/p). Как результат, длительность выполнения операции сбора данных в этом случае может быть определена при помощи следующего выражения T 2 p log p i= 1 i 1 (comm) = (α + 2 m(N / p) / β) = α log p + m (N / p)(p 1) / β. Сравнение полученных выражений показывает, что второй разработанный способ параллельных вычислений имеет существенно более высокую эффективность, несет меньшие коммуникационные затраты и допускает лучшую масштабируемость при увеличении количества используемых процессоров Краткий обзор раздела В разделе была рассмотрена методика разработки параллельных алгоритмов, предложенная в Foster (1995). Данная методика включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы. При применении методики предполагается, что вычислительная схема решения рассматриваемой задачи уже является известной. Основные требования, которые должны быть обеспечены при разработке параллельных алгоритмов, состоят в обеспечении равномерной загрузки процессоров при низком информационном взаимодействии сформированного множества подзадач. Для описания получаемых в ходе разработки вычислительных параллельных схем рассмотрены две модели. Первая из них модель "подзадачи-сообщения" может быть использована на стадии проектирования параллельных алгоритмов, вторая модель "процессы-каналы" может быть применена на стадии реализации методов в виде параллельных программ. В завершение раздела показывается применение рассмотренной методики разработки параллельных алгоритмов на примере решения гравитационной задачи N тел Обзор литературы Рассмотренная в разделе методика разработки параллельных алгоритмов впервые была предложена в Foster (1995). В этой работе изложение методики проводится более детально; кроме того, в работе содержится несколько примеров использования методики для разработки параллельных методов для решения ряда вычислительных задач. Полезной при рассмотрении вопросов проектирования и разработки параллельных алгоритмов может оказаться также работа Quinn (2004). Гравитационная задача N тел более подробно рассматривается в Andrews (2000) Контрольные вопросы 1. В чем состоят исходные предположения для возможности применения рассмотренной в разделе методики разработки параллельных алгоритмов? 2. Каковы основные этапы проектирования и разработки методов параллельных вычислений? 3. Как определяется модель "подзадачи-сообщения"? 4. Как определяется модель "процессы-каналы"? 5. Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов? 6. В чем состоят основные действия на этапе выделения подзадач? 7. Каковы основные действия на этапе определения информационных зависимостей? 8. В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач? 9. В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы? 10. Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер - исполнитель"? 11. Какой метод параллельных вычислений был разработан для решения гравитационной задачи N тел? 10

11 12. Какой способ выполнения операции обобщенного сбора данных является более эффективным? 6.7. Задачи и упражнения 1. Выполните реализацию каскадной схемы вычисления суммы последовательности числовых значений (см. раздел 2) и сравните время выполнения выполненной реализации и функции MPI_Bcast библиотеки MPI. 2. Выполните реализацию рассмотренных способов выполнения обобщенной операции сбора данных и сравните время их выполнения. Сопоставьте получаемые временные характеристики с имеющими теоретическими оценками. Выполните сравнение со временем выполнения функции MPI_Allgather библиотеки MPI. 3. Разработайте схему параллельных вычислений, используя рассмотренную в разделе методику проектирования и разработки параллельных методов: для задачи поиска максимального значения среди минимальных элементов строк матрицы (такая задача имеет место для решения матричных игр) y = max min a, 1 i N 1 j N ij (обратите особое внимание на ситуацию, когда число процессоров превышает порядок матрицы, т.е. p>n), для задачи вычисления определенного интеграла с использованием метода прямоугольников b N 1 y = f (x) dx h fi, a i= 0 f i = f (x), x = i h, h = (b a) / N. i i (описание методов интегрирования дано, например, в Kahaner, Moler and Nash (1988)) 4. Выполните реализацию разработанных параллельных методов для задач п Разработайте схему параллельных вычислений для задачи умножения матрицы на вектор, используя рассмотренную в разделе методику проектирования и разработки параллельных методов. Литература Andrews, G. R. (2000). Foundations of Multithreaded, Parallel, and Distributed Programming.. Reading, MA: Addison-Wesley (русский перевод Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом "Вильямс", 2003) Bertsekas, D.P., Tsitsiklis, J.N. (1989) Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Ed.) (1999). High Performance Cluster Computing. Volume1: Architectures and Systems. Volume 2: Programming and Applications. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Numerical Methods and Software. Prentice Hall (русский перевод Каханер Д., Моулер Л., Нэш С. Численные методы и программное обеспечение. М.: Мир, 2001) Foster, I. (1995). Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. New York, NY: McGraw-Hill. Wilkinson, B., Allen, M. (1999). Parallel programming. Prenrice Hall. 11

ГЛАВА 3 ПРИНЦИПЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ МЕТОДОВ Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную

Методы и алгоритмы параллельных вычислений Проектирование параллельных алгоритмов Кулаков Кирилл Александрович 2016 Петрозаводск Цели проектирования Балансировка нагрузки Масштабируемость Эффективность

Высокопроизводительные вычисления Лекция 2. Оценка максимально возможного параллелизма Обеспечение наилучших наилучшего ускорения S T = эффективности E = 1 возможно не для всех вычислительно T трудоемких

Лекции Лекция 1. Принципы построения параллельных вычислительных систем.............................. 23 Лекция 2. Моделирование и анализ параллельных вычислений...... 49 Лекция 3. Оценка коммуникационной

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 9. Параллельные

Проект комиссии Президента по модернизации и технологическому развитию экономики России «Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного

Тема: Распараллеливание выражений на примере арифметических Основные характеристики сложности и параллельности Что подлежит распараллеливанию? Задача (декомпозиция на подзадачи меньшей размерности) 2Метод

ВОПРОСЫ К ТЕСТУ ПО КУРСУ «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ» 1. Принципы построения параллельных вычислительных систем (15) 1. Схемы многопроцессорных систем с однородным и неоднородным доступом. 2.

Проектирование параллельных алгоритмов Лекция 3.1 29.03.2012 Т.Ю.Лымарь 1 3.1 Методология проектирования Разделение Установление связей Агрегирование Привязка к конкретной ЭВМ 29.03.2012 Т.Ю.Лымарь 2 3.1.1

Московский государственный университет им. М.В. Ломоносова История и методология параллельного программирования 9. Проектирование параллельных алгоритмов Разработчики: Л.Б. Соколинский, д.ф.-м.н., профессор

Федеральное агентство по образованию Нижегородский государственный университет им. Н.И. Лобачевского Национальный проект «Образование» Инновационная образовательная программа ННГУ. Образовательно-научный

Нижегородский государственный университет им. Н.И.Лобачевского Факультет вычислительной математики и кибернетики Кафедра математического обеспечения ЭВМ Лаборатория «Информационные технологии» ItLab Практический

Нижегородский государственный университет им. Н.И. Лобачевского - Национальный исследовательский университет - Лекция. Моделирование параллельных вычислений Гергель В.П., декан ВМК ННГУ Суперкомпьютерные

Алгоритмы для параллельных вычислительных систем 1. Типы параллелизма и методы синтеза параллельных алгоритмов. 2. Оценка эффективности параллельных алгоритмов. 1. Типы параллелизма и методы синтеза параллельных

СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Проект Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения

Оценка эффективности параллельных алгоритмов Лекция 4. 29.03.2012 Т.Ю. Лымарь 1 Введение Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:

Оценка эффективности параллельных алгоритмов Лекция 7 Т.Ю. Лымарь Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма: Оценка максимально возможного

ОСНОВНЫЕ ПОНЯТИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Параллельные вычисления (параллельная обработка) это использование нескольких или многих вычислительных устройств для одновременного выполнения разных частей одной

Математические модели и методы эффективного использования распределенных Цифровая вычислительных 3D-медицина систем Заголовок Результаты Подзаголовок в области компьютерной презентации графики и геометрического

УДК 681.5 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ЧИСЛЕННОГО РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ СОДУ Назарова И.А. Донецкий национальный технический университет Запропоновано паралельні чисельні алгоритми однокрокових методів для

ГЛАВА МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ При разработке параллельных алгоритмов решения сложных научнотехнических задач принципиальным моментом является анализ эффективности использования параллелизма,

1. Цели и задачи дисциплины: Суперкомпьютерные технологии и высокопроизводительные вычисления с использованием многопроцессорных вычислительных систем (МВС) становятся важным фактором научно-технического

Построение статистических моделей эффективности параллельных программ В.Н.Белецкий, С.А.Резникова, А.А.Чемерис Институт проблем моделирования в энергетике им. Г.Е.Пухова НАН Украины В статье рассмотрен

Информатика, управление, экономика ТРУДЫ МФТИ 2 Том 2, (5) УДК 59687+475 АС Хританков Московский физико-технический институт (государственный университет) Математическая модель характеристик производительности

АЛГОРИТМЫ БАЛАНСИРОВКИ ЗАГРУЗКИ ПРОЦЕССОРОВ ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ Бельков Д.В. Донецкий национальный технический университет, г. Донецк кафедра вычислительной математики и программирования

Вычислительные машины и программное обеспечение УДК 681.3.06 П.А. Павлов ЭФФЕКТИВНОСТЬ РАСПРЕДЁЛЕННЫХ ВЫЧИСЛЕНИЙ В МАСШТАБИРУЕМЫХ СИСТЕМАХ Масштабируемость (scalability) является одним из важнейших требований

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

ДИАГОНАЛЬНЫЙ МЕТОД УМНОЖЕНИЯ ПЛОТНЫХ МАТРИЦ Князькова Т.В., к.т.н., доцент, ВятГУ, г. Киров Сегодня с ростом мощностей вычислительных систем и современных суперкомпьютеров в широком спектре отраслей экономики

Введение 1 Глава 1 Задания 1.1 Разминка Первое задание на написание программы, использующей библиотеку MPI, одно на всех. 1.1.1 Вычисление числа π Вычислить число π по следующей формуле: 1 1 dx 4 1 + x

Лабораторная работа 4 Параллельная реализация метода Якоби в трехмерной области Цель работы: практическое освоение методов распараллеливания численных алгоритмов на регулярных сетках на примере реализации

Р. И. Идрисов ВРЕМЕННАЯ РАЗВЁРТКА ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ IR2 ЯЗЫКА SISAL 3.1 * На сегодняшний день увеличение вычислительных мощностей связано уже не с ускорением отдельного, а с добавлением дополнительных

Стратегия оптимизационного исследования и методы решения задач статической и динамической оптимизации технологических объектов Задачи статической оптимизации технологических объектов традиционно формулируются

ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ЗЕРНИСТЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ (Получение параллельных последовательностей зернистых вычислений) Приведем примеры получения параллельных алгоритмов, множества операций которых

ПАРАЛЛЕЛЬНЫЕ СВОЙСТВА АЛГОРИТМА Параллельные компьютеры (суперкомпьютеры) предназначены для быстрого решения больших задач. Чем мощнее компьютер, тем потенциально быстрее можно решить на нем задачу. Помимо

Каляев А.В. ПРОГРАММИРОВАНИЕ ВИРТУАЛЬНЫХ АРХИТЕКТУР И ОРГАНИЗАЦИЯ СТРУКТУРНО- ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ 1 Аннотация НИИ многопроцессорных вычислительных

Алгоритмы параллельного умножения матриц 1 Ленточные алгоритмы умножения матриц В данных алгоритмах матрицы разбиваются на непрерывные последовательности строк или столбцов (полосы). В простейшем случае

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

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ вида Численное решение нелинейных алгебраических или трансцендентных уравнений. заключается в нахождении значений

«Алгебра и геометрия» 13. Системы линейных алгебраических уравнений (СЛАУ). Теорема Кронекера-Капелли. Общее и частное решения СЛАУ. 14. Кривые второго порядка: эллипс, гипербола, парабола, и их свойства.

УДК 681.32 ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ КЛАСТЕРОВ РАБОЧИХ СТАНЦИЙ С ИСПОЛЬЗОВАНИЕМ ВЕЕРНОГО РАСПРЕДЕЛЕНИЯ ДОПОЛНИТЕЛЬНЫХ ЗАДАНИЙ НА ПРОСТАИВАЮЩЕЕ ОБОРУДОВАНИЕ 2012 В. М. Довгаль 1, С. Г. Спирин 2 1 профессор

Граф алгоритма и параллельные вычисления. Внутренний параллелизм программ. Лекция 3 12.04.2012 (С) Л.Б.Соколинский 1 3.1 Внутренний параллелизм Программа содержит параллелизм, если некоторые ее части (операторы)

МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П.КОРОЛЕВА

Лекция 5 5 Теорема существования и единственности решения задачи Коши для нормальной системы ОДУ Постановка задачи Задача Коши для нормальной системы ОДУ x = f (, x), () состоит в отыскании решения x =

Глава 5. МЕТОДЫ НЕЯВНОГО ПЕРЕБОРА Рассмотрим общую постановку задачи дискретной оптимизации mi f (x), (5.) x D в которой -мерный искомый вектор x принадлежит конечному множеству допустимых решений D.

ОГЛАВЛЕНИЕ Введение.... 12 Ч а с т ь I. Основы распараллеливания Лекция 1. О постановке задачи распараллеливания... 17 1.1. Введение.... 17 1.2. О некоторых вычислительных задачах.... 19 1.3. Численный

УДК 68.3.06 ОПРЕДЕЛЕНИЕ ЧИСЛА И ТОПОЛОГИИ РАЗМЕЩЕНИЯ СТАНЦИЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ А.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected] Рассмотрены задачи

ЭКСТРАПОЛЯЦИОННЫЕ БЛОЧНЫЕ ОДНОШАГОВЫЕ МЕТОДЫ ЧИСЛЕННОГО ВЫСОКОТОЧНОГО РЕШЕНИЯ ЗАДАЧИ КОШИ Кулаков В.В. Назарова И. А.Фельдман Л.П. Донецкий национальный технический университет Рассматриваются параллельные

Труды ИСА РАН, 2008. Т. 32 О понятии производительности в распределенных вычислительных системах М. А. Посыпкин, А. С. Хританков Институт системного анализа Российской академии наук (ИСА РАН) В данной

2007 НАУЧНЫЙ ВЕСТНИК МГТУ ГА 26 серия Радиофизика и радиотехника УДК 6236:6239 ОЦЕНКА ЦЕЛЕСООБРАЗНОСТИ РАСПАРАЛЛЕЛИВАНИЯ ИНФОРМАЦИОННО-ЗАВИСИМЫХ ЗАДАЧ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РН АКИНШИН Статья представлена

Максимальное распараллеливание алгоритмов на основе концепции Q-детерминанта Валентина Николаевна Алеева Южно-Уральский государственный университет (НИУ) Новосибирcк, 2015 ВВЕДЕНИЕ В докладе рассматривается

Министерство образования и науки Российской Федерации Нижегородский государственный университет им. Н.И. Лобачевского В.П. Гергель ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОПРОЦЕССОР- НЫХ МНОГОЯДЕРНЫХ

ЛК 1. Моделирование. 1. Основные понятия. 2 Принципы моделирования. 3 Свойства моделей 4 Классификация методов моделирования. 5. Математическое моделирование 1. ОСНОВНЫЕ ПОНЯТИЯ. Моделирование замещение

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Новосибирский государственный университет» (НГУ) Факультет информационных технологий

Нижегородский государственный университет им. Н.И. Лобачевского Научно исследовательский университет Создание учебной библиотеки параллельных методов Parlib Выполнили: Козинов Е.А. Кутлаев М.В. Осокин

УДК 681.3.06 ПРОЕКТИРОВАНИЕ СТРУКТУРЫ ЛОКАЛЬНОЙ СЕТИ ДЛЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ А.В. Погребной, Д.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected]

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА ЦИКЛИЧЕСКОЙ ПРОГОНКИ Головашкин Д.Л., Филатов М. В. Институт систем обработки изображений РАН Самарский государственный аэрокосмический университет Аннотация Работа посвящена

УДК 519.856; 519.854; 519.85 СТАТИСТИЧЕСКИЙ ПОИСК СТРУКТУР ИНФОРМАЦИОННО- ВЫЧИСЛИТЕЛЬНОЙ СЕТИ В.В. Малыгин Исследованы свойства сходимости функции оценки структуры информационно вычислительной сети. На

Построение рекурсивно-параллельных алгоритмов решения задач вычислительной геометрии на основе стратегии «распределяй и властвуй» В.Н. Терещенко В работе рассматривается один из подходов построения эффективных

12.1. Ввод-вывод по опросу готовности устройства Готовность или неготовность внешнего устройства к вводу-выводу проверяется в регистре состояния внешнего устройства Для программно-управляемого ввода/вывода

ТАКСОНОМИЯ ФЛИННА Кириллова Юлия 6057/2 22.11.11 Таксономия Флинна общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. предложена в 1972 г. Майклом Флинном.

Лабораторная работа 4 Решение задачи Пуассона методом Якоби в трехмерной области Цель - практическое освоение методов распараллеливание алгоритмов задач, решаемых сеточными методами на примере решения

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

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

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

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

1. Взаимодействие через разделяемую память (например, в Java или C#). Данный вид параллельного программирования обычно требует какой-то формы захвата управления для координации потоков между собой.

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

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

1. OpenMP используется в параллельных системах с общей памятью (например, современные компьютеры с многоядерными процессорами);

2. MPI (Message Passing Interface) является стандартом систем передачи сообщений между параллельно исполняемыми процессами, используется при разработке программ для суперкомпьютеров;

3. POSIX Threads является стандартом реализации потоков выполнения;

4. Операционная система Windows имеет встроенную поддержку многопоточных приложений для C++ на уровне API;

5. PVM (Parallel Virtual Machine) позволяет объединять разнородные связанные сетью компьютеры в общий вычислительный ресурс.

Системы на базе нескольких компьютеров относят к классу систем для распределенных вычислений. Подобные решения используются довольно давно. Наиболее яркий пример технологии распределенных вычислений - MPI (Message Passing Interface - интерфейс передачи сообщений). MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для огромнейшего числа компьютерных платформ. MPI предоставляет программисту единый механизм взаимодействия ветвей внутри параллельного приложения независимо от машинной архитектуры (однопроцессорные/многопроцессорные с общей/раздельной памятью), взаимного расположения ветвей (на одном процессоре или на разных).

Так как MPI предназначен в первую очередь для систем с раздельной памятью, то использование его для организации параллельного процесса в системе с общей памятью является крайне сложным нецелесообразным. Тем не менее, ничего не мешает делать MPI-решения для одной машины.

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

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

OpenMP (Open Multi-Processing) - это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью.

Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB).

Первая версия появилась в 1997 году, предназначалась для языка Fortran. Для С/С++ версия разработана в 1998 году. В 2008 году вышла версия OpenMP 3.0. Интерфейс OpenMP стал одной из наиболее популярных технологий параллельного программирования. OpenMP успешно используется как при программировании суперкомпьютерных систем с большим количеством процессоров, так и в настольных пользовательских системах или, например, в Xbox 360.

OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков).

Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка - прагм. Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой: !$OMP PARALLEL PRIVATE(N)

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

Ключевыми элементами OpenMP являются

1. конструкции для создания потоков (директива parallel);

2. конструкции распределения работы между потоками (директивы DO/for и section);

3. конструкции для управления работой с данными (выражения shared и private для определения класса памяти переменных);

4. конструкции для синхронизации потоков (директивы critical, atomic и barrier);

5. процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num);

6. переменные окружения (например, OMP_NUM_THREADS).

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

Число потоков в группе, выполняющихся параллельно, можно контролировать несколькими способами. Один из них - использование переменной окружения OMP_NUM_THREADS. Другой способ - вызов процедуры omp_set_num_threads(). Еще один способ - использование выражения num_threads в сочетании с директивой parallel.

В этой программе два массива (a и b) складываются параллельно десятью потоками.

#include

int main(int argc, char *argv)

float a[N], b[N], c[N];

omp_set_dynamic(0); // запретить библиотеке openmp менять число потоков во время исполнения

omp_set_num_threads(10); // установить число потоков в 10

// инициализируем массивы

for (I = 0; I < N; i++)

// вычисляем сумму массивов

#pragma omp parallel shared(a, b, c) private(i)

for (I = 0; I < N; i++)

c[i] = a[i] + b[i];

printf (“%f\n”, c);

Эту программу можно скомпилировать, используя gcc-4.4 и более новые с флагом –fopenmp. Очевидно, если убрать подключение заголовочного файла omp.h, а также вызовы функции настроки OpenMP, программу возможно скомпилировать на любом компиляторе С как обычную последовательную программу.

OpenMP поддерживается многими современными компиляторами:

1. Компиляторы Sun Studio поддерживают официальную спецификацию - OpenMP 2.5 - с улучшенной производительностью под ОС Solaris; поддержка Linux запланирована на следующий релиз.

2. Visual C++ 2005 и выше поддерживает OpenMP в редакциях Professional и Team System.

3. GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.

4. Intel C++ Compiler, включая версию Intel Cluster OpenMP для программирования в системах с распределённой памятью.

Message Passing Interface (MPI, интерфейс передачи сообщений) - программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Разработан Уильямом Гроуппом, Эвином Ласком (англ.) и другими.

MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для большого числа компьютерных платформ. Используется при разработке программ для кластеров и суперкомпьютеров. Основным средством коммуникации между процессами в MPI является передача сообщений друг другу. Стандартизацией MPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который должен поддерживаться как на платформе, так и в приложениях пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.

В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затраты на передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью (многоядерные с общим ЭШем). Обе технологии могут использоваться совместно, дабы оптимально использовать в кластере многоядерные системы.

Первая версия MPI разрабатывалась в 1993-1994 году, и MPI 1 вышла в 1994.

Большинство современных реализаций MPI поддерживают версию 1.1. Стандарт MPI версии 2.0 поддерживается большинством современных реализаций, однако некоторые функции могут быть реализованы не до конца.

передача и получение сообщений между отдельными процессами;

коллективные взаимодействия процессов;

взаимодействия в группах процессов;

реализация топологий процессов;

динамическое порождение процессов и управление процессами;

односторонние коммуникации (Get/Put);

параллельный ввод и вывод;

расширенные коллективные операции (процессы могут выполнять коллективные операции не только внутри одного коммуникатора, но и в рамках нескольких коммуникаторов).

Версия MPI 2.1 вышла в начале сентября 2008 года.

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

1. отправитель - ранг (номер в группе) отправителя сообщения;

2. получатель - ранг получателя;

3. признак - может использоваться для разделения различных видов сообщений;

4. коммуникатор - код группы процессов.

Операции приёма и передачи могут быть блокирующимися и не блокирующимися. Для не блокирующихся операций определены функции проверки готовности и ожидания выполнения операции.

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

Ниже приведён пример программы вычисления числа π на языке C с использованием MPI:

// Подключение необходимых заголовков

#include

// Подключение заголовочного файла MPI

#include «mpi.h»

// Функция для промежуточных вычислений

double f(double a)

return (4.0 / (1.0+ a*a));

// Главная функция программы

int main(int argc, char **argv)

// Объявление переменных

int done = 0, n, myid, numprocs, I;

double PI25DT = 3.141592653589793238462643;

double mypi, pi, h, sum, x;

double startwtime = 0.0, endwtime;

char processor_name;

// Инициализация подсистемы MPI

MPI_Init(&argc, &argv);

// Получить размер коммуникатора MPI_COMM_WORLD

// (общее число процессов в рамках задачи)

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

// Получить номер текущего процесса в рамках

// коммуникатора MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(processor_name,&namelen);

// Вывод номера потока в общем пуле

fprintf(stdout, “Process %d of %d is on %s\n”, myid,numprocs,processor_name);

// количество интервалов

fprintf(stdout, “Enter the number of intervals: (0 quits) “);

if(scanf(“%d”,&n) != 1)

fprintf(stdout, “No number entered; quitting\n”);

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1.0 / (double) n;

// Обсчитывание точки, закрепленной за процессом

for(I = myid + 1 ; (I <= n) ; I += numprocs)

x = h * ((double)I – 0.5);

// Сброс результатов со всех процессов и сложение

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

// Если это главный процесс, вывод полученного результата

printf(“PI is approximately %.16f, Error is %.16f\n”, pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf(“wall clock time = %f\n”, endwtime-startwtime);

// Освобождение подсистемы MPI

Наиболее распространенными реализациями MPI на сегодняшний день являются:

MPICH - самая распространённая бесплатная реализация, работает на UNIX-системах и Windows NT

LAM/MPI - ещё одна бесплатная реализация MPI. Поддерживает гетерогенные конфигурации, LAM (http://www.lam-mpi.org) поддерживает гетерогенные конфигурации, пакет Globus и удовлетворяет IMPI (Interoperable MPI).

Поддерживаются различные коммуникационные системы (в том числе Myrinet).

WMPI - реализация MPI для Windows

MPI/PRO for Windows NT - коммерческая реализация для Windows NT

Intel MPI - коммерческая реализация для Windows / Linux

Microsoft MPI входит в состав Compute Cluster Pack SDK. Основан на MPICH2, но включает дополнительные средства управления заданиями. Поддерживается спецификация MPI-2.

HP-MPI - коммерческая реализация от HP

SGI MPT - платная библиотека MPI от SGI

Mvapich - бесплатная реализация MPI для Infiniband

Open MPI - бесплатная реализация MPI, наследник LAM/MPI

Oracle HPC ClusterTools - бесплатная реализация для Solaris SPARC/x86 и Linux на основе Open MPI

MPJ - MPI for Java

POSIX Threads - стандарт POSIX реализации потоков выполнения, определяющий API для создания и управления ими.

Библиотеки, реализующие этот стандарт (и функции этого стандарта), обычно называются Pthreads (функции имеют приставку «pthread_»). Хотя наиболее известны варианты для Unix-подобных операционных систем, таких как Linux или Solaris, но существует и реализация для Microsoft Windows (Pthreads-w32)

Pthreads определяет набор типов и функций на языке программирования Си. Заголовочный файл - pthread.h.

Типы данных:

1. pthread_t – дескриптор потока;

2. pthread_attr_t – перечень атрибутов потока.

Функции управления потоками:

1. pthread_create() – создание потока;

2. pthread_exit() – завершение потока (должна вызываться функцией потока при завершении);

3. pthread_cancel() – отмена потока;

4. pthread_join() – заблокировать выполнение потока до прекращения другого потока, указанного в вызове функции;

5. pthread_detach() – освободить ресурсы занимаемые потоком (если поток выполняется, то освобождение ресурсов произойдёт после его завершения);

6. pthread_attr_init() – инициализировать структуру атрибутов потока;

7. pthread_attr_setdetachstate() – указать системе, что после завершения потока она может автоматически освободить ресурсы, занимаемые потоком;

8. pthread_attr_destroy() – освободить память от структуры атрибутов потока (уничтожить дескриптор).

Функции синхронизации потоков:

2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();

3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().

Пример использования потоков на языке C:

#include

static void wait_thread(void)

time_t start_time = time(NULL);

while (time(NULL) == start_time)

/* do nothing except chew CPU slices for up to one second. */

static void *thread_func(void *vptr_args)

for (I = 0; I < 20; i++)

fputs(“ b\n”, stderr);

pthread_t thread;

if (pthread_create(&thread, NULL, thread_func, NULL) != 0)

return EXIT_FAILURE;

for (I = 0; I < 20; i++)

if (pthread_join(thread, NULL) != 0)

return EXIT_FAILURE;

return EXIT_SUCCESS;

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

Программа на C создает один новый поток для печати "b", а основной поток печатает "a". Основной поток (после печати "aaaaa….") ждёт завершения дочернего потока.

Контрольные вопросы

Что такое параллельная программа?
В чем отличие между процессом и потоком выполнения?
Может ли программа создать 5 потоков при работе на четырехядерном процессоре?
Каковы особенности параллельных программ с разделяемой памятью?
Какие существуют программные средства для разработки параллельных программ?
Почему большое распространение при создании программ для ПК получил именно OpenMP, а не, например, MPI?

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Южно-Российский государственный технический университет

(Новочеркасский политехнический институт)

Шахтинский институт (филиал) ЮРГТУ (НПИ)

ЛЕКЦИИ ПО ДИСЦИПЛИНЕ

«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ»

Шахты- 2010

Введение

Основные понятия

1. Общие вопросы решения ";больших задач";

1.1 Современные задачи науки и техники, требующие для решения суперкомпьютеры

1.2.2 Абстрактные модели параллельных вычислений

1.2.3 Способы параллельной обработки данных, погрешность вычислений

1.3 Понятие параллельного процесса и гранулы распараллеливания

1.4 Взаимодействие параллельных процессов, синхронизация процессов

1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля)

2. Принципы построения многопроцессорных вычислительных систем

2.1 Архитектура многопроцессорных вычислительных систем

2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью

2.3 Классификация параллельных вычислительных систем

2.4 Многопроцессорные вычислительные системы c распределенной памятью

2.4.1 Массивно-параллельные суперкомпьютеры серии Cry T3

2.4.2 Кластерные системы класса BEOWULF

Заключение

Список литературы

Введение

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

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

С некоторых пор повышение быстродействия компьютеров традиционной (именуемой ";фон Неймановской";) архитектуры стало чрезмерно дорого вследствие технологических ограничений при производстве процессоров, поэтому разработчики обратили внимание на иной путь повышения производительности – объединение электронно-вычислительных машин в многопроцессорные вычислительные системы. При этом отдельные фрагменты программы параллельно (и одновременно) выполняются на различных процессорах, обмениваясь информацией посредством внутренней компьютерной сети.

Идея объединения электронно-вычислительных машин с целью повышения, как производительности, так и надежности известны с конца пятидесятых годов.

Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных комплексов; известны системы такого рода, объединяющие вычислительные мощности тысяч отдельных процессоров. Следующим этапом являются попытки объединить миллионы разнородных компьютеров планеты в единый вычислительный комплекс с огромной производительностью посредством сети Internet. На сегодняшний день применение параллельных вычислительных систем является стратегическим направлением развития вычислительной техники. Развитие ";железа"; с необходимостью подкрепляются совершенствованием алгоритмической и программной компонент – технологий параллельного программирования.

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

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

Рассмотрим два основных вопроса:

1. Многопроцессорные вычислительные системы – (массивно-параллельные суперкомпьютеры) Cray T3D(E) с количеством процессоров от 40 до 2176. Это суперкомпьютеры с распределенной памятью на RISC-процессорах типа Alpha21164A, с топологией коммуникационной сети – трехмерный тор, операционной системой UNIX с микроядром и трансляторами для языков FORTRAN, HPF, C/C++. Поддерживаемые модели программирования: MPI, PVM, HPF.

2. Беовульф-кластеры рабочих станций. Кластеры рабочих станций – совокупность рабочих станций, соединенных в локальную сеть. Кластер – вычислительная система с распределенной памятью и распределенным управлением. Кластерная система может обладать производительностью, сравнимой с производительностью суперкомпьютеров. Кластеры рабочих станций обычно называют Беовульф-кластерами (Beowulf cluster – по одноименному проекту), связанны локальной сетью Ethernet и используют операционную систему Linux.

Основные понятия

Наиболее распространенной технологией программирования для кластерных систем и параллельных компьютеров с распределенной памятью в настоящее время является технология MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии – Message Passing Interface (интерфейс передачи сообщений). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. MPI поддерживает работу с языками Фортран и Си. Полная версия интерфейса содержит описание более 125 процедур и функций.

Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты, гораздо чаще используют SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с так называемыми ";нитями";.

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

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

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

Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения – коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу. Коммуникаторы имеют в языке Фортран тип integer (в языке Си – предопределенный тип MPI Comm).

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

Процессоры с сокращенным набором команд (RISC). В основе RISC-архитектуры (RISC – Reduced Instruction Set Computer) процессора лежит идея увеличения скорости его работы за счет упрощения набора команд.

Исследования показали, что 33% команд типичной программы составляют пересылки данных, 20% – условные ветвления и еще 16% – арифметические и логические операции. В подавляющем большинстве команд вычисление адреса может быть выполнено быстро, за один цикл. Более сложные режимы адресации используются примерно в 18% случаев. Около 75% операндов являются скалярными, то есть переменными целого, вещественного, символьного типа и т. д., а остальные являются массивами и структурами. 80% скалярных переменных – локальные, а 90% структурных являются глобальными. Таким образом, большинство операндов – это локальные операнды скалярных типов. Они могут храниться в регистрах.

Согласно статистике, большая часть времени тратится на обработку операторов ";вызов подпрограммы"; и ";возврат из подпрограммы";. При компиляции эти операторы порождают длинные последовательности машинных команд с большим числом обращений к памяти, поэтому даже если доля этих операторов составляет всего 15%, они потребляют основную часть процессорного времени. Только около 1% подпрограмм имеют более шести параметров, а около 7% подпрограмм содержат более шести локальных переменных.

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

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

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

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

1. Общие вопросы решения ";больших задач";

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

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

1.1. Современные задачи науки и техники, требующие

для решения суперкомпьютеры

Достаточно часто приходится сталкиваться с такими задачами, которые, представляя немалую ценность для общества, не могут быть решены с помощью относительно медленных компьютеров офисного или домашнего класса. Единственная надежда в этом случае возлагается на компьютеры с большим быстродействием, которые принято называть суперкомпьютерами. Только машины такого класса могут справиться с обработкой больших объемов информации. Это могут быть, например, статистические данные или результаты метеорологических наблюдений, финансовая информация. Иногда скорость обработки имеет решающее значение. В качестве примера можно привести составление прогноза погоды и моделирование климатических изменений. Чем раньше предсказано стихийное бедствие, тем больше возможностей подготовиться к нему. Важной задачей является моделирование лекарственных средств, расшифровка генома человека, томография, в том числе и медицинская, разведка месторождений нефти и газа. Примеров можно привести много.

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

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

Предсказания погоды, климата и глобальных изменений в атмосфере

Науки о материалах

Построение полупроводниковых приборов

Сверхпроводимость

Разработка фармацевтических препаратов

Генетика человека

Астрономия

Транспортные задачи большой размерности

Гидро и газодинамика

Управляемый термоядерный синтез

Разведка нефти и газа

Вычислительные задачи наук о мировом океане

Распознавание и синтез речи, распознавание изображений

Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,6×106 (сетка с шагом 10 по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,6×107 числами. При шаге дискретизации по времени 10 минут за моделируемый промежуток времени необходимо определить 5×104 ансамблей (то есть 1014 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 102÷103 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 1016÷1017.

Суперкомпьютер с производительностью 1012 оп/сек при идеальном случае (полная загруженность и эффективная алгоритмизация) будет выполнять такой эксперимент в течение нескольких часов; для проведения полного процесса моделирования необходима многократная (десятки/сотни раз) прогонка программы.

Проблема супервычислений столь важна, что многие государства курируют работы в области суперкомпьютерных технологий.

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

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

Недостатком метода оценки пиковой производительности как числа выполняемых компьютером команд в единицу времени (MIPS, Million Instruction Per Second) дает только самое общее представление о быстродействии, так как не учитывает специфику конкретных программ (трудно предсказуемо, в какое число и каких именно инструкций процессора отобразится пользовательская программа).

Необходимо отметить, что существуют аргументы против широкого практического применения параллельных вычислений:

Параллельные вычислительные системы чрезмерно дороги. По подтверждаемому практикой закону Гроша, производительность компьютера растет пропорционально квадрату его стоимости; в результате гораздо выгоднее получить требуемую вычислительную мощность приобретением одного производительного процессора, чем использование нескольких менее быстродействующих процессоров.

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

При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского (Marvin Minsky) достигаемое при использовании параллельной системы ускорение вычислений пропорционально двоичному логарифму от числа процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10).

Контраргумент. Приведенная оценка ускорения верна для распараллеливания определенных алгоритмов. Однако существует большое количество задач, при параллельном решении которых достигается близкое к 100% использованию всех имеющихся процессоров параллельной вычислительной системы.

Последовательные компьютеры постоянно совершенствуются. По широко известному закону Мура сложность последовательных микропроцессоров возрастает вдвое каждые 18 месяцев, поэтому необходимая производительность может быть достигнута и на ";обычных"; последовательных компьютерах.

Контраргумент. Аналогичное развитие свойственно и параллельным системам.

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

Контраргумент. При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные ";устоявшиеся"; способы обеспечения параллелизма. Инвариантность создаваемого программного обеспечения обеспечивается при помощи использования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.). PVM и MPI используются в суперкомпьютерах Cray-T3.

За десятилетия эксплуатации последовательных электронно-вычислительных машинах накоплено огромное программное обеспечение, ориентировано на последовательные электронно-вычислительные машины; переработка его для параллельных компьютеров практически нереальна.

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

Существует ограничение на ускорение вычисление при параллельной реализации алгоритма по сравнению с последовательной.

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

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

1.2 Параллельная обработка данных

1.2.1 Принципиальная возможность параллельной обработки

Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.

Можно построить m процессоров, которые при одновременной работе выдают нужный результат за один-единственный такт работы вычислителя.

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

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

Зако́н Амдала - иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей.

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

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

Пусть процессоры однородны по производительности. Т 0 – время выполнения последовательной части параллельного алгоритма, например, генерирование начальных данных и обработка полученного при решении задачи результата. Т 1 , Т 2 , ... Т p – время последовательной работы, выполняемой каждым процессором без взаимодействия между собой. Тогда время выполнения задачи на p процессорах определяется неравенством:

где i=1, 2, ... p. Равенство получается, когда Тi равны между собой . Отсюда, подставляя
T seq – T 0 , где T seq есть время выполнения задачи на одном процессоре , получаем T par ≥ T 0
.

Делим на T seq и, обозначая через f = T 0 / T seq - долю (fraction) последовательного участка в общем объеме вычислений, получим:
.(1.1)

Ускорение (Speedup ) – это отношение времени выполнения задачи в последовательном режиме (на 1 процессоре), ко времени выполнения задачи в параллельном режиме (на p процессорах).

, используя неравенство (1.1), получим
(1.2)

Отсюда видно, что при f=0 и равенстве T i получим S=p, при f >0 и p → ∞, получим
. Данная функция является монотонно-возрастающей по p и, значит, достигает максимума на бесконечности. Следовательно, ни на каком числе процессоров ускорение счета не может превысить обратной величины доли последовательного участка .

Рассматривая закон Амдаля, мы предполагали, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи . Однако для большого ряда задач доля f=f(n) является убывающей функцией от n , и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет уменьшения доли последовательной работы, выполняемой каждым процессором. Иначе говоря, ускорение Sp= Sp(n) является возрастающей функцией от параметра n (данное утверждение часто называют эффектом Амдаля).

Эффективность распараллеливания- это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

(1.2)

Т.е. если ускорение S = p (максимально возможное на p процессорной машине), то эффективность распараллеливания задачи равна 100%. Используя закон Амдаля получаем верхнюю оценку эффективности:

E ≤ 100%
(1.3)

Например, E ≤ 52.25% для p=100 и f=0.01 и E ≤ 9.1% для p=1000 и f=0.01.

Вывод . При малой долипоследовательной работыувеличение количества процессов приводит к ухудшению параллельной эффективности (причина – с ростом процессов растет количество обменов). Например, если f=0.01 (1%), то Е<100 и использовать для решения параллельной задачи более 100 процессоров нецелесообразно. Для повышения эффективности , как правило, не распараллеливают управляющие части программы или небольшие участки вычислений, которые требуют интенсивной синхронизации процессов.

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

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

Масштабируемость – этопропорциональное увеличение объема задачи с увеличением числа используемых для ее решения процессоров. Наличие масштабируемости задач является важным свойством тестовых систем оценки производительности параллельных вычислительных систем.

Плохая масштабируемость параллельного приложения на MPP-системе может быть вызвана а) ростом затрат на коммуникации при увеличении числа используемых процессоров; б) неравномерностью распределения вычислительной нагрузки между процессорами.

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

Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма T 0 = P *Tp − T 1 , где T 1 - время выполнения последовательного алгоритма задачи, T p - время выполнения алгоритма задачи на P процессорах.

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

Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:

Tp = (T 1 + T 0 )/P , Sp = T 1 / Tp = (P* T 1 )/(T 1 + T 0 )

Тогда эффективность использования процессоров можно выразить как

E P = Sp/P = T 1 / (T 1 + T 0 ) = 1/(1+ T 1 /T 0 )

Тогда, если сложность решаемой задачи является фиксированной (T 1 =const ), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T 0 . При фиксированном числе процессоров, эффективность можно улучшить путем повышения сложности решаемой задачи T 1 , поскольку предполагается, что при увеличении сложности накладные расходы T 0 растут медленнее, чем объем вычислений T 1 .

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

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

2. Топология сети передачи данных. Примеры элементарных топологий, основные характеристики. Алгоритмы маршрутизации и методы передачи данных.

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

Примеры топологий сети передачи данных

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

Полный граф (completely-connected graph or clique) – система, в которой между любой парой процессоров существует прямая линия связи, поэтому данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров.

Линейка (linear array or farm) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений).

Кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки.

Звезда (star) – система, в которой все процессоры имеют линии связи с некоторым управляющим процессором; данная топология является эффективной, например, при организации централизованных схем параллельных вычислений.

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

Гиперкуб (hypercube) – данная топология представляет частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора; данный вариант организации сети передачи данных достаточно широко распространен в практике и характеризуется следующим рядом отличительных признаков:

а) два процессора имеют соединение, если двоичные представления их номеров имеют

только одну различающуюся позицию;

б) N-мерный гиперкуб может быть разделен на два (N-1)-мерных гиперкуба (всего возможно N различных разбиений);

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

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

Плаксин М.А.

Национальный исследовательский университет Высшая школа экономики (Пермский филиал), г.Пермь, к.ф.м.н., доцент кафедры информационных технологи в бизнесе, mapl @ list. ru

«СУПЕРКОМПЬЮТЕРЫ» VS «ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ». «ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ» VS «СОВМЕСТНАЯ ДЕЯТЕЛЬНОСТЬ». КАК ИЗУЧАТЬ ТЕМУ «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ» В СРЕДНЕЙ ШКОЛЕ?

КЛЮЧЕВЫЕ СЛОВА

Информатика, параллельное программирование, параллельные вычисления, параллельные алгоритмы, суперкомпьютеры, начальная школа, средняя школа, ТРИЗформашка.

АННОТАЦИЯ

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

Современный этап развития computer science связан с массовым распространением параллелизма вычислений на всех уровнях (многомашинные кластеры, многопроцессорные ЭВМ, многоядерные процессоры).

Массовое распространение параллелизма влечет серьезные последствия, которые еще предстоит выявить и проанализировать. Начнем с перечисления некоторых теоретических проблем.

Современная теория алгоритмов создавалась в расчете на понятие последовательного алгоритма. Каким образом отразится на понятии алгоритма отказ от требования последовательности выполнения шагов?

По крайней мере последние 20 лет понятие «алгоритм» вводилось в школе в неразрывной связке с понятием «исполнитель». Для последовательного алгоритма это естественно. Как быть с алгоритмом параллельным? Его выполняет один исполнитель или группа исполнителей? Для конкретности в качестве примера рассмотрим компьютерную обучающую программу «Танковый экипаж» . В этой программе от учащегося требуется запрограммировать действия экипажа танка, состоящего из трех человек: наводчика, водителя и заряжающего. Каждый из них имеет свою систему команд. Для того, чтобы выполнить боевую задачу (поразить все цели), все члены экипажа должны действовать согласованно. Пример игрового поля программы «Танковый экипаж» см. на рис.1.

Вопрос: надо ли рассматривать этих трех действующих лиц как независимых исполнителей или как три составные части (устройства) одного сложного исполнителя? Для экипажа танка более естественным представляется второй вариант, поскольку ни один персонаж сам по себе выполнить задание не в состоянии. Но как быть, если игра будет усложнена, и боевая задача будет поставлена сразу для двух танков? Для трех танков? Трех членов одного экипажа вполне можно рассматривать как три части одного исполнителя. Но каждый экипаж очевидно является самостоятельным исполнителем. Значит, параллельный алгоритм для нескольких танков будет выполняться сразу группой исполнителей. Получается, что для параллельного алгоритма рассматривать надо обе возможности: выполнение параллельных действий одним исполнителем и группой исполнителей. В случае танкового экипажа границу провести просто. Исполнитель - это тот, кто в состоянии решить поставленную задачу. Этот исполнитель может состоять из нескольких компонент, каждая из которых выполняет некую часть задания, но не может самостоятельно без помощи других компонент выполнить задание целиком. Но всегда ли разделение «целых исполнителей» и частей сложного исполнителя будет также просто - сейчас сказать нельзя.

Файл 1*ра Окне О программе

Вьполиеть все

Bbno.n«fTb до выделенной строки

Вернуть в начальное попаже**»

быпопнлтъ пошагово (после выполнения «.ладом команды несйкоа^« будет наждтъ кнопки гВ ыголг«п-ъ следующий uwr")

Ё ЬГВД iTHWTt. спеауюшнй шаг

Осглноснть пошаговое

Рис.1. Фрагмент игрового поля программы «Танковый экипаж»

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

Нужно договориться о термине для обозначения группы совместно действующих исполнителей. Термин «команда» не годится, ассоциируется с «системой команд исполнителя» и с «командами центрального процессора». «Коллектив исполнителей»? «Бригада исполнителей»?

Ш. Алгоритм

н Наезд1«; Водитель Заряжающий

1 Пмер^ть орун* по «освой сгклл V Стоп V Зарядить 1

г Пци V Стоп V Зарядить 2

3 Опт! V Повернуться прет« часовой стрелки на 90 градусов V Зарядить 1 V

Л V В перш V Зарядить? V

5 Огонь! V Стоп V Зарядить 1

Í П^чм V Ст*п V Зарясь? V

7 Огонь! V Стоп V Зарядить 1 V

3 Па^ V Повернуться па часовой стрелке на 45 градусов V Зарядить 2 V

S Пауя V Вперйа V Пауза V

10 Пвдэа V Вперед V Пауза ¿d

11 Плрл V Вперед V Пауза V

12 Паум V Повернуться по часовой стрелке на 45 градусов V Пауза V

13 Падм V Вперед V Пауза V

14 V n&stpHyTbtft то чксевн стрелке на 45 градус« V Зар^а^ьТ V

Рис.2. Фрагмент программы для «Танкового экипажа» (пример линеек команд) Требует доработки традиционное понятие «системы команд исполнителя» (СКИ) и само понятие команды. Если мы считаем, что три члена танкового экипажа образуют единого исполнителя, то что считать СКИ этого исполнителя? И что считать командой? Или оставить понятие СКИ для каждого персонажа? То есть это уже не система команд ИСПОЛНИТЕЛЯ, а система команд одной из компонент исполнителя (для которой еще нет названия)?

Понятие команды удобно расширить до «линейки команд». Пример линеек команд танкового экипажа см. на рис.2. Однако понятие «линейки команд» хорошо работает только для линейных алгоритмов. В остальных случаях линейки формируются динамически. Изобразить их в виде наглядной таблицы невозможно.

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

Отдельный вопрос - методы распараллеливания уже существующих последовательных алгоритмов.

До недавнего времени параллельное программирование было уделом небольшого числа высоко квалифицированных системных программистов. Сегодня оно становится частью профессиональной компетенции. Но технология параллельного программирования существенно отличается от традиционного последовательного. В подтверждение этого утверждения вслед за Л.Л. Босовой процитируем крупнейшего российского специалиста в области параллельных вычислений В.В. Воеводина :

«... Освоение вычислительной техники параллельной архитектуры... молодыми специалистами идет с большими трудностями. На наш взгляд, это связано с тем, что знакомство с параллельными вычислениями, как и образование в этой области в целом, начинается не с того, с чего надо бы начинать. К тому же то, с чего надо начинать, не рассказывается ни в каких курсах вообще. Возможность быстрого решения задач на вычислительной технике параллельной архитектуры вынуждает пользователей изменять весь привычный стиль взаимодействия с компьютерами. По сравнению, например, с персональными компьютерами и рабочими станциями меняется практически все: применяются другие языки программирования, видоизменяется большинство алгоритмов, от пользователей требуется предоставление многочисленных нестандартных и трудно добываемых характеристик решаемых задач, интерфейс перестает быть дружественным и т.п. Важным является то обстоятельство, что неполнота учета новых условий работы может в значительной мере снизить эффективность использования новой и, к тому же, достаточно дорогой техники.»

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

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

Тридцать лет назад начинающаяся массовая компьютеризация производства потребовала увеличения уровня компьютерной грамотности населения. Это привело к введению в школьную программу в 1985 г. курса информатики. Но курс информатики в советском (затем в российском) исполнении не сводился к «кнопочной информатике» - к освоению технологии работы с пакетами прикладными программ и компьютерными играми. Он начал изменять стиль мышления подрастающего поколения. В первую очередь это касалось алгоритмичности, точности, строгости. Затем курс информатики вобрал в себя элементы логики и системного анализа. Впоследствии все это значительно упростило распространение так необходимого в XXI в. проектного подхода. Сейчас речь идет о том, что в течение следующего десятилетия параллельные алгоритмы должны стать

элементом общей культуры мышления. Вопрос: каким образом скажется на мышлении следующего поколения освоение понятия параллельного алгоритма, к чему приведет перестройка сознания «на параллельный лад»?

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

Исторически первая попытка включения тематики параллельных вычислений в школьный курс информатики была сделана еще двадцать лет назад. Двадцать лет назад в курсе под названием «Алгоритмика» был описан исполнитель «Директор строительства», который командовал параллельными действиями нескольких бригад, строящих сооружение из блоков прямоугольной и треугольной формы. Более того, для этого исполнителя была создана программная реализация. Увы! Эта замечательная методическая разработка в середине 90-х оказалась не востребована. Она почти на двадцать лет опередила свое время!

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

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

Организационную поддержку со стороны суперкомпьютерного сообщества. Каждое лето на факультете вычислительной математики и кибернетики МГУ проводится Летняя Суперкомпьютерная Академия . И каждое лето в рамках этой Академии организуется школьный трек для учителей информатики. Обучение проводится бесплатно. Иногородние слушатели обеспечиваются жильем на весьма льготных условиях. На конференции Russian Supercomputing Days в сентябре 2015 г. была организована школьная секция и мастер-класс для учителей информатики. Последовательная организационная работа привела к выявлению и формированию группы учителей, заинтересованных в продвижении данной тематики;

Наличие яркого харизматичного лидера, каковым является Владимир Валентинович Воеводин - доктор физико-математических наук, профессор, член-корреспондент РАН, заместитель директора Научно-исследовательского вычислительного центра Московского государственного университета;

Интерес и поддержку (в том числе, материальную) со стороны российского представительства фирмы Интел и менеджера по стратегическому развитию фирмы Интел Игоря Олеговича Одинцова.

Недостаток «суперкомпьютерного» подхода заключается в зауживании тематики параллельных вычислений. Сами суперкомпьютеры школьникам, как правило, недоступны (разве что в крупных городах на них можно поглазеть на экскурсии). Задачи, на решение которых они нацелены, для школьников слишком сложны и, в большинстве случаев, не имеют непосредственной практической значимости и не представляют практического интереса.

Естественным расширением суперкомпьютерной тематики является изучение параллельного программирования. В настоящее время для выполнения параллельных программ совсем не обязательно иметь суперЭВМ. Достаточно многоядерного процессора или видеокарты с набором графических ускорителей. А это доступно уже почти всем. Из работ в этом направлении отметим кандидатскую диссертацию М.А. Соколовской по методике обучения будущих учителей информатики основам параллельного программирования и опыт Е.Ю. Киселевой по освоению школьниками технологии CUDA .

По мнению автора данной статьи сосредоточение внимания на спуерЭВМ и параллельном программировании существенно обедняет и усложняет тему параллельных вычислений, отвлекает учащихся от множества важных и доступных вопросов. Целью темы «параллельные

вычисления» в средней школе является не обучение «реальному» параллельному программированию (изучение соответствующих языковых конструкций, языков программирования и технологий), а ознакомление учащихся с соответствующим набором понятий и понимание особенностей параллельной работы. Мир вокруг и внутри нас представляет собой сложную параллельную систему. И эта система сама по себе дает массу материала для освоения понятий и механизмов параллелизма. Никакие сложные искусственные конструкции типа технологий MPI и OpenMP для этого не нужны. Школьная информатика должна воспитать мышление, настроенное на «параллельный лад». А дальше университет пусть закладывает в это мышление профессиональные знания, умения, навыки. В школе акцентировать имеет смысл не знакомство с суперкомпьютерами и изучение параллельного программирования, а освоение механизмов «совместной деятельности», постоянно и широко используемых в жизни. В курсе предлагается отразить следующие вопросы:

1) Совместная работа нескольких исполнителей (копание канавы несколькими землекопами) и распараллеливание «внутри» одного исполнителя при наличии нескольких обрабатывающих устройств (читаю и ем яблоко). В computer science это будут многомашинный комплекс и многоядерный процессор.

2) Виды параллелизма: параллелизм истинный и псевдопараллелизм (один процессор выполняет частями несколько программ).

3) Исполнители однотипные (землекопы) и разнотипные (экипаж танка).

4) Работы однотипные и разнотипные.

5) Соотношение «исполнители - работы»: 1 исполнитель - 1 работа, 1 исполнитель - N работ (псевдопараллельное выполнение или истинный параллелизм при наличии нескольких обрабатывающих устройств для разных работ), N исполнителей - 1 работа, N исполнителей - N работ.

6) Согласование деятельности исполнителей. Виды согласования: по частям работы, по времени, по результатам деятельности, по ресурсам.

7) Ресурсы. Ресурсы разделяемые и неразделяемые, расходуемые и повторно используемые. Утилизация потребленных ресурсов («сборка мусора» в широком смысле).

8) Выполнение одной и той же работы одним исполнителем и группой исполнителей. Зависимость скорости работы от количества исполнителей. Зависимость стоимости работы от количества исполнителей. Нелинейный рост скорости работы при росте количества исполнителей. Критический путь. Оптимальное количество исполнителей. Оптимальная загрузка исполнителей. Оптимальный порядок действий. Балансировка нагрузки.

9) Конкуренция исполнителей за ресурсы. Блокировка. Клинч (тупик).

10) Механизмы согласования действий исполнителей.

11) Псевдопараллельное выполнение процессов на компьютере (разделение между исполнителями-процессами одного ресурса - процессора).

12) Пригодность алгоритмов к распараллеливанию. Возможная степень распараллеливания. Существование алгоритмов, не поддающихся распараллеливанию.

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

Материал должен быть продемонстрирован на примерах, не связанных с работой ЭВМ. Исполнители должны манипулировать материальными объектами.

Как можно большая часть обучения должна носить характер деловых (организационно-деятельностных) игр.

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

Работу над подготовкой методики изучения параллельных вычислений автор данной статьи начал в 2013 г. в ходе подготовки конкурса «ТРИЗформашка-2013» и продолжил в последующие годы .

(«ТРИЗформашка» - межрегиональный Интернет-конкурс по информатике, системному анализу и ТРИЗ. Проводится ежегодно во второй половине марта. Возраст участников - с I класса до IV курса. География - от Владивостока до Риги. Среднее число участников - 100 команд (300 чел.), максимальное - 202 команды (более 600 чел.). Сайт конкурса www. trizformashka . ru.) Тогда, в 2013 г. цель работы была сформулирована следующим образом:

1. В течение двух-трех лет подготовить описание исполнителей, набор игр и задач, связанных с параллельными вычислениями;

2. Предложить их (по частям, ежегодно) участникам конкурса;

3. Проанализировать их реакцию (оценить количество решавших, их возраст, успешность решения, типичные ошибки, обнаруженные неточности в формулировке задач и т.д.). Конкурс «ТРИЗформашка» оказался удобным инструментом отладки задач, поскольку

позволял получить реакцию всех возрастов (от I класса до IV курса), из различных регионов, из различных учебных заведений.

За прошедшие годы был подготовлен следующий набор методических инструментов и площадок для их апробации.

1. Задания на параллелизм, начиная с 2013 г., вошли в конкурс «ТРИЗформашка» (начиная с 2013 г., конкурс имеет подзаголовок «Параллельные вычисления»). Список типов заданий приведен ниже;

2. Подготовлена глава про параллелизм для новой версии учебника информатики для 4 класса . Материал прошел апробацию в 3-х и 4-х классах Лицея №10 г.Перми;

3. Разработана и с 2014 г. используется в конкурсе «ТРИЗформашка» компьютерная игра «Танковый экипаж» ;

4. Разработан и прошел апробацию ряд игр , в которых отражены следующие вопросы:

Согласование деятельности исполнителей. Различные виды согласования;

Выполнение одной и той же работы одним исполнителем и группой исполнителей. Зависимость скорости работы от количества исполнителей. Нелинейный рост скорости работы при росте количества исполнителей. Критический путь. Оптимальное количество исполнителей. Оптимальная загрузка исполнителей. Оптимальный порядок действий;

Ресурсы. Ресурсы разделяемые и неразделяемые;

Конкуренция исполнителей за ресурсы. Блокировка. Клинч (тупик). Были предложены и опробованы следующие типы задач :

1. Задачи на виды согласования. (Какие виды согласования существуют в школьной столовой?);

2. Игра «Танковый экипаж». Задание на построение параллельного алгоритма;

3. Исполнитель «Стройка» . Одновременно работающие бригады строят сооружение из горизонтальных и вертикальных балок. Задания включают в себя задания на исполнение указанного алгоритма, на разработку нового алгоритма, на поиск ошибок в заданном алгоритме, на исследование алгоритмов (сравнение сроков строительства по разным алгоритмам, сравнение стоимости строительства, оценка возможности сэкономить за счет перераспределения рабочей силы и др.);

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

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

6. Ярусно-параллельные формы. Планирование работ по разным критериям. Дано задание на работу, производительность работников, правила оплаты. Требуется определить количество работников, нужных, чтобы выполнить работу в заданное время, определить срок работы при заданном количестве работников, определить количество работников, нужное для минимизации стоимости работ;

7. Диаграммы Ганта. Описан текстом план работ по реконструкции цеха: продолжительность и взаимная последовательность действий, требуемые работники. Требуется определить срок сдачи объекта, изменение срока при тех или иных изменениях в рабочей силе, список работников, задействованных на конкретную дату.

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

На сегодня имеем в наличии следующие результаты:

1. Сформулирован подход с изучению темы «параллельные вычисления»: идти не от проблем computer science, а «от жизни», делать акцент на «совместной деятельности»;

2. Сформулирован перечень вопросов, которые предлагается отразить в начальном курсе параллельных вычислений;

3. Сформулированы некоторые классы задач. На основании накопленного опыта можно оценить, какого рода задачи стоит придумывать;

4. Подготовлен набор задач названных классов. Задачи прошли апробацию в конкурсах «ТРИЗформашка» за 2013, 2014, 2015 гг. и/или в начальной школе (на занятиях с учениками третьих-четвертых классов лицея №10 г.Перми);

5. Подготовлен набор деловых игр. Игры прошли апробацию в начальной школе и на ряде мероприятий для учителей. В частности, были представлены на школьном треке Летней Суперкомпьютерной Академии ВМК МГУ в 2014 г., на мастер-классе для учителей на Russian Supercomputing Days-2015, на нескольких других конференциях (в том числе, на конференции ИТ-0бразование-2015 ассоциации АПКИТ) и других мероприятиях для учителей информатики;

6. Подготовлен набор текстов про параллелизм для учебника IV класса. Тексты прошли апробацию в лицее №10 г.Перми;

7. Подготовлена компьютерная игра «Танковый экипаж». Игра прошла апробацию в конкурсах «ТРИЗформашка» 2014 и 2015;

8. Конкурс «ТРИЗформашка» оправдал себя в качестве апробационной площадки;

9. Сформулирована задача «провести рокировку» в процессе обучения алгоритмизации: учить сразу параллельному программированию, представляя последовательный алгоритм частью параллельного. Есть мысли о том, как можно реализовать эту идею. Есть возможность опробовать эти идея в течение текущего учебного года (на учащихся 4-х - 5-х классов);

10. Есть потребность, желание и возможность продолжать работу.

Литература

1. Алгоритмика: 5-7 классы: Учебник и задачник для общеобразоват. учебных заведений /А.К. Звонкин, А.Г. Кулаков, С.К. Ландо, А.Л. Семенов, А.Х. Шень. - М.: Дрофа, 1996.

2. Босова Л.Л. Параллельные алгоритмы в начальной и основной школе. //Информатика в школе. 2015, №2. С.24-27.

3. Воеводин В.В. Вычислительная математика и структура алгоритмов: 10 лекция о том, поему трудно решать задачи на вычислительных системах параллельной архитектуры и что надо знать дополнительно. чтобы успешно преодолевать эти трудности: учебник. М.: Изд-во МГУ 2010.

4. Гаврилова И.В. Первое путешествие в «параллельный мир». //Информатика в школе. 2015, №6. С.16-19.

5. Дитер М.Л., Плаксин М.А. Параллельные вычисления в школьной информатике. Игра «Стройка». //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. - Пермь, 2014. - С.258-261.

6. Иванова Н.Г., Плаксин М.А., Русакова О.Л. ТРИЗформашка. //Информатика. N05 Проверено 10.10.2015.

14. Плаксин М.А. Информатика: учебник для 4 класса: в 2 ч. /М.А.Плаксин, Н.Г.Иванова, О.Л.Русакова. - М.: БИНОМ. Лаборатория знаний, 2012.

15. Плаксин М.А. О методике начального знакомства с параллельными вычислениями в средней школе. //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. - Пермь, 2014. - С.256-258.

16. Плаксин М.А. Комплекс деловых игр для знакомства с параллельными вычислениями в начальной школе. //Преподавание информационных технологий в Российской Федерации: материалы Тринадцатой открытой Всероссийской конференции «ИТ-0бразование-2015» (г.Пермь, 14-15 мая 2015 г.). Пермский государственный национальный исследовательский университет, - Пермь, 2015. С.60-62.

17. Плаксин М.А., Иванова Н.Г., Русакова О.Л. Набор заданий для знакомства с параллельными вычислениями в конкурсе «ТРИЗформашка». //Преподавание информационных технологий в Российской Федерации: материалы Тринадцатой открытой Всероссийской конференции «ИТ-Образование-2015» (г.Пермь, 14-15 мая 2015 г.). Пермский государственный национальный исследовательский университет, - Пермь, 2015. С. 232-234.

18. Соколовская М.А. Методическая система обучения основам параллельного программирования будущих учителей информатики.: автореф. дис. ... канд. пед. наук, Красноярск, 2012.