Computação estocástica - Stochastic computing

A computação estocástica é uma coleção de técnicas que representam valores contínuos por fluxos de bits aleatórios. Cálculos complexos podem ser calculados por operações simples sobre bits nos fluxos. A computação estocástica é diferente do estudo de algoritmos aleatórios .

Motivação e um exemplo simples

Suponha que seja dado e desejamos calcular . A computação estocástica realiza esta operação usando probabilidade em vez de aritmética. ${\ displaystyle p, q \ in [0,1]}$${\ displaystyle p \ times q}$

Especificamente, suponha que existam dois fluxos de bits independentes e aleatórios chamados de número estocástico s (isto é, processos de Bernoulli ), onde a probabilidade de um no primeiro fluxo é , e a probabilidade no segundo fluxo é . Podemos pegar o AND lógico dos dois fluxos. ${\ displaystyle p}$${\ displaystyle q}$

${\ displaystyle a_ {i}}$	1	0	1	1	0	1	...
${\ displaystyle b_ {i}}$	1	1	0	1	1	0	...
${\ displaystyle a_ {i} \ land b_ {i}}$	1	0	0	1	0	0	...

A probabilidade de um no fluxo de saída é . Observando bits de saída suficientes e medindo a frequência de uns, é possível estimar com precisão arbitrária. ${\ displaystyle pq}$${\ displaystyle pq}$

A operação acima converte uma computação bastante complicada (multiplicação de e ) em uma série de operações muito simples (avaliação de ) em bits aleatórios. ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle a_ {i} \ land b_ {i}}$

De um modo mais geral, a computação estocástica representa os números como fluxos de bits aleatórios e reconstrói os números calculando as frequências. Os cálculos são realizados nos fluxos e traduzem operações complicadas em e em operações simples em suas representações de fluxo. (Por causa do método de reconstrução, os dispositivos que realizam essas operações às vezes são chamados de processadores de média estocástica.) Em termos modernos, a computação estocástica pode ser vista como uma interpretação de cálculos em termos probabilísticos, que são avaliados com um amostrador de Gibbs . Ele também pode ser interpretado como um computador híbrido analógico / digital . ${\ displaystyle p}$${\ displaystyle q}$

História

A computação estocástica foi introduzida pela primeira vez em um artigo pioneiro de John von Neumann em 1953. No entanto, a teoria não pôde ser totalmente desenvolvida até os avanços da computação na década de 1960, principalmente por meio de uma série de esforços simultâneos e paralelos nos Estados Unidos e no Reino Unido. No final da década de 1960, a atenção se voltou para o projeto de hardware de uso especial para realizar cálculos estocásticos. Muitas dessas máquinas foram construídas entre 1969 e 1974; RASCEL é retratado neste artigo.

Apesar do intenso interesse nas décadas de 1960 e 1970, a computação estocástica acabou falhando em competir com a lógica digital mais tradicional, pelos motivos descritos abaixo. O primeiro (e último) Simpósio Internacional de Computação Estocástica ocorreu em 1978; as pesquisas ativas na área diminuíram nos anos seguintes.

Embora a computação estocástica tenha declinado como método geral de computação, ela se mostrou promissora em várias aplicações. Tradicionalmente, a pesquisa tem se concentrado em certas tarefas de aprendizado e controle de máquina. Recentemente, o interesse se voltou para a decodificação estocástica, que aplica a computação estocástica à decodificação de códigos de correção de erros. Mais recentemente, os circuitos estocásticos têm sido usados ​​com sucesso em tarefas de processamento de imagem , como detecção de bordas e limiar de imagem .

Forças e fraquezas

Embora a computação estocástica tenha sido uma falha histórica, ela ainda pode permanecer relevante para resolver certos problemas. Para entender quando ele permanece relevante, é útil comparar a computação estocástica com métodos mais tradicionais de computação digital.

Forças

Suponha que desejamos multiplicar dois números cada um com bits de precisão. Usando o método típico de multiplicação longa , precisamos realizar operações. Com a computação estocástica, podemos usar o AND em qualquer número de bits e o valor esperado sempre estará correto. (No entanto, com um pequeno número de amostras, a variação tornará o resultado real altamente impreciso). ${\ displaystyle n}$${\ displaystyle n ^ {2}}$

