F4 Модель автомата состояний компьютерных систем

Прежде чем углубляться в то, как проектировать процессоры, давайте сначала разберёмся с основными принципами работы процессоров. Однако пока мы не будем рассматривать процессоры с точки зрения цифровых схем. Вместо этого мы объясним некоторые важные понятия, связанные с процессорами, с помощью менее строгой математической модели. Поэтому вы можете временно отложить в сторону знания о цифровых схемах, полученные в предыдущем разделе. Процессоры и цифровые схемы действительно тесно связаны. В следующем разделе мы обсудим, как реализовать процессоры с помощью цифровых схем. Пока же всё, что вам нужно, — это бумага и ручка.

Устройство и принцип работы процессоров

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

Инструкции и их кодирование

Вам всем наверняка знакомы электронные калькуляторы. Современные калькуляторы умеют выполнять как минимум четыре арифметических действия: сложение, вычитание, умножение и деление. Возможности процессора намного превосходят возможности электронного калькулятора. Как устройство для обработки данных, он, разумеется, не ограничен единственным способом обработки. Кроме того, поскольку процессор — это устройство, механически обрабатывающее данные, то, какую именно обработку он выполняет, должно каким-то образом управляться извне, ведь он не обладает способностью мыслить самостоятельно. Средством управления процессором служат инструкции. Например, с помощью инструкции сложения можно заставить процессор сложить два фрагмента данных. Это очень похоже на ввод 1+2= на электронном калькуляторе, чтобы им управлять.

Фраза «с помощью инструкции сложения заставить процессор сложить два фрагмента данных» означает, что инструкция должна предоставлять два вида информации: с одной стороны, компьютеру приходится обрабатывать данные многих видов, поэтому инструкция должна указывать, какие именно данные обрабатывать, — это называется полем «операнд» инструкции; с другой стороны, у компьютера также есть много способов обработки данных, поэтому инструкция должна также указывать способ обработки данных, — это называется полем «код операции» инструкции.

+--------------+---------+
| код операции | операнд |
+--------------+---------+

«Процессор» в повседневной жизни: кухня

На самом деле у многих понятий внутри процессора есть похожие аналоги в повседневной жизни. Например, кухня — это место для обработки ингредиентов. Повар обрабатывает ингредиенты по рецепту, в итоге получая различные блюда.

То, как работает процессор, очень похоже на то, что происходит на кухне. Например, инструкция подобна пункту меню. То, что повар готовит по меню, можно понимать так, будто меню «управляет» действиями повара. В меню тоже есть понятия, похожие на «операнды» и «коды операций». Например, «помидор» и «яйцо» в блюде «жареные помидоры с яйцом» похожи на «операнды» — они указывают, что для блюда нужно обработать именно эти два ингредиента; а «обжарить» похоже на «код операции» — оно указывает тип кулинарной операции, которую нужно выполнить над ингредиентами. Блюда из меню, такие как дважды приготовленная свинина или рыба на пару, тоже можно понимать с точки зрения инструкций.

Некоторые промежуточные результаты нужно сохранять для дальнейшего использования, поэтому процессору нужны компоненты, способные хранить данные. Такие компоненты называются регистрами. Процессор обычно содержит несколько регистров, объединённых в набор регистров, который в некоторых учебниках также называют регистровым файлом. Поскольку эти регистры используются для хранения данных общего назначения, их называют регистрами общего назначения (GPR). Другие регистры служат для специализированных целей и поэтому не относятся к GPR.

Например, рассмотрим вычисление 1+2+...+10. Поскольку одна инструкция сложения может сложить только два значения данных, результат 1+2 сначала нужно сохранить в каком-нибудь регистре r среди GPR. Затем процессор может вычислить r+3, и так далее. Поэтому поле операнда инструкции должно указывать, какие GPR предоставляют входные данные и какой GPR получает результат. Что касается кода операции, процессору достаточно соглашения, определяющего, какую операцию представляет каждый код операции.

«Процессор» в повседневной жизни: кухня (2)

Для блюда «дважды приготовленная свинина» перед обжаркой мясо нужно отварить. Поэтому отваренное мясо нужно временно переложить в миску, прежде чем вернуть его обратно в вок для обжарки. Регистры внутри процессора аналогичны мискам на кухне — они служат временным хранилищем для ингредиентов в процессе обработки.

Будучи цифровой схемой, процессор способен представлять всю информацию с помощью 0 и 1, и инструкции не исключение. Например, простой процессор с 4 GPR поддерживает 3 типа инструкций, два из которых показаны ниже:

 7  6 5  4 3   2 1   0
+----+----+-----+-----+
| 00 | rd | rs1 | rs2 | R[rd]=R[rs1]+R[rs2]    инструкция add, складывает два регистра
+----+----+-----+-----+
| 10 | rd |    imm    | R[rd]=imm              инструкция li, загружает непосредственное значение, старшие биты заполняются нулями
+----+----+-----+-----+

Поскольку типов инструкций всего три, для различения всех инструкций достаточно 2-битного кода операции. В приведённом выше примере код операции 00 представляет инструкцию add; код операции 10 представляет инструкцию li. Для удобства у инструкций обычно есть соответствующие названия, например инструкция add и инструкция li.

Что касается операндов, поскольку GPR всего 4, для указания адреса GPR достаточно 2-битного числа (00, 01, 10, 11). Источник данных операнда называется «регистром-источником». Приведённая выше инструкция add требует два регистра-источника, чтобы получить слагаемые; адреса этих двух регистров-источников обозначаются как rs1 и rs2 соответственно, а содержимое, хранящееся в GPR, обозначается как R[rs1] и R[rs2]; место, куда записывается результат операции, называется «регистром-приёмником» и обычно обозначается как rd. Среди них у второй инструкции, li, формат операнда немного отличается. Её исходный операнд — уже не GPR, а число, разбираемое напрямую из поля imm инструкции как двоичное значение. Такой тип операнда называется «непосредственным операндом».

