De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

El límite de memoria se refiere a una situación en la que el tiempo para completar un problema computacional dado se decide principalmente por la cantidad de memoria requerida para almacenar los datos de trabajo . Esto contrasta con los algoritmos vinculados al cálculo , donde el número de pasos de cálculo elementales es el factor decisivo.

Los límites de memoria y cálculo a veces se pueden intercambiar entre sí, por ejemplo, guardando y reutilizando resultados preliminares o usando tablas de búsqueda .

Funciones vinculadas a la memoria y funciones de la memoria

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

Las funciones de memoria utilizan una técnica de programación dinámica llamada memorización para aliviar la ineficacia de la recursividad que podría ocurrir. Se basa en la simple idea de calcular y almacenar soluciones a subproblemas para que las soluciones puedan reutilizarse posteriormente sin volver a calcular los subproblemas . El ejemplo más conocido que se aprovecha de la memorización es un algoritmo que calcula los números de Fibonacci . El siguiente pseudocódigo usa recursividad y memorización, y se ejecuta en tiempo de CPU lineal :

 Fibonacci  ( n )  {  para  i  =  0  a  n -1  resultados [ i ]  =  -1  // -1 significa sin definir return  Fibonacci_Results  ( resultados ,  n );  } Fibonacci_Results  ( results ,  n )  {  if  ( results [ n ]  ! =  -1 )  // Si se ha resuelto antes,  devuelve  resultados [ n ]  // búscalo.  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  // Guarde este resultado para reutilizarlo. return  val  }

Compare lo anterior con un algoritmo que solo usa recursividad y se ejecuta en un tiempo de CPU exponencial :

 Recursive_Fibonacci  ( n )  {  if  ( n  ==  0 )  return  0  if  ( n  ==  1 )  return  1 return  Recursive_Fibonacci  ( n -1 )  +  Recursive_Fibonacci  ( n -2 )  }

Si bien el algoritmo solo recursivo es más simple y elegante que el algoritmo que usa recursividad y memorización, este último tiene una complejidad de tiempo significativamente menor que el primero.

El término "función ligada a la memoria" ha aparecido recientemente y se usa principalmente para describir una función que usa XOR y consiste en una serie de cálculos en los que cada cálculo depende del cálculo anterior. Mientras que las funciones de memoria han sido durante mucho tiempo un actor importante en la mejora de la complejidad del tiempo, las funciones ligadas a la memoria han visto muchas menos aplicaciones. Recientemente [ ¿cuándo? ] , sin embargo, los científicos han propuesto un método que utiliza funciones ligadas a la memoria como un medio para disuadir a los spammers de abusar de los recursos, lo que podría ser un gran avance en esa área.

Uso de funciones vinculadas a la memoria para evitar el spam

Las funciones ligadas a 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, los científicos de investigación de IBM Cynthia Dwork y Moni Naor publicaron un artículo en CRYPTO 1992 titulado Pricing via Processing o Combatting Junk Mail , [1] sugiriendo la posibilidad de usar funciones vinculadas a la CPU para disuadir a los abusadores de enviar spam. El esquema se basó en la idea de que es mucho más probable que los usuarios de computadoras abusen de un recurso si el costo de abusar del recurso es insignificante: la razón subyacente 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 spam podría reducirse inyectando un costo adicional en la forma de un costoso cálculo de CPU : las funciones vinculadas a la CPU consumirían recursos de CPU en la máquina del remitente para cada mensaje, evitando así que se envíen grandes cantidades de spam en un período corto.

El esquema básico que protege contra abusos es el siguiente:
Sea S el remitente, R el destinatario y M un correo electrónico. Si R ha aceptado de antemano recibir correo electrónico de S , entonces M se transmite de la forma habitual. De lo contrario, S calcula alguna función G (M) y envía (M, G (M)) a R . R comprueba si lo que recibe de S tiene la forma (M, G (M)) . En caso afirmativo, R acepta M . De lo contrario, R rechaza M .La figura de la derecha muestra casos en los que no hubo acuerdos previos .

La función G () se selecciona de manera que la verificación por R sea ​​relativamente rápida (tomando un milisegundo) y tal que el cálculo por S sea ​​algo lento (involucrando al menos varios segundos). Por lo tanto, se desalentará a S de enviar M a múltiples destinatarios sin acuerdos previos: el costo en términos de tiempo y recursos informáticos de computar G () repetidamente se volverá muy prohibitivo para un spammer que tiene la intención de enviar muchos 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 CPU lentas. Además, los sistemas informáticos de gama alta también tienen tuberías sofisticadas y otras características ventajosas que facilitan los cálculos. Como resultado, un spammer con un sistema de última generación apenas se verá afectado por tal disuasión, mientras que un usuario típico con un sistema mediocre se verá afectado negativamente. Si un cálculo tarda unos segundos en una PC nueva , puede tardar un minuto en una PC vieja y varios minutos en una PDA., lo que puede resultar una molestia para los usuarios de PC antiguas, pero probablemente inaceptable para los usuarios de PDA. La disparidad en la velocidad de la CPU del cliente constituye uno de los obstáculos importantes para la adopción generalizada de cualquier esquema basado en una función vinculada a la CPU. Por lo tanto, los investigadores se preocupan por encontrar funciones que la mayoría de los sistemas informáticos evaluarán aproximadamente a la misma velocidad, de modo que los sistemas de gama alta puedan evaluar estas funciones algo más rápido que los sistemas de gama baja (2 a 10 veces más rápido, pero no 10 a 100 veces más rápido). más rápido) como pueden implicar las disparidades de CPU. Estas proporciones son lo suficientemente " igualitarias " para las aplicaciones previstas: las funciones son eficaces para desalentar los abusos y no añaden un retraso prohibitivo a las interacciones legítimas en una amplia gama de sistemas.

