587 lectures

Explorez le Caire : une architecture CPU pratique et efficace, compatible avec STARK et compatible avec Turing

par Sin7Y2022/05/05

Trop long; Pour lire

Cairo est une architecture CPU compatible STARK et pratiquement efficace. Dans cet article, nous présentons l'architecture CPU de Cairo en termes de structure d'instruction et de transition d'état, et fournissons quelques exemples d'instruction. Structure des instructions Le mot pris en charge nativement par Cairo CPU est un élément de champ, où le champ est un champ ﬁni ﬁxe de caractéristique P>2^63. Chaque instruction occupera 1 ou 2 mots. Si une valeur immédiate ([ap] = "12345678") suit l'instruction, l'instruction occupera 2 mots et la valeur sera stockée dans le deuxième mot.

Company Mentioned

featured image - Explorez le Caire : une architecture CPU pratique et efficace, compatible avec STARK et compatible avec Turing

Cairo est une architecture CPU compatible STARK et pratiquement efficace.

Dans cet article, nous présentons l'architecture CPU de Cairo en termes de structure d'instruction et de transition d'état, et fournissons quelques exemples d'instruction.

Structure des instructions

Le mot supporté nativement par Cairo CPU est un élément de champ, où le champ est un champ ﬁni ﬁxe de caractéristique P>2^63 .

Chaque instruction occupera 1 ou 2 mots. Si une valeur immédiate ([ap] = "12345678") suit l'instruction, l'instruction occupera 2 mots et la valeur sera stockée dans le deuxième mot. Le premier mot de chaque instruction est composé des éléments suivants :

off _dst[ bit0…15] : décalage de l'adresse de destination, valeur représentative
-2^{15} + ∑_{i = 0}^{15} b_i . 2^je ∈ [-2^{15}, 2^{15});
off_op0 [ bit16…31] : décalage d'adresse op0, valeur représentative

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

off_op1 [ bit32…47] : décalage de l'adresse op1, valeur représentative
-2^{15} + ∑_{i = 0}^{15} b_i . 2^je ∈ [-2^{15}, 2^{15});
dst reg [ bit48] : Registre de base du décalage d'adresse de destination, ap ou fp ;
op0 reg [bit49] : registre de base du décalage d'adresse op0, ap ou fp ;
op1_src [ bit50…52] : adresse de op1,
- Cas: 000
  op1=m(op0+off_op1)
- Cas : 001
  op1=m(pc+off_op1)
- Cas : 010
  op1=m(fp+off_op1)
- Caisse : 100
  op1=m(ap+off_op1)
res_logic bit53…54] : logique de calcul
- Caisse : 00
  res = op1
- Cas : 01
  res = op0 + op1
- Caisse : 10
  res = op0 ∗ op1
pc_update [ bit55…57] : la logique de mise à jour du pc
- Cas : 000 // commun
  prochain_pc = pc + instruction_size
- Cas : 001 // saut absolu
  prochain_pc = res
- Cas : 010 // saut relatif
  prochain_pc = pc + res
- Cas : 100 // saut relatif conditionnel
  next_pc = pc + op1 (ou instruction_size si dst = 0)
ap_update [ bit58…59] : la logique de mise à jour de ap
- Caisse : 00
  next_ap = ap (ou ap+2 si opcode = 1)
- Cas : 01
  next_ap = ap + res
- Caisse : 10
  next_ap = ap + 1
opcode [ bit60…62] : types d'opcodes
- Cas : 000 // jmp
- Cas : 001 // appel
- Cas : 010 // ret
- Cas : 100 // affirmation

Commentaire de transition d'état

La fonction de transition d'état représente une unité de transition d'état générale (car elle contient la logique de traitement de tous les types d'instructions), et un calcul est généralement décomposé en plusieurs instructions exécutées en continu.

Par conséquent, nous devons :

assurer le contenu de l'instruction et la validité des états avant et après l'exécution de l'instruction (par exemple, passer un certain contrôle de plage et un contrôle de cohérence d'état) et
s'assurer que l'instruction exécutée est valide.

Commentaire de la logique de transition

