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 :   <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 [   ] 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 <address> jmp rel <offset> #Conditional jumps. jmp rel <offset> if <op> !  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 <address> call rel <offset> 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 += <op> 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. 

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Cet audio est produit dans la langue originale de l'histoire !

Trop long; Pour lire

Make resilience your competitive advantage

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

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

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Comment améliorer votre flux de travail par 10 : 17 applications essentielles

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Boostez votre productivité avec ces 18 outils de développement 🚀🔥

La fuite de l'invite du système Claude Sonnet 3.5 : une analyse médico-légale

Comment améliorer votre flux de travail par 10 : 17 applications essentielles

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Boostez votre productivité avec ces 18 outils de développement 🚀🔥

La fuite de l'invite du système Claude Sonnet 3.5 : une analyse médico-légale

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps