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.
-
-
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.