Si l'état avant et après l'exécution de l'instruction est cohérent, la mise à jour de l'état doit être exécutée selon la logique suivante :

 #Context: m(.). #Input state: (pc, ap, and fp). #Output state: (next_pc, next_ap, and next_fp). #Compute op0. If op0_reg == 0: // Judge the basic register of op0 according to the flag value, 0 is ap,1 is fp, and obtain the value of op0. op0 = m(ap + off_{op0}) else: op0 = m(fp + off_{op0}) #Compute op1 and instruction_size. switch op1_src: // Obtain the value of op1 case 0: instruction_size = 1 // op1 = m[[ap/fp + off_op0] +off_op1], with two-level imbedding at most. op1 = m(op0 + off_{op1}) case 1: instruction_size = 2 // There exist(s) immediate number(s). The instruction size is 2 words. op1 = m(pc + off_{op1})// #If off_{op1} = 1, we have op1 = immediate_value. // For example, [ap] = "12345678", op1 = "12345678" case 2: instruction_size = 1 // op1 = [fp + off_op1] op1 = m(fp + off_{op1}) case 4: instruction_size = 1 // op1 = [ap +off_op1] op1 = m(ap + off_{op1}) default: Undefined Behavior #Compute res. if pc_update == 4: // jnz if res_logic == 0 && opcode == 0 && ap_update != 1: // Assign && jump && advanced ap res = Unused // Under conditional jump, the values of res_logic, opcode and ap_update flags can only be as shown above.The res variable will not be used on this occasion. else: Undefined Behavior else if pc_update = 0, 1 or 2: switch res_logic: // The computational logic of res is: case 0: res = op1 case 1: res = op0 + op1 case 2: res = op0 * op1 default: Undefined Behavior else: Undefined Behavior # Compute dst. if dst_reg == 0: dst = m(ap + offdst) else: dst = m(fp + offdst) # Compute the new value of pc. switch pc_update: case 0: # The common case: [ap] = 1 next_pc = pc + instruction_size case 1: # Absolute jump: jmp abs 123 next_pc = res case 2: # Relative jump: jmp rel [ap - 1] next_pc = pc + res case 4: # Conditional relative jump (jnz): jmp rel [ap - 1] if [fp - 7] = 0 next_pc = if dst == 0: pc + instruction_size // If dst = 0, then pc conducts ordinary updates; otherwise, it is similar to Case 2. else: pc + op1 // Under this circumstance, res is Unused, so pc directly conducts + op1, instead of + res. default: Undefined Behavior # Compute new value of ap and fp based on the opcode. if opcode == 1: # "Call" instruction. assert op0 == pc + instruction_size assert dst == fp # Update fp. next_fp = ap + 2 // [ap] saves the current fp value, [ap + 1] saves the pc after the call instruction; when the ret instruction is executed, it is convenient to reset fp to [ap], and then continue to execute subsequent instructions. # Update ap. switch ap_update: case 0: next_ap = ap + 2 // [ap] saves the value of fp, and [ap+1] saves the instruction address after the call instruction; thus, ap increases by 2. default: Undefined Behavior else if opcode is one of 0, 2, 4: # Update ap. switch ap_update: case 0: next_ap = ap // [fp + 1] = 5 case 1: next_ap = ap + res // advanced ap [ap] += 123 case 2: next_ap = ap + 1 // normal [fp + 1] = [ap]; ap++ default: Undefined Behavior switch opcode: // Within the same function, the fp value remains unchanged. case 0: next_fp = fp case 2: # "ret" instruction. next_fp = dst // The ret instruction goes with the call instruction, and assert dst == fp. case 4: # "assert equal" instruction. assert res = dst next_fp = fp else: Undefined Behavior

Vérification des instructions

Comme le montre la figure 1, une instruction se compose des éléments suivants :

 structure instruction := (off_dst : bitvec 16) (off_op0 : bitvec 16) (off_op1 : bitvec 16) (flags : bitvec 15)

Où:

off_dst [ bit0…15], off_op0 [ bit16…31], off_op1 [ bit32…47] sont dans la plage

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

Mais dans AIR, nous les convertissons sous la forme suivante :

˜off∗ = off∗ + 2^15