Таким образом, длина приведённых выше инструкций составляет 8 бит. Опираясь на приведённые выше правила кодирования инструкций, можно понять смысл инструкции. Ниже приведены несколько конкретных примеров инструкций:

00100001   инструкция add, складывает R[0] и R[1] и записывает результат в R[2]
10110000   инструкция li, записывает непосредственное значение 0000 в R[3]
10000101   инструкция li, записывает непосредственное значение 0101 в R[0]

Хранимая программа

На самом деле компьютеры, которые мы считаем почти всемогущими, выполняют разнообразные сложные задачи, непрерывно исполняя последовательность инструкций. Различные программы, которые вы запускаете на своём компьютере, в конечном счёте тоже исполняют последовательность инструкций. Поэтому суть программы — это последовательность инструкций. Вам может быть трудно в это поверить, ведь рассмотренные выше инструкции очень просты и ничем не отличаются от инструкций электронного калькулятора. Так почему же компьютеры настолько мощнее электронных калькуляторов?

Ответ кроется в том, как работают компьютеры: они позволяют программе автоматически управлять выполнением компьютера. А именно, мы можем сначала сохранить последовательность инструкций в памяти (такой как RAM (оперативная память) современных компьютеров) и заставить компьютер извлекать инструкции из памяти для выполнения; что особенно важно, после того как компьютер завершает выполнение одной инструкции, он переходит к выполнению следующей инструкции. Чтобы компьютер знал, где находится следующая инструкция, также нужен компонент, указывающий, какая инструкция выполняется в данный момент, — этот компонент называется «счётчиком команд» (Program Counter, PC). Теперь компьютеру нужно делать только одно:

Повторяйте следующие шаги:
  Извлеките инструкцию из ячейки памяти, на которую указывает PC.
  Выполните инструкцию.
  Обновите PC.

Таким образом, нам достаточно разместить последовательность инструкций в памяти, затем направить PC на первую инструкцию, и компьютер автоматически, без остановки, выполнит эту последовательность инструкций. В этом заключается основная идея компьютеров «с хранимой программой». По сути, все современные распространённые компьютеры — это компьютеры «с хранимой программой».

Есть решение ещё более изящное! Поскольку PC хранит адрес выполняемой в данный момент инструкции, PC тоже должен быть регистром. В этом случае мы также можем спроектировать соответствующие инструкции для его изменения, тем самым повышая гибкость процесса выполнения программы. Например, мы можем добавить третью инструкцию к двум упомянутым выше:

 7  6 5         2 1  0
+----+---- -----+-----+
| 11 |   addr   | rs2 | if (R[0]!=R[rs2]) PC=addr инструкция bner0, переход, если не равно R[0]
+----+----------+-----+

Инструкция bner0 довольно особая: она означает Branch if Not Equal r0 («переход, если не равно r0»). Если при выполнении этой инструкции R[rs2] и R[0] не равны, регистр PC обновляется значением addr, то есть PC начинает указывать на инструкцию по адресу addr. Однако регистр PC не используется для обработки данных общего назначения, поэтому он не относится к GPR.

С этими инструкциями теперь можно заставить компьютер выполнять более сложные задачи.

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

Вычислим с помощью инструкций сумму последовательности 1+2+...+10. Для простоты понимания мы не будем представлять инструкции с помощью 0 и 1. Мы будем использовать r0, r1, r2 и r3 для обозначения четырёх GPR, а операнды инструкций будем разделять запятыми. Предположим, что в памяти хранится следующая последовательность инструкций для вычисления суммы указанной выше последовательности, где число перед : обозначает счётчик команд (PC), а текст после # обозначает комментарий:

0: li r0, 10   # Это десятичное 10.
1: li r1, 0
2: li r2, 0
3: li r3, 1
4: add r1, r1, r3
5: add r2, r2, r1
6: bner0 r1, 4
7: bner0 r3, 7

На первый взгляд может быть трудно понять, как приведённая выше последовательность инструкций реализует суммирование последовательности чисел. Представим себя процессором и разберёмся в процессе, выполняя инструкции одну за другой. Чтобы понять процесс выполнения инструкций, нам также нужно фиксировать изменения регистров. Мы будем использовать формат (PC, r0, r1, r2, r3) для записи значений регистров, что также отражает состояние процессора. Например, (7, 2, 3, 1, 8) означает, что следующая инструкция, которую нужно выполнить, имеет номер 7, а текущие значения четырёх GPR равны 2, 3, 1 и 8. Договоримся, что изначально состояние процессора — (0, 0, 0, 0, 0). Ниже показан процесс выполнения процессором нескольких инструкций:

PC r0 r1 r2 r3
(0, 0, 0, 0, 0)   # начальное состояние
(1, 10, 0, 0, 0)  # После выполнения инструкции с PC = 0 r0 обновляется до 10, а PC обновляется на адрес следующей инструкции.
(2, 10, 0, 0, 0)  # После выполнения инструкции с PC = 1 r1 обновляется до 0, а PC обновляется на адрес следующей инструкции.
(3, 10, 0, 0, 0)  # После выполнения инструкции с PC = 2 r2 обновляется до 0, а PC обновляется на адрес следующей инструкции.
(4, 10, 0, 0, 1)  # После выполнения инструкции с PC = 3 r3 обновляется до 1, а PC обновляется на адрес следующей инструкции.
(5, 10, 1, 0, 1)  # После выполнения инструкции с PC = 4 r1 обновляется до r1 + r3, а PC обновляется на адрес следующей инструкции.
(6, 10, 1, 1, 1)  # После выполнения инструкции с PC = 5 r2 обновляется до r2 + r1, а PC обновляется на адрес следующей инструкции.
(4, 10, 1, 1, 1)  # После выполнения инструкции с PC = 6, поскольку r1 не равно r0, PC обновляется до 4.
(5, 10, 2, 1, 1)  # После выполнения инструкции с PC = 4 r1 обновляется до r1 + r3, а PC обновляется на адрес следующей инструкции.
......

