Intel-лаборатория НГУ 06.02.2010 О ПРОБЛЕМЕ НАЧАЛЬНОГО ОБУЧЕНИЯ ПАРАЛЛЕЛЬНОМУ ПРОГРАММИРОВАНИЮ Лидия Васильевна Городняя gorod@iis.nsk.su ИСИ СО РАН им. - презентация

1 Intel-лаборатория НГУ О ПРОБЛЕМЕ НАЧАЛЬНОГО ОБУЧЕНИЯ ПАРАЛЛЕЛЬНОМУ ПРОГРАММИРОВАНИЮ Лидия Васильевна Городняя ИСИ СО РАН им. А.П. Ершова

2 Уровни и цели обучения Начальное (полгода в лет) - интуитивное понимание параллелизма, - навыки синхронизации независимо запрограммированных потоков, - ознакомление с проблемами взаимодействия параллельных процессов. Допроизводственное (2 года с/к для старшеклассников и студентов) - базовые теории параллельных вычислений, - навыки программирования, отладки и оптимизации параллельных алгоритмов, - опыт оценки производительности программ и распараллеливания программ с учетом различных видов памяти и коммуникаций, нацеленные на переход к производственным средствам. Целенаправленное (специализация и научный эксперимент)

3 Требования к языку обучения параллельному программированию Многовариантность лингвистической базы. Концентричность по уровням обучения. Естественность представления и понимания параллельных программ Визуализация объектов и процессов при отладке. Представление и преобразование моделей управления процессами. Определение видов памяти с разной дисциплиной доступа. Настраивание на производственные языки и системы. Выводимость оценки значимых характеристик производительности программ.

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

5 Проект языка начального обучения Учтен опыт и история языков: Basic, Pascal, Logo, Grow, Робик, Рапира, Lisp, Scheme, Prolog, REX, Forth, A++, ECL, Elan, Karel, MIX, MMIX, APL, Algol-68, Setl, Ada, БАРС, SISAL, mpC и др.

6 Текущие задачи Учебные языки программирования XXI века поддерживают основные парадигмы программирования на ЯВУ: императивное функциональное логическое объектно-ориентированное. Проблема - параллельное программирование (GPU, MPI, Open MP)

7 Основные понятия Поток: серия (команда | структура) фильтр Серия: после, одновременно, исключение, тираж Структура: очередь, множество, вариант, вектор Команда: (отображение, управление, поток) / длительность Отображение: данное {результат | отказ} фильтр

8 Основные понятия Управление: Ожидание, Ветвление, Цикл Ветвление: условие, вероятность Цикл: (условие тело) фильтр Ожидание: начало_потока конец_потока барьер событие

9 Основные понятия Условие: фильтр предикат: when-until кратность структура Вероятность: положительное число < 1 % число < 100 M/N часто, редко, иногда, обычно, возможно Длительность: число часы Скорость: число быстро, норма, медленно

10 Проект ЯПП %Язык начального обучения параллельному программированию Пр = [( Барьер... )] [ [ПОТОКИ] Поток ( [, ] Поток )...] % Программа состоит из сети совместно выполняемых потоков. % Барьеры- это метки, выделяющие в сети потоков % параллели – синхронизуемые звенья.

11 Проект ЯПП Поток = [( Барьер... )] [Имя_потока = ] ( Дир ( [ ; ] Дир )... ) % Поток – это сосредоточенное описание % рассредоточенных действий, % согласованное с другими потоками с помощью барьеров

12 Проект ЯПП Дир = Простое | Сложное | Метка : Дир | Исполнитель ! Дир | Данные | Дир [[{ | =}] [РЕЗУЛЬТАТ] Фильтр] % Директивы выполняются, если могут. % Иначе следующие (;) за ними НЕ выполняются, % но могут выполняться независимые [,].

13 Проект ЯПП Простое = [РЕЗУЛЬТАТ] Выр Сложное = Управление Дир | Вариант | Одновременно | Последовательно Управление = Ожидание | Обход | Цикл

14 Проект ЯПП Ожидание = ЖДИ Число [:] | КОГДА Метка [:] | ПРИ Усл [:] % управление останавливается перед директивой, % пока не выполнится условие ожидания Обход = ЕСЛИ Клапан ТО | ЕСЛИ_НЕ Клапан ТО | [ВЕРОЯТНО] Число % % управление переходит вслед за директивой Цикл = [ПОКА Усл] ПОВТОР | ПОВТОР Целое РАЗ

15 Проект ЯПП Варианты = { [ВАРИАНТ] Дир ( [ | ] Дир )... } % успешное завершение одного варианта % дает сигнал о принудительном прерывании остальных, % и происходит откатка незавершенных вариантов % перебор или выбор вариантов идет слева направо Одновременно = [ [СОВМЕСТНО] Дир ( [, ] Дир )...] % неимперативная одновременность Последовательно = ( ( [ ; ] Дир )... ) % между соседними директивами может быть % выполнение директив из смежных потоков

16 Проект ЯПП Выр = Имя | Значение | Отображение | Арг Операция Арг | Фильтр Отображение = Имя_ФН ( Арг...) Операция = > | = | | + | - | * |... % и другие % Операции просачиваются относительно структур Фильтр = > | = | … % и другие % выделяются элементы, соответствующие сравнению

17 Проект ЯПП Исполнитель = Имя_ФН Арг = Простое Знач = Число | Текст | Структура | Функция | Исполнитель | Метка | ПУСТО | ДА | НЕТ | НЕИЗВЕСТНО | ЧАСТО | РЕДКО | ИНОГДА

18 Проект ЯПП Структура = Очередь | Вектор % При чтении элементы из очереди удаляются, % новые попадают в «хвост» Клапан = Усл % Клапан пропускает управление, % регулируя выполнение/невыполнение директивы Усл = Выр Барьер = Метка % Барьеры выделяют в потоках синхронизуемые параллели. % Можно делать выборки-вырезки из потоков, указывая барьеры. Метка = Имя

19 Поливариантный синтаксис Абстрактный синтаксис Конкретные вариации фразеологической поддержки по выбору учителя и уровню обучения (setq А Б) А := Б Переменной А присвоить значение выражения Б Значение Б разместить по адресу А Теперь А имеет то же значение, что и Б Б -> А

20 Источники примеров Олимпиады Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир Робик (исполнители)

21 Олимпиадная задача 3 котлеты на 2 сковороды Для обжарки одной стороны котлеты требуется 5 минут. Имеется 2 сковороды, на них надо как можно скорее поджарить 3 котлеты. Примечание: на Intel-семинаре в Москве упоминалась как пример немасштабируемого алгоритма. Надо предложить и ясно записать масштабируемое решение.

22 3 котлеты на 2 сковороды ОЧЕРЕДЬ жарить = (2 2 2), % предстоит обжарить 2 стороны каждой котлеты готово = () % тарелка для готовых котлет % в конце строки ; не обязательна ВЕКТОР сковороды [1..2] ПОКА жарить ПОВТОР % общая вертикаль выделяет блок жарить сковороды % два первых элемента из очереди исчезают ЖДУ 1 % время «жарки» сковороды = ( сковороды - 1) % внутренний цикл: ск [i] = ск [i] - 1, % значит, что одна сторона обжарена [ (жарить ; (сковороды ? 0)), % «недожаренные» (= 1) становятся в очередь (готово ; (сковороды ?= 0)) ] % накапливается результат (со 2-го витка) % разделили готовые и требующие жарки РЕЗУЛЬТАТ готово % = (0 0 0 )

23 2-3: описание данных ОЧЕРЕДЬ жарить = (2 2 2), % предстоит обжарить 2 стороны каждой котлеты готово = ( ) % тарелка для готовых котлет ВЕКТОР сковороды [1..2]

24 2-3: основной цикл ПОКА жарить ПОВТОР жарить сковороды % два первых элемента ЖДУ 1 % время «жарки» сковороды = ( сковороды - 1) % одна сторона обжарена [ (жарить ; (сковороды 0)), (готово ; (сковороды = 0)) ] % разделили готовые и требующие жарки РЕЗУЛЬТАТ готово % = (0 0 0 )

25 Хоар: Простой торговый автомат Описать поведение автомата, принимающего монету, а потом выдающего шоколадку

26 Хоар: Простой торговый автомат ПОВТОР ( ! мон ; % сначала прием монетки, ? шок ) % потом выдача шоколадки

27 Хоар: Простой торговый автомат с доверием Автомат допускает выдачу шоколадки до получения монетки - доверяет покупателю.

28 Хоар: Простой торговый автомат с доверием ПОВТОР [ ! мон, % прием монетки и независимо ? шок ] % выдача шоколадки в любом порядке

29 Хоар: Простой торговый автомат (учет числа шоколадок в автомате) Автомат может по разным причинам не выдать шоколадку. Описать поведение автомата, сообщающего покупателю об отсутствии товара и возвращающего монету.

30 Хоар: Простой торговый автомат (учет числа шоколадок в автомате) шоколадки = N % число шоколадок в автомате ПОКА шоколадки ПОВТОР ( ! мон ; % прием монетки ? шок % выдача шоколадки шоколадки = шоколадки – 1 ) % учет остатка ? «шоколадок пока нет» ! мон % возврат монетки СТОП

31 Хоар: Простой торговый автомат (Хоар): подсчет выручки Описать автомат, выполняющий подсчет выручки. Считаем, что монетоприемник по объему превышает объем возможной выручки.

32 Хоар: Простой торговый автомат (Хоар): подсчет выручки Монеты = M % выручка % монетоприёмник вмещает монет больше, % чем число шоколадок в автомате ПОКА шоколадки ПОВТОР ( ! мон % прием монетки ? шок % выдача шоколадки монеты = монеты + 1 ) % подсчет выручки СТОП

33 Счетчики шоколадки = N % для учета ПОКА шоколадки ПОВТОР шоколадки = шоколадки – 1 % монеты = M % для подсчета выручки ПОВТОР монеты = монеты + 1

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

35 Расстановка барьеров для взаимодействия процессов ПТА = ПОВТОР ( ! мон ; % сначала прием монетки, Контроль: % барьер ? шок ) % потом выдача шоколадки УЧЕТ = шоколадки = N ПОКА шоколадки ПОВТОР Контроль: % барьер шоколадки = шоколадки – 1 СТОП

36 Определение взаимодействия ПТА_С_УЧЕТОМ = (Контроль) [ ПТА, УЧЕТ ] % общий барьер

37 Автомат с заманиванием ПТА = ПОВТОР ( ! мон ; % сначала прием монетки, ? шок % потом выдача шоколадки Контроль: ) ВЫИГРЫШ = ПОВТОР Контроль: ИНОГДА % ? сувенир % иногда выдается «приманка» ВЫРУЧКА = монеты = M ПОВТОР Контроль:монеты = монеты + 1

38 Варианты взаимодействий (Контроль) % барьер во всех процессах [ ПТА, УЧЕТ, ВЫРУЧКА ] % автомат с учетом числа шоколадок и подсчетом монет [(Контроль) ПТА, (Контроль) УЧЕТ, % процессы синхронизованы ВЫИГРЫШ ] % процесс без барьеров % автомат с учетом числа шоколадок, возможно заманивание

39 Функции Ф_ПТА = (мон шок) ( мон ; шок ; Контроль: Ф_ПТА ) % по умолчанию параметры сохраняются Ф_ПТА (жетон, игрушка) % явная параметризация (Контроль) [Ф_ПТА (жетон, игрушка), ВЫРУЧКА ]

40 Управление рекурсией УЧЕТ = ( N ) ПОКА N ПОВТОР Контр: N = N – 1 Ф_ПТА = (мон шок) ( мон ; шок ; Контр: Ф_ПТА ) (Контр) [Ф_ПТА (жетон, игрушка), УЧЕТ (4)] % выдать 4 игрушки

41 Переименование барьера УЧЕТ_Б = ( N b ) ПОКА N ПОВТОР b: N = N – 1 Ф_ПТА_Б = (мон шок p) ( мон ; шок ; p: Ф_ПТА_Б ) (Контр) [Ф_ПТА_Б (жетон, игрушка, Контр), УЧЕТ (4, Контр)]

42 Sisal - произведение матриц Массив из суммы произведений (строка на столбец)

43 Sisal - произведение матриц function MM ( A, B ) if size (A, 2) ~= size (B, 1) then Error[] else array [ i in 1.. size (A, 1), j in 1.. size (B, 2) : [i,j] sum (A [ i,..] * B [.., j] ) ] end if end function

44 Sisal - быстрая сортировка Быстрая сортировка: рекурсия с разделением на каждом шаге на меньшие, равные и большие

45 Sisal - быстрая сортировка Function QS (Data) If ( size (Data) < 2 then Data ) else Let Pivot := Data [ liml (Data)] Low, Mid, High := for E in Data do returns array of E when E < Pivot, array of E when E = Pivot, array of E when E > Pivot end for in QS (Low) || Mid || QS (High) end if end function

46 Параллельная сортировка Сравнивать по 2 соседних элемента на процессор, меняя порядок, где надо. Потом сдвинуть процессоры на один элемент и т.д. пока не обнаружится, что порядок достигнут, т.е. обмена не происходит.

47 Параллельная сортировка процессоры П [1.. K]; числа A [1.. 2K]; цикл ( для i из 1.. К выполнять П [i] : { ? A [ 2*i - 1] =< A [ 2*i] | A [ 2*i - 1] A [ 2*i]} % перебор вариантов слева направо ; % затем для i из 1.. К-1 выполнять П [i] : { ? A [ 2*i] >= A [ 2*i + 1] | A [ 2*i] A [ 2*i +1] } ) пока выполнялось ( )

48 Первоочередные мероприятия Включение учебного материала по параллельному программированию для учащихся младшего и среднего звена в план работы ЗШ на сайте НГУ Запуск серии учебных проектов по детской разработке систем управления визуальными роботами и игр на ЛШЮП Подготовка для Всесибирской олимпиады по программированию задач, естественно решаемых в терминах параллельных процессов

49 Литература 1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.- СПб.: БХВ-Петербург, – 608 с. 2. Котов В.Е. МАРС: архитектуры и языки для реализации параллелизма. с Системная информатика. Вып 1. Проблемы современного программирования. - Новосибирск: Наука. Сиб. отд-ние, с. 3. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 264 с о Робике

50 Спасибо за внимание