Исследуйте Каир: практичная и эффективная архитектура ЦП с поддержкой Turing-Complete и STARK

Cairo — это практически эффективная Тьюринг-полная архитектура ЦП, дружественная к STARK.

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

Структура инструкции

Слово, изначально поддерживаемое ЦП Cairo, является элементом поля, где поле — это некоторое фиксированное конечное поле характеристики P>2^63.

Каждая инструкция будет занимать 1 или 2 слова. Если за инструкцией следует непосредственное значение（[ap] = «12345678»), инструкция займет 2 слова, а значение будет сохранено во втором слове. Первое слово каждой инструкции состоит из следующих элементов:

• off_dst[bit0…15]: смещение адреса назначения, репрезентативное значение

-2^{15} + ∑_{i = 0}^{15} b_i . 2^i ∈ [-2^{15}, 2^{15});

• off_op0[bit16…31]: смещение адреса op0, репрезентативное значение

-2^{15} + ∑_{i = 0}^{15} b_i . 2^i ∈ [-2^{15}, 2^{15});

• off_op1[bit32…47]: смещение адреса op1, репрезентативное значение

-2^{15} + ∑_{i = 0}^{15} b_i . 2^i ∈ [-2^{15}, 2^{15});

• dst reg[bit48]: базовый регистр смещения адреса получателя, ap или fp;

• op0 reg[bit49]: базовый регистр смещения адреса op0, ap или fp;

• op1_src[bit50…52]: адрес op1,

• Случай: 000
  op1=m(op0+off_op1)

• Дело: 001

op1=m(pc+off_op1)

• Случай: 010
  op1=m(fp+off_op1)

• Дело: 100

op1=m(ap+off_op1)

• res_logic bit53…54]: вычислительная логика

• Регистр: 00
  res = op1

• Случай: 01
  res = op0 + op1

• Случай: 10
  res = op0 ∗ op1

• pc_update[bit55…57]: логика обновления ПК

• Регистр: 000 // общий
  следующий_пк = пк + размер_инструкции

• Случай: 001 // абсолютный переход
  next_pc = res

• Case: 010 // относительный переход
  next_pc = pc + res

• Случай: 100 // условный относительный переход
  next_pc = pc + op1 (или размер_инструкции, если dst = 0)

• ap_update[bit58…59]: логика обновления ap

• Регистр: 00
  next_ap = ap (или ap+2, если код операции = 1)

• Случай: 01
  next_ap = ap + res

• Случай: 10
  next_ap = ap + 1

• opcode[bit60…62]: типы опкодов

• Регистр: 000 // jmp

• Регистр: 001 // вызов

• Дело: 010 // рет

• Случай: 100 // утверждать

Комментарий к переходу состояния

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

Поэтому нам необходимо:

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

1. убедиться, что выполняемая инструкция действительна.

Комментарий к логике перехода

Если состояние до и после выполнения инструкции согласовано, обновление состояния должно выполняться в соответствии со следующей логикой:

```javascript

Контекст: м(.).

Состояние ввода: (ПК, ап и фп).

Состояние вывода: (next_pc, next_ap и next_fp).

Вычислить op0.

Если op0_reg == 0: // Оценить базовый регистр op0 в соответствии со значением флага, 0 — это ap, 1 — это fp, и получить значение op0.

op0 = m(ap + off_{op0})

еще:

op0 = m(fp + off_{op0})

Вычислить op1 и размер инструкции.

switch op1_src: // Получить значение op1

случай 0:

инструкция_size = 1 // op1 = m[[ap/fp + off_op0] +off_op1], максимум с двухуровневым встраиванием.

op1 = m(op0 + off_{op1})

Дело 1:

инструкция_size = 2 // существуют непосредственные числа. Размер инструкции 2 слова.

op1 = m(pc + off_{op1})//

Если off_{op1} = 1, имеем op1 = немедленное_значение. // Например, [ap] = "12345678", op1 = "12345678"

случай 2:

инструкция_размер = 1 // op1 = [fp + off_op1]

op1 = m(fp + off_{op1})

случай 4:

инструкция_размер = 1 // op1 = [ap +off_op1]

op1 = m(ap + off_{op1})

По умолчанию:

Неопределенное поведение

Вычислить разрешение

если pc_update == 4: // jnz

if res_logic == 0 && код операции == 0 && ap_update != 1: // Назначить && прыжок && расширенный ап

res = Unused // При условном переходе значения флагов res_logic, opcode и ap_update могут быть только такими, как показано выше. В этом случае переменная res не будет использоваться.

еще:

Неопределенное поведение

иначе, если pc_update = 0, 1 или 2:

switch res_logic: // Вычислительная логика res:

случай 0: res = op1

случай 1: res = op0 + op1

случай 2: res = op0 * op1

по умолчанию: Неопределенное поведение

еще: Неопределенное поведение

Вычислить dst.

если dst_reg == 0:

dst = m(ap + offdst)

еще:

dst = m(fp + offdst)

Вычислить новое значение pc.

переключить pc_update:

case 0: # Общий случай: [ap] = 1

следующий_пк = пк + размер_инструкции

case 1: # Абсолютный прыжок: jmp abs 123

следующий_пк = разрешение

case 2: # Относительный переход: jmp rel [ap - 1]

next_pc = ПК + разрешение

case 4: # Условный относительный переход (jnz): jmp rel [ap - 1] if [fp - 7] = 0

следующий_ПК =

if dst == 0: pc + размер_инструкции // Если dst = 0, то pc выполняет обычные обновления; в остальном аналогично случаю 2.

else: pc + op1 // В этом случае res не используется, поэтому pc напрямую проводит + op1 вместо + res.

по умолчанию: Неопределенное поведение

Вычислить новое значение ap и fp на основе кода операции.

если код операции == 1:

Инструкция "Позвонить".

утверждать op0 == ПК + размер_инструкции

утверждать dst == fp

Обновить fp.

next_fp = ap + 2 // [ap] сохраняет текущее значение fp, [ap + 1] сохраняет пк после инструкции вызова; при выполнении инструкции ret удобно сбросить fp в [ap], а затем продолжить выполнение последующих инструкций.

Обновить ап.

переключить ap_update:

case 0: next_ap = ap + 2 // [ap] сохраняет значение fp, а [ap+1] сохраняет адрес инструкции после инструкции вызова; таким образом, ар увеличивается на 2.

по умолчанию: Неопределенное поведение

иначе, если код операции является одним из 0, 2, 4:

Обновить ап.

переключить ap_update:

case 0: next_ap = ap // [fp + 1] = 5

случай 1: next_ap = ap + res // расширенный ap [ap] += 123

случай 2: next_ap = ap + 1 // обычный [fp + 1] = [ap]; ап++

по умолчанию: Неопределенное поведение

код операции switch: // Внутри одной и той же функции значение fp остается неизменным.

случай 0:

следующий_кадр = кадр

случай 2:

инструкция "возврата".

next_fp = dst // Инструкция ret идет с инструкцией call и утверждает dst == fp.

случай 4:

Инструкция "подтвердить равенство".

утверждать res = dst

следующий_кадр = кадр

еще: Неопределенное поведение

Проверка инструкции

Как показано на рисунке 1, одна инструкция состоит из следующих элементов:

```javascript

инструкция по структуре :=

(off_dst: битвек 16)

(off_op0: битвек 16)

(off_op1: битвек 16)

(флаги: битвек 15)

Где:

off_dst[ бит0…15], off_op0[ бит16…31], off_op1[ бит32…47] находятся в диапазоне

-2^{15} + ∑_{i = 0}^{15} b_i . 2^i ∈ [-2^{15}, 2^{15})

Но в AIR мы преобразуем их в следующий вид:

˜выкл = выкл + 2^15

(Где * представляет один из dst, op0 и op1)