Продолжите выполнение приведённых выше инструкций

Попробуйте продолжить выполнение инструкций и зафиксировать изменения состояний регистров. В каком состоянии окажется процессор по завершении выполнения? В каком регистре хранится сумма приведённой выше последовательности?

Как видите, процессор работает, механически обновляя состояние регистров в соответствии со смыслом инструкций. На этом этапе вы уже разобрались в основных принципах работы процессора.

На самом деле, преимущество компьютеров заключается в их чрезвычайно высокой скорости обработки: тактовая частота современных процессоров достигла уровня ГГц. Возьмём для примера 2 ГГц — это означает, что за одну секунду процессор проходит 2 000 000 000 тактов. Вычисление 1+2+...+10 с помощью упомянутой выше последовательности инструкций требует менее 40 инструкций. Если предположить, что за такт выполняется одна инструкция, современному процессору потребуется всего 0.00000002 с, то есть 20 нс, чтобы завершить вычисление. Если бы мы вручную пользовались электронным калькулятором, нажатие 10 клавиш в секунду уже считалось бы очень быстрым, но для ввода 1+2+...+10= потребовалось бы 22 нажатия клавиш, что заняло бы примерно 2 секунды. Чтобы вычислить 1+2+...+10000, нам достаточно изменить приведённую выше инструкцию с PC, равным 0, на li r0, 10000 (хотя для представления непосредственного значения 10000 потребуется более длинная инструкция), и тем же способом это потребовало бы около 30 000 инструкций, что заняло бы всего 0.000015 с, то есть 15 мкс. Если бы это делалось вручную на электронном калькуляторе, потребовалось бы 48 894 нажатия клавиш, что заняло бы 4889 секунд! Даже если вычислять в уме по формуле суммы арифметической прогрессии ((10 000 + 1) * 10 000 / 2), на то, чтобы получить верный ответ, всё равно ушло бы несколько секунд, что меркнет по сравнению с мощью компьютера.

Переосмысление программирования

Возможно, вы и раньше сталкивались с языками программирования, но вряд ли много размышляли о сути программирования. На самом деле программирование — это процесс решения сложных задач путём комбинирования заданных функций. Возможно, вы сталкивались с такими языками программирования, как C++, Python и Scratch, — все они являются языками программирования высокого уровня. Приведённый выше пример, где сумма последовательности вычисляется с помощью комбинации инструкций, — это тоже программирование!

Приведённые выше инструкции, такие как add и li, относятся к категории языка ассемблера в области компьютерных наук. Язык ассемблера — это символьное представление инструкций. По сравнению с языком ассемблера, есть ещё более низкоуровневый машинный язык — двоичное представление инструкций. Он может выполняться непосредственно процессором, реализованным с помощью цифровых схем. Например, представление на машинном языке приведённой выше программы суммирования последовательности выглядит так:

10001010    # 0: li r0, 10
10010000    # 1: li r1, 0
10100000    # 2: li r2, 0
10110001    # 3: li r3, 1
00010111    # 4: add r1, r1, r3
00101001    # 5: add r2, r2, r1
11010001    # 6: bner0 r1, 4
11011111    # 7: bner0 r3, 7

На самом деле, приведённое выше представление на машинном языке переводит язык ассемблера в последовательность 0 и 1 на основе ранее согласованного кодирования инструкций. Пока вы понимаете правила кодирования инструкций, язык ассемблера и машинный язык можно свободно преобразовывать друг в друга. Однако программисту трудно понимать машинный язык сам по себе. В отличие от него, язык ассемблера способен более наглядно представлять коды операций и операнды инструкций, что делает его более читаемым, чем машинный язык.

Вычислите сумму нечётных чисел меньше 10

Попробуйте написать программу, используя приведённые выше инструкции, чтобы вычислить сумму нечётных чисел меньше 10, то есть вычислить 1+3+5+7+9. Написав программу, попробуйте перечислить изменения состояния процессора, чтобы проверить, верна ли написанная вами программа.

Модель автомата состояний архитектуры системы команд

Упомянутые выше GPR, PC, память, инструкции и процессы их выполнения относятся к категории архитектуры системы команд (Instruction Set Architecture, ISA) в области компьютерных наук. Возможно, вы слышали о таких понятиях, как x86, ARM и RISC-V, — все они являются примерами ISA. Рассмотренный ранее пример всего с тремя инструкциями — тоже разновидность ISA. Для удобства мы будем называть её sISA (simple ISA, «простая ISA»).

По своей сути ISA — это набор спецификаций, которые обычно документируются в соответствующих руководствах. Эти спецификации определяют функции и поведение модельной машины. Модельная машина — это машина, существующая только в сознании. Мы обсуждаем только её функции и поведение, а не конкретную реализацию. Поэтому, изучая модельную машину, мы можем отделить принципы от деталей реализации, что помогает понять суть процессора. Когда мы реализуем эту существующую в сознании модельную машину с помощью цифровых схем, мы получаем настоящий компьютер.

Прежде чем подробнее объяснить, что именно входит в ISA, сначала введём математическую модель, которая очень важна для понимания компьютерных систем: автомат состояний.

Определение автомата состояний включает следующие части:

• Множество состояний
• Множество событий
• Правила перехода состояний . Описывают следующее состояние для каждого состояния при разных событиях, то есть бинарная функция задаёт следующее состояние после получения стимулирующего события в состоянии
• Начальное состояние

Хотя приведённое выше определение не является строгим на 100% в математическом смысле, его достаточно, чтобы понять поведение компьютерных систем.

Теперь разберёмся с ISA с точки зрения автомата состояний:

• Множество состояний. Вспомним соответствующее содержание про последовательностные логические схемы: состояния — это элементы, способные устойчиво хранить информацию. Расширяя этот смысл, в ISA состояния должны включать PC, GPR и память. То есть состояние в ISA — это конкретная комбинация PC, GPR и памяти, а множество всех состояний — это комбинация всех возможных значений PC, GPR и памяти, то есть .
• Множество событий. В ISA выполнение инструкции меняет состояние, поэтому выполнение инструкции — это событие для данного автомата состояний.
• Правила перехода состояний. По определению, в ISA правила перехода состояний описывают «следующее состояние после выполнения некоторой инструкции в заданном состоянии», то есть семантику инструкции. Они задают, как должно измениться состояние после выполнения определённой инструкции, тем самым осуществляя переход из одного состояния в другое.
• Начальное состояние. Состояние до выполнения каких-либо инструкций.

Возьмём в качестве примера упомянутую выше sISA — её модель автомата состояний выглядит так:

• Множество состоянийНапример, в примере с суммированием последовательности некоторое состояниегде обозначает информацию, хранящуюся в памяти, — это кодировка упомянутой ранее последовательности инструкций. Однако, поскольку инструкции в sISA не изменяют информацию, хранящуюся в памяти, для упрощения представления описание памяти в состоянии можно опустить: .
• Как конкретная ISA, sISA тоже использует выполнение инструкции в качестве события.
• В sISA правила перехода состояний — это семантика следующих трёх инструкций:

7 6 5 4 3 2 1 0
+---+---+---+---+
| 00| rd| rs1| rs2| R[rd]=R[rs1]+R[rs2]
+----+----+-----+-----+
| 10 | rd |    imm    | R[rd]=imm                 инструкция li, загружает непосредственное число, старшие биты заполняются нулями
+----+----+-----+-----+
| 11 |   addr   | rs2 | if (R[0]!=R[rs2]) PC=addr инструкция bner0, если не равно R[0], то переход
+----+----------+-----+

Например, означает, что при состоянии выполнение инструкции 00101001 даёт следующее состояние . Согласно приведённому выше, поведение этой инструкции — R[2] = R[2] + R[1], поэтому . Это, по сути, один из шагов в процессе выполнения рассмотренного выше примера суммирования последовательности.

• Начальное состояние .

Жизнь подобна пьесе

Выше мы уже объяснили, как работают компьютеры, с помощью естественного языка и примера суммирования последовательности. Причина, по которой мы вводим модель автомата состояний, наполненную математическими символами, в том, чтобы помочь вам раскрыть тайну компьютеров: с момента своего появления работа компьютеров — это математическая игра, а модель автомата состояний — это просто правила этой математической игры. На самом деле, будь то упомянутый выше набор команд или программы и процессоры, которые мы рассмотрим позже, эти базовые понятия компьютеров по сути согласуются друг с другом: все они — часть математической игры под названием «автомат состояний». Поэтому, если вы освоили правила этой игры, вы уже готовы понимать компьютеры.

Что касается реальных ISA промышленного уровня, таких как x86, ARM и RISC-V, у них больше GPR, больше инструкций и более сложное поведение инструкций. Однако их фундаментальные принципы по сути такие же, как у рассмотренной выше sISA всего с тремя инструкциями. Поэтому, если в будущем вам понадобится в них разобраться, вам достаточно будет прочитать соответствующие руководства, чтобы узнать больше о деталях инструкций.

Подробнее об ISA

Помимо семантики инструкций, ISA также охватывает ввод/вывод (I/O), состояние системы, прерывания и исключения, управление виртуальной памятью и модели памяти. По мере продвижения в обучении мы будем последовательно вводить эти понятия. У вас также будет возможность реализовать эти понятия в собственном, спроектированном вами процессоре, тем самым значительно усилив его.

Программирование на C для начинающих

В предыдущем разделе мы рассмотрели язык ассемблера. Хотя на языке ассемблера можно программировать, он неудобен для разработки более крупных программ. Это связано с тем, что программирование на языке ассемблера требует внимания к тому, как данные перетекают между GPR, а каждая инструкция обычно может выполнять лишь немного операций. Даже простая логика программы может потребовать для своего выражения более десятка инструкций. На практике современная разработка программ обычно использует языки программирования высокого уровня.

Существует много языков программирования высокого уровня, но мы выбрали C, потому что это один из более простых языков программирования высокого уровня. Мы можем легко связать C с процессом работы компьютерных систем, что помогает понять суть компьютеров.

Простой пример на языке C

Начнём с простого примера кода:

#include <stdio.h>

/* 1 */ int main() {
/* 2 */   int x = 1;
/* 3 */   int y = 2;
/* 4 */   int z = x + y;
/* 5 */   printf("z = %d\n", z);
/* 6 */   return 0;
/* 7 */ }

Этот пример вычисляет 1+2 и выводит результат. Разберём детали кода:

• Содержимое между /* и */ — это комментарий на языке C. Комментарии не влияют на логику программы, поэтому они предназначены главным образом для чтения программистами. Например, приведённый выше код и код ниже логически эквивалентны:

#include <stdio.h>

/* This is
   an example. */
int main() {
  int x = 1;
  int y = 2;
  int z = x + y;
  printf("z = %d\n", z);
  return 0;
}

• int обозначает целочисленный тип и является сокращением от integer.

• int main() { ... } определяет функцию с именем main. Функции — это базовые модули языка C. Процесс выполнения программы на C — это процесс выполнения кода функций в программе на C. В частности, функция main — особая функция. Она является точкой входа программы на C, то есть выполнение программы на C начинается с функции main.

• Содержимое внутри фигурных скобок { ... } — это тело функции, состоящее из операторов. Каждый оператор указывает программе выполнить какое-либо действие. Операторы внутри фигурных скобок по умолчанию выполняются по порядку.

• int x = 1; определяет переменную с именем x и присваивает ей начальное значение 1. Переменные — это объекты, хранящие информацию в программе, подобно упомянутым выше GPR. В языке C оператор заканчивается точкой с запятой ;. int y = 2; работает точно так же.

• int z = x + y; определяет переменную z и присваивает ей начальное значение x + y.

