MIPS: arquitectura, memòria i assemblador ETC II

I 0 flashcards i 6 preguntes més al document.

Text del document

APUNTS ESTRUCTURA I TECNOLOGIA DE COMPUTADORS II Grau en Enginyeria Informàtica Universitat de Girona AprenAI 2026-2027 Apunts d'Estructura i Tecnologia de Computadors II: banc de registres MIPS, operacions de memòria, bucles, algorismes i conveni de crida a subrutines.

APREN.AI Índex 1 Arquitectura MIPS — Organització de la memòria i registres El banc de registres de propòsit general Organització de la memòria i endianness Restriccions d'alineament de memòria Directives de definició de dades Estructures de dades complexes: vectors i matrius 2 Estructura d'un programa MIPS i macros Estructura d'un programa font en MIPS Etiquetes de codi i comentaris Macros en assemblador MIPS Efectes secundaris dels registres temporals en macros Exemple d'integració global: tractament d'imatge 3 Repertori d'instruccions i pseudoinstruccions MIPS Instruccions natives i la limitació dels valors immediats Repertori d'instruccions natives de MIPS32 Pseudoinstruccions i la seva traducció a codi màquina Descomposició de càrregues de 32 bits (lui i ori) 4 Traducció d'estructures de control d'alt nivell Estructures condicionals: if-then-else Traducció inversa: d'assemblador a alt nivell Bucles condicionals: while i do-while Bucles for i recorregut de matrius Estructura switch-case 5 Algorismes fonamentals en assemblador Processament de cadenes i recorregut de dades en memòria Ordenació de vectors: algorisme de la bombolla (BubbleSort) Cerca dicotòmica iterativa 6 Subrutines, gestió de la pila i conveni MIPS Estructura i gestió de la pila (stack) Mecanisme de crida i retorn: jal, jr i crides niades Pas de paràmetres i valors de retorn El conveni MIPS32: caller-saved, callee-saved i les 3 fases 7 Formulari Registres de propòsit general i convenis MIPS: arquitectura, memòria i assemblador ETC II 1 Directives, alineament i càlcul d'adreces Procediments bàsics en assemblador Conveni MIPS32: seqüència de les 3 fases Errors típics de programació Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. MIPS: arquitectura, memòria i assemblador ETC II 2 1 Arquitectura MIPS — Organització de la memòria i registres EN ACABAR SABRÀS Identificar la funció i conveni dels 32 registres de la CPU MIPS Calcular la disposició de bytes en memòria segons el format Big Endian i Little Endian Aplicar les restriccions d'alineament i calcular l'espai de memòria per a vectors i matrius amb directives assemblador PENSA-HI ABANS DE LLEGIR 1 Si deses el nombre 0x1234 a la memòria, quin dels dos bytes (0x12 o 0x34) se situa a la primera posició d'adreça?

L'arquitectura MIPS és un model de processador RISC basat en una estructura regular de registres i un espai de memòria lineal adreçable a escala de byte. Abans d'escriure codi executable, cal conèixer amb precisió quins registres estan disponibles, com s'ordenen els bytes a l'espai d'adreces i com s'emmagatzemen les estructures de dades bàsiques i compostes. ESQUEMA Arquitectura MIPS i organització de dades El banc de registres de propòsit general La CPU MIPS disposa de 32 registres de propòsit general de 32 bits cadascun, anomenats internament des de fins a .

Per conveni, s'utilitzen àlies que en descriuen la funció recomanada: Registres ($0-$31) 32 registres de propòsit general Temporals i salvats $t0-$t9 (caller) i $s0-$s7 (callee) Punters i control $sp, $fp, $ra i $zero Memòria i Endianness Adreçament per bytes Big Endian Byte més significatiu a adreça baixa Little Endian Byte menys significatiu a adreça baixa Dades i estructures Alineament i directives Tipus elementals .byte, .half, .word, .double Vectors i matrius Seqüències per files o columnes $0 $31 MIPS: arquitectura, memòria i assemblador ETC II 3 Registre físic Nom simbòlic Funció convencional Constant 0 no modificable (sempre retorna 0 en lectura).

Temporal reservat per a l'assemblador per a la generació de codi. Retorn de valors en funcions i selecció de serveis del sistema ( ). Pas dels quatre primers paràmetres a subrutines. Registres temporals d'ús lliure; tipus caller-saved (no salvaguardats pel callee). Registres salvats; tipus callee-saved (la subrutina els ha de preservar abans de modificar-los). Registres temporals addicionals (caller-saved). Reservats pel nucli (kernel) del sistema operatiu i tractament d'interrupcions. Punter global a l'àrea de dades estàtiques (global pointer). Punter a la part superior de la pila (stack pointer). Punter al marc d'execució de la subrutina (frame pointer).

Adreça de retorn d'una crida de subrutina (return address). COMPROVA-HO 2 Quina diferència fonamental hi ha entre els registres $t0-$t9 i els registres $s0-$s7 quan s'invoca una funció? Organització de la memòria i endianness La memòria s'adreça per bytes individuals, però les dades poden ocupar blocs de 1, 2, 4 o 8 bytes consecutius segons el tipus: Byte: bloc elemental de 8 bits ( ). Halfword (mitja paraula): bloc de 16 bits ( ). Word (paraula): mida estàndard dels registres, amb 32 bits ( ). Double (doble paraula): bloc de 64 bits ( ).

Quan una dada ocupa més d'un byte, l'ordenació interna dels bytes a les diferents posicions d'adreça es regeix per l'endianness: $0 $zero $1 $at $2 $3 $v0 $v1 $v0 $4 $7 $a0 $a3 $8 $15 $t0 $t7 $16 $23 $s0 $s7 $24 $25 $t8 $t9 $26 $27 $k0 $k1 $28 $gp $29 $sp $30 $fp $31 $ra 1 byte 2 bytes 4 bytes 8 bytes MIPS: arquitectura, memòria i assemblador ETC II 4 DEFINICIÓ En l'organització Big Endian, el byte de més pes (MSB) s'emmagatzema a l'adreça numèrica més baixa. En Little Endian, el byte de menys pes (LSB) ocupa l'adreça més baixa de memòria.

Considerem el valor hexadecimal de 32 bits desat a partir d'una adreça base : Modalitat Adreça Adreça Adreça Adreça Big Endian (més pes) (menys pes) Little Endian (menys pes) (més pes) EXEMPLE Si la paraula és en una màquina Little Endian a l'adreça base , llegir la dada sencera amb una instrucció de paraula completa produeix . Llegir només una mitja paraula ( ) des d' retorna , i carregar un únic byte des d' retorna . COMPROVA-HO 3 Si a l'adreça 0x1000 hi ha el byte 0xAA i a la 0x1001 el byte 0xBB, quin valor té la halfword a 0x1000 en un sistema Big Endian?

Restriccions d'alineament de memòria MIPS imposa una regla estricta d'alineament de dades: l'adreça de memòria a la qual s'accedeix ha de ser divisible per la mida en bytes del tipus manipulat. Un byte pot situar-se a qualsevol adreça de memòria sense restricció. Una mitja paraula (halfword) només es pot carregar o emmagatzemar en adreces parelles ( ). Una paraula (word o float) requereix adreces que siguin estrictament múltiples de 4 (acabades en en binari). Un valor de tipus double exigeix una adreça que sigui múltiple de 8.

ERROR FREQÜENT Intentar accedir a una paraula de 32 bits a través d'una adreça imparella o no divisible per 4 genera una excepció de processador per error d'alineament (bus error o address error exception). Recordeu sempre que la posició inicial d'un vector de words ha de complir el mòdul corresponent.

Directives de definició de dades Per reservar memòria i inicialitzar variables al segment de dades, s'utilitzen directives específiques de l'assemblador: 0x23456789 @ @ @ + 1 @ + 2 @ + 3 23 16 45 16 67 16 89 16 89 16 67 16 45 16 23 16 0x23456789 @ 0x23456789 2 bytes @ 0x6789 @ 0x89 m ltiples de 2 u ˊ 00 2 MIPS: arquitectura, memòria i assemblador ETC II 5 Directiva Mida assignada Descripció i ús típic .byte 1 byte Reserva espai per a nombres enters petits o caràcters aïllats. .half 2 bytes Enters de 16 bits en complement a dos o naturals. .word 4 bytes Enters de 32 bits o adreces de punters. .float 4 bytes Coma flotant de precisió simple segons IEEE 754.