(Où * représente l'un des dst, op0 et op1)

Ainsi, la plage de valeurs de ˜off∗ devrait être [0,2^16)

Ainsi, pour le codage d'une instruction, on a :

Remarque : Au lieu d'allouer 15 colonnes virtuelles d'une longueur de NN aux indicateurs 15 bits de l'instruction, nous utilisons à la place une colonne virtuelle.

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

Avec une longueur de 16N, qui répond aux exigences suivantes :

˜f_0 = ∑_{j=0}^{14} 2^{j-0}⋅f_j est une valeur de 15 bits
˜f_15 = 0
˜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

L'équation (1) peut donc s'écrire :

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

Comme la caractéristique du champ fini P > 2^63 , une instruction ne peut correspondre qu'à un élément de champ valide.

Par conséquent, pour l'instruction elle-même, les contraintes suivantes doivent être respectées :

Instruction： inst= ˜off_dst + 2^16⋅˜off_op0 + 2^32⋅˜off_op1 + 2^48⋅ ˜ f0

Bit： (˜f_i−2˜f_i +1)(˜f_i−2˜f_i+1 −1)=0 pour tout i ∈ [0,15)

La dernière valeur est zéro : ˜f_15=0

Les décalages sont dans la plage : colonne virtuelle ˜off∗ ∈ [0,2^16), donc off∗ ∈ [2^−15, 2^15)

Exemples d'instructions

Affirmer égal

L'instruction assert equal peut être exprimée dans la syntaxe suivante :

<left_handle_op> = <right_handle_op>

Il garantit que les deux côtés de la formule sont égaux; sinon l'exécution du programme sera rejetée.

Le côté gauche de l'équation vient souvent de [ fp+off_dst ] ou [ ap+off_dst ], et le côté droit a quelques formes possibles (reg_0 et reg_1 peuvent être fp ou ap , ∘ peut être une addition ou une multiplication, et imm peut être tout élément de champ fixe) :

je suis
[reg1+offop1][reg1+offop1]
[reg0+offop0]∘[reg1+offop1][reg0+offop0]∘[reg1+offop1]
[reg0+offop0]∘imm[reg0+offop0]∘imm
[[reg0+offop0+offop1][[reg0+offop0+offop1]

Remarque 2 : La division et la soustraction peuvent être exprimées respectivement sous forme de multiplication et d'addition avec différents ordres d'opérandes.

Une instruction d' affirmation peut être considérée comme une instruction d'affectation, dans laquelle la valeur d'un côté est connue et l'autre côté est inconnue.

Par exemple, [ap]=4[ap]=4 peut être considéré comme une assertion que la valeur de [ap] est 4, ou comme une affectation fixant [ap] à 4, selon le contexte.

La figure 4 montre quelques exemples d'instructions « assert equal » et les valeurs de drapeau pour chaque instruction :

Interprétez l'instruction [fp + 1] = 5 :

instruction assert => opcode = 4
next_ap = ap => ap_update = 00 = 0
pc_suivant = pc + taille_instruction => pc_update = 000 = 0
Pour op0 et op1, il n'y a pas d'addition ou de mul => res_logic(res) = 00 = 0
Il existe une valeur immédiate => op1_src(op1) = 001 = 1
L'adresse de valeur immédiate indique que les adresses sont adjacentes => off_op1 = 1
Le côté gauche de l'équation [fp + 1] => dst_reg(dst) = 1
Le côté gauche de l'équation [fp + 1] => off_dst = 1
op0_reg/ off_op0 => valeur initiale(1/-1) //Parce que ces drapeaux ne sont pas utilisés dans cette instruction, la valeur par défaut est remplie.

Commentaire de saut conditionnel et inconditionnel

L'instruction jmp permet de changer la valeur du compteur de programme pc .

Cairo prend en charge le saut relatif (son opérande représente le décalage par rapport au pcpc actuel) et le saut absolu - représenté respectivement par les mots-clés rel et abs .

L'instruction jmp peut être conditionnelle. Par exemple, lorsque la valeur d'une unité de mémoire n'est pas 0, l'instruction jmp sera déclenchée.

La syntaxe de l'instruction est la suivante :

 #Unconditional jumps. jmp abs <address> jmp rel <offset> #Conditional jumps. jmp rel <offset> if <op> !

La figure 5 montre quelques exemples d'instructions jmp et les valeurs d'indicateur correspondantes de chaque instruction :

Interprétez l'instruction jmp rel [ap +1] + [fp - 7] :

instruction jmp => code opération = 0
next_ap = ap => ap_update = b00 = 0
pc_suivant = pc + res=> mise à jour_pc = b010 = 2
res = op0 + op1 => res_logique(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 => valeur initiale(1/-1) ///Parce que ces drapeaux ne sont pas utilisés dans cette instruction, la valeur par défaut est remplie.

appel et ret

Les instructions call et ret permettent l'implémentation de la pile de fonctions. L'instruction d'appel met à jour les registres du compteur de programme ( pc ) et du pointeur de trame ( fp ).

La mise à jour du compteur de programme est similaire à l'instruction jmp . La valeur précédente de fp est écrite dans [ ap ], pour permettre à l'instruction ret de réinitialiser la valeur de fp à la valeur avant l'appel ; de même, le pcpc retourné (l'adresse de l'instruction après l'instruction d'appel) est écrit dans [ ap+1 ], pour permettre à l'instruction ret de revenir en arrière et de continuer l'exécution du code après l'instruction d'appel.

Au fur et à mesure que deux unités de mémoire ont été écrites, ap a avancé de 2 et fp est défini sur le nouveau ap .

La syntaxe des instructions est la suivante :

 call abs <address> call rel <offset> ret

La figure 6 montre quelques exemples d'instructions call et ret et de valeurs de drapeau correspondant à chaque instruction :

Interprétez l'appel d'instruction abs [fp + 4] :

instruction d'appel => opcode = 0
next_ap = ap => ap_update = b00 = 0
prochain_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 => valeur initiale(0/1) ///Parce que ces drapeaux ne sont pas utilisés dans cette instruction, la valeur par défaut est remplie.
dst_reg/ off_dst => valeur initiale(0/0) ///Parce que ces drapeaux ne sont pas utilisés dans cette instruction, la valeur par défaut est remplie.

Avancer ap

L'instruction ap += <op> incrémente la valeur de ap de l'opérande donné.

Commentaire

La figure 7 montre quelques exemples d'instructions ap avancées et les valeurs de drapeau correspondantes de chaque instruction :

Interprétez l'instruction ap += 123 :

faire avancer l'instruction ap => opcode = 0
next_ap = ap + res => ap_update = b01 = 1
next_pc = pc + instruction_size => 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 => valeur initiale(1/-1) ///Parce que ces drapeaux ne sont pas utilisés dans cette instruction, la valeur par défaut est remplie.
dst_reg/ off_dst => valeur initiale(1/-1) ///Parce que ces drapeaux ne sont pas utilisés dans cette instruction, la valeur par défaut est remplie.