Computación estocástica - Stochastic computing

La computación estocástica es una colección de técnicas que representan valores continuos mediante flujos de bits aleatorios. A continuación, se pueden calcular cálculos complejos mediante operaciones simples de bits en los flujos. La computación estocástica es distinta del estudio de algoritmos aleatorios .

Motivación y un ejemplo sencillo

Supongamos que está dado y deseamos calcular . La computación estocástica realiza esta operación usando probabilidad en lugar de aritmética. ${\ Displaystyle p, q \ in [0,1]}$${\ Displaystyle p \ times q}$

Específicamente, suponga que hay dos flujos de bits independientes aleatorios llamados números estocásticos s (es decir, procesos de Bernoulli ), donde la probabilidad de uno en el primer flujo es y la probabilidad en el segundo flujo es . Podemos tomar el AND lógico de las dos corrientes. ${\ 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	...

La probabilidad de que aparezca uno en el flujo de salida es . Observando suficientes bits de salida y midiendo la frecuencia de unos, es posible estimar con precisión arbitraria. ${\ displaystyle pq}$${\ displaystyle pq}$

La operación anterior convierte un cálculo bastante complicado (multiplicación de y ) en una serie de operaciones muy simples (evaluación de ) en bits aleatorios. ${\ Displaystyle p}$${\ Displaystyle q}$${\ Displaystyle a_ {i} \ land b_ {i}}$

Hablando en términos más generales, la computación estocástica representa los números como flujos de bits aleatorios y reconstruye los números calculando frecuencias. Los cálculos se realizan en los flujos y traducen operaciones complicadas en y en operaciones simples en sus representaciones de flujo. (Debido al método de reconstrucción, los dispositivos que realizan estas operaciones a veces se denominan procesadores de promedios estocásticos). En términos modernos, la computación estocástica puede verse como una interpretación de cálculos en términos probabilísticos, que luego se evalúan con un muestreador de Gibbs . También se puede interpretar como una computadora híbrida analógica / digital . ${\ Displaystyle p}$${\ Displaystyle q}$

Historia

La computadora estocástica RASCEL, alrededor de 1969

La computación estocástica fue introducida por primera vez en un artículo pionero por John von Neumann en 1953. Sin embargo, la teoría no pudo desarrollarse completamente hasta los avances en computación de la década de 1960, principalmente a través de una serie de esfuerzos simultáneos y paralelos en los EE. UU. Y el Reino Unido. A finales de la década de 1960, la atención se centró en el diseño de hardware de propósito especial para realizar cálculos estocásticos. Varias de estas máquinas se construyeron entre 1969 y 1974; RASCEL se muestra en este artículo.

A pesar del intenso interés en las décadas de 1960 y 1970, la computación estocástica finalmente no pudo competir con la lógica digital más tradicional, por las razones que se describen a continuación. El primer (y último) Simposio Internacional sobre Computación Estocástica tuvo lugar en 1978; la investigación activa en el área disminuyó en los próximos años.

Aunque la computación estocástica declinó como método general de computación, se ha mostrado prometedora en varias aplicaciones. La investigación se ha centrado tradicionalmente en determinadas tareas de control y aprendizaje automático. Recientemente, el interés se ha vuelto hacia la decodificación estocástica, que aplica la computación estocástica a la decodificación de códigos de corrección de errores. Más recientemente, los circuitos estocásticos se han utilizado con éxito en tareas de procesamiento de imágenes como la detección de bordes y el umbral de imagen .

Fortalezas y debilidades

Aunque la computación estocástica fue un fracaso histórico, aún puede seguir siendo relevante para resolver ciertos problemas. Para comprender cuándo sigue siendo relevante, es útil comparar la computación estocástica con métodos más tradicionales de computación digital.

Fortalezas

Suponga que deseamos multiplicar dos números cada uno con bits de precisión. Usando el método típico de multiplicación larga , necesitamos realizar operaciones. Con la computación estocástica, podemos Y juntos cualquier número de bits y el valor esperado siempre será correcto. (Sin embargo, con una pequeña cantidad de muestras, la variación hará que el resultado real sea muy inexacto). ${\ Displaystyle n}$${\ Displaystyle n ^ {2}}$

Además, las operaciones subyacentes en un multiplicador digital son sumadores completos , mientras que una computadora estocástica solo requiere una puerta AND . Además, un multiplicador digital requeriría ingenuamente cables de entrada, mientras que un multiplicador estocástico solo requeriría 2 cables de entrada. (Sin embargo, si el multiplicador digital serializara su salida, también requeriría solo 2 cables de entrada). ${\ Displaystyle 2n}$

Además, la computación estocástica es robusta contra el ruido; si se invierten algunos bits en una secuencia, esos errores no tendrán un impacto significativo en la solución.

Además, los elementos informáticos estocásticos pueden tolerar un sesgo en el tiempo de llegada de las entradas. Los circuitos funcionan correctamente incluso cuando las entradas están desalineadas temporalmente. Como resultado, los sistemas estocásticos pueden diseñarse para trabajar con relojes económicos generados localmente en lugar de utilizar un reloj global y una red de distribución de reloj cara.

Finalmente, la computación estocástica proporciona una estimación de la solución que se vuelve más precisa a medida que ampliamos el flujo de bits. En particular, proporciona una estimación aproximada muy rápidamente. Esta propiedad generalmente se conoce como precisión progresiva , lo que sugiere que la precisión de los números estocásticos (flujos de bits) aumenta a medida que avanza el cálculo. Es como si los bits más significativos del número llegaran antes que los bits menos significativos ; a diferencia de los circuitos aritméticos convencionales donde los bits más significativos suelen llegar en último lugar. En algunos sistemas iterativos, las soluciones parciales obtenidas mediante la precisión progresiva pueden proporcionar una retroalimentación más rápida que a través de los métodos informáticos tradicionales, lo que conduce a una convergencia más rápida.

Debilidades

La computación estocástica es, por su propia naturaleza, aleatoria. Cuando examinamos un flujo de bits aleatorio e intentamos reconstruir el valor subyacente, la precisión efectiva se puede medir por la varianza de nuestra muestra. En el ejemplo anterior, el multiplicador digital calcula un número en bits de precisión, por lo que la precisión es . Si usamos un flujo de bits aleatorio para estimar un número y queremos que la desviación estándar de nuestra estimación de la solución sea al menos , necesitaríamos muestras. Esto representa un aumento exponencial de trabajo. En ciertas aplicaciones, sin embargo, la propiedad de precisión progresiva de la computación estocástica se puede aprovechar para compensar esta pérdida exponencial. ${\ Displaystyle 2n}$${\ Displaystyle 2 ^ {- 2n}}$${\ Displaystyle 2 ^ {- 2n}}$${\ Displaystyle O (2 ^ {4n})}$

En segundo lugar, la computación estocástica requiere un método para generar flujos de bits con polarización aleatoria. En la práctica, estos flujos se generan con generadores de números pseudoaleatorios . Desafortunadamente, generar bits (pseudo) aleatorios es bastante costoso (en comparación con el costo de, por ejemplo, un sumador completo). Por lo tanto, la ventaja a nivel de puerta de la computación estocástica generalmente se pierde.

En tercer lugar, el análisis de la computación estocástica asume que los flujos de bits son independientes (no correlacionados). Si esta suposición no se cumple, la computación estocástica puede fallar dramáticamente. Por ejemplo, si intentamos calcular multiplicando un flujo de bits por sí mismo, el proceso falla: dado que el cálculo estocástico daría como resultado , lo que generalmente no es cierto (a menos que sea 0 o 1). En los sistemas con retroalimentación, el problema de la descorrelación puede manifestarse de formas más complicadas. Los sistemas de procesadores estocásticos son propensos a enclavarse , donde la retroalimentación entre diferentes componentes puede alcanzar un estado de interbloqueo. Debe dedicarse una gran cantidad de esfuerzo a descorrelacionar el sistema para intentar remediar el enganche. ${\ Displaystyle p ^ {2}}$${\ Displaystyle p}$${\ Displaystyle a_ {i} \ land a_ {i} = a_ {i}}$${\ Displaystyle p \ times p = p}$${\ Displaystyle p =}$

Cuarto, aunque algunas funciones digitales tienen contrapartes estocásticas muy simples (como la traducción entre la multiplicación y la puerta AND), muchas no las tienen. Intentar expresar estas funciones de forma estocástica puede provocar diversas patologías. Por ejemplo, la decodificación estocástica requiere el cálculo de la función . No existe una operación de un solo bit que pueda calcular esta función; la solución habitual implica producir bits de salida correlacionados que, como hemos visto anteriormente, pueden causar una serie de problemas. ${\ Displaystyle f (p, q) \ rightarrow pq / (pq + (1-p) (1-q))}$

Otras funciones (como el operador de promediado requieren el diezmado del flujo o el inflado. Las compensaciones entre la precisión y la memoria pueden ser un desafío. ${\ Displaystyle f (p, q) \ rightarrow (p + q) / 2}$

Decodificación estocástica

Aunque la computación estocástica tiene una serie de defectos cuando se considera un método de computación general, existen ciertas aplicaciones que destacan sus fortalezas. Un caso notable ocurre en la decodificación de ciertos códigos de corrección de errores.

En desarrollos no relacionados con la computación estocástica, se desarrollaron métodos altamente efectivos para decodificar códigos LDPC utilizando el algoritmo de propagación de creencias . La propagación de creencias en este contexto implica la reestimación iterativa de ciertos parámetros utilizando dos operaciones básicas (esencialmente, una operación XOR probabilística y una operación de promediado).

En 2003, los investigadores se dieron cuenta de que estas dos operaciones podían modelarse de forma muy sencilla con la computación estocástica. Además, dado que el algoritmo de propagación de creencias es iterativo, la computación estocástica proporciona soluciones parciales que pueden conducir a una convergencia más rápida. Las implementaciones de hardware de decodificadores estocásticos se han construido sobre FPGA . Los defensores de estos métodos argumentan que el rendimiento de la decodificación estocástica es competitivo con las alternativas digitales.

Métodos deterministas para la computación estocástica

Se han desarrollado métodos deterministas de SC para realizar cálculos completamente precisos con circuitos SC. El principio esencial de estos métodos es que cada bit de uno de los flujos de bits interactúa con cada bit de los otros flujos de bits exactamente una vez. Para producir un resultado completamente exacto con estos métodos, la operación debe ejecutarse para el producto de la longitud de los flujos de bits de entrada. Los métodos deterministas se desarrollan basados ​​en flujos de bits unarios, flujos de bits pseudoaleatorios y flujos de bits de discrepancia baja.

Variantes de la computación estocástica

Hay una serie de variantes del paradigma básico de la computación estocástica. Se puede encontrar más información en el libro de referencia de Mars y Poppelbaum.

El procesamiento de paquetes implica enviar un número fijo de bits en lugar de un flujo. Una de las ventajas de este enfoque es que se mejora la precisión. Para ver por qué, supongamos que transmitimos bits. En la computación estocástica regular, podemos representar una precisión de valores aproximadamente diferentes, debido a la varianza de la estimación. En el procesamiento de paquetes, podemos representar una precisión de . Sin embargo, el procesamiento de paquetes conserva la misma solidez al error del procesamiento estocástico regular. ${\ Displaystyle s}$${\ Displaystyle O (1 / {\ sqrt {s}})}$${\ Displaystyle 1 / s}$

El procesamiento ergódico implica el envío de un flujo de paquetes, que captura los beneficios del procesamiento estocástico y de paquetes regular.

El procesamiento de ráfagas codifica un número mediante un flujo de aumento de base más alto. Por ejemplo, codificaríamos 4.3 con diez dígitos decimales como

4444444555

ya que el valor medio de la secuencia anterior es 4,3. Esta representación ofrece varias ventajas: no hay aleatorización ya que los números aparecen en orden creciente, por lo que se evitan los problemas del PRNG, pero se conservan muchas de las ventajas de la computación estocástica (como las estimaciones parciales de la solución). Además, conserva la precisión lineal del procesamiento de paquetes y ergódico.

Referencias

Otras lecturas

• Gaines, Brian R. (1967). "Técnicas de identificación con la computadora estocástica" (PDF) . Actas Simposio de la IFAC sobre "Los problemas de identificación en sistemas de control automático", Sección 6 Instrumentos especiales de identificación, Praga 12-19 de junio de 1967 . Consultado el 11 de noviembre de 2013 .
• Alaghi, Armin; Hayes, John P. (2013). "Encuesta de Computación Estocástica" (PDF) . Transacciones ACM en sistemas informáticos integrados . 12 (2s): 1–19. CiteSeerX   10.1.1.296.4448 . doi : 10.1145 / 2465787.2465794 . S2CID   4689958 . Consultado el 11 de noviembre de 2013 .