Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Новосибирский государственный университет» (НГУ)
Факультет информационных технологий
Кафедра Параллельных вычислений
ПРОГРАММА
«Разработка и моделирование мелкозернистых алгоритмов и
ДИСЦИПЛИНЫ
структур»ЦИКЛ* Специальные дисциплины НАПРАВЛЕНИЕ ПОДГОТОВКИ БАКАЛАВРОВ 230100.62 «Информатика и вычислительная техника»
Авторы Пискунов С.В. к.т.н., доцент Остапкевич М.Б., м.н.с.
Новосибирск * Наименование цикла дисциплин в соответствии с ГОС ВПО Программа дисциплины «Разработка и моделирование мелкозернистых алгоритмов и структур» составлена в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки дипломированного специалиста по циклу «специальных дисциплин» Федеральных государственных образовательных стандартов высшего профессионального образования по специальности 230100.62 «Информатика и вычислительная техника».
1. Цели и задачи дисциплины (курса) Дисциплина (курс) «Разработка и моделирование мелкозернистых алгоритмов и структур»
имеет своей целью обучение теоретическим и практическим знаниям формальных методов, языковых и инструментальных средств синтеза глубоко параллельных мелкозернистых алгоритмов и архитектур.
Для достижения поставленной цели выделяются задачи курса:
1. овладение базовыми знаниями о методах организации вычислений с мелкозернистым параллелизмом 2. овладение клеточной технологией конструирования имитационных моделей мелкозернистых алгоритмов и структур.
2. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины студент должен:
Иметь представление о об универсальности парадигмы «клеточный автомат» в области параллельных вычислений, - об асинхронной композиции мелкозернистых алгоритмов, - о корректности мелкозернистых параллельных вычислений в синхронной и асинхронной модах, - об областях применения таких моделей массового параллелизма, как клеточный автомат, ассоциативный процессор, нейронная и клеточно-нейронная сеть, - об алгоритмическом проектировании спецпроцессоров с массовым параллелизмом, - о построении клеточно-автоматных моделей физических процессов.
Знать виды некорректности параллельных мелкозернистых вычислений в синхронной и асинхронной модах и методы их распознавания;
- методы пространственно-временных и структурных эквивалентных преобразований алгоритмов с мелкозернистым параллелизмом;
- методы асинхронной композиции параллельных алгоритмов;
-- основные приемы конструирования моделей в системе имитационного моделирования.
виды некорректности параллельных мелкозернистых вычислений в синхронной и асинхронной модах и методы их распознавания;
- методы пространственно-временных и структурных эквивалентных преобразований алгоритмов с мелкозернистым параллелизмом;
- методы асинхронной композиции параллельных алгоритмов;
-- основные приемы конструирования моделей в системе имитационного моделирования.
Уметь - строить модели мелкозернистых алгоритмов и структур в широком спектре приложений в информатике и технической физике с использованием системы имитационного моделирования WinALT.
3. Объем дисциплины и виды учебной работы Вид учебной работы Всего часов Семестры 6 Общая трудоемкость дисциплины 96 48 Аудиторные занятия, в том числе: 64 38 Лекции 32 16 Семинары 12 Лабораторные работы 20 10 Самостоятельная работа, в том числе: 32 10 Курсовой проект 22 Реферат 10 Расчетные работы Другие виды самостоятельной работы Вид промежуточного контроля зачет экзамен Общая трудоемкость дисциплины составляет 96 часов зачетных единиц (если применяется на факультете/кафедре).
4. Содержание дисциплины 4.1. Новизна курса (научная, содержательная; сравнительный анализ с подобными курсами в России и за рубежом).
Одним из основных видов параллелизма, на который опирается технология организации параллельных вычислений, является мелкозернистый параллелизм.
Привлекательность мелкозернистого параллелизма объясняется тем, что только в его рамках для многих задач возможно предельное, свойственное алгоритму решаемой задачи ("естественное") распараллеливание. Значение мелкозернистого параллелизма возрастает во все большей степени в связи со стремительным ростом степени интеграции СБИС и, как следствие, с лавинообразным ростом возможностей распараллеливания вычислительного процесса как на макро- так и на микро уровне. Курсы, в которых рассматривалось бы построение имитационных моделей физических и информационных процессов для широкого спектра классов мелкозернистых алгоритмов и структур, а не только для клеточного автомата и некоторых его модификаций, авторам данного курса неизвестны.
4.2. Тематический план курса (распределение часов по видам учебной работы).
мелкозернистых подстановок (АПП) преобразования АПП мелкозернистых использованием конструирования 4.3. Содержание разделов и тем курса.
А) Лекции Раздел 1. Обобщенная модель мелкозернистых вычислений Тема 1.1. (2 час) Введение. Предмет и содержание курса, учебно-методическая и научная литература. История развития параллельных вычислений. Тенденции в конструировании параллельных алгоритмов и структур. Обзор компьютерных систем моделирования клеточных автоматов и их расширений.
Тема 1.2. (2 часа) Формальные модели массовых параллельных вычислений:
основные определения, характерные черты, области применения.
Клеточный автомат: основные определения. Одномерный клеточный автомат Неймана:
сравнение тьюринговых и неймановых вычислений на примере задачи распознавания симметрии слов. Уменьшение трудоемкости вычислений путем их распараллеливания.
Применение клеточных автоматов для исследования физических и информационных процессов. Универсальные клеточные автоматы, автомат Бэнкса. Другие модели мелкозернистых вычислений: нейронные и клеточно-нейронные сети, ассоциативные машины, систолические структуры.
Тема 1.3. (4 часа) Алгоритм параллельных подстановок Происхождение модели и ее основные черты (объединение концепций клеточного автомата и алгоритма Маркова). Базовые понятия: клеточный массив, конфигурация, параллельная подстановка, система параллельных подстановок. Синхронная и асинхронная моды выполнения системы параллельных подстановок. Понятие алгоритма параллельных подстановок. Подклассы и расширения алгоритмов параллельных подстановок. Интерпретация алгоритмов параллельных подстановок сетями автоматов.
Тема 1.4. (2 час) Асинхронная композиция алгоритмов параллельных подстановок.
Граф-схема взаимодействия параллельных процессов. Моделирование управления сетью Петри. Представление сети Петри в виде алгоритма параллельных подстановок.
Композиционное расширение алгоритма параллельных подстановок, способы получения композиционных расширений. Представление асинхронной композиции сетью автоматов.
Тема 1.5. (2 час) Эквивалентные преобразования алгоритмов параллельных подстановок.
Пространственно-временные и синхронно-асинхронные преобразования алгоритмов параллельных подстановок. Преобразование двумерных алгоритмов параллельных подстановок в трехмерные (методы расслоения).
Тема 1.6. (4 часа) Корректность систем параллельных подстановок.
Синхронная, ординарная асинхронная и асинхронная моды выполнения параллельных подстановок. Вычисление конечное, однозначное, непротиворечивое. Распознавание непротиворечивости систем параллельных подстановок в синхронной моде.
Распознавание неоднозначности и распознавание незавершаемости систем параллельных подстановок в синхронной, ординарной асинхронной и асинхронной модах.
Раздел 2. Компьютерное моделирование мелкозернистых алгоритмов и структур с использованием системы WinALT.
Тема 2.1. (2 часа) Общее описание системы WinALT.
Принципы построения системы. Архитектура и возможности системы WinALT. Версии системы. Графический образ системы. Описание сайта системы. Архитектура параллельной версии системы.
Тема 2.2. (4 часов) Языковые средства системы.
Общий обзор. Моделирующая программа. Средства параллельного программирования (воплощение алгоритма параллельных подстановок). Средства последовательного структурного программирования. Объединение средств параллельной и последовательной частей языка. Средства модульности и расширения возможностей языка. Средства редактирования текстов. Библиотеки системы WinALT.
Тема 2.3. (4 часа) Графическая среда системы WinALT.
WinALT – система визуального программирования. Окно «Дерево проекта». Меню.
Панели инструментов. Основные диалоги. Вспомогательные окна. Средства визуального конструирования и модификации графических образов данных модели и моделирующих программ.
Тема 2.4. (6 часов) Основы клеточной технологии конструирования моделей.
Создание проекта в системе. Создание полотен (файлов) с клеточными объектами и моделирующими программами. Режимы выполнения и отладки модели. Примеры проектов в области классических клеточных автоматов, клеточно-нейронных сетей, многоступенчатых микроконвейеров, искусственной жизни, имитации физических процессов. Синтез архитектур 3D спецпроцессоров с оптическими межсоединениями.
Б) Семинары 1. Изучение операторов поддержки АПП, средств параллельного исполнения блоков операторов. Ознакомление с операторами параллельно-последовательной композиции и вспомогательными операторами. Изучение библиотек реализации синхронного, асинхронного и смешанного режимов моделирования (4 часа).
2. Освоение техники представления архитектуры имитационной модели в системе WinALT. Освоение средств описания пользовательских окон, диалогов и их элементов, средств отрисовки графики. Выработка стиля оформления и документирования моделей (4 часа).
3. Изучение механизмов импорта внешних библиотек и подпрограмм, написанных на языках Си/Си++. Освоение методики подключения внешних стандартных библиотек к системе WinALT и их использования из моделирующих программ. Изучение событийно-ориентированных механизмов расширения функциональности системы WinALT на базе средств, предоставляемых собственной библиотекой системы (4 часа).
В) Лабораторные работы 1. Построение в системе WinALT имитационных моделей машины Тьюринга (сложение, умножение и др.) (2 часа).
2. Построение в системе WinALT имитационных моделей модификаций классических клеточных автоматов: игра «Жизнь», автомат Гриффита, автомат Бэнкса, самовоспроизводящаяся структура Сиппера, самовоспроизводящаяся петля Лангтона (4 часа).
3. Построение в системе WinALT имитационных моделей информационных структур:
многоступенчатые конвейеры арифметических операций, динамически перестраиваемые в процессе вычислений многоступенчатые конвейеры, ассоциативные процессоры, однородные вычислительные структуры (4 часа).
4. Построение в системе WinALT имитационных моделей физических процессов:
модели диффузии, модели FHP-газа (6 часов).
5. Конструирование средствами системы WinALT пользовательских меню, диалогов, окон с графиками и диаграммами для задания параметров графической среды и управления процессом моделирования (4 часа).
4.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы.
1. Клеточный автомат - парадигма параллельных вычислений.
2. Клеточный автомат - модель пространственно-распределенной динамической системы (изучение явлений: упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др.).
3. Варианты клеточных автоматов: универсальные, асинхронные, вероятностные.
4. Охарактеризовать нейронные сети, описать модель Хопфилда, показать возможности нейронной сети как ассоциативной памяти.
5. Охарактеризовать однородные вычислительные структуры, привести пример вычисления булевской функции в ПЛМ.
6. Охарактеризовать итеративные структуры, привести пример вычисления булевской функции в итеративной структуре.
7. Охарактеризовать ассоциативные структуры с вертикальной обработкой информации (типа STARAN), описать реализацию простейших операций (=, min, 8. Описать технологию ПЛИС, привести пример ее применения для создания специализированных процессоров.
9. Описать технологию проектирования систолических алгоритмов для нечисловой обработки данных на примере поиска кратчайших путей в графе.
10. Описать технологию проектирования систолических алгоритмов, построить пример систолического алгоритма умножения матриц.
11. Охарактеризовать модель мелкозернистого параллелизма – клеточно-нейронная сеть. Показать пример использования модели для решения слабо формализованных 12. Описать принципы конструирования матричных схем, разобрать пример построения матричного умножителя.
13. Оценить достоинства и недостатки известных систем имитационного моделирования клеточных алгоритмов и структур.
14. Описать клеточную технологию конструирования конвейерных алгоритмов арифметических операций, ориентированную на реализацию в 3D СБИС.
15. Описать принципы построения программных систем с открытой архитектурой и основные технологии для их построения.
16. Дать классификацию доступных систем моделирования и привести их основные 17. Описать классы языков моделирования и рассмотреть примеры подобных языков.
4.5. Примерная тематика рефератов, курсовых работ.
1. Реализовать возможность использования форматов данных приложений графических редакторов (форматы bmp, png, jpg, gig), электронных таблиц (форматы xls, csv) в виде конверторов в стандартные для WinALT форматы или в виде внешних модулей WinALT.
2. Разработать внешние модули системы WinALT для поддержки форматов представления аудио (wav) данных.
3. Разработать внешние модули системы WinALT обеспечивают разнообразные режимы отображения модельных данных, например, показ значений клеток как пиктограмм, стрелок и др.
4. Построить WinALT модель конвейерного алгоритма выполнения потока коротких сортировок (чет-нечетная перестановка) в матричном процессоре.
5. Построить WinALT модель конвейерного алгоритма умножения двоичных чисел (на основе счетчиковой схемы 3->2) в матричном процессоре.
6. Построить WinALT модель конвейерного алгоритма вычисления скалярного произведения в матричном процессоре.
7. Построить WinALT модель алгоритма визуальной криптографии.
8. Построить WinALT модель FHP газа.
9. Построить WinALT модель универсальной машины Тьюринга.
10. Построить WinALT модель клеточно-нейронной сети.
11. Построить WinALT модель ассоциативные структуры с вертикальной обработкой 12. Построить WinALT модель систолического алгоритма умножения матриц.
5. Учебно-методическое и информационное обеспечение дисциплины (курса) 5.1. Примерный перечень вопросов к зачету.
1. Классические алгоритмические системы: машина Тьюринга, алгоритм Маркова.
Основные понятия и определения.
2. Устройство одномерного автомата Неймана. Сравнение тьюринговых и неймановых вычислений на примере задачи распознавания симметрии слов.
Уменьшение трудоемкости вычислений путем их распараллеливания 3. Клеточный автомат: определение, свойства, классы, теоретическое и практическое значение.
4. Универсальные клеточные автоматы - автоматы Неймана, Кодда, Бэнкса.
5. Универсальный клеточный автомат - игра «Жизнь».
6. Клеточный автомат с окрестностью Марголуса (чередующиеся подрешетки).
Моделирование диффузии.
7. Клеточный автомат с окрестностью Марголуса (чередующиеся подрешетки).
Моделирование динамики жидкости.
8. Модель мелкозернистых вычислений - клеточно-нейронная сеть, общая характеристика.
9. Модель мелкозернистых вычислений - ассоциативный вычислитель, общая характеристика.
10. Модель мелкозернистых вычислений - систолическая структура, общая характеристика.
11. Обобщенная модель распределенных вычислений - Алгоритм Параллельных Подстановок. Происхождение модели, общая характеристика.
12. Сеть Петри - модель поведения параллельной системы.
13. Параллельная граф-схема алгоритма и ее представление сетью Петри.
14. Асинхронная композиция алгоритмов параллельных подстановок (АПП).
Построение управляющего АПП по сети Петри. Композиционное расширение 15. Интерпретация алгоритма параллельных подстановок сетью автоматов. Процедура построения сети.
16. Компьютерное моделирование клеточных вычислений. Сравнительный анализ известных систем имитационного моделирования клеточных автоматов и их расширений.
17. Основные этапы построения имитационной модели в системе WinALT.
18. Операторы языка системы WinALT. Структура моделирующей программы.
19. Назначение и возможности средств редактирования текстов моделирующих программ в системе WinALT.
20. Назначение и возможности графической среды системы WinALT.
21. Выполнение и отладка модели в системе WinALT.
5.2. Примерный перечень билетов к экзамену по всему курсу.
Билет 1.
1. Клеточный автомат: определение, свойства, классы, теоретическое и практическое 2. Компьютерное моделирование клеточных вычислений. Структура и основные характеристики системы имитационного моделирования WinALT.
Билет 2.
1. Алгоритм параллельных подстановок. Основные понятия: клеточный массив, конфигурация, классификация конфигураций, параллельная подстановка.
2. Возможности средств редактирования текстов моделирующих программ в системе Билет 3.
1. Интерпретация алгоритма параллельных подстановок сетью автоматов. Процедура 2. Описание основных операторов языка системы WinALT. Структура моделирующей Билет 4.
1. Подклассы и расширения алгоритмов параллельных подстановок.
2. Создание проекта в системе WinALT.
Билет 5.
1. Асинхронная композиция алгоритмов параллельных подстановок. Построение управляющего АПП на базе сети Петри. Композиционное расширение АПП.
2. Меню и панели инструментов системы WinALT.
Билет 6.
1. Сеть Петри - модель поведения параллельной системы. Параллельная граф-схема алгоритма и ее представление сетью Петри.
2. Архитектура параллельной версии системы WinALT.
Билет 7.
1. Декомпозиция алгоритма параллельных подстановок и расслоение клеточной 2. Выполнение и отладка имитационной модели в системе WinALT.
Билет 8.
1. Пространственно-временные и синхронно-асинхронные преобразования алгоритмов параллельных подстановок.
2. Компьютерное моделирование клеточных вычислений. Сравнительный анализ известных систем имитационного моделирования клеточных автоматов и их Билет 9.
1. Универсальные клеточные автоматы: автомат Бэнкса, игра «Жизнь».
2. Архитектура сетевой версии системы WinALT.
Билет 10.
1. Клеточный автомат с окрестностью Марголуса. Моделирование физических процессов: диффузии, динамика жидкости.
2. Средства модульности и расширения возможностей языка системы WinALT.
Билет 11.
1. Корректность систем параллельных подстановок – основные проблемы.
2. Клеточная технология проектирования архитектуры спецпроцессора.
5.3.
Не более 10 источников.
1. Тоффоли Т., Марголус Н. Машины клеточных автоматов. - М.: Мир, 1991, 278 с.
2. Dieter A. Wolf-Gladrow. Lattice-Gas Cellular Automata and Lattice Boltzmann Models:
An Introduction / Editors: A. Dold, Heidelberg,F. Takens, Groningen, B. Teissier, Paris.
Lecture Notes in Mathematics. Berlin: Springer-Verlag, 2000, 1725. – 273 р.
3. Andrew Ilachinski. Cellular Automata. A Discrete Universe. - Singapore, World Scientific, 2001. – 808 p.
4. Achasova S., Bandman O., Markova V. and Piskunov S. Parallel Substitution Algorithm.
Theory and Application. - Singapore:World Scientific, 1994, 220 р.
5. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990, 226 с.
6. Специализированные процессоры для высокопроизводительной обработки данных / Под ред. В.Е. Котова, Н.Н. Миренкова. - Новосибирск: Наука. Сибирское отделение, 1988, 203 с.
«