Arquitectura de Computadoras
Arquitectura de Computadoras para Ingeniería
Ejercicios prácticos complementarios
para promoción y final
Dra. Dana Urribarri
Universidad Nacional del Sur
5. jul. 2023
Nota: Estos son algunos de los ejercicios que he ido tomando en los exámenes de promoción y en los finales. Como
verán hay una gran variedad.
1
Ejercicio 1.
Suponiendo el siguiente escenario:
• Direccionamiento al byte
• Dirección física de 16 bits y dirección lógica de 24 bits
• Memoria virtual implementada con paginación. Los últimos 8 bits de la dirección representan el
desplazamiento dentro de la página.
• Memoria caché física, 2-way set associative, con 8 líneas de 64 bytes de dato.
Si se cuenta con un TLB de solo 4 entradas que contiene los siguientes datos:
1234H A3H 1b
1235H B1H 1b
AB12H 04H 0b
CD34H 17H 1b
Y una memoria cache con los siguientes datos:
idx Tag 1 V Data 1 (64 bytes ASCII) Tag 2 V Data 2 (64 bytes ASCII) Bits Extras
This·book·is·about·t purpose·is·to·presen
he·structure·and·fun t,·as·clearly·and·co
0 17H 0b 32H 0b
ction·of·computers.· mpletely·as·possible
Its· ,·th
e·nature·and·charact s·task·is·challengin
eristics·of·modern-d g·for·several·reason
1 A4H 1b A3H 1b
ay·computer·systems. s.·First,·there·is·a
·Thi ·tre
mendous·variety·of·p omputer,·from·single
roducts·that·can·rig -chip·microprocessor
2 17H 1b 18H 1b
htly·claim·the·name· s·costing·a·few·doll
of·c ars·
to·supercomputers·co s·exhibited·not·only
sting·tens·of·millio ·in·cost·but·also·in
3 17H 1b B8H 1
ns·of·dollars.·Varie ·size,·performance,·
ty·i and·
a) ¿Qué representa cada columna del TLB?
b) ¿A qué dirección física (o qué ocurre) al mapear las siguientes direcciones lógicas: AB1222H, 17CD34H,
CD34A4H, CD341CH, 123577H? En el caso de ser posible marque en el enunciado el carácter direccionado.
Explique las respuestas esquematizando gráficamente el proceso completo.
c) ¿Cuál es el tamaño para datos de la caché? ¿Cuál es el tamaño real de la caché teniendo en cuenta que es una
caché con política de escritura writeback – write allocate y con reemplazo LRU?
2
Ejercicio 2.
010800H Aquí␣me␣pongo␣a␣ Suponiendo el siguiente escenario:
cantar␣al␣compás • Direccionamiento al byte
␣de␣la␣vigüela,␣
• Dirección física de 16 bits y dirección lógica de 24 bits
que␣el␣hombre␣qu
e␣lo␣desvela␣una • Memoria virtual implementada con paginación. Los últimos 8 bits de la
␣pena␣estraordin dirección representan el desplazamiento dentro de la página.
aria,␣como␣la␣av • Memoria caché física, 2-way set associative, con 8 líneas de 32 bytes de
e␣solitaria␣con␣ dato, implemenada con políticas de escritura writeback y write-allocate y
el␣cantar␣se␣con reemplazo LRU.
suela.␣Pido␣a␣lo Si se cuenta con el fragmento de memoria principal del cuadro 1, que comienzan
s␣Santos␣del␣Cie
en la dirección lógica 010800H y es un texto de 640 caracteres ASCII, un TLB de
lo␣que␣ayuden␣mi
solo 4 entradas inicializado como indica el cuadro 2 y una caché física
␣pensamiento,␣le
inicializada como indica el cuadro 3.
s␣pido␣en␣este␣m
omento␣que␣voy␣a 1. ¿Cuál es el tamaño en bytes de cada página? ¿En cuántos frames se
␣cantar␣mi␣histo puede dividir como máximo el espacio de direccionamiento físico?
ria␣me␣refresque ¿Cuántas páginas tiene el espacio de direccionamiento lógico?
n␣la␣memoria,␣y␣ 2. ¿En cuántas páginas se dividiría el fragmento de texto? Indique y calcule
aclaren␣mi␣enten qué cambiaría si el texto estuviera codificado en UTF-32, donde cada
dimiento.␣Vengan carácter ocupa 32 bits.
␣Santos␣milagros
3. Explique cuál es la semántica del bit U en esta caché y qué indica.
os,␣vengan␣todos
␣en␣mi␣ayuda,␣qu 4. Indique los valores finales de los registros y explique qué cambios
e␣la␣lengua␣se␣m ocurren en la memoria y en la caché al ejecutar la siguiente secuencia de
e␣añuda␣y␣se␣me␣ instrucciones. Muestre como queda finalmente la caché.
turba␣la␣vista;␣ ▪ R1 ← Mem[010802H]
pido␣a␣mi␣Dios␣q ▪ R2 ← Mem[010822H]
ue␣me␣asista␣en␣
▪ Mem[010845H] ← “%”
esta␣ocasión␣tan
␣ruda.␣Yo␣he␣vis ▪ Mem[010913H] ← “$”
to␣muchos␣cantor ▪ Mem[010983H] ← “&”
es,␣con␣famas␣bi ▪ R3 ← Mem[0108D2]
en␣obtenidas,␣y␣
▪ R4 ← Mem[010953]
que␣después␣de␣a
lquiridas␣no␣las ▪ R5 ← Mem[0109E3]
␣quieren␣sustent 5. Indique qué ocurre si se accede a la dirección 010A4F
ar-:␣parece␣que␣
6. Si los accesos a memoria caché exitosos (o determinar que hay un fallo)
sin␣largar␣se␣ca
demoran 1 ciclo y los accesos a memoria principal para leer o escribir un
nsaron␣en␣partid
bloque demandan 100 ciclos, ¿cuánto demora la etapa Memory en cada
as.␣␣␣␣␣␣␣␣␣␣␣␣␣
una de las instrucciones anteriores?
Cuadro 1
idx Tag 0 V Data 0 (32 bytes ASCII) D Tag 1 V Data 1 (32 bytes ASCII) D U
Aquí␣me␣pongo␣a␣ a␣ vista;␣pido␣a␣
ria_me_refresque 0108H 14H 1b
0 0508 1b cantar␣al␣compás 0b 3278 0
1b
mi ␣Dios␣que␣me␣ 1b 1b
1 0
n_l$_memoria,_y_
Mas ␣ande␣otro␣cr ␣de␣la␣vigüela,␣ 0109H B1H 0b
_de_la_viguela,_
1 0508 10b iollo␣pasa␣Martí 0b 7508 1b que␣el␣hombre␣qu 0b 1
0b
que_el_hombre_qu
010AH A1H 0b
ee_lo_desvela_una
␣lo␣%desvela␣una ␣Santos␣milagros
2 772 pena␣estraordin 0
05088 10b ␣_pena_estraordin 1b 2748 1b os,␣vengan␣todos 0b 1
0b 0109H 5EH 1b
aria,␣como␣la␣av to␣muchos␣cantor
3 0508 1b e␣solitaria␣con␣ 0b 2758 1b es,␣con␣mañas␣bi 1b 1b Cuadro 2
Cuadro 3
3
Ejercicio 3.
Dada una matriz cuadrada A de NxN enteros, donde N = 32 y los enteros ocupan 4 bytes. El primer índice representa
filas, el segundo columnas y ambas se numeran de 0 a N-1. La matriz se encuentra almacenada en memoria siguiendo
un orden row-major, es decir el elemento A[i][j] se encuentra en la posición de memoria: dirección_base_de_A + (i * N
+ j) * tamaño_elemento.
a) Asumiendo que la dirección base de la matriz A es 0410 H, ¿cuál es la dirección base de la segunda fila? ¿cuál
es la dirección de la componente A[N-1][N-1] de la matriz?
Asumiendo que se tienen direcciones de memoria física de 16 bits y caché física de 512 Bytes para datos, implementada
con mapeo directo y líneas de 32 Bytes.
b) Indique cómo se divide la dirección física para acceder a la caché y qué cantidad de bits tiene cada parte.
c) Indique en cuántos bloques se divide la matriz, cuál es la dirección base de cada bloque (al menos para las
primeras 4 filas) y cuál es el index de caché asociado a cada uno.
Hay dos posibles recorridos de la matriz que resuelven un problema particular:
(Recorrido 1) (Recorrido 2)
Asumiendo que al comenzar con cada recorrido en la caché de datos no hay nada útil y que operar con los índices
involucrados en el recorrido no implica accesos a memoria porque están almacenados en registros.
d) Para cada recorrido ¿cuántos fallos ocurrieron por acceso a datos? ¿cuál fue la tasa de fallos?
e) Del total de fallos, ¿cuál es el porcentaje de fallos compulsivos?
f) ¿Cuál de los dos recorridos es más recomendable? Justifique.
g) ¿Qué hubiera ocurrido si la matriz estuviera almacenada en memoria siguiendo un orden column-major, es
decir, si el elemento A[i][j] se encontrara en la posición de memoria dirección_base_de_A + (j * N + i) *
tamaño_elemento?
Ejercicio 4.
Dadas dos matrices cuadradas A y B que contienen 1024 enteros cada una y cada entero es de 4 bytes. El primer
elemento de A (A[0,0]) está almacenado en la dirección física 0000 4020 H y el primer elemento de B en la dirección
física 0001 0800H.
El sistema tiene una caché de 4KB para datos, organizada en mapeo directo con líneas de 16 bytes y política de
escritura write through - write allocate.
a. ¿Cuántas líneas hay en la caché?
b. ¿En qué campos y de qué cantidad de bits cada uno se divide la dirección física para acceder a la caché?
[Link] en cuántos bloques se dividen las matrices y qué set le corresponde a cada uno.
Si inicialmente todas las entradas de la caché están marcadas como inválidas y durante la ejecución del siguiente código
solamente A y B se almacenan en la caché porque i y j se almacenan en registros.
for (i = 0; i < 32; i++) {
4
for (j=0; j < 32; j++) {
A[i,j] = i+j;
B[j,i] = B[j,i] + A[i,j];
}
}
d. ¿Cuántos fallos de lectura y de escritura ocurren? ¿Ese valor hubiera variado si la caché, manteniendo la
capacidad para datos, hubiera estado organizada con un grado de asociatividad 2?
e. ¿Cuántos bytes se escribieron en memoria principal?
Ejercicio 5.
Supongamos dos microarquitecturas M1 y M2 del mismo set de instrucciones, con los siguientes CPI.
Operations M1 M2
Load–store 1 2
ALU 2 2
Branches 3 2
Nos interesa analizar el tiempo de ejecución de dos programas A y B, que tienen la siguiente proporción de cada
instrucción:
Operations A B
Load–store 20% 50%
ALU 50% 30%
Branches 30% 20%
a) Si la frecuencia del reloj de M1 es 2 GHz. ¿Cuál debería ser la frecuencia del reloj de M2 para que el programa
A tenga el mismo tiempo de ejecución en M1 que en M2? ¿Y para que ocurra eso con el programa B? ¿A qué
conclusión puede llegar en función de los resultados obtenidos?
b) Supongamos que la frecuencia del reloj de M1 y M2 es la misma, ambos programas tiene la misma cantidad de
instrucciones y para realizar determinada tarea encontramos un algoritmo que requiere ejecutar A y B la misma
cantidad de veces ¿qué microarquitectura va a ser más rápida?
c) ¿Cuál debería haber sido la relación entre la cantidad de ejecuciones de A y la cantidad de B para que en el
inciso anterior el resultado fuera que son igual de rápidas?
Ejercicio 6.
Estás diseñando un sistema de memoria virtual que usa una tabla de páginas de un único nivel implementada en
hardware dedicado (una memoria SRAM y la lógica asociada). Soporta direcciones virtuales de 25 bits, direcciones
físicas de 22 bits y páginas de 2 16 bytes. Cada entrada de la tabla de páginas contiene el número de frame, el bit de
válido y el bit de dirty.
a) ¿Cuál es el tamaño total en bits de la tabla de páginas?
b) El equipo que diseña el sistema optativo propone reducir el tamaño de la página a 16KB, pero los integrantes
del equipo que diseña el hardware (tu equipo) lo rechazan basándose en el costo del hardware adicional.
Explica el porqué de tal objeción.
c) La tabla de páginas va a ser integrada en el chip del procesador, junto con la caché (que soporta solo
direcciones físicas, no virtuales). Para un dado acceso a memoria, ¿es posible acceder el set correcto en la
5
caché concurrentemente con el acceso a la tabla de páginas? Explique qué debe ocurrir para que esto sea
posible.
d) Para un dado acceso a memoria, ¿es posible realizar la comparación del tag en la caché concurrentemente con
el acceso a la tabla de páginas? Explique qué debe ocurrir para que esto sea posible.
Ejercicio 7.
Supongamos que sos parte del equipo de diseño de una máquina. Ya está decidido que el sistema podrá direccionar un
espacio virtual de 232 bytes dividido en páginas de 4KiB. El espacio en disco no es un problema, pero el hardware
limita la memoria RAM a un máximo de 8MiB.
a) ¿Cuántos bits tiene la dirección física?
b) ¿En cuántas páginas se divide el espacio virtual?
c) ¿Cuál es el máximo número de frames posible?
d) ¿Cuántos bits tiene el número página y el número de frame?
e) Alguien del equipo propone usar un esquema de mapeo directo entre páginas y frames. El mapeo usaría los
últimos bits del número de página para determinar el número de frame. Sorprendentemente, a la mayoría del
equipo le está gustando la idea ¿qué argumentos usarías para convencer al equipo de que esta es una mala idea
y no debe prosperar?
f) Finalmente, se decide usar una tabla de páginas para almacenar ese mapeo. La tabla además del número
de frame debe almacenar 2 bits extras de estado (bit de válido y bit de dirty). ¿Cuál será el tamaño, en cantidad
entera de bytes, de esa tabla?
g) Al calcular el tamaño de la tabla (inciso anterior) el equipo de diseño se encuentra con otro problema. ¿Cuál es
ese problema? Explique la estrategia que propondrías para solucionarlo.
6
Ejercicio 8.
Suponiendo el siguiente escenario:
001040H Liliana␣Bodoc␣LO
S␣DÍAS␣DEL␣VENAD • Direccionamiento al byte.
O␣La␣saga␣de␣los • Memoria virtual con paginado y se necesitan 10 bits para
␣confines␣I␣Pról direccionar dentro de la página.
ogo.␣Ocurrió␣hac
e␣tantas␣Edades␣
• Direcciones físicas de 24 bits y lógicas de 32 bits.
que␣no␣queda␣de␣ • Memoria caché física, con 8 líneas de datos y una capacidad
ella␣ni␣el␣eco␣d total de 256 bytes de datos. La organización de la caché es 2-
el␣recuerdo␣del␣ way set associative, reemplazo FIFO y política de escritura
eco␣del␣recuerdo writeback – write allocate.
.␣Ningún␣vestigi • La primera letra del fragmento de texto se encuentra en la
o␣sobre␣estos␣su dirección de memoria física 001040H
cesos␣ha␣consegu
ido␣permanecer.␣ a) ¿Cuál es el tamaño en bytes de cada página? ¿Cuántos
Y␣aún␣cuando␣pud frames ocupa el fragmento de texto? (considerando la
ieran␣adentrarse dirección física en la que empieza y que, incluyendo todos
␣en␣cuevas␣sepul los espacios marcados , tiene 720 caracteres ASCII).
tadas␣bajo␣nueva
s␣civilizaciones b) En el reemplazo FIFO se reemplaza aquella línea de caché
,␣nada␣encontrar que hace más tiempo que está en la caché. Describa qué
ían.␣Lo␣que␣voy␣ información debe almacenarse en cada set de la caché y
a␣relatar␣sucedi cuántos bits hacen falta. ¿Cuál es el tamaño real de la
ó␣en␣un␣tiempo␣l caché?
ejanísimo;␣cuand c) Asumiendo que en la caché no hay nada útil y que se
o␣los␣continente accede secuencialmente para lectura a las siguientes
s␣tenían␣otra␣fo direcciones de memoria:
rma␣y␣los␣ríos␣t 0010C3H – 001181H – 001262H – 0011F4H –
enían␣otro␣curso 001189H – 001270H – 0010FAH – 0010DBH –
.␣Entonces,␣las␣ 0010DCH – 001144H – 0012C0H – 0010DDH
horas␣de␣las␣Cri c.i. Para cada acceso indique el index y el tag de la
aturas␣pasaban␣l dirección, si ocurre un hit o un miss y en, el caso de
entas,␣los␣Brujo miss, detalle los cambios que ocurren en la caché.
s␣de␣la␣Tierra␣r
ecorrían␣las␣mon
[Link]. Muestre el contenido final de la caché (incluyendo
tañas␣Maduinas␣b
datos).
uscando␣hierbas␣
salutíferas,␣y␣t
odavía␣resultaba
␣sencillo␣ver␣a␣
los␣lulus,␣en␣la
s␣largas␣noches␣
de␣las␣islas␣del
␣sur,␣bailando␣a
lrededor␣de␣sus␣
colas.␣␣␣␣␣␣␣␣␣␣
