Visto que esta de moda esto de los hilos de twitter, voy a volver a contar mi ultima investigacion, pero esta vez en espanol (a pesar de la falta de tildes y enes en este portatil xD) y tratando de hacerlo de forma mas llana.
-
-
El tiempo depende de detalles muy sutiles y generalmente nada bien documentados de la microarquitectura, lo que a menudo desencadena tareas de ingenieria inversa para arrojar algo mas de luz sobre esta.
Prikaži ovu nit -
Las politicas de reemplazamiento de caches juegan un papel especialmente importante aqui, ya que son estas las que controlan el contenido que se almacena en o se elimina de la jerarquia de caches.
Prikaži ovu nit -
Es posible modelar las politicas de reemplazamiento como automatas, maquinas de Mealy, de forma natural. Imaginad una maquina de estados donde cada bloque de memoria accedido actua como entrada, causa una transicion, y produce una salida, que es o bien un "hit", o un "miss".pic.twitter.com/Numb4fi1Nq
Prikaži ovu nit -
Dana Angluin propuso, en 1987, su famoso algoritmo L* para aprendizaje de lenguajes regulares. L* nos permite aprender cualquier automata finito determinista (DFA), o cualquier lenguaje regular, con coste polinomico en el numero de estados final, utilizando tan solo...
Prikaži ovu nit -
...preguntas de "inclusion" (esta la palabra en el lenguaje) y preguntas de equivalencia (acepta el automata el lenguaje deseado). Existen librerias como LearnLib, que implementan no solo L* sino multiples extensiones, incluyendo una para aprendizaje de maquinas Mealy.
Prikaži ovu nit -
Suficiente contexto. Nuestra primera contribucion ha sido CacheQuery (https://github.com/cgvwzq/cachequery …) una interfaz, libre de ruido e interferencias, para interactuar con cualquier conjunto de la jerarquia de caches de la CPU.
Prikaži ovu nit -
CacheQuery nos permite especificar cualquier secuencia de bloques (e.g. "a b c a"), selecciona las direcciones de memoria necesarias, genera el codigo x86 para la evaluacion, y nos devuelve una secuencia de aciertos y fallos (e.g. "miss miss miss hit").
Prikaži ovu nit -
Sin embargo, intentar aprender el automata de una cache directamente es muy ineficiente, ya que la maquina de estados es enorme. Nuestra segunda contribucion trata de mitigar este problema, y para ello explotamos algunas simetrias presentes en las caches, por ejemplo...
Prikaži ovu nit -
..."a b c a" produce la misma salida que "c b a c". Con esto en mente proponemos Polca, un algoritmo que nos permite interactuar con un automata abstracto, que contiene tan solo el comportamiento esencial de la politica de reemplazamiento, a traves de preguntas a una cache real.pic.twitter.com/0twXPP2FRK
Prikaži ovu nit -
Con Polca, somos capaces de conectar LearnLib y CacheQuery para aprender el automata de cualquier politica de reemplazamiento determinista en una CPU. De hecho, hemos sido capaces de descubrir 2 politicas previamente no documentadas usadas en procesadores Skylake y Kaby Lake! :Dpic.twitter.com/dlNORlgZZh
Prikaži ovu nit -
El ultimo problema que tenemos, es que el automata aprendido es generalmente demasiado complejo para ser interpretado por un humano :(
Prikaži ovu nit -
Nuestra tercera contribucion consiste en crear una "plantilla" de un programa que implementa polticas de reemplazamiento con varios "huecos", es decir, dejamos partes del programa como valores o expresiones a medio especificar.
Prikaži ovu nit -
Sketch, una herramienta de sintesis de codigo, recibe la plantilla junto con varias restricciones extraidas del automata, y rellena todos los huecos sintetizando un programa que implementa exactamente la misma logica que nuestro automata, pero que es interpretable por un humano.
Prikaži ovu nit -
Podeis encontrar nuestra herramienta usando LearnLib y Polca, ademas de las plantillas y las soluciones sintetizadas en https://github.com/cgvwzq/polca :)
Prikaži ovu nit -
Ah, y para los interesados, aqui el paper original en ingles: https://vwzq.net/papers/cachequery19.pdf …
Prikaži ovu nit
Kraj razgovora
Novi razgovor -
Čini se da učitavanje traje već neko vrijeme.
Twitter je možda preopterećen ili ima kratkotrajnih poteškoća u radu. Pokušajte ponovno ili potražite dodatne informacije u odjeljku Status Twittera.