Практическое закрепление материала: семинары

Для уверенного закрепления материала в лекциях предусмотрены предусмотрены семинарские занятия по каждой теме, для которой имеется соответствующий инструмент (как правило, эмулятор соответствующей архитектуры или устройства). Задача семинара — заполнить базовые пробелы в знаниях и навыках студента и дать больше практики более активному студенту. Семинарские занятия не преследуют цели полностью закрывать лекционный материал, даже в практической части.

Семинар состоит из чередующихся активностей:

• Фрагмент теории (как правило, терминология, ссылки)

• Совместный разбор примеров (студенты воспроизводят действия преподавателя)

• Самостоятельное решение простейших упражнений на разобранную тему

• Дополнительно может быть составлено отдельное домашнее задание по практической части лекций (в данном плане отсутствует)

Более подробно см. описание методологии ведения практикума.

Семинары пронумерованы в соответствии с лекционным планом. Время каждого семинара — 2 ак. часа

Не предполагается пересказывать на семинарах «теоретическую» часть лекций

• В идеале видеозаписи должны находиться в открытом доступе

• [2] Системы счисления и эмулятор учебных машин

  • Перевод между системами счисления

  • Перевод между двоичным, десятичным и шестнадцатеричным представлением числа

  • Запись отрицательного числа в дополнительном коде в двоичном виде.

  • Запись отрицательного числа в дополнительном коде в двоичном виде.

  • эмулятор учебных машин

  • Установка и запуск эмулятора modelmachine

  • Модификация простейшей программы для УМ3.

• [4] УМ-3: условия и циклы

  • Система команд УМ3

  • Условие как переход вперёд

  • Сравнение двух чисел

  • Сравнение трёх чисел (вложенное условие)

  • Цикл как переход назад

  • Таблица умножения в столбик

• [6] УМ-2 и УМ-1

  • Система команд УМ-2

  • Команды УМ-2 и флаги для условного перехода

  • Таблица умножения в столбик

  • Система команд УМ-1

  • Планирование вычислений для одноадресной ЭВМ

  • Вычисление формулы

• [8] УМ-С и УМ-0

  • Стек как особый вид памяти. Система команд УМ-C

  • Преобразование формулы в обратную польскую запись

  • Вычисление формулы

  • Система команд УМ-0. Относительная и абсолютная адресация.

  • Пример: вычисление среднего арифметического

  • Переписать вычисление среднего арифметического таким образом, чтобы под конец работы программы на стеке оставалось единственное значение — результат

• [10] УМ-М и переменный размер команды

  • Регистры и их назначение

  • Простой цикл для УМ-М

  • Простой цикл для УМ-М

  • Косвенная адресация и массивы

  • Обход массива

  • Простейшая задача на модификацию массива

• [12] Коллоквиум по теме «Учебные машины»

• [14] Система команд и ассемблер RISC-V

  • Понятие языка ассемблера, работа с RARS, интерактивная помощь в RARS

  • Простейшая программа для RARS

  • Сумма трёх чисел

  • Использование ecall

  • Вdод, сумма и вывод трёх чисел

• [16] Работа с памятью

  • Хранение данных и строк

  • Ввести, обработать, вывести числа диагностикой

  • Условный переход

  • Неравенство треугольника

  • Каноническая схема цикла

  • Цикл

  • Таблица умножения в столбик

• [18] Массивы

  • Косвенная адресация

  • Ввод и вывод массива

  • Ввод, обработка и вывод массива

  • Работа с отладчиком в RARS; точки останова

  • Вычислить формулу, посмотреть значения регистров посередине вычисления

  • Двумерные массивы: ввод и вывод

  • Транспонирование матрицы

• [20] Концевые подпрограммы

  • call и ret; простейшая подпрограмма

  • Формула с подпрограммой к качестве подформулы

  • Конвенции по передаче параметров

  • Подпрограмма с несколькими параметрами и двумя возвращаемыми значениями

• [22] Стек и универсальные подпрограммы

  • Стек в RISC-V; понятие «локальной переменной»

  • В цикле положить 10 значений на стек, потом снять и вывести их

  • Конвенции по использованию регистров

  • Простейшая универсальная подпрограмма — сложение двух чисел

  • Универсальная подпрограмма — сумма четырёх параметров с использованием подпрограммы, вычисляющей сложение

  • Использование стека для восстановления сохраняемых регистров

  • Универсальная подпрограмма reduce, которая получает на вход адрес массива A, его длину n и адрес подпрограммы, реализующей бинарную операцию ζ (например, сложение или умножение). Подпрограмма возвращает A₀ ζ A₁ ζ … ζ A_n-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)² + (ycenter - y)² ⩽ radius² ).

• [36] Таймеры и прерывания по таймеру

  • Таймеры и счётчики

  • CSR-Счётчики RARS

  • Написать программу, которая считает от 0 до ∞, и выводит текущее число всякий раз, когда CSR-регистр instret переваливает за очередную сотню

  • Таймер как внешнее устройство. Прерывания по таймеру

  • Timer Tool в RARS, обработка прерываний. Отличие от обработчика исключений

  • Ввести слово, выводить по одной букве этого слова раз в секунду при помощи прерывания по таймеру

• [38] Прерывания ввода-вывода

  • Прерывания от внешних устройств

  • RARS keyboard and display MMIO simulator («консоль»), прерывание по вводу с клавиатуры

  • Написать программу, которая выводит на консоль (с помощью поллинга) введённые с клавиатуры консоли символы

    • обработчик должен быть минимальным — только вводить байт, выводом должна заниматься программа
    • подобрать задержки устройства таким образом, чтобы часть ввода пропадала (пока поллинг ждёт, прерывание срабатывает несколько раз)

  • Прерывание консоли по готовности ввода

  • Написать программу, которая выводит на консоль

• [40] Динамические структуры данных: таблицы

  • Динамическое управление памятью.

  • Таблица (массив ссылок)

  • Ограничения работы с памятью в RARS, ecall 9; таблица как стек, процедуры добавления и снятия элемента

  • Реализовать подпрограммы поиска, вставки и удаления элемента для таблиц; написать программу-пример, в которой эти функции используются

    • Удобно использовать уникальный для каждой таблицы заголовок — адрес её начала и количество элементов

  • Геометрическое масштабирование динамических данных

  • Модифицировать предыдущее решение: добавить масштабирование в большую сторону при добавлении элемента

    • В заголовке теперь нужно хранить также максимальное количество элементов

• [42] Конвейер

  • Конвейер как способ увеличения быстродействия вычислений, RISC-V

  • Имитация конвейера на примере Ripes или QtRvSim

  • Написать программу, в цикле выводящую числа от 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 Варианты задач