Архитектура ЭВМ

(2014.05.13)
Вопросы на экзамен

Часть 1

1. Модели вычислений: машина Тьюринга (МТ), лямбда-исчисление, машина Маркова, клеточный автомат, RAM/RASP (определения). Невычислимые функции (привести примеры). Гарвардская архитектура и архитектура фон Неймана, гибридная архитектура (схема, принцип работы, недостатки). Примеры «нефоннеймановских» архитектур.

2. Недетерминированная МТ (НМТ=NMT), эквивалентность НМТ и ДМТ=DMT. Проблема P vs NP. Конечный автомат (КА=FA), эквивалентность НКА=NFA и ДКА=DFA. Автомат с магазинной памятью (АМП=PDA), неэквивалентность НАМП=NPDA и ДАМП=DPDA. Соответствие классов порождающих грамматик и распознавателей (иерархия Хомского).

3. Языки высокого уровня и низкого уровня. Транслятор (интерпретатор, компилятор), байт-код. Динамическая и статическая типизация. Дать сравнение процедурной и функциональной парадигм программирования.

4. Ассемблер/дизассемблер. Машинный код vs объектный код, компоновщик. Характерные элементы парадигм машинных языков (ISA): регистровая машина (CISC vs RISC), стек-машина, TTA (transport-triggered architecture).

5. API vs ABI. Стек вызовов, соглашение вызова (привести примеры на основе существующих соглашений вызова x86/x86-64). Пролог и эпилог функции, регистровое окно (понятия). Режимы адресации.

6. Уровни микроархитектуры (перечисление + краткая характеристика). Подложка, слои металлизации, EDA, HDL, стандартные ячейки и библиотеки ячеек (понятия). Структура МОП-транзистора=MOSFET, FinFET. Отличия между PGA, LGA и BGA.

7. Представление целых чисел в двоичной системе. Представление отрицательных чисел: прямой, обратный и дополнительный код. Использование сумматора для вычитания. Переполнение и оборачивание (как можно определить ситуацию переполнения при выполнении операции сложения в сумматоре?). Каким арифметическим операциям соответствуют поразрядные сдвиги влево и вправо?

8. Числа с фиксированной запятой. Представление чисел с плавающей запятой по стандарту IEEE-754. ULP. Возможные режимы округления. Логарифмическая система счисления.

9. Устройство управления в составе процессора. PAL, FPGA. Автомат Ричардса. Микрокод, микросеквенсер.

10. Подсистема памяти: MMU, виртуальная (страничная) память, кэши CPU. Основные принципы работы DDR SDRAM.

11. Flash-память: NOR vs NAND, SLC vs MLC, SSD. RAID-массив (принципы работы режимов 0, 1, 5, 6, 10, 50, 60). JBOD.

12. Прерывания, отложенный вызов процедур. Локальная шина, DMA. Основные принципы работы шины PCIE.

13. Модель PRAM, закон Амдала. Основные модели аппаратного параллелизма с общей памятью. Основные принципы работы современных GPU, GPGPU.

14. Гетерогенные вычисления, UMA vs NUMA, проблема когерентности кэшей, сильная и слабая модели памяти. Гипервизор, «облачные вычисления».

Часть 2

1. Привести схему (на уровне функциональных устройств) простого RISC-процессора с 5-ступенчатым конвейером.

2. Как реализовать стандартную функцию C memcpy, располагая доступом, выровненным по границе 4 байт?

3. Как реализовать стандартную функцию C memchr, располагая доступом, выровненным по границе 4 байт?

*ответ на вопросы 2, 3 предполагает описание общего подхода к реализации указанных функций, см. также демонстрационный пример.

4. Привести схему 4-битного сквозного сумматора, чем он отличается от carry-save-adder (CSA)?

5. Привести схему дешифратора 2-4, на его основе построить схему мультиплексора 4-1 и демультиплексора 1-4.

6. Привести схему SR-триггера, D-триггера, T-триггера на основе D-триггера.

7. На основе D-триггеров (и мультиплексоров) построить схемы 4-битного счётчика, 4-битного сдвигового регистра parallel-to-serial.

