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 : _dst[ bit0…15] : décalage de l'adresse de destination, valeur représentative off -2^{15} + ∑_{i = 0}^{15} b_i . 2^je ∈ [-2^{15}, 2^{15}); [ bit16…31] : décalage d'adresse op0, valeur représentative off_op0 -2^{15} + ∑_{i = 0}^{15} b_i . 2^je ∈ [-2^{15}, 2^{15}); [ bit32…47] : décalage de l'adresse op1, valeur représentative off_op1 -2^{15} + ∑_{i = 0}^{15} b_i . 2^je ∈ [-2^{15}, 2^{15}); [ bit48] : Registre de base du décalage d'adresse de destination, ap ou fp ; dst reg [bit49] : registre de base du décalage d'adresse op0, ap ou fp ; op0 reg [ bit50…52] : adresse de op1, op1_src 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) bit53…54] : logique de calcul res_logic Caisse : 00 res = op1 Cas : 01 res = op0 + op1 Caisse : 10 res = op0 ∗ op1 [ bit55…57] : la logique de mise à jour du pc pc_update 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) [ bit58…59] : la logique de mise à jour de ap ap_update Caisse : 00 next_ap = ap (ou ap+2 si opcode = 1) Cas : 01 next_ap = ap + res Caisse : 10 next_ap = ap + 1 [ bit60…62] : types d'opcodes opcode 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ù: [ bit0…15], [ bit16…31], [ bit32…47] sont dans la plage off_dst off_op0 off_op1 -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 devrait être [0,2^16) ˜off∗ Ainsi, pour le codage d'une instruction, on a : 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. Remarque : =∑_{j=i}^{14} 2j−i⋅fj ˜f_i 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 : （2） inst = ˜off_dst + 2^16⋅˜off_op0 + 2^32⋅˜off_op1 + 2^48⋅˜f0 ∈ [0,263) Comme la caractéristique du champ fini , une instruction ne peut correspondre qu'à un élément de champ valide. P > 2^63 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 colonne virtuelle ∈ [0,2^16), donc ∈ [2^−15, 2^15) Les décalages sont dans la plage : ˜off∗ off∗ Exemples d'instructions Affirmer égal L'instruction assert equal peut être exprimée dans la syntaxe suivante : = 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 [ ] ou [ ], et le côté droit a quelques formes possibles (reg_0 et reg_1 peuvent être ou , ∘ peut être une addition ou une multiplication, et imm peut être tout élément de champ fixe) : fp+off_dst ap+off_dst fp ap 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] division et la soustraction peuvent être exprimées respectivement sous forme de multiplication et d'addition avec différents ordres d'opérandes. Remarque 2 : La Une instruction d' 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. affirmation 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 : l'instruction [fp + 1] = 5 : Interprétez 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 permet de changer la valeur du compteur de programme . jmp 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 et . rel abs L'instruction peut être conditionnelle. Par exemple, lorsque la valeur d'une unité de mémoire n'est pas 0, l'instruction sera déclenchée. jmp jmp La syntaxe de l'instruction est la suivante : #Unconditional jumps. jmp abs jmp rel #Conditional jumps. jmp rel if ! La figure 5 montre quelques exemples d'instructions et les valeurs d'indicateur correspondantes de chaque instruction : jmp l'instruction jmp rel [ap +1] + [fp - 7] : Interprétez 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. et appel ret Les instructions et permettent l'implémentation de la pile de fonctions. L'instruction met à jour les registres du compteur de programme ( ) et du pointeur de trame ( ). call ret d'appel pc fp La mise à jour du compteur de programme est similaire à l'instruction . La valeur précédente de est écrite dans [ ], pour permettre à l'instruction de réinitialiser la valeur de à 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 [ ], pour permettre à l'instruction de revenir en arrière et de continuer l'exécution du code après l'instruction d'appel. jmp fp ap ret fp ap+1 ret Au fur et à mesure que deux unités de mémoire ont été écrites, a avancé de 2 et est défini sur le nouveau . ap fp ap La syntaxe des instructions est la suivante : call abs call rel ret La figure 6 montre quelques exemples d'instructions et et de valeurs de drapeau correspondant à chaque instruction : call ret l'appel d'instruction abs [fp + 4] : Interprétez 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 incrémente la valeur de de l'opérande donné. ap += ap Commentaire La figure 7 montre quelques exemples d'instructions avancées et les valeurs de drapeau correspondantes de chaque instruction : ap l'instruction ap += 123 : Interprétez 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.