ПРОЕКТ ПРОГРАММЫ ДИСЦИПЛИНЫ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение высшего профессионального образования
«Новосибирский государственный университет» (НГУ)
Факультет информационных технологий
УТВЕРЖДАЮ
_______________________
"_____"_______________20__ г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«Разработка и моделирование мелкозернистых устройств и процессов»
Магистерская программа
552802 «Высокопроизводительные вычислительные системы»
НАПРАВЛЕНИЕ ПОДГОТОВКИ 230100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
Квалификация (степень) выпускника
Магистр
Форма обучения очная
Новосибирск
2011
Программа дисциплины «Разработка и моделирование мелкозернистых устройств и процессов»» составлена в соответствии с требованиями ФГОС ВПО к структуре и результатам освоения основных образовательных программ магистратуры по «Профессиональному циклу. Дисциплины по выбору студента» по направлению подготовки «Информатика и вычислительная техника», а также задачами, стоящими перед Новосибирским государственным университетом по реализации Программы развития НГУ.
Автор: , к. т.н., доцент по специальности 05.13.15 – вычислительные машины и системы.
Факультет информационных технологий
Кафедра Параллельных вычислений.
1. Цели освоения дисциплины
Целью освоения дисциплины «Разработка и моделирование мелкозернистых устройств и процессов» является обучение теоретическим и практическим знаниям формальных методов, языковых и инструментальных средств синтеза глубоко параллельных мелкозернистых устройств и процессов, включающее: а) изучение формальных моделей мелкозернистых (клеточных) вычислений, б) систематизацию знаний об обобщенной модели мелкозернистых вычислений – алгоритме параллельных подстановок (АПП), в) освоение клеточной технологии конструирования имитационных моделей мелкозернистых устройств и процессов, основанной на формальных и эвристических эквивалентных преобразованиях АПП и системе имитационного моделирования WinALT, г) разработку и исследование моделей мелкозернистых устройств и процессов с помощью системы имитационного моделирования WinALT, д) освоение технологии построения библиотек для расширения функциональности системы с использованием языков Си, Си++. Освоив дисциплину обучающийся приобретает теоретические и практические знания по конструированию имитационных моделей с мелкозернистым параллелизмом не только клеточных автоматов и их расширений (прежде всего для описания нелинейных процессов в физике, биологии, социологии и т. д.), но и матричных, и конвейерных (включая систолические) архитектур, мультимикропроцессорных архитектур, ассоциативных процессоров, клеточно-нейронных сетей, однородных перестраиваемых вычислителей.
2. Место дисциплины в структуре магистерской программы
Дисциплина входит в число дисциплин по выбору профессионального цикла образовательной программы магистра. Изучение данной дисциплины основывается на базовых знаниях студента, поступающего в магистратуру, включая курсы «Вычислительная математика», «Математическая логика и теория алгоритмов», «Логические основы программирования», «Объектно-ориентированное программирование», «Операционные системы», «Основы параллельного программирования», «Методы трансляции и компиляции». Студент должен уметь использовать основные законы естественнонаучных дисциплин для понимания преподаваемой дисциплины, иметь навыки работы с компьютером как средством управления и обработки информации, знать языки программирования Си, Паскаль, уметь работать в ОС Windows и разрабатывать программы для платформы Win32. Знания, полученные при освоении дисциплины, могут быть использованы при параллельном освоении курсов «Формальные модели параллельных вычислений», "Современные проблемы информатики и вычислительной техники", "Технология разработки программных систем".
3. Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля) Изучение дисциплины направлено на формирование следующих общекультурных компетенций ОК-1, ОК-2, ОК-4, ОК-6, ОК-7, ОК-8 и профессиональных компетенций ПК-1, ПК-2, ПК-4, ПКС-8, ПКС-9, ПКС-14 выпускника.
В результате освоения дисциплины обучающийся должен:
· Знать: о применимости моделей с мелкозернистым параллелизмом в самых различных областях – от исследования архитектур вычислительных устройств, до решения задач из естественных наук; понятие параллельной алгоритмической системы – клеточный автомат, понятие обобщенной алгоритмической системы – алгоритм параллельных подстановок (АПП); методы асинхронной композиции АПП; виды некорректности АПП в синхронной и асинхронной модах исполнения и методы их распознавания; методы пространственно-временных и структурных эквивалентных преобразований АПП; архитектуру и основные характеристики системы имитационного моделирования мелкозернистых алгоритмов и структур – WinALT; основные приемы конструирования моделей параллельных процессов, представленных в виде АПП, в системе WinALT; способы и средства расширения функциональных возможностей системы WinALT с целью ее адаптации к новой предметной области; концепцию построения программных систем с открытой архитектурой.
· Уметь: разрабатывать алгоритмы с мелкозернистым параллелизмом для представления вычислительных процессов в информатике и технической физике; строить компьютерные модели мелкозернистых алгоритмов и структур в широком спектре приложений в информатике и технической физике с использованием системы WinALT; разрабатывать внешние библиотеки, расширяющие функциональные возможности системы WinALT использовать библиотеки для построения сложных моделей из библиотечных элементов;
· Владеть: основами клеточной технологии конструирования моделей с мелкозернистым параллелизмом, средствами компьютерным моделированием клеточных вычислений, способами и средствами расширения функциональных возможностей системы WinALT.
4. Структура и содержание дисциплины (модуля) «Разработка и моделирование мелкозернистых устройств и процессов»
Общая трудоемкость дисциплины составляет 5 зачетных единиц, 180 часов.
№ п/п | Разделы дисциплины | Семестр | Недели семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (часы) | Контроль успеваемости (по неделям семестра). Промежуточная аттестация (по семестрам)
| ||||
Лекции | Семинары | Практ. занятия. | Самост. работа | Сумма | |||||
1 | ВВЕДЕНИЕ | 2 | 1 | 2 | 2 | ||||
2 | ФОРМАЛЬНЫЕ МОДЕЛИ МАССОВЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ | 2 | 2 | 2 | 4 | 6 | |||
3 | ОБОБЩЕННАЯ МОДЕЛЬ МЕЛКО-ЗЕРНИСТЫХ ВЫЧИСЛЕНИЙ -- АЛГОРИТМ ПАРАЛЛЕЛЬНЫХ ПОДСТАНОВОК (АПП) | 2 | 3-4 | 4 | 4 | 4 | 12 | ||
4 | СИСТЕМА ИМИТАЦИОННОГО МОДЕЛИ - РОВАНИЯ WINALT | 5-7 | 4 | 4 | 4 | 6 | 18 | ПЗ1(6) | |
5 | ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ АПП | 2 | 8-11 | 4 | 4 | 4 | 6 | 18 | ПЗ2(8), ПЗ3(10) |
6 | АСИНХРОННАЯ КОМПОЗИЦИЯ АПП | 2 | 12-16 | 4 | 8 | 6 | 8 | 26 | ПЗ4(15) |
7 | АПП - ИНСТРУМЕНТ ПРОЕКТИРОВАНИЯ АРХИТЕКТУРЫ МЕЛКОЗЕРНИСТОГО УСТРОЙСТВА | 3 | 1-4 | 4 | 4 | 6 | 8 | 22 | ПЗ5(3) |
8 | ЯЗЫКОВЫЕ СРЕДСТВА и ГРАФИЧЕСКАЯ СРЕДА СИСТЕМЫ WINALT | 3 | 5-8 | 6 | 6 | 6 | 8 | 26 | ПЗ6(7) |
9 | ОСНОВЫ КЛЕТОЧНОЙ ТЕХНОЛОГИИ КОНСТРУИРОВАНИЯ МОДЕЛЕЙ | 3 | 9-12 | 4 | 6 | 6 | 8 | 24 | ПЗ7(11) |
10 | ПОСТРОЕНИЯ БИБЛИОТЕК ИМИТАЦИОННЫХ МОДЕЛЕЙ | 3 | 13-16 | 6 | 6 | 6 | 8 | 26 | ПЗ8(15) КР (15,16) З (16) |
Всего часов | 40 | 42 | 38 | 60 | 180 |
А) Лекции
Разделчас) Введение. Исследование физических и информационных процессов в клеточном пространстве. Две тенденции (теоретическая и прикладная) в развитии клеточных вычислений. Клеточная технология вычислений. Задачи синтеза клеточных алгоритмов и устройств с массовым пространственно-временным параллелизмом.
Разделчаса) Формальные модели массовых параллельных вычислений. Клеточный автомат: основные определения. Универсальные клеточные автоматы. Нейронные и клеточно-нейронные сети, ассоциативные машины, систолические структуры, однородные вычислительные структуры.
Разделчаса). Обобщенная модель мелкозернистых вычислений - алгоритм параллельных подстановок (АПП). Происхождение модели и ее основные черты. Базовые понятия: клеточный массив, конфигурация, параллельная подстановка, система параллельных подстановок. Синхронная и асинхронная моды выполнения системы параллельных подстановок. Понятие АПП. Подклассы и расширения АПП. Интерпретация АПП сетью автоматов.
Разделчаса). Система имитационного моделирования WINALT. Принципы построения системы. Архитектура системы. Назначение и характеристика подсистем. Графический образ системы. Описание сайта системы. Введение в технологию конструирования моделей в системе WinALT.
Разделчаса). Эквивалентные преобразования АПП. Пространственно-временные и синхронно-асинхронные преобразования алгоритмов параллельных подстановок. Преобразование двумерных алгоритмов параллельных подстановок в трехмерные (методы расслоения).
Разделчаса). Асинхронная композиция АПП. Способы представления и описания асинхронного параллельного управления. Граф-схема взаимодействия параллельных процессов. Моделирование управления сетью Петри. Представление сети Петри в виде алгоритма параллельных подстановок. Композиционное расширение алгоритма параллельных подстановок, способы получения композиционных расширений. Представление асинхронной композиции сетью автоматов.
Разделчаса). АПП - инструмент проектирования архитектуры мелкозернистого устройства. Общая схема проектирования архитектуры клеточного устройства по его алгоритмическому описанию. Архитектура двумерных и трехмерных клеточных устройств. Примеры возможной реализации клеточных устройств в виде трехмерных (многослойных) электрооптических СБИС с простой топологией отдельного слоя и массовыми межслойными оптическими связями.
Разделчаса). Языковые средства и графическая среда системы WINALT.
Общий обзор. Моделирующая программа. Средства параллельного программирования (воплощение АПП). Средства последовательного структурного программирования. Объединение средств параллельной и последовательной частей языка. Средства редактирования текстов. WinALT – система визуального программирования. Окно «Дерево проекта». Меню. Панели инструментов. Основные диалоги. Вспомогательные окна. Средства визуального конструирования и модификации графических образов данных модели и моделирующих программ.
Разделчаса). Основы клеточной технологии конструирования моделей. Создание проекта в системе. Создание полотен (файлов) с клеточными объектами и моделирующими программами. Режимы выполнения и отладки модели. Примеры проектов в области классических клеточных автоматов, клеточно-нейронных сетей, многоступенчатых микроконвейеров, искусственной жизни, имитации физических процессов. Синтез архитектур 3D спецпроцессоров с оптическими межсоединениями.
Раздел часа). Разработка библиотек системы WINALT. Средства модульности и расширения возможностей языка. Конструирование библиотек имитационных моделей. Построение сложных имитационных моделей с использованием библиотечных элементов.
Б) Практические занятия (лабораторные работы)
Лабораторная работачаса) Освоение среды моделирования.
Выполняется освоение инструментов системы по созданию проекта имитационной модели, набора полотен для размещения графических и текстовых объектов модели, редактированию и просмотру клеточных объектов, редактированию, исполнению и отладке моделирующих программ. Разбирается создание демонстрационного проекта «с нуля» в режиме «шаг за шагом».
Лабораторная работа 2. (4 часа) Универсальные клеточные автоматы.
Цель - ознакомление с возможностями клеточных автоматов игра «Жизнь» и автомат Бэнкса как универсальных конструкторов вычислительных устройств (сетей из логических вентилей). Подробно разбирается построение имитационных моделей клеточных автоматов: игра «Жизнь», автомат Бэнкса, по их описаниям с использованием операторов in, at, do языка моделирования.
Лабораторная работа 3. (4 часа) Построение моделей нелинейных процессов в клеточном пространстве.
Освоение графических и программных средств представления нелинейных динамических процессов в системе WinALT. Подробно разбирается использование наряду с операторами in, at, do операторов on, step, delay для построение имитационных моделей клеточных автоматов: Гриффита и автомата с окрестностью Марголуса по их описаниям, также строятся тесты для этих операторов для различных вариантов используемых в них параметров.
Лабораторная работа 4. (6 часов) Построение моделей информационных процессов в 2D и 3D композициях клеточных массивов.
Освоение конструкций языка, позволяющих описывать сложные преобразования в неоднородном клеточном пространстве (векторные подстановки, функциональные подстановки, смешанные подстановки, а также всевозможные композиции подстановок указанных видов), использовать виртуальные массивы – подмассивы родительских массивов, как самостоятельные массивы в операторах языка моделирования.
Лабораторная работа 5. (4 часа) Построение интерфейсов в системе WinALT.
Освоение способов конструирования с использованием языковых средств системы пользовательских меню, диалогов, окон с графиками и диаграммами для задания параметров графической среды, управления процессом моделирования.
Лабораторная работа 6. (6 часов) Написание ACL библиотеки функций.
Цель – освоение технологии интеграции внешних библиотек, написанных на ЯВУ Си, Си++ в среду моделирования. Осваивается технология построения по прототипу внешней библиотеки на языках Си, Си++ с использованием среды VS2008 Express Edition. Подключение библиотеки к среде и использование ее функций в моделирующей программе.
Лабораторная работа 7. (4 часа) Композиции моделей.
Освоение технологий 1) построения библиотеки фрагментов моделей, которые описываются на языке системы и 2) сборки составных моделей из библиотечных элементов на примере сборки АЛУ из библиотечных фрагментов конвейерных реализаций арифметических операций.
Лабораторная работа 8. (6 часов) Технология расширения функциональных возможностей системы моделирования.
Освоение технологии расширения среды моделирования новыми режимами моделирования (синхронный, полностью асинхронный, разнообразные блочно-асинхронные), новыми режимами визуализации (показ нестандартных сеток, показ клеток с помощью пиктограмм и т. д.) и поддержки новых форматов данных с использованием внешних модулей, написанных на ЯВУ Си, Си++.
В) Семинары.
1. Обязательные выступления студентов с докладами по темам рефератов. Список тем приведен в разделе 6 данной программы.
2. Обязательные выступления студентов с докладами по темам курсовых работ. Список тем приведен в разделе 6 данной программы.
3. Темы, связанные с изучением системы WinALT и самостоятельной работой расширяющей рамки лабораторных работ:
а). Изучение операторов поддержки АПП, средств параллельного исполнения блоков операторов. Ознакомление с операторами параллельно-последовательной композиции и вспомогательными операторами. Изучение библиотек реализации синхронного, асинхронного и смешанного режимов моделирования.
б). Освоение техники представления архитектуры имитационной модели в системе WinALT. Освоение средств описания пользовательских окон, диалогов и их элементов, средств отрисовки графики. Выработка стиля оформления и документирования моделей.
в). Изучение механизмов импорта внешних библиотек и подпрограмм, написанных на языках Си/Си++. Освоение методики подключения внешних стандартных библиотек к системе WinALT и их использования из моделирующих программ. Изучение событийно-ориентированных механизмов расширения функциональности системы WinALT на базе средств, предоставляемых собственной библиотекой системы (4 часа).
5. Образовательные технологии
При разработке образовательной технологии основной упор сделан на соединение активной и интерактивной форм обучения, с переносом «центра тяжести» в интерактивную форму обучения. Технологическая цепочка изучения курса построена по следующей схеме.
Лекционный материал включает в себя все темы, перечисленные в структуре курса. Курс в существенной степени основан на оригинальных работах, выполняемых в течение ряда лет в лаборатории параллельных алгоритмов и структур ИВМ и МГ СО РАН и связанных с темой «Исследованием физических и информационных процессов с использованием моделей мелкозернистого параллелизма». Основу курса составляет изучение алгоритмической системы – АПП (Achasova S., Bandman O., Markova V., Piskunov S. Parallel Substitution Algorithm. Theory and Application, 1994. Singapore: World Sci., 220 p.) и методов эквивалентных преобразований АПП (3D лазерные информационные технологии / Отв. редактор , 2003, Новосибирск, 550 с.). Изложение лекций предполагает диалог со слушателями. В начале каждой лекции выделяется 15 минут для напоминания содержания предыдущей лекции и ответов на вопросы студентов. В конце лекции также выделяется 15 минут для ответов на вопросы по текущему материалу и его обсуждения. Презентация каждой лекции пересылается магистрантам по электронной почте и сопровождается списком вопросов, которые позволяют магистранту проверить степень усвоения лекционного материала. Дополнительно студент может получить разъяснения преподавателя по электронной почте или скайпу.
Лекционное изложения материала сочетается с выполнением лабораторных работ с использованием системы имитационного моделирования мелкозернистых алгоритмов и структур WinALT, разработанной в лаборатории параллельных алгоритмов и структур ИВМ и МГ СО РАН и доступной на сайте http://winalt. *****. Лабораторный практикум разделен на две части. Выполнение работ первой группы закрепляет базовые навыки владения языковыми и графическими средствами системы WinALT. Выполнение работ второй группы, в первую очередь, научает магистранта строить модули с использованием собственного языка системы и языков C и C++ и встраивать их в систему WinALT. Типичное назначение модулей - интерфейсы для новых прикладных областей. Разработка моделей и модулей выполняется как на персональных компьютерах магистрантов, так и на вычислительных средствах отдела МОВВС ИВМ и МГ СО РАН с использованием образцов моделей и модулей, представленных соответственно в библиотеках моделей и внешних библиотеках системы WinALT на сайте http://winalt. *****. Если выполнение лабораторной работы предполагает построение имитационной модели, то эта модель должна быть размещена на сайте системы и быть доступна другим магистрантам для ее оценки, сравнения с другими моделями.
Самостоятельная работа делится на три части. Первая часть состоит в выполнении небольших заданий, расширяющих рамки лабораторных работ и нацеленных на привитие навыков самостоятельного освоения программных продуктов. Вторая часть (второй семестр) состоит в подготовке реферата и презентации в рамках основных идей курса по теме, которая либо не рассматривалась в курсе, либо будет рассмотрена в реферате более углубленно с использованием материала книг и статей. Точкой контроля является выступление студента на семинарских занятиях, ответы на вопросы, умение отстаивать собственную точку зрения в процессе обсуждения выступления участниками этих занятий. Совокупность докладов детализирует ряд тем курса. Лекции преподавателя, доклады и презентации, созданные студентами, образуют блоки, из которых собирается электронный образ курса, доступный каждому обучающемуся. Таким образом, получается вариант курса, в формировании дополнительной части которого активное участие принимают студенты. Третья часть (третий семестр) состоит в выполнении курсовой работы. Задача выполнения курсовой работы – не только привить магистранту навыки самостоятельной работы по созданию и исследованию имитационных моделей в избранной предметной области, но и сделать его активным участником процесса расширения функциональных возможностей системы WinALT, которая является системой со свободным доступом. Магистранту предоставляется возможность встраивания в систему WinALT модулей, обеспечивающих организацию библиотек имитационных моделей, их использование для конструирования новых моделей, модулей, обеспечивающих взаимодействие пользователей в сетевой среде, модулей, расширяющих функциональные возможности системы WinALT в связи с появлением новых разновидностей или классов мелкозернистых алгоритмов и структур, режимов функционирования моделей, визуализации вычислительного процесса и т. д. Каждая курсовая работа докладывается и защищается на семинарском занятии в конце семестра с участием студентов группы. Обязательное условие положительной оценки при защите курсовой работы – наличие работающей имитационной модели, либо библиотеки имитационных моделей, либо внешних модулей системы WinALT, оформленных в соответствии со стандартами системы WinALT.
При выполнении самостоятельной работы магистранту не только предоставляется доступ к информационным ресурсам системы WinALT, но и возможность выполнить пополнение ее информационного пространства дополнительными легальными материалами (электронные статьи, книги, рефераты, отчеты, Интернет ссылки и т. п.) по тематике курса.
Выше представлена организация базовой части курса, но он также предоставляет магистранту дополнительные возможности по изучению параллельных вычислений. Эти возможности нацелены на привитие магистранту навыков публичных выступлений и командной работы, опыта общения и участия в дискуссиях. Магистранты, изучающие курс «Разработка и моделирование мелкозернистых устройств и процессов» принимают обязательное участием в работе постоянно действующего (один раз в неделю) объединенного семинара «Математическое и архитектурное обеспечение параллельных вычислений» двух лабораторий – параллельных алгоритмов и структур и синтеза параллельных программ ИВМ и МГ СО РАН, и двух кафедр - параллельных вычислительных технологий НГТУ и НГУ. К работе в семинаре привлекаются ведущие специалисты в области теории и приложений параллельных вычислений. Участие в работе семинара является действенной формой обучения магистрантов профессиональным компетенциям, связанным в первую очередь с научно-исследовательской деятельностью. Магистрантам также предоставлена возможность выступать с докладами по тематике курса на традиционной конференции молодых ученых, проводимой ежегодно в апреле, в ИВМ и МГ СО РАН. Программный комитет конференции, включающий ведущих ученых ИВМ и МГ СО РАН, выполняет отбор докладов. Предусмотрено премирование студентов, занявших первые три места в своей секции. Как правило, это – секция «Информатика и телекоммуникации». Для магистрантов является обязательным участие в проекте, связанном с мелкозернистым параллелизмом, зимней и летней школ (http://ssd. *****/school/index. html), прослушивание лекций и участие в дискуссиях. Школы проводятся кафедрой ПВ НГУ. Участие в проекте означает, что студенты, разбившись на небольшие группы по 2-3 человека, в тесном взаимодействии между собой и с преподавателем, выполняют построение и исследование имитационных моделей мелкозернистых процессов и устройств, для предложенных в проекте предметных областей.
В целом, объем занятий, проводимых в интерактивной форме, составляет порядка 70 процентов от объема всех занятий.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
Приняты три вида самостоятельных работ. Первый вид - выполнение небольших заданий, расширяющих рамки лабораторных работ. Эти работы сопутствуют выполнению лабораторных работ и предъявляются при их защите. Второй вид – подготовка реферата и презентации по выбранной обучающимся теме.
Для выполнения самостоятельной работы студентам обеспечивается доступ к информационным ресурсам курса. Каждый обучающийся имеет сетевой доступ к базам данных и библиотечным фондам, представленных на сервере отдела МО ВВС ИВМ и МГ СО РАН, и к электронным материалам информационного пространства системы WinALT, включающего: а) презентации лекций по курсу «Разработка и моделирование мелкозернистых устройств и процессов б) описания лабораторных работ и средств доступа к сетевым и вычислительным ресурсам ИВМ и МГ СО РАН, в) описание внешних библиотек системы WinALT и технологии их пополнения с использованием прототипов, г) описание документации системы WinALT, д) инструкцию по установке системы WinALT, е) описание библиотек имитационных моделей и технологии их пополнения, з) список литературы, включающий книги, журналы, труды конференций.
Контролирующие материалы включают набор заданий для самостоятельной работы, списки вопросов для защиты лабораторных работ, сдачи зачета, перечень тем рефератов и курсовых работ. Текущий и промежуточный контроль осуществляется на основе бально-рейтинговой системы, принятой в образовательной программе.
Вопросы к лабораторным работам.
1. Каковы этапы построения проекта в системе WinALT. Какие задачи решаются на каждом из них.
2. Какие средства редактирования и упорядочения расположения клеточных объектов на полотне присутствуют в системе.
3. Каковы основные функции текстового редактора в системе WinALT.
4. Каковы этапы построения имитационной модели. Какие задачи решаются на каждом из них.
5. Описать структуру моделирующей программы и назначение ее разделов.
6. Какие типы данных используются в языке системы для задания состояний клеток.
7. Какова семантика синхроблоков ex – end, ch – end, cl – end, substitution-begin-end.
8. Как устроен оператор параллельной подстановки. Какова семантика операторов in, at, do.
9. Какие панели инструментов и меню для построения клеточных объектов присутствуют в системе WinALT, какие можно выделить группы операций по работе с клеточными объектами.
10. Какие панели инструментов и меню используются для запуска, отладки и исполнения моделирующих программ.
11. Какие языковые средства используются в системе WinALT для описания последовательных вычислений.
12. Конструкции языка моделирования, которые применяются при построении моделей классических клеточных автоматов.
13. Какова семантика операторов on, step, shift, delay.
14. Какие конструкции языка моделирования, используются при описании автоматов с окрестностью Марголуса.
15. Какие типы параллельных подстановок присутствуют в языке системы, какие у них общие свойства и в чем их различия.
16. Как задается композиция клеточных массивов в языке системы. Как создается и применяется виртуальный клеточный массив.
17. Каково назначение оператора синхронного присваивания let. В чем заключаются его отличия от 1) классического оператора присваивания, 2) операторов параллельной подстановки.
18. Как объединяются параллельная и последовательная части языка при конструировании имитационной модели.
19. Какова семантика операторов импорта include, import и use.
20. Каково назначение утилиты stg.
21. Какие форматы данных представлены в библиотеке форматы данных системы.
22. Какой набор функций реализован в библиотеке языковых функций.
23. Какие сервисные функции включены в библиотеку модельных подпрограмм.
24. Каков состав и набор функций инструментов для генерации интерфейсного кода внешних ACL библиотек.
25. Какие средства языка моделирования обеспечивают возможность параметризации фрагментов моделей из библиотек
26. Какой набор интерфейсных функций характерен для модуля реализации формата данных.
27. Какой набор интерфейсных функций характерен для модуля реализации режима визуализации.
28. Какой набор интерфейсных функций характерен для модуля реализации режима моделирования.
Задания для самостоятельной работы к лабораторному практикуму.
1. Выполнить создание 3D (многослойных) клеточных объектов.
2. Выполнить создание клеточных объектов с разными типами данных.
3. Выполнить установку клеток клеточного объекта в состояния с различными типами данных.
4. Освоить средства редактирования клеточных объектов.
5. Изучить пользовательские функции управления размером и расположением клеточных объектов на полотне.
6. Изучить функции работы с цветовой палитрой для отображения значений клеточных объектов.
7. Освоить средства редактирования текстов моделирующих программ.
8. Реализовать имитационную модель автомата Игра «Жизнь» на плоской гексагональной решетке.
9. Реализовать имитационную модель автомата Игра «Жизнь» в 3D клеточном пространстве.
10. Реализовать в клеточном пространстве автомата Игра «Жизнь» логические элементы компьютера.
11. Реализовать в клеточном пространстве автомата Бэнкса логические элементы компьютера.
12. Собрать из логических элементов в клеточном пространстве автомата Игра «Жизнь»/автомат Бэнкса вычислительное устройство «сумматор».
13. Собрать из логических элементов в клеточном пространстве автомата Игра «Жизнь» вычислительное устройство «мультиплексор».
14. Собрать из логических элементов в клеточном пространстве автомата автомат Бэнкса вычислительное устройство «мультиплексор».
15. Выполнить переход от автомата с окрестностью Марголуса к автомату с окрестностью Неймана или Мура.
16. Построить тесты для операторов ex, ch, cl, in, at, do.
17. Построить тесты для операторов on, step, shift.
18. Выполнить тестирование оператора let.
19. Выполнить тестирование виртуальных массивов.
20. Выполнить тестирование векторных и функциональных подстановок.
21. Выполнить тестирование последовательных операторов языка моделирования.
22. Построить примеры простых моделей, в которых используются все библиотеки системы WinALT.
Перечень примерных тем рефератов.
Сравнение неймановских и тьюринговых вычислений. Клеточный автомат - модель пространственно-распределенной динамической системы (изучение явлений: упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др.). Варианты клеточных автоматов: универсальные, асинхронные, вероятностные. Вычисления в клеточных автоматах. Самовоспроизведение (искусственная жизнь) в клеточных автоматах. ПЛИС, области применение, примеры применений. Ассоциативные структуры с вертикальной обработкой информации (типа STARAN). Систолические алгоритмы и структуры и их применения. Тьюрмиты и их возможное применение для описания взаимодействующих процессов в клеточном пространстве. Клеточно-нейронные сети, использование для решения слабо формализованных задач. Вычисления на ДНК. Квантовые вычисления и компьютеры. Мелкозернистые модели физических явлений. Вычисление булевских функций в итеративных структурах. Однородные вычислительные структуры. Параллельные вычисления и сети Петри. Корректность АПП. Распознавание некорректности АПП. Алгоритмы анализа свойств сетей Петри. Клеточная технология проектирования архитектуры спецпроцессора. Клеточная технология конструирования конвейерных алгоритмов арифметических операций, ориентированная на реализацию в 3D СБИС. Мультиагентный подход в имитационном моделировании клеточных автоматов. Обзор систем имитационного моделирования клеточных автоматов и их расширений. Классификация языков моделирования. Технологии построения программных систем с открытой архитектурой.Примечание. Приветствуются предложения студентами собственных тем рефератов по проблематике курса.
Примерная тематика курсовых работ.
1. Конструирование библиотеки WinALT моделей ассоциативных структур с вертикальной обработкой информации (min, max, сравнение с эталоном и другие по выбору студента).
2. Конструирование библиотеки WinALT моделей алгоритмов визуальной криптографии (визуальная пороговая схема разделения секрета, модификации моделей визуальной криптографии по работе с серыми и цветными изображениями, и другие по выбору студента).
3. Построение и исследование WinALT модели FHP газа на двумерной гексагональной решетке с библиотекой профилей для обтекания.
4. Конвертирование форматов данных приложений графических редакторов (форматы bmp, png, gif, pcx), электронных таблиц (формат xls, odf) в стандартные для WinALT форматы.
5. Построение внешних модулей системы WinALT для поддержки форматов данных графических редакторов (форматы jpg, gig), электронных таблиц (формат csv).
6. Построение внешних модулей системы WinALT для поддержки форматов представления аудио (wav, mp3) данных.
7. Построение внешних модулей системы WinALT обеспечивающих разнообразные режимы отображения модельных данных (показ значений клеток как пиктограмм, стрелок и др.).
8. Построение и исследование WinALT модели клеточно-нейронной сети для восстановления искаженных образов.
9. Построение внешних библиотек для ввода данных в имитационную модель из видео потока (файлы с видеоданными в форматах mpg, avi, wmv) и вывода результатов работы модели в видео поток.
10. Интеграция внешних свободно распространяемых библиотек в систему WinALT по следующим направлениям: обработка сигналов, системы распознавания образов, обработка мультимедиа данных, по выбору студента.
11. Реализация расширений подсистемы визуализации среды моделирования для обеспечения возможностей визуализации 3D данных в стерео режимах с использованием оборудования nVidia, ViewSonic.
12. Построение и исследование WinALT моделей 2D и 3D многоступенчатых конвейеров арифметических операций.
13. Построение и исследование WinALT модели асинхронного алгоритма управления динамически перестраиваемым многоступенчатым конвейером.
14. Построение и исследование WinALT моделей многослойных оптико-электронных структур.
15. Построение библиотеки WinALT моделей «Искусственная жизнь» (вариации алгоритмов Лангтона, Сиппера, другие по предложению студентов).
16. Построение библиотеки однородных структур (альфа-структура, ипсилон-структура и другие структуры из книги Я. И Фета «» по выбору студента).
17. Построение библиотеки WinALT 2D и 3D моделей операций быстрой и векторно-матричной арифметики.
Примечание. Приветствуются предложения студентами собственных тем курсовых работ по проблематике курса.
Примерный перечень вопросов к зачету.
1. Клеточный автомат: определение, свойства, классы, теоретическое и практическое значение.
2. Сравнение тьюринговых и неймановых вычислений на примере задачи распознавания симметрии слов. Уменьшение трудоемкости вычислений путем их распараллеливания.
3. Универсальные клеточные автоматы - автоматы Неймана, Кодда, Бэнкса. Определения, сложность автоматов.
4. Универсальный клеточный автомат - игра «Жизнь».
5. Клеточный автомат с окрестностью Марголуса. Моделирование физических процессов: диффузии, динамика жидкости.
6. Модели мелкозернистых вычислений: клеточно-нейронная сеть, ассоциативный вычислитель, систолическая структура; общая характеристика, области применения.
7. Обобщенная модель мелкозернистых вычислений - Алгоритм Параллельных Подстановок (АПП). Основные понятия: клеточный массив, конфигурация, классификация конфигураций, параллельная подстановка.
8. Подклассы и расширения АПП.
9. Корректность систем параллельных подстановок – основные проблемы.
10. Сеть Петри - модель поведения параллельной системы. Параллельная граф-схема алгоритма и ее представление сетью Петри.
11. Асинхронная композиция АПП. Построение управляющего АПП по сети Петри. Композиционные расширения АПП.
12. Интерпретация АПП сетью автоматов. Процедура построения сети.
13. Декомпозиция АПП и расслоение клеточной структуры.
14. Пространственно-временные и синхронно-асинхронные преобразования АПП.
15. Сравнительный анализ известных систем имитационного моделирования клеточных автоматов и их расширений.
16. Архитектура и основные характеристики системы имитационного моделирования WinALT.
17. Создание проекта в системе WinALT.
18. Меню и панели инструментов системы WinALT.
19. Основные этапы построения имитационной модели в системе WinALT.
20. Операторы языка системы WinALT. Структура моделирующей программы.
21. Средства редактирования текстов моделирующих программ в системе WinALT.
22. Графическая среда системы WinALT.
23. Выполнение и отладка имитационной модели в системе WinALT.
24. Средства модульности и расширения возможностей языка системы WinALT.
25. Внешние библиотеки системы WinALT.
Промежуточный контроль. В течение изучения дисциплины проводятся семинары с выступлениями студентов и выполняются лабораторные работы. Выполнение лабораторных работ является обязательным для всех студентов, результаты промежуточного контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете.
Текущий контроль. Для контроля усвоения дисциплины учебным планом предусмотрены зачет во третьем семестре. Для допуска к зачету необходимы два выступления на семинаре. К зачету допускаются студенты, выполнившие все лабораторные работы и защитившие курсовые работы, обязательно включающие работающие имитационные модели в системе WinALT.
7. Учебно-методическое и информационное обеспечение дисциплины (модуля) «Разработка и моделирование мелкозернистых устройств и процессов»
а) Основная литература:
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 с.
7. Tino Gramb, Stefan Bornholdt, Michael Grob, Melanie Mitchell, Thomas Pellizzari. Non-Standard Computation: Molecular Computation - Cellular Automata - Evolutionary Algorithms - Quantum Computers / WILEY-VCH, 1998. – 221 p.
8. 3D лазерные информационные технологии / Отв. редактор , 2003, Новосибирск, 550 с. (глава 4. Трехмерные интегральные схемы с оптическими межсоединениями, авторы и , С.
б) Дополнительная литература:
1. Питерсон Дж. Сети Петри и моделирование систем.- М.: Мир, 1984.
2. Дж. фон Нейман. Теория самовоспроизводящихся автоматов. - М.: Мир, 1971.
3. Методы параллельного микропрограммирования / Под ред. .- Новосибирск: Наука, Сибирское отделение, 1981.
4. Evolution of Parallel Cellular Machines: The Cellular Programming Approach, by Moshe Sipper, Springer-Verlag, Heidelberg 1997. http://www. /pcm/
5. Commentary on Edwin Roger Banks, "Information Processing and Transmission in Cellular Automata" Banks' Ph. D. thesis, 1971 (MIT, Dep't of Mechanical Engineering) By Ross Rhodes http://www. /bottom/banks/banks_commentary. htm
6. Codd E. F. Cellular Automata. - Academic Press, Inc. N. Y. and London, 1968.
7. Langton C. G. Self-replication in cellular automata // Physica D. 1984. V. 10. P. 135.
8. Reggia J. A., Armentrout S. I., Chou H.-H., Peng Y. Simple systems that exhibit self-directed replication // Science. 1993. V. 259. P. 1282.
9. Stauffer A., Sipper M. Externally controllable and destructible self-replicating loops // Lect. Notes in Artificial Intelligence. 2001. 2159. P.282.
10. , Степанцов автоматы для расчета некоторых газодинамических процессов // Журнал вычислительной математики и математической физики, 1996, том 36, N 5, с.137-145.
11. , Степанцов диффузионных процессов с помощью клеточных автоматов с окрестностью Марголуса // Журнал вычислительной математики и математической физики, 1998, том 38, N 6, с..
12. , Степанцов динамики движения толпы при помощи клеточных автоматов с окрестностью Марголуса // Известия Высших учебных заведений. Прикладная нелинейная динамика, 1997, том 5, N 5, с.75-79.
13. . Программа-конструктор клеточных самовоспроизводящихся структур. // Программирование. – 2009. - № 4. – С. 1-9.
14. . Клеточно-автоматное моделирование пространственной динамики. В кн. Системы информатики. – Новосибирск: Наука, 2006. – С.
15. , Умрихина моделирование асинхронной композиции алгоритмов с мелкозернистым параллелизмом // Научный вестник НГТУ. – 2007. - № 3 (28). – С. 51-64
16. Theory and Applications of Cellular Automata / Stephen Wolfram. - Singapore: World Scientific, 1986.
17. S. Bandini, G. Mauri (Eds). Proceedings of the Second (and Third)Conference on Cellular Automata for Research and Industry. - Milan (Trieste), Springer, 1
18. Parallel Computing Technologies: Proceedings of International Conference. - Lect. Notes Comput. Sci.; N 964, 1995, N 1277 , 1997, N 1662, 1999.
19. , , Болотов теории однородных структур. - М.: Наука, 1990.
20. и др. Однородные структуры. Анализ. Синтез. Поведение.- М.: Энергия, 1973.
21. , Косарев универсальные вычислительные системы высокой производительности.- Новосибирск: Наука. Сибирское отделение, 1966.
22. , Прангишвили автоматы с настраиваемой структурой (однородные среды). - М.: Энергия, 1974.
23. Матричные процессоры на СБИС. - М.: Мир, 1991.
24. Y. I/ Fet. Parallel Processing in Cellular Arrays. – Research Studies Press LTD, Taunton, Somerset, England, 19p.
25. , , Метод подвижных клеточных автоматов как инструмент физической мезомеханики материалов // Физическая мезомеханика. 1998. No 1. с. 95--108
26. . Клеточно-нейронные вычисления. Формальная модель и возможные применения // Программирование. 1997, № 6, С. 29-40.
27. Пискунов // АвтометрияN4, С. 47-57. АвтометрияN3, С.3-13. АвтометрияN3, С. 14-27. АвтометрияN3, С. 3-16 (совместно с ).
28. Труды конференции Parallel Computing Technologies (PaCT), 2005, Lect. Notes in Comput. Sci., Springer-Verlag, Vol. 3306; 2007, Lect. Notes in Comput. Sci., Springer-Verlag. - Vol. 4671; 2009, Lect. Notes in Comput. Sci., Springer-Verlag, Vol. 5698.
в) Программное обеспечение и Интернет-ресурсы:
Система имитационного моделирования мелкозернистых алгоритмов и структур WinALT - http://winalt. *****/ (на сайте доступен дистрибутив системы).
Библиографии по клеточным автоматам (электронные)
1. http:///bibliography/index. php (928 источников с 1953 года по 1996 год)
2. http://computacion. cs. cinvestav. mx/~acaceres/docs/tesis/node115.html (70 источников с 1936 года по 2004 год)
3. http:///ww/fr. arxiv. org/list/nlin. CG/recent?* Cellular Automata and Lattice Gases. Authors and titles for recent submissions (последние поступления).
Путеводители и справочники
1. Cellular Automata Notebooks . http://cscs. umich. edu/~crshalizi/notebooks/cellular-automata. html
2. Cellular Automata FAQ (Все про клеточные автоматы) http:///
3. Artificial Life Links and Bookmarks (есть раздел с клеточными автоматами) http://www. rennard. org/alife/english/liensgb. html
8. Материально-техническое обеспечение дисциплины (модуля)
Доступ с персональных компьютеров и ноутбуков к вычислительным и информационным ресурсам и услугам локальной сети отдела МОВВС ИВМ и МГ СО РАН, возможность выполнения лабораторных работ в терминальном классе ИВМ и МГ СО РАН.
Рецензент (ы) _________________________
Программа одобрена на заседании Методической комиссии ФИТ
от ___________ года, протокол № ________.