.double 8 bytes Coma flotant de doble precisió segons IEEE 754. .ascii 1 byte per lletra Cadena de caràcters en format ASCII sense caràcter terminador afegit. .asciiz 1 byte per lletra + 1 Cadena de caràcters ASCII que afegeix automàticament el byte nul final (0). .space n n bytes Reserva un bloc buit de bytes consecutius sense inicialitzar. Els valors booleans no tenen directiva pròpia: se solen gestionar mitjançant valors enters (0 per a fals, diferent de zero per a cert) derivats d'instruccions de comparació. PER RECORDAR-HO Diferència clau: .ascii "Hola" ocupa exactament 4 bytes de memòria, mentre que .asciiz "Hola" n'ocupa 5 a causa del byte nul final que delimita el missatge.

Estructures de dades complexes: vectors i matrius A nivell d'assemblador, no existeix la noció abstracta d'array o matriu; totes les estructures es tradueixen en seqüències contigües de bytes a la memòria principal. El càlcul del desplaçament respecte a l'adreça base és responsabilitat del programador.

Vectors (arrays unidimensionals) Un vector s'assigna declarant valors consecutius sota una mateixa etiqueta o reservant un volum total de bytes amb .space : v: .word 10, 20, 30, 40 # Vector de 4 enters (16 bytes en total) buit: .space 40 # Espai per a 10 enters (10 * 4 bytes) Per accedir a l'element en la posició (indexat des de 0), l'adreça efectiva es calcula sumant a l'adreça base un salt equivalent a (1 per a byte, 2 per a halfword i 4 per a word).

Matrius bidimensionals Una matriu de dimensions (on és el nombre de files i el nombre de columnes) es pot aplanar i emmagatzemar seguint dos criteris principals: n i i × mida_tipus F × C F C MIPS: arquitectura, memòria i assemblador ETC II 6 Per a una matriu d'enters de com ara : Organització per files: M: .word 1, 2, 3, 4, 5, 6 Organització per columnes: M: .word 1, 4, 2, 5, 3, 6 Alternativament, es poden declarar les dimensions explícitament abans del bloc de dades per facilitar la lectura del programa: files: .word 2 columnes: .word 3 fila0: .word 1, 2, 3 fila1: .word 4, 5, 6 COMPROVA-HO 4 Quants bytes s'han de reservar amb .space per emmagatzemar una matriu de 10 files per 20 columnes de nombres enters de 32 bits?

IDEES CLAU MIPS disposa de 32 registres de propòsit general de 32 bits amb convencions específiques com caller-saved ($t0-$t9) i callee-saved ($s0-$s7). L'ordre dels bytes a la memòria depèn de l'endianness: Big Endian emmagatzema el byte més significatiu a l'adreça més baixa i Little Endian hi situa el menys significatiu. L'alineament imposa que els accessos a memòria siguin múltiples de la mida del tipus: 2 bytes per a halfword, 4 bytes per a word/float i 8 bytes per a double. Les directives de dades com .byte, .half, .word, .asciiz o .space defineixen la representació exacta en bytes de les variables.

Les estructures complexes com vectors i matrius no tenen suport sintàctic especial i es mapegen com a blocs contigus de memòria organitzats per files o per columnes. COMPROVA EL QUE HAS APRÈS 5. Quin error es produeix si s'intenta carregar una paraula (word) des de l'adreça de memòria 0x1002? 6. Quina és la diferència de mida entre una cadena declarada amb .ascii "Test" i una amb .asciiz "Test"? Emmagatzematge per files (Row-major order): es desen tots els elements de la primera fila consecutivament, després els de la segona, i així successivament. És la disposició estàndard a la majoria de llenguatges com C.

1 Emmagatzematge per columnes (Column-major order): es desen primer tots els elements de la columna 0, seguits dels elements de la columna 1, fins a la darrera. 2 2 × 3 M = ( 1 4 2 5 3 6 ) MIPS: arquitectura, memòria i assemblador ETC II 7 Test Encercla la resposta correcta. Les solucions són al final. 7. Quin registre conté sempre de manera immutable el valor numèric 0? 8. En un sistema Little Endian, quin byte es troba a l'adreça més baixa d'una paraula? 9. A quina classe d'adreces ha d'estar alineat un nombre de tipus double? 10. Quants bytes reserva la directiva .space 32 a la memòria?

2 Estructura d'un programa MIPS i macros EN ACABAR SABRÀS Diferenciar clarament les directives .data, .text i .end en l'estructura d'un fitxer MIPS. Implementar i invocar macros parametritzades identificant el seu procés de substitució textual. Preveure i evitar la pèrdua involuntària d'informació en registres temporals en utilitzar macros. Rastrejar el flux d'execució entre un programa principal i subrutines auxiliars. PENSA-HI ABANS DE LLEGIR 11 Per què l'ús reiterat d'una macro pot augmentar la mida final del fitxer binari a diferència d'una subrutina? Estructura d'un programa font en MIPS Un fitxer de codi assemblador en arquitectura MIPS s'organitza en blocs lògics anomenats segments.

Per delimitar cadascun d'aquests blocs s'utilitzen directives de l'assemblador, que comencen amb un punt. El segment de dades (.data) conté les variables estàtiques, cadenes de text i vectors que el programa necessita emmagatzemar en memòria.

Per reservar espai i inicialitzar continguts s'usen directives com ara .ascii (per a seqüències de caràcters), .byte (per a valors enters de mida 1 byte) i .word (per $ra a) $t0 b) $zero c) $sp d) El byte de menys pes a) El byte de més pes b) El byte intermedi c) Depèn del tipus d) Múltiples de 4 a) Qualsevol adreça b) Adreces parelles c) Múltiples de 8 d) 32 bytes a) 8 paraules b) Depèn del registre c) 128 bytes d) MIPS: arquitectura, memòria i assemblador ETC II 8 a valors enters de 4 bytes). La reserva de memòria no inicialitzada es realitza mitjançant la directiva .space (vegeu «Arquitectura MIPS — Organització de la memòria i registres»).

El segment de text (.text) conté les instruccions màquina executables del programa. Dins d'aquest segment s'ubica tant el flux d'execució principal com les rutines auxiliars. Tant el bloc de dades com els blocs de codi es tanquen formalment amb la directiva .end . Directiva Funció principal Exemple d'ús .data Inicia el segment de declaració de variables i dades en memòria. .data seguit de variables. .text Inicia el segment amb el conjunt d'instruccions executables. .text seguit de les rutines. .end Marca la finalització d'un mòdul, funció o segment concret. .end al final d'un bloc. .word Reserva paraules de 32 bits (4 bytes) amb valors assignats.

Width: .word 38 .byte Reserva un o diversos bytes consecutius amb valors inicials. .byte 84, 104, 87, 23 .ascii Emmagatzema una cadena de text literal sense caràcter nul final automàtic. .ascii "Els valors son:" ESQUEMA Segments i components d'un programa MIPS Etiquetes de codi i comentaris Les etiquetes de codi són identificadors que associen un nom textual a una adreça de memòria concreta, facilitant la lectura i els salts en el flux de control. S'escriuen seguides de dos punts ( : ).

Algunes etiquetes són estrictament funcionals per rebre salts, com loop: en un bucle que avalua una condició, mentre que d'altres s'utilitzen de manera informativa o per marcar el punt de sortida, com endloop: o exiti: . Els comentaris en MIPS s'inicien amb el caràcter # . L'assemblador ignora qualsevol text situat a la dreta d'aquest caràcter fins al final de la línia, la qual cosa permet documentar el funcionament del codi o relacionar-lo amb variables d'un llenguatge d'alt nivell com C.

.data Declaració de dades i espai de memòria Tipus de dades Directives .word, .byte, .ascii i .space .text (Rutines) Funcions auxiliars com voltejarH jr $ra Retorn a la subrutina invocadora .text (Main) Punt d'entrada i gestió de la pila jal Crida de subrutina amb enllaç a $ra MIPS: arquitectura, memòria i assemblador ETC II 9 COMPROVA-HO 12 Quina diferència funcional existeix entre l'etiqueta que encapçala un bucle i una etiqueta informativa com endloop:? Macros en assemblador MIPS Una macro en assemblador és una plantilla de codi parametritzada que es defineix mitjançant les directives .macro i .end_macro .

Quan l'assemblador processa el fitxer font i troba una invocació d'aquesta macro, duu a terme una substitució textual directa, substituint el nom i els seus paràmetres formals pel bloc d'instruccions definit. DEFINICIÓ Una macro no és una funció. No utilitza instruccions de salt ni genera retorn amb adreces d'enllaç; l'assemblador clona literalment el cos d'instruccions en cada lloc on s'invoca la macro abans d'iniciar la generació del codi màquina definitiu.

A continuació s'il·lustra la definició de la macro print_int , destinada a mostrar un enter per pantalla aprofitant el servei del sistema corresponent (vegeu «Repertori d'instruccions i pseudoinstruccions MIPS»): .macro print_int ($arg) li $v0, 1 add $a0, $0, $arg syscall .end_macro Dins del segment .text , aquesta macro pot invocar-se passant com a argument tant un registre com un valor immediat: print_int ($t7) # Crida passant el contingut del registre $t7 print_int (10) # Crida passant el valor constant 10 PROCÉS Flux de funcionament d'una macro 1 Definició Es descriu el bloc amb .macro i paràmetres 2 Crida S'invoca la macro amb registres o valors immediats 3 Substitució L'assemblador clona literalment el cos d'instruccions 4 Execució seqüencial S'executa el codi resultant alterant els registres utilitzats MIPS: arquitectura, memòria i assemblador ETC II 10 Efectes secundaris dels registres temporals en macros Com que una macro s'expandeix textualment dins del codi principal, qualsevol registre modificat en el seu interior té una incidència directa sobre el context d'execució circumdant.

Les macros no salven ni restauren l'estat dels registres a la pila (vegeu «Subrutines, gestió de la pila i conveni MIPS»). Considereu la següent macro swap per intercanviar el contingut de dos registres fent servir un tercer registre temporal: .macro swap ($r1, $r2, $temp) move $temp, $r1 move $r1, $r2 move $r2, $temp .end_macro Si s'invoca la instrucció textual swap ($s1, $s2, $t1) , els continguts de $s1 i $s2 queden intercanviats amb èxit. Malgrat tot, el registre $t1 rep el valor que originalment residia a $s1, destruint irreversiblement el valor previ que allotjava $t1 abans d'executar la macro. ERROR FREQÜENT Confondre una macro amb una rutina o funció.

Pensar que els arguments d'una macro o els seus registres temporals d'ús intern tenen un abast local tancat provoca la pèrdua involuntària de dades als registres temporals del programa invocador. COMPROVA-HO 13 Si un programa utilitza el registre $t1 per a un càlcul actiu i tot seguit executa swap ($s1, $s2, $t1), quin problema apareix? Exemple d'integració global: tractament d'imatge Per observar com interactuen el segment de dades, les rutines del segment de text i el flux del programa principal, s'analitza l'esquelet complet d'un algorisme dissenyat per rotar una imatge emmagatzemada a la memòria del sistema, implementat mitjançant la rutina voltejarH . 1.

Declaració del segment de dades En el segment .data es defineixen les dimensions de la imatge i la memòria necessària. Per facilitar la visualització per pantalla durant les proves de depuració, s'utilitza una mida de matriu de 38 28 píxels en lloc de la mida estàndard de 384x288 píxels: .data Width: .word 38 # Amplada de la imatge Height: .word 28 # Alçada de la imatge Image: .space 4256 # Espai en bytes: 38 * 28 * 4 bytes = 4256 .end 90 × MIPS: arquitectura, memòria i assemblador ETC II 11 2. Definició de la subrutina en codi El primer segment .text acull la rutina voltejarH . Aquesta rutina rep l'adreça base de la matriu en $a0, l'amplada en $a1 i l'alçada en $a2.

Segons el conveni establert, la rutina pot utilitzar els registres $t0-$t9 directament sense guardar-los: .text # Paràmetres: $a0 = Adreça base de la imatge, $a1 = Width, $a2 = Height voltejarH: srl $t0, $a1, 1 # $t0 <- Width / 2 (desplaçament lògic a la dreta) li $t1, 0 # Comptador de files i = 0 fori: bge $t1, $a2, exiti # Mentre i < Height; si i >= Height, salta a exiti # ... Operacions internes del bucle ... exiti: jr $ra # Retorn a la rutina invocadora .end 3. Programa principal i crida a la rutina En un segon segment .text s'estableix la rutina principal ( main ).

Atès que el procediment principal fa ús de la instrucció de salt amb enllaç ( jal ) per saltar a voltejarH , cal protegir l'adreça de retorn $ra fent espai a la pila: COMPROVA-HO 14 Quants bytes s'ocupen a memòria per allotjar una imatge de 38 columnes per 28 files si cada element consumeix una paraula? Reserva d'espai a la pila: es decrementa el punter de pila executant subu $sp, $sp, 4 i es preserva l'adreça de retorn amb sw $ra, 0($sp) . 1 Càrrega dels arguments: es preparen els paràmetres carregant l'adreça de la imatge ( la $a0, Image ) i les dimensions directament des de la memòria ( lw $a1, Width($0) i lw $a2, Height($0) ).

Com que les rutines no modifiquen aquests paràmetres, només cal escriure'ls un cop als registres. 2 Invocació i restauració: s'executa jal voltejarH . En tornar, es recupera l'adreça original mitjançant lw $ra, 0($sp) , s'allibera la pila amb addu $sp, $sp, 4 i es tanca l'execució tornant al sistema amb jr $ra . 3 MIPS: arquitectura, memòria i assemblador ETC II 12 IDEES CLAU Els programes en MIPS s'estructuren en un segment de dades (<code>.data</code>) per a variables i memòria, i un o més segments d'instruccions (<code>.text</code>) per al codi executable.

Les macros (<code>.macro</code> / <code>.end_macro</code>) produeixen una substitució textual en temps d'assemblat sense generar una crida de subrutina real. L'ús de registres temporals dins d'una macro sobrescriu els seus valors previs en el programa principal, ja que les macros no preserven el context automàticament. Les etiquetes associen noms a posicions de memòria tant per saltar a bucles com per delimitar l'inici o final de blocs de codi. COMPROVA EL QUE HAS APRÈS 15. En què es diferencia l'execució d'una macro de la crida a una rutina mitjançant jal? 16. Per què la macro swap ($s1, $s2, $t1) provoca un efecte secundari a $t1? Test Encercla la resposta correcta.

Les solucions són al final. 17. Quina directiva s'utilitza per iniciar el bloc que conté el codi màquina executable? 18. Com gestiona l'assemblador una macro durant el procés de traducció? 19. Quin risc comporta emprar un registre com a paràmetre temporal a la macro swap? 20. Quants bytes reserva .space 4256 per a una imatge de 38x28 elements de tipus paraula?

.data a) .space b) .text c) .code d) Fa una crida amb jal a memòria a) Reserva espai en el segment de dades b) Substitueix el codi textualment cada vegada c) Genera una rutina amb pila aïllada d) Destrueix el contingut previ del registre a) Bloqueja el registre per a escriptures futures b) Provoca una fallada de segmentació immediata c) Obliga a canviar el segment de text d) 1064 bytes a) 4256 bytes b) 2128 bytes c) 8512 bytes d) MIPS: arquitectura, memòria i assemblador ETC II 13 3 Repertori d'instruccions i pseudoinstruccions MIPS EN ACABAR SABRÀS Distingir entre instruccions natives de MIPS32 i pseudoinstruccions generades per l'assemblador.