• printf("z = %d\n", z); — это оператор вызова функции, вызывающий функцию printf. Вызовы функций в программах похожи на вычисление значений функций в математике. Например, в математике, если задано , то процесс нахождения заключается в подстановке в определение и выполнении вычисления; printf("z = %d\n", z); подставляет два параметра, "z = %d\n" и z, в определение printf и выполняет его. В программе на C printf — это специальная функция, используемая для вывода информации в терминал. %d в первом параметре указывает, что второй параметр, z, нужно вывести в десятичном формате. Таким образом, приведённый выше вызов функции выводит текущее значение переменной z в десятичном формате в терминал.

• return 0; — это оператор возврата из функции, означающий, что выполнение функции завершено, и возвращающий 0 в качестве результата вычисления в оператор, вызвавший функцию. В этом примере мы познакомились с некоторыми ключевыми строительными блоками языка C:

1. Переменные — объекты, обрабатываемые программой на C
2. Операторы — описывают последовательность действий, выполняемых программой на C
3. Функции ввода/вывода — обеспечивают мост между переменными в программе на C и внешним миром

Запустите программу на C онлайн

Вы можете запустить приведённую выше программу на C на онлайн-сайте Compiler Explorer. А именно, введя приведённый выше код на C в редакторе кода, нажмите Add new... на панели инструментов над редактором, выберите Execution Only, и появится окно терминала с результатами выполнения. Если вы всё сделали правильно, в окне терминала вы увидите вывод z = 3. Вы можете попробовать изменить код на C по своему усмотрению и понаблюдать за выводом программы. Подсказка: вы можете добавить этот сайт в закладки, так как будете использовать его как среду разработки на ранних этапах этапа E.

Следует отметить, что приведённое выше объяснение не охватывает все соответствующие детали языка C. Некоторые детали пока нельзя объяснить ясно, поэтому мы их пока опустим. Однако приведённого выше объяснения достаточно, чтобы понять остальную часть хендаута.

Модель автомата состояний программ на C

Возможно, вы уже почувствовали, что понятия переменных и операторов в языке C в чём-то похожи на упомянутые выше понятия GPR и инструкций в ISA. На самом деле, с точки зрения компьютерных систем, они действительно тесно связаны. Подобно ISA, программы на C тоже можно понимать с точки зрения автомата состояний:

• Множество состояний. В программах на C наиболее непосредственное состояние — это переменные, поскольку они являются объектами, хранящими информацию. Кроме того, как упоминалось ранее: «операторы внутри фигурных скобок по умолчанию выполняются по порядку». Естественно, во время выполнения программы на C также нужна неявная переменная, указывающая, какой оператор выполняется в данный момент, — эта неявная переменная и есть «счётчик команд» (PC) в языке C, и она тоже должна входить в состояние. Поэтому в программе на C состояние — это набор конкретных значений переменных и PC, а множество всех состояний — это комбинация всех возможных значений переменных и PC, то есть , где обозначает значения всех переменных программы.

• Множество событий. В программах на C выполнение операторов меняет состояние, поэтому выполнение операторов — это событие для данного автомата состояний.

• Правила перехода состояний. Согласно поведению программ на C, правила перехода состояний описывают «следующее состояние после выполнения некоторого оператора в некотором состоянии», то есть семантику оператора. Они задают, как должно измениться состояние после выполнения определённого оператора, чтобы произошёл переход из одного состояния в другое.

• Начальное состояние. Состояние до выполнения каких-либо операторов, то есть .

Изложив приведённую выше модель автомата состояний, мы можем понять процесс выполнения программы на C с точки зрения автомата состояний. Рассматривая приведённый выше пример кода, пусть PC обозначает строку, которую выполняет программа, а номер строки указан с помощью комментариев. Мы будем использовать формат (PC, x, y, z) для записи состояния приведённой выше программы. Согласно соглашениям языка C, начальное состояние — (2, ?, ?, ?), где PC равно 2, что означает, что выполнение начинается со строки 2, то есть с первого оператора функции main, а ? означает, что переменная ещё не определена или не инициализирована. Ниже показан процесс выполнения приведённой выше программы на C:

PC  x  y  z
(2, ?, ?, ?)    # начальное состояние
(3, 1, ?, ?)    # После выполнения оператора с PC = 2 x обновляется до 1, а PC обновляется на позицию следующего оператора.
(4, 1, 2, ?)    # После выполнения оператора с PC = 3 y обновляется до 2, а PC обновляется на позицию следующего оператора.
(5, 1, 2, 3)    # После выполнения оператора с PC = 4 z обновляется до x + y, а PC обновляется на позицию следующего оператора.
(6, 1, 2, 3)    # После выполнения оператора с PC = 5 терминал выводит 'z = 3', а PC обновляется на позицию следующего оператора.
(END, 1, 2, 3)  # После выполнения оператора с PC = 6 программа возвращается из функции main, и выполнение завершается.

Реализация суммирования последовательности на C

Мы также можем использовать язык C, чтобы вычислить 1+2+...+10. Рассмотрим следующую программу на C:

#include <stdio.h>

/* 1 */ int main() {
/* 2 */   int sum = 0;
/* 3 */   int i = 1;
/* 4 */   do {
/* 5 */     sum = sum + i;
/* 6 */     i = i + 1;
/* 7 */   } while (i <= 10);
/* 8 */   printf("sum = %d\n", sum);
/* 9 */   return 0;
/* 10*/ }

Приведённый выше код содержит цикл do-while, который ведёт себя так: сначала выполняются операторы в теле цикла (в фигурных скобках), затем проверяется, истинно ли условие цикла (в круглых скобках). Если истинно, тело цикла повторяется; иначе цикл завершается, и выполняются последующие операторы.

По сравнению с языком ассемблера, упомянутым ранее, можно увидеть как минимум два преимущества разработки программ на языке C:

