Un simulado de memo ias cache mul ini el.
Rica do Almisas, Ra ael Paz, Alejand o Lina es, Claudio Amaya, José Luis
Se illano(*).
Facul ad de In o má ica. Uni e sidad de Se illa.
A da. Reina Me cedes, s/n. 41012, Se illa.
e-mail: (*)
[email p o ec ed]
Resumen
En es e abajo, se desc ibe un simulado g á ico
denominado Simula Cache 1.0, que acili a la
ealización de p ác icas sob e je a quía de
memo ia en cu sos de a qui ec u a y es uc u a de
compu ado es. Es á inspi ado en el conocido
Dine o III [1], aunque diseñado pa a un en o no
W9x-NT, con una in e az g á ica muy in ui i a y
ácil de u iliza . Además, incluye algunas
ca ac e ís icas a anzadas (has a es ni eles de
cache, p ebúsqueda, subbloques, e c.) así como
pa áme os no malmen e no incluidos en o os
simulado es. Po ello, puede ambién se ú il pa a
e aluación de sis emas ealis as o como
alidación de modelos de p es aciones.
1. In oducción
Aunque exis e un buen núme o de simulado es de
caches y je a quías de memo ia [2-9], es di ícil
encon a uno que cub a odos los aspec os
eque idos. En gene al, pa ecen exis i dos
ap oximaciones di e en es. Po un lado,
simulado es o ien ados a la docencia de los
concep os undamen ales, a la ilus ación del
uncionamien o in e no y al e ec o de pa áme os
básicos de diseño. Es os simulado es suelen ene
una in e az de usua io g á ica, sencilla de u iliza ,
pe o ienen como limi aciones undamen ales el
hecho de que no admi en con igu aciones
complejas ( ípicamen e es án limi ados a un solo
ni el de cache, po ejemplo) y que los esul ados
o ecidos suelen educi se al miss a e ( azón de
allos) de un conjun o de accesos. Es o es lógico,
pues o que es a ían especialmen e indicados pa a
asigna u as in oduc o ias o básicas, en las que
inclui más de alles o con igu aciones complejas
esul a casi con ap oducen e. En e ec o, eso
eque i ía dedica mucho iempo de aula en
asigna u as en las que el es udio de la je a quía de
memo ia debe se necesa iamen e b e e. Ejemplos
de es e ipo de simulado es se ían VC [7]
(ejecu ado en una página Web), Visual Cache,
diseñado en nues o g upo [6], CVT [4] (aunque
es e simulado es bas an e más ambicioso), y o os
[5,8].
En el o o ex emo es a ían simulado es que
aunque ambién pueden se usados como
he amien a docen e, ienen una se ie de
ca ac e ís icas que los hacen más adecuados al
es udio de aspec os más a anzados o incluso pa a
la ealización de pequeños p oyec os de
in es igación. En la mayo ía de es os simulado es,
la in e az con el usua io suele se pob e,
no malmen e equi iendo da la con igu ación en
línea de comandos o en iche os. Es e es el caso
del popula Dine o III [1], y su e sión más
ecien e Dine o IV [3], el A gen Cache Simula o
[2], Acme [9], e c.
El simulado p esen ado aquí, denominado
SimulaCache1.0, p e ende si ua se en un pun o
in e medio en e es os dos ex emos. Man iene
una in e az de usua io g á ica e in ui i a que
pe mi i ía su uso en p ác icas sin demasiado
es ue zo po pa e de los alumnos, pe o incluye
ambién algunas ca ac e ís icas (como caches
mul ini el), que pe mi i ían su uso en digamos
es udios más a anzados como el compo amien o
de sis emas eales an e aplicaciones eales,
alidación de modelos de p es aciones, e c. Es as
ca ac e ís icas se án desc i as con más de alle en
las siguien es secciones.
2. Fo ma o de azas.
La p ime a decisión a la ho a de diseña un
simulado de je a quías de memo ia es la elección
del o ma o de las azas. En e ec o, la inmensa
mayo ía de los simulado es son ace-d i en [13],
430 Demos
es deci , la en ada del simulado es un iche o de
azas de memo ia, cuyos egis os poseen
in o mación e e en e a la di ección de memo ia
accedida po el p ocesado , al ipo de acceso del
que se a a (lec u a o en esc i u a) y el ipo de
in o mación al que se es á accediendo (Da os o
Ins ucciones). Es o es lo habi ual en los es udios
de p es aciones de sis emas de memo ia. No
in e esa que la en ada de da os sea código
máquina, que necesa iamen e es dependien e del
p ocesado , ni código de al o ni el, donde es
di ícil aisla los accesos al sis ema de memo ia
(aunque po ejemplo CVT [4] pe mi e simula
pequeños bucles en Fo an).
Sin emba go, la longi ud de los iche os de azas
es mucho mayo que la del código uen e o iginal,
pues en los iche os de azas de memo ia los
bucles se “desen ollan”. Además, en sis emas
ealis as (y po an o complejos), pa a ob ene
es adís icas iables deben simula se millones de
e e encias a memo ia, necesi ando cada una de
ellas has a 10 by es, lo que nos lle a a iche os del
o den de decenas de megaby es [10]. Muchos de
los es ue zos en in es igación an o ien ados a
desa olla écnicas pa a supe a es e p oblema,
como la comp esión [10] o el mues eo es adís ico
de los iche os de azas [11].
Sin emba go en nues o caso las azas deben se
en lo posible au oexplica i as. Es deci , si se
p e ende su uso docen e, un simple is azo de la
aza debe da una idea de los accesos que se es án
ealizando en de e minados pun os del p og ama,
sob e odo si in e esa comp oba el
uncionamien o en de e minados pun os de la
aza. Es o impide usa o ma os comp imidos
como PDATS. O o o ma o muy ex endido,
ETCH [12] usa códigos numé icos e incluye casos
a anzados como accesos múl iples.
Pa a es e caso, no hemos op ado po un o ma o
único, sino que man enemos es posibles
o ma os, pe mi iendo la aducción de uno a o o.
Todos ienen en común que son iche os de ex o
donde cada línea se co esponde con un acceso,
pe mi iendo al alumno iden i ica ácilmen e los
accesos básicos.
2.1.- T azas DIN.
Es e es el o ma o que econoce el p og ama
Dine o en sus e siones e ce a y cua a [1,3].
Es á compues o po dos campos. El p ime campo
es á o mado po un ca ác e que indica el ipo de
acceso a la memo ia caché. El segundo campo
indica la di ección del acceso y se p esen a en
o ma o hexadecimal, con la opción de ene como
p e ijo “0x”, siendo de longi ud máxima de 32
bi s. En el caso de que ue a meno de 32 bi s se le
añadi ían ce os a la izquie da.
Los di e en es ca ac e es que pe mi e es e o ma o
pa a indica el ipo de acceso son:
• 0 : lec u a de da os en la caché.
• 1: esc i u a de da os en la caché.
• 2: lec u a de ins ucciones en la caché.
• 3: misc, lec u a de da os en la caché que no
gene a p ebúsquedas (en caso de se posible).
• 4: in alida una posición de la caché.
• 5: copyback, ealiza una esc i u a en el
siguien e ni el de memo ia si la posición
e e enciada es u ie a “sucia”.
En cuan o al amaño de los accesos que se ealizan
a memo ia siemp e son de 4 by es.
2.2.- T azas X-DIN.
Es e o ma o, usado po el p og ama Dine o IV
[3], es una ex ensión del o ma o an e io . La
p incipal di e encia es que en és e el amaño del
acceso es á indicado exp esamen e como un
campo más. Así, enemos es campos, el p ime o
es á compues o po un ca ác e e indica el ipo de
acceso a la memo ia caché que se ealiza. El
segundo campo indica la di ección del acceso y
es a á en o ma o hexadecimal, con la opción de
ene como p e ijo “0x”, y se á de longi ud
máxima de 32 bi s. En el caso de que ue a meno
de 32 bi s se le añadi ían ce os a la izquie da. El
e ce campo indica el amaño del acceso en by es,
es e campo es a á en o ma o hexadecimal.
También puede ene con ca ác e opcional el
p e ijo “0x”.
Los di e en es ipos de acceso que pe mi e indica
es e o ma o son: R (lec u a), W (esc i u a), I
(ins ucción), M (misc), V (in alidación) y C
(copyback), equi alen es a los accesos DIN 0, 1,
2, 3, 4 y 5, espec i amen e.
2.3 T azas Visual Caché 1.0.
Po úl imo, ambién se pe mi e el uso de un
o ma o de azas u ilizado po o o simulado
diseñado en nues o g upo, denominado Visual
Cache [6], y que es á o ien ado undamen almen e
Demos 431
a la ilus ación del p oceso in e no que iene luga
en caches sencillas. Aquí no in e esa an o el
esul ado es adís ico inal como la isualización
de la e olución paso a paso de la ejecución de una
aza, po lo que es más impo an e si cabe que la
aza sea muy ácil de en ende . Los campos son:
• Un ca ác e indica i o del ipo de acceso que
se es á ealizando (L
‡
Lec u a o W
‡
Esc i u a).
• Un campo con la di ección e e enciada (en
hexadecimal, 8 dígi os).
• Un ca ác e indica i o de si el acceso es a un
da o o a una ins ucción (D
‡
Da o o I
‡
Ins ucción).
• Finalmen e, un campo de 2 dígi os decimales
con el amaño del da o accedido en by es.
Po ejemplo, L 0x00000FF0 I 04. Es e o ma o de
azas puede conside a se como un subconjun o de
o ma os más complejos.
En ealidad es os o ma os son simila es, lo que
pe mi e una aducción muy sencilla. Nues a
aplicación pe mi e la aducción de azas de un
o ma o a o o (con las limi aciones lógicas).
3. Ca ac e ís icas simuladas.
El simulado incluye po supues o odas las
ca ac e ís icas habi uales en cualquie simulado
de cache: amaño de la cache, núme o de palab as
po bloque, modo de ubicación de los da os
(Co espondencia Di ec a, Po ías o To almen e
asocia i a), ipo de esc i u a (Copy Back o W i e
Th ough), modo de ubicación de la esc i u a
(W i e Alloca e o No W i e Alloca e), p ime
ni el de caché uni icada o sepa ada pa a da os e
ins ucciones y algo i mo de eemplazo (LRU,
FIFO o Alea o io) cuando exis e asocia i idad.
Pe o además de es os pa áme os básicos, se
incluyen o os que pe mi en su u ilización po
ejemplo en cu sos más a anzados, como:
• has a es ni eles de caché en la je a quía de
memo ia, siendo cada uno de ellos con igu able
independien emen e.
• pe mi e di idi los bloques de caché en
subbloques.
• pe mi e ealiza p ebúsquedas de bloques o
subbloques, dependiendo de si se ha elegido
di idi los bloques en subbloques o no.
Pudiéndose con igu a las p ebúsquedas pa a
ealiza se siemp e que se simule un acceso de ipo
ins ucción o de lec u a de da os, o pa a que se
ealiza an las p ebúsquedas sólo en el caso de que
ocu iese un allo en el acceso pa a los ipos de
accesos an e io men e comen ados.
• pe mi e con igu a el amaño, en bi s, de la
palab a que usa á el sis ema de memo ia du an e
la simulación.
• pe mi e con igu a el ancho de los buses de
memo ia que comunican a cada ni el de cache
con su ni el inmedia amen e in e io .
Todas es as ca ac e ís icas pueden con igu a se
median e en anas in e ac i as ( e igu a 1),
pudiéndose ambién almacena en iche os
(.CFG), lo que posibili a dispone de una especie
de “lib e ía de o ganizaciones de cache” de
sis emas eales.
4. Resul ados.
En lo que espec a a los esul ados que o ece es a
aplicación as la simulación, end íamos:
• el núme o de accesos o ales y po ipo de
acceso, con sus espec i os po cen ajes.
• el núme o de allos o ales y po ipo de
acceso, con sus espec i os po cen ajes.
• el núme o de by es leídos en el siguien e
ni el y el núme o de by es esc i os en el siguien e
ni el.
• el núme o de by es que deben se esc i os en
el siguien e ni el al e mina la simulación y su
po cen aje espec o al núme o o al de by es
esc i os en el siguien e ni el.
el núme o de by es medio esc i os en el siguien e
ni el po cada acceso de ipo esc i u a simulado.
También han sido añadidos una se ie de esul ados
que se han conside ado in e esan es, y que no son
habi uales en o os simulado es de la li e a u a.
Uno de los mo i os ha sido que el simulado ha
sido usado como alidación de modelos analí icos
simples sob e memo ias cache desa ollados po
nues o g upo [14]. Algunos de es os pa áme os
son:
• el núme o de accesos de más simulados,
dis inguiendo los que hayan sido mo i ados po
accesos desalineados o po que el ancho del bus no
podía accede en un solo acceso a odos los da os
eque idos en un momen o dado.
• el núme o medio de lec u as y esc i u as
ealizados po cada bloque o subbloque de la
caché, dependiendo de si la caché simulada
u ie a los bloques di ididos en subbloques o no,
432 Demos
en elación al núme o o al de bloques o
subbloques ( ambién se p opo ciona, a modo de
in o mación, el núme o de bloques o subbloques
o al).
• el núme o medio de lec u as y esc i u as
ealizados po cada bloque o subbloque de la
caché en elación al núme o de bloques o
subbloques a los que se ha accedido du an e la
simulación ( ambién se p opo ciona es e núme o
de bloques o subbloques o al).
A los iche os de aza que son ca gados en una
en ana se les pod á asigna pun os de co e
(b eakpoin s), pa a los cuales se mues an los
esul ados de la simulación has a ese momen o,
además, cla o es á, de mos a los esul ados
ob enidos al inal de la simulación.
Finalmen e, es á la pa e de compa a i as de los
esul ados ob enidos. Si los esul ados mos ados
al inal de cualquie simulación son gua dados en
un a chi o (.RST), después es os a chi os pod án
se u ilizados pa a ealiza compa a i as de
esul ados en e ellos. Pa a ello, se pe mi e elegi
qué iche os de esul ados se desean mos a en la
compa a i a y cuáles se án compa ados. Además
puede elegi se qué pa áme os se desean compa a
( e igu a 2). El núme o o al de pa áme os que
o ece el simulado es g ande, y a menudo sólo
in e esan unos pocos en conc e o, po lo que no
iene mucho sen ido p esen a odos po de ec o.
T as es o la aplicación mues a una abla, en la
que po columna se pueden e los esul ados de
cada iche o y po ilas se pod án compa a los
esul ados de unos iche os con o os ( igu a 3).
5. Conclusión
En es e abajo se ha desc i o un simulado que
pe mi e e alua el compo amien o de un sis ema
de memo ias cache an e la ejecución de
de e minadas azas de memo ia. Se admi en es
o ma os de aza, pudiéndose aduci iche os de
un o ma o a o o. Las ca ac e ís icas simuladas
incluyen aspec os a anzados como pueden se
a ios ni eles de cache (has a es), p ebúsquedas,
sub-bloques, e c. Las con igu aciones pueden
edi a se median e en anas in e ac i as, y sal a se
como iche o. Como esul ado de la simulación, se
o ece un buen núme o de pa áme os que pueden
se sal ados, edi ados e incluso compa ados desde
la p opia aplicación. El p og ama es á esc i o
usando Visual Basic, y se ejecu a bajo Windows
9x o NT.
Re e encias
[1] J.L. Hennessy, D.A. Pa e son “Compu e
A chi ec u e: A Quan i a i e App oach” (2ª Ed.).
Mo gan Kau mann, 1996.
[2]
h p://papi.ee.duke.edu/a gen /a gen .h m
.
[3]
h p://www.neci.nj.nec.com/homepages/edle /d
4/
[4] E. Deijl, G. Kanbie , O. Temam, E.D.
G ans on, “A Cache Visualiza ion Tool”.
Compu e , ol. 30, no. 7, July 1997.
[5] R.N. Ibbe , Compu e a chi ec u e
isualisa ion echniques, Mic op ocesso s and
Mic osys ems 23-5 (1999) 291-300
[6] M.A. Rod íguez e al. “Un simulado g á ico
pa a la enseñanza de memo ias cache”. IV
Cong eso sob e Tecnologías aplicadas a la
Enseñanza de la Elec ónica. Ba celona,
Sep iemb e de 2000.
[7]
h p://www.cc.ga ech.edu/ ac/Bill.Leahy/ csa/
cs.h ml
[8]
h p://www.ece.ga ech.edu/ esea ch/labs/ e en
g/cachesim/
[9]
h p://a anaso .nmsu.edu/~acme/acs.h ml
.
[10] E.E. Johnson, J. Ha, “PDATS: Lossless
Add ess T ace Comp ession o Reducing File
Size and Access Time”. P oc. IEEE In . Phoenix
Con . Comp. and Commun., 1994.
[11] T.M. Con e, M.A. Hi sch, W.W. Hwu,
“Combining T ace Sampling wi h Single Pass
Me hods o E icien Cache Simula ion”. IEEE
T ans. Comp., ol. 47, no. 6, June 1998.
[12]
h p://memsys.cs.washing on.edu/memsys/h
ml/e ch.h ml
.
[13] R.A. Uhlig, T.N. Mudge, T ace-D i en
Memo y Simula ion: A Su ey, ACM Compu ing
Su eys, 29-2 (1997) 129-170.
[14] F. Díaz e al. “A Dynamic Equilib ium based
Model o Caches”. En p oceso de e isión pa a
Mic op ocesso s and Mic osys ems.