Além disso, as operações subjacentes em um multiplicador digital são somadores completos , enquanto um computador estocástico requer apenas uma porta AND . Além disso, um multiplicador digital exigiria ingenuamente fios de entrada, enquanto um multiplicador estocástico exigiria apenas 2 fios de entrada. (Se o multiplicador digital serializou sua saída, no entanto, ele também exigiria apenas 2 fios de entrada.) ${\ displaystyle 2n}$

Além disso, a computação estocástica é robusta contra ruído; se alguns bits em um fluxo forem invertidos, esses erros não terão impacto significativo na solução.

Além disso, os elementos de computação estocástica podem tolerar distorção no tempo de chegada das entradas. Os circuitos funcionam corretamente mesmo quando as entradas estão desalinhadas temporariamente. Como resultado, os sistemas estocásticos podem ser projetados para funcionar com relógios baratos gerados localmente, em vez de usar um relógio global e uma rede de distribuição de relógios cara.

Finalmente, a computação estocástica fornece uma estimativa da solução que se torna mais precisa à medida que estendemos o fluxo de bits. Em particular, ele fornece uma estimativa aproximada muito rapidamente. Essa propriedade é geralmente conhecida como precisão progressiva , o que sugere que a precisão dos números estocásticos (fluxos de bits) aumenta à medida que o cálculo prossegue. É como se os bits mais significativos do número chegassem antes dos bits menos significativos ; ao contrário dos circuitos aritméticos convencionais , onde os bits mais significativos geralmente chegam por último. Em alguns sistemas iterativos, as soluções parciais obtidas por meio de precisão progressiva podem fornecer feedback mais rápido do que por meio de métodos de computação tradicionais, levando a uma convergência mais rápida.

Fraquezas

A computação estocástica é, por sua própria natureza, aleatória. Quando examinamos um fluxo de bits aleatório e tentamos reconstruir o valor subjacente, a precisão efetiva pode ser medida pela variação de nossa amostra. No exemplo acima, o multiplicador digital calcula um número em bits de precisão, portanto, a precisão é . Se estivermos usando um fluxo de bits aleatório para estimar um número e quisermos que o desvio padrão de nossa estimativa da solução seja pelo menos , precisaremos de amostras. Isso representa um aumento exponencial no trabalho. Em certas aplicações, no entanto, a propriedade de precisão progressiva da computação estocástica pode ser explorada para compensar essa perda exponencial. ${\ displaystyle 2n}$${\ displaystyle 2 ^ {- 2n}}$${\ displaystyle 2 ^ {- 2n}}$${\ displaystyle O (2 ^ {4n})}$

Em segundo lugar, a computação estocástica requer um método de geração de fluxos de bits enviesados ​​aleatoriamente. Na prática, esses fluxos são gerados com geradores de números pseudo-aleatórios . Infelizmente, gerar bits (pseudo-) aleatórios é bastante caro (em comparação com o custo de, por exemplo, um somador completo). Portanto, a vantagem de nível de porta da computação estocástica é normalmente perdida.

Terceiro, a análise da computação estocástica assume que os fluxos de bits são independentes (não correlacionados). Se essa suposição não for válida, a computação estocástica pode falhar drasticamente. Por exemplo, se tentarmos calcular multiplicando um fluxo de bits por si mesmo, o processo falha: uma vez que , o cálculo estocástico produziria , o que geralmente não é verdadeiro (a menos que 0 ou 1). Em sistemas com feedback, o problema de decorrelação pode se manifestar de maneiras mais complicadas. Os sistemas de processadores estocásticos são propensos a travar , onde o feedback entre diferentes componentes pode atingir um estado de deadlock. Um grande esforço deve ser despendido na descorrelação do sistema para tentar remediar o travamento. ${\ displaystyle p ^ {2}}$${\ displaystyle p}$${\ displaystyle a_ {i} \ land a_ {i} = a_ {i}}$${\ displaystyle p \ times p = p}$${\ displaystyle p =}$

Quarto, embora algumas funções digitais tenham contrapartes estocásticas muito simples (como a tradução entre a multiplicação e a porta AND), muitas não têm. Tentar expressar essas funções estocasticamente pode causar várias patologias. Por exemplo, a decodificação estocástica requer o cálculo da função . Não existe uma operação de bit único que possa calcular esta função; a solução usual envolve a produção de bits de saída correlacionados, que, como vimos acima, podem causar uma série de problemas. ${\ displaystyle f (p, q) \ rightarrow pq / (pq + (1-p) (1-q))}$