1. Имена переменных могут более наглядно отражать их назначение, тогда как в языке ассемблера назначение GPR можно определить только по контексту.
2. Выражения циклов более понятны и позволяют напрямую различать условие цикла и тело цикла, тогда как в языке ассемблера условие цикла и тело цикла — это одни и те же инструкции, и их приходится различать по контексту.

Согласно приведённой выше программе, процесс выполнения предшествующих операторов выглядит так:

PC sum i
(2, ?, ?)   # начальное состояние
(3, 0, ?)   # После выполнения оператора с PC = 2 sum обновляется до 0, а PC обновляется на следующий оператор.
(5, 0, 1)   # После выполнения оператора с PC = 3 i обновляется до 1, а PC обновляется на следующий оператор (строка 4 не выполняет никаких действий и пропускается).
(6, 1, 1)   # После выполнения оператора с PC = 5 sum обновляется до sum + i, а PC обновляется на следующий оператор.
(7, 1, 2)   # После выполнения оператора с PC = 6 i обновляется до i + 1, а PC обновляется на следующий оператор.
(5, 1, 2)   # После выполнения оператора с PC = 7, поскольку условие цикла i <= 10 истинно, выполнение возвращается к телу цикла.
......

Продолжите выполнение приведённой выше программы

Попробуйте продолжить выполнение приведённого выше кода и зафиксировать изменения состояния. В каком состоянии окажется программа по завершении выполнения?

Модель автомата состояний цифровых схем

В предыдущем абзаце мы упомянули «реализацию этой существующей в сознании модельной машины с помощью цифровых схем». Это означает, что цифровые схемы тоже могут установить некую связь с ISA. Так можем ли мы также понимать поведение цифровых схем с точки зрения автомата состояний?

Ответ — да! Опираясь на знания о цифровых схемах из предыдущего раздела, можно легко сформулировать модель автомата состояний цифровых схем:

• Множество состояний. В цифровых схемах только последовательностные логические схемы способны хранить информацию. Поэтому состояние — это конкретная информация, хранимая последовательностным логическим элементом, а множество всех состояний — это комбинация всей информации, которую способны хранить последовательностные логические элементы.

• Множество событий. Поскольку последовательностные логические элементы представляют состояния цифровой схемы, а внутреннее состояние последовательностных логических элементов можно изменить через их входные выводы (например, данные можно записать в D-триггер через его входной вывод), цифровую схему можно рассматривать в виде следующей модели:

    +------------------+
+-->| Sequential Logic |----+
|   +------------------+    |
| next state                | current state
|                           |
|  +---------------------+  |
+--| Combinational Logic |<-+
   +---------------------+

    +-----------------------------+
+-->| Последовательностная логика |----+
|   +-----------------------------+    |
| следующее                            | текущее
| состояние                            | состояние
|                                      |
|   +-----------------------+          |
+---| Комбинационная логика |<---------+
    +-----------------------+

Иными словами, именно сигнал, выдаваемый комбинационной логической схемой, вызывает изменение состояния последовательностного логического элемента. Поэтому комбинационная логическая схема — это событие для данного автомата состояний.

• Правила перехода состояний. То, как должно измениться состояние последовательностного логического элемента, определяется конкретной логикой комбинационной логической схемы.

• Начальное состояние. Это состояние последовательностного логического элемента в момент сброса схемы.

Например, структура схемы счётчика Джонсона выглядит так:

Опираясь на логику структуры схемы, можно понять процесс работы приведённого выше счётчика Джонсона с точки зрения автомата состояний:

 A  B  C  D
(0, 0, 0, 0)    # начальное состояние
(1, 0, 0, 0)
(1, 1, 0, 0)
(1, 1, 1, 0)
(1, 1, 1, 1)
(0, 1, 1, 1)
(0, 0, 1, 1)
(0, 0, 0, 1)
(0, 0, 0, 0)    # совпадает с начальным состоянием

Поймите работу схемы суммирования последовательности с точки зрения автомата состояний

В предыдущем подразделе вы построили простую схему суммирования последовательности из регистров и сумматоров, чтобы вычислить 1+2+...+10. Попробуйте перечислить изменения состояния схемы.

Разумеется, этот пример со счётчиком Джонсона сильно отличается от CPU, но если CPU можно спроектировать с помощью цифровых схем, он тоже обязательно должен содержать последовательностные логические схемы и комбинационные логические схемы, а значит, работу CPU тоже можно понимать с точки зрения автомата состояний.

Выполнение программ на C на компьютере

Мы понимаем процесс выполнения программы на C с точки зрения автомата состояний, что по сути означает выполнение программы на C в нашем сознании. Однако компьютеры способны выполнять только инструкции; они не могут понимать смысл программы на C, поэтому не могут выполнять код вроде sum = sum + i;. Так как же заставить компьютер выполнить программу на C? Ответ — перевести код программы на C в поведенчески эквивалентную последовательность инструкций, а затем заставить схемы компьютера выполнить эту последовательность инструкций.

Компиляция = перевод кода C в последовательность инструкций

У этого процесса в компьютерных системах есть специальное название: «компиляция». В принципе, компиляцию можно выполнить вручную, но современные программы очень велики, и ручная компиляция очень утомительна. Поэтому компиляцию обычно выполняет специальный тип программы, называемый «компилятором».

Поскольку и выполнение программ на C, и выполнение последовательностей инструкций можно понимать с точки зрения автомата состояний, мы также можем попробовать понять, какие задачи должен решать компилятор. Сначала перечислим содержимое двух автоматов состояний (начальное состояние здесь рассматривать не будем):

	Программа на C	ISA
Состояние
Событие	Выполненный оператор	Выполненная инструкция
Правило перехода состояний	Семантика оператора	Семантика инструкции

Поэтому задача компилятора — перевести автомат состояний программы на C в автомат состояний ISA, иными словами, построить

так, чтобы

тогда,

