Практическое закрепление материала: семинары
Для уверенного закрепления материала в лекциях предусмотрены предусмотрены семинарские занятия по каждой теме, для которой имеется соответствующий инструмент (как правило, эмулятор соответствующей архитектуры или устройства). Задача семинара — заполнить базовые пробелы в знаниях и навыках студента и дать больше практики более активному студенту. Семинарские занятия не преследуют цели полностью закрывать лекционный материал, даже в практической части.
Семинар состоит из чередующихся активностей:
Фрагмент теории (как правило, терминология, ссылки)
Совместный разбор примеров (студенты воспроизводят действия преподавателя)
Самостоятельное решение простейших упражнений на разобранную тему
- Дополнительно может быть составлено отдельное домашнее задание по практической части лекций (в данном плане отсутствует)
Более подробно см. описание методологии ведения практикума.
Семинары пронумерованы в соответствии с лекционным планом. Время каждого семинара — 2 ак. часа
Не предполагается пересказывать на семинарах «теоретическую» часть лекций
- В идеале видеозаписи должны находиться в открытом доступе
[2] Системы счисления и эмулятор учебных машин
Перевод между системами счисления
Перевод между двоичным, десятичным и шестнадцатеричным представлением числа
Запись отрицательного числа в дополнительном коде в двоичном виде.
Запись отрицательного числа в дополнительном коде в двоичном виде.
Установка и запуск эмулятора modelmachine
Модификация простейшей программы для УМ3.
[4] УМ-3: условия и циклы
Система команд УМ3
Условие как переход вперёд
Сравнение двух чисел
Сравнение трёх чисел (вложенное условие)
Цикл как переход назад
Таблица умножения в столбик
[6] УМ-2 и УМ-1
Система команд УМ-2
Команды УМ-2 и флаги для условного перехода
Таблица умножения в столбик
Система команд УМ-1
Планирование вычислений для одноадресной ЭВМ
Вычисление формулы
[8] УМ-С и УМ-0
Стек как особый вид памяти. Система команд УМ-C
Преобразование формулы в обратную польскую запись
Вычисление формулы
Система команд УМ-0. Относительная и абсолютная адресация.
Пример: вычисление среднего арифметического
Переписать вычисление среднего арифметического таким образом, чтобы под конец работы программы на стеке оставалось единственное значение — результат
[10] УМ-М и переменный размер команды
Регистры и их назначение
Простой цикл для УМ-М
Простой цикл для УМ-М
Косвенная адресация и массивы
Обход массива
Простейшая задача на модификацию массива
[14] Система команд и ассемблер RISC-V
Понятие языка ассемблера, работа с RARS, интерактивная помощь в RARS
Простейшая программа для RARS
Сумма трёх чисел
Использование ecall
Вdод, сумма и вывод трёх чисел
[16] Работа с памятью
Хранение данных и строк
Ввести, обработать, вывести числа диагностикой
Условный переход
Неравенство треугольника
Каноническая схема цикла
Цикл
Таблица умножения в столбик
[18] Массивы
Косвенная адресация
Ввод и вывод массива
Ввод, обработка и вывод массива
Работа с отладчиком в RARS; точки останова
Вычислить формулу, посмотреть значения регистров посередине вычисления
Двумерные массивы: ввод и вывод
Транспонирование матрицы
[20] Концевые подпрограммы
call и ret; простейшая подпрограмма
Формула с подпрограммой к качестве подформулы
Конвенции по передаче параметров
Подпрограмма с несколькими параметрами и двумя возвращаемыми значениями
[22] Стек и универсальные подпрограммы
Стек в RISC-V; понятие «локальной переменной»
В цикле положить 10 значений на стек, потом снять и вывести их
Конвенции по использованию регистров
Простейшая универсальная подпрограмма — сложение двух чисел
Универсальная подпрограмма — сумма четырёх параметров с использованием подпрограммы, вычисляющей сложение
Использование стека для восстановления сохраняемых регистров
Универсальная подпрограмма reduce, которая получает на вход адрес массива A, его длину n и адрес подпрограммы, реализующей бинарную операцию ζ (например, сложение или умножение). Подпрограмма возвращает A0 ζ A1 ζ … ζ An-1
Для хранения индекса массива или адреса элемента использовать сохраняемый регистр s1
[24] Математический сопроцессор
(коротко) Представление вещественных чисел по IEEE 754; нормализованная и денормализованная формы
RARS Floating Point Representation
Система команд RISC-V FPU (расширение F)
Написать программу, которая получает из числа в нормализованном представлении число в денормализованом представлении (путём деления на 4, например); убедиться в этом с помощью Floating Point Representation
Конвенции по передаче параметров и использованию регистров
Универсальная подпрограмма с вычислением формулы; ввод и вывод вещественных чисел в RARS
Универсальная подпрограмма с вычислением формулы
[26] Макросы
Макроподстановка и макровзрыв
Макроопределение и макроподстановка в программе, использование параметров
Задание и использование макроса «вывод строки + числа в заданном формате» (строка передаётся в виде адреса, формат передаётся в виде номера ecall)
Локальное хранение констант (совмещение секций кода и данных) и метки в макросах
Переписать предыдущий пример с передачей строки в виде строки
[28] Математический сопроцессор (продолжение) и кадр стека
Назначение кадра стека, регистр fp; конвенции по использованию кадра (кратко)
Универсальная подпрограмма с использованием кадра
Трижды вызвать по цепочке одну подпрограмму с кадром из другой, пронаблюдать в памяти связный список кадров
Неатомарная операция сравнения; пример
Неравенство треугольника (ввести три числа и проверить, можно ли построить треугольник с такими сторонами)
Управляющие регистры FPU и их использование: пример с флагом fcsr OF
Ввести два числа, вывести их произведение и информацию, была ли потеряна точность (fcsr NX)
[30] Статические структуры данных
Косвенная индексация и адресная арифметика
Моделирование двумерных массивов: подпрограммы вывода двумерного массива по строкам и ввода по столбцам
Написать подпрограмму rotate N addr0 addr1, которая поворачивает квадратную матрицу addr0 размером N×N на 90°, заполняя addr1. Вызвать её четырежды.
Структура кольцевого буфера — очереди
Разбор реализации очереди из лекций
Дописать к имеющейся реализации две подпрограммы — push_q, которая добавляет значение в голову очереди, и pop_q, которая снимает значение из хвоста очереди
[32] Обработка исключений
Регистры статуса и управления RISC-V; понятие исключения и обработчика
Разбор простейшего обработчика из лекций
Написать простейший обработчик несуществующего внешнего вызова (ENVIRONMENT_CALL), который перегружает a0 в -1, а в противном случае — останавливает работу программы
Конвенция по сохранению контекста в обработчике: uscratch и память для регистров
Написать «внешний вызов "счётчик"»: обработчик исключения ENVIRONMENT_CALL, который при a7 == 0x100 возвращает в a0 постоянно увеличивающееся на 1 число. В остальных исключениях останавливать выполнение.
[34] Ввод/вывод: поллинг и MMIO
Понятие MMIO
Цифровой блок RARS: сегментный индикатор
Написать подпрограмму, которая выводит на цифровом индикаторе двузначное двоичное число в диапазоне от 0 до 3
Цифровой блок RARS: клавиатура
Написать подпрограмму, которая возвращает число от 0 до 15, соответствующее клавише, нажатой на цифровой клавиатуре, иначе -1.
Графический дисплей RARS: подпрограмма рисования точки
Написать подпрограмму рисования круга circle xcenter ycenter radius color (подсказка: перебрать все точки квадрата, и заполнить те, для которых (xcenter - x)2 + (ycenter - y)2 ⩽ radius2 ).
[36] Таймеры и прерывания по таймеру
Таймеры и счётчики
CSR-Счётчики RARS
Написать программу, которая считает от 0 до ∞, и выводит текущее число всякий раз, когда CSR-регистр instret переваливает за очередную сотню
Таймер как внешнее устройство. Прерывания по таймеру
Timer Tool в RARS, обработка прерываний. Отличие от обработчика исключений
Ввести слово, выводить по одной букве этого слова раз в секунду при помощи прерывания по таймеру
[38] Прерывания ввода-вывода
Прерывания от внешних устройств
RARS keyboard and display MMIO simulator («консоль»), прерывание по вводу с клавиатуры
Написать программу, которая выводит на консоль (с помощью поллинга) введённые с клавиатуры консоли символы
- обработчик должен быть минимальным — только вводить байт, выводом должна заниматься программа
- подобрать задержки устройства таким образом, чтобы часть ввода пропадала (пока поллинг ждёт, прерывание срабатывает несколько раз)
Прерывание консоли по готовности ввода
Написать программу, которая выводит на консоль
[40] Динамические структуры данных: таблицы
Динамическое управление памятью.
Таблица (массив ссылок)
Ограничения работы с памятью в RARS, ecall 9; таблица как стек, процедуры добавления и снятия элемента
Реализовать подпрограммы поиска, вставки и удаления элемента для таблиц; написать программу-пример, в которой эти функции используются
- Удобно использовать уникальный для каждой таблицы заголовок — адрес её начала и количество элементов
Геометрическое масштабирование динамических данных
Модифицировать предыдущее решение: добавить масштабирование в большую сторону при добавлении элемента
- В заголовке теперь нужно хранить также максимальное количество элементов
[42] Конвейер
Конвейер как способ увеличения быстродействия вычислений, RISC-V
Написать программу, в цикле выводящую числа от 1 до 12.
- Запустить эту программу в варианте без задержки инструкций («5-stage processor w/o hazard detection»)
Отладить её при помощи ручной вставки nop везде, где требуется задержка
Минимизировать количество nop-ов за счёт разнесения зависимых инструкций
Пронаблюдать и по возможности использовать т. н. «слот задержки»: при выполнении инструкции условного перехода всегда выполняется также и следующая за ней инструкция (потому что она прошла этап F)
[44] Динамические структуры данных: связные списки
Связные списки
Разбор примеров из лекции: поиск, вставка и удаление элементов
Реализовать тип данных «упорядоченный список однотипных элементов»
В поле cell стартового элемента списка хранится адрес подпрограммы сравнения двух элементов; подпрограмма возвращает отрицательное число, 0 или положительное число в зависимости от результата сравнения
- Модифицировать подпрограммы поиска
- Написать программу-пример
[46] Кеш и предсказание перехода
Предсказание перехода как способ увеличения быстродействия вычислений
Одноуровневый и двухуровневый предсказатель перехода в RARS
Написать программу, которая в цикле выводит числа от 1 до 100, при этом предсказатель перехода должен быть по возможности максимально неэффективным
Кеш как способ увеличения быстродействия доступа к памяти
Виды (имитированного) кеша в RARS, примеры из лекции
По аналогии с примером из лекции написать программу, которая заполняет память так, что:
Малоэффективен (⩽ 30%) множественно-ассоциативный LRU кеш 4 банка по 4 строки (всего 16 строк) по 8 слов в строке (всего 512 байт)
Эффективен (⩾ 60%) множественно-ассоциативный LRU кеш 4 банка по 4 строки (всего 16 строк) по 16 слов в строке (всего 1024 байта)
[48] Финальная контрольная: написание программы с использованием прерываний и / или динамических структур данных (может понадобиться более 2 часов)
TODO Варианты задач