Explicar com l'assemblador tradueix operacions comunes com move, clear i salts condicionals complexos. Descompondre la càrrega d'una adreça o constant de 32 bits en la seqüència nativa lui i ori. PENSA-HI ABANS DE LLEGIR 21 Com pot un processador que només admet constants de 16 bits carregar una adreça de memòria de 32 bits en un registre? Instruccions natives i la limitació dels valors immediats L'arquitectura MIPS utilitza instruccions de longitud fixa de 32 bits (una paraula o word). Com que la instrucció sencera ocupa 32 bits, el màxim nombre de bits que pot tenir un valor immediat és estrictament de 16 bits. DEFINICIÓ: INSTRUCCIÓ NATIVA VS.

PSEUDOINSTRUCCIÓ Una instrucció nativa és aquella que la unitat de control de la CPU MIPS pot descodificar i executar directament en maquinari. En canvi, una pseudoinstrucció és una instrucció fictícia que l'assemblador reconeix per comoditat del programador i que tradueix automàticament a una o més instruccions natives reals abans de generar el codi binari final. Aquesta divisió permet a MIPS disposar d'un joc d'instruccions reduït i altament optimitzat (filosofia RISC), delegant en l'assemblador la síntesi d'operacions més complexes. COMPROVA-HO 22 Quina limitació física tenen les constants numèriques emmagatzemades directament dins d'una instrucció de tipus I a MIPS?

Repertori d'instruccions natives de MIPS32 Les instruccions natives es divideixen en blocs funcionals segons el tipus d'operació que executen sobre la memòria, els registres o el flux del programa. MIPS: arquitectura, memòria i assemblador ETC II 14 ESQUEMA Famílies d'instruccions natives de MIPS32 Operacions aritmètiques i de desplaçament Les operacions aritmètiques permeten realitzar càlculs bàsics tant amb operands de registres com amb valors immediats.

MIPS diferencia entre operacions amb signe i sense signe pel que fa a la gestió de desbordament (overflow): Mnemònic Nom complet Descripció funcional add / addu Add Word / Add Unsigned Word Suma dos registres (amb o sense detecció de desbordament). addi / addiu Add Immediate / Add Imm. Unsigned Suma un registre i una constant de 16 bits amb o sense signe. sub / subu Subtract / Subtract Unsigned Resta el valor de dos registres. mult Multiply Word Multiplica dos registres de 32 bits amb signe; el resultat de 64 bits es desa als registres especials HI i LO. div / divu Divide / Divide Unsigned Divideix dos registres; el quocient es guarda a LO i el residu a HI.

slt / slti Set on Less Than / Immediate Posa el registre destinació a 1 si el primer operand és menor que el segon; si no, el posa a 0. clo / clz Count Leading Ones / Zeros Compta el nombre d'uns o de zeros consecutius des del bit més significatiu. sll / srl Shift Left Logical / Shift Right Logical Desplaçament de bits a l'esquerra o a la dreta afegint zeros pel costat oposat. Instruccions lògiques i de transferència de registres especials Les instruccions lògiques operen bit a bit sobre registres o combinant un registre amb una màscara immediata de 16 bits: and , andi : operació i lògica a nivell de bit.

Aritmètica i Lògica add, sub, mult, and, ori, slt Memòria (Load/Store) lw, sw, lb, sb, lh, sh Bifurcació i Salts beq, bne, j, jal, jr Control i Sistema nop, syscall, break, teq MIPS: arquitectura, memòria i assemblador ETC II 15 or , ori : operació o lògica; molt utilitzada per establir bits o carregar constants immediates. xor , xori : operació o exclusiva. nor : operació no-o lògica; permet obtenir la inversió de bits (NOT) quan s'opera un registre amb $0.

Com que les operacions mult i div no guarden el seu resultat en un registre de propòsit general, cal disposar d'instruccions per moure dades des dels registres auxiliars HI i LO: mfhi (Move From Hi) i mflo (Move From Lo): copien el valor des del registre especial corresponent cap a un registre general. mthi (Move To Hi) i mtlo (Move To Lo): escriuen un valor des d'un registre general cap a HI o LO. Instruccions de càrrega i emmagatzematge en memòria MIPS és una arquitectura Load/Store: cap operació aritmètica pot operar directament sobre la memòria; cal carregar prèviament les dades als registres i emmagatzemar els resultats posteriorment.

Mnemònic Nom complet Mida transferida Comportament lb Load Byte 8 bits (1 byte) Carrega el byte i n'estén el bit de signe fins als 32 bits. lh Load Halfword 16 bits (2 bytes) Carrega mitja paraula amb extensió de signe. lw Load Word 32 bits (4 bytes) Carrega una paraula sencera (requereix alineament múltiple de 4). sb Store Byte 8 bits (1 byte) Guarda el byte inferior del registre a la memòria. sh Store Halfword 16 bits (2 bytes) Guarda els 16 bits inferiors del registre a la memòria. sw Store Word 32 bits (4 bytes) Guarda la paraula sencera de 32 bits a la memòria.

Bifurcacions, salts i control de flux El control del programa es divideix en salts condicionals (branches) i salts incondicionals (jumps): beq (Branch on Equal): salta a una etiqueta si dos registres són iguals. bne (Branch on Not Equal): salta si dos registres són diferents. bgtz / bgez : salta si el registre és estrictament major que zero ( ) o major o igual a zero ( ). bltz / blez : salta si el registre és menor que zero ( ) o menor o igual a zero ( ). j (Jump): salt incondicional a una adreça de codi. jal (Jump and Link): salt incondicional guardant l'adreça de retorn al registre $ra (vegeu «Subrutines, gestió de la pila i conveni MIPS»).

jr (Jump Register): salt incondicional a l'adreça continguda dins d'un registre general. > 0 0 < 0 0 MIPS: arquitectura, memòria i assemblador ETC II 16 Instruccions de control, sistema i gestió d'excepcions Per a la sincronització, la gestió de condicions anòmales i la interacció amb el sistema operatiu, MIPS ofereix diverses instruccions específiques: DEFINICIÓ: LA INSTRUCCIÓ NOP La instrucció nop (No Operation) és una instrucció de control que indica a la CPU que no faci cap acció durant aquell cicle de rellotge. A MIPS, es codifica a nivell màquina com 32 zeros consecutius, cosa que coincideix de manera exacta amb la instrucció nativa sll $0, $0, 0 .

D'altra banda, per comunicar-se amb el sistema operatiu o aturar l'execució s'utilitzen: syscall : cedeix el control al sistema operatiu per sol·licitar un servei (com ara entrades/sortides o finalització del programa). break : genera una excepció per definir un punt d'aturada (breakpoint) útil en tasques de depuració. Instruccions de trap: avaluen una condició lògica i, si es compleix, disparen una excepció al sistema automàticament. Exemples habituals inclouen teq (Trap if Equal), teqi (Trap if Equal Immediate), tge (Trap if Greater or Equal), tlt (Trap if Less Than) i tne (Trap if Not Equal).

COMPROVA-HO 23 Quina relació binària hi ha entre la instrucció màquina de 32 zeros i el desplaçament lògic a MIPS? Pseudoinstruccions i la seva traducció a codi màquina Les pseudoinstruccions amplien el ventall expressiu de l'assemblador, permetent que el programador escrigui instruccions més intuïtives que el processador no té implementades físicament.

Pseudoinstrucció Significat Implementació equivalent en instruccions natives move $t0, $t1 Còpia de registres addu $t0, $t1, $0 clear $t0 Posar a zero un registre add $t0, $0, $0 o addu $t0, $0, $0 bgt $t0, $t1, L Salta si slt $at, $t1, $t0 seguit de bne $at, $0, L blt $t0, $t1, L Salta si slt $at, $t0, $t1 seguit de bne $at, $0, L bge $t0, $t1, L Salta si slt $at, $t0, $t1 seguit de beq $at, $0, L ble $t0, $t1, L Salta si slt $at, $t1, $t0 seguit de beq $at, $0, L Descomposició de càrregues de 32 bits (lui i ori) Atès que els registres i les adreces a MIPS tenen una mida de 32 bits, però el màxim nombre de bits que pot tenir un valor immediat és 16, és impossible assignar una adreça arbitrària completa o una constant de 32 bits en una sola instrucció nativa.

Per superar aquest obstacle, l'arquitectura ofereix la t0 > t1 t0 < t1 t0 t1 t0 t1 MIPS: arquitectura, memòria i assemblador ETC II 17 instrucció lui . DEFINICIÓ: LUI (LOAD UPPER IMMEDIATE) La instrucció nativa lui carrega un valor immediat de 16 bits als 16 bits més significatius (part alta) del registre de destinació, mentre omple automàticament els 16 bits menys significatius (part baixa) amb zeros. Quan utilitzem la pseudoinstrucció li (Load Immediate) per carregar un valor que cap en 16 bits (o ori directe per a valors menors), el procés es resol ràpidament.

Per exemple: li $8, Immediat15..0 Es tradueix simplement com una o lògica amb el registre zero: ori $8, $0, Immediat15..0 Tanmateix, si es tracta de carregar una adreça de 32 bits mitjançant la pseudoinstrucció la (Load Address), l'assemblador la descompon forçosament en dues etapes: PROCÉS Descomposició de càrrega d'adreça (la) 1 Pseudoinstrucció la Petició de càrrega d'una adreça de 32 bits 2 Execució de lui Assigna els 16 bits alts al registre destinació 3 Execució d'ori Fusiona els 16 bits baixos mitjançant una OR lògica 4 Adreça completa Registre amb l'adreça de 32 bits carregada EXEMPLE: DESCOMPOSICIÓ DE LA INSTRUCCIÓ LA Per carregar l'adreça completa d'una variable mitjançant: la $8, Immediat31..0 L'assemblador generarà exactament la seqüència nativa següent: lui $8, Immediat31..16 ori $8, $8, Immediat15..0 Càrrega de la meitat superior: S'utilitza lui per col·locar els 16 bits alts ( ) a la part alta del registre destinació.

1 Immediat 31..16 Fusió de la meitat inferior: S'executa una operació ori sobre el mateix registre amb els 16 bits baixos ( ). Com que els 16 bits inferiors eren zeros després del lui , l'OR lògic inserta el valor baix sense alterar la part alta. 2 Immediat 15..0 MIPS: arquitectura, memòria i assemblador ETC II 18 Càrrega de dades amb etiqueta i registre base Un cas molt freqüent en programació és l'accés a dades mitjançant una etiqueta combinada amb un desplaçament en registre: lw $9, A($8) . Si l'adreça de l'etiqueta A requereix 32 bits, la instrucció nativa lw no la pot codificar directament com a offset de 16 bits.

L'assemblador resol aquesta contradicció convertint la línia en una pseudoinstrucció de tres passos: ERROR FREQÜENT: CONFONDRE INSTRUCCIONS DE CÀRREGA LA I LW Un error molt comú en els exàmens és confondre la (Load Address) amb lw (Load Word). La instrucció la $t0, var obté el punter o l'adreça de memòria on resideix la variable. En canvi, lw $t0, var accedeix al contingut emmagatzemat a aquella adreça i el copia al registre. Utilitzar lw quan es volia obtenir l'adreça provocarà una fallada de segmentació o càlculs d'adreces erronis. COMPROVA-HO 24 Per què la pseudoinstrucció la requereix l'ús combinat de lui i ori en lloc d'una sola instrucció addi?

IDEES CLAU Les instruccions a MIPS tenen una mida de 32 bits i els seus valors immediats estan limitats a un màxim de 16 bits. Els camps immediats en instruccions de tipus I estan limitats estrictament a 16 bits. La instrucció nop es codifica màquina com 32 zeros, equivalent a l'operació . L'assemblador tradueix les pseudoinstruccions a una o diverses instruccions natives reals. La càrrega d'una constant o adreça de 32 bits amb la es descompon en lui (part alta) i ori (part baixa). COMPROVA EL QUE HAS APRÈS 25. Com sintetitza l'assemblador la pseudoinstrucció move $t0, $t1 en codi màquina natiu? 26. Què fa exactament la instrucció lui $t0, 0x1234 sobre el registre destinació?

Carrega l'adreça base de l'etiqueta a un registre auxiliar (per conveni, el registre reservat a l'assemblador $1 o $at) mitjançant lui $1, adreça_alta . 1 Afegeix el contingut del registre índex o base inicial: addu $1, $1, $8 . 2 Fa la lectura efectiva des de la posició calculada: lw $9, 0($1) . 3 sll $0, $0, 0 MIPS: arquitectura, memòria i assemblador ETC II 19 Test Encercla la resposta correcta. Les solucions són al final. 27. Com es codifica físicament la instrucció nop en maquinari MIPS32? 28. Quina combinació nativa utilitza l'assemblador per descompondre la càrrega la $r, adreça de 32 bits? 29. A quina instrucció bàsica recorre MIPS per emmagatzemar una paraula de 32 bits a la memòria?

30. Quina diferència funcional hi ha entre executar la instrucció la i la instrucció lw sobre una etiqueta? 4 Traducció d'estructures de control d'alt nivell EN ACABAR SABRÀS Traduir estructures condicionals if-then-else emprant salts de condició oposada Deduir el codi d'alt nivell equivalent a partir d'un fragment de codi assemblador MIPS Implementar bucles while, do-while i for amb control de sortida i comptadors Construir l'estructura de selecció múltiple switch tant amb jumptable com amb comparacions en cascada PENSA-HI ABANS DE LLEGIR 31 Per què en passar una condició de C com if (a == b) a assemblador MIPS solem fer servir la instrucció de desigualtat bne?

Una seqüència binària de 32 zeros a) Un salt a la instrucció següent b) Una suma d'un registre amb si mateix c) Una crida al sistema de tipus trap d) mult seguida de mfhi per assignar bits a) addiu seguida d'un desplaçament srl b) lui seguida d'una operació ori c) lw combinada amb un desplaçament sll d) sh a) sw b) lw c) sb d) la només opera amb bytes de memòria a) la obté l'adreça i lw el contingut b) Totes dues fan la mateixa lectura exacta c) la obté el contingut i lw l'adreça d) MIPS: arquitectura, memòria i assemblador ETC II 20 Els llenguatges d'alt nivell empren construccions com condicions, alternatives múltiples i bucles per articular el flux d'execució.

El processador MIPS no disposa d'aquestes estructures de manera nativa; per tant, cal transformar-les mitjançant salts condicionals, salts incondicionals i etiquetes. ESQUEMA Estructures de control a MIPS Estructures condicionals: if-then-else Per implementar una alternativa simple (if-then-else), el patró general consisteix a avaluar la condició i saltar al bloc alternatiu quan aquesta no es compleix. S'empra la tècnica del salt amb condició oposada: si el codi d'alt nivell demana entrar quan dues variables són iguals, l'assemblador utilitzarà una instrucció de desigualtat com bne per desviar el flux directament a la branca de l'else.

Quan la branca afirmativa s'executa completament, cal incloure un salt incondicional j que esquivi les instruccions del bloc fals. Sense aquest salt, el processador continuaria seqüencialment i executaria també les instruccions de l'alternativa.

Estructura en C Estratègia en MIPS Instrucció clau Salt si són diferents cap a l'alternativa Comparació a registre auxiliar i salt si és zero slt seguit de beq (sense else) Salt oposat si menor o igual per sortir del bloc Condicionals Selecció mitjançant salts If-Then-Else Salts oposats i salt incondicional Switch-Case Jumptable o comparació cascada Iteratives Bucles i comptadors Bucle While Avaluació a l'inici Bucle Do-While Avaluació a la cua Bucle For Comptador i recorregut matrius i == j bne $s0, $s1, else i < j i > j ble $s0, $s1, fora MIPS: arquitectura, memòria i assemblador ETC II 21 EXEMPLE Traducció d'una assignació condicional: si , aleshores ; en cas contrari, .

ERROR FREQÜENT Oblidar la instrucció j incondicional al final del bloc then. Si s'omet aquest salt, el flux del programa continuarà línia a línia i sobreescriurà el resultat amb el codi del bloc else. COMPROVA-HO 32 Si volem implementar l'estructura d'alt nivell if (a != b) { c = d; }, quina instrucció de salt condicional hem d'utilitzar per esquivar el bloc? Traducció inversa: d'assemblador a alt nivell Quan s'interpreta un programa en assemblador per recuperar el codi original en llenguatge C, cal invertir el sentit del salt condicional. En trobar una instrucció com situada a l'inici d'un bloc, s'evidencia que les instruccions interiors només s'executen quan la condició del salt falla.

Per tant, la condició lógica subjacent és $s0 > $s1. PER RECORDAR-HO L'assemblador salta quan la condició d'alt nivell és falsa. Per passar a C, agafa la condició del salt condicional i escriu la seva oposada estricta. Bucles condicionals: while i do-while El bucle while realitza una avaluació prèvia a l'entrada de cada iteració. Si la condició no es satisfà des d'un inici, el cos de la iteració mai arriba a executar-se. A MIPS s'estructura amb una etiqueta inicial de retorn, una comprovació que salta a l'etiqueta final en cas contrari, el cos d'instruccions i finalment un salt incondicional j a la capçalera.

Aquest patró s'utilitza habitualment per tractar vectors o cadenes de caràcters acabades en sentinella, com en cadenes .asciiz on es llegeix byte a byte fins a trobar un salt de línia o caràcter final mitjançant beq. dades1 < dades2 c = 100 c = 1000 Carregar dades1 a i dades2 a mitjançant lw. 1 $t0 $t1 Avaluar la desigualtat amb . Si , ; si no, . 2 slt $t3, $t0, $t1 $t0 < $t1 $t3 = 1 $t3 = 0 Verificar la fallada de la condició amb . 3 beq $t3, $0, else Executar la branca certa assignant el valor mitjançant i saltar al final amb j continua. 4 addi $s0, $0, 100 Sota l'etiqueta else: , carregar el valor alternatiu mitjançant .

5 addi $s0, $0, 1000 ble $s0, $s1, foraif MIPS: arquitectura, memòria i assemblador ETC II 22 Per contra, l'estructura repeat-until o do-while presenta una avaluació posterior. El cos del bucle s'executa sempre com a mínim un cop. Al final de la iteració, una instrucció condicional comprova si cal repetir el procés, saltant directament a l'inici sense necessitat de salts incondicionals auxiliars. COMPROVA-HO 33 Quina diferència principal presenta el cost d'instruccions de salt entre un bucle while i un bucle do-while a MIPS? Bucles for i recorregut de matrius El bucle for és una especialització del bucle per comptador.

Consta d'una inicialització del registre comptador, una avaluació de límit, el bloc d'instruccions a executar i la modificació incremental del comptador (habitualment amb addi). Quan s'implementen bucles niuats per recórrer estructures bidimensionals com matrius (vegeu «Arquitectura MIPS — Organització de la memòria i registres»), s'utilitza un cicle exterior per a les files i un cicle interior per a les columnes. Per accedir a la posició en una matriu de dimensions , cal computar l'adreça de memòria corresponent.

El desplaçament lineal de cada cel·la en una distribució per files es determina mitjançant la fórmula: A MIPS, la multiplicació de l'índex compost per 4 (mida d'una paraula en bytes) es realitza mitjançant un desplaçament lògic a l'esquerra de dues posicions amb , optimitzant el càlcul d'accés a memòria amb la instrucció sw. COMPROVA-HO 34 Per què s'aplica una operació sll de 2 bits a l'índex calculat abans de guardar o llegir un enter d'una matriu a memòria? Estructura switch-case L'estructura de selecció múltiple o switch pot traduir-se a l'arquitectura MIPS seguint dues estratègies diferenciades: mitjançant una taula de salts (jumptable) o mitjançant comparacions en cascada.

Taula de salts (jumptable) La taula de salts és l'estratègia més eficient quan els casos són nombres enters consecutius o densos. Es defineix a memòria un vector d'adreces corresponents a les etiquetes de cada cas ( ). c i,j N × M Despla ament = ç (i M + j) 4 sll $s0, $t6, 2 L , L , L ... 0 1 2 Multiplicar el selector de cas per 4 utilitzant un desplaçament per obtenir el desplaçament en bytes. 1 sll $t1, $s0, 2 Carregar a un registre l'adreça de l'etiqueta objectiu mitjançant . 2 lw $t2, jumptable($t1) Efectuar un salt indirecte al destí calculat mitjançant la instrucció jr $t2. 3 En finalitzar el bloc de cada cas, afegir un salt j exit que emula la sentència break d'alt nivell.

4 MIPS: arquitectura, memòria i assemblador ETC II 23 Comparacions en cascada Quan els valors del switch són dispersos o representen caràcters solts d'un menú d'usuari (per exemple, les opcions 's' , 'r' , 'm' , 'd' , 'p' ), s'utilitzen comparacions individuals consecutives. La pseudoinstrucció s'expandeix en una càrrega del valor immediat a un registre temporal ( ) seguida d'un beq entre registres. Cada branca fa les operacions pertinents i salta a la rutina final comú. IDEES CLAU Les estructures condicionals en assemblador inverteixen la lògica d'alt nivell per saltar quan la condició no es compleix.

L'omissió del salt incondicional j al final del bloc de certesa fa que el flux s'executi seqüencialment sobre el bloc alternatiu. El bucle while requereix avaluar la condició abans d'executar el cos, mentre que el do-while l'avalua a la cua de la iteració. L'adreçament de matrius bidimensionals requereix calcular utilitzant sll de 2 bits. La taula de salts (jumptable) implementa un switch mitjançant un salt indirecte amb jr basat en una adreça emmagatzemada a memòria. Els menús amb opcions disperses o caràcters s'implementen habitualment amb branques de comparació en cascada. COMPROVA EL QUE HAS APRÈS 35. Com s'obté l'adreça de salt d'una jumptable a partir del valor enter d'un cas k? 36.

Què succeeix en una estructura switch en assemblador si s'oblida el salt incondicional a la sortida d'un cas? Test Encercla la resposta correcta. Les solucions són al final. 37. Quina instrucció de salt substitueix directament la condició d'alt nivell if (a == b) cap a l'etiqueta else? 38. Quina instrucció permet saltar a l'adreça obtinguda d'una taula jumptable? 39. A quina operació aritmètica correspon la instrucció sll $s0, $t6, 2 emprada en matrius?

beq $v0, 's', etiqueta $at/$1 (i M + j) 4 slt $t0, $s0, $s1 a) bne $s0, $s1, else b) j else c) beq $s0, $s1, else d) j $t0 a) bne $t0, $0 b) jr $t0 c) jal $t0 d) Sumar 4 al valor a) Dividir el valor per 4 b) Multiplicar el valor per 2 c) Multiplicar el valor per 4 d) MIPS: arquitectura, memòria i assemblador ETC II 24 40. En quina circumstància és preferible un switch en cascada sobre una jumptable? 5 Algorismes fonamentals en assemblador EN ACABAR SABRÀS Distingir l'eficiència computacional entre l'accés a dades per índex i per punter en memòria. Implementar la conversió d'un text a majúscules aplicant les operacions aritmètiques del codi ASCII.

Construir l'algorisme d'ordenació de la bombolla gestionant el registre de bandera i la indexació decreixent. Programar la cerca dicotòmica iterativa calculant la posició central i ajustant els límits del rang de cerca. PENSA-HI ABANS DE LLEGIR 41 Per què un compilador optimitzador prefereix recórrer un vector avançant un punter en comptes d'incrementar un comptador i fer v[i]? Processament de cadenes i recorregut de dades en memòria El tractament d'estructures contigües a la memòria (com cadenes de caràcters o vectors) planteja una decisió clau de disseny: accedir a cada posició mitjançant un índex o desplaçar directament un punter.