Таким образом, диапазон значений ˜off* должен быть [0,2^16)

Следовательно, для кодирования инструкции имеем:

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

˜f_i=∑_{j=i}^{14} 2j−i⋅fj

При длине 16Н, что соответствует следующим требованиям:

1. ˜f_0 = ∑_{j=0}^{14} 2^{j-0}⋅f_j – 15-битное значение.

1. ˜f_15 = 0

1. ˜f_i −2˜f_{i+1} = ∑{j=i}^{14} (2^{j−i}⋅f_j) − 2⋅∑{j=i+1}^ {14}(2^{j−i−1}⋅fj) =∑_{j=1}^{14}(2j−i⋅fj) − ∑{j=i+1}^{14}(2j −i⋅fj)=fi

Следовательно, уравнение (1) можно записать в виде:

inst = ˜off_dst + 2^16⋅˜off_op0 + 2^32⋅˜off_op1 + 2^48⋅˜f0 ∈ [0,263)(2)

Поскольку характеристика конечного поля P > 2^63, одна инструкция может соответствовать только одному действительному элементу поля.

Поэтому для самой инструкции должны выполняться следующие ограничения:

Инструкция: inst= ˜off_dst + 2^16⋅˜off_op0 + 2^32⋅˜off_op1 + 2^48⋅˜f0

Бит： (˜f_i−2˜f_i +1)(˜f_i−2˜f_i+1 −1)=0 для всех i ∈ [0,15)

Последнее значение равно нулю: ˜f_15=0

Смещение находится в диапазоне: виртуальный столбец ˜off ∈ [0,2^16), поэтому off** ∈ [2^−15, 2^15)

Примеры инструкций

Подтвердить равенство

Инструкция утверждения равенства может быть выражена в следующем синтаксисе:

= <правая_handle_op>

Это гарантирует, что обе части формулы равны; в противном случае выполнение программы будет отклонено.

Левая часть уравнения часто получается из [fp+off_dst] или [ap+off_dst], а правая часть имеет несколько возможных форм (reg_0 и reg_1 может быть fp или ap, ∘ может быть сложением или умножением, а imm может быть любым фиксированным элементом поля):

• имм

• [reg1+offop1][reg1+offop1]

• [reg0+offop0]∘[reg1+offop1][reg0+offop0]∘[reg1+offop1]

• [reg0+offop0]∘imm[reg0+offop0]∘imm

• [[reg0+offop0+offop1][[reg0+offop0+offop1]

Примечание 2. Деление и вычитание могут быть выражены как умножение и сложение с разным порядком операндов соответственно.

Инструкцию assert можно рассматривать как инструкцию присваивания, в которой значение одной стороны известно, а значение другой стороны неизвестно.

Например, [ap]=4[ap]=4 можно рассматривать как утверждение о том, что значение [ap] равно 4, или как установку присваивания [ap] на 4, в соответствии с контекст.

На рис. 4 показаны некоторые примеры инструкций «подтвердить равенство» и значения флагов для каждой инструкции:

Рисунок 4. Примеры инструкций Assert Equal

Интерпретировать инструкцию [fp + 1] = 5:

• инструкция утверждения => код операции = 4

• next_ap = ap => ap_update = 00 = 0

• next_pc = pc + размер_инструкции => pc_update = 000 = 0

• Для op0 и op1 нет add или mul => res_logic(res) = 00 = 0

• Существует непосредственное значение => op1_src(op1) = 001 = 1

• Адрес непосредственного значения указывает, что адреса являются смежными => off_op1 = 1

• Левая часть уравнения [fp + 1] => dst_reg(dst) = 1

• Левая часть уравнения [fp + 1] => off_dst = 1

• op0_reg/ off_op0 => начальное значение (1/-1) //Поскольку эти флаги не используются в этой инструкции, заполняется значение по умолчанию.

Комментарий условного и безусловного перехода

Инструкция jmp позволяет изменить значение программного счетчика pc.

Cairo поддерживает относительный переход (его операнд представляет собой смещение от текущего pcpc) и абсолютный переход, представленный ключевыми словами rel и abs соответственно.

Инструкция jmp может быть условной. Например, если значение блока памяти не равно 0, будет запущена инструкция jmp.

Синтаксис инструкции следующий:

```javascript

Безусловные переходы.

jmp абс <адрес>

jmp отн <смещение>

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

jmp rel <смещение> if !

На рис. 5 показаны некоторые примеры инструкций jmp и соответствующие значения флагов для каждой инструкции:

Рисунок 5 Примеры инструкций перехода

Интерпретация инструкция jmp rel [ap +1] + [fp - 7]:

• инструкция jmp => код операции = 0

• next_ap = ap => ap_update = b00 = 0

• next_pc = pc + res=> pc_update = b010 = 2

• res = op0 + op1 => res_logic(res) = b01 = 1

• op1: [fp - 7] => op1_src(op1) = b010 = 2

• op1: [fp - 7] => off_op1 = -7

• op0: [ap + 1] => op0_src(op0) = 0

• op0: [ap + 1] => off_op0 = 1

• dst_reg/ off_dst => начальное значение (1/-1) ///Поскольку эти флаги не используются в этой инструкции, заполняется значение по умолчанию.

звонить и отзывать

Инструкции call и ret позволяют реализовать стек функций. Инструкция call обновляет регистры счетчика программы (pc) и указателя кадра (fp ).

Обновление счетчика программ аналогично инструкции jmp . Предыдущее значение fp записывается в [ap], чтобы позволить инструкции ret сбросить значение fp до значения перед вызовом; аналогичным образом возвращенный pcpc (адрес инструкции после инструкции call) записывается в [ap+1], чтобы позволить инструкции ret вернуться назад и продолжить выполнение кода после инструкции call. .

Поскольку были записаны две единицы памяти, ap увеличивается на 2, а fp устанавливается на новый ap.

Синтаксис инструкций следующий:

```javascript

позвонить в абс <адрес>

вызов rel <смещение>

рет

На рис. 6 показаны некоторые примеры инструкций call и ret и значения флагов, соответствующие каждой инструкции:

Рисунок 6 Примеры инструкций вызова и инструкций возврата

Интерпретировать вызов инструкции abs [fp + 4]:

• инструкция вызова => код операции = 0

• next_ap = ap => ap_update = b00 = 0

• next_pc = res => pc_update = b001 = 1

• res = op1 => res_logic(res) = b00 = 0

• op1: [fp + 4] => op1_src(op1) = b010 = 2

• op1: [fp + 4] => off_op1 = 4

• op0_reg/ off_op0 => начальное значение (0/1) ///Поскольку эти флаги не используются в этой инструкции, заполняется значение по умолчанию.

• dst_reg/ off_dst => начальное значение (0/0) ///Поскольку эти флаги не используются в этой инструкции, заполняется значение по умолчанию.

Продвижение ap

Инструкция ap +=  увеличивает значение ap на заданный операнд.

Комментарий

На рис. 7 показаны некоторые примеры инструкций ap и соответствующие значения флагов для каждой инструкции:

Рис. 7 Примеры продвижения инструкций ap

Интерпретировать инструкцию ap += 123:

• инструкция продвижения ap => код операции = 0

• next_ap=ap+res=>ap_update=b01=1

• next_pc = pc + размер_инструкции => pc_update = b000 = 0

• res = op1 => res_logic(res) = b00 = 0

• op1 = 123 => op1_src(op1) = b001 = 1

• op1 = 123 => off_op1 = 1

• op0_reg/ off_op0 => начальное значение (1/-1) ///Поскольку эти флаги не используются в этой инструкции, заполняется значение по умолчанию.

• dst_reg/ off_dst => начальное значение (1/-1) ///Поскольку эти флаги не используются в этой инструкции, заполняется значение по умолчанию.