La programación basada en transposición (TDS) es un algoritmo de equilibrio de carga para computación paralela . Fue desarrollado en la Vrije Universiteit en Ámsterdam , Países Bajos, como un algoritmo para resolver acertijos . El algoritmo proporciona una aceleración casi lineal con algunos problemas y escala extremadamente bien. Fue publicado [1] por John Romein, Aske Plaat, Henri Bal y Jonathan Schaeffer .
En un rompecabezas, todas las jugadas posibles se pueden representar en un árbol con las posiciones del tablero correspondientes a los nodos, los movimientos correspondientes a los bordes, la posición inicial como la raíz del árbol y las soluciones como las hojas. Los ciclos en un camino, es decir, los movimientos que dan como resultado una posición que ya se encuentra más arriba en el árbol, se dejan fuera del árbol porque nunca pueden conducir a una solución óptima.
En la mayoría de los rompecabezas, diferentes órdenes de acciones pueden llevar a la misma posición del rompecabezas. En los rompecabezas donde las acciones anteriores no influyen en la solución, solo necesita evaluar esta posición una vez para obtener una solución para ambos caminos. Para evitar evaluar la misma posición más de una vez (y así desperdiciar ciclos de cálculo), los programas escritos para resolver este tipo de rompecabezas usan tablas de transposición . Una transposición es un estado del rompecabezas al que se puede llegar por diferentes caminos pero que tiene la misma solución. Cada vez que un programa de este tipo comienza a evaluar una posición, primero busca en una tabla si la posición ya ha sido evaluada. Si es así, la solución se toma de la tabla en lugar de calcularse, lo que ahorra una gran cantidad de tiempo.
Sin embargo, en computación paralela, este enfoque tiene un serio inconveniente. Para aprovechar al máximo las ventajas de las búsquedas por transposición, todos los ordenadores de la red tienen que comunicar sus soluciones a los demás de una forma u otra, o se corre el riesgo de resolver algunas posiciones de forma redundante. Esto genera una sobrecarga de comunicación importante, lo que significa que gran parte del tiempo de todos los ordenadores se dedica a comunicarse con los demás en lugar de resolver el problema.
Para resolver este inconveniente, se ha adoptado un enfoque que integra la resolución del problema y el equilibrio de carga . Para empezar, se define una función que asigna un valor único a cada posición de la placa. A cada ordenador de la red se le asigna un rango de posiciones de la placa para las que tiene autoridad. Cada ordenador tiene su propia tabla de transposición y una cola de trabajos. Siempre que un ordenador termina su trabajo actual, obtiene un nuevo trabajo de la cola. A continuación, calcula todas las posibles posiciones distintas a las que se puede llegar desde la posición actual en una sola acción. Todo esto es la resolución de problemas basada en la transposición tradicional. Sin embargo, en el método tradicional, el ordenador ahora, para cada posición recién calculada, le preguntaría al ordenador que tiene autoridad sobre esa posición si tiene una solución para ella. Si no la tiene, el ordenador calcula la solución de forma recursiva y la envía al ordenador bajo cuya autoridad cae. Esto es lo que causa una gran cantidad de sobrecarga de comunicación.
Lo que hace TDS es, en lugar de preguntar a otra persona si tiene la solución, agregar el problema a la cola de trabajos de otra persona. En otras palabras, cada vez que una computadora tiene una posición en la placa para la cual desea una solución, simplemente la envía por la red a la computadora responsable y ya no se preocupa más por ella . Solo si un problema cae dentro de su propio rango de autoridad, una computadora intentará buscar si tiene una solución almacenada en su propia tabla. Si no, simplemente la agrega a su propia cola. Si tiene una solución, ya no tiene que calcular nada más y obtiene un nuevo trabajo de la cola.
La gran diferencia entre la resolución de problemas basada en transposición tradicional y el TDS es que preguntar a una computadora si ha resuelto un problema sigue un enfoque de solicitud-respuesta, en el que la computadora que pregunta a la otra computadora tiene que esperar una respuesta. En el TDS, reenviar un trabajo a otra computadora no implica ninguna espera, porque se sabe (por diseño) que la otra computadora aceptará el trabajo e intentará resolverlo. Esto significa que la latencia (la principal causa de demoras en los modelos de solicitud-respuesta) no es un problema, porque una computadora simplemente nunca espera una respuesta. El hardware o el sistema operativo pueden garantizar que el mensaje llegue a su destino, por lo que el programa no tiene que preocuparse por nada más después de reenviar el trabajo.
El TDS produce resultados espectaculares en comparación con los algoritmos tradicionales, llegando incluso a alcanzar una aceleración superlineal (aunque sólo en un sentido de la palabra). Esta propiedad se consigue porque los ordenadores tienen una cantidad limitada de memoria y, para problemas grandes, no se pueden almacenar todas las transposiciones. Por lo tanto, algunas transposiciones se calcularán más de una vez. Como 16 ordenadores tienen 16 veces más memoria que 1 (suponiendo que todos los ordenadores son idénticos), 16 ordenadores con TDS pueden almacenar más transposiciones que 1 y, por tanto, tienen que calcular menos. Cuando un ordenador tiene 16 veces más memoria que cada uno de los del grupo de 16, la aceleración es apenas inferior a la lineal.
Debido a que el esquema de comunicación en TDS utiliza únicamente comunicación punto a punto y no difusión u otra comunicación grupal, la cantidad total de comunicación es proporcional a la cantidad de computadoras que participan en el cálculo. Debido a esto, TDS escala muy bien a sistemas paralelos con más computadoras. Además, debido a que la latencia no es un problema, TDS también es escalable en un sentido geográfico.