Per entendre aquest contrast, analitzem la conversió d'un text a majúscules mitjançant la rutina toupper . CODI ASCII I CONVERSIÓ DE CARÀCTERS En el joc de caràcters ASCII, les lletres majúscules ocupen els valors decimals del 65 al 90 (de la 'A' a la 'Z'), mentre que les minúscules es troben entre el 97 i el 122 ('a'-'z'). La diferència numèrica entre una majúscula i la seva minúscula és exactament 32. Per convertir una minúscula en majúscula, n'hi ha prou amb restar 32 al seu valor en un bucle que finalitza quan detecta el caràcter nul de fi de cadena (0).

Aquesta transformació es pot programar en llenguatge d'alt nivell de dues maneres diferents, les quals es tradueixen en estratègies d'assemblador clarament diferenciades: Quan els casos són dispersos o caràcters a) Quan el nombre de casos és molt gran b) Quan els índexs són consecutius c) Quan es vol màxima velocitat d'accés d) MIPS: arquitectura, memòria i assemblador ETC II 25 Característica Accés per índex ( str[i] ) Accés per punter ( *str ) Mètode d'accés Es manté l'adreça base fixa i un índex separat que s'incrementa. Es desplaça directament el registre que conté l'adreça de memòria. Càlcul d'adreça a cada volta Requereix recalcular sumant registres a cada iteració.

Només cal sumar l'increment (+1 en bytes o +4 en paraules) al mateix punter. Sobrecàrrega en paraules (words) Obliga a multiplicar l'índex per 4 abans de sumar-lo a la base. No necessita multiplicacions: només avança directament de 4 en 4 bytes. Eficiència d'instruccions Menor: més instruccions aritmètiques dins del cos del bucle. Major: estalvia instruccions de càlcul d'adreça per element. Observant el codi assemblador generat per a cadascuna, la versió per índex utilitza un registre comptador (per exemple, $t0 per a l'índex ) i fa una suma explícita add $t1, $t0, $a0 per obtenir l'adreça de l'element abans de carregar-lo amb lb $t2, 0($t1) .

En canvi, la versió per punter utilitza directament el registre base rebut ($a0), carrega amb lb $t2, 0($a0) i avança al final amb una única instrucció addi $a0, $a0, 1 . ERROR FREQÜENT Quan s'accedeix a vectors d'enters (paraules de 32 bits) per índex, un error habitual és oblidar multiplicar l'índex per 4 abans de sumar-lo a l'adreça base. Si s'utilitza accés per punter, l'avanç no pot ser d'una unitat: cal sumar sempre 4 bytes per saltar a la paraula següent (vegeu «Arquitectura MIPS — Organització de la memòria i registres»). COMPROVA-HO 42 Per què l'accés per punter resulta computacionalment més eficient que l'accés per índex en el recorregut seqüencial d'un vector d'enters?

Ordenació de vectors: algorisme de la bombolla (BubbleSort) L'algorisme d'ordenació de la bombolla compara parelles d'elements consecutius i els intercanvia si no estan en l'ordre adequat. Aquest procediment es repeteix en passades successives fins que no es realitza cap intercanvi, senyal que el vector ja està ordenat.

PROCÉS Passades de l'ordenació de la bombolla en MIPS 1 Inicialització de passada Es posa la bandera a zero i el punter al penúltim element 2 Comparació de parella Es carreguen dues paraules consecutives i es comparen 3 Intercanvi si escau Si estan desordenades s'inverteixen a memòria i bandera = 1 4 Comprovació de final Si la bandera roman a zero en acabar la passada, s'acaba adre a = ç base + ndex ı ˊ i MIPS: arquitectura, memòria i assemblador ETC II 26 Per implementar-lo eficientment en assemblador MIPS, resulta molt convenient transformar l'estructura habitual del bucle.

En lloc de fer avançar l'índex intern des de 0 fins a la longitud, és habitual inicialitzar el punter o desplaçament a la posició superior i decrementar fins a assolir el límit inferior. La raó tècnica és directa: comparar un registre amb zero és més ràpid i senzill en MIPS que avaluar-lo contra una fita variable calculada a la memòria. L'esquema de funcionament del codi requereix els registres següents: Longitud i desplaçament màxim ($a0): emmagatzema la mida del vector. Es multiplica per 4 aplicant un desplaçament lògic a l'esquerra ( sll $a0, $a0, 2 ) per transformar elements en bytes de memòria.

Punter de recorregut ($t0): s'inicialitza a , apuntant al penúltim element del vector, i es decrementa de 4 en 4 ( sub $t0, $t0, 4 ) a cada passada fins a arribar a un valor negatiu (comprovat amb bgez ). Bandera d'intercanvi ($t1): actua com a indicador o booleà (flag). S'inicialitza a 0 abans de cada passada; si s'efectua algun intercanvi es posa a 1. El bucle exterior finalitza quan $t1 roman a 0 (verificat mitjançant bnez ). INTERCANVI D'ELEMENTS (SWAP) EN ASSEMBLADOR Per avaluar i permutar dues paraules adjacents i es carreguen els seus valors en registres temporals: COMPROVA-HO 43 Quina funció té la comprovació de la bandera ($t1) al final del bucle d'ordenació de la bombolla?

Cerca dicotòmica iterativa La cerca dicotòmica o binària és un algorisme eficient per localitzar la posició d'un element en un vector que ja es troba prèviament ordenat. A cada iteració, l'algorisme divideix a la meitat l'espai de cerca comparant el valor objectiu amb l'element situat al punt mitjà. Aquest enfocament redueix dràsticament el cost computacional: per exemple, en un vector d'uns 50 milions d'elements només cal fer com a màxim 26 comparacions per localitzar la dada o determinar que no hi és. Tot i que es pot plantejar de manera recursiva, la implementació iterativa evita la creació de marcs a la pila.

$a0 8 A[j] A[j + 1] Carregar els dos valors contigus: lw $t2, A+4($t0) i lw $t3, A($t0) . 1 Comprovar la condició d'ordre: amb bgt $t2, $t3, no_swap , si el segon és estrictament major que el primer, no cal canvi. 2 Realitzar l'escriptura creuada si estan desordenats: sw $t2, A($t0) i sw $t3, A+4($t0) . 3 Assignar el valor 1 al registre de bandera: li $t1, 1 per forçar una nova passada completa del vector.

4 MIPS: arquitectura, memòria i assemblador ETC II 27 PROCÉS Flux de decisió en la cerca dicotòmica 1 Càlcul del mig Es divideix la suma d'esquerra i dret entre 2 2 Avaluació del valor Es compara la dada central amb l'element cercat 3 Ajust de límits Es redueix l'interval a mig-1 o mig+1 segons el valor En l'algorisme iteratiu en MIPS s'assignen variables d'estat a registres concrets: Estat de cerca ($t0): indicador booleà trobat , inicialitzat a 0. Es posa a 1 només si l'element de la posició mitjana coincideix amb la clau cercada. Límits de la cerca: límit esquerre a i límit dret a (on és la longitud emmagatzemada a memòria). Element objectiu ($t3): contingut del valor que es vol trobar.

Càlcul de la posició mitjana ($t5): es calcula sumant i dividint el resultat entre 2 (mitjançant la instrucció div seguida de mflo ). El cos del bucle s'executa mentre es compleixin dues condicions simultànies: que el límit esquerre sigui menor o igual que el dret ( ) i que encara no s'hagi trobat el valor ( ). Un cop calculat el punt mitjà $t5, cal multiplicar-lo per 4 (fent sll $t7, $t5, 2 ) abans de fer la càrrega de dades lw $t6, Vector($t7) .

Segons el resultat de comparar el valor de memòria $t6 amb l'objectiu $t3, es prenen tres possibles camins: En sortir del bucle, si el valor de $t0 continua sent 0, el programa assigna el codi d'error -1 al registre de sortida $a0 abans d'invocar la crida al sistema per imprimir el resultat. COMPROVA-HO 44 Quina operació prèvia cal fer sobre l'índex del punt mitjà abans d'executar la instrucció lw en la cerca binària? $t1 = 0 $t2 = n 1 n esquerra + dret esquerra dret !trobat Coincidència exacta: si , s'assigna la posició a l'índex final ( ), es marca la troballa posant i es tanca la iteració.

1 valor == vector[mig] $t1 = $t5 $t0 = 1 Valor inferior al mig: si l'objectiu és menor que l'element del mig, el límit dret es desplaça cap a l'esquerra: (restando 1 amb subu ). 2 $t2 = mig 1 Valor superior al mig: si l'objectiu és més gran, el límit esquerre s'avança cap a la dreta: (sumant 1 amb addu ). 3 $t1 = mig + 1 MIPS: arquitectura, memòria i assemblador ETC II 28 IDEES CLAU La distància en codi ASCII entre una lletra majúscula i la seva minúscula és exactament de 32 unitats. El recorregut per punter és més ràpid que per índex perquè evita sumar la base i multiplicar per la mida de la paraula a cada iteració.

En BubbleSort per a MIPS és més eficient iterar els desplaçaments en compte enrere cap a zero, aprofitant les instruccions bgez. La cerca binària requereix un vector prèviament ordenat i redueix el temps de cerca fins a un màxim logarítmic de comparacions. Per carregar una paraula d'un vector d'enters a partir d'un índex lògic, és imprescindible desplaçar 2 bits a l'esquerra (multiplicar per 4) l'índex per adreçar correctament la memòria en bytes. COMPROVA EL QUE HAS APRÈS 45. Com es realitza la conversió de caràcters minúscules a majúscules sobre una cadena en codi ASCII? 46. Quin avantatge ofereix l'accés continu per punter respecte a l'accés per índex en vectors de tipus paraula (words)?

47. Quin valor de sortida retorna la rutina de cerca dicotòmica quan el valor sol·licitat no és present al vector? Test Encercla la resposta correcta. Les solucions són al final. 48. Quina diferència numèrica exacta separa el valor ASCII d'una minúscula del de la seva majúscula? 49. Per què s'utilitza la instrucció sll per dues posicions sobre l'índex d'un vector de paraules? 50. Com detecta l'algorisme de la bombolla que el vector ha quedat completament ordenat?

48 a) 32 b) 64 c) 16 d) Per multiplicar per 4 l'índex a) Per dividir entre dues unitats b) Per netejar els bits inferiors c) Per calcular el punt mitjà d) Quan el punter arriba a 0 a) Quan la bandera d'intercanvi és 0 b) Quan l'índex assoleix la mida màxima c) En creuar els límits dels extrems d) MIPS: arquitectura, memòria i assemblador ETC II 29 51. Què succeeix en la cerca dicotòmica si el valor és menor que l'element de la posició mitjana? 6 Subrutines, gestió de la pila i conveni MIPS EN ACABAR SABRÀS Gestionar correctament la pila mitjançant el punter $sp decrementant i incrementant adreces. Implementar crides a rutina niades salvaguardant el registre $ra a la memòria.

Aplicar el conveni MIPS32 diferenciant entre registres caller-saved ($t0-$t9) i callee-saved ($s0-$s7). PENSA-HI ABANS DE LLEGIR 52 Per què s'avaria el flux de retorn d'un programa si una rutina crida una altra subrutina sense tocar la pila? Estructura i gestió de la pila (stack) La modularitat mitjançant rutines permet reduir la mida del codi, simplificar la depuració, facilitar el manteniment i compartir instruccions. No obstant això, la concurrència d'execució entre fragments de codi requereix una estructura dinàmica de memòria per emmagatzemar dades temporals: la pila (stack).

A l'arquitectura MIPS, la pila d'usuari s'inicialitza durant la fase de linkatge amb el límit superior situat habitualment a l'adreça 0x7fffffff. La pila creix en sentit descendent cap a posicions baixes de memòria. Dos registres gestionen aquesta estructura: el punter de pila $sp (registre físic $29), que assenyala sempre l'última posició ocupada, i el punter de marc $fp (registre físic $30), emprat com a base estable per referenciar dades locals i paràmetres. Les dues operacions fonamentals sobre la pila són apilar (PUSH) i desapilar (POP).

Com que cada paraula ocupa 4 bytes, cal ajustar el valor de restant o sumant 4 unitats abans o després de transferir la informació amb les instruccions de memòria: Es posa la bandera trobat a 1 a) S'assigna esquerra = mig + 1 b) S'assigna dret = mig - 1 c) Es finalitza retornant la posició -1 d) $sp MIPS: arquitectura, memòria i assemblador ETC II 30 EXEMPLE Manipulació bàsica d'apilament i desapilament d'un registre de 32 bits a MIPS: # PUSH (guardar el contingut de sp, sp, -4 # Reserva espai per a una paraula (creixement cap avall)\nswt0, 0($sp) # Emmagatzema el valor al nou cim de la pila # POP (recuperar el valor superior cap a $t0) lw $t0, 0($sp) # Carrega el valor situat al cim de la pila addi $sp, $sp, 4 # Allibera l'espai ocupat En el desenvolupament d'un programa, cada subrutina defineix el seu propi espai anomenat marc de pila (frame).

Aquest bloc de memòria s'estableix entre (final o cim dinàmic) i (base del marc), amb una mida estàndard de com a mínim 32 bytes. COMPROVA-HO 53 Per què cal restar un valor immediat a $sp per realitzar una operació de PUSH en lloc de sumar-lo? Mecanisme de crida i retorn: jal, jr i crides niades La invocació d'una rutina s'efectua mitjançant la instrucció de salt incondicional amb enllaç jal (jump and link). Aquesta instrucció transfereix el control a l'adreça de la subrutina i, simultàniament, desa l'adreça de la instrucció immediatament posterior (l'adreça de retorn procedent del comptador de programa) al registre $ra (registre físic $31).

Per retornar el flux d'execució cap a l'invocador un cop finalitzada la subrutina, s'executa la instrucció de salt a registre jr $ra. Aquest mecanisme directe és suficient quan una subrutina no crida cap altra funció (funció fulla). El problema sorgeix en les crides niades, on una funció invocada crida al seu torn una altra funció. La segona instrucció jal sobreescriu el contingut de $ra, perdent irremeiablement el punt de retorn cap al programa original si no s'ha preservat prèviament. La solució imprescindible consisteix a salvaguardar a la pila abans de produir qualsevol crida interna secundària.

ERROR FREQÜENT Oblidar desar el registre $ra a la pila abans d'executar un jal dins d'una subrutina provoca que la instrucció final retorni a la pròpia funció en comptes de tornar a l'invocador principal, generant un bucle infinit destructiu. COMPROVA-HO 54 Quina conseqüència té executar una segona instrucció jal dins d'una subrutina sense haver guardat abans el valor de $ra?

t0alapila)\naddi $sp $fp $ra jr $ra MIPS: arquitectura, memòria i assemblador ETC II 31 Pas de paràmetres i valors de retorn El traspàs d'arguments cap a una subrutina es pot dur a terme mitjançant dues modalitats bàsiques: Pas per valor: es copia el contingut directe de la variable al registre o posició de memòria destinat al paràmetre; la rutina treballa amb una còpia i no pot modificar la dada original de l'invocador. Pas per referència: es transfereix l'adreça de memòria on s'allotja la variable original, la qual cosa permet a la rutina accedir i modificar directament la dada allotjada.

L'arquitectura MIPS reserva registres concrets per a aquestes tasques per optimitzar la velocitat d'execució: Registres Funció principal Destinació en cas de saturació $a0 - $a3 ($4 - $7) Recepció dels 4 primers arguments o paràmetres d'entrada La pila d'usuari (a partir del 5è paràmetre) $v0 - $v1 ($2 - $3) Lliurament dels valors o resultats retornats per la rutina Memòria / pila reservada per l'invocador COMPROVA-HO 55 Com es gestiona el pas de paràmetres quan una funció necessita rebre 6 arguments d'entrada a MIPS? El conveni MIPS32: caller-saved, callee-saved i les 3 fases Perquè diversos procediments…