Расширенная программа курса

  1. Теоретические основы вычислений. Архитектура набора команд.
    1. Данные и информация. Бит. Байт. Машинное слово. Физическое кодирование данных, простейшие схемы: RZ, NRZ, манчестерский код. Что такое 1 бод? Понятие кодировки символов, многобайтные кодировки, проблема big-endian vs little-endian. Программный принцип управления vs управление с обратной связью. Аппаратное обеспечение и программное обеспечение. Системное ПО и прикладное ПО.
    2. Аналоговые и цифровые вычислительные машины. Поколения цифровых ЭВМ. Неудача транспьютеров и японского проекта компьютера 5-го поколения. Поколения (iGL) языков программирования (ЯП), проблема 5GL, возможные классификации ЯП. Императивное и декларативное программирование. Domain-specific language (DSL). Дать общую характеристику современному этапу развития вычислительной техники.
    3. Теоретические основы вычислений. Алгоритм. Машина Тьюринга (МТ). Недетерминированная МТ. Универсальная МТ. Тезис Чёрча-Тьюринга, вычислимые и невычислимые функции. Полнота по Тьюрингу. Гипервычислитель. Привести пример невычислимой функции. Квантовый вычислитель.
    4. Random access machine (RAM). Классы вычислительной сложности (EXPSPACE, EXPTIME, PSPACE, NP, P, NL, L). X-трудные и X-полные задачи (где X – некоторый класс сложности). Проблема P=NP, привести пример NP-полной задачи.
    5. Формальные грамматики. Порождающие и распознающие грамматики (в частности, PEG). Транслятор: интерпретатор vs компилятор. «Компилятор компиляторов». Иерархия Хомского, отвечающие её классам грамматик распознающие автоматы (пример: регулярные грамматики распознаются конечными автоматами).
    6. Различие между микроархитектурой, архитектурой набора команд (ISA) и архитектурой систем (system design). Понятие шины передачи данных, физический и логический уровни. Гарвардская архитектура и архитектура фон Неймана, гибридная архитектура. Процессор. Контроллер. Переносимый код (p-code, байткод, биткод), JIT-компиляция. Теговая архитектура.
    7. Принципы программирования на языках низкого уровня. Ассемблер, дизассемблер, макроассемблер, объектный код, компоновщик, загрузчик, монитор, отладчик. Типы регистров: общего назначения, аккумулятор, флагов, управляющий, индексный, сегментный, указатель инструкции, указатель вершины стека. Режимы адресации. Типы функциональных устройств: устройство управления (CU), регистровый файл (RF), ALU, FPU, load-store unit (LSU), MMU, scratchpad, внутренняя шина (datapath).
    8. Стековая машина и регистровая машина. Язык Forth (основные принципы). Инфраструктура LLVM. Основы процедурного программирования, библиотеки подпрограмм. Вызов процедур, соглашения вызова, стек вызовов. Сопроцедуры (coroutines). Регистровое окно. Регистры и базовые соглашения вызова архитектур MIPS64, ARMv7, ARMv8, x86-64.
    9. Клеточный автомат (привести не менее двух примеров полных по Тьюрингу клеточных автоматов). Искусственная нейронная сеть (принципы работы, возможности, основные типы, ускорители).

     

  2. Физические основы вычислений. Микроархитектура.
    1. Принцип работы транзистора, биполярные (BJT) и полевые транзисторы (FET). Виды транзисторной логики (TTL, PMOS, NMOS, CMOS). Что быстрее (на кремнии), NMOS или PMOS? Почему? Перспективные типы транзисторов: баллистические, HEMT, на основе CNT. Динамическая и статическая логика.
    2. Технологический процесс изготовления микросхем методом фотолитографии: основные этапы. Слои металлизации. Многозатворные транзисторы, увеличение площади затвора: FinFET, Intel 3D tri-gate. Закон Мура и антизакон Мура (рост расходов на освоение более тонких техпроцессов). Перечислить основных разработчиков оборудования и ПО для фотолитографии. 3D stacking. Типы корпусов микросхем (SIP, DIP, ZIP, QFP, (C)PGA, LGA, BGA). Что такое flip-chip? Чем «слот» отличается от «сокета»?
    3. Основные сведения о процессе проектирования микросхем. Инструменты для автоматизации разработки и моделирования микросхем (EDA). Средства упрощения и моделирования логики. Стандартные ячейки и библиотеки ячеек (cell libraries). ПЛИС vs БМК vs ASIC. Уровень регистровых передач, HDL. Описать основные этапы создания новой микросхемы как серийного продукта. Перечислить основных контрактных производителей микросхем и наилучшие предлагаемые ими на данный момент техпроцессы. MPW.
    4. Логические вентили (общее определение и виды вентилей). Понятия fan-in, fan-out, FO4-метрика. Примеры реализации NAND-вентиля на реле, в TTL-логике, CMOS-логике. Инвертор и буфер. Реализация AND, OR, NOT, XOR вентилей на основе NAND-вентилей. Шифратор-дешифратор. Мультиплексор-демультиплексор. Составить схему мультиплексора 4-на-1 и соответствующего демультиплексора.
    5. Средства тестирования микросхем: JTAG, BITE/BIST. Hardware race condition. Использование метастабильных состояний для создания генераторов истинно случайных чисел (см., например, про Intel Ivy Bridge). Исторические этапы и масштабы интеграции микросхем, система-на-чипе (SoC).
    6. Сквозной сумматор. Carry-save adder. Способы ускорения работы сумматоров (carry look-ahead). Реализация вычитания. Сдвигатель (barrel shifter). Общая схема простого арифметико-логического устройства (реализующего операции ADD, SUB, AND, OR, XOR; как пример: ALU Intel 8085, хотя можно обойтись более простой и менее эффективной схемой). Как реализовать сравнение чисел?
    7. Схемы питания микросхем. Широтно-импульсный преобразователь. H-дерево. Power gating, clock gating. Режимы энергосбережения в современных процессорах. Генератор тактовой частоты, генератор Пирса, джиттер, phased-locked loop (PLL).
    8. Триггеры (RS, D, JK, T). Дать схему D-триггера, срабатывающего по фронту. Счётчик тактов на основе D-триггеров. Сдвиговый регистр (последовательный ввод, параллельный ввод), UART. Устройство SRAM, схема ячейки 6T-SRAM. Где используется SRAM?
    9. Алгоритмы целочисленного умножения и деления. Алгоритм Бута. Умножитель на основе сдвигового регистра. Умножитель на основе систолической матрицы. (См., например, здесь.) Дерево Уоллеса.
    10. Двоичное представление целых чисел. Числа с фиксированной запятой. Форматы чисел с плавающей запятой (и нечисел) в рамках стандарта IEEE-754. Точность вычислений арифметических выражений с использованием чисел с плавающей запятой (ULP, режимы округления, гарантии в рамках IEEE-754, FMA). Деление и извлечение квадратного корня с помощью метода Ньютона. Приближение тригонометрических функций алгоритмом CORDIC.
    11. Парадигмы проектирования микропроцессоров: CISC, RISC, MISC (стек-машина), VLIW. «Ортогональный» набор инструкций. Вычислительный конвейер. Байпас. Основные характеристики RISC-архитектуры. Изобразить схему устройства (на уровне функциональных устройств и внутренних шин) простого RISC-подобного процессора (например, MIPS). Связь тактовой частоты и длины конвейера.
    12. Устройство управления в составе ЦП. Реализация конечного автомата в виде устройства Ричардса. Микрокод, микрооперации, микросеквенсер. Технологии ускорения выполнения одного потока инструкций: суперскалярность, переименование регистров, внеочередное исполнение инструкций (out-of-order vs in-order), предсказание переходов (branch prediction) и загрузок данных (prefetch). В качестве примеров можно смотреть описания микроархитектур современных «больших» ЦП от Intel и AMD.
    13. Ускорение специализированных задач: логарифмическая система счисления, подходы digital signal processor (DSP), field-programmable gate array (FPGA), transport-triggered architecture (TTA, NISC). Описать принципы работы, достоинства и недостатки.
  3. Архитектура систем. Параллельные вычисления.
    1. Динамическая память. Схема работы контроллера SDRAM, основные тайминги, error correction (ECC). Общие сведения о стандарте JEDEC DDR3, форм-фактор DDR3 DIMM. eDRAM. FB-DIMM.
    2. Прерывания. x86 APIC, IRQ. Отложенный вызов процедур (DPC) в Windows NT. Direct memory access (DMA). Локальная шина. Общие сведения о шине PCI-Express, конфигурационное пространство PCI(-Express).
    3. Старт системы. Reset vector. BIOS и POST в IBM PC, Plug and Play. ACPI. UEFI, OpenFirmware. Trusted platform module (TPM). SMBIOS, WBEM.
    4. Виртуальная память. Страничные иерархии x86-64, дескрипторные таблицы. Virtual memory manager (VMM), пространство ядра ОС и пространство пользователя. Принцип представления устройств ввода-вывода и файлов в виде диапазонов адресов (device/file memory mapping).
    5. Кэш центрального процессора: строка (victim cache) , промах, ассоциативность, алгоритмы записи (WT, WB), эксклюзивность и инклюзивность. Translation look-aside buffer (TLB). Адресация на уровне кэша (физические адреса или виртуальные адреса?). Иерархия кэшей: FSB и BSB, зачем нужны L1I, L1D, L2, L3, а также возможные вариации на тему L0 (например, кэш трасс Pentium 4, кэш микроинструкций в Intel Sandy Bridge, load to store forwarding) и L4 (например, в Intel Haswell).
    6. ПЗУ (PROM, EPROM, EEPROM). Flash-память: NOR и NAND, SLC и MLC. Принцип работы твёрдотельных накопителей (SSD) на основе flash-памяти. Почему запись по случайному адресу медленнее последовательной записи? Недостатки SSD. Перспективные типы NVRAM (nvSRAM, FeRAM, MRAM, PRAM, RRAM, NRAM).
    7. HDD и ODD, кодирование RLL. LBA. SATA vs SAS; AHCI; NCQ. SMART. RAID (0, 1, 5, 6, 10, 50, 60), проблемы надёжности RAID. JBOD.
    8. Модели Parallel RAM. Закон Амдала; может ли возникать обратный эффект, т.е. сверхлинейный прирост скорости при распараллеливании нагрузки? почему? Транзакционная память. Модели вычислений с разделяемой памятью: SMP, MIMD, SIMT/SPMD (GPU), их преимущества и недостатки. Принцип scatter-gather. Simultaneous multithreading (на примере Intel HyperThreading, преимущества и недостатки относительно «честного» SMP). Temporal multithreading, barrel processor.
    9. Параллельные вычисления. Блокирующие и неблокирующие алгоритмы. Техники thread pool и parallel pipeline (вычислительный конвейер – параллельная работа разных стадий). Параллелизм уровня данных (DLP) и параллелизм уровня задач (TLP). Параллелизм на уровне одного логического ядра: параллелизм уровня инструкций (ILP), памяти (MLP). SIMD; SIMD within a register (SWAR) и bit-level parallelism (BLP).
    10. Многоядерный процессор: внеядро (uncore), интегрированный контроллер памяти (IMC), кэш L3, протоколы обеспечения когерентности кэшей (см. например, здесь). Сильная (например, в x86) и слабая (например, в ARM) модели памяти. Проблема false sharing в SMP-вычислениях. Вычислительный кластер, NUMA.
    11. Гипервизор, проблемы виртуализации устройств (например, GPU). «Большие данные» (big data). ЦОД, облачные вычисления: VPS, SaaS, PaaS, IaaS.  Map-Reduce. Грид-системы. Способы организации хранения больших объёмов данных.