Outras funções (como o operador de média exigem a dizimação do fluxo ou a inflação. As compensações entre precisão e memória podem ser desafiadoras. ${\ displaystyle f (p, q) \ rightarrow (p + q) / 2}$

Decodificação estocástica

Embora a computação estocástica tenha vários defeitos quando considerada um método de computação geral, existem certas aplicações que destacam seus pontos fortes. Um caso notável ocorre na decodificação de certos códigos de correção de erros.

Em desenvolvimentos não relacionados à computação estocástica, foram desenvolvidos métodos altamente eficazes de decodificação de códigos LDPC usando o algoritmo de propagação de crenças . A propagação de crenças neste contexto envolve a reestimativa iterativa de certos parâmetros usando duas operações básicas (essencialmente, uma operação XOR probabilística e uma operação de média).

Em 2003, os pesquisadores perceberam que essas duas operações poderiam ser modeladas de forma muito simples com a computação estocástica. Além disso, como o algoritmo de propagação de crenças é iterativo, a computação estocástica fornece soluções parciais que podem levar a uma convergência mais rápida. Implementações de hardware de decodificadores estocásticos foram construídas em FPGAs . Os proponentes desses métodos argumentam que o desempenho da decodificação estocástica é competitivo com as alternativas digitais.

Métodos Determinísticos para Computação Estocástica

Métodos determinísticos de SC foram desenvolvidos para realizar cálculos totalmente precisos com circuitos SC. O princípio essencial desses métodos é que cada bit de um fluxo de bits interage com cada bit dos outros fluxos de bits exatamente uma vez. Para produzir resultados totalmente precisos com esses métodos, a operação deve ser executada para o produto do comprimento dos fluxos de bits de entrada. Métodos determinísticos são desenvolvidos com base em fluxos de bits unários, fluxos de bits pseudoaleatórios e fluxos de bits de baixa discrepância.

Variantes de computação estocástica

Existem várias variantes do paradigma da computação estocástica básica. Mais informações podem ser encontradas no livro referenciado de Mars e Poppelbaum.

O processamento de pacote envolve o envio de um número fixo de bits em vez de um fluxo. Uma das vantagens dessa abordagem é que a precisão é aprimorada. Para ver por quê, suponha que transmitamos bits. Na computação estocástica regular, podemos representar uma precisão de valores aproximadamente diferentes, por causa da variância da estimativa. No processamento de pacotes, podemos representar uma precisão de . No entanto, o processamento do pacote retém a mesma robustez ao erro do processamento estocástico regular. ${\ displaystyle s}$${\ displaystyle O (1 / {\ sqrt {s}})}$${\ displaystyle 1 / s}$

O processamento ergódico envolve o envio de um fluxo de pacotes, que captura os benefícios do processamento estocástico e de pacotes regulares.

O processamento de rajadas codifica um número por um fluxo crescente de base mais alta. Por exemplo, codificaríamos 4.3 com dez dígitos decimais como

4444444555

já que o valor médio do fluxo anterior é de 4,3. Essa representação oferece várias vantagens: não há randomização, pois os números aparecem em ordem crescente, portanto, os problemas de PRNG são evitados, mas muitas das vantagens da computação estocástica são mantidas (como estimativas parciais da solução). Além disso, ele retém a precisão linear do processamento de feixe e ergódico.

Referências

Leitura adicional

• Gaines, Brian R. (1967). "Técnicas de identificação com o computador estocástico" (PDF) . Proceedings IFAC Symposium on "The Problems of Identification in Automatic Control Systems", Section 6 Special Identification Instruments, Praga 12–19 de junho de 1967 . Página visitada em 2013-11-11 .
• Alaghi, Armin; Hayes, John P. (2013). "Pesquisa de Computação Estocástica" (PDF) . Transações ACM em sistemas de computação incorporados . 12 (2s): 1–19. CiteSeerX   10.1.1.296.4448 . doi : 10.1145 / 2465787.2465794 . S2CID   4689958 . Página visitada em 2013-11-11 .