III Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ В СРЕДЕ PASCALABC. NET ДЛЯ РЕШЕНИЯ ШКОЛЬНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Абрамова И.А. 1

---

1МБОУ СОШ 83

Гаврилова И.В. 1

---

1МБОУ СОШ №83, г. Ногинск-9

Работа в формате PDF

594.1 KB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

Введение

Проект основан на сравнении времени выполнения параллельной и последовательной программ. В качестве наглядной демонстрации рассмотрены тривиальные задачи по алгоритмизации и программированию базового школьного курса информатики. Запуск программ осуществляется на 1, 2 ядрах, процессора IntelPentium(R) 3556U @ 1.70 GHz. Так же был осуществлён запуск на 4-ядерном процессоре.

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

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

В проекте рассматривается среда программирования PascalABC.NET, поскольку она широко используется в образовательных учреждениях. Для данного проекта важно то, что в PascalABC.NET реализованы средства параллельного программирования в виде директив OpenMP. Таким образом, чтобы показать некоторые возможности параллельного программирования не предполагается изучение дополнительных языков программирования и установки нового программного обеспечения.

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

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

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

• Изучить возможность применения параллельного программирования в школьной программе;

• Сравнить время выполнения последовательной и параллельной программ;

• Оценить эффективность каждого из методов;

• Понять от чего зависит время выполнения;

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

• Изучение возможности применения PascalABC.net для обучения параллельного программирования в школе

В среде PascalABC.net написаны параллельная и последовательная программы для некоторых задач школьного курса по информатике (программированию). Производится сравнение и анализ результатов. Выясняются причины несовпадения с ожидаемыми результатами или же подтверждаются прогнозы. Осознание возможности применения параллельного программирования в PascalABC.net.

• В современном мире даже в телефонах используются технологии параллельного программирования, но пользователь не знает для чего это им нужно;

• Суперкомпьютеры, с помощью которых наука открывает все новые и новые горизонты, нуждаются в квалифицированных специалистах;

РЕШЕНИЕ ЗАДАЧ

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

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

Результатом выполнения программы должно быть число - сколько раз в тексте встречается данная буква.

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

Для сравнения времени выполнения программ, выполняется сначала последовательная, а затем параллельная.

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

SHARED Применяется к переменным, которые необходимо сделать общими.

PRIVATE Применяется к переменным, которые необходимо сделать приватными. При входе в параллельную область для каждой нити создается отдельный экземпляр переменной, который не имеет никакой связи с оригинальной переменной вне параллельной области (Приложение, рис.1).

Время выполнения последовательной программы – 60 мс.

Время выполнения параллельной программы – 26 мс.

Результаты (количество букв в тексте) совпадают.

Таким образом, получаемускорение

Эффективность распараллеливания:

E = 2,3 ∕ 2= 1, 15

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

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

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

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

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

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

Время выполнения было быстрее то у параллельной, то у последовательной программы.

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

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

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

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

В некоторых случаях ускорение превосходит все ожидания. Возможно, это связано с кэш-попаданиями и кэш-промахами.

Между процессором и ОЗУ используется быстродействующая буферная память. Буферная память скрыта от программиста в том смысле, что он не может ей адресовывать и может даже не знать о ее существовании. Поэтому такая скрытая буферная память получила название КЭШ памяти, от английского слова Cache – тайник. Работа КЭШ памяти прозрачна, то есть невидима для пользователя.

Процессор в основном работает с данными, находящимися в КЭШ-памяти, и только при их отсутствии в КЭШ, вынужден обращаться к ОЗУ.

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

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

Вывод: На данной задаче достаточно трудно показать плюсы параллельного программирования, тем более в рассматриваемой среде – PascalABC.net. Тем не менее, на этой программе можно удачно показать реальную работу нескольких ядер одновременно, если добавить вывод промежуточных результатов. В случае с одним ядром промежуточных результатов гораздо больше, поскольку все вычисления одно ядро выполняет последовательно. При запуске параллельной программы промежуточных результатов (частичных сумм) будет гораздо меньше. Причем чем больше ядер, тем меньше количество этих сумм (что тоже ограничено – слишком большое количество ядер приведет к временным задержкам, поскольку работы будет меньше, чем «рабочих»). Кроме того, и сами промежуточные суммы в последовательной и параллельной программе будут отличаться, что также можно продемонстрировать школьникам.

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

Усложним вычислительную задачу.

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

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

Кроме того, при использовании 2 ядер последовательная программа оказывается быстрее параллельной. Но при запуске на 4 ядрах параллельная все же быстрее (Приложение, рис.3). Это также наглядно демонстрирует возможности параллельных вычислений и может использоваться учителем на уроках.

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

Алгоритм прост: Встретил букву «а», добавь единицу в ячейку массива с номером 1, встретил «Б» - в ячейку с номером 2 и т.д.

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

Ниже приведена диаграмма с данными по нескольким запускам программы.

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

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

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

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

К сожалению, OpenMP реализован в PascalABC.NET не полностью. Здесь можно распараллелить только совсем простые циклы, поэтому были встречены проблемы с реализацией.

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

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

• От количества используемых ядер (характеристик процессора);

• От сложности программ (объема вычислений);

• От количества обрабатываемых данных.

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

Полученные результаты могут использовать учителя информатики для ознакомления школьников с параллельным программированием на уроках.

1. http://pascalabc.net/

2. http://www.parallel.ru/tech/tech_dev/openmp.html

3. http://www.studfiles.ru/preview/2014486/page:4/