Здесь обозначает -е состояние автомата состояний языка C, а обозначает -е состояние автомата состояний ISA. На естественном языке это означает: состояние программы на C после выполнения оператора семантически эквивалентно состоянию ISA после выполнения последовательности инструкций, полученной в результате компиляции.

А именно, сравнив два автомата состояний, можно увидеть, что компилятору нужно выполнить следующие задачи:

• Перевести состояние программы на C в состояние ISA, то есть
  • Отобразить PC программы на C на PC ISA
  • Отобразить переменные программы на C на GPR или память ISA
• Перевести правила перехода состояний программы на C в правила перехода состояний ISA, то есть перевести операторы в последовательности инструкций.

Разберитесь в работе компилятора на примере суммирования последовательности чисел

Мы уже привели программу на C для суммирования последовательности чисел и соответствующую последовательность инструкций. Попробуйте разобраться в связи между ними с точки зрения автомата состояний.

Разберитесь в работе компилятора в Compiler Explorer

А именно, нажмите Add new... на панели инструментов над редактором, выберите Compiler, и появится окно с соответствующим кодом на ассемблере. По умолчанию ассемблерный код использует набор команд x86. Вы можете не понимать конкретный смысл каждой инструкции, но, наводя мышь и наблюдая за подсветкой фона, вы сможете увидеть соответствие между фрагментом кода на C и фрагментом ассемблерного кода.

Проектирование CPU = проектирование цифровых схем на основе ISA

Аналогично, поскольку и ISA, и цифровые схемы можно понимать с точки зрения автомата состояний, мы также можем попробовать понять, как должно вестись проектирование CPU. Сначала перечислим содержимое двух автоматов состояний (начальное состояние здесь рассматривать не будем):

	ISA	Цифровая схема
Состояние		Последовательностная логическая схема
Событие	Выполнение инструкции	Обработка комбинационной логики
Правило перехода состояний	Семантика инструкции	Логика комбинационной логической схемы

Поэтому задача проектирования CPU — реализовать автомат состояний ISA с помощью автомата состояний цифровой схемы, иными словами, построить

так, чтобы

тогда,

Здесь обозначает -е состояние автомата состояний схемы CPU. На естественном языке это означает: состояние после выполнения ISA инструкции семантически эквивалентно следующему состоянию спроектированного CPU под управлением комбинационных логических схем.

А именно, сравнив два автомата состояний, можно увидеть, что при проектировании CPU нужно решить следующие задачи:

• Реализовать состояния ISA с помощью состояний цифровой схемы, то есть реализовать PC, GPR и память с помощью последовательностных логических схем.
• Реализовать правила перехода состояний ISA с помощью правил перехода состояний цифровой схемы, то есть реализовать функции инструкций с помощью комбинационных логических схем.

Взаимосвязь между программами, ISA и CPU

На этом этапе мы можем кратко подытожить взаимосвязь между программой, ISA и CPU:

1. На основе функционального описания в руководстве по ISA нарисовать структуру CPU -> проектирование микроархитектуры процессора
2. На основе структурного проекта спроектировать конкретную схему -> логическое проектирование
3. Разработать программу -> программирование
4. Перевести программу в последовательность инструкций, описанную в руководстве по ISA -> компиляция
5. Выполнить программу на CPU = использовать скомпилированную из программы последовательность инструкций, чтобы управлять переходами состояний схем CPU

• На этом этапе три автомата состояний оказываются взаимосвязаны:

Если это можно объяснить одной фразой, зачем всё так усложнять?

Это потому, что модель автомата состояний — эффективный способ понимания сложных систем. Анализ определённых понятий и проблем с точки зрения модели автомата состояний может дать нам новые озарения. По мере углубления в проект «ysyx» («One Student One Chip») мы будем продолжать использовать модели автоматов состояний, чтобы анализировать ключевые вопросы и предлагать эффективные решения.

Однако самое важное, что нужно донести до каждого, — это: машина всегда права. Поведение компьютерной системы происходит именно так, как описано в официальных руководствах, и каждый переход состояния в системе подкреплён этими документами. Иными словами, если вы не можете понять поведение компьютерной системы, весьма вероятно, что вы упускаете какие-то важные детали в соответствующих руководствах.

Когда вы только начинаете изучать «ysyx», вас может захлестнуть волна незнакомых понятий. Однако для решения проблем крайне важно выработать правильный настрой. Некоторые начинающие могут задаваться вопросами вроде «а нет ли проблемы в операционной системе?» или «а нет ли бага в компиляторе?». Такие непрофессиональные предположения не помогут ни по-настоящему решить проблему, ни по-настоящему вырасти.

Разумеется, слово «всегда» здесь не означает, что машины находятся вне всякого сомнения. В реальности в коммерческих продуктах тоже встречаются баги — например, исторически печально известная ошибка деления с плавающей запятой в процессорах Intel Pentium. Тем не менее, когда профессионалы задаются вопросами, они всегда приводят доказательства того, что их сомнения не беспочвенны. Более того, чем менее вероятна проблема, тем строже должна быть проверка. Используемые вами компьютерные системы, скорее всего, обладают высокой степенью зрелости, поэтому вероятность того, что вы случайно столкнётесь с багом, изначально ничтожно мала; а если вы не можете предоставить убедительных доказательств, вероятность того, что виновата именно машина, ещё ниже.

От одного до бесконечности

Возможно, вам кажется, что приведённые выше примеры слишком просты. Действительно ли современные компьютеры работают именно так? Теперь давайте приподнимем завесу тайны над современными компьютерами.

Мы уже знаем, что благодаря использованию дополнительного кода компьютеры могут использовать один и тот же аппаратный сумматор для выполнения как арифметического сложения, так и вычитания. Предоставив новую инструкцию вычитания, программа может выполнять операции вычитания. Используя цикл, реализованный с помощью инструкции перехода, чтобы многократно выполнять инструкцию сложения, мы получаем функциональность арифметического умножения; а многократно выполняя инструкцию вычитания, можно получить функциональность арифметического деления.

