Função ligada à memória - Memory-bound function

O limite de memória se refere a uma situação na qual o tempo para concluir um determinado problema computacional é decidido principalmente pela quantidade de memória necessária para manter os dados de trabalho . Isso está em contraste com algoritmos que são limitados por computação , onde o número de etapas de computação elementares é o fator decisivo.

Os limites de memória e computação às vezes podem ser negociados entre si, por exemplo, salvando e reutilizando resultados preliminares ou usando tabelas de pesquisa .

Funções ligadas à memória e funções de memória

As funções ligadas à memória e as funções de memória estão relacionadas, pois ambas envolvem amplo acesso à memória, mas existe uma distinção entre as duas.

As funções de memória usam uma técnica de programação dinâmica chamada memoização para aliviar a ineficiência de recursão que pode ocorrer. Baseia-se na ideia simples de calcular e armazenar soluções para subproblemas de forma que as soluções possam ser reutilizadas posteriormente sem recalcular os subproblemas novamente. O exemplo mais conhecido que tira vantagem da memoização é um algoritmo que calcula os números de Fibonacci . O pseudocódigo a seguir usa recursão e memoização e é executado em tempo de CPU linear : 

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {
     if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

Compare o acima com um algoritmo que usa apenas recursão e é executado em tempo 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)
 }

Embora o algoritmo somente recursivo seja mais simples e mais elegante do que o algoritmo que usa recursão e memoização, o último tem uma complexidade de tempo significativamente menor do que o primeiro.

O termo "função limitada pela memória" surgiu recentemente e é usado principalmente para descrever uma função que usa XOR e consiste em uma série de cálculos em que cada cálculo depende do cálculo anterior. Enquanto as funções de memória têm sido um ator importante no aprimoramento da complexidade do tempo, as funções associadas à memória viram muito menos aplicativos. Recentemente, no entanto, os cientistas propuseram um método que usa funções ligadas à memória como um meio de desencorajar os spammers de abusar de recursos, o que poderia ser um grande avanço nessa área.

Usando funções ligadas à memória para evitar spam

As funções ligadas à memória podem ser úteis em um sistema de prova de trabalho que pode impedir o spam , que se tornou um problema de proporções epidêmicas na Internet .

Em 1992, os cientistas pesquisadores da IBM Cynthia Dwork e Moni Naor publicaram um artigo no CRYPTO 1992 intitulado Pricing via Processing or Combatting Junk Mail , sugerindo a possibilidade de usar funções vinculadas à CPU para impedir que os abusadores enviem spam. O esquema foi baseado na ideia de que os usuários de computador são muito mais propensos a abusar de um recurso se o custo do abuso for insignificante: o motivo subjacente do spam ter se tornado tão galopante é que o envio de um e-mail tem um custo mínimo para os spammers.

Dwork e Naor propuseram que o spamming poderia ser reduzido injetando um custo adicional na forma de uma computação de CPU cara : funções vinculadas à CPU consumiriam recursos da CPU na máquina do remetente para cada mensagem, evitando assim que grandes quantidades de spam sejam enviadas em um período curto.

O esquema básico que protege contra abusos é o seguinte:
seja S o remetente, R o destinatário e M um e-mail. Se R concordou previamente em receber e-mail de S , então M é transmitido da maneira usual. Caso contrário, S calcula alguma função G (M) e envia (M, G (M)) para R . R verifica se o que recebe de S é da forma (M, G (M)) . Se sim, R aceita M . Caso contrário, R rejeita M . A figura à direita mostra casos em que não houve acordo prévio .

A função G () é selecionada de forma que a verificação por R seja relativamente rápida (levando um milissegundo) e de forma que o cálculo por S seja um tanto lento (envolvendo pelo menos vários segundos). Portanto, S será desencorajado a enviar M para vários destinatários sem acordo prévio: o custo em termos de tempo e recursos de computação de G () repetidamente se tornará muito proibitivo para um spammer que pretende enviar muitos milhões de e-mails .

O principal problema de usar o esquema acima é que CPUs rápidas computam muito mais rápido do que CPUs lentas. Além disso, os sistemas de computador de ponta também têm canais sofisticados e outros recursos vantajosos que facilitam os cálculos. Como resultado, um spammer com um sistema de última geração dificilmente será afetado por tal dissuasão, enquanto um usuário típico com um sistema medíocre será afetado adversamente. Se um cálculo demorar alguns segundos em um PC novo , pode demorar um minuto em um PC antigo e vários minutos em um PDA , o que pode ser um incômodo para usuários de PCs antigos, mas provavelmente inaceitável para usuários de PDAs. A disparidade na velocidade da CPU do cliente constitui um dos obstáculos importantes para a adoção generalizada de qualquer esquema baseado em uma função vinculada à CPU. Portanto, os pesquisadores estão preocupados em encontrar funções que a maioria dos sistemas de computador avaliará aproximadamente na mesma velocidade, de modo que os sistemas de ponta possam avaliar essas funções um pouco mais rápido do que os sistemas de baixa qualidade (2 a 10 vezes mais rápido, mas não 10 a 100 vezes mais rápido) como as disparidades de CPU podem implicar. Essas proporções são " igualitárias " o suficiente para as aplicações pretendidas: as funções são eficazes para desencorajar abusos e não adicionam um atraso proibitivo em interações legítimas, em uma ampla gama de sistemas.

A nova abordagem igualitária é contar com funções ligadas à memória. Como afirmado antes, uma função limitada à memória é uma função cujo tempo de computação é dominado pelo tempo gasto acessando a memória. Uma função vinculada à memória acessa locais em uma grande região da memória de uma maneira imprevisível, de forma que o uso de caches não seja eficaz. Nos últimos anos, a velocidade da CPU cresceu drasticamente, mas houve um progresso comparativamente pequeno no desenvolvimento de uma memória principal mais rápida. Como as taxas de latências de memória das máquinas construídas nos últimos cinco anos normalmente não são maiores que dois e quase sempre menores que quatro, a função limitada pela memória será igualitária para a maioria dos sistemas no futuro previsível.

Veja também

Referências

links externos