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

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

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

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

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

Пусть процессоры однородны по производительности. Т 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 различных разбиений);

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

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

Текущая версия страницы пока не проверялась

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

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

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

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

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

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

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

Способы синхронизации параллельного взаимодействия

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

Типичные задачи, допускающие параллельные вычисления

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

Программные инструменты параллелизма

OpenMP - стандарт интерфейса приложений для параллельных систем с общей памятью.
POSIX Threads - стандарт реализации потоков (нитей) выполнения.
Windows API - многопоточные приложения для C++.
PVM (Parallel Virtual Machine) позволяет объединить разнородный (но связанный сетью) набор компьютеров в общий вычислительный ресурс.
MPI (Message Passing Interface) - стандарт систем передачи сообщений между параллельно исполняемыми процессами.

См. также

Напишите отзыв о статье "Параллельные вычисления"

Литература

Словарь по кибернетике / Под редакцией академика В. С. Михалевича . - 2-е. - Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. - 751 с. - (С48). - 50 000 экз. - ISBN 5-88500-008-5 .
. - IBM RedBook, 1999. - 238 с. (англ.)
Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. - СПб: БХВ-Петербург, 2002. - 608 с. - ISBN 5-94157-160-7 .
Оленев Н. Н. . - М .: ВЦ РАН, 2005. - 80 с. - ISBN 5201098320 .

Примечания

Ссылки

(англ.)
(англ.)

Параллельные вычисления

Общие положения

Уровни параллелизма

Поток выполнения

Теория

Элементы

Взаимодействие

Программирование

Компьютерная техника

API

Проблемы

Отрывок, характеризующий Параллельные вычисления

Дух войска – есть множитель на массу, дающий произведение силы. Определить и выразить значение духа войска, этого неизвестного множителя, есть задача науки.
Задача эта возможна только тогда, когда мы перестанем произвольно подставлять вместо значения всего неизвестного Х те условия, при которых проявляется сила, как то: распоряжения полководца, вооружение и т. д., принимая их за значение множителя, а признаем это неизвестное во всей его цельности, то есть как большее или меньшее желание драться и подвергать себя опасности. Тогда только, выражая уравнениями известные исторические факты, из сравнения относительного значения этого неизвестного можно надеяться на определение самого неизвестного.
Десять человек, батальонов или дивизий, сражаясь с пятнадцатью человеками, батальонами или дивизиями, победили пятнадцать, то есть убили и забрали в плен всех без остатка и сами потеряли четыре; стало быть, уничтожились с одной стороны четыре, с другой стороны пятнадцать. Следовательно, четыре были равны пятнадцати, и, следовательно, 4а:=15у. Следовательно, ж: г/==15:4. Уравнение это не дает значения неизвестного, но оно дает отношение между двумя неизвестными. И из подведения под таковые уравнения исторических различно взятых единиц (сражений, кампаний, периодов войн) получатся ряды чисел, в которых должны существовать и могут быть открыты законы.
Тактическое правило о том, что надо действовать массами при наступлении и разрозненно при отступлении, бессознательно подтверждает только ту истину, что сила войска зависит от его духа. Для того чтобы вести людей под ядра, нужно больше дисциплины, достигаемой только движением в массах, чем для того, чтобы отбиваться от нападающих. Но правило это, при котором упускается из вида дух войска, беспрестанно оказывается неверным и в особенности поразительно противоречит действительности там, где является сильный подъем или упадок духа войска, – во всех народных войнах.
Французы, отступая в 1812 м году, хотя и должны бы защищаться отдельно, по тактике, жмутся в кучу, потому что дух войска упал так, что только масса сдерживает войско вместе. Русские, напротив, по тактике должны бы были нападать массой, на деле же раздробляются, потому что дух поднят так, что отдельные лица бьют без приказания французов и не нуждаются в принуждении для того, чтобы подвергать себя трудам и опасностям.

