Скачать 177.69 Kb.
|
![]() Национальный исследовательский университет «Высшая школа экономики» Программа дисциплины для направления/ специальности подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет компьютерных наук Департамент программной инженерии Программа дисциплины "Компиляторные технологии и верификация программ" для направления 09.03.04 «Программная инженерия» подготовки бакалавра Авторы программы: Белеванцев А.А, к.ф.-м.н., abel@ispras.ru Одобрена на заседании кафедры системного программирования «___»____________ 20 г Зав. кафедрой Иванников В.П. Рекомендована секцией УМС «___»____________ 20 г Председатель Утверждена УС факультета «___»_____________20 г. Ученый секретарь ________________________ Москва, 2015 Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 09.03.04 «Программная инженерия», обучающихся по бакалаврской программе изучающих дисциплину " Компиляторные технологии и верификация программ". Программа разработана в соответствии с образовательным стандартом Национального исследовательского университета «Высшая школа экономики» по направлению 09.03.04 «Программная инженерия». 1Цели освоения дисциплиныЦель курса – Целью курса является изучение основ построения оптимизирующих статических и динамических компиляторов современных языков программирования, учитывающих особенности архитектур современных компьютеров. Задачами данного курса являются:
2Компетенции обучающегося, формируемые в результате освоения дисциплиныВ результате освоения дисциплины студент должен:
В результате освоения дисциплины студент осваивает следующие компетенции:
3Место дисциплины в структуре образовательной программыИзучение данной дисциплины базируется на знаниях, полученных студентами при освоении учебных дисциплин: «Дискретная математика», «Программирование», «Информатика, математическая логика и теория алгоритмов», «Построение и анализ алгоритмов», «Архитектура вычислительных систем», «Операционные системы». 4Тематический план учебной дисциплины
5Формы контроля знаний студентов
5.1Критерии оценки знаний, навыков Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале. 5.2Порядок формирования оценок по дисциплине Преподаватель оценивает работу студентов на семинарских и практических занятиях: Оценки за работу на семинарских и практических занятиях преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за работу на семинарских и практических занятиях определяется перед промежуточным или итоговым контролем - Оауд. Преподаватель оценивает самостоятельную работу студентов. Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за самостоятельную работу определяется перед промежуточным или итоговым контролем – Осам. работа. Накопленная оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом: Онакопленная= 0,5* Оауд + 0,5*Осам.работа На пересдаче студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль. На экзамене студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл. В диплом выставляет результирующая оценка по учебной дисциплине, которая формируется по следующей формуле: Орезульт = 0,5*Онакопл + 0,5*Оэкз ВНИМАНИЕ: оценка за итоговый контроль блокирующая, при неудовлетворительной итоговой оценке она равна результирующей. 6Содержание дисциплины
7Оценочные средства для текущего контроля и аттестации студента7.1Тематика заданий текущего контроляПеречень контрольных вопросов для экзамена 1. Промежуточное представление программы. Граф потока управления и алгоритм его построения. Локальная оптимизация. Представление базового блока в виде ориентированного ациклического графа. Локальный метод нумерации значений. Виды локальной оптимизации. 2. Понятие потока данных. Состояние программы. Передаточная функция инструкции. Передаточная функция базового блока. Пути выполнения. 3. Определение и использование переменной в программе. Понятие дости-гающего определения. Передаточные функции достигающих определений. Итеративный алгоритм вычисления достигающих определений. 4. Применение достигающих определений. Обнаружение кода, инвариант-ного относительно цикла и вынесение его за пределы цикла. 5. Понятие живой (активной) переменной. Итеративный алгоритм анализа живых переменных. Понятие доступного выражения. Итеративный алго-ритм вычисления доступных выражений. 6. Полурешетки. Основные свойства полурешеток. Примеры полурешеток. Наибольшая нижняя граница и ее связь с операцией сбора. Диаграммы полурешеток. 7. Структура потока данных. Замкнутость семейства передаточных функций для достигающих определений, живых переменных и доступных выраже-ний. Монотонные и дистрибутивные структуры. Дистрибутивность структур достигающих определений, живых переменных и доступных выражений. 8. Обобщенный итеративный алгоритм. Сходимость итеративного алгоритма к решению уравнений потоков данных. Максимальная фиксированная точка. Сравнение максимальной фиксированной точки с идеальным решением уравнений потока данных и решением сбором по всем путям. 9. Распространение констант как задача потока данных. Передаточные функции структуры распространения констант, ее монотонность и недист-рибутивность. Итеративный алгоритм распространения констант. 10. Обход графа потока управления. Глубинное остовное дерево. Алгоритм упорядочения графа потока в глубину. Классификация ребер графа потока управления. Доминаторы. Свойства отношения доминирования. Алгоритм вычисления доминаторов. Дерево доминаторов. 11. Обратные ребра и естественные циклы. Построение естественного цикла обратного ребра. 12. Структурный анализ графа потока управления. Понятие области. Выделение областей в графе потока. Виды областей. Построение иерархии областей для приводимых графов потока. Дерево управления. Алгоритм построения восходящего порядка областей графа потока. 13. Алгоритм анализа на основе областей: построение иерархии областей (снизу вверх) и обработка иерархии областей (сверху вниз). Пересчет передаточных функций. Пример применения алгоритм анализа достига-ющих на основе областей. Обработка неприводимых графов потоков. 14. Форма статического единственного присваивания (SSA-форма). Функции объединения значений (f-функции). Определение f-функции. Свойства f-функций. Базовый алгоритм построения SSA-формы. 15. Алгоритм построения квазиоптимальной SSA-формы. Алгоритм постро-ения границы доминирования. Алгоритм переименования переменных. 16. Алгоритм восстановления программы по ее квазиоптимальной SSA-форме. 17. Глобальная нумерация значений (постановка задачи). Два подхода к реализации глобальной нумерации значений. Первый подход: использо-вание хэш-функций. 18. Глобальная нумерация значений: конгруэнтные подграфы. 19. Анализ алиасов: определение алиасов, виды алиасов. Глобальный (внутрипроцедурный) анализ алиасов. 20. Недостаточность глобального анализа алиасов. Межпроцедурный анализ алиасов. Контекстно-нечувствительный межпроцедурный анализ и его недостатки. Построение графа вызовов. 21. Межпроцедурный анализ алиасов. Чувствительность к контексту. Строки вызовов. k-ограниченный контекстно-чувствительный анализ. 22. Контекстно-чувствительный анализ на основе клонирования и на основе аннотаций. 23. Симметричные мультипроцессоры с общей памятью (SMP). Многоядерные процессоры. Закон Амдаля. Понятие локальности данных: пространственная и временная локальность. Формальная постановка задачи распараллеливания циклов. 24. Распараллеливание циклов. Пространство итераций. Построение пространств итераций для гнезд циклов. Управление порядком выполнения циклов гнезда. Алгоритм исключения Фурье-Моцкина. Алгоритм вычисления границ циклов для заданного порядка выполнения. 8Учебно-методическое и информационное обеспечение дисциплины8.1Базовый учебникA.В. Axo, М.С. Лам, P. Сети, Дж.Д. Ульман. Компиляторы: принципы, технологии и инструментарий. Издание второе. / М.: ООО «И.Д. Вильямс», 2008, ISBN: 978-5-8459-1349-4 8.2Основная литератураK.D. Cooper and L. Torczon. Engineering a Compiler. / Morgan Kaufman Publishers, 2004, ISBN: 1-55860-698-X 8.3Дополнительная литература
|
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки/ специальности... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки/специальности... |
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 040100. 68 Социология,... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 040100. 68 Социология,... |
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки, обучающихся... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки fillin... |
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки fillin... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 080200.... |
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов для направления 080200. 62... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки |
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки магистра... | ![]() | ... |
![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 040100. 68 «Социология»... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки/ специальности... |
![]() | Рабочая программа составлена на основании учебного плана по специальности : 310900 – «Землеустройство» направления подготовки дипломированного... | ![]() | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 39.... |
Поиск |