Ссылки

Вендоры: Altera, AMD, ARM, Atmel, IBM/Power, Imagination/MIPS, Intel, NVidia, Oracle/OpenSPARC (arch 2011), Tilera, Xilinx,

Техноблоги: Агнер Фог, Future Chips, Proper Fixation, Intel на Хабре, Realworldtech, SysProg, Random ASCII, Exploring Binary, Linus Åkesson. О вычислениях с плавающей запятой: 1, 2. К вопросу о техпроцессах изготовления микросхем: 1, 2.

Книги: Computer Architecture and Organization: From Software to Hardware, Operating Systems and Middleware: Supporting Controlled Interaction.

Другое: Лаборатория Параллельных информационных технологий, Modern GPU, iXBT (разделы по CPU, GPU), IEEE Spectrum, OpenCores (MCPU), Google Research publications, The Multicore Association, забавный пример имитации транзисторной логики в sh: pipe logic.

Софт: Logisim, TCE, Kactus2, Ngspice, Icarus Verilog, Verilator, GTKWave, EDA software list.

Литература

  1. Таненбаум Э. Архитектура компьютера. 5-е изд. – СПб.: «Питер», 2007.
  2. Паттерсон Д., Хеннесси Дж. Архитектура компьютера и проектирование компьютерных систем. 4-е изд. – СПб.: «Питер», 2012.
  3. Петцольд Ч. Код. – М.: «Русская Редакция», 2001.
  4. Аверченков О.Е. Схемотехника: аппаратура и программы. – М.: ДМК Пресс, 2012.
  5. Хоровиц П., Хилл У. Искусство схемотехники. 3-е изд. – М.: «Мир», 1986.
  6. Бройдо В.Л., Ильина О.П. Архитектура ЭВМ и систем. 2-е изд. – СПб.: «Питер», 2009.
  7. Максимов Н.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем. М.: ФОРУМ: ИНФРА-М, 2006.
  8. Лехин С.Н. Схемотехника ЭВМ. – СПб.: БХВ-Петербург, 2010.
  9. Юров В.И. Assembler: учебник для вузов. 2-е изд. – СПб.: «Питер», 2011.
  10. Стюарт Т. Теория вычислений для программистов. – М.: ДМК Пресс, 2014.
  11. J. Hennessy, D. Patterson. Computer Architecture: A Quantitative Approach. 4th ed. Elsevier, Morgan Kaufmann Publishers, 2007.
  12. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.
  13. Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы. – М.: БИНОМ, 2006.
  14. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002.
  15. Таненбаум Э. Современные операционные системы. 3-е изд. — СПб.: Питер, 2010.
  16. Карпов Ю.Г. Основы построения трансляторов. – СПб.: БХВ-Петербург, 2005.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: