Función limitada a la memoria

En informática , un problema computacional está limitado por la memoria cuando el tiempo que tarda en completarse depende principalmente de la cantidad de memoria libre necesaria para almacenar los datos de trabajo . Esto contrasta con los algoritmos que están limitados por la capacidad de cálculo , donde el número de pasos de cálculo elementales es el factor determinante.

En ocasiones, los límites de memoria y de computación pueden intercambiarse, por ejemplo, guardando y reutilizando resultados preliminares o utilizando tablas de consulta .

Las funciones vinculadas a la memoria y las funciones de memoria están relacionadas en el sentido de que ambas implican un acceso extenso a la memoria, pero existe una distinción entre ambas.

Las funciones de memoria utilizan una técnica de programación dinámica llamada memorización para mitigar la ineficiencia que podría producirse en la recursión . Se basa en la sencilla idea de calcular y almacenar soluciones a subproblemas para poder reutilizarlas posteriormente sin necesidad de volver a calcular los subproblemas . El ejemplo más conocido que aprovecha la memorización es un algoritmo que calcula los números de Fibonacci . El siguiente pseudocódigo utiliza recursión y memorización, y se ejecuta en tiempo de CPU lineal :

Fibonacci ( n ) { para i = 0 a n -1 resultados [ i ] = -1 // -1 significa indefinidoreturn Fibonacci_Results ( resultados , n ); }Fibonacci_Results ( resultados , n ) { if ( resultados [ n ] != -1 ) // Si ya se ha resuelto antes, devolver resultados [ n ] // buscarlo. if ( n == 0 ) val = 0 else if ( n == 1 ) val = 1 else val = Fibonacci_Results ( resultados , n -2 ) + Fibonacci_Results ( resultados , n -1 ) resultados [ n ] = val // Guardar este resultado para su reutilización.devolver val }

Compare lo anterior con un algoritmo que utiliza únicamente recursión y que se ejecuta en un tiempo de CPU exponencial :

Fibonacci recursivo ( n ) { si ( n == 0 ) devolver 0 si ( n == 1 ) devolver 1return Recursive_Fibonacci ( n -1 ) + Recursive_Fibonacci ( n -2 ) }

Si bien el algoritmo exclusivamente recursivo es más sencillo y elegante que el algoritmo que utiliza recursión y memorización, este último tiene una complejidad temporal significativamente menor que el primero.

El término "función con dependencia de memoria" se ha popularizado recientemente y se utiliza principalmente para describir una función que emplea la operación XOR y consiste en una serie de cálculos en los que cada cálculo depende del anterior. Las funciones con dependencia de memoria han sido durante mucho tiempo una herramienta importante para mejorar la complejidad temporal, pero las funciones con dependencia de memoria han tenido muchas menos aplicaciones.

Las funciones que dependen de la memoria podrían ser útiles en un sistema de prueba de trabajo que podría disuadir el spam , que se ha convertido en un problema de proporciones epidémicas en Internet .

En 1992, las investigadoras de IBM Cynthia Dwork y Moni Naor publicaron un artículo en CRYPTO 1992 titulado " Pricing via Processing or Combatting Junk Mail" ^{[ 1 ]} , en el que sugerían la posibilidad de utilizar funciones que consumen muchos recursos de la CPU para disuadir a los usuarios de enviar spam. El plan se basaba en la idea de que los usuarios de computadoras son mucho más propensos a abusar de un recurso si el costo de dicho abuso es insignificante: la razón fundamental por la que el spam se ha vuelto tan desenfrenado es que enviar un correo electrónico tiene un costo minúsculo para los spammers.

Dwork y Naor propusieron que el envío de spam podría reducirse mediante la introducción de un coste adicional en forma de un costoso cálculo de CPU : las funciones que dependen de la CPU consumirían recursos de la CPU en la máquina del remitente para cada mensaje, evitando así que se enviaran grandes cantidades de spam en un corto período de tiempo.

El esquema básico que protege contra los abusos es el siguiente: Dado un remitente, un destinatario y un mensaje de correo electrónico. Si el destinatario ha aceptado previamente recibir correos electrónicos del remitente, el mensaje se transmite de la forma habitual. De lo contrario, el remitente calcula una función G(Mensaje) y envía (Mensaje, G(Mensaje)) al destinatario. El destinatario comprueba si lo que recibe del remitente tiene el formato (Mensaje, G(Mensaje)) . Si es así, el destinatario acepta el mensaje. De lo contrario, el destinatario lo rechaza.

La función G() se selecciona de forma que la verificación por parte del Receptor sea relativamente rápida (por ejemplo, en un milisegundo) y que el cálculo por parte del Remitente sea algo lento (al menos varios segundos). Por lo tanto, se desincentivará al Remitente a enviar Mensajes a múltiples destinatarios sin acuerdos previos: el coste, tanto en tiempo como en recursos informáticos, de calcular G() repetidamente resultará prohibitivo para un remitente de spam que pretenda enviar millones de correos electrónicos.

El principal problema de utilizar el esquema anterior es que las CPU rápidas calculan mucho más rápido que las lentas. Además, los sistemas informáticos de gama alta también cuentan con sofisticados sistemas de procesamiento y otras características ventajosas que facilitan los cálculos. Como resultado, un remitente de spam con un sistema de última generación apenas se verá afectado por esta medida disuasoria, mientras que un usuario típico con un sistema mediocre se verá perjudicado. Si un cálculo tarda unos segundos en un PC nuevo , puede tardar un minuto en un PC antiguo y varios minutos en una PDA , lo que podría ser una molestia para los usuarios de PC antiguos, pero probablemente inaceptable para los usuarios de PDA. La disparidad en la velocidad de la CPU del cliente constituye uno de los principales obstáculos para la adopción generalizada de cualquier esquema basado en una función limitada por la CPU. Por lo tanto, los investigadores se centran en encontrar funciones que la mayoría de los sistemas informáticos evalúen aproximadamente a la misma velocidad, de modo que los sistemas de gama alta puedan evaluar estas funciones algo más rápido que los de gama baja (entre 2 y 10 veces más rápido, pero no entre 10 y 100 veces más rápido), como podrían implicar las disparidades de CPU. Estas proporciones son suficientemente " igualitarias " para las aplicaciones previstas: las funciones son eficaces para desalentar los abusos y no añaden una demora prohibitiva a las interacciones legítimas, en una amplia gama de sistemas.

El nuevo enfoque igualitario consiste en utilizar funciones limitadas por memoria. Como se mencionó anteriormente, una función limitada por memoria es aquella cuyo tiempo de cálculo está determinado principalmente por el tiempo de acceso a la memoria. Estas funciones acceden a ubicaciones en una amplia región de la memoria de forma impredecible, lo que hace que el uso de cachés no sea efectivo. En los últimos años, la velocidad de la CPU ha aumentado drásticamente, pero el desarrollo de memorias principales más rápidas ha avanzado relativamente poco. Dado que la relación de latencias de memoria en las máquinas construidas en los últimos cinco años no suele ser superior a dos, y casi siempre inferior a cuatro, las funciones limitadas por memoria serán igualitarias para la mayoría de los sistemas en el futuro previsible.

• Arquitectura de computadoras
• Limitado por la CPU
• Programación dinámica
• Limitado a E/S
• Memorización
• Función de memoria dura
• Subestructura óptima
• Prueba de trabajo
• Recursión
• cuello de botella de memoria

• Implementación de una función limitada a la memoria
• Arquitectura de computadoras
• Cómo funciona la memoria de la computadora
• Programación dinámica
• Limitado por la CPU frente a limitado por la E/S
• Spam – Información para el consumidor de la FTC