Формирование представлений о параллельных процессах в школьном курсе информатики

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

Современная теория алгоритмов создавалась в расчете на понятие последовательного алгоритма. Каким образом отразится на понятии алгоритма отказ от требования последовательности выполнения шагов? По крайней мере последние 20 лет понятие «алгоритм» вводилось в школе в неразрывной связке с понятием «исполнитель». Для последовательного алгоритма это естественно. Как быть с параллельным алгоритмом? Его выполняет один исполнитель или группа исполнителей?

В связи с этим возникает ряд вопросов: требует доработки традиционное понятие системы команд исполнителя (СКИ) и само понятие команды. Если мы считаем, что группа исполнителей образуют единого исполнителя, то, что считать СКИ этого исполнителя? И что считать командой? Или оставить понятие СКИ для каждого отдельного исполнителя? То есть это уже не система команд исполнителя, а система команд одной из компонент исполнителя (для которой еще нет названия)? Что считать параллельным алгоритмом? Среди свойств алгоритмов выделяется новая практически значимая характеристика -способность к распараллеливанию. До какой степени имеет смысл увеличивать количество процессоров при выполнении данного алгоритма? Отдельный вопрос — методы распараллеливания уже существующих последовательных алгоритмов. Соответственно, возникает необходимость поиска ответов на поставленные вопросы.

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

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

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

Сегодня положение сложилось так, что тематика параллельных вычислений в средней школе в первую очередь оказалась связана с темой суперкомпьютеров. Именно на суперкомпьютерах акцентируют внимание учащихся авторы различных методических разработок [3,4]

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

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

В школьном курсе информатики предлагается отразить следующие вопросы:

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

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

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

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

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

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

• 7.    Ресурсы. Ресурсы разделяемые и неразделяемые, расходуемые и повторно используемые.

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

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

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

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

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

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

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

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

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

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

• ■    Конкуренция исполнителей за ресурсы. Блокировка.

• ■    Предложены следующие типы задач:

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

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

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

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

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

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

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

• 3.    Сформулированы некоторые классы задач;

• 4.    Подготовлен набор деловых игр.