Четыре арифметических действия над целыми числами уже реализованы выше, и реализовать операции над дробными числами несложно. Мы знаем, что в математике десятичную дробь можно представить с помощью научной записи. Компьютеры тоже могут представлять дробные числа аналогичным способом, но используют двоичную научную запись. А именно, любое дробное число можно представить как , где — беззнаковое число, представленное в двоичном виде, а — знаковое число, представленное в двоичном виде. Пока компьютер хранит и , это эквивалентно представлению дробного числа в двоичной форме. Очевидно, что арифметические операции над дробными числами тоже можно свести к арифметическим операциям над и .

После реализации арифметических операций над дробными числами мы можем вычислять базовые элементарные функции в математическом смысле, включая постоянные функции, степенные функции, показательные функции, логарифмические функции, тригонометрические функции и обратные тригонометрические функции. А именно, за исключением постоянных функций, остальные пять базовых элементарных функций можно вычислить с помощью разложения в степенной ряд, а степенной ряд можно вычислить с помощью арифметических операций и циклов.

После того как мы научились вычислять базовые элементарные функции, все элементарные функции можно вычислить с помощью конечного числа рациональных операций и композиций базовых элементарных функций. Вызовы функций в программе можно использовать для реализации композиции функций.

Мы можем продолжить дифференцировать и интегрировать функцию. Согласно определению производной, достаточно подставить очень малое , чтобы приближённо вычислить производную функции в некоторой точке. Согласно определению определённого интеграла, можно разбить интервал интегрирования на достаточное число отрезков, затем приближённо оценить значение функции на каждом отрезке по её значению в некоторой точке внутри отрезка, а затем вычислить сумму Римана функции на интервале, сложив эти значения. Разумеется, это простые и наглядные методы вычисления. Чтобы вычислять на компьютере более точные производные и интегралы, учёные разработали ряд алгоритмов численного анализа.

Все приведённые выше вычисления выполняются в области вещественных чисел. Распространить вычисления на область комплексных чисел на самом деле несложно. А именно, достаточно выполнить вычисления отдельно для вещественной и мнимой частей, а затем применить соответствующие правила для обработки мнимой единицы . Хотя некоторые операции в области комплексных чисел отличаются от операций в области вещественных чисел, пока метод вычисления можно описать математическим языком, всегда есть способ свести его к описанным выше операциям.

После того как поддержаны дифференцирование и интегрирование в комплексной области, мы можем реализовать в программе различные физические движки, моделирующие различные физические законы реального мира. Различные формулы механики, электромагнетизма, оптики и термодинамики вычисляются в программе с помощью последовательности простых инструкций, позволяя пользователям ощутить в компьютерном мире тот же самый физический мир. Всё, что мы переживаем внутри компьютера, достигается посредством вычислений!

Разумеется, чтобы сделать процесс вычислений более эффективным, современные ISA также предоставляют больше инструкций, включая инструкции умножения и деления, инструкции логических операций (такие как AND, OR, NOT и т. д.), инструкции для чисел с плавающей запятой, атомарные инструкции и так далее. Например, вместо реализации умножения через циклы, компьютеры предоставляют инструкции умножения и схемы умножителя, позволяя программам эффективно вычислять умножение с помощью инструкций умножения. Некоторые ISA даже предоставляют инструкции для непосредственного вычисления базовых элементарных функций, такие как инструкции извлечения квадратного корня и инструкции тригонометрических функций. Нетрудно представить, что обеспечение возможности вычислять эти базовые элементарные функции на уровне схемы требует от инженеров-электронщиков тщательной проработки.

Помимо предоставления более богатого набора инструкций, архитекторы компьютеров также стремятся проектировать компьютеры, более эффективно выполняющие инструкции. Например, конвейеризация может повысить пропускную способность по инструкциям, суперскалярное исполнение позволяет процессору выполнять несколько инструкций за один такт, кеширование может повысить эффективность обращений к памяти, а специализированные процессоры, такие как GPU, могут ускорять определённые задачи. В конечном счёте эти технологии предоставляют пользователям всё более высокую производительность.

Система команд и процессор — понятия разных уровней

По мере роста популярности RISC-V всё больше людей знакомятся с понятиями, связанными с процессорными чипами. Однако, поскольку «система команд» — понятие довольно абстрактное, многие неспециалисты не могут полностью в нём разобраться, из-за чего приходят к выводам, не соответствующим действительности.

На самом деле система команд и процессор — это понятия разных уровней: первое — это спецификация, а второе — конкретная реализация. У обоих есть три различные модели интеллектуальной собственности (IP):

1. Открытая и бесплатная: можно использовать без финансовых затрат.
2. Лицензируемая: можно использовать за плату.
3. Закрытая: нельзя использовать даже за плату.

Три IP-модели этих двух уровней можно объединить, образовав матрицу 3×3. Приведённый ниже рисунок взят из статьи Некоторые пояснения к RISC-V и процессорам с открытым исходным кодом.

Из рисунка можно сделать два вывода:

1. Закрытая система команд не может породить процессор с открытым исходным кодом; поэтому нижний левый треугольник матрицы пуст.
2. Открытая система команд не означает, что получившийся процессор обязательно должен быть с открытым исходным кодом; поэтому верхний правый треугольник матрицы не пуст.

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

На самом деле, будь то компьютер Z3 1941 года, выполнявший в среднем операций умножения в секунду, или суперкомпьютер, занявший первое место в списке Top500 за ноябрь 2024 года, с пиковой вычислительной производительностью операций с плавающей запятой в секунду, — принципы их работы фундаментально одинаковы. Хотя приведённые выше примеры сильно упрощены, их достаточно, чтобы помочь вам понять самые фундаментальные элементы компьютерных систем и связи между ними. В дальнейшем обучении мы продолжим уточнять эти понятия и в конечном итоге научимся проектировать настоящий чип CPU на основе настоящей ISA и запускать на нём настоящие программы.

zxz