El nuevo enfoque igualitario se basa en funciones ligadas a la memoria. Como se indicó anteriormente, una función limitada a la memoria es una función cuyo tiempo de cálculo está dominado por el tiempo empleado en acceder a la memoria. Una función vinculada a la memoria accede a ubicaciones en una gran región de la memoria de una manera impredecible, de tal manera que el uso de cachés no es efectivo. En los últimos años, la velocidad de la CPU ha crecido drásticamente, pero ha habido un progreso comparativamente pequeño en el desarrollo de una memoria principal más rápida. Dado que las proporciones de latencias de memoria de las máquinas construidas en los últimos cinco años no suelen ser superiores a dos, y casi siempre inferiores a cuatro, la función ligada a la memoria será igualitaria para la mayoría de los sistemas en el futuro previsible.

Ver también

Referencias

  1. ^ Dwork, Cynthia ; Naor, Moni (1992). "Fijación de precios mediante el procesamiento o la lucha contra el correo basura" . Avances en criptología - CRYPTO 1992, 12ª Conferencia Anual Internacional de Criptología, Santa Bárbara, California, EE. UU., 16 al 20 de agosto de 1992, Actas : 139–147. doi : 10.1007 / 3-540-48071-4_10 .( versión actualizada del mismo )
  • Abadi, M., Burrows, M., Manasse, M. y Wobber, T. (mayo de 2005). Funciones moderadamente difíciles, vinculadas a la memoria , transacciones ACM en tecnología de Internet .
  • Dwork, C., Goldberg, A. y Naor, M. (2003). Sobre funciones limitadas a la memoria para combatir el spam , avances en criptología .
  • Hellman, ME (1980). Un intercambio criptoanalítico de tiempo-memoria , transacciones IEEE en la teoría de la información .

Enlaces externos

  • Implementación de una función limitada a la memoria
  • Arquitectura de Computadores
  • Cómo funciona la memoria de la computadora
  • Programación dinámica
  • CPU enlazado frente a E / S enlazado
  • Spam: información para el consumidor de la FTC