Concurso EDA

Omar Pera Mira

Estructura del programa

Funcionamiento: Entrada de datos

Funcionamiento: Entrada de datos

Archivos proyectados en memoria

• Se utiliza la llamada al sistema mmap()
• Datos accedidos mediante referencias a posiciones de memoria (punteros)
• No necesidad buffers intermedios
• Acceso a cada página de disco cuando necesita ser leída

Funcionamiento: Estructuras de datos

Funcionamiento: Estructuras de datos

Diccionario: vector de objetos

• Cada elemento del vector --> información de una palabra del lenguaje origen
• Indexado por el id de dicho token
• Lista de nodos con el id de la palabra destino y su probabilidad
• Ordenado parcialmente por probabilidad (Se explicara más tarde)

Funcionamiento: Estructuras de datos

Funcionamiento: Estructuras de datos

Bigramas: Tabla Hash

• Clave --> Id de las 2 palabras (concatenación de 2 enteros de 32-bit)
• Valor --> Probabilidad condicional asociada
• Funcion hash6432shift() realizada por Thomas Wang

Funcionamiento: Cuckoo Hash

Funcionamiento: Cuckoo Hash

Correspondencia biunívoca entre tokens y enteros

• Usa tablas T1 y T2 con 2 funciones hash h1, h2
• Guarda la cadena X en T1[h1(x)] o en T2[h2(x)]
• Si no está libre, se inserta y se repite el proceso con la ocupada previamente

Funcionamiento: Cuckoo Hash

Mejoras

• Cada cubeta alberga [Concat, prob, hash1, hash2]
• Comparación de 2 enteros de 32-bit (no strcmp()) ----> No hace falta que guardemos las cadenas de Diccionario
• Busqueda en tiempo constante en el peor caso
• Tamaño dinamico con el tamaño de fichero

Funcionamiento: Salida de datos

Funcionamiento: Salida de datos

• Reservamos bloques en memoria
• Concatenamos las distintas traducciones a dichos buffers
• Volcado mediante la llamada al sistema write()

Funcionamiento: Traducción

Funcionamiento: Traducción

Para cada palabra a traducir:

• Ordenamos parcialmente la lista correspondiente a sus posibles traducciones (Diccionario)
• Itero sobre la probabilidad más alta
• Concateno dicho id con la palabra anterior y busco en la tabla hash de Bigramas --> Producto de probabilidades
• Producto máximo --> Resultado

Funcionamiento: Traducción

¿Para que ordenar si no se pudiera detener el bucle?

---> Calcular el máximo producto de probabilidades que se puede llegar a obtener en futuras iteraciones

• Optimo: Producto de los maximos de las ternas restantes de Big y Dic
• Estimación de dichos máximos:
  • Dic: el siguiente elemento, del vector semi-ordenado.
  • Big: maxima probabilidad, contando todos los elementos. (*)

Otras optimizaciones

• Probabilidad --> Entero de 32-bit
• Ordenación parcial con una versión de QuickSort
• Pooling de memoria
• Tamaño de las estructuras de datos ajustado al tamaño de los ficheros de entrada, y ajustado a potencias de 2

¿Preguntas?