2021
112
Alba Ped o Zapa e
Apo aciones al modelado
del cálculo del WCET en
en o nos de memo ia
cache
Di ec o /es
Sega a Flo , Juan
Rod íguez La uen e, Clemen e
© Uni e sidad de Za agoza
Se icio de Publicaciones
ISSN 2254-7606
Alba Ped o Zapa e
APORTACIONES AL MODELADO DEL CÁLCULO
DEL WCET EN ENTORNOS DE MEMORIA CACHE
Di ec o /es
Sega a Flo , Juan
Rod íguez La uen e, Clemen e
Tesis Doc o al
Au o
2021
UNIVERSIDAD DE ZARAGOZA
Escuela de Doc o ado
P og ama de Doc o ado en Ingenie ía de Sis emas e In o má ica
Reposi o io de la Uni e sidad de Za agoza – Zaguan h p://zaguan.uniza .es
UNIVERSIDAD DE ZARAGOZA
TESIS DOCTORAL
Apo aciones al modelado del cálculo del
WCET en en o nos de memo ia cache
Au o a:
Alba PEDRO ZAPATER
Di ec o es:
D . Juan SEGARRA
D . Clemen e RODRÍGUEZ
Memo ia p esen ada pa a ob ene el í ulo
de Doc o a en in o má ica
en el
G upo de A qui ec u a de Compu ado es de la Uni e sidad de Za agoza
Depa amen o de in o má ica e ingenie ía de sis emas
17 de sep iemb e de 2020

II
«Technology is no neu al. We’ e inside o wha we make, and i ’s inside o us. We’ e li ing
in a wo ld o connec ions — and i ma e s which ones ge made and unmade.»
Donna Ha away
III
UNIVERSIDAD DE ZARAGOZA
Resumen
Apo aciones al modelado del cálculo del WCET en en o nos de memo ia cache
po Alba PEDRO ZAPATER1
Los sis emas de iempo eal cob an cada ez más impo ancia en nume osas á eas.
Pa a log a una buena plani icación de es os sis emas se equie e un análisis p eciso
y segu o del peo caso de iempo de ejecución (WCET) siendo el análisis de la je-
a quía de memo ia uno de los p incipales desa íos. En es e abajo nos cen amos
en mejo a la e iciencia de la je a quía de memo ia en los sis emas de iempo eal
es ic o en cuan o a su p edic ibilidad aunque ambién se conside an o os aspec os
como el consumo ene gé ico.
Es e p opósi o se alcanza educiendo an o la co a del WCET como su iempo de
análisis y es udiando pa ones de acceso a memo ia en a eas ele an es en sis emas
de iempo eal.
Comenzamos analizando el impac o de la cache de ins ucciones en el WCET,
cen ándonos en el mé odo Lock-MS de análisis del WCET. A in de usa es e mé odo
diseñamos el algo i mo necesa io pa a ans o ma el g a o de con ol del lujo del
bina io en una es uc u a en á bol. Es e algo i mo educe el iempo de análisis del
WCET sin pe de p ecisión pa a una cache de ins ucciones bloqueable. P oponemos
una heu ís ica de bloqueo dinámico basada en bucles que aplicada a es e mé odo
pe mi e ob ene el con enido óp imo de cache pa a el WCET en cada una de las
egiones de e minadas po la heu ís ica. Además de educi el WCET, ya que explo a
el euso empo al, ambién educe su iempo de análisis.
A con inuación, ampliamos el es udio del análisis del WCET conside ando las
ins ucciones esul an es de la ec o ización au omá ica. De ec amos que la ec o-
ización del código puede se una buena opción pa a educi de mane a e ec i a el
WCET si és a se lle a a cabo en aquellos bucles que concen an la mayo pa e del
iempo ejecución. Po an o, es con enien e in e i iempo y ecu sos en una buena
ec o ización del código en el con ex o de los sis emas de iempo eal.
Pa a inaliza , cen amos nues o es udio en el impac o de la cache de da os es-
udiando el pa ón de acceso a da os en la ansposición de ma ices y aco ando su
asa ideal de acie os en su e sión iling. De es e es udio ob enemos unas exp esio-
nes con espec o a los pa áme os de cache que ga an izan que se alcanza á la asa
ideal de acie os. Especí icamen e, cuando la dimensión del ile es igual al amaño
de línea de cache la asa ideal de acie os se alcanza con muy pocos conjun os y an
solo dos ías en una cache asocia i a po conjun os. Además, compa amos nues os
esul ados con un algo i mo de la anspues a «indi e en e» a los pa áme os de la
cache (obli ious).
1Es á es ic amen e p ohibido usa , in es iga o desa olla , de mane a di ec a o indi ec a cualquie-
a de las con ibuciones cien í icas de la au o a de es e abajo po cualquie eje ci o o g upo a mado en
el mundo, pa a p opósi os mili a es o pa a cualquie uso en con a de los de echos humanos o de cual-
quie o a especie animal, así como del medio ambien e, a no se que se cuen e con su consen imien o
esc i o o, si no ue a posible, se debe á con a con el consen imien o esc i o de odas las pe sonas del
plane a.
V
Ag adecimien os
Me gus a ía ag adece les a odas las pe sonas que me quie en y me han apoyado
du an e es os años: soy a o unada y son demasiadas pa a nomb a las una a una.
Hay muchos cuidados que no se en sos eniendo odo es e abajo, sin los cuales no
hubie a sido posible llega has a aquí. G acias po eco da me una y o a ez que lo
esencial es in isible a los ojos.
Me gus a ía ag adece a mis di ec o es Juan y Clemen e po odo el abajo, apo -
aciones, consejo y sob e odo paciencia. Habéis sido los pila es que han esis ido
cada empo al al que nos hemos en en ado. G acias ambién a Rubén po odas sus
apo aciones y sob e odo po ene siemp e la pue a abie a pa a mí. E e namen e
ag adecida a Víc o , que además de apo a odo su conocimien o y expe iencia ha
sido un apoyo mo al inc eíble. Muchas g acias po habe c eído en mí y po oda la
escucha.
Po úl imo, me gus a ía ag adece al gaZ su acogida, apoyo y calidad humana
que ya había ecibido cuando an solo e a una alumna. Me sien o muy a o unada
de habe o mado pa e de es e g upo. Y, po supues o, no me puedo ol ida de
mis compañe os doc o andos cuya amis ad es una de las mejo es apo aciones de
es a esis a mi ida. Muchas g acias po odos esos buenos momen os y ambién la
compañia en los no an buenos.
Rein e p e ando a Vi ginia Wool , pa a desa olla abajo in elec ual, además
de un cua o p opio, es imp escindible con a con apoyo económico. Es e abajo
se ha lle ado a cabo g acias a la inanciación ecibida de las siguien es en idades y
p oyec os:
Ayuda pa a la Fo mación del P o eso ado Uni e si a io. FPU14/02463. Minis-
e io de Educación, Cul u a y Depo e. (2015-2020)
Je a quía de memo ia y aplicaciones. TIN2013-46957-C2-1-P, Minis e io de Cien-
cia y Tecnología. (2013-2016)
A qui ec u a y p og amación de compu ado es escalables de al o endimien o
y bajo consumo. TIN2016-76635-C2-1-R, Minis e io de Ciencia y Tecnología.
(2016-2019)
Supe compu ación y Eciencia. Consolide TIN2014-52608-REDC. Minis e io
de Ciencia y Tecnología. (2014-2016)
gaZ. Reconocimien o G upo Consolidado de In es igación (T48,T58_17R), Dipu-
ación Gene al de A agón.
HiPEAC Collabo a ion G an . Eu opean Ne wo k o Excellence on High Pe -
o mance and Embedded A chi ec u e and Compila ion. (2015)
Cons uyendo Eu opa desde A agón. Fondo Eu opeo de Desa ollo Regional
(FEDER) en A agón. (2014-2020)
2Capí ulo 1. In oducción, es ado del a e y obje i os
FIGURA 1.1: Esquema del análisis empo al de sis emas. Figu a o-
mada de [ARS13].
no a o as a eas del sis ema de iempo eal [Ves07]. El análisis de plani icabilidad se
usa pa a p edeci el compo amien o empo al median e p uebas que de e minan
si se cumpli án las es icciones empo ales en iempo de ejecución [Sha+04]. Es e
análisis puede ca ac e iza se median e dis in os ac o es, que incluyen las es iccio-
nes del modelo compu acional (e.g. unip ocesado , independencia de a eas, e c.) y
la cobe u a de las p uebas de plani icabilidad. Las p uebas necesa ias y su icien es
son ideales, pe o pa a muchos modelos son demasiado complejas (NP-di ícil pa a
modelos compu acionales no i iales). Si se abo da el análisis con p uebas su icien-
es pe o no necesa ias suele se más simple, pe o más pesimis a. Si la plani icación
alla, el sis ema debe ediseña se y epe i odos los p ocesos p e ios.
Sea como sea, es imp escindible ga an iza la plani icabilidad an es de la ejecu-
ción del sis ema y, como ya hemos señalado, pa a pode calcula si un sis ema es
plani icable, es imp escindible conoce una co a del WCET pa a cada a ea.
1.1.2. WCET
De e mina una co a supe io del iempo de ejecución, es deci su peo caso, es
imp escindible en el desa ollo y alidación de los sis emas de iempo eal es ic o.
Dados componen es ha dwa e con la encia ija, el WCET de una a ea pod ía calcu-
la se median e el WCET pa cial de cada bloque básico. Sin emba go, pa a mejo a el
endimien o, los p ocesado es ac uales lle an a cabo muchas ope aciones cuya du-
ación es a iable. Esas ope aciones p o ienen de las caches, la segmen ación, los
p edic o es de sal os y o os componen es especula i os [Wil+08]. Aunque las pla a-
o mas o ien adas al endimien o se bene ician de es os componen es, di icul an el
análisis pa a sis emas de iempo eal es ic o.
Ya que el WCET depende de las especi icaciones écnicas del ha dwa e y cómo
in e accionan con la a ea ejecu ada, un WCET conc e o no es álido pa a ningún
o o ha dwa e que no sea el analizado. Po lo an o, un buen mé odo pa a el análisis
del WCET no se á solo aquel que dé una co a lo más ajus ada posible sino ambién
aquel cuyo iempo de análisis sea meno ya que es o puede educi mucho el iempo
necesa io pa a diseña un sis ema de iempo eal.
La igu a 1.1 ilus a el p oblema del análisis del WCET. La cu a in e io ep e-
sen a un subconjun o de ejecuciones medidas. Su mínimo y máximo son el iempo
de ejecución obse ado mínimo y máximo, espec i amen e. La cu a más oscu a,

1.2. Es ado del a e 3
en ol iendo la an e io , ep esen a el iempo de odas las posibles ejecuciones. Su
mínimo co esponde al mejo caso de iempo de ejecución Bes Case Execu ion Ti-
me, BCET) y su máximo al WCET. Resul a impo an e señala que, gene almen e,
cuando hablamos de calcula el WCET hacemos e e encia a calcula la co a más
ap oximada posible al WCET eal.
En gene al, la je a quía de memo ia es el componen e con mayo impac o en el
WCET, an o po su con inuo uncionamien o como po su la encia a iable [Apa+08].
Además, en las caches con encionales la la encia de acceso depende de los accesos
an e io es lo que di icul a ex emadamen e su p edic ibilidad. Según la polí ica de
eemplazo es a dependencia suele implica un mayo iempo de análisis, po ejem-
plo LRU (Leas Recen ly Used, menos usada ecien emen e) o una g an sob es ima-
ción del WCET cuando se ag upan posibles e en os de ejecución al e na i os, po
ejemplo el e ec o domino en Pseudo-LRU (PLRU) [Rei+07].
1.2. Es ado del a e
A con inuación analizamos el es ado del a e que ha sus en ado la base eó ica
de es e abajo.
1.2.1. Mé odos de análisis del WCET
Los mé odos de análisis del WCET deben pe segui an o ajus a su co a lo má-
ximo posible, es deci sob ees imándolo lo mínimo posible, como educi su iempo
de análisis. Podemos di idi los mé odos que encon amos en la bibliog a ía pa a
calcula el WCET en es ipos:
Mé odos es á icos. Es os mé odos usan el código de la a ea jun o con ano aciones
pa a analiza el lujo de con ol, combinándolo con algún modelo (abs ac o)
de la a qui ec u a ha dwa e, pa a ob ene co as empo ales. El obje i o es ob-
ene una co a supe io lo más ajus ada posible al WCET eal. Los mé odos
es á icos o ecen segu idad median e dichas co as, ga an izando que la ejecu-
ción no las excede á. Es os mé odos son complejos po que modela de mane a
p ecisa el ha dwa e es di ícil. Además hay que ene en cuen a que gene a
modelos inco ec os puede p oduci esul ados no segu os (calcula una co a
del WCET meno que el p opio WCET) y modelos mal diseñados pueden p o-
duci esul ados demasiado pesimis as (una co a del WCET muy supe io al
WCET eal).
Mé odos basados en medidas. Es os mé odos ejecu an la a ea o pa es de ella en el
ha dwa e inal o en un simulado pa a un conjun o amplio de en adas. A pa -
i de los iempos medidos, de i an el iempo máximo de ejecución obse ado
o su dis ibución, o combinan los iempos medidos en dis in os agmen os de
código pa a in e i el WCET de la a ea comple a. Es os mé odos no son segu-
os, ya que no puede ga an iza se que el peo caso haya sido obse ado. No
obs an e, se conside an menos complejos y menos p opensos a e o es.
Mé odos p obabilís icos. Es os mé odos usan eo ía de p obabilidades pa a conse-
gui una dis ibución p obabilís ica del WCET es imado [Caz+13]. Aunque no
pueden ga an iza la segu idad, pueden es ima el WCET pa a una p obabili-
dad de insegu idad dada. Po ejemplo, es ima el WCET con una p obabilidad
de insegu idad meno que la p obabilidad de allo de ha dwa e. La p incipal
4Capí ulo 1. In oducción, es ado del a e y obje i os
FIGURA 1.2: Dis ibución del iempo de ejecución pa a a qui ec u as
de e minis as con encionales y una p opues a de a qui ec u a alea o-
izada en el iempo, supe pues as con la dis ibución p obabilís ica de
peo caso en sis emas de iempo eal analizables p obabilís icamen e
(P obabilis ically Analyzable Real-Time Sys ems, PROARTIS), mos an-
do la sob eca ga de la alea o ización (a), la posible localización del
WCET exac o (b), y las co as del WCET conside adas (c). Figu a o-
mada de [Caz+13].
des en aja de es os mé odos es que la eo ía p obabilís ica solo puede aplica -
se en ha dwa e/so wa e no de e minis a, i.e. con compo amien o alea o io.
Ob iamen e, an o el ha dwa e como el so wa e son de e minis as, así que
es os mé odos equie en ha dwa e alea o io (in es igado ac ualmen e de ma-
ne a ac i a) y el código a analiza iene que se alea o izado con espec o al
iempo. Incluso asumiendo co as p ecisas del WCET, eque i alea o iedad en
el sis ema puede inc emen a a i icialmen e es as co as, dando como esul a-
do sis emas ine icien es. Encon amos un ejemplo en la igu a 1.2 que ilus a la
di e encia en e el iempo de ejecución en una a qui ec u a de e minis a y una
alea o izada.
En es e abajo nos cen amos en los mé odos es á icos ya que son los únicos que
nos pe mi en calcula un co a segu a del WCET. En la igu a 1.3 encon amos un
esquema de una he amien a de análisis empo al que implemen a un mé odo es á-
ico. Podemos e que el análisis del WCET incluye no malmen e es pasos: análisis
del lujo que consis e básicamen e en iden i ica los caminos (im)posibles y aco a los
bucles; el análisis de bajo ni el que p e ende de e mina los e ec os globales de la a -
qui ec u a en los iempos de ejecución y calcula el peo caso de iempo de ejecución
de los agmen os de código; inalmen e, el esul ado de los dos análisis an e io es
se combina pa a calcula el WCET en conjun o.
Podemos usa un mé odo es á ico di e en e pa a cada una de es as ases, e inclu-
so pa a sis emas muy simples pod ía no desa olla se alguna de es as ases explíci-
amen e. O a o ma de isualiza lo es que lo p ime o que necesi amos es ex ae la
in o mación del lujo de con ol, pa a gene a un modelo ma emá ico que inalmen e
podamos esol e ob eniendo el WCET. Veamos algunos ejemplos de mé odos que
se usan pa a la ex acción de la in o mación:
Abs ac In e p e a ion (AbsIn ): AbsIn es un conocido modelo ma emá ico
que aplicado a los mé odos de análisis es á icos consis e en pa i de un es a-
do abs ac o y analiza cómo a e olucionando a lo la go de dis in os pun os
1.2. Es ado del a e 5
FIGURA 1.3: Los p incipales componen es de una he amien a de
análisis empo al que implemen a el mé odo es á ico. El lujo de in-
o mación se mues a a a és de las lechas g ises. Las lechas blan-
cas ep esen an las en adas que cons uyen la he amien a. Imagen
omada de [Wil+08].
del p og ama. Una de las inalidades de los mé odos que aplican AbsIn es
analiza los accesos a la cache de da os [The+03]. En es os casos los es ados
abs ac os ep esen a án el es ado de la cache de da os en cada pun o del p o-
g ama. También puede aplica se pa a de e mina el es ado de la cache de ins-
ucciones [FW99]. Adicionalmen e exis en mé odos basados en AbsIn que se
aplican al análisis del lujo de con ol [Gus00]. En es e caso los es ados abs ac-
os se án los p opios caminos en cada pun o del código analizado. Finalmen e,
AbsIn puede aplica se al análisis de lujo de da os calculando in a ian es del
es ado de ejecución del p ocesado en cada pun o del p og ama [CC77].
Conco dancia de pa ones: Es os mé odos se aplican al análisis de pa ones de
los bucles y se basan en que la mayo ía de es os usan las mismas ins ucciones,
o simila es, pa a la inicialización, ac ualización o comp obación de los con a-
do es de bucle [Gus+03].
Una ez ob enemos es a in o mación, el modelo ma emá ico que se gene a y que
pe mi i á calcula el WCET en conjun o puede cons ui se a pa i de los siguien es
mé odos:
Basados en la es uc u a: Aco an el iempo de ejecución a pa i de un eco i-
do de abajo hacia a iba del á bol de la a ea. Es e á bol se cons uye a pa i
del g a o de con ol del lujo (Con ol G aph Flow, CFG). En es e p ocedimien o,
conjun os de nodos se usionan en un único nodo, del que se calcula su co a
empo al a pa i de los nodos que lo componen has a educi odo el á bol en
un único nodo con el WCET inal [CP00;CB02;Lim+95]. Sin emba go, no odos
los lujos de con ol pueden exp esa se como es uc u as en á bol. O o de sus
p incipales incon enien es su ge cuando usamos sis emas con caches con en-
cionales ya que no ole a su p opio compo amien o dependien e del con ex o.
No obs an e, es a p opues a es p obablemen e la más ápida [Wil+08], po lo
que, pa a cie os obje i os, los mé odos basados en la es uc u a con mejo as
son los más adecuados.
Basados en el eco ido: El iempo de ejecución pa a una a ea se de e mina cal-
culando las co as de cada camino, buscando cuál es el de mayo iempo de eje-
cución en e odos ellos [SA00;SEE01;Hea+99]. Es o implica que los posibles
6Capí ulo 1. In oducción, es ado del a e y obje i os
caminos de ejecución deben se ep esen ados explíci amen e, con el co es-
pondien e cos e en la explosión combina o ia de és os al aumen a su núme o
exponencialmen e con espec o al núme o de pun os de bi u cación.
Técnica de enume ación implíci a de caminos (Implici Pa h Enume a ion Tech-
nique, IPET): el lujo del p og ama y las co as de iempo de ejecución de los blo-
ques básicos se combinan en un conjun o de es icciones [LM95], bien a a és
de écnicas de p og amación lineal en e a (In ege Linea P og amming, ILP) o
p og amación de es icciones. El núme o de es icciones iene una comple-
jidad exponencial al amaño de la a ea y aumen a con las es icciones que
p o ienen de los da os de lujo.
Un mé odo es á ico que pod ía sus i ui odo lo an e io se ía la Simulación Sim-
bólica donde la ejecución de la a ea es simulada en un modelo abs ac o del p o-
cesado . Es a simulación se lle a a cabo sin ninguna en ada lo que conlle a que el
simulado debe se capaz de maneja es ados pa cialmen e desconocidos. Po lo an-
o, es e mé odo combina el análisis del lujo, la p edicción del compo amien o del
p ocesado y el calculo de la co a del WCET en una sola ase in eg ada [Lun02].
1.2.2. A qui ec u as ha dwa e
Las a qui ec u as ha dwa e son un ema abie o en los sis emas de iempo eal.
Se ha in e ido mucho es ue zo pa a pode usa de o ma segu a el ha dwa e a-
dicional de p opósi o gene al. Po ejemplo, ARM o ece una se ie Co ex pa a sis-
emas de iempo eal (R-se ies) [Limb], incluida en la a qui ec u a Xilinx Ul aScale
MPSoC [Xil]. También la se ie LEON (o iginalmen e diseñada po la Agencia Espacial
Eu opea basada en el SPARC V8) da sopo e a muchos sis emas ope a i os de iem-
po eal. Sin emba go, su al a de especi icaciones es ic as de la encia sugie e que
debe ían desa olla se nue os diseños más p edecibles.
En conc e o, la je a quía de memo ia es, como ya hemos indicado, uno de los
pun os c í icos en los sis emas de iempo eal debido a su la encia a iable. Es o es lo
que sucede con las caches con encionales con polí icas de eemplazo que dependen
de los accesos an e io es y los pa áme os de cache (asocia i idad, amaño, e c.).
Es as caches p opo cionan un g an endimien o en los sis emas con encionales pe o
esul an con ap oducen es ya que la di icul ad pa a aco a la la encia de cada acceso
implica un g an iempo de análisis y, en gene al, una g an sob es imación. Po es a
azón, muchas eces se p escinde de ellas asumiendo que odos los accesos se dan a
memo ia p incipal.
En el caso de las caches de ins ucciones una de las p opues as más ex endidas
pa a abo da es a p oblemá ica es el uso de caches bloqueables que simpli ican y
consiguen un análisis más p eciso [Apa+10;Apa+11;Pua06;PD02;CIM01].
Podemos encon a p opues as de diseños especializadas como las caches con
polí ica de eemplazo alea o ia que pe mi en aplica mé odos de análisis de sis emas
de iempo eal p obabilís icos [Kos+14]. También encon amos p opues as de dise-
ño especí icas pa a iempo eal de caches de da os, que conlle an un análisis mucho
más complejo que las de ins ucciones. Algunos ejemplos de es os diseños son la
Add ess-Cache Da a-Cache [Seg+15] y la Fully-associa i e FIFO agged Bu e [G a+15].
Es as caches p opo cionan una al a p edic ibilidad sin comp ome e la e iciencia e i-
ando la polución, i.e. no pe mi iendo los eemplazos no deseados.
1.3. Obje i os y Log os 7
1.2.3. Consumo ene gé ico
Como el análisis empo al de los sis emas de iempo eal es an c í ico, no se
suelen conside a o os pa áme os como el consumo de ene gía. Sin emba go, la
op imización del peo caso de consumo de ene gía (wo s -case ene gy consump ion,
WCEC) puede se un ac o cla e en aquellos sis emas que engan limi aciones im-
po an es en el suminis o de ene gía. Po ejemplo, aquellos sis emas alimen ados
con ba e ías o cualquie o a uen e de alimen ación que pueda ago a se y pa a la
cual es c í ico consegui un consumo de ene gía lo más bajo posible. Es os sis emas
cada ez adquie en más impo ancia ya que se ex ienden desde edes de senso es,
sis emas de igilancia y subsis emas sa éli es has a los obo s de búsqueda y esca e.
Exis en abajos p e ios ela i os al consumo de ene gía en sis emas de iempo
eal que hacen uso del ajus e dinámico de la ensión pa a consegui una plani icación
de a eas que sea e icien e ene gé icamen e [CK07]. Es as in es igaciones son bási-
camen e eó icas y es udian cómo ges iona la elocidad del p ocesado (y po an o
su consumo es imado de ene gía) cuando hay su icien e ma gen has a el deadline,
po ejemplo, en base al WCET de las a eas. Sin emba go, no suelen inclui en es os
análisis de plani icación el WCEC del sis ema, ya que gene almen e se desconoce
es e alo .
El abajo que abo da inicialmen e el p oblema de la combinación del WCET con
el WCEC [JML06], además de desc ibi lo, mues a que el WCEC no pude calcula se
como la ene gía media po el WCET. Es o se debe a que el camino co espondien e
al WCET no iene po que coincidi con el que enga un mayo consumo de ene gía.
Así que en es e abajo se p opone una écnica que p opo ciona una es imación del
WCEC pa a un p ocesado que ejecu e una sola a ea. Es a écnica emplea ILP de
mane a simila a las écnicas de análisis del WCET. Es deci , modelando el consumo
de ene gía de los bloques básicos a a és de es icciones lineales y ob eniendo el
peo caso encon ando el máximo consumo de ene gía.
En un abajo pos e io [G a+13] se mejo a es a p opues a p oponiendo una o -
ganización de memo ia de ins ucciones que incluye una cache bloqueable, mucho
más ap opiada pa a sis emas de iempo eal po su p edic ibilidad. Po o o lado
ambién amplian el análisis de un sis ema de una sola a ea a uno con a ias ejecu-
sandose en un plani icado de iempo eal p e en i o que pe mi e ene en cuen a
las in e e encias de los cambios de con ex o. En es a p opues a no solo calculan el
WCEC sino que lo op imizan en elación al conjun o de ins ucciones a bloquea en
la cache.
Po lo an o, en el con ex o de los sis emas de iempo eal es impo an e no pone
el oco únicamen e en el WCET ya que se pod ían desca a opciones que engan
algunos ciclos más incluso si consumen mucha menos ene gía.
1.3. Obje i os y Log os
El obje i o gene al de es a esis es mejo a la e iciencia de la je a quía de memo ia
en sis emas de iempo eal. Es o implica esencialmen e mejo a su p edic ibilidad,
aunque ambién se conside an o os aspec os como el el consumo ene gé ico. Los
obje i os especí icos son:
Mejo a an o el peo caso de iempo de ejecución (WCET) como su análisis en
sis emas de iempo eal que cuen en con je a quía de memo ia.
Es udia pa ones de acceso a memo ia en a eas pa a sis emas de iempo eal
y sis emas empo ados.