Так называемая партизанская война началась со вступления неприятеля в Смоленск.
Прежде чем партизанская война была официально принята нашим правительством, уже тысячи людей неприятельской армии – отсталые мародеры, фуражиры – были истреблены казаками и мужиками, побивавшими этих людей так же бессознательно, как бессознательно собаки загрызают забеглую бешеную собаку. Денис Давыдов своим русским чутьем первый понял значение той страшной дубины, которая, не спрашивая правил военного искусства, уничтожала французов, и ему принадлежит слава первого шага для узаконения этого приема войны.
24 го августа был учрежден первый партизанский отряд Давыдова, и вслед за его отрядом стали учреждаться другие. Чем дальше подвигалась кампания, тем более увеличивалось число этих отрядов.
Партизаны уничтожали Великую армию по частям. Они подбирали те отпадавшие листья, которые сами собою сыпались с иссохшего дерева – французского войска, и иногда трясли это дерево. В октябре, в то время как французы бежали к Смоленску, этих партий различных величин и характеров были сотни. Были партии, перенимавшие все приемы армии, с пехотой, артиллерией, штабами, с удобствами жизни; были одни казачьи, кавалерийские; были мелкие, сборные, пешие и конные, были мужицкие и помещичьи, никому не известные. Был дьячок начальником партии, взявший в месяц несколько сот пленных. Была старостиха Василиса, побившая сотни французов.
Последние числа октября было время самого разгара партизанской войны. Тот первый период этой войны, во время которого партизаны, сами удивляясь своей дерзости, боялись всякую минуту быть пойманными и окруженными французами и, не расседлывая и почти не слезая с лошадей, прятались по лесам, ожидая всякую минуту погони, – уже прошел. Теперь уже война эта определилась, всем стало ясно, что можно было предпринять с французами и чего нельзя было предпринимать. Теперь уже только те начальники отрядов, которые с штабами, по правилам ходили вдали от французов, считали еще многое невозможным. Мелкие же партизаны, давно уже начавшие свое дело и близко высматривавшие французов, считали возможным то, о чем не смели и думать начальники больших отрядов. Казаки же и мужики, лазившие между французами, считали, что теперь уже все было возможно.
22 го октября Денисов, бывший одним из партизанов, находился с своей партией в самом разгаре партизанской страсти. С утра он с своей партией был на ходу. Он целый день по лесам, примыкавшим к большой дороге, следил за большим французским транспортом кавалерийских вещей и русских пленных, отделившимся от других войск и под сильным прикрытием, как это было известно от лазутчиков и пленных, направлявшимся к Смоленску. Про этот транспорт было известно не только Денисову и Долохову (тоже партизану с небольшой партией), ходившему близко от Денисова, но и начальникам больших отрядов с штабами: все знали про этот транспорт и, как говорил Денисов, точили на него зубы. Двое из этих больших отрядных начальников – один поляк, другой немец – почти в одно и то же время прислали Денисову приглашение присоединиться каждый к своему отряду, с тем чтобы напасть на транспорт.
– Нет, бг"ат, я сам с усам, – сказал Денисов, прочтя эти бумаги, и написал немцу, что, несмотря на душевное желание, которое он имел служить под начальством столь доблестного и знаменитого генерала, он должен лишить себя этого счастья, потому что уже поступил под начальство генерала поляка. Генералу же поляку он написал то же самое, уведомляя его, что он уже поступил под начальство немца.
Распорядившись таким образом, Денисов намеревался, без донесения о том высшим начальникам, вместе с Долоховым атаковать и взять этот транспорт своими небольшими силами. Транспорт шел 22 октября от деревни Микулиной к деревне Шамшевой. С левой стороны дороги от Микулина к Шамшеву шли большие леса, местами подходившие к самой дороге, местами отдалявшиеся от дороги на версту и больше. По этим то лесам целый день, то углубляясь в середину их, то выезжая на опушку, ехал с партией Денисов, не выпуская из виду двигавшихся французов. С утра, недалеко от Микулина, там, где лес близко подходил к дороге, казаки из партии Денисова захватили две ставшие в грязи французские фуры с кавалерийскими седлами и увезли их в лес. С тех пор и до самого вечера партия, не нападая, следила за движением французов. Надо было, не испугав их, дать спокойно дойти до Шамшева и тогда, соединившись с Долоховым, который должен был к вечеру приехать на совещание к караулке в лесу (в версте от Шамшева), на рассвете пасть с двух сторон как снег на голову и побить и забрать всех разом.
Позади, в двух верстах от Микулина, там, где лес подходил к самой дороге, было оставлено шесть казаков, которые должны были донести сейчас же, как только покажутся новые колонны французов.
Впереди Шамшева точно так же Долохов должен был исследовать дорогу, чтобы знать, на каком расстоянии есть еще другие французские войска. При транспорте предполагалось тысяча пятьсот человек. У Денисова было двести человек, у Долохова могло быть столько же. Но превосходство числа не останавливало Денисова. Одно только, что еще нужно было знать ему, это то, какие именно были эти войска; и для этой цели Денисову нужно было взять языка (то есть человека из неприятельской колонны). В утреннее нападение на фуры дело сделалось с такою поспешностью, что бывших при фурах французов всех перебили и захватили живым только мальчишку барабанщика, который был отсталый и ничего не мог сказать положительно о том, какие были войска в колонне.
Нападать другой раз Денисов считал опасным, чтобы не встревожить всю колонну, и потому он послал вперед в Шамшево бывшего при его партии мужика Тихона Щербатого – захватить, ежели можно, хоть одного из бывших там французских передовых квартиргеров.

Плаксин М.А.

Национальный исследовательский университет Высшая школа экономики (Пермский филиал), г.Пермь, к.ф.м.н., доцент кафедры информационных технологи в бизнесе, 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.