Catalytic Computing aprovecha al máximo la potencia de un disco duro completo

“Obviamente” es una palabra peligrosa, incluso en situaciones que parecen sencillas. Supongamos, por ejemplo, que necesita realizar un cálculo importante. Puede elegir entre dos computadoras que son casi idénticas, excepto que una tiene un disco duro adicional lleno de valiosas fotos familiares. Es natural suponer que las dos opciones son igualmente buenas: un disco adicional sin espacio libre no ayudará a realizar el cálculo.

“Obviamente, no ayuda, ¿verdad?”, dijo. Bruno Loff, científico informático de la Universidad de Lisboa.

Incorrecto. En 2014, Loff y otros cuatro investigadores descubrieron que, en principio, añadir espacio de almacenamiento completo puede hacer que los ordenadores sean más potentes. Su marco teórico, denominado computación catalítica, se ha convertido en un objeto de estudio por derecho propio. Y recientemente, también ayudó a los investigadores a demostrar una resultado sorprendente en un área relacionada con la informática: El enfoque estándar para resolver una importante pregunta abierta sobre el papel de la memoria en la computación es, muy probablemente, un callejón sin salida.

“Es toda una hazaña”, dijo Pierre McKenzie, un teórico de la complejidad de la Universidad de Montreal. “Realmente aprecio estos resultados”.

Casi sin memoria

La computación catalítica surgió del trabajo en la teoría de la complejidad computacional, la rama de la informática centrada en los recursos necesarios para resolver diferentes problemas. Todos los problemas que los teóricos de la complejidad consideran se pueden resolver con procedimientos paso a paso llamados algoritmos. Pero no todos los algoritmos son iguales: algunos se ejecutan más rápido que otros o requieren menos espacio en la memoria de una computadora. Los teóricos de la complejidad clasifican los problemas en diferentes clases basado en el comportamiento de los mejores algoritmos conocidos para resolverlos.

La clase más famosa, llamada “P”, contiene todos los problemas que se sabe que tienen algoritmos rápidos, como encontrar el número más pequeño en una lista o encontrar el camino más corto entre dos puntos en una red. Otra clase, llamada “L”, establece un estándar más alto para la membresía: los problemas en L deben tener algoritmos que no solo sean rápidos, sino que también utilicen poca memoria. El problema del “número más pequeño en una lista” es un ejemplo. Por definición, todos los problemas en L también están en P, pero los investigadores se han preguntado durante mucho tiempo si lo inverso también es cierto.

“La pregunta básica es: ¿Puedo tomar cualquier problema en P y resolverlo usando muy, muy poca memoria?”, dijo McKenzie.

La mayoría de los investigadores sospechan que la respuesta es no. Para demostrarlo, tendrán que elegir un problema específico en P y demostrar que es imposible resolverlo con cualquier truco ingenioso que ahorre memoria.

A finales de la década de 2000, McKenzie y el pionero teórico de la complejidad Stephen Cook Se ideó un problema que parecía un candidato prometedor. Se denomina problema de evaluación de árbol y consiste en resolver repetidamente un problema matemático más simple que convierte un par de números de entrada en un único resultado. Las copias de este problema matemático se organizan en capas, como los partidos de una clasificación de un torneo: los resultados de cada capa se convierten en las entradas de la siguiente capa hasta que solo queda una salida. Los diferentes algoritmos de evaluación de árbol representan diferentes estrategias para calcular este resultado final a partir de las entradas iniciales: pueden realizar los cálculos en un orden diferente o registrar los resultados de los pasos intermedios de una manera diferente.

Muchos algoritmos pueden resolver el problema de evaluación de árboles rápidamente, colocándolo en la clase P. Pero cada uno de estos algoritmos debe dedicar algo de memoria a los números con los que trabaja, al mismo tiempo que almacena los números que ya ha calculado para usarlos en pasos posteriores. Es por eso que Cook y McKenzie sospecharon que el problema era imposible de resolver usando una memoria limitada. Formalizaron esta intuición en un papel 2010 Fue coautor junto con otros tres investigadores y demostró que cada algoritmo ordinario para resolver el problema de evaluación de árboles requería demasiada memoria para calificar para ser miembro de L.

Pero su trabajo no descartaba la posibilidad de algoritmos extraños que pudieran utilizar de algún modo el mismo trozo de memoria para almacenar y realizar cálculos simultáneamente, el equivalente informático a utilizar una página llena de notas importantes como borrador. Cook y McKenzie pensaban que esos algoritmos tan extravagantes no podían existir, y estaban lo suficientemente seguros como para apostar a que así sería: cualquiera que pudiera demostrar que estaban equivocados ganaría 100 dólares.

Conversión catalítica

Michal Koucký, un teórico de la complejidad de la Universidad Charles de Praga, se enteró del resultado de la evaluación de árboles por boca de Cook durante un año sabático en Toronto en 2011. Se decidió a terminar lo que Cook y McKenzie habían empezado, demostrando que no hay forma de hacer cálculos adicionales utilizando la memoria que guarda datos para más adelante. La búsqueda de Koucký lo llevaría a un desvío inesperado hacia el descubrimiento de la computación catalítica. Casi una década después, ese descubrimiento inspiraría a dos jóvenes investigadores a volver a la evaluación de árboles y resolver la apuesta de Cook y McKenzie de una vez por todas.

Pero volvamos a la historia de la computación catalítica. Todo comenzó cuando Koucký visitó a unos colegas en Ámsterdam y les planteó la pregunta que lo había estado preocupando en términos más simples: ¿qué se puede hacer con una memoria que ya está llena?

“Nada”, fue la respuesta obvia. “Pensé: ‘Está bien, esto es, por supuesto, muy inútil y lo vamos a demostrar’”, dijo. Harry Buhrman, el líder del grupo de Amsterdam. “Y luego no pudimos demostrarlo”.

El gran avance llegó meses después, cuando Buhrman estaba visitando a su colaborador habitual. ricardo cleve en la Universidad de Waterloo. Decidieron centrarse en un escenario extremo, uno en el que la memoria llena es muy grande. Si un ordenador con poca memoria libre puede acceder a esta enorme memoria llena, ¿le permitiría eso resolver problemas que serían imposibles con la memoria libre únicamente? Es como la pregunta del “disco duro lleno de fotos familiares”, pero con un disco duro del tamaño de un centro de datos.

Si esos datos adicionales son intocables (no se puede interactuar con ellos en absoluto), definitivamente no sirven de nada. Pero ¿qué pasa si se te permite modificar algunos de los bits que codifican estos datos, siempre y cuando prometas restablecerlos cuando hayas terminado? No puedes simplemente mantener un registro de tus cambios, ya que eso ocuparía aún más espacio, así que en su lugar tendrás que asegurarte de que tus cambios sean fácilmente reversibles. Es más, no puedes elegir el contenido de los datos adicionales, así que todo lo que hagas debe funcionar para cualquier posible configuración inicial de bits.

Se trata de restricciones bastante estrictas, por lo que no era obvio que la memoria adicional pudiera resultar útil. Pero para su sorpresa, Buhrman y Cleve demostraron que, si se modifican los bits de la manera correcta, realmente se puede obtener una mayor potencia computacional de una memoria llena.

“Eso fue un shock para todos”, dijo Loff, quien en ese momento era un estudiante de posgrado en el grupo de Buhrman y trabajaba en la cuestión de la memoria con su compañero de estudios. Florian SpeelmanEl equipo pronto extendió el resultado a una clase aún más amplia de problemas y publicó sus resultados combinados en el 2014.

El nuevo marco fue denominado computación catalítica, tomando prestado un término de la química. “Sin el catalizador, la reacción no habría tenido lugar”, dijo Raghunath Tewari, un teórico de la complejidad del Instituto Indio de Tecnología de Kanpur. “Pero el catalizador en sí permanece inalterado”.

No muy lejos del árbol

Un pequeño grupo de investigadores siguió desarrollando la computación catalítica, pero nadie intentó siquiera aplicarla al problema de evaluación de árboles que había inspirado inicialmente la búsqueda de Koucký. Para ese problema, la pregunta que quedaba abierta era si una pequeña cantidad de memoria podría usarse para almacenamiento y computación simultáneamente. Pero las técnicas de computación catalítica dependían de que la memoria adicional, completa, fuera muy grande. Si se reduce esa memoria, las técnicas ya no funcionan.

Aun así, un joven investigador no pudo evitar preguntarse si habría una manera de adaptar esas técnicas para reutilizar la memoria en un algoritmo de evaluación de árboles. Su nombre era James Cook, y para él el problema de evaluación de árboles era personal: Stephen Cook, el legendario teórico de la complejidad que lo inventó, es su padre. James incluso había trabajado en él en la escuela de posgrado, aunque se centró principalmente en temas completamente no relacionadosCuando se encontró con el artículo original sobre computación catalítica en 2014, James estaba a punto de graduarse y dejar la academia para dedicarse a la ingeniería de software. Pero incluso mientras se adaptaba a su nuevo trabajo, seguía pensando en la computación catalítica.

“Tenía que entenderlo y ver qué se podía hacer”, dijo.

Durante años, James Cook experimentó con un enfoque catalítico para el problema de la evaluación de árboles en su tiempo libre. Dio una charla sobre su progreso en un simposio de 2019 en honor a su padre. trabajo innovador en teoría de la complejidad. Después de la charla, se le acercó un estudiante de posgrado llamado Ian Mertz, quien se había enamorado de la computación catalítica cinco años antes, después de aprender sobre ella cuando era un joven e impresionable estudiante universitario.

“Fue como una escena en la que un pajarito tomó su impronta”, dijo Mertz.

Cook y Mertz unieron fuerzas y sus esfuerzos pronto dieron frutos. En 2020, idearon un algoritmo que resolvió el problema de evaluación de árboles con menos memoria que el mínimo necesario conjeturado por Cook padre y McKenzie, aunque estaba apenas por debajo de ese umbral. Aun así, eso fue suficiente para cobrar la apuesta de $100; convenientemente para los Cook, la mitad de esa cantidad permaneció en la familia.

Pero aún quedaba trabajo por hacer. Los investigadores habían comenzado a estudiar la evaluación de árboles porque parecía que finalmente podría proporcionar un ejemplo de un problema en P que no está en L; en otras palabras, un problema relativamente fácil que no se puede resolver usando muy poca memoria. El nuevo método de Cook y Mertz usaba menos memoria que cualquier otro algoritmo de evaluación de árboles, pero aún así usaba significativamente más que cualquier algoritmo para un problema en L. La evaluación de árboles estaba inactiva, pero no descartada.

En 2023, Cook y Mertz presentaron un algoritmo mejorado que utilizaba mucha menos memoria, apenas más que el máximo permitido para problemas en L. Muchos investigadores ahora sospechan que la evaluación de árboles se realiza en L después de todo, y que una prueba es solo una cuestión de tiempo. Los teóricos de la complejidad pueden necesitar un enfoque diferente para el problema de P versus L.

Mientras tanto, los resultados de Cook y Mertz han despertado el interés en la computación catalítica, con nuevos trabajos que exploran conexiones con la aleatoriedad y los efectos de permitir una pocos errores en restablecer la memoria completa a su estado original.

“Aún no hemos terminado de explorar lo que podemos hacer con estas nuevas técnicas”, dijo McKenzie. “Podemos esperar aún más sorpresas”.