8Capí ulo 1. In oducción, es ado del a e y obje i os
Conside amos que los obje i os se han alcanzado a a és de la consecución de
los siguien es log os:
Hemos diseñado un algo i mo que ans o ma el CFG del bina io a analiza en
una es uc u a en á bol, necesa ia pa a usa Lock-MS como mé odo de análisis
del WCET. Es e algo i mo pe mi e educi el iempo de análisis del WCET sin
sac i ica p ecisión pa a una cache de ins ucciones bloqueable.
Hemos p opo cionado una heu ís ica de bloqueo dinámico basada en los bu-
cles que pe mi e ob ene el con enido óp imo de cache pa a el WCET de ca-
da egión. Es a heu ís ica a la ez que posee una baja complejidad, educe el
WCET explo ando de mane a e ec i a el euso empo al, y educe ambién su
iempo de análisis.
Hemos iden i icado que el WCET se educe de mane a e ec i a cuando los
bucles ec o izados o man pa e del código dónde se lle a a cabo la mayo
pa e de la ejecución, y po lo an o, ale la pena abaja po consegui una
buena ec o ización, ya sea a a és de la p og amación o del compilado , en
los sis emas de iempo eal.
Hemos aco ado que la asa ideal de acie os pa a la ansposición de ma ices
en su e sión iling se log a con muy pocos conjun os y no más de dos ías en
una cache asocia i a po conjun os cuando se aplica una con igu ación de ile
ap opiada (la dimensión del ile igual al amaño de línea de cache).
1.3.1. Es uc u a esis
En es e capí ulo (capí ulo 1) p esen amos el p oblema del análisis y cálculo del
WCET y e isamos los abajos de in es igación más ele an es elacionados con es-
e p oblema. Además desc ibimos los obje i os y log os alcanzados en el desa ollo
de es e abajo.
En el capí ulo 2exponemos los mé odos y he amien as que nos han pe mi i-
do lle a a cabo es e abajo. También ca ac e izamos los p og amas de p ueba que
u iliza emos pa a ob ene los esul ados.
En el capí ulo 3p esen amos un algo i mo que pe mi e educi el iempo de aná-
lisis del WCET en sis emas con una cache de ins ucciones simple y bloqueable, cen-
ándonos en el mé odo Lock-MS. P esen amos ambién cómo amplia es e algo i mo
pa a pode de e mina a ios pun os de bloqueo en cada a ea, cada uno con un con-
enido especí ico de cache, en ez de bloquea un solo con enido pa a la ejecución
de oda la a ea. Además de educi el iempo de análisis, los esul ados que ob e-
nemos del abajo de es e capí ulo mues an que ambién se ha educido el WCET
y que la asa de acie os que se alcanza pa a la cache de ins ucciones bloqueada es
simila a una ejecución eal con una cache de ins ucciones LRU. Finalmen e, anali-
zamos la suscep ibilidad a las op imizaciones del compilado , mos ando cual es la
elección co ec a pa a cada p og ama de p ueba y señalando que O0 es siemp e la
peo opción.
En el capí ulo 4se es udia el impac o de la ec o ización au omá ica de ins uc-
ciones en el análisis del WCET. Una ez aplicada la ec o ización po pa e del com-
pilado se analizan las pa es ec o izadas pa a aco a su con ibución al WCET de
la a ea con el obje i o de in eg a es as co as en el análisis del WCET de la a ea co-
espondien e. Pa a inaliza p esen amos los esul ados que mues an que el WCET
se educe de mane a e ec i a pe o que la e iciencia de la ec o ización au omá ica es
bas an e limi ada.
1.3. Obje i os y Log os 9
En el capí ulo 5analizamos un algo i mo undamen al en los sis emas de iem-
po eal, la ansposición de ma ices, en elación con su asa de acie os en cache de
da os, cuyo e ec o es de g an ele ancia en el cálculo del WCET. En es e análisis ob-
enemos la elación en e los pa áme os de cache que ga an izan la asa (p edecible)
ideal de acie os en da os omando una cache de da os LRU. T as ello compa amos
los algo i mos de ansposición de ma ices iling ycache-obli ious, demos ando que,
con el amaño adecuado de ile, la e sión iling del algo i mo ob iene una asa de
acie os en da os mejo o igual. También analizamos el consumo de ene gía y el
iempo en ejecución de la ansposición en ha dwa e eal con caches PLRU.
En el capí ulo 6se esumen las conclusiones de es a esis.
11
Capí ulo 2
Me odología y ca ac e ización de
benchma ks
En es e capí ulo exponemos los mé odos y he amien as que nos han pe mi i-
do lle a a cabo es e abajo. También ca ac e izamos los p og amas de p ueba que
u iliza emos pa a ob ene los esul ados.
2.1. Mé odos y he amien as exis en es pa a el cálculo del
WCET
2.1.1. He amien as de análisis de CFG
Una de las p ime as a eas al inicio de es a esis ue es udia las dis in as he a-
mien as disponibles con las que lle a a cabo el análisis del WCET de los capí u-
los 3y4.
La p ime a de ellas, Ch onos [Li+07], ue desca ada debido a que pa a pode
amplia y adap a el analizado había que abaja con SimpleScala [ALE02] que, si
bien ha sido uno de los simulado es más ampliamen e usados en la comunidad in-
es igado a, se encuen a ac ualmen e obsole o sin man enimien o desde 2011 [Sim].
O a he amien a in e esan e es Hep ane [HRP17]. En el momen o que se desa-
olló es e es udio (2015) es aba disponible la segunda e sión pe o lle aba 5 años
sin man enimien o y pese a se código abie o no acili aba la in eg ación de nue-
os análisis, algo imp escindible pa a el desa ollo de nues o abajo. Sin emba go,
publica on una e ce a e sión en 2017 en la que habían cambiado o almen e su es-
a egia de desa ollo y habían ede inido la a qui ec u a so wa e de Hep ane pa a
acili a an o la legibilidad del código como el desa ollo de nue os análisis.
Conside ando es a úl ima e sión, si es a decisión se u ie a que oma en la
ac ualidad Hep ane se p esen a ía como una buena elección.
SWEET [Lis14] se cen a en el análisis del lujo de con ol pe o no incluye ningún
análisis a ni el de ha dwa e, de hecho se plan ea como una he amien a comple-
men a ia a o as que ealicen un análisis a más bajo ni el. Además es a he amien a
no con empla que se añadan nue os análisis a los ya implemen ados. Ac ualmen e
no se encuen a disponible.
Bound-T [Tid] se encuen a o almen e des asada y podemos encon a una ex-
ensa y hones a decla ación en su web sob e los p oblemas de iabilidad que p esen a
debido a sus sucesi as ampliaciones.
Una de las he amien as ac uales más a anzada pa a el análisis del WCET es
aiT [FH04] pe o desg aciadamen e no es código abie o sino que es una he amien a
18 Capí ulo 2. Me odología y ca ac e ización de benchma ks
un camino de e minado. Po lo an o, odos los Bipa h se pueden sus i ui po Bi y
los bloques comunes se pueden analiza po sepa ado. Si una línea de memo ia es á
bloqueada y cacheada, su cos e de búsqueda se á siemp e el de un acie o en cache.
Sin emba go el cos e debe se allo en el line-bu e pa a la p ime a e e encia de cada
línea accedida. Los cos es de búsqueda de líneas de memo ia que no es án en cache
y son compa idas po a ios bloques básicos son es udiados en p o undidad en es e
mé odo. En esumen, es o pe mi e eesc ibi la ecuación 2.2 como:
WCET =min(B0+B3+B6+max(B1+B4, B1+B5, B2+B4, B2+B5)) (2.3)
De la ecuación 2.3 podemos ob ene exp esiones equi alen es a la unción de maxi-
mización de la siguien e mane a. Si B1>B2, en onces B1+B4>B2+B4, po lo
an o es ob io que B2+B4 puede desca a se ya que no o ma á pa e del peo caso.
De lo con a io, B1+B4≤B2+B4 y B2+B4 debe pe manece en la exp esión. Así
maximizando p ime o el pa B1, B2 y después B4, B5 enemos:
max(B1+B4, B1+B5, B2+B4, B2+B5) = max(B1, B2) + max(B4, B5)(2.4)
Po lo an o, podemos eesc ibi la ecuación 2.3 como:
WCET =min(Cos eComun +max(B1, B2) + max(B4, B5)) (2.5)
Es a in o mación pod ía aduci se a un á bol en el que el cos e de cada nodo
ue a la suma del cos e común más el máximo cos e de en e sus nodos hijos. Es
deci , cada una de las amas se ía un camino al e na i o. Como se puede e la di e-
encia en e las exp esiones de las ecuaciones 2.1 y2.5 es que la p ime a, exp esada
po caminos, equie e de muchas más es icciones que la segunda, con es uc u a
de á bol. Sin emba go, es e mé odo no p opo ciona el algo i mo pa a cons ui la
es uc u a en á bol necesa ia pa a es ablece las es icciones del modelo ILP.
2.2. Ca ac e ización de benchma ks
En es a sección p esen amos aquellos p og amas de p ueba que u ilizamos du-
an e nues a in es igación.
2.2.1. Sui es de benchma ks pa a sis emas de iempo eal
Una de las p incipales cues iones de la mayo ía de los abajos de in es igación
de nues a á ea es qué p og amas de p ueba (benchma ks) an a u iliza se pa a me-
di los esul ados de la p opues a de dicho abajo. Es o es especialmen e ú il en el
á ea de los sis emas de iempo eal dónde es c ucial e alua y compa a écnicas
de análisis del WCET, de los compilado es y de a qui ec u a de compu ado es. Po
ello, es muy ú il ene un conjun o de benchma ks (llamados sui es de benchma ks)
que se encuen en disponibles con acilidad, que hayan sido p obados, que es én
bien documen ados, que sean ieles a los p og amas que se es án usando en sis e-
mas de iempo eal en la indus ia y que engan un econocimien o de la comunidad
in es igado a que pe mi a es ablece compa aciones en la e aluación de dis in os
algo i mos, mé odos y he amien as.
Todos es os mo i os son los que nos han lle ado a escoge las dos sui es de
benchma ks que p esen amos a con inuación:

2.2. Ca ac e ización de benchma ks 19
o ( i =0; i <n ; i ++)
o (k=0;k<n ; k++) {
=B[ i ][ k ] ;
o ( j =0; j <n ; j ++)
A[ i ] [ j ]=A[ i ][ j ]+ ∗C[k ][ j ] ;
}
FIGURA 2.4: Algo i mo del benchma k ma mul _op i.
Mäla dalen [Gus+10] es la p ime a colección de p og amas especialmen e di-
igido pa a las he amien as de análisis del WCET, con un en oque en el análi-
sis del lujo del p og ama. Se c eó en 2005 ecopilando p og amas de dis in as
uen es y desde en onces se ha usado en muchas in es igaciones del WCET. La
mayo ía de sus benchma ks son ela i amen e pequeños y de un solo camino,
lo cual limi a su apo ación a la ho a de e alua he amien as que admi en
códigos de caminos múl iples.
TACLeBench [Fal+16] p opo ciona un conjun o de benchma ks g a ui os dis-
ponibles y elacionados con emas de in es igación. Sus códigos son au ocon-
enidos; no exis en dependencias de cabece as especí icas del sis ema a a és
de #include o del sis ema ope a i o. Todos los da os de en ada o man pa e
del código uen e en C. Es o hace que la colección TACLeBench sea ú il pa-
a sis emas empo ados donde no hay biblio ecas es ánda disponibles. Como
uno de los obje i os de la c eación de TACLeBench es abo da las necesida-
des que equie en las he amien as de análisis empo al, odos los benchma ks
con ienen ano aciones sob e in o mación del lujo de da os (po ejemplo, el nú-
me o máximo de i e aciones de los bucles).
La abla 2.1 mues a los benchma ks que se han u ilizado en nues os expe i-
men os de los capí ulos 3y4que se desca ga on en eb e o de 2017 de los paque es
TACLeBench [Fal+16] y Mäla dalen [Gus+10], más el benchma k ma mul _op que
ejecu a una mul iplicación de ma ices op imizada ( igu a 2.4).
Algunos de los benchma ks de es os paque es se han desca ado po las siguien-
es azones: e o es de compilación en compilado es c uzados1, núme o desconoci-
do de i e aciones de bucles en unciones de biblio ecas al compila con coma lo an e
emulada2y p oblemas con la ex acción del CFG3. Es os p oblemas de ex acción in-
cluyen cons ucciones «swi ch» implemen adas median e sal os a di ecciones desco-
nocidas, CFGs con bucles i educibles (po ejemplo, bucles con múl iples en adas),
unciones ecu si as, e c. Es as cues iones p o ienen de limi aciones en el p ocesa-
mien o del código bina io, pe o no a ec an a nues as p opues as.
2.2.2. T ansposición de ma ices
La asposición de una ma iz es una ope ación que consis e en coloca sus ilas
en o ma de columna, espe ando su o den. En la igu a 2.5 podemos encon a un
ejemplo de la ansposición de una ma iz de 3×3 elemen os. Es a ope ación apa en-
emen e sencilla es undamen al en á eas como el álgeb a lineal o las ans o madas
1powe window, bi coun , gsm_dec, ijndael_dec, dijndael_enc, susan.
2powe window, p ime, adpcm_dec, adpcm_enc, ammuni ion, anag am, cjpeg_ ansupp, cjpeg_w bmp, epic,
hu _enc, ijndael_dec, ijndael_enc.
3sha, gsm_enc, h264_dec, co e , du , mpeg2, lms, es 3, quickso , ecu sion.
20 Capí ulo 2. Me odología y ca ac e ización de benchma ks
TABLA 2.1: Benchma ks usados en nues os expe imen os (TACLe-
Bench [Fal+16] y Mäla dalen [Gus+10]).
Nomb e Sui e
audiobeam TACLeBench
basicma h TACLeBench
bina ysea ch TACLeBench
bso Mäla dalen
bs Mäla dalen
cn Mäla dalen
complex_upda es TACLeBench
coun nega i e TACLeBench
c c Mäla dalen
dijks a TACLeBench
dc Mäla dalen
TACLeBench
il e bank TACLeBench
i 2dim TACLeBench
m e TACLeBench
g723_enc TACLeBench
ii TACLeBench
janne_complex Mäla dalen
j dc in TACLeBench
li TACLeBench
ludcmp Mäla dalen
ma mul Mäla dalen
ma mul _op i P opio
ma ix1 TACLeBench
md5 TACLeBench
min e TACLeBench
nsichneu Mäla dalen
ndes Mäla dalen
pe ine TACLeBench
pm TACLeBench
qso -exam Mäla dalen
qu Mäla dalen
selec Mäla dalen
s TACLeBench
s a ema e Mäla dalen
de Fou ie , en e o as. Además iene muchas aplicaciones en o as como el análisis
numé ico, el p ocesado de imágenes y g á icos. Hay muchos ejemplos de aplicacio-
nes desa olladas en los cen os de supe compu ación que usan, de un modo u o o,
la ansposición de ma ices como pa e esencial pa a soluciona sus p oblemas. Po
ejemplo, el Oak Ridge Na ional Labo a o y (EEUU) desa olla, man iene, p ueba y ges-
iona SCALE Code Sys em [RJ16] que es un conjun o de benchma ks de modelado y
simulación ampliamen e usado pa a el diseño y análisis de segu idad nuclea . O o
ejemplo que encon amos es Geo ess [Bal+16] desa ollado po Sandia Na ional Labo-
a o y. Es e sis ema de sopo e so wa e y pa ame ización de modelos implemen a
la cons ucción, almacenamien o y consul a de los da os pe enecien es a modelos
3D de la Tie a.
En el á ea de iempo eal encon amos que el pa ón de accesos del algo i mo es
de e minis a y de ácil comp ensión, po lo an o su es udio puede se i de base
pa a analiza o os algo i mos con pa ones de acceso más complicados. Sin emba -
go, su análisis en el en o no de iempo eal no es i ial ya que apa ecen muchos
2.2. Ca ac e ización de benchma ks 21
FIGURA 2.5: Ejemplo de ansposición de una ma iz de 3×3 elemen-
os.
pa áme os a ene en cuen a: el amaño de la ma iz y odos los elacionados con la
es uc u a de la memo ia cache ( amaño, asocia i idad, núme o de conjun os, ama-
ño de bloque...). Además, es a ope ación iene a ias p opues as de implemen ación
que a ían el o den de acceso de los elemen os de la ma iz al e ando la e icacia del
uso de la cache de da os y, po an o, la e icacia del sis ema.
23
Capí ulo 3
Reducción del WCET y del iempo
de análisis en sis emas con caches
bloqueables de ins ucciones
En es e capí ulo a amos uno de los e os cla e en los sis emas de iempo eal
que es el análisis de la je a quía de memo ia. Muchos mé odos de análisis del WCET
que admi en una cache de ins ucciones se basan en algo i mos i e a i os o con e -
gen es los cuales son bas an e len os. Nues o obje i o en es e capí ulo es educi el
iempo de análisis del WCET en sis emas con una cache de ins ucciones bloquea-
ble, cen ándonos en el mé odo Lock-MS. P ime o, p oponemos un algo i mo pa a
ob ene una ep esen ación basada en la es uc u a del g a o de con ol de lujo. Es-
e algo i mo o ganiza el p oblema del WCET como un conjun o de subp oblemas
anidados, el cual ap o echa los algo i mos habi uales de ami icación y poda de los
sol e s de ILP. Después, añadimos al algo i mo la posibilidad de de e mina a ios
pun os de bloqueo en cada a ea, cada uno con un con enido especí ico de cache, en
ez de bloquea un solo con enido pa a la ejecución de oda la a ea. Los pun os de
bloqueo se es ablecen heu ís icamen e an es de los bucles ex e io es. Es a heu ís ica
es an simple que no añade complejidad y educe el WCET ap o echando el euso
empo al que encon amos en los bucles. Debido a que los bucles pueden p ocesa se
como egiones aisladas, pa a cada egión se puede ob ene el con enido óp imo a
bloquea en la cache y el iempo de análisis del WCET se e á no ablemen e educi-
do. Con es as dos mejo as nues o análisis del WCET esul a un o den de magni ud
más ápido que o as p opues as. Además, nues os esul ados mues an que la a-
sa de acie os que se alcanza pa a la cache de ins ucciones bloqueada es simila a
una ejecución eal con una cache de ins ucciones LRU. Finalmen e, analizamos la
suscep ibilidad a las op imizaciones del compilado , mos ando cual es la elección
co ec a pa a cada p og ama de p ueba y señalando que O0 es siemp e la peo op-
ción.
3.1. In oducción
Uno de los p incipales e os en el análisis del WCET es la je a quía de memo-
ia [Apa+08]. El compo amien o con encional de la cache depende de las e e en-
cias pasadas y, pa a que el análisis sea p eciso, se á necesa io conoce odos los ac-
cesos de memo ia p e ios pa a de e mina la la encia de un de e minado acceso a
memo ia. Si nos cen amos en el eemplazo LRU, los mé odos es á icos ac uales de
análisis del WCET se basan en AbsIn [CC77;FW99], IPET [LMW96], o el uso de am-
bos [T a]. Dado el conside able iempo de análisis que es os mé odos p ecisan pa a

24 Capí ulo 3. Reducción del WCET y del iempo de análisis
analiza el WCET en sis emas con una cache de ins ucciones, no es á cla o si pue-
den analiza p og amas complejos en sis emas que incluyan o os componen es de
ha dwa e como la cache de da os, la p ebúsqueda, e c. Po ejemplo, aunque eó ica-
men e an o AbsIn como IPET pe mi en caches de da os [LMW96], ningún es udio
las ha e aluado a conciencia has a donde sabemos.
Pa a educi el iempo de análisis muchos es udios han p opues o usa caches
comple amen e bloqueables [Mi 16]. Es as caches se pueden encon a en p ocesa-
do es de la mayo ía de ab ican es como Mo o ola (ColdFi e, Powe PC, MPC7451,
MPC7400), MIPS32, ARM (904, 946E-S), In eg a ed De ice Technology (79R4650,
79RC64574), In el 960, e c. En caso de allo es as caches piden la línea que ha esul a-
do en allo al siguien e ni el de memo ia pe o cuando llega se en ía a un line-bu e
(memo ia in e media con capacidad de almacena una línea de cache) sin gua da
ninguna copia en la cache. Po lo an o, no se á necesa io ealiza ningún eemplazo
y odo el almacenamien o y con ol dedicado a su implemen ación en las caches con-
encionales se sup ime al ca ece de u ilidad. Debido a que el con enido de la cache
bloqueable es conocido y no cambia, el cálculo de acie os y allos es mucho más ácil
y no depende de los accesos an e io es a memo ia, de es e modo se simpli ica el aná-
lisis del WCET. Sin emba go, el e o que p esen an es as caches es de e mina qué
conjun o de ins ucciones se á el mejo pa a bloquea en la cache, además de lle a
a cabo su análisis del WCET. Po lo an o, los mé odos de caches bloqueables a an
de encon a qué con enidos deben se bloqueados en la cache pa a gene a el míni-
mo WCET posible. Depende á de su lexibilidad en cuan o a los pun os de ca ga y
bloqueo, de los dis in os conjun os de con enidos a ges iona , y ambién de cómo se
abo de el análisis (heu ís icamen e, analí icamen e, e c.). Hay muchos mé odos pa a
abo da es e p oblema.
Los mé odos de «bloqueo es á ico» seleccionan un solo conjun o de ins uccio-
nes pa a bloquea du an e odas las a eas que se ejecu an en el sis ema, po lo an o
es a selección se ija cuando el sis ema se inicia [PD02]. Po o o lado, los mé odos
de «bloqueo dinámico» seleccionan uno o más conjun os de ins ucciones pa a ca-
da a ea. En gene al, el bloqueo dinámico unciona mejo que el es á ico en cuan o
al WCET [Cam+03]. Cen ándonos en el bloqueo dinámico, nos e e i emos como
bloqueo dinámico de un solo con enido a aquellos mé odos que seleccionan un solo con-
enido po a ea, el cual se ca ga y bloquea en el cambio de con ex o de la a ea
co espondien e (po ejemplo [Apa+11]), y bloqueo dinámico de con enido múl iple a
aquellos mé odos que pe mi en a cada a ea ca ga y bloquea con enidos du an-
e su ejecución en múl iples ocasiones(po ejemplo [Pua06]). Dos p opiedades muy
in e esan es del bloqueo dinámico de un solo con enido son que, p ime o, se pue-
de lle a a cabo el análisis del WCET con mé odos basados en la es uc u a (cuya
solución es mucho más ápida) sin pe de p ecisión, y segundo, que es os mé o-
dos ambién p opo cionan la selección óp ima de con enidos a bloquea [Apa+11].
Es o pe mi e ex ende el análisis del WCET de mane a que incluya la p ebúsque-
da [Apa+10], cache de da os [Seg+12;Seg+15], e incluso pode analiza al mismo
iempo el consumo de ene gía pa a ob ene una solución equilib ada que enga en
cuen a an o el WCET como el WCEC [G a+13]. Po o o lado, los mé odos dinámi-
cos de con enido múl iple mejo an el WCET pe o se añade la di icul ad de decidi
cuáles se án los mejo es luga es del código en los que ija la ca ga y bloqueo de
ins ucciones, y cuales se án es as ins ucciones en cada pun o de ca ga.
No malmen e es os dos p oblemas se abo dan heu ís icamen e pa a in en a li-
mi a el iempo de análisis, así que sus esul ados no son óp imos. Además el iem-
po de análisis que necesi an sigue siendo compa able al necesa io pa a ealiza el
análisis del WCET en una cache LRU [AP;Pua06]. O os es udios usan algo i mos
3.1. In oducción 25
gené icos pa a in en a esol e es os p oblemas [CIM01].
Po úl imo, algunos es udios suponen caches pa cialmen e bloqueables a ni el de
conjun o. En cada conjun o de es as caches puede habe un núme o a iable de lí-
neas no bloqueadas o denadas en LRU y el es o de líneas del conjun o es a án
bloqueadas [DLM13;ZWY17]. La complejidad del con ol y almacenamien o pa a
implemen a es e mé odo sob epasa las capacidades de las caches con encionales y,
po supues o, de las caches comple amen e bloqueables. Has a donde sabemos, es e
ha dwa e oda ía no es á disponible y los diseños ac uales de cache es án bas an-
e alejados de alcanza es e compo amien o. Además se necesi a mucho iempo de
análisis pa a el g an núme o de con igu aciones que admi e una cache pa cialmen e
bloqueable a ni el de conjun o. Po ejemplo, se ha p opues o un p oceso con e gen e
que consis e en dos ases [ZWY17]. En la p ime a se ealiza el análisis del WCET asu-
miendo una cache de ins ucciones que puede ene algunas líneas bloqueadas. En
la segunda ase se p ueba si hay una nue a línea adecuada pa a bloquea , con igu-
ando la cache de ins ucciones de acue do con la p óxima i e ación del algo i mo de
con e gencia. Sin emba go, ninguno de es os es udios p opo ciona unos pun os de
e e encia que sean independien es del sis ema (po ejemplo, si uación de siemp e
acie o o de siemp e allo) lo cual di icul a in e p e a sus esul ados. Además no se
compa an con las caches con encionales y cuando se compa an con caches comple-
amen e bloqueables usan un ha dwa e sesgado ya que no conside an el line-bu e
que es necesa io pa a que las caches bloqueables uncionen co ec amen e [Apa+10;
Apa+11;AP;Pua06;PD02;Seg+12;Seg+15]. Sin emba go, en es e capí ulo nos cen-
amos en es uc u as de cache simples y mé odos de análisis del WCET ápidos, así
que las soluciones a a és de caches bloqueables pa cialmen e a ni el de conjun o
se encuen an ue a de nues o ámbi o.
Como hemos a i mado an e io men e, es an impo an e mejo a la elocidad
del análisis que muchas eces los mé odos heu ís icos son p e e ibles a los mé odos
analí icos. Sin emba go, los mé odos de análisis o ien ados a caches bloqueables no
han explo ado oda ía a conciencia el po encial de es os sis emas pa a ob ene un
análisis ápido. Nues o obje i o en es e capí ulo es educi el iempo de análisis del
WCET de a eas en p esencia de caches de ins ucciones bloqueables. Es o se log a-
á desa ollando DLock-MS, un mé odo de bloqueo dinámico de con enido múl iple.
Básicamen e consis e en añadi dos mejo as cla es a Lock-MS [Apa+11], un mé o-
do de bloqueo dinámico de un solo con enido. Es e mé odo ha sido de allado más
p o undamen e en las sección 2.1.2
La p ime a de es as mejo as es un algo i mo que aduce el CFG a una es uc u a
en á bol que ep esen a el p oblema de análisis del WCET, la cual pe mi e usa Lock-
MS como un mé odo basado en la es uc u a. Es e ipo de mé odos son en gene al
los más ápidos, ya que no usan algo i mos de con e gencia ni supe ponen p oble-
mas de lujo. Es e algo i mo o ganiza el p oblema del WCET como un conjun o de
subp oblemas anidados, el cual ap o echa los algo i mos habi uales de ami icación
y poda de los sol e s (so wa es de esolución de modelos ILP). La p og amación li-
neal en en e os da espues a a si uaciones en las que se exige maximiza o minimiza
unciones que se encuen an suje as a de e minadas es icciones, y cuyas a iables
de decisión deben se en e as. Los sol e s una ez de inidas las unciones y es ic-
ciones esuel en es a maximización o minimización de las unciones aplicando las
es icciones co espondien es. Al habe hecho una di isión en subp oblemas cada
uno se op imiza pa a consegui una esolución lo su icien emen e ápida. En é -
minos de e iciencia, nues o algo i mo gene a una es uc u a en á bol en una única
pasada y explo a cada ama solo una ez.
Nues a segunda mejo a a a la limi ación de amaño que p esen an los mé odos
26 Capí ulo 3. Reducción del WCET y del iempo de análisis
Algo i mo 1 Explo a (nodoCFGac ual,caminoAc ual)
1: i |hijos(nodoCFGac ual)|=0 hen # no hay más nodos en el camino
2: e u n caminoAc ual +nodoCFGac ual
3: else i |hijos(nodoCFGac ual)|=1 hen # hijo único: expandi camino
4: e u n Explo a (hijo(nodoCFGac ual), caminoAc ual +nodoCFGac ual)
5: else i |hijos(nodoCFGac ual)|>1and explo ado[nodoCFGac ual] hen
6: e u n caminoAc ual +nodoCFGac ual # condicional ya explo ado
7: else # condicional no explo ado (|hijos(nodoCFGac ual)|>1)
8: o all nodoHijo ∈hijos(nodoCFGac ual)do # p ocesa cada camino al e na i o
9: caminoAl e na i o ←Explo a (nodoHijo,nodoCFGac ual)
10: p ocesa YCons ui Res icciones(nodoCFGac ual,caminoAl e na i o) # es ablece es icciones
como CBBx ≥caminoAl e na i o
11: end o
12: explo ado[nodoCFGac ual]← ue
13: e u n caminoAc ual +nodoCFGac ual # odos los caminos al e na i os han sido p ocesados
14: end i
de bloqueo dinámico con un único con enido, no solo pa a sob epasa esa limi a-
ción consiguiendo mejo es esul ados en el WCET sino ambién eniendo en cuen a
el iempo y e iciencia del análisis. DLock-MS aplica heu ís icas basadas en bucles pa-
a selecciona el emplazamien o de los pun os múl iples de ca ga y bloqueo pa a la
cache de ins ucciones. Después pe mi e al sol e encon a los con enidos óp imos
pa a ca ga y bloquea en cada pun o. Además las egiones dónde pe manecen ijos
cada uno los con enidos bloqueados se pueden p ocesa como subp oblemas aisla-
dos, lo cual acele a aún más el análisis del WCET y su esolución. Es o nos da ía la
posibilidad ambién de calcula cada una de las egiones en pa alelo (no lo abo da-
mos en es e abajo).
El es o del capí ulo lo o ganizamos de la siguien e mane a. Nues as dos p o-
pues as se desc iben en las secciones 3.2 y3.3. En la sección 3.4 e aluamos las p o-
pues as y, inalmen e p esen amos nues as conclusiones en la sección 3.5.
3.2. T ans o mación de CFG a á bol
En es a sección p esen amos la p ime a con ibución de es e capí ulo, un algo-
i mo que aduce el CFG a una es uc u a en á bol que ep esen a el p oblema de
análisis del WCET, la cual pe mi e usa Lock-MS como un mé odo basado en la es-
uc u a.
Comienza sus i uyendo los bucles y las unciones que no sean el p og ama p in-
cipal po nodos i uales (bloques básicos) en el CFG. Después, se p ocesan como
sub-CFGs independien es pa a ans o ma los en á boles. El Algo i mo 1se aplica
ecu si amen e an o en el CFG p incipal como en cada uno de los sub-CFGs inde-
pendien es, comenzando desde el nodo de en ada del CFG co espondien e y un
camino acío (Explo a (en ada,∅)). Es e algo i mo lle a a cabo una búsqueda ecu -
si a en p o undidad que cons uye los á boles asociados a cada CFG y gene a sus
co espondien es es icciones ILP con o me al modelo Lock-MS. Básicamen e, cada
á bol se compone de un nodo condicional más odos sus caminos al e na i os has-
a que se alcanzan o o nodo condicional. El Algo i mo 1 unciona de la siguien e
mane a: Las líneas 1 y 2 a an los nodos inales del CFG, de ol iendo el camino
en cu so más el nodo ac ual (y inal), po lo an o comple an la explo ación de ese
camino. En las líneas 3 y 4, que co esponden a un nodo con un solo hijo, con inúa
la explo ación siguiendo el camino de es e hijo único. Las líneas 5 y 6 co espon-
den a la explo ación de un nodo condicional, es deci que iene más de un hijo, que
3.2. T ans o mación de CFG a á bol 27
ya ha sido explo ado. En consecuencia, ya se ha lle ado a cabo su p ocesamien o y
la gene ación de sus es icciones co espondien es siendo innecesa io con inua su
explo ación. Finalmen e, en las líneas 7 a 13 se desc ibe como p osegui cuando el
nodo ac ual es condicional y oda ía no se ha explo ado. En es e caso, se gene a un
á bol nue o, con el nodo ac ual como su aíz. Cada uno de sus hijos se explo a á pa a
cons ui las amas (caminos al e na i os) de es a aíz (líneas 8 y 9). A con inuación
en la línea 10, se p ocesa cada una de las amas y se es ablecen sus es icciones ILP
co espondien es ( al como explicamos más adelan e). Finalmen e, el nodo ac ual
se ma ca como explo ado, de ol iendo el camino has a es e nodo (líneas 12 y 13).
Hay que ene en cuen a que el nodo de en ada de un bucle no se conside a hijo
de ningún nodo que sea in e no del p opio bucle, ya que los a cos que los puedan
elaciona son aquellos esponsables de la epe ición del bucle.
Básicamen e, la es icciones ILP (línea 10, Algo i mo 1) modelan un p oblema
de minimización pa a un á bol de nodos (bloques básicos, BB). El cos e de cada
nodo en pa icula BBico esponde al cos e o al acumulado de ejecu a ese nodo,
lo que esul a en una exp esión dependien e de sus di e en es casos de ejecución y
su núme o de ins ancias. Pa a cada línea de memo ia que puede es a en cache jen
un bloque básico, se asocia una a iable enCacheBBijque de e mina si es á o no en
cache pa a educi el WCET. Es a líneas de memo ia en cache no pueden aumen a
más allá de la capacidad misma de la cache, así que ambién es án es ingidas según
el núme o de conjun os y ías.
Po ejemplo, asumiendo una cache bloqueable y un bloque básico BB1 que quepa
en una única línea de cache L1, sus cos es se es ablecen como:
BB1 =nEjecsBB1 ·Cos eBB1
=nEjecsBB1 ·(cos eAcie o ·enCacheL1 +cos eFallo ·(1−enCacheL1) + ejecIns BB1)
, donde cos eAcie o ycos eFallo son cons an es p e iamen e calculadas en base a los
pa áme os de ha dwa e, ejecIns BB1 cos e de ejecución de las ins ucciones del blo-
que básico, nEjecsBB1 depende del CFG, y enCacheL1 es una a iable bina ia (0/1).
Sin emba go, en es e abajo nos cen amos en la es uc u a de las es icciones
gene ales que modelan el CFG y no en aquellas que modelan el ha dwa e [Apa+10;
Apa+11;G a+13;Seg+12;Seg+15].
Tomamos como ejemplo la igu a 3.1 que mues a un CFG con 12 caminos ex-
plíci os que hay conside a en el análisis del WCET, los á boles que se ob ienen as
su ans o mación y sus p incipales es icciones ILP co espondien es. Señala que
con una cache bloqueable el peo iempo de ejecución de un bucle no puede in-
clui combinaciones de caminos al e na i os en su in e io [Apa+11]. Po lo an o
los 12 caminos a conside a ejecu an lo siguien es bloques básicos: 1-2-4-5-10-11-13,
1-2-4-5-10-12-13, 1-3-4-5-10-11-13, 1-3-4-5-10-12-13, 1-2-4-6-7-9-10-11-13, 1-2-4-6-7-9-
10-12-13, 1-2-4-6-8-9-10-11-13, 1-2-4-6-8-9-10-12-13,1-3-4-6-7-9-10-11-13, 1-3-4-6-7-9-
10-12-13, 1-3-4-6-8-9-10-11-13, y 1-3-4-6-8-9-10-12-13. El Á bol A ep esen a el úl imo
de los condicionales, en BB10, cuyo cos e se á el máximo de sus dos amas al e na i-
as. El Á bol B ep esen a del bloque BB4 a BB10, es e úl imo ya ha sido explo ado
(Á bol A). El bucle que empieza en BB6 se analiza como un CFG independien e con
sus p opio á bol (Á bol Bucle) y se ep esen a como un nodo i ual (BucleBB6) en
el Á bol B. Po úl imo, el Á bol C ep esen a del bloque BB1 al BB4. Po lo an o
en ez de 12 caminos en el CFG, nues a p opues a p opo ciona 4 sub-á boles con
2 sub-caminos cada uno.
Se puede es ablece el WCET como el cos e de odo el á bol, es deci , el cos e de
su aíz: WCET =CBB1. A su ez, el cos e de cada á bol (compues o po los cos es
34 Capí ulo 3. Reducción del WCET y del iempo de análisis
Cuando aplicamos DLock-MS enemos que conside a cie o sob ecos e. Asumi-
mos que el bloqueo dinámico se ealiza ejecu ando unciones, al como hacen o os
es udios [ZWY17]. Esas unciones ca gan y bloquean el conjun o de ins ucciones ne-
cesa ias en la cache pa a la siguien e egión del código. En conc e o, conside amos
una penalización de 47 ciclos po llamada, una po egión. Es os ciclos co espon-
de ían a los cos es de ejecución, allos en cache y penalizaciones de la segmen ación
en una unción que, es imando, se ía de 12 ins ucciones. Además, po cada línea
de cache bloqueada, añadimos el cos e de la encia de memo ia (10 ciclos). Es e es-
cena io es bas an e conse ado ya que pa a bloquea ins ucciones se pod ían usa
ope aciones de ca ga especializadas, po ejemplo, ca gando un g an núme o de lí-
neas de memo ia con inuas usando algún ipo de modo de ans e encia de memo ia
en á agas, lo que pod ía educi de mane a no able el iempo o al de ans e en-
cia [ZWY17].
El modelo ILP que ob enemos se esuel e po el sol e lp-sol e e sión 5.5.2.3.
Debido a las pa icula es p opiedades de anidación de nues o modelo basado
en la es uc u a, usamos las siguien es opciones en el sol e -BB, -Bc, -Bd, -Bg, y -Bo
pa a o dena a iables y aplica una codiciosa ami icación y poda in e sa.
3.4.1. E aluación de iempos de análisis
En es a sección es udiamos el iempo necesa io pa a el análisis es á ico del WCET
con el mé odo DLock-MS, una ex ensión de Lock-MS con una ans o mación e icien-
e de CFG a á bol y una heu ís ica de bloqueo dinámico.
La igu a 3.4 mues a nues os iempos de análisis compa ados con aquellos que
necesi a el analizado del WCET (AbsIn +IPET) de O awa (owce 1.2.0) [T a]. En el
eje xes án ep esen ados los benchma ks y en el eje yla mejo a ob enida en el aná-
lisis del WCET: el iempo de ejecución del análisis del WCET de O awa asumiendo
una cache de ins ucciones LRU con encional di idido po el iempo de ejecución
de DLock-MS en una cache de ins ucciones bloqueable del mismo amaño. En la
pa e de la de echa se especi ica el ni el de op imización. Los benchma ks es án o -
denados po núme o de caminos a explo a en la ep esen ación basada en á bol
pa a la op imización O3, de mane a que e leja su ni el de complejidad. Pa a cada
benchma k, se mues an con boxplo s odos los expe imen os a iando el amaño de
cache ( e abla 3.1). Es o es, cada columna mues a una caja cuyos lími es indican
el p ime y e ce cua il, con una ma ca den o que de e mina la mediana. En las
líneas e icales ue a de la caja se mues a la a iabilidad ue a de es os cua iles
y los pun os más allá de es as líneas indican alo es a ípicos, es deci , aquellos que
no son es adís icamen e ele an es. También, la línea ho izon al mues a la unidad
de mejo a, es deci cuando nues a p opues a no mejo a ni empeo a en e a O awa,
y po lo an o el cocien e de compa ación es uno. Así, cuan o más al os es án los
boxplo s más ápido es nues o análisis del WCET compa ado con el de O awa.
Con espec o al iempo de análisis, lo limi amos a un máximo de 10 minu os,
así que cualquie expe imen o que a de más iempo se asumi á que ha a dado
10 minu os exac amen e. Señalemos en onces que cuando es os casos apa ecen en
O awa es amos asumiendo un iempo de análisis meno que el que debe ía de se .
Con DLock-MS, solo un expe imen o a da más de 10 minu os. Sin emba go, es im-
po an e des aca que noso os somos capaces de p opo ciona esul ados segu os
an es de que se comple e nues o análisis/op imización del WCET. Es o es, cuando
pa amos nues o análisis a los 10 minu os, ya enemos un co a segu a del WCET
y un conjun o de con enidos especí icos pa a ca ga los en cada pun o de bloqueo,

3.4. Resul ados 35
-O0
-O1
-O2
-O3
complex_upda es
coun nega i e
i 2dim
ii
janne_complex
j dc in
ma mul
ma ix1
bina ysea ch
bso
il e bank
selec
qso -exam
dijks a
s
c c
qu
min e
li
ndes
ludcmp
audiobeam
md5
pm
s a ema e
m e
basicma h
pe ine
g723_enc
0,1
10
103
0,1
10
103
0,1
10
103
0,1
10
103
Benchma k
Tiempo de análisis del WCET ( eces más ápido que O awa)
FIGURA 3.4: Compa ación de iempo de análisis es á ico del WCET
pa a nues a p opues a (basada en la es uc u a) y O awa (AbsIn +
IPET).
aunque no podamos ga an iza que es la con igu ación óp ima, es deci , la que p o-
po ciona el WCET meno . Po lo an o, asumi que los expe imen os no a dan más
de 10 minu os bene icia a O awa en la compa ación.
En la igu a 3.4 emos que en la mayo ía de los casos las cajas son simplemen e
líneas ho izon ales. Pa a es os benchma ks, es o signi ica que la a iación de la mejo-
a es muy pequeña en elación al amaño de cache. Tan o a a és de los benchma ks
como de los ni eles de op imización, DLock-MS es no malmen e unas 10 eces más
ápido que O awa, aunque cie os benchma ks pueden se especialmen e di íciles
de analiza pa a cada mé odo. Po ejemplo, los esul ados po encima de 104co es-
ponden a análisis que no se han comple ado en 10 minu os en O awa. Po o o lado,
en los pocos casos en los que el análisis de O awa es más ápido pa ece que se debe a
la exis encia de a ios caminos con un iempo igual o muy simila de ejecución. Es o
e i a que el sol e pueda desca a ápidamen e es os caminos como sucede en el
caso de s a ema e O3. También se iene que ene en cuen a que O awa es más ápido
que o as p opues as. Po ejemplo, el iempo de análisis necesa io que encon amos
en o os es udios es más de 30 eces mayo que el nues o [ZWY17].
Aunque no se p esen a en la igu a 3.4, hemos es udiado ambién el iempo que
DLock-MS in ie e en cada pa e del análisis. Pa a los expe imen os que se p esen an
en es a igu a, nues a p opues a a da una media de 0,06 segundos en ob ene el
36 Capí ulo 3. Reducción del WCET y del iempo de análisis
complex_upda es
coun nega i e
i 2dim
ii
janne_complex
j dc in
ma mul
ma ix1
bina ysea ch
bso
il e bank
selec
qso -exam
dijks a
s
c c
qu
min e
li
ndes
ludcmp
audiobeam
md5
pm
s a ema e
m e
basicma h
pe ine
g723_enc
( odos)
-O0
-O1
-O2
-O3
LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD LD
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
Mé odo de análisis del WCET: Lock-MS (L) o DLock-MS (D)
WCET / Siemp e acie o WCET (pa a cada ni el de op imización)
FIGURA 3.5: Compa ación de WCETs de Lock-MS yDLock-MS, cuan o
meno mejo .
CFG y gene a la es uc u a en á bol y las es icciones de ILP, mien as que el ILP
sol e a da una media de 2,29 segundos en esol e el p oblema.
3.4.2. E aluación de la e icacia
La igu a 3.5 mues a la e aluación de la e icacia de DLock-MS compa ada con el
mé odo Lock-MS o iginal. Como an es, los esul ados es án ep esen ados po box-
plo s pa a cada ni el de op imización. Ya que DLock-MS básicamen e ex iende a
Lock-MS admi iendo múl iples pun os de ca ga y bloqueo, sus esul ados son, en
gene al, iguales o mejo es. En conc e o, los WCETs se mejo an un 2,2% de media, in-
cluyendo ya el cos e ex a de in oduci los pun os de bloqueo. Es e sob ecos e (una
llamada a unción en cada pun o de bloqueo) supone en media un 2,1% del WCET.
Aplicando un es de signo de Fishe con un ni el del con ianza de 0,99, se ob ie-
ne un p- alo de 2,2 ·10−16, lo cual a i ma que DLock-MS unciona mejo que Lock-
MS.
Aunque las mejo as en la igu a 3.5 puedan pa ece pequeñas, hay que ene en
cuen a que en a ios casos Lock-MS ya alcanza el mejo WCET posible (po ejemplo
en dijks a), po lo an o en es os casos no hay ma gen de mejo a. También puede
inc emen a se el WCET lige amen e al añadi pun os de ca ga y bloqueo innece-
sa ios, aunque es e inc emen o debe ía no a se solo en benchma ks sencillos (po
ejemplo en ii ,janne_complex ybina ysea ch). En los benchma ks más complejos (los
de la pa e de echa), las mejo as en el WCET son cla as y el único caso p oblemá i-
co es cuando a ias egiones es án ol iendo a ca ga los mismos con enidos, como
pasa en qu . No obs an e, es a si uación es bas an e i ial de de ec a y e i a .
Además de las compa aciones p e ias, e aluamos ambién la e icacia de la ca-
che de ins ucciones bloqueable cuando se analiza con DLock-MS. Debido a que el
WCET dec ece linealmen e con espec o a la asa de acie os de la cache de ins uc-
ciones, si nues a asa de acie os en el camino del WCET es pa ecida a aquella en
la ejecución eal, podemos asegu a que nues os esul ados son lo su icien emen e
p ecisos. Además de es e modo e i amos que la peculia idades de los mé odos de
3.4. Resul ados 37
complex_upda es
coun nega i e
i 2dim
ii
janne_complex
j dc in
ma mul
ma ix1
bina ysea ch
bso
il e bank
selec
qso -exam
dijks a
s
c c
qu
min e
li
ndes
ludcmp
audiobeam
md5
pm
s a ema e
m e
basicma h
pe ine
g723_enc
( odos)
-O0
-O1
-O2
-O3
SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD SD
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
Caso de análisis de asa de acie os: simulación con LRU con encional (S) o camino WCET con DLock-MS (D)
Tasa de acie os en cache de ins ucciones
FIGURA 3.6: Compa ación de las asas de acie os en la cache de ins-
ucciones de nues a p opues a ( asa de acie os alcanzada a a és
del camino WCET analizado) y una simulación de ejecución ( asa de
acie os de una ejecución de simulación con una cache de ins uccio-
nes con encional), cuan o mayo mejo .
análisis del WCET en u bien el obje i o eal, es o es, se lige amen e mejo que la
co a del WCET alcanzada po o os mé odos es mucho menos impo an e que ace -
ca se al WCET eal del p og ama. Así mismo, compa amos los esul ados de nues a
cache de ins ucciones bloqueable con una cache de ins ucciones LRU pa a comp o-
ba que DLock-MS alcanza un ni el acep able de endimien o. Pa a ob ene las asas
de acie o eales usamos el simulado Gem5 2.0 [Bin+11] con igu ando una seg-
men ación equi alen e con una cache de ins ucciones LRU del mismo amaño. Po
o a pa e ob enemos la asa de acie os de la cache de ins ucciones bloqueable en el
peo camino de ejecución cuando se aplica DLock-MS. Como an es, es os esul ados
se p esen an a a és de boxplo s pa a cada benchma k y ni el de op imización.
La igu a 3.6 mues a que las asas de acie os en el peo camino con una cache
bloqueable son compa ables con aquellas con una cache LRU en odos los bench-
ma ks y ni eles de op imización, y en media es siemp e mejo en la cache bloquea-
da dinámicamen e (columna de la de echa). De hecho, hay muchos casos donde la
cache bloqueada dinámicamen e supe a la cache LRU. Es o signi ica que, pa a mu-
chos benchma ks, bloquea el código adecuado es p obable que uncione an bien o
mejo que la polí ica LRU, cuyo dinamismo puede expulsa con enido que se usa á
de nue o p on o. Po o o lado, los benchma ks cuya asa de acie os LRU es mayo
son mayo i a iamen e los que es án si uados a la de echa en la igu a 3.6. Es o es
cohe en e, ya que el dinamismo na u al de la cache LRU adap a su compo amien o
en es os benchma ks que son más g andes y complejos, mien as que la cache blo-
queable, incluso con una heu ís ica de bloqueo dinámico, iene un compo amien o
más es ingido.
38 Capí ulo 3. Reducción del WCET y del iempo de análisis
complex_upda es
coun nega i e
i 2dim
ii
janne_complex
j dc in
ma mul
ma ix1
bina ysea ch
bso
il e bank
selec
qso -exam
dijks a
s
c c
qu
min e
li
ndes
ludcmp
audiobeam
md5
pm
s a ema e
m e
basicma h
pe ine
g723_enc
( odos)
123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123
0.25
0.50
0.75
1.00
Ni el de op imización gcc (-O)
WCET con espec o a -O0
FIGURA 3.7: E ec os del ni el de op imización del compilado
(GCC 6.3.1) en el WCET (cuan o meno , mejo ).
3.4.3. Impac o del ni el de op imización del compilado
La mayo ía de es udios en sis emas de iempo eal deshabili an las op imizacio-
nes pa a que la conco dancia en e le código bina io y el de al o ni el sea más senci-
lla. Además, has a donde sabemos, ninguno de ellos ha ealizado un análisis exhaus-
i o sob e cómo a ec an las op imizaciones al peo caso de iempo de ejecución. De
mane a in ui i a podemos a i ma que las op imizaciones educen el iempo medio
de ejecución, así que, en gene al, debe ía educi se ambién el WCET. Sin emba go,
cualquie op imización que educe el iempo medio de ejecución inc emen ando el
iempo de ejecución en caminos in ecuen es, esul a á en un inc emen o del WCET
si es e se encuen a en uno de es os caminos inusuales. En es a sección es udiamos el
impac o en el WCET de los ni eles de op imización en compilación. Nos cen amos
en los esul ados pa a GCC 6.3.1, los esul ados pa a GCC 4.8.4 (no se mues an)
p esen an endencias casi idén icas.
La igu a 3.7 mues a cómo los ni eles de op imización a ec an al WCET. El eje x
ep esen a el WCET ela i o a compila sin ninguna op imización (-O0). Se p esen a
es a in o mación pa a cada benchma k más el ag egado de odos ellos en la pa e
de la de echa, y se ep esen an con boxblo s como an es. También podemos e una
línea ho izon al que indica el caso base (es deci , el WCET del bina io compilado
sin op imizaciones pa a cada expe imen o) en y=1. Po lo an o, cuan o más bajos
es én los bloxpo s, meno (mejo ) se á el WCET co espondien e pa a esa op imiza-
ción.
La obse ación más impo an e es que, en media, los boxplo s se si úan al ede-
do del 0,3. Es o signi ica que, en gene al, el WCET de un código op imizado se á en
o no a un e cio de su WCET sin op imizaciones. Po lo an o, se debe ían usa bi-
na ios op imizados en los sis emas de iempo eal. En media, los mejo es esul ados
se alcanzan con O3, aunque cada benchma k iene un compo amien o especí ico.
O o de alle in e esan e es que la mejo a del WCET no se debe (exclusi amen e)
al amaño del código del bina io op imizado. Los bina ios de O3 no malmen e son
mayo es que aquellos compilados con O1 y O2 ( e en la abla 3.2) y sin emba go
3.5. Conclusiones 39
p esen an un WCET meno .
Po ejemplo, el amaño de los bina ios O3 es al ededo de dos eces el amaño
de O2 en i 2dim, m e ,g723_enc,ii , cua o eces en ludcmp, y seis eces en com-
plex_upda es, y a pesa de ello O3 consigue un WCET meno . Es e es un pun o muy
impo an e a ene en cuen a ya que odos los expe imen os ealizados conlle an un
g an abajo pa a la cache que el amaño del bina io puede inc emen a sus ancial-
men e. Sin emba go, es as op imizaciones pueden ene ambién e ec os lige amen e
ad e sos pa a el WCET, como puede e se en bina ysea ch, dónde O3 es unas 7 eces
mayo que el amaño de O2.
Des aca el e ec o singula que encon amos en pe ine . Como se puede e , O2
y O3 mues an un WCET signi ica i amen e peo que O1. Es o se debe a las ans-
o maciones que se han lle ado a cabo en los bucles po es as op imizaciones. Es as
ans o maciones han de i ado en unos pa ones de bucle que de mane a inhe en-
e se sob es iman en el p oceso de análisis del WCET. A con inuación, explo amos
más p o undamen e en es e p oblema de análisis de cie os pa ones de bucle. De-
pendiendo del código uen e y el ni el de op imización, la dis ibución de bloques
básicos que con ienen la cabece a y el cue po del bucle pueden se o almen e dis-
in os. En la igu a 3.8 se mues an a ios pa ones de bucle, donde Nes el núme o
máximo de ejecuciones del cue po del bucle, que en nues os expe imen os ha sido
e ique ado manualmen e. En es a igu a, las cajas limi adas po líneas discon inuas
ep esen an uno o más bloques básicos, mien as aquellas limi adas po líneas con-
inuas ep esen an un solo bloque básico.
En el pa ón 1 (a) encon amos el bucle básico do-while. Solo hay una salida y es á
en el mismo bloque básico que uel e al inicio del bucle. Todos los bloques básicos
de es e bucle se ejecu an como mucho N eces.
El pa ón 2 (b) (un bucle while o o ) iene solo una salida, que es á en el bloque
básico de en ada (la cabece a) del bucle. Si el cue po del bucle se ejecu a N eces,
su cabece a se ejecu a N+1 eces.
Nos encon amos que en o os pa ones de bucle, como el 3 (c), puede se di ícil
o incluso imposible sabe dónde se encuen a la cabece a o el cue po del bucle, los
cuales pueden incluso es a in e calados con condiciones de salida de bucle, ambos
dis ibuidos a lo la go de a ios bloques básicos. Po lo an o, una ap oximación
segu a implica asumi que odos los bloques básicos implicados se ejecu an N+
1 eces. Es a ap oximación, aunque segu a, puede p oduci una sob es imación. Es e
es el caso de los bina ios O2 y O3 de pe ine en la igu a 3.7. En O1, es e benchma k
con iene 151 bloques básicos (de un o al de 161) que se ejecu an dos eces cada uno
en el peo caso, sin emba go en O3 se iene que asumi que se pueden ejecu a has a
3 eces. Es o inc emen a la co a del WCET en o no a 3/2, como se pude e en la
igu a 3.7.
3.5. Conclusiones
En es e capí ulo se ha p esen ado DLock-MS, una ex ensión del mé odo de anális
del WCET Lock-MS.
Nues o obje i o es educi el iempo de análisis del WCET en p esencia de una
cache de ins ucciones bloqueable. Nues a ex ensión implemen a p incipalmen e
dos mejo as.
La p ime a es un algo i mo pa a ans o ma el CFG en una es uc u a en á bol,
necesa ia pa a usa Lock-MS como un mé odo de análisis del WCET basado en la

40 Capí ulo 3. Reducción del WCET y del iempo de análisis
(b) Pa ón 2
N+1
N
(a) Pa ón 1
N
(c) Pa ón 3
N+1
N+1
N+1
FIGURA 3.8: Va ios pa ones de bucle encon ados en el código bina-
io.
es uc u a. Es e algo i mo gene a un á bol cuyo modelo ILP puede esol e se á-
cilmen e a a és de una ami icación y poda in e ida. Es as ans o maciones se
ealizan en una sola pasada, p ocesando cada camino al e na i o una sola ez. El
á bol esul an e iene muchos menos caminos a explo a que el CFG o iginal, lo cual
educe el iempo de análisis del WCET sin sac i ica p ecisión pa a una cache de
ins ucciones bloqueable.
La segunda mejo a es una heu ís ica de bloqueo dinámico basada en los bucles,
aplicada en los bucles ex e nos, que pe mi e ob ene el con enido óp imo de cache
pa a el WCET de cada egión, es deci , la con igu ación que minimiza el WCET en
cada egión. La complejidad de es a heu ís ica es muy baja, educe el WCET ex-
plo ando de mane a e ec i a el euso empo al, y educe oda ía más el iempo de
análisis del WCET aislando el WCET de cada egión.
Los esul ados mues an que DLock-MS es al ededo de 10 eces más ápido que
O awa, una he amien a del es ado del a e basada en AbsIn eIPET. Debido a su
apidez es e análisis del WCET pude se muy signi ica i o en el p oceso de diseño
de un sis ema de iempo eal y una al e na i a al análisis pa amé ico del WCET.
Además, nues o análisis puede de ene se an es de comple a se, p opo cionando,
incluso en es e caso, un WCET segu o y una con igu ación pa a la cache bloqueable
que lo ga an iza. Es o quie e deci que cualquie solución de nues o modelo es se-
gu a, y que es al comple a el análisis cuando se ga an iza el WCET óp imo (mínimo)
pa a cada egión.
También e aluamos la e icacia de DLock-MS, con i mando que educe el WCET
espec o al mé odo o iginal Lock-MS, y compa amos su asa de acie os en una cache
bloqueable con una con encional LRU. Nues os esul ados mues an una asa de
acie os muy simila en odos los benchma ks, siendo la cache bloqueable la que
o ece mejo es asas de acie os en muchos de ellos. Hay que des aca ambién que
es os esul ados se consiguen con un ha dwa e muy sencillo, mucho más que una
cache con encional LRU.
Finalmen e, es udiamos el impac o de los ni eles de op imización en el WCET.
Nues a conclusión es que se deben desca a las compilaciones sin op imización
(-O0) ya que gene an bina ios con un WCET en e 3 y 4 eces peo que con la p e-
sencia de op imizaciones. En gene al, O3 gene a los bina ios con los WCETs más pe-
queños, pe o o os ni eles de op imización son ambién muy e icaces. Sin emba go,
op imizaciones ag esi as en algunos benchma ks pueden supone un inc emen o
3.5. Conclusiones 41
signi ica i o del WCET. Es as op imizaciones pueden cambia los pa ones de bucle
de mane a que el mé odo de análisis del WCET se e o zado a asumi i e aciones
adicionales en los bucles pa a ga an iza la segu idad del análisis.
Es e abajo ha sido publicado en [Ped+20b].
43
Capí ulo 4
Impac o de la ec o ización
au omá ica en el WCET
En es e capí ulo con inuamos el es udio del análisis del WCET conside ando
las ins ucciones esul an es de la ec o ización au omá ica. Desde los años 80 los
mic op ocesado es come ciales han es ado añadiendo cons an emen e ex ensiones
ec o iales a su epe o io de ins ucciones y ecu sos ha dwa e pa a pode ejecu a
e icien e es as ins ucciones ec o iales. Sin emba go, su impac o en el WCET no se
ha es udiado en p o undidad debido a la al a de sopo e de las ins ucciones ec o-
iales en las he amien as ac uales de análisis del WCET. Es e se á en onces el obje o
de es e capí ulo. Gene amos el código ec o izado de mane a au omá ica desde el
código uen e a a és de las unciones que p opo cionan los compilado es ac uales.
Después, pa iendo de las especi icaciones empo ales de los ab ican es es udiamos
las pa es ec o izadas pe mi iéndonos aco a su apo ación al WCET de la a ea. Fi-
nalmen e, in eg amos las co as ob enidas en el análisis del WCET de la a ea co es-
pondien e. Como esul ado ob enemos que el WCET se educe si se ec o izan los
bucles que concen an la mayo pa e del iempo de ejecución. Además, la e icien-
cia de la ec o ización au omá ica en las he amien as de compilación es bas an e
limi ada, po lo que cabe espe a más bene icios en benchma ks más g andes o si se
eesc ibe el código.
4.1. In oducción
Independien emen e del mé odo de análisis del WCET, mejo a una a ea en los
sis emas de iempo eal es ic o signi ica educi la co a calculada del WCET, aunque
es o suponga inc emen a el iempo medio de ejecución. Po el con a io, no siemp e
que se educe el iempo medio de ejecución a a e se educido el WCET. A es e
espec o, las mejo as mic oa qui ec u ales como la memo ia cache han demos ado
educi el iempo medio de ejecución pe o no el peo caso de ejecución, al y como
hemos is o. En es e capí ulo, nos cen amos en o a mejo a mic oa qui ec u al: la
ec o ización, que explo a el pa alelismo de da os, analizando su e ec o en el WCET.
El p ocesado In el Pen ium MMX popula izó la ec o ización a mediados de los
años 90 y ac ualmen e encon amos que exis en p ocesado es de dis in os ab ican-
es que inco po an en su epe o io de ins ucciones (ins uc ion se a chi ec u e, ISA)
las llamadas ex ensiones ec o iales. Es as ex ensiones u ilizan un ipo de pa alelis-
mo en las que cada ins ucción de ine una ope ación que se aplica simul áneamen e
en los elemen os de un ec o (single ins uc ion mul iple da a, SIMD). Desde su apa-
ición, la ec o ización ha demos ado ampliamen e su solidez an o en aplicaciones
50 Capí ulo 4. Impac o de la ec o ización au omá ica en el WCET
De odo nues o epe o io de benchma ks encon amos que el compilado no ha
p oducido ninguna ec o ización del código en 18 de ellos1. Es e hecho nos señala
que es necesa io segui abajando pa a iden i ica si es a al a de pa alelismo ec-
o ial es eal o si po el con a io puede subsana se con ans o maciones sencillas
del código o de los da os. Debido a que nues o p opósi o es compa a benchma ks
en sus e siones escala y ec o izada, aquellos en los que la ec o ización no ha
su ido e ec o se han desca ado. Además en es e capí ulo u ilizamos el benchma k
ma mul _op i en ez de ma mul pa a acili a su ec o ización.
Cabe des aca que aunque hay a ios benchma ks de la sui e TACLeBench cuyo
algo i mo coincide con o o benchma k de Mäla dalen (bina ysea ch/bs,coun nega i-
e/cn ,j dc in / dc ,pe ine /nsichneu), su compo amien o al se ec o izados po el
compilado no coincide ya que es e esul ado depende en g an medida del código
en al o ni el. De hecho, de es as duplas, la única que de la que se ob iene una ec o-
ización de la sui e de Mäla dalen es el benchma k cn . Es e hecho e ue za la idea
de la impo ancia de una p og amación que acili e la ec o ización.
El núme o de i e aciones de los bucles escala es que se dan en el peo caso es á
ano ado en el código uen e de los p og amas. Es as ano aciones o bien se encon-
aban ya en el código o iginal del benchma k o las hemos añadido noso os ma-
nualmen e. En el caso del núme o de i e aciones en los bucles ec o iales se han
calculado al como se expone en la sección 4.3.1.
4.5. Resul ados expe imen ales
En es a sección, e aluamos el impac o que iene en el WCET la ec o ización de
código en los benchma ks de iempo eal. Calculamos el WCET de nues os bench-
ma ks con nues o en o no de análisis es á ico de bina ios (sección 4.3) basado en
OTAWA [Bal+10] y Lock-MS [Apa+11]. Pa a cada uno de los benchma ks p oduci-
mos dos bina ios dis in os. Uno se ha gene ado ac i ando la ec o ización au omá-
ica de bucles del compilado GCC 4.8.4 mien as que el o o bina io se ha gene ado
e i ando es a ec o ización. El es o de opciones de compilación es án de alladas en
la sección 4.4.1.
En las es columnas más a la de echa de la abla 4.2 encon amos in o mación
adicional que nos pe mi e mos a la e icacia del compilado GCC 4.8.4 ec o izando
los bucles del código uen e de cada benchma k.
En conc e o, se mues a el núme o de bucles que han sido ec o izados po el
compilado (Columna Vec .), el núme o de bucles que no se han ec o izado (Co-
lumn No-Vec .), y el núme o de elemen os que se p ocesan simul aneamen e en cada
i e ación de los bucles ec o izados (Columna Vías).
En el caso de j dc in ,md5 ypm, los ipos de da o de los bucles ec o izados son
en e os de 32-bi y ca ac e es así que el núme o de elemen os que se p ocesan simul-
áneamen e son 4 y 16, espec i amen e. El hecho de que la ec o ización au omá ica
de GCC 4.8.4 haya uncionado en solo 17 de 35 benchma ks, pa ece indica que la au-
o ec o ización de es e compilado es bas an e limi ada. Segu amen e eesc ibiendo
algunas pa es del código o iginal pod íamos acili a es a ec o ización au omá ica,
pe o es a a ea a más allá del p opósi o de es e abajo.
La igu a 4.3 mues a la mejo a ela i a del código ec o izado sob e el código
no ec o izado pa a cada benchma k. Asumimos una cache de ins ucciones blo-
queable de mapeo di ec o de 128 by es, con líneas de cache de 32 by es. También
1byna ysea ch, bs, c c, dijks a, dc , ii , janne_complex, ludcmp, ma mul , ndes, nsichneu, pe ine , qso -
exam, qu , selec , s , s a ema e, min e .

4.5. Resul ados expe imen ales 51
audiobeam
basicma h
bso
cn
complex_upda es
coun nega i e
il e bank
i 2dim
m e
g723_enc
j dc in
li
ma mul _op i
ma ix1
md5
pm
A F A F A F A F A F A F A F A F A F A F A F A F A F A F A F A F A F
1.0
1.5
2.0
2.5
3.0
La encia de da os (A: Siemp e acie o, 1 ciclo; F: Siemp e allo, 10 ciclos)
WCET no- ec o izado/ WCET ec o izado
FIGURA 4.3: Compa ación del impac o de la ec o ización en el
WCET.
asumimos la p esencia de un line-bu e : una cache con encional (dinámica) de ins-
ucciones de solo una línea de cache [Apa+11;PD02]. Po an o, el mé odo de aná-
lisis del WCET con abiliza los acie os (1 ciclo) y allos (11 ciclos) en la búsqueda de
ins ucciones.
Conside amos dos escena ios di e en es que dan una pe spec i a de la impo -
ancia de la cache de da os (ya sean escala es o ec o iales). El p ime escena io (A)
co esponde a una je a quía de cache de da os ideal donde cada acceso a da os e-
sul a siemp e en acie o. En el segundo escena io (F), los accesos a da os siemp e
esul an en allo y se penalizan con 10 ciclos debido a la la encia de memo ia. P oba-
blemen e es e úl imo escena io se ace ca más a la ealidad ya que no malmen e las
ins ucciones ec o iales en los p ocesado es come ciales ac uales omi en a la cache
de da os L1 y solici an los da os que necesi an di ec amen e a L2.
Des acan los esul ados de la ec o ización en el caso de ma mul _op i yma ix1
ya que son has a 3 eces mejo que la e sión no ec o izada. Es e alo es muy
ce cano al máximo espe ado cuando 4 elemen os se p ocesan simul áneamen e, que
esul a ía una mejo a de 4 ( e abla 4.2). Al inspecciona manualmen e el bina io
ec o izado descub imos que el bucle que con iene la mayo ca ga compu acional
se ha ec o izado especialmen e bien y que no se ha necesi ado un bucle de epílogo.
Es os casos mues an que las ins ucciones ec o iales educen de o ma e ec i a el
WCET. Pa a o os benchma ks como ,g723-enc yli , a pesa de que algunos de sus
bucles se han ec o izado, no consiguen una mejo a mayo del 1.25. En es a ocasión,
los bucles ec o izados no o man pa e de donde se concen a la mayo pa e de la
ejecución, así que la mejo a es meno .
Desa o unadamen e, en algunos benchma ks, (audiobeam,basicma h,bso and
il e bank) el endimien o del bina io ec o izado es peo que el no ec o izado. En
es os casos el núme o de i e aciones es especialmen e pequeño compa ado con o os
benchma ks. Po ejemplo, el bucle ec o ial en basicma h se ejecu a una sola ez. Es e
no puede compensa el sob ecos e gene ado en el código al ec o iza el bucle. Es o
es, el código en el que se elige en e el bucle escala o ec o ial, las ins ucciones
adicionales que los bucles ec o iales necesi an pa a p epa a el eco ido del bucle
52 Capí ulo 4. Impac o de la ec o ización au omá ica en el WCET
(po ejemplo, la p opagación de cons an es en las ías de un egis o ec o ial) y los
allos adicionales en la cache de ins ucciones que el código ec o ial pueda causa .
De odos modos, nues a ecomendación es compa a los WCET de las e siones
escala es y ec o iales y elegi el mejo de ellos, es deci , el meno .
4.6. Conclusiones
En es e capí ulo analizamos la e icacia del código ec o izado en el WCET es-
udiando las p es aciones de la ec o ización au omá ica de GCC en paque es de
benchma k de iempo eal. T as analiza los código ec o iales, se in eg an sus espe-
ci icaciones empo ales co espondien es en la he amien a de análisis del WCET.
Nues os esul ados mues an que el WCET se educe de mane a e ec i a cuando
los bucles ec o izados o man pa e del código dónde se lle a a cabo la mayo pa e
de la ejecución. Po ejemplo, en la e sión ec o ial del benchma k ma mul _op i el
WCET se educe po un ac o de 3 espec o a la e sión escala . Sin emba go, sus
bene icios no esul an an e iden es como se espe aba, debido, en pa e, a la e icacia
limi ada que o ecen las he amien as de compilación en la ec o ización au omá-
ica. Se pod ía sol en a eesc ibiendo el código uen e de mane a que se acili a a
la ec o ización au omá ica o incluso esc ibiendo explíci amen e el código ec o ial,
pe o la e icacia de es a ec o ización depende á de la habilidad de quien p og ama.
El núme o de i e aciones de los bucles en algunos de los benchma ks de iempo
eal que hemos analizado es bas an e pequeño, p obablemen e po que es os bench-
ma ks son simples ke nels, es deci , ope aciones/algo i mos que o man pa e de los
núcleos de p og amas de iempo eal mucho mayo es. Po lo an o, el núme o de
i e aciones no es lo su icien emen e g ande pa a compensa el sob ecos e de u iliza
código ec o ial. En es os casos, se debe e i a la ec o ización. Como conclusión,
pensamos que nues os esul ados omen an el uso de los ecu sos ec o iales en
sis emas de iempo eal es ic o, posiblemen e esc ibiendo códigos con el pa alelis-
mo de da os en men e, al como puede se el benchma k ma mul _op i que se ha
p esen ado en la sección 4.4.3. Ac ualmen e, como los ecu sos del chip con inúan
c eciendo, el p ocesamien o ec o ial es a con i iéndose en una u ilidad básica en
los mayo ía de los p ocesado es del me cado. Es e abajo pod ía con inua se en el
u u o examinando con más de enimien o los benchma ks que no han podido ec-
o iza se, pa a encon a a qué se debe. Pa a ello se end ía que e alua la can idad
de pa alelismo en da os y comp oba el es ilo de p og amación buscando cons uc-
ciones que di icul en la ec o ización al como pun e os, euso escala a a és de
dis in as i e aciones, ec o es no alineados, e c.
53
Capí ulo 5
Tasa ideal y p edecible de acie os
pa a la ansposición de ma ices
en caches de da os
T as conclui en los capí ulos an e io es el g an impac o de la la encia en la je a -
quía de memo ia en el WCET y explo a dis in as ías an o pa a agiliza su análisis
como pa a educi el p opio WCET, en es e capí ulo, analizamos un algo i mo un-
damen al en los sis emas de iempo eal: la ansposición de ma ices. Analizamos
el núme o de accesos y asa de acie os en cache de da os, cuyo e ec o es de g an
ele ancia en el cálculo de su WCET.
Una ansposición de ma ices es una ope ación básica. Sin emba go, su asa de
acie os en cache de da os pa a g andes ma ices es muy baja y no se puede p edeci
ácilmen e. En el con ex o de iempo eal es imp escindible que la asa de acie os
(su peo caso) se pueda p edeci de mane a segu a. En es e capí ulo ob enemos la
elación en e los pa áme os de cache que ga an izan la asa (p edecible) ideal de
acie os en da os omando una cache de da os LRU.
T as ello y eniendo en cuen a nues as alo aciones analí icas compa amos los
algo i mos de ansposición de ma ices iling ycache-obli ious. El esul ado de es-
a compa ación demues a que, con el amaño adecuado de ile, la e sión iling
del algo i mo ob iene una asa de acie os en da os igual o mejo . Adicionalmen e
analizamos el consumo de ene gía y el iempo de ejecución de la ansposición en
ha dwa e eal con caches PLRU.
G acias a que nues o análisis de acie os y allos p opo ciona co as pa a el peo
caso podemos pe mi i el uso de caches de da os LRU (poco p edecibles en gene-
al) pa a la ansposición de ma ices en sis emas de iempo eal. Además, nues as
alo aciones analí icas pe mi en es ingi sin ningún impac o nega i o los ecu sos
dedicados a la ansposición de ma ices. Se consigue así educi an o la con amina-
ción a o os p ocesos como el consumo de ene gía, lo que es ealmen e ú il en gene al
y especí icamen e en la compu ación de al o endimien o.
5.1. In oducción
La ansposición de ma ices es una ope ación undamen al en á eas ales como
el álgeb a lineal o las ans o madas de Fou ie . Además iene muchas aplicacio-
nes en o as como el análisis numé ico, el p ocesado de imágenes y g á icos. Hay
muchos ejemplos de aplicaciones desa olladas en los cen os de supe compu ación
que usan, de un modo u o o, la ansposición de ma ices como pa e esencial pa a
soluciona sus p oblemas [RJ16;Bal+16].
54 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
Aunque la ansposición en sí misma es un p oblema bas an e simple, cuando
omamos ma ices de g an amaño p esen a una asa de acie os en cache de da os
muy pequeña [CS00]. Es o se debe a que aunque los elemen os po ilas son acce-
didos consecu i amen e se in e calan con el eco ido po columnas que conlle a la
ansposición. El que los elemen os se accedie an consecu i amen e po ilas ha ía
posible que encajasen en la misma línea de cache y po lo an o hubie a euso empo-
al. Sin emba go, la in e e encia del acceso po columnas conlle a que los acie os
po enciales acaban gene ando allos po capacidad.
Exis en ans o maciones de código conocidas y usadas de mane a habi ual pa-
a sol en a es e p oblema. La ans o mación iling oblocking es á p esen e en las
biblio ecas de al o endimien o (p.e. In el MKL, NVIDIA cuBLAS) y consis e en di-
idi odo el p oblema en pequeños iles (« eselas») que quepan en la cache [LRW91]
y con los que se puede abaja de mane a independien e. Al anspone los iles
comple amen e uno de ás de o o (o po pa ejas) pe mi e que los iles implicados
pe manezcan en cache mien as se es án p ocesando, e i ando así los allos po ca-
pacidad.
Aunque aplica e icien emen e una ans o mación de iling inc emen a la asa
de acie os en la cache de da os oda ía podemos encon a dos impo an es des-
en ajas. P ime o, añadi bucles implica añadi más ins ucciones pa a pode lle a
a cabo la ansposición de ma ices, con su co espondien e iempo de ejecución. La
segunda des en aja que enemos que conside a es que la asa de acie os del códi-
go ans o mado es á in luenciada po el amaño de la ma iz a anspone y po la
con igu ación especí ica de la cache del sis ema co espondien e (es deci , núme o
de conjun os y ías, amaño de línea de cache, polí ica de eemplazo, p ebúsqueda,
cache íc ima, e c.). Es os incon enien es se han abo dado desde la pe spec i a de
op imización de compilado es a ando de minimiza el núme o de allos en cache
que se gene an desde el código bina io [Bao+18].
Cuando abajamos con sis emas de iempo eal es as des en ajas se uel en
c í icas ya que se debe conc e a el peo iempo de ejecución (WCET) en el momen o
del diseño [Rei+07].
Po es a azón si los acie os y allos no se pueden p edeci con an elación el
sis ema de iempo eal se diseña á asumiendo una sob e-es imación en su compo -
amien o, lo que nos lle a á a desap o echa los ecu sos ha dwa e e inc emen a
el consumo de ene gía. Además, los sis emas de iempo eal necesi an p edicciones
segu as así que no se pueden aplica écnicas que no ga an icen el esul ado del
peo caso. También es os incon enien es son impo an es en la compu ación en la
nube ya que las con igu aciones de las caches de las máquinas i uales u ilizadas y
conocidas pueden no coincidi con las máquinas ísicas y además se desconocidas.
Po o o lado podemos usa un algo i mo cache-obli ious de ansposición de ma-
ices. Es e algo i mo es, esencialmen e, una e sión ecu si a del algo i mo de iling
(has a alcanza iles de 2 ×2 elemen os) po lo an o el endimien o óp imo de la ca-
che se alcanza po su p opia na u aleza ecu si a y su con igu ación no depende de
los pa áme os de la cache.
Como concluyen Tsi akis e al [TRS04]: «No es i ial p edeci a p io i como a a
se el endimien o del algo i mo cache-obli ious», po lo an o pe sis en las des en a-
jas an e io men e p esen adas. No obs an e es e algo i mo e i a ene que añadi un
pa áme o ex a que ene en cuen a: el amaño de ile.
Independien emen e de como implemen emos la ansposición de ma ices, has-
a donde alcanza nues o conocimien o, no hay ningún abajo p e io que p opo -
cione una alo ación analí ica de acie os/ allos de es e p oblema. Sin es e análisis
se puede es udia la endencia del endimien o pa a unos pa áme os especí icos
5.2. Es udios p e ios 55
de cache pe o no a a se posible ajus a de o ma p ecisa es os pa áme os y de la
misma mane a ampoco se a a pode da una p edicción concisa del endimien o.
Pa a abo da es e p oblema es udiamos la ansposición de ma ices desde una
pe spec i a eó ica y cómo a ec an a la asa de acie os an o los pa áme os de cache
(núme o de conjun os, ías y amaño de línea) como el padding (« elleno») aplicado
a la ma iz pa a el algo i mo iling y una cache con polí ica de eemplazo LRU.
Validamos las exp esiones analí icas ob enidas en nues o es udio a a és de
simulaciones en las que conside amos un amplio ango de pa áme os. Y ambién
compa amos nues os esul ados con los de una implemen ación cache-obli ious me-
jo ada con una nue a écnica de padding que hemos denominado phan om padding
(« elleno an asma»). Pa a e mina analizamos el endimien o de una ansposición
de ma ices en ha dwa e eal (con una con igu ación especí ica de cache) que nos
pe mi i á e i ica si se cumplen nues as p edicciones eó icas.
El es o del capí ulo se es uc u a de la siguien e mane a. En la sección 5.2 p e-
sen amos el abajo elacionado con el es udio del compo amien o en cache de la
ansposición de ma ices. En la sección 5.3 p esen amos el o den de acceso de las
di e en es implemen aciones de la ansposición de ma ices. A con inuación en la
sección 5.4 calculamos las asas ideales de acie o pa a la ansposición de ma ices
independien emen e de la cache y del ipo de algo i mo. En la sección 5.5 analiza-
mos qué con igu aciones de cache LRU son necesa ias pa a alcanza es as asas. En
la siguien e sección 5.6 p oponemos un padding ex a que pe mi e alcanza la asa
ideal de acie os con menos ecu sos de cache. Todas las exp esiones analí icas ob e-
nidas en es as secciones son alidadas po medio de simulaciones ex ensi as en la
sección 5.7. En es a sección, además, los esul ados ob enidos se compa an con aque-
llos p opo cionados po el algo i mo cache-obli ious. Finalmen e, las conclusiones de
es e capí ulo se exponen en la sección 5.8.
5.2. Es udios p e ios
En es a sección examinamos algunos abajos que analizan el compo amien o
de acie os y allos de la cache de a ios algo i mos de ansposición de ma ices.
Debido a que el algo i mo de ansposición de ma ices es bas an e simple y ha-
ce un uso in ensi o de memo ia nume osos abajos se han cen ado en a a de
analiza y mejo a el uso de la je a quía de memo ia.
Se han in es igado dos al e na i as pa a ges iona el pa ón de accesos en una
cache pa a es e algo i mo al y como se han in oducido en es e capí ulo: iling y
cache-obli ious. Ambos en oques buscan expone a la je a quía de memo ia a un pa-
ón de acceso de da os que explo e el euso (espacial y empo al) en la cache subya-
cen e [F i+99;LRW91;CS00;TRS04;Yo +07;Lei03;F i+12]. A con inuación, p esen-
amos las di e encias en e los abajos elacionados y el nues o.
Cache-E icien Ma ix T ansposi ion Re e ence [CS00] desc ibe a ios algo i mos de
ansposición de ma ices y compa a su endimien o usando an o simulación co-
mo ejecuciones eales en un sis ema basado en Sun Ul aSPARC II. A a és de las
simulaciones se mues a que el algo i mo cache-obli ious es el que iene menos nú-
me o de allos pa a ma ices de pequeño amaño. Sin emba go, ocu e al con a io
pa a ma ices g andes ya que es el que p esen a mayo núme o de allos. Además,
los iempos de ejecución p esen ados mues an que, en la mayo ía de los casos, el
algo i mo cache-obli ious es signi ica i amen e más len o que los o os algo i mos
analizados. En el es udio se sugie e que la azón po la que el endimien o no es el
espe ado es po que no hay su icien e asocia i idad. Si lo compa amos con nues o

56 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
en oque, su análisis se limi a a una e aluación expe imen al sin p opo ciona nin-
guna alo ación analí ica de acie os y allos de los di e en es algo i mos.
Cache Obli ious Ma ix T ansposi ion: Simula ion and Expe imen Re e ence [TRS04]
analiza en mayo p o undidad el algo i mo de ansposición de ma ices cache-obli ious
con la in ención de acionaliza los esul ados de Cha e jee y Sen [CS00]. Es udian
el endimien o del algo i mo, con espec o a los allos en cache, an o con simu-
lación como con con ado es ha dwa e en dos sis emas Sun Ul aSPARC comple a-
men e dis in os en e sí. Como en nues o abajo, compa an los algo i mos iling y
cache-obli ious pe o se cen an en el compo amien o de es e úl imo. Sin emba go,
analizan solo una con igu ación especí ica de cache y un solo amaño de ile, a ian-
do únicamen e el amaño de la ma iz. Sus esul ados mues an que los allos en
cache se ca ac e izan po un pa ón bas an e es uc u ado que depende de la con i-
gu ación de la cache y del amaño de la ma iz. No obs an e, no de e minan cuándo
el algo i mo cache-obli ious a a ene un buen o un mal endimien o, sino solamen e
que inc emen ando el núme o de ías de la cache se mejo a la asa de acie os. En
nues o abajo, e aluamos analí icamen e es a cues ión.
The Cache Pe o mance and Op imiza ions o Blocked Algo i hms Re e ence [LRW91] se
cen a en op imiza el endimien o de la cache a a és del ans o mación blocking
( iling) de algo i mos. Su en oque consis e en, p ime o, mos a el compo amien-
o de caches bajo iling, pa a después mejo a su endimien o a a és de écnicas
so wa e y/o ha dwa e. Analizan el algo i mo de mul iplicación de ma ices en su
e sión iling y concluyen que el endimien o de la cache es ex emadamen e de-
pendien e del amaño del p oblema y del ile. También a i man que las asas de allo
ienen una g an sensibilidad con espec o al amaño de la ma iz. Sin emba go, como
e emos en nues a p opues a, un ajus e p eciso del algo i mo iling de ansposición
p opo ciona a quien p og ama muchos más g ados de libe ad.
An Expe imen al Compa ison o Cache-obli ious and Cache-conscious P og ams Re-
e ence [Yo +07] compa a de mane a expe imen al un p og ama cache-obli ious con
uno cache-conscious (cache conscien e, iene aplicado la ans o mación de iling) an-
o pa a la mul iplicación como pa a la ansposición de ma ices. A i man que hay
un sob ecos e que pagan los p og amas cache-obli ious po su habilidad pa a adap-
a se au omá icamen e a la je a quía de memo ia. También de e minan que incluso
aquellos p og amas cache-obli ious que es án al amen e op imizados ienen un en-
dimien o signi ica i amen e peo que su espec i o p og ama cache-conscious.
Sin emba go, a di e encia de noso os, no analizan un ex enso ango de con igu-
aciones de cache ni de amaños de ile debido a limi aciones expe imen ales.
En gene al, conside amos al compa a es os abajos que pa a lle a a cabo sus
expe imen aciones e implemen aciones muchos de ellos usan un amaño de ma iz
múl iplo del amaño de línea de la cache y del amaño de ile lo cual acili a el análi-
sis [CS00;LRW91;TRS04] y o os conside an el padding como una écnica pa a e i a
es a es icción pe o no e alúan analí icamen e sus e ec os [Yo +07].
De odos modos, ninguno ha conside ado las colisiones en los conjun os de la
cache en el caso de ilas consecu i as de la misma columna, que es el caso p inci-
pal de acceso a las columnas en la ansposición. Noso os abo damos es a cues ión
añadiendo un padding adicional, el ow-shi padding [Hon+16;Pan+99;Bac+94]. Exis-
e o o p oblema más pa a el algo i mo cache-obli ious de ansposición de ma ices,
que ha á que se bene icie de la aplicación de un phan om padding (has a dónde sa-
bemos una p opues a o iginal de nues o abajo) que ambién analiza emos en es e
capí ulo.
5.3. Implemen aciones de la ansposición de ma ices 57
5.3. Implemen aciones de la ansposición de ma ices
En es a sección examinamos los eco idos de las di e en es implemen aciones
de la ansposición de ma ices ya in oducidas en es e capí ulo. Es as p opues as
p e endenden inc emen a la asa de acie os en cache de da os (obje o de nues o
es udio) a íando el o den de acceso a los elemen os de la ma iz y, po an o, a
las líneas de cache que los con ienen de e minando su p esencia en la cache (con el
consecuen e allo o acie o en el acceso) según la polí ica de eemplazo.
En la igu a 5.1 se mues an el o den de acceso a los elemen os de una ma iz
8×8 pa a cada uno de los algo i mos:
Simple: Reco e la ma iz po ilas in e cambiando sus elemen os en la posi-
ción (i,j)po aquellos en la posición (j,i). Es a implemen ación es simple pe o
p esen a una asa de acie os muy pequeña en g andes ma ices ya que no se
bene icia del euso empo al. En la igu a 5.1(a) se mues a es e compo amien-
o.
Tiling: di ide odo el p oblema en pequeños iles (« eselas») que quepan en la
cache [LRW91] y con los que se puede abaja de mane a independien e. Es o
pe mi e un aumen o de la asa de acie os g acias al euso empo al. Básica-
men e es a ans o mación consis e en añadi bucles ex e nos al código o iginal
de modo que la secuencia de accesos globales no se ex iende a oda la memo ia
sino que se localiza en el p oceso de cada ile. En la igu a 5.1(c) encon amos
un ejemplo con amaño de ile 4 ×4 elemen os. La ma iz se di ide en 4 i-
les, aquellos que pe enecen a la diagonal se ansponen sob e si mismos y los
o os se ansponen en e sí po pa ejas (siguiendo uno un eco ido po ilas,
y el o o po columnas). En cada ile se aplica in e namen e el eco ido del
algo i mo «Simple». Análogamen e, en la igu a 5.1(d) se mues a el algo i mo
iling si de e minamos un amaño de ile 2 ×2 elemen os.
Cache-obli ious: Es e algo i mo es, esencialmen e, una e sión ecu si a del al-
go i mo de iling po lo an o el endimien o óp imo de la cache se alcanza po
su p opia na u aleza ecu si a. Es deci , un algo i mo cache-obli ious no p ecisa
conoce explíci amen e ningún pa áme o de la con igu ación de la cache.
Tal como se mues a en la igu a 5.1(b), el algo i mo di ide p ime o la ma iz
en iles de 4 ×4 elemen os pa a di idi cada una en iles de 2 ×2. La p incipal
di e encia en el eco ido con el algo i mo iling con iles de 2 ×2 elemen os es
el o den en la que eco e los iles, como se puede ap ecia en la igu a.
5.4. Tasas ideales en cache de da os pa a la ansposición de
ma ices
La asa de acie os en cache de da os es el po cen aje de accesos de da os que
p oducen acie os en cache. Llamamos asa ideal de acie os a aquella que se p odu-
ci ía en una cache de capacidad ilimi ada. Conc e amen e conside amos una cache
con un núme o ilimi ado de líneas, inicialmen e acía, y con un amaño de línea ca-
paz de almacena Lelemen os de la ma iz a aspone (1 ≤L∈N). Además, la
asa ideal de acie os solo iene en cuen a los allos obliga o ios y no los allos po
capacidad, po con lic o o la secuencia de accesos del algo i mo de ansposición.
No obs an e, el algo i mo 2, que implemen a una ansposición de ma iz di ec a, es
deci , sin ans o maciones ni op imizaciones, se puede usa como e e encia.
58 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
(a) Simple. (b) Obli ious.
(c) Tiling 4 ×4. (d) Tiling 2 ×2.
FIGURA 5.1: O den de acceso a los elemen os de una ma iz 8×8 pa a
cada uno de los algo i mos es udiados de ansposición de ma ices.
El colo solo apo a una guía isual de los eco idos y di isiones po
iles.
Algo i mo 2 T ansposicionDeMa iz(Ma ix,N): T anspone una ma iz N×N.
1: o indice1←1 o Ndo # N i e aciones
2: o indice2←indice1+1 o Ndo # N i e aciones
3: emp ←Ma ixindice1,indice2# Lec u a de memo ia
4: Ma ixindice1,indice2←Ma ixindice2,indice1# Lec u a y esc i u a de memo ia
5: Ma ixindice2,indice1← emp # Esc i u a en memo ia
6: end o
7: end o
C ea modelos de casos ideales esul a ú il pa a de e mina las co as del mejo es-
cena io de asa de acie os dada una de e minada con igu ación de cache, mapeo de
elemen o a línea o algo i mo. Comenzamos conside ando que solo los elemen os que
se an a anspone en la ma iz an a se enidos en cuen a pa a los allos en cache,
po lo an o se excluyen los elemen os de la diagonal y como esul ado ob enemos
una co a supe io pa a cualquie asa ideal de acie os. A con inuación mos amos
ambién las asas ideales de acie os incluyendo los e ec os del padding. Conside a-
mos una ma iz N×Npa a anspone , con sus elemen os almacenados po ilas,
alineada con el amaño de línea de cache. Todos los esul ados que se p esen an en
es e capí ulo son álidos ambién pa a elemen os almacenados po columnas pe o,
po simplicidad, a a emos solo uno de los casos. También asumimos que la ma iz
inal, ya anspues a, se sob esc ibe en la ma iz inicial y no se usan o as es uc u as
de memo ia más allá de egis os.
5.4. Tasas ideales en cache de da os pa a la ansposición de ma ices 59
FIGURA 5.2: Di e en es mapeos de memo ia cuando se aplica padding
a una ma iz N×Ncon líneas de cache que con ienen Lelemen os:
(a) = (Nm´
od L) = 0, (b) =1, (c) =3.
5.4.1. Co a de la asa ideal de acie os con una línea de cache que con iene
L elemen os
Teniendo en cuen a las conside aciones an e io es se puede calcula ácilmen-
e una co a supe io pa a la asa ideal de acie os. Excep uando los elemen os dia-
gonales, odos los elemen os (N2−N) se acceden an o pa a se leídos como pa a
se esc i os en memo ia, lo que nos da 2(N2−N)accesos en o al. Si asumimos
que los N2−Nelemen os caben pe ec amen e en las líneas de cache, end emos
(N2−N)/L allos obliga o ios. Di idi po Limplica implíci amen e que los ele-
men os de la diagonal no compa en su línea de cache con o os elemen os. Aunque
asumi es o no es ealis a (complica ía de hecho cualquie acceso indexado), p opo -
ciona la siguien e co a supe io pa a la asa de acie os ideal:
1−(N2−N)/L
2(N2−N)=1−1
2L(5.1)
Sin emba go, pa a calcula o as asas ideales de acie os end emos que analiza
la elación en e el amaño de la ma iz y el amaño de línea de cache.
5.4.2. Tasa ideal de acie os en una ma iz con su amaño de ila múl iplo
del amaño de línea de cache ( =0)
Suponemos que la ma iz N×Na aspone se almacena en memo ia po ilas
y es á alineada con el amaño de línea de cache, incluyendo los elemen os diago-
nales. También asumimos una línea de cache de da os que con iene Lelemen os
consecu i os de una misma ila, con Nmúl iplo de L. Usando la no ación de módulo
= (Nm´
od L) = 0. Es o co esponde a la igu a 5.2(a).
El núme o o al de accesos es el mismo que en la ecuación 5.1. El núme o de
allos obliga o ios en es e caso es (N/L)N, es deci , el núme o de líneas de cache
necesa ias pa a eco e una ila po el núme o de ilas. Po lo an o, la asa ideal de
acie os es:
1−N2/L
2(N2−N)=1−1
2L−1
2L(N−1). (5.2)
66 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
FIGURA 5.7: Mapeo en memo ia de los bloques Bi∈[a−h]que con ienen
cada uno, T=L=4 elemen os a anspone .
(T>L). En es os casos, son necesa ias d(T/L)/Selíneas adicionales de cache que
con engan elemen os ho izon ales a anspone . Dependiendo de la elación en e
los pa áme os de la cache LRU y el amaño de la ma iz, la asa ideal de acie os se
puede log a con un núme o de ías lige amen e dis in o. Po ejemplo, las ma ices
cuya dimensión (N) no es múl iplo de 2 necesi an una ía menos. De odos modos,
la asocia i idad necesa ia pa a alcanza la asa ideal de acie os pa a cualquie Ses á
aco ada po :
W=T
S+T/L
S+1, con T>L. (5.10)
5.6.3. Co a en W pa a alcanza la asa ideal de acie os con T<L
Es bas an e poco p ác ico supone que usamos una dimensión de ile cuyo nú-
me o de elemen os Tes meno que la capacidad de una línea de cache Lya que es o
implica que al p ocesa un ile de T×Telemen os aemos a cache más con enido
que el es ic amen e necesa io. Po lo an o, pa a alcanza la asa ideal de acie os
es e con enido que no se usa no puede se expulsado has a que se haya ealmen e
usado. En o as palab as, se necesi a una cache lo su icien emen e g ande pa a e i a
allos po capacidad. Conc e amen e, el núme o de líneas de cache (S×W) iene que
se mayo que el doble del núme o de columnas de la ma iz (2N). Con es e amaño
de ile an inap opiado, el núme o de ías necesa ias pa a alcanza la asa ideal de
acie os depende del amaño de la ma iz, aco ándose de la siguien e mane a:
W=2N
S+1, con T<L. (5.11)
5.7. Expe imen os
En es a sección alidamos las exp esiones analí icas que hemos ob enido p e-
iamen e po medio de simulaciones ex ensi as. Calculamos la asa de acie os en

5.7. Expe imen os 67
TABLA 5.1: E olución del con enido de una pila LRU du an e la
ansposición de un ile en una cache con L=T=4 y S=1. La
cap u a de cada pila LRU se oma después de la ejecución de las ins-
ucciones de lec u a (ld) o esc i u a (s ) que acceden a los E ila,columna
elemen os, y nos mues a la secuencia o denada de odas las líneas
de cache Biaccedidas p e iamen e.
Secuencia de accesos a memo ia de las ins ucciones de lec u a (ld) y esc i u a (s )
1 2 3 4 5 6 7 8 9
ld Ei,jld Ej,is Ei,js Ej,ild Ei,j+1ld Ej+1,is Ei,j+1s Ej+1,ild Ei,j+2
MRU BaBeBaBeBaB BaB Ba
1BaBeBaBeBaB BaB
2BeBeBeBe
3
4
LRU
10 11 12 13 14 15 16 17 18
ld Ej+2,is Ei,j+2s Ej+2,ild Ei,j+3ld Ej+3,is Ei,j+3s Ej+3,ild Ei+1,jld Ej,i+1
MRU BgBaBgBaBhBaBhBbBe
1BaBgBaBgBaBhBaBhBb
2B B B B BgBgBgBaBh
3BeBeBeBeB B B BgBa
4BeBeBeB Bg
LRU BeB
19 20 21 22 23 24 25 26 27
s Ei+1,js Ej,i+1ld Ei+1,j+1ld Ej+1,i+1s Ei+1,j+1s Ej+1,i+1ld Ei+1,j+2ld Ej+2,i+1s Ei+1,j+2
MRU BbBeBbB BbB BbBgBb
1BeBbBeBbB BbB BbBg
2BhBhBhBeBeBeBeB B
3BaBaBaBhBhBhBhBeBe
4BgBgBgBaBaBaBaBhBh
LRU B B B BgBgBgBgBaBa
28 29 30 31 32 33
s Ej+2,i+1ld Ei+1,j+3ld Ej+3,i+1s Ei+1,j+3s Ej+3,i+1ld Ei+2,j
MRU BgBbBhBbBhBc
1BbBgBbBhBbBh
2B B BgBgBgBb
3BeBeB B B Bg
4BhBhBeBeBeB
LRU BaBaBaBaBaBe
e ic ed Ba
da os en con igu aciones de cache di e en es pa a un amplio amaño de ma ices.
Además, los esul ados ob enidos se compa an con aquellos p opo cionados po el
algo i mo cache-obli ious demos ando que si el amaño del ile T×Tse es ablece
como igual al amaño de la línea de cache (T=L), el algo i mo iling siemp e a a
ene un endimien o (en é minos de asa de acie os en da os) mejo o igual que
el de cache-obli ious. También, lle amos a cabo múl iples expe imen os en ha dwa e
eal pa a es udia los iempos de ejecución (y no solo las asas de acie os en cache
de da os). Pa a inaliza es a sección, u ilizamos los esul ados ob enidos pa a con-
segui un modelo del consumo de ene gía de la je a quía de cache pa a cada uno
de los sis emas es udiados. Es o nos pe mi e e alua el gas o ene gé ico debido al
compo amien o de la ac i idad de eemplazo en la je a quía de memo ia.
68 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
5.7.1. Tasa de acie os en cache de da os en el algo i mo iling de anspo-
sición de ma ices
En es a sección e i icamos si la asa ideal de acie os (sección 5.4) se puede al-
canza pa a el algo i mo iling de ansposición de ma ices. Pa a ello, suponemos
una cache de da os LRU y que a la ma iz a aspone se le ha aplicado la écnica de
padding al y como se desc ibe en la sección 5.6. La igu a 5.8 mues a a ias g á icas
que co esponden a di e en es amaños de línea de cache L(en núme o de elemen-
os). Todas ellas mues an un boxplo po cada combinación de núme o de conjun os
(S), ías (W) y amaños de ile (T). Cada boxplo se p olonga e icalmen e y ep e-
sen a la asa de acie os en da os pa a ma ices de amaño desde 1024 ×1024 has a
2048 ×2048 elemen os, es deci , 1025 expe imen os. En la mayo ía de los casos solo
apa ece la mediana de los da os, como una línea ho izon al, debido a que odas las
asas de acie os de odas las ma ices ep esen adas son iguales o sus di e encias
son inap eciables. La línea ho izon al y pun eada ep esen a la asín o a de la asa de
acie os 1 −1
2L(ecuación 5.1). El colo del boxplo indica si se ha alcanzado la asa
ideal de acie os (sección 5.4) (azul), o si no ( ojo). Como podemos e , la asa ideal de
acie os se log a cuando el eje x(T) coincide con el amaño de línea en las columnas
(T=L), dependiendo del núme o de conjun os S(ecuaciones 5.7–5.9). Cuando se
alcanzan esul ados ideales con un amaño de ile subóp imo (T>L, ecuación 5.10),
con los mismos pa áme os, un amaño óp imo de ile (T=L) ambién lo log a.
Además las p opiedades de la polí ica LRU ga an izan que cuando la asa ideal de
acie os se alcanza con cie a con igu ación de cache, se sigue alcanzando al aumen-
a el núme o de conjun os y/o ías de es a con igu ación. Encon amos que la asa
ideal de acie os puede no alcanza se solo si la cache es demasiado pequeña o si sus
pa áme os no es án co ec amen e ajus ados. A o unadamen e, es os casos no son
ealis as, y la caches de da os ac uales son mucho más g andes que las ep esen adas
en la igu a 5.8. De hecho, la cache más g ande que hemos p obado (W=4, S=16)
con amaño de línea de 64 by es iene un amaño de solo 4 KiB.
5.7.2. Tasa de acie os en da os: Tiling s. Obli ious
Los esul ados an e io es nos mues an que, con el amaño ap opiado de ile, la
asa ideal de acie os se log a con caches muy pequeñas. En ez de un algo i mo
iling, se pod ía usa un algo i mo cache-obli ious [F i+99;F i+12]. En es a sección
e aluamos los equisi os de la cache de da os pa a log a la asa ideal de acie os
con un algo i mo cache-obli ious, as lo cual lo compa a emos con nues os esul a-
dos con iling. Un algo i mo cache-obli ious se puede e como un algo i mo iling en
el cual la ma iz a p ocesa se di ide ecu si amen e has a llega , en la ansposición
de ma ices, a un amaño de ile de 2 ×2 elemen os. Po lo an o, es p obable que
el p ocesado de cada ile pueda cabe en cache. El o den en el que se lle a a cabo la
ansposición iene dado po la ecu sión. Es e o den es una a iación de Z-o de el
cual conse a la localidad [Mo 66] ( e igu a 5.1(b)). Así, no es necesa io conoce
la con igu ación de cache pa a aplica es e algo i mo. Sin emba go, su endimien o
depende de los pa áme os de cache y p edeci cuando se á bueno o malo no es i-
ial [TRS04]. Debido a que el algo i mo obli ious di ide ecu si amen e la ma iz a
anspone su gen p oblemas cuando la dimensión de es a ma iz (N) no es po encia
de 2. Podemos e es e e ec o en la igu a 5.9 donde solo alcanzan la asa ideal de
acie os aquellas ma ices cuya dimensión es po encia de dos. P oponemos aplica
un phan om padding («Relleno an asma») que pe mi e esol e es e incon enien e.
5.7. Expe imen os 69
S=1
S=2
S=4
S=8
S=16
W=2
W=3
W=4
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
0
25
50
75
100
0
25
50
75
100
0
25
50
75
100
T (elemen os)
Tasa de acie os ( %)
(a) L=2.
S=1
S=2
S=4
S=8
S=16
W=2
W=3
W=4
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
0
25
50
75
100
0
25
50
75
100
0
25
50
75
100
T (elemen os)
Tasa de acie os ( %)
(b) L=4.
S=1
S=2
S=4
S=8
S=16
W=2
W=3
W=4
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
0
25
50
75
100
0
25
50
75
100
0
25
50
75
100
T (elemen os)
Tasa de acie os ( %)
(c) L=8.
S=1
S=2
S=4
S=8
S=16
W=2
W=3
W=4
2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16 2 4 8 16
0
25
50
75
100
0
25
50
75
100
0
25
50
75
100
T (elemen os)
Tasa de acie os ( %)
(d) L=16.
FIGURA 5.8: Las g á icas (a–d) mues an las asas de acie os en da-
os a iando el núme o de elemen os po línea (L=2,4,8,16 elemen-
os) pa a di e en es con igu aciones de cache con Sconjun os, W ías,
y amaño de ile T×Telemen os. Cada boxplo eúne los esul ados
de odas las ma ices de 1024×1024 a 2048 ×2048 elemen os. El colo
de cada boxplo mues a si se alcanza siemp e la asa ideal de acie os
(azul) o no ( ojo).
Su aplicación no modi ica el mapeo en memo ia de la ma iz a anspone pe o ue -
za al algo i mo obli ious a abaja como si la dimensión de la ma iz ue a po encia
de 2. A con inuación, solo se in e cambian los elemen os que son eales, en o as
palab as, el in e cambio de elemen os no se da en los elemen os « an asma» que se
añaden debido a la aplicación de es e padding. Es a ans o mación ampoco a ec a
al núme o de accesos a da os, simplemen e se asegu a que la secuencia de accesos
en el algo i mo obli ious sea egula . Has a donde sabemos es a écnica de padding
es una p opues a o iginal de es e abajo.
Los algo i mos 4y5mues an los algo i mos de ansposición de ma ices cache-
obli ious basados en la p opues a o iginal [F i+99;F i+12]. Básicamen e, es os algo-
i mos asumen que el pa áme o Nes po encia de 2 y la ma iz que ealmen e se
70 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
0.86
0.90
0.94
4 8 16 32 64 128 256 512 1024 2048 4096 8192
Dimensión de la ma iz (elemen os)
Tasa de acie os en da os
Phan om padding
no
si
FIGURA 5.9: Tasas de acie os en cache de da os con y sin phan om
padding (algo i mos 4y5) pa a la ansposición de ma ices cache-
obli ious. La con igu ación de la cache de da os es: L=16,S=16 y
W=2. Los amaños de ma iz a ían de 4 ×4 a 8192 ×8192 elemen-
os. La asa ideal de acie os en da os (ecuaciones 5.2–5.4) coincide
con la e sión phan om padding. La línea pun eada neg a mues a la
co a supe io de asa de acie os de la ecuación 5.1.
debe anspone se especi ica a a és de los pa áme os de índice. De es a mane a,
solo se lle a a cabo el in e cambio de elemen os cuando el índice co espondien e es
meno que N. Podemos encon a es a condición que hemos in oducido en la línea
6 en el algo i mo 4y en la línea 8 en el algo i mo 5.
Algo i mo 4 T anspues a(Ma izConPadding,N,indice1=1, indice2=N): anspo-
ne ecu si amen e una ma iz con phan om padding, almacenada po ilas.
1: i indice2−indice1≤2 hen
2: Ma izConPaddingindice1,indice1+1↔Ma izConPaddingindice1+1,indice1
3: else
4: indicemi ad ←(indice1+indice2)/2;
5: T anspues a(Ma izConPadding,N,indice1, indicemi ad);
6: i indicemi ad <N hen
7: T anspues a(Ma izConPadding,N,indicemi ad,indice2);
8: T anspues aIn e cambio(Ma izConPadding,N,indicemi ad,indice1,indice2,indicemi ad);
9: end i
10: end i
5.7. Expe imen os 71
Algo i mo 5 T anspues aIn e cambio(Ma izConPadding,N, s,cs, e,ce).
1: i (( e − s)≤2and (ce −cs)≤2) hen
2: o indice1← s o e −1do
3: o indice2←cs o ce −1do
4: Ma izConPaddingindice1,indice2↔Ma izConPaddingindice2,indice1
5: end o
6: end o
7: else
8: i s <N hen
9: mi ad ←( s + e)/2;
10: cmi ad ←(cs +ce)/2;
11: T anspues aIn e cambio(Ma izConPadding,N, s,cs, mi ad,cmi ad);
12: T anspues aIn e cambio(Ma izConPadding,N, mi ad,cs, e,cmi ad);
13: T anspues aIn e cambio(Ma izConPadding,N, s,cmi ad, mi ad,ce);
14: T anspues aIn e cambio(Ma izConPadding,N, mi ad,cmi ad, e,ce);
15: end i
16: end i
A con inuación, epe imos los expe imen os de la sección 5.7.1 pa a es e algo-
i mo obli ious mejo ado. La igu a 5.10 ecapi ula nues os esul ados pa a iling
( igu a 5.8), y los co espondien es a obli ious. Es a g á ica mues a el mínimo nú-
me o de ías de cache Wnecesa ias pa a log a la asa ideal de acie os pa a cada
combinación de amaño de línea de cache Ly núme o de conjun os de cache S, es
deci , cuan o más pequeña mejo . Encon amos los esul ados de iling a la izquie da
y los de obli ious a la de echa. Solo se mues an amaños adecuados de ile. Las con-
igu aciones inadecuadas de iling (T6=L) ienen peo es esul ados y no apa ecen
en es a g á ica. La ba as e des señalan el mínimo núme o de conjun os necesa ios
pa a alcanza la asa ideal de acie os. Se puede e que, con un núme o su icien e
de conjun os (S≥L), obli ious necesi a el mismo núme o de ías en cache que iling.
Sin emba go, en caches con un meno núme o de conjun os (incluidas las o almen e
asocia i as) obli ious necesi a más ías que iling pa a log a la asa ideal de acie os.
Es o se debe a que obli ious no se de iene cuando la ecu sión alcanza el amaño de
ile más ap opiado sino que con inúa educiendolo has a llega a iles de amaño
2×2 elemen os. Así, cuan o mayo es el amaño de línea, más con enido innecesa io
se ae de memo ia. Es e con enido (que se necesi a á pa a los iles pos e io es) de-
be man ene se en cache pa a pode ga an iza la asa ideal de acie os en da os. De
modo que si ijamos el núme o de conjun os, se á necesa io inc emen a el núme o
de ías.
Las caches de da os ienen habi ualmen e un núme o ela i amen e g ande de
conjun os(S≥L), así que en gene al en la ansposición de ma ices, an o iling
como cache-obli ious, se alcanza la asa ideal de acie os. Aun así hay que ene en
cuen a que las caches en los p ocesado es ac uales pueden se compa idas po di-
e en es hilos ha dwa e al mismo iempo, de modo que sigue siendo impo an e ac-
cede a ellas de la mane a más e icien e posible. Los esul ados an e io es mues an
que iling alcanza la asa ideal de acie os con menos ecu sos que obli ious. Además
es impo an e señala que los códigos ecu si os, como el del algo i mo obli ious,
suelen se más len os que los i e a i os debido al sob ecos e de las llamadas a un-
ciones y del p ocesamien o de la pila. También hay que ene en cuen a que pa a
sis emas de iempo eal, con un algo i mo ecu si o, end íamos que p opo ciona
como in o mación en el análisis el máximo ni el de ecu sión y comp oba que no

72 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
42 2 2 2
632 2 2
10 532 2
18 9532
42 2 2 2
842 2 2
16 742 2
32 15 742
Tiling (T=L)
Obli ious
L=2
L=4
L=8
L=16
1 2 4 8 16 1 2 4 8 16
2
8
32
2
8
32
2
8
32
2
8
32
Conjun os
Mín. núm. de ías pa a la asa ideal de acie os en da os
FIGURA 5.10: Mínimo núme o de ías (W) necesa ias pa a alcanza
la asa ideal de acie os, según el núme o de conjun os Sy amaño de
línea Lde la cache, pa a la ansposición de ma ices con el algo i mo
iling con amaño de iles T×T(T=L) y pa a el algo i mo obli ious
con phan om padding (cuán o más pequeño mejo ).
apa ecen p oblemas en la pila debido a ello.
5.7.3. PLRU y iempo de ejecución en pla a o mas eales
Los esul ados an e io es cuen an con una cache asocia i a po conjun os LRU.
Debido a que cues a bas an e cons ui una polí ica LRU que sea e icien e pa a una
g an cache, la mayo ía de caches en los p ocesado es come ciales usan una polí ica
PLRU la cual o ece un compo amien o pa ecido pe o es más simple de implemen-
a [AR13]. En es a sección p ime o compa amos la asa de acie os en da os LRU
con la de PLRU po medio de simulaciones. La igu a 5.11 mues a las asas de acie -
os en da os pa a la ansposición de ma ices de 4096 ×4096 elemen os de 8 B con
una con igu ación común de cache de da os L1 (64 conjun os, 8 ías, y 64 by es po
línea, siendo su amaño o al de 32 KiB). Con es e amaño de línea, cada una con iene
8 elemen os de la ma iz. Los expe imen os a ían la dimensión del ile de T=2 a
T=512. El á ea somb eada mues a los amaños de ile que alcanzan la asa ideal
de acie os en da os con LRU pa a iles cuya dimensión (T) es múl iplo del amaño
de línea (L=8). Es o se puede e cla amen e en e 8 y 16 de amaño de ile donde
dec ece la asa de acie os. El ile 8 ×8 co esponde a T=L( asa ideal de acie os
con los mínimos ecu sos de cache). Al inc emen a el amaño del ile a pa i de
8×8 has a 256 ×256 elemen os se alcanza la asa ideal de acie os pe o u ilizando
más conjun os/ ías (ecuación 5.10). Se puede e que an o LRU como PLRU ie-
nen p ác icamen e las mismas asas de acie o. Tal como se espe a la asa de acie os
disminuye ue a del á ea somb eada an o en LRU como en PLRU. Las únicas di e-
encias que se pueden ap ecia ealmen e, aunque mínimas, se encuen an en o no
aT=256, es deci , la co a de la ecuación 5.10.
G acias a las conclusiones ob enidas en las secciones p e ias de es e capí ulo po-
demos ga an iza la p edic ibilidad en LRU, an impo an e en cie as á eas como
en la que se desa olla nues o abajo, los sis emas de iempo eal. Sin emba go, no
puede ga an iza se pa a PLRU que se debe á e i a en es os sis emas, como ya han
5.7. Expe imen os 73
0.75
0.80
0.85
0.90
2 4 8 16 32 64 128 256 512
Dimensión del ile
Tasa de acie os en da os
LRU
PLRU
FIGURA 5.11: Tasa de acie os en da os pa a la ansposición de ma-
ices de 4096 ×4096 elemen os (cuan o mayo , mejo ) pa a polí ica
de eemplazo LRU y PLRU en una con igu ación de cache de da os
L1 común (64 conjun os, 8 ías, y 64 by es po línea, con un amaño
o al de 32 KiB). La línea neg a pun eada mues a la co a supe io de
asa de acie os de la ecuación 5.1.
indicado o os es udios [Be 06;Rei+07;AR14]. Aunque el ac o más de e minan-
e pa a el endimien o en es as simulaciones sea p obablemen e la asa de acie os
en da os, hay ambién o os elemen os impo an es que pueden a ec a a es e en-
dimien o como el núme o de ins ucciones ejecu adas (dependien e del amaño del
ile). Pa a pode ene en cuen a es os y o os ac o es (p. ej. p ebuscado es ha dwa-
e de da os) medimos los iempos de ejecución. Es os expe imen os se han lle ado
a cabo en a ias máquinas: In el-Xeon-L5410 2.33 GHz, In el-i7-4810MQ 2.80 GHz,
In el-Co e-2-Quad-Q9550 2.83 GHz,y In el-i7-2640M 2.80 GHz. Todas ellas ienen
una cache L1 de ins ucciones y o a de da os, ambas con eemplazo PLRU, 64 con-
jun os, 8 ías, y 64 by es po línea, con un amaño o al de 32 KiB, al como la que
simulamos en la igu a 5.11.
Se ha codi icado el algo i mo 3en C (código uen e disponible online1) y, pa a
cada máquina, se ha gene ado un bina io dis in o usando el compilado disponible
(GCC-4.7.0 o i7-4810M and Co e-2-Quad-Q9550, In el C++ Compose XE 2013 o
Xeon-L5410, y GCC-4.9.2 o i7-2640), pe o siemp e con op imización de ni el 3.
La igu a 5.12 mues a el meno iempo de ejecución pa a la ansposición de ma-
ices de 4096×4096 elemen os, a iando el núme o de elemen os po ile. Cada uno
de los iempos ep esen ados es el meno de 400 epe iciones, ep esen ando la eje-
cución más ápida, es deci la que es a ía más ce ca de una ansposición de ma ices
aislada de in e e encias ex e nas. El á ea somb eada indica las con igu aciones de
ile que alcanzan la asa ideal de acie os con una cache LRU pa a iles múl iplos del
amaño de línea, como an es. El iempo debe ía inc emen a se pa a LRU ue a del
á ea somb eada y de hecho se puede e que es e es el compo amien o que p esen-
a PLRU en la g á ica en la pla a o ma 2QuadQ9550. Sin emba go, en las o as es
pla a o mas el iempo de ejecución c ece pa a g andes iles aunque muy lige amen-
e. Es o se debe al p ebuscado en da os, el cual econoce los pa ones de acceso a
1webdiis.uniza .es/gaz/ eposi o ies/ iling-ma ix- ansposi ion
74 Capí ulo 5. Tasa ideal de acie os pa a la ansposición de ma ices
0.05
0.10
2 4 8 16 32 64 128 256 512
Dimensión del ile
Tiempo de ejecución (s)
2QuadQ9550
i7-2640M
i7-4810MQ
XeonL5410
FIGURA 5.12: Tiempos de ejecución pa a la ansposición de ma ices
de 4096 ×4096 elemen os. Además de los amaños de ile en el eje-x,
se puede e los iempos de ejecución pa a o os alo es de T: 6, 10,
12, 14, 20, 24, 28, 40, 48, 56, 96, 192, y 384.
da os y e i a las penalizaciones en iempo. En el á ea de la izquie da los iles son
demasiado pequeños pa a que el p ebuscado econozca ningún pa ón de acceso,
po ello el iempo de ejecución pa a es os iles es bas an e mayo . Los amaños que
son múl iplos de 8 abajan con líneas comple as de cache y po lo an o, en gene al,
ob iene un endimien o mejo que aquellos a su al ededo . Se puede e cla amen e
que en e 8 y 16 odas las g á icas mues an un inc emen o del iempo de ejecución.
Po úl imo, cuan o mayo es el amaño del ile, menos ins ucciones se ejecu an. Pa a
cada ile, se ienen que calcula las co as de sus índices y ambién asegu a que en
los iles de los ex emos de la ma iz no se in e cambian da os de ue a de ella. Es o
es, cuan o meno es son los amaños de ile den o del á ea somb eada más e icien e
es el uso que hacen de la cache, pe o ienen más ins ucciones. Po an o, se p odu-
ce una compensación en e los ecu sos de cache y las ins ucciones ejecu adas y la
endencia en cuan o al iempo de ejecución di e i á dependiendo de la máquina en
la que se ejecu e la ansposición.
5.7.4. Modelado y educción del consumo de ene gía en el subsis ema de
memo ia pa a la ansposición de ma iz e sión iling
En es a sección analizamos el consumo de ene gía en los subsis emas de memo-
ia de las cua o pla a o mas de la sección 5.7.3. Pa a pode hace lo usamos la asa
analí ica de acie os in oducida en la sección 5.6 y la combinamos con las g á icas
de ene gía ob enidas po la he amien a de modelización CACTI 7.0 [Bal+17]. Es a
he amien a pe mi e calcula la ene gía po acceso y la ene gía es á ica dada un con-
igu ación de cache o de memo ia p incipal. P ime o, desc ibimos los subsis emas
de memo ia de las cua o pla a o mas, p esen amos las g á icas de po encia y ene -
gía de cada componen e y explicamos cómo calcula la ene gía global. Después, nos
cen amos en un amaño especí ico de ma iz omando a ios amaños de ile con lo
que ob enemos el consumo de ene gía global y as lo cual suge imos mejo as en el
so wa e/ha dwa e.
5.7. Expe imen os 75
(a) 2 ni eles: QuadQ9550 y XeonL5410. (b) 3 ni eles: i7-2640 y i7-4810.
FIGURA 5.13: O ganización de las je a quías de memo ia.
Modelado analí ico de consumo de ene gía
La igu a 5.13 mues a las dos je a quías que encon amos en las cua o pla a o -
mas de nues a expe imen ación. Xeon-L5410 y 2QuadQ9550 ienen dos ni eles de
cache, y i7-2640M y i7-4810MQ ienen es. El úl imo ni el de cache, el más ce cano
a la memo ia p incipal, es á compa ido en e los núcleos (solo se mues a uno en la
igu a 5.13), mien as que los ni eles más bajos son p i ados pa a cada uno de ellos.
Todas las caches de da os son caches copy-back, lo que quie e deci que el e ec o de
una sola esc i u a no se e en ni eles supe io es has a que no se expulsa po com-
ple o la línea modi icada. Las ope aciones de lec u a y esc i u a que se ejecu an en el
núcleo acceden p ime o a la cache L1. Cuando se da un allo, se busca en el siguien e
ni el de cache has a que se p oduce un acie o o se llega a memo ia p incipal. Un
allo en el úl imo ni el ae la línea de memo ia p incipal al menos a cache L1 y, de-
pendiendo de la polí ica de con ol de con enido en e ni eles, ambién a las caches
L2 y L3. Po simplicidad, ya que las cua o pla a o mas ienen di e en es polí icas,
asumimos que odas ienen una polí ica inclusi a en la cual se o dena que se copien
las líneas que engan de memo ia p incipal a odos los ni eles de cache, es deci , L1
⊂L2 ⊂L3.
La abla 5.2 mues a los pa áme os de cache y ecnológicos pa a odas las pla-
a o mas. Las g á icas de ene gía y po encia han sido calculadas po CACTI, con-
side ando la ecnología del nodo, el ni el de memo ia, y los di e en es amaños y
asocia i idades. Solo se mues a la ene gía pa a lee /esc ibi un elemen o de 8 by es
en las caches L1, cuando las ins ucciones de lec u a y esc i u a ope an a es a g a-
nula idad, mien as que la ene gía pa a lee /esc ibi obje os de 64 by es pe mi en
conside a las ans e encias de líneas en e odos los ni eles de memo ia. Elegimos
una memo ia p incipal de 1 GiB po que es lo su icien emen e g ande pa a almacena
128 MiB, el amaño de la ma iz de 4096 ×4096 elemen os de 8 by es que se usa en
la igu a 5.12 y en la siguien e sección. Aho a podemos usa el modelo de la asa de
acie os de la sección 5.6 pa a con a odos los e en os de in e és en cualquie ni el
de la je a quía inclusi a expues a a iba: esc i u as, lec u as, acie os y eemplazos.
En onces podemos calcula la ene gía dinámica o al mul iplicando el núme o de
82 Capí ulo 6. Conclusiones
Comple amos es e es udio analizando el impac o de los ni eles de op imización
en el WCET y concluyendo que es con enien e desca a las compilaciones sin op i-
mización (-O0) ya que el WCET de los bina ios gene ados esul a en e 3 y 4 eces
peo que con la p esencia de op imizaciones. Sin emba go, hay que e i a op imiza-
ciones demasiado ag esi as que puedan cambia los pa ones de bucle di icul ando,
y empeo ando, el análisis del WCET.
El abajo desa ollado en es e capí ulo se ha p esen ado en A. Ped o-Zapa e , J. Se-
ga a, C. Rod íguez, R.G. Teje o y V. Viñals-Yú e a (2016) «Ob ención del WCET óp imo en
caches de ins ucciones bloqueables (Lock-MS) en O awa» V Simposio de sis emas de iempo
eal, 13-16 Sep iemb e 2016, Salamanca. y se ha publicado en A. Ped o-Zapa e , J. Sega-
a, C. Rod íguez, R.G. Teje o y V. Viñals-Yú e a (2020) «Reducing he WCET and analysis
ime o sys ems wi h simple lockable ins uc ion caches» PLOS ONE 15(3): e022998.
En el capí ulo 4ampliamos el es udio a aquellos p og amas con código ec o i-
zado analizando su impac o en el WCET. Pa a ello se es udian las ec o izaciones
au omá icas gene adas po GCC en paque es de benchma ks de iempo eal, in e-
g ando sus especi icaciones empo ales en la he amien a de análisis del WCET.
Si los bucles ec o izados o man pa e del código donde se concen a la mayo
pa e del iempo de ejecución, nues os esul ados con i man que el WCET se edu-
ce de mane a signi ica i a (ob eniendo has a una educción po un ac o de 3 del
WCET en alguno de los benchma ks). Sin emba go, en los benchma ks en los que
no se da es a si uación no hay an o ma gen de mejo a. Es o se debe en pa e a las
p opias limi aciones de la ec o ización au omá ica, y ambién de la p opia p og a-
mación de los benchma ks. Po an o, pa a ob ene mejo es esul ados es necesa io
o bien eesc ibi el código acili ando el abajo de ec o ización del compilado o
bien esc ibi código ec o ial explíci o. En cualquie a de los dos casos la e iciencia
de la ec o ización queda en manos de quien p og ama.
O a conclusión que ecogemos en es e capí ulo es que debe e i a se la ec o iza-
ción si el núme o de i e aciones de los bucles ec o izados no es lo su icien emen e
g ande pa a compensa el sob ecos e de u iliza código ec o ial. Es e sob ecos e
se debe al código gene ado pa a selecciona el modo escala o ec o ial, a las ins-
ucciones adicionales que p epa an el bucle o a los allos adicionales en cache de
ins ucciones po las ins ucciones ec o iales.
En esumen, es os esul ados jun o con el hecho de que el p ocesamien o ec o-
ial es á con i iéndose en una u ilidad básica en la mayo ía de los p ocesado es del
me cado alien an a usa los ecu sos ec o iales en sis emas de iempo eal es ic-
o eniendo en cuen a las cues iones plan eadas como un pun o de pa ida pa a un
es udio más ex enso.
En el capí ulo 5abo damos el análisis del WCET en p esencia de cache de da os
a a és del análisis de pa ones de accesos de la ope ación de ansposición de ma-
ices, una ope ación básica en sis emas de iempo eal. De e mina de o ma p ecisa
y, si es posible, educi el núme o de accesos y aumen a la asa de acie os conlle a
un impac o di ec o en el cálculo del WCET.
En es e capí ulo ob enemos las exp esiones analí icas que pe mi en de e mina
el compo amien o ideal de la cache de da os ( allos obliga o ios) pa a la ansposi-
ción de ma ices y cuál se á la con igu ación óp ima pa a una cache de da os LRU en
la e sión iling del algo i mo. T as ello, alidamos las exp esiones an e io es y las
compa amos con la e sión cache-obli ious del algo i mo po medio de simulaciones.
En es a compa ación obse amos que, con el amaño adecuado de ile, la e sión
iling del algo i mo ob iene una asa de acie os en da os igual o mejo . Finalmen-
e, o ecemos esul ados expe imen ales en ha dwa e eal y una compa ación con
PLRU.

Capí ulo 6. Conclusiones 83
Nues a p incipal apo ación, la cual e a obje o de es e es udio, es p opo cio-
na esul ados que pe mi en de e mina de o ma sencilla los acie os y allos de la
e sión iling de la ansposición de ma ices (imp escindible pa a aplicaciones de
iempo eal) en una cache LRU de da os y, bajo de e minadas con igu aciones de
cache, en una cache PLRU.
Adicionalmen e a es os esul ados podemos conclui que no an a se necesa ias
más de dos ías en la cache de da os y unos pocos conjun os pa a log a la asa de
acie os ideal y po an o las ías que no se usen en una cache de da os asocia i a po
conjun os pueden desconec a se sin ningún impac o nega i o p opo cionando un
aho o de ene gía (desde un 3% a un 46% en nues os expe imen os, dependiendo
de la pla a o ma). Además, pueden ese a se en exclusi a dos ías en las caches de
los úl imos ni eles pa a la ansposición de ma ices, e i ando la con aminación de
o os p ocesos.
El abajo desa ollado en es e capí ulo se ha p esen ado en A. Ped o-Zapa e , C.
Rod íguez, J. Sega a, R.G. Teje o y V. Viñals-Yú e a (2019), «Tasa de acie os ideal y p e-
decible pa a la ansposición de ma ices en caches de da os», XXX Jo nadas de Pa alelismo
(JP2019), 18-20 Sep iemb e 2019, Cáce es. y se ha publicado en A. Ped o-Zapa e , C. Ro-
d íguez, J. Sega a, R.G. Teje o y V. Viñals-Yú e a (2020), «Ideal and P edic able Hi Ra io
o Ma ix T ansposi ion in Da a Caches», Ma hema ics., Feb ua y, 2020. Vol. 8(2), pp. 184.
MDPI AG.
85
Bibliog a ía
[ALE02] Todd M. Aus in, E ic La son y Dan E ns . «SimpleScala : An In as uc-
u e o Compu e Sys em Modeling». En: IEEE Compu e 35.2 (2002),
págs. 59-67. DOI:10.1109/2.982917.
[AP] Alexis A naud e Isabelle Puau . «Dynamic ins uc ion cache locking in
ha d eal- ime sys ems». En: In RTNS.
[Apa+08] Luis C. Apa icio, Juan Sega a, Clemen e Rod íguez, J. L. Villa oel y Víc-
o Viñals. «A oiding he WCET O e es ima ion on LRU Ins uc ion
Cache». En: The Fou een h IEEE In e na ionl Con e ence on Embedded and
Real-Time Compu ing Sys ems and Applica ions, RTCSA 2008, Kaohisung,
Taiwan, 25-27 Augus 2008, P oceedings. IEEE Compu e Socie y, 2008,
págs. 393-398. DOI:10.1109/RTCSA.2008.10.
[Apa+10] Luis C. Apa icio, Juan Sega a, Clemen e Rod íguez y Víc o Viñals.
«Combining P e e ch wi h Ins uc ion Cache Locking in Mul i asking
Real-Time Sys ems». En: 16 h IEEE In e na ional Con e ence on Embedded
and Real-Time Compu ing Sys ems and Applica ions, RTCSA 2010, Macau,
SAR, China, 23-25 Augus 2010. IEEE Compu e Socie y, 2010, págs. 319-328.
DOI:10.1109/RTCSA.2010.8.
[Apa+11] Luis C. Apa icio, Juan Sega a, Clemen e Rod íguez y Víc o Viñals.
«Imp o ing he WCET compu a ion in he p esence o a lockable ins-
uc ion cache in mul i asking eal- ime sys ems». En: J. Sys . A chi . 57.7
(2011), págs. 695-706. DOI:10.1016/j.sysa c.2010.08.008.
[AR13] And eas Abel y Jan Reineke. «Measu emen -based modeling o he ca-
che eplacemen policy». En: 19 h IEEE Real-Time and Embedded Techno-
logy and Applica ions Symposium, RTAS 2013, Philadelphia, PA, USA, Ap il
9-11, 2013. IEEE Compu e Socie y, 2013, págs. 65-74. DOI:10 . 1109 /
RTAS.2013.6531080.
[AR14] And eas Abel y Jan Reineke. «Re e se enginee ing o cache eplacemen
policies in In el mic op ocesso s and hei e alua ion». En: 2014 IEEE
In e na ional Symposium on Pe o mance Analysis o Sys ems and So wa-
e, ISPASS 2014, Mon e ey, CA, USA, Ma ch 23-25, 2014. IEEE Compu e
Socie y, 2014, págs. 141-142. DOI:10.1109/ISPASS.2014.6844475.
[ARM] GNU ARM. GNU ARM Embedded Toolchain Ve sion 6-2017-q2-upda e.URL:
de elope .a m.com/open-sou ce/gnu- oolchain/gnu- m/downloads
( isi ado 04-05-2020).
[ARS13] Luis Ca los Apa icio Ca diel, Clemen e Rod íguez La uen e y Juan Se-
ga a Flo . «» En: (2013). P esen ado: 21 02 2013.
[AU14] Pa el G. Zayko A hu Pyka Ma hias Rohde y Sascha Uh ig. «Case
S udy: On-Demand Cohe en Cache o A ionic Applica ions». En: 2nd
Wo kshop on High-pe o mance and Real- ime Embedded Sys ems. 2014.
86 Bibliog a ía
[Bac+94] Da id F. Bacon, Jyh-He ng Chow, Dz-ching Ju, Kalyan Mu hukuma
y Vi ek Sa ka . «A compile amewo k o es uc u ing da a decla-
a ions o enhance cache and TLB e ec i eness». En: P oceedings o he
1994 Con e ence o he Cen e o Ad anced S udies on Collabo a i e Resea ch,
Oc obe 31 - No embe 3, 1994, To on o, On a io, Canada. Ed. po John E.
Bo s o d, Ann Gawman, W. Mo en Gen leman, E elyn Kidd, Kelly
A. Lyons, Jacob Slonim y J. Howa d Johnson. IBM, 1994, pág. 3. URL:
dl.acm.o g/ci a ion.c m?id=782188.
[Bal+10] Clémen Ballab iga, Hugues Cassé, Ch is ine Rochange y Pascal Sain-
a . «OTAWA: An Open Toolbox o Adap i e WCET Analysis». En:
So wa e Technologies o Embedded and Ubiqui ous Sys ems - 8 h IFIP WG
10.2 In e na ional Wo kshop, SEUS 2010, Waidho en/Ybbs, Aus ia, Oc obe
13-15, 2010. P oceedings. Ed. po Sang Lyul Min, Robe G. Pe i IV, Pe-
e P. Puschne y Theo Unge e . Vol. 6399. Lec u e No es in Compu e
Science. Sp inge , 2010, págs. 35-46. DOI:10.1007/978-3-642-16256-
5 _6.
[Bal+16] San o d Balla d, James Hipp, B ian K aus, And e Enca nacao y Ch is-
ophe Young. «GeoTess: A Gene alized Ea h Model So wa e U ili y».
En: Seismological Resea ch Le e s 87 (mayo de 2016), págs. 719-725. DOI:
10.1785/0220150222.
[Bal+17] Rajee Balasub amonian, And ew B. Kahng, Na een Mu alimanoha ,
Ali Sha iee y Vaishna S ini as. «CACTI 7: New Tools o In e connec
Explo a ion in Inno a i e O -Chip Memo ies». En: TACO 14.2 (2017),
14:1-14:25. DOI:10.1145/3085572.
[Bao+18] Wenlei Bao, S i am K ishnamoo hy, Louis-Noël Pouche y P. Sadayap-
pan. «Analy ical modeling o cache beha io o a ine p og ams». En:
PACMPL 2.POPL (2018), 32:1-32:26. DOI:10.1145/3158120.
[BC11] Shekha Bo ka y And ew A. Chien. «The u u e o mic op ocesso s».
En: Commun. ACM 54.5 (2011), págs. 67-77. DOI:10 . 1145 / 1941487 .
1941507.
[Be 06] Ch is oph Be g. «PLRU Cache Domino E ec s». En: 6 h In l. Wo kshop
on Wo s -Case Execu ion Time (WCET) Analysis, July 4, 2006, D esden, Ge -
many. Ed. po F ank Muelle . Vol. 4. OASICS. In e na ionales Begegnungs-
und Fo schungszen um ue In o ma ik (IBFI), Schloss Dags uhl, Ge -
many, 2006. URL:d ops.dags uhl.de/opus/ oll ex e/2006/672.
[Bin+11] Na han L. Binke , B ad o d M. Beckmann, Gab iel Black, S e en K.
Reinha d , Ali G. Saidi, A kap a a Basu, Joel Hes ness, De ek Howe ,
Tusha K ishna, Somayeh Sa dash i, Ra hiji Sen, Ko ey Sewell, Muham-
mad Shoaib Bin Al a , Nilay Vaish, Ma k D. Hill y Da id A. Wood. «The
gem5 simula o ». En: SIGARCH Compu e A chi ec u e News 39.2 (2011),
págs. 1-7. DOI:10.1145/2024716.2024718.
[BMS08] A melle Bonen an , Ma ianne de Michiel y Pascal Sain a . «oRange: A
ool o s a ic loop bound analysis». En: P oceedings o he Wo kshop on
Resou ce Analysis. 2008.
[Cam+03] A. M. Campoy, A. Pe les, F. Rod iguez y J. V. Busque s-Ma aix. «S a-
ic use o locking caches s. dynamic use o locking caches o eal- ime
Bibliog a ía 87
sys ems». En: CCECE 2003 - Canadian Con e ence on Elec ical and Compu-
e Enginee ing. Towa d a Ca ing and Humane Technology (Ca . No.03CH37436).
Vol. 2. 2003, 1283-1286 ol.2.
[Cam+05] An onio Ma í Campoy, Eugenio Tamu a, S. Sáez, F ancisco Rod íguez
y José V. Busque s-Ma aix. «On Using Locking Caches in Embedded
Real-Time Sys ems». En: Embedded So wa e and Sys ems, Second In e na-
ional Con e ence, ICESS 2005, Xi’an, China, Decembe 16-18, 2005, P ocee-
dings. Ed. po Lau ence Tian uo Yang, Xingshe Zhou, Wei Zhao, Zhaohui
Wu, Yian Zhu y Man Lin. Vol. 3820. Lec u e No es in Compu e Science.
Sp inge , 2005, págs. 150-159. DOI:10.1007/11599555 _17.
[Caz+13] F ancisco J. Cazo la, Edua do Quiñones, Tullio Va danega, Liliana Cu-
cu, Benoi T ique , Guillem Be na , Eme y D. Be ge , Jaume Abella, F anck
Wa el, Michael Hous on, Luca San inelli, Leonidas Kosmidis, Code Lo
y Do in Maxim. «PROARTIS: P obabilis ically Analyzable Real-Time
Sys ems». En: ACM T ans. Embedded Compu . Sys . 12.2s (2013), 94:1-94:26.
DOI:10.1145/2465787.2465796.
[CB02] An oine Colin y Guillem Be na . «Scope-T ee: A P og am Rep esen a-
ion o Symbolic Wo s -Case Execu ion Time Analysis». En: 14 h Eu-
omic o Con e ence on Real-Time Sys ems (ECRTS 2002), 19-21 June 2002,
Vienna, Aus ia, P oceedings. IEEE Compu e Socie y, 2002, pág. 50. DOI:
10.1109/EMRTS.2002.1019185.
[CC77] Pa ick Couso y Radhia Couso . «Abs ac In e p e a ion: A Uni ied
La ice Model o S a ic Analysis o P og ams by Cons uc ion o Ap-
p oxima ion o Fixpoin s». En: Con e ence Reco d o he Fou h ACM Sym-
posium on P inciples o P og amming Languages, Los Angeles, Cali o nia,
USA, Janua y 1977. Ed. po Robe M. G aham, Michael A. Ha ison
y Ra i Se hi. ACM, 1977, págs. 238-252. DOI:10.1145/512950.512973.
[Che14] Ma yline Che o. Real- ime sys ems scheduling. ISTE L d, 2014.
[CIM01] Ma i Campoy, A. Pe les I a s y J. V. Busque s Ma aix. «S a ic Use o
Locking Caches in Mul i ask P eemp i e Real-Time Sys ems». En: In
P oceedings o IEEE/IEE Real-Time Embedded Sys ems Wo kshop (Sa elli e
o he IEEE Real-Time Sys ems Symposium. 2001.
[CK07] Jian-Jia Chen y Chin-Fu Kuo. «Ene gy-E icien Scheduling o Real-
Time Sys ems on Dynamic Vol age Scaling (DVS) Pla o ms». En: 13 h
IEEE In e na ional Con e ence on Embedded and Real-Time Compu ing Sys-
ems and Applica ions (RTCSA 2007), 21-24 Augus 2007, Daegu, Ko ea.
IEEE Compu e Socie y, 2007, págs. 28-38. DOI:10.1109/RTCSA.2007.
37.
[CP00] An oine Colin e Isabelle Puau . «Wo s Case Execu ion Time Analysis
o a P ocesso wi h B anch P edic ion». En: Real-Time Sys ems 18.2/3
(2000), págs. 249-274. DOI:10.1023/A:1008149332687.
[CS00] Siddha ha Cha e jee y Sandeep Sen. «Cache-E icien Ma ix T ans-
posi ion». En: P oceedings o he Six h In e na ional Symposium on High-
Pe o mance Compu e A chi ec u e, Toulouse, F ance, Janua y 8-12, 2000.
IEEE Compu e Socie y, 2000, págs. 195-205. DOI:10.1109/HPCA.2000.
824350.

88 Bibliog a ía
[DLM13] Huping Ding, Yun Liang y Tulika Mi a. «In eg a ed ins uc ion cache
analysis and locking in mul i asking eal- ime sys ems». En: The 50 h
Annual Design Au oma ion Con e ence 2013, DAC ’13, Aus in, TX, USA,
May 29 - June 07, 2013. ACM, 2013, 147:1-147:10. DOI:10.1145/2463209.
2488916.
[Fal+16] Heiko Falk, Sebas ian Al meye , Pe e Hellinckx, Bjö n Lispe , Wol gang
Pu i sch, Ch is ine Rochange, Ma in Schoebe l, Rasmus Bo So ensen,
Pe e Wägemann y Simon Wegene . «TACLeBench: A Benchma k Co-
llec ion o Suppo Wo s -Case Execu ion Time Resea ch». En: 16 h In-
e na ional Wo kshop on Wo s -Case Execu ion Time Analysis, WCET 2016,
July 5, 2016, Toulouse, F ance. Ed. po Ma in Schoebe l. Vol. 55. OASICS.
Schloss Dags uhl - Leibniz-Zen um ü In o ma ik, 2016, 2:1-2:10. DOI:
10.4230/OASIcs.WCET.2016.2.
[FH04] Ch is ian Fe dinand y Reinhold Heckmann. «aiT: wo s case execu ion
ime p edic ion by s a ic p og am analysis». En: Building he In o ma ion
Socie y, IFIP 18 h Wo ld Compu e Cong ess, Topical Sessions, 22-27 Augus
2004, Toulouse, F ance. Ed. po René Jacqua . Vol. 156. IFIP. Kluwe /S-
p inge , 2004, págs. 377-383. DOI:10.1007/978-1-4020-8157-6 _29.
[Fla+02] K isz ián Flau ne , Nam Sung Kim, S e en M. Ma in, Da id T. Blaauw
y T e o N. Mudge. «D owsy Caches: Simple Techniques o Reducing
Leakage Powe ». En: 29 h In e na ional Symposium on Compu e A chi ec-
u e (ISCA 2002), 25-29 May 2002, Ancho age, AK, USA. Ed. po Yale N.
Pa , Di k G unwald y Ke in Skad on. IEEE Compu e Socie y, 2002,
págs. 148-157. DOI:10.1109/ISCA.2002.1003572.
[FLS13] B. Fi zge ald, S. Lopez y Julio Sahuquillo. «D owsy cache pa i ioning
o educed s a ic and dynamic ene gy in he cache hie a chy». En: In-
e na ional G een Compu ing Con e ence, IGCC 2013, A ling on, VA, USA,
June 27-29, 2013, P oceedings. IEEE Compu e Socie y, 2013, págs. 1-6.
DOI:10.1109/IGCC.2013.6604475.
[F e12] Inc. F ee So wa e Founda ion. GCC, he GNU Compile Collec ion. 2012.
URL:gcc.gnu.o g/ ( isi ado 20-05-2020).
[F i+12] Ma eo F igo, Cha les E. Leise son, Ha ald P okop y S idha Rama-
chand an. «Cache-Obli ious Algo i hms». En: ACM T ans. Algo i hms
8.1 (2012), 4:1-4:22. DOI:10.1145/2071379.2071383.
[F i+99] Ma eo F igo, Cha les E. Leise son, Ha ald P okop y S idha Rama-
chand an. «Cache-Obli ious Algo i hms». En: 40 h Annual Symposium
on Founda ions o Compu e Science, FOCS ’99, 17-18 Oc obe , 1999, New
Yo k, NY, USA. IEEE Compu e Socie y, 1999, págs. 285-298. DOI:10.
1109/SFFCS.1999.814600.
[FW99] Ch is ian Fe dinand y Reinha d Wilhelm. «E icien and P ecise Cache
Beha io P edic ion o Real-Time Sys ems». En: Real-Time Sys ems 17.2-
3 (1999), págs. 131-181. DOI:10.1023/A:1008186323068.
[Ge +11] Mike Ge des, Julian Wol , I akli Guliash ili, Theo Unge e , Michael Hous-
on, Guillem Be na , S e an Schni zle y Hans Regle . «La ge d illing
machine con ol code - Pa allelisa ion and WCET speedup». En: Indus-
ial Embedded Sys ems (SIES), 2011 6 h IEEE In e na ional Symposium on,
SIES 2011. Vas e as, Sweden, June 15-17, 2011. IEEE, 2011, págs. 91-94.
DOI:10.1109/SIES.2011.5953688.
Bibliog a ía 89
[G a+13] Ruben G an, Juan Sega a, Clemen e Rod íguez, Luis C. Apa icio y Víc-
o Viñals. «Op imizing a combined WCET-WCEC p oblem in ins uc-
ion e ching o eal- ime sys ems». En: J. Sys . A chi . 59.9 (2013), págs. 667-678.
DOI:10.1016/j.sysa c.2013.07.012.
[G a+15] Ruben G an, Juan Sega a, A. Ped o-Zapa e , Luis C. Apa icio, Víc o
Viñals y Clemen e Rod íguez. «A p edic able ha dwa e o exploi em-
po al euse in eal- ime and embedded sys ems». En: J. Sys . A chi . 61.5-
6 (2015), págs. 227-238. DOI:10.1016/j.sysa c.2015.05.001.
[Gus+03] Jan Gus a sson, Bjö n Lispe , Ch is e Sandbe g y Ne ina Be mudo. «A
Tool o Au oma ic Flow Analysis o C-p og ams o WCET Calcula-
ion». En: 8 h IEEE In e na ional Wo kshop on Objec -O ien ed Real-Time
Dependable Sys ems (WORDS 2003), 15-17 Janua y 2003, Guadalaja a, Me-
xico. IEEE Compu e Socie y, 2003, págs. 106-112. DOI:10.1109/WORDS.
2003.1218072.
[Gus+10] Jan Gus a sson, Adam Be s, And eas E medahl y Bjö n Lispe . «The
Mäla dalen WCET Benchma ks – Pas , P esen and Fu u e». En: WCET2010.
Ed. po Bjö n Lispe . B ussels, Belgium, jul. de 2010, págs. 137-147. DOI:
10.4230/OASIcs.WCET.2010.136.
[Gus00] Jan Gus a sson. «Analyzing Execu ion-Time o Objec -O ien ed P og ams
Using Abs ac In e p e a ion». Tesis doc . Depa men o Compu e
Enginee ing, Mäla dalen Uni e si y, Box 883, S-721 23 Väs e ås, Swe-
den, y Depa men o Compu e Sys ems, In o ma ion Technology, Upp-
sala Uni e si y, Box 325, S-751 05 Uppsala, Sweden, mayo de 2000. URL:
h p://www.es.mdh.se/publica ions/231-.
[Hea+99] Ch is ophe A. Healy, Robe D. A nold, F ank Muelle , Da id B. Wha-
lley y Ma ion G. Ha mon. «Bounding Pipeline and Ins uc ion Cache
Pe o mance». En: IEEE T ans. Compu e s 48.1 (1999), págs. 53-70. DOI:
10.1109/12.743411.
[Hon+] Honeywell, BSC, Uni e si é Toulouse III - Paul Saba ie y Rapi a Sys-
ems. MERASA P ojec .URL:co dis.eu opa.eu/p ojec /id/216415/
es ( isi ado 15-06-2020).
[Hon+16] Changwan Hong, Wenlei Bao, Albe Cohen, S i am K ishnamoo hy,
Louis-Noël Pouche , Fab ice Ras ello, J. Ramanujam y P. Sadayappan.
«E ec i e padding o mul idimensional a ays o a oid cache con lic
misses». En: P oceedings o he 37 h ACM SIGPLAN Con e ence on P o-
g amming Language Design and Implemen a ion, PLDI 2016, San a Ba ba-
a, CA, USA, June 13-17, 2016. Ed. po Chand a K in z y Eme y Be ge .
ACM, 2016, págs. 129-144. DOI:10.1145/2908080.2908123.
[HRP17] Damien Ha dy, Benjamin Rouxel e Isabelle Puau . «The Hep ane S a-
ic Wo s -Case Execu ion Time Es ima ion Tool». En: 17 h In e na ional
Wo kshop on Wo s -Case Execu ion Time Analysis, WCET 2017, June 27,
2017, Dub o nik, C oa ia. Ed. po Jan Reineke. Vol. 57. OASICS. Schloss
Dags uhl - Leibniz-Zen um ü In o ma ik, 2017, 8:1-8:12. DOI:10.4230/
OASIcs.WCET.2017.8.URL:h ps://doi.o g/10.4230/OASIcs.WCET.
2017.8.
[II] INRIA e I3S. MasCo TE P ojec .URL:www-sop.in ia. / eams/masco e/
( isi ado 15-06-2020).
90 Bibliog a ía
[Ins20] Global Ma ke Insigh s. Embedded Sys ems Ma ke Size By Componen (Ha d-
wa e, [ASIC & ASSP, Mic ocon olle , Mic op ocesso , Powe Managemen
In eg a ed Ci cui (PMIC), Field P og ammable Ga e A ay (FPGA), Digi al
Signal P ocesso (DSP), Memo y], So wa e (OS, Middlewa e)], By Func ion
(S andalone Sys em, Real-Time Sys em, Ne wo k Sys em, Mobile Sys em), By
Applica ion (Au omo i e, Consume Elec onics, Manu ac u ing, Re ail, Me-
dia & En e ainmen , Mili a y & De ense, Telecom), Indus y Analysis Re-
po , Regional Ou look, Applica ion Po en ial, Compe i i e Ma ke Sha e &
Fo ecas , 2020-2026. 2020. URL:gminsigh s.com/indus y-analysis/
embedded-sys em-ma ke ( isi ado 14-09-2020).
[IUU] INRIA Siège, Uni e si é Toulouse III - Paul Saba ie y Uni e si é Pa ís
VI- Pie e e Ma ie Cu ie. MORE P ojec .URL:an . /P ojec -ANR-
06-ARFU-0002 ( isi ado 15-06-2020).
[JML06] Ramkuma Jayaseelan, Tulika Mi a y Xian eng Li. «Es ima ing he Wo s -
Case Ene gy Consump ion o Embedded So wa e». En: 12 h IEEE Real-
Time and Embedded Technology and Applica ions Symposium (RTAS 2006),
4-7 Ap il 2006, San Jose, Cali o nia, USA. IEEE Compu e Socie y, 2006,
págs. 81-90. DOI:10.1109/RTAS.2006.17.
[Kos+14] Leonidas Kosmidis, Jaume Abella, Edua do Quiñones y F ancisco J. Ca-
zo la. «E icien Cache Designs o P obabilis ically Analysable Real-
Time Sys ems». En: IEEE T ans. Compu e s 63.12 (2014), págs. 2998-3011.
DOI:10.1109/TC.2013.182.
[Kuc+81] Da id J. Kuck, Robe H. Kuhn, Da id A. Padua, B uce Leasu e y Mi-
chael Wol e. «Dependence G aphs and Compile Op imiza ions». En:
Con e ence Reco d o he Eigh h Annual ACM Symposium on P inciples o
P og amming Languages, Williamsbu g, Vi ginia, USA, Janua y 1981. Ed.
po John Whi e, Richa d J. Lip on y Pa icia C. Goldbe g. ACM P ess,
1981, págs. 207-218. DOI:10.1145/567532.567555.
[Lei03] Cha les E. Leise son. «Cache-Obli ious Algo i hms». En: Algo i hms and
Complexi y, 5 h I alian Con e ence, CIAC 2003, Rome, I aly, May 28-30, 2003,
P oceedings. Ed. po Rossella Pe eschi, Giuseppe Pe siano y Ricca do
Sil es i. Vol. 2653. Lec u e No es in Compu e Science. Sp inge , 2003,
pág. 5. DOI:10.1007/3-540-44849-7 _5.
[Li+07] Xian eng Li, Liang Yun, Tulika Mi a y Abhik Roychoudhu y. «Ch onos:
A iming analyze o embedded so wa e». En: Sci. Compu . P og am.
69.1-3 (2007), págs. 56-67. DOI:10.1016/j.scico.2007.01.014.
[Lima] ARM Limi ed. A m 6 e e ence manual.URL:in ocen e . a m . com /
help/index.jsp? opic=/com.a m . doc . dui0489e / CJAJIIGG . h ml
( isi ado 11-05-2020).
[Limb] ARM Limi ed. Co ex-A8 e e ence manual.URL:in ocen e .a m.com/
help/ opic/com.a m.doc.ddi0344k/DDI0344K_co ex_a8_ 3p2_ m.
pd ( isi ado 11-05-2020).
[Lim+95] Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-Do Rhee, Sang
Lyul Min, Chang Yun Pa k, Heonshik Shin, Kunsoo Pa k, Soo-Mook
Moon y Chong-Sang Kim. «An Accu a e Wo s Case Timing Analysis
o RISC P ocesso s». En: IEEE T ans. So wa e Eng. 21.7 (1995), págs. 593-604.
DOI:10.1109/32.392980.
Bibliog a ía 91
[Lis14] Bjö n Lispe . «SWEET - A Tool o WCET Flow Analysis (Ex ended Abs-
ac )». En: Le e aging Applica ions o Fo mal Me hods, Ve i ica ion and Va-
lida ion. Specialized Techniques and Applica ions - 6 h In e na ional Sympo-
sium, ISoLA 2014, Impe ial, Co u, G eece, Oc obe 8-11, 2014, P oceedings,
Pa II. Ed. po Tiziana Ma ga ia y Be nha d S e en. Vol. 8803. Lec u-
e No es in Compu e Science. Sp inge , 2014, págs. 482-485. DOI:10.
1007/978-3-662-45231-8 _38.
[LM95] Yau-Tsun S e en Li y Sha ad Malik. «Pe o mance Analysis o Embed-
ded So wa e Using Implici Pa h Enume a ion». En: P oceedings o he
32s Con e ence on Design Au oma ion, San F ancisco, Cali o nia, USA, Mos-
cone Cen e , June 12-16, 1995. Ed. po B yan P eas. ACM P ess, 1995,
págs. 456-461. DOI:10.1145/217474.217570.
[LMW96] Yau-Tsun S e en Li, Sha ad Malik y And ew Wol e. «Cache modeling
o eal- ime so wa e: beyond di ec mapped ins uc ion caches». En:
P oceedings o he 17 h IEEE Real-Time Sys ems Symposium (RTSS ’96), De-
cembe 4-6, 1996, Washing on, DC, USA. IEEE Compu e Socie y, 1996,
págs. 254-263. DOI:10.1109/REAL.1996.563722.
[LPR14] Hanbing Li, Isabelle Puau y E en Rohou. «T aceabili y o Flow In o -
ma ion: Reconciling Compile Op imiza ions and WCET Es ima ion».
En: 22nd In e na ional Con e ence on Real-Time Ne wo ks and Sys ems, RTNS
’14, Ve saille, F ance, Oc obe 8-10, 2014. Ed. po Ma hieu Jan, Belgacem
Ben Hedia, Joël Goossens y Clai e Maiza. ACM, 2014, pág. 97. DOI:10.
1145/2659787.2659805.
[LPR15] Hanbing Li, Isabelle Puau y E en Rohou. «T acing Flow In o ma ion
o Tigh e WCET Es ima ion: Applica ion o Vec o iza ion». En: 21s
IEEE In e na ional Con e ence on Embedded and Real-Time Compu ing Sys-
ems and Applica ions, RTCSA 2015, Hong Kong, China, Augus 19-21, 2015.
IEEE Compu e Socie y, 2015, págs. 217-226. DOI:10.1109/RTCSA.2015.
18.
[LRW91] Monica S. Lam, Edwa d E. Ro hbe g y Michael E. Wol . «The Cache
Pe o mance and Op imiza ions o Blocked Algo i hms». En: ASPLOS-
IV P oceedings - Fo h In e na ional Con e ence on A chi ec u al Suppo
o P og amming Languages and Ope a ing Sys ems, San a Cla a, Cali o -
nia, USA, Ap il 8-11, 1991. Ed. po Da id A. Pa e son y Bob Rau. ACM
P ess, 1991, págs. 63-74. DOI:10.1145/106972.106981.
[Lun02] Thomas Lundq is . «A WCET Analysis Me hod o Pipelined Mic o-
p ocesso s wi h Cache Memo ies». Tesis doc . Chalme s Uni e si y o
Technology, Go henbu g, Sweden, 2002. URL:h p://publica ions.
lib.chalme s.se/publica ion/606-a-wce -analysis-me hod- o -
pipelined-mic op ocesso s-wi h-cache-memo ies.
[Mal+11] Saeed Maleki, Yaoqing Gao, Ma íaa Jesús Ga za án, Tommy Wong y Da-
id A. Padua. «An E alua ion o Vec o izing Compile s». En: 2011 In-
e na ional Con e ence on Pa allel A chi ec u es and Compila ion Techniques,
PACT 2011, Gal es on, TX, USA, Oc obe 10-14, 2011. Ed. po Law ence
Rauchwe ge y Vi ek Sa ka . IEEE Compu e Socie y, 2011, págs. 372-382.
DOI:10.1109/PACT.2011.68.
[Mal08] Rajib Mall. Real- ime sys ems: heo y and p ac ice. Published by Do ling
Kinde sley (India), licensees o Pea son Educa ion in Sou h Asia, 2008.