Computación estocástica

Computación utilizando flujos de bits aleatorios

La computación estocástica es un conjunto de técnicas que representan valores continuos mediante secuencias de bits aleatorios. A continuación, se pueden realizar cálculos complejos mediante operaciones simples bit a bit sobre las secuencias. La computación estocástica se diferencia del estudio de algoritmos aleatorios .

Motivación y un ejemplo sencillo

Supongamos que se da y queremos calcular . El cálculo estocástico realiza esta operación utilizando probabilidad en lugar de aritmética. ${\displaystyle p,q\in [0,1]}$ ${\displaystyle p\times q}$

En concreto, supongamos que hay dos flujos de bits aleatorios e independientes llamados números estocásticos (es decir, procesos de Bernoulli ), donde la probabilidad de un 1 en el primer flujo es , y la probabilidad en el segundo flujo es . Podemos tomar el AND lógico de los dos flujos. ${\displaystyle p}$ ${\displaystyle q}$

La probabilidad de que aparezca un 1 en el flujo de salida es . Al observar suficientes bits de salida y medir la frecuencia de los 1, es posible realizar una estimación con una 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. Para ponerlo en otra perspectiva, suponiendo la tabla de verdad de una compuerta AND. La interpretación convencional es que la salida es verdadera si y solo si las entradas A y B son verdaderas. Sin embargo, si la tabla se interpreta verticalmente, (0011) AND (0101) es (0001), es decir, 1/2 x 1/2 = 1/4, que es exactamente una multiplicación aritmética. Como la información se presenta en una distribución de probabilidad, la multiplicación de probabilidad es literalmente una operación AND. ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle a_{i}\land b_{i}}$

En términos más generales, la computación estocástica representa números como flujos de bits aleatorios y reconstruye números calculando frecuencias. Los cálculos se realizan en los flujos y traducen operaciones complicadas 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 promedio estocástico). 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 puede interpretarse como una computadora híbrida analógica / digital . ${\displaystyle p}$ ${\displaystyle q}$

Historia

El ordenador estocástico RASCEL, alrededor de 1969

La computación estocástica fue introducida por primera vez en un artículo pionero de John von Neumann en 1953. ^[1] Sin embargo, la teoría no pudo desarrollarse completamente hasta los avances en computación de la década de 1960, ^{[2] [3]} principalmente a través de una serie de esfuerzos simultáneos y paralelos en los EE. UU. ^[4] y el Reino Unido. ^[5] A fines de la década de 1960, la atención se centró en el diseño de hardware de propósito especial para realizar computación estocástica. Una gran cantidad ^[6] de estas máquinas se construyeron entre 1969 y 1974; RASCEL ^[7] se muestra en este artículo.

A pesar del intenso interés suscitado en los años 1960 y 1970, la computación estocástica no logró 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 ^[8] tuvo lugar en 1978; la investigación activa en el área disminuyó en los años siguientes.

Aunque la computación estocástica declinó como un método general de computación, ha demostrado ser prometedora en varias aplicaciones. La investigación se ha centrado tradicionalmente en ciertas tareas en el aprendizaje automático y el control. ^{[9] [10]} Recientemente, el interés se ha volcado 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. ^[11] 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 ^[12] y el umbral de imágenes . ^[13] El avance reciente en circuitos estocásticos también muestra ventajas prometedoras de velocidad y eficiencia energética en la aceleración de hardware de inteligencia artificial (IA) en la computación de borde.

Fortalezas y debilidades

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

Fortalezas

Supongamos que queremos multiplicar dos números, cada uno con bits de precisión. Si utilizamos el típico método de multiplicación larga , debemos realizar operaciones. Con la computación estocástica, podemos combinar cualquier cantidad de bits y el valor esperado siempre será correcto. (Sin embargo, con una pequeña cantidad de muestras, la varianza 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 compuerta AND . Además, un multiplicador digital requeriría ingenuamente cables de entrada, mientras que un multiplicador estocástico solo requeriría dos cables de entrada ^{[ cita requerida ]} . (Sin embargo, si el multiplicador digital serializara su salida, también requeriría solo dos cables de entrada). ${\displaystyle 2n}$

Además, la computación estocástica es robusta al ruido: si se invierten algunos bits en un flujo, esos errores no tendrán un impacto significativo en la solución.

Además, los elementos de computación estocástica pueden tolerar desviaciones 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 que funcionen con relojes económicos generados localmente en lugar de utilizar un reloj global y una red de distribución de relojes costosa. ^[14]

Por último, 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 suele denominarse 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. ^[15] Es como si los bits más significativos del número llegaran antes que sus bits menos significativos ; a diferencia de los circuitos aritméticos convencionales donde los bits más significativos suelen llegar al final. En algunos sistemas iterativos, las soluciones parciales obtenidas mediante precisión progresiva pueden proporcionar una retroalimentación más rápida que mediante los métodos de computación 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 con una precisión de bits, por lo que la precisión es . Si estamos utilizando 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 del trabajo. Sin embargo, en ciertas aplicaciones, 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 secuencias de bits aleatorias y sesgadas. En la práctica, estas secuencias 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 compuerta de la computación estocástica generalmente se pierde.

En tercer lugar, el análisis de la computación estocástica supone que los flujos de bits son independientes (no están correlacionados). Si esta suposición no se cumple, la computación estocástica puede fallar drásticamente. Por ejemplo, si tratamos de calcular multiplicando un flujo de bits por sí mismo, el proceso falla: dado que , el cálculo estocástico produciría , lo que generalmente no es cierto (a menos que sea 0 o 1). En sistemas con retroalimentación, el problema de la decorrelación puede manifestarse de formas más complicadas. Los sistemas de procesadores estocásticos son propensos al enclavamiento , donde la retroalimentación entre diferentes componentes puede lograr un estado de bloqueo. ^[16] Se debe dedicar una gran cantidad de esfuerzo a decorrelacionar el sistema para intentar remediar el enclavamiento. ${\displaystyle p^{2}}$ ${\displaystyle p}$ ${\displaystyle a_{i}\land a_{i}=a_{i}}$ ${\displaystyle p\times p=p}$ ${\displaystyle p=}$

En cuarto lugar, aunque algunas funciones digitales tienen contrapartes estocásticas muy simples (como la traducción entre la multiplicación y la compuerta AND), muchas no las tienen. Intentar expresar estas funciones de forma estocástica puede causar 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, lo que, como hemos visto anteriormente, puede causar una serie de problemas. ${\displaystyle f(p,q)\rightarrow pq/(pq+(1-p)(1-q))}$

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

Descodificación estocástica

Aunque el cálculo estocástico presenta una serie de defectos cuando se lo considera como método de cálculo general, existen ciertas aplicaciones que resaltan sus puntos fuertes. 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 reestimar iterativamente 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 se podían modelar de manera muy sencilla con computación estocástica. ^[17] 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. Se han construido implementaciones de hardware de decodificadores estocásticos en FPGAs . ^[18] 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 el cálculo estocástico

Se han desarrollado métodos deterministas de SC para realizar cálculos completamente precisos con circuitos SC. ^[19] El principio esencial de estos métodos es que cada bit de un flujo de bits interactúa con cada bit de los otros flujos de bits exactamente una vez. Para producir un resultado completamente preciso 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 en base a flujos de bits unarios, ^{[20] [21]} flujos de bits pseudoaleatorios, ^[22] y flujos de bits de baja discrepancia. ^[23]

Variantes de la computación estocástica

Existen diversas variantes del paradigma básico de 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 una cantidad fija 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 robustez 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 en ráfagas codifica un número mediante un flujo de incremento de base superior. Por ejemplo, codificaríamos 4,3 con diez dígitos decimales como

4444444555

ya que el valor medio del flujo 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 de PRNG, pero se conservan muchas de las ventajas del cálculo estocástico (como las estimaciones parciales de la solución). Además, conserva la precisión lineal del procesamiento ergódico y de los paquetes.

Véase también

• Computación no convencional

Referencias

1. von Neumann, J. (1963). "Lógica probabilística y síntesis de organismos fiables a partir de componentes no fiables". The Collected Works of John von Neumann . Macmillan. ISBN 978-0-393-05169-8.
2. Petrovic, R.; Siljak, D. (1962). "Multiplicación por medio de la coincidencia". Actas de la 3.ª reunión internacional de computación analógica de ACTES .
3. Afuso, C. (1964), Informe de programa de tecnología de Quart. , Departamento de Ciencias de la Computación, Universidad de Illinois, Urbana, Illinois{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
4. Poppelbaum, W.; Afuso, C.; Esch, J. (1967). "Elementos y sistemas de computación estocástica". Actas de la conferencia conjunta de computación de otoño del 14 al 16 de noviembre de 1967, AFIPS '67 (otoño) . Vol. 31. págs. 635–644. doi :10.1145/1465611.1465696. ISBN 9781450378963.S2CID8504153  .​
5. Gaines, B. (1967). "Computación estocástica". Actas de la conferencia conjunta de informática de primavera del 18 al 20 de abril de 1967, AFIPS '67 (primavera) . Vol. 30. págs. 149-156. doi :10.1145/1465482.1465505. ISBN 9781450378956.S2CID832296  .​
6. Mars, P.; Poppelbaum, W. (1981). Procesadores de promedios estocásticos y deterministas . P. Peregrinus. ISBN 978-0-906048-44-3.
7. Esch, John W. (1969). RASCEL, una computadora analógica programable basada en una matriz regular de lógica de elementos computacionales estocásticos (PhD). Universidad de Illinois, Urbana, Illinois. AAI700084.
8. Actas del primer Simposio Internacional sobre Computación Estocástica y sus Aplicaciones . Toulouse, Francia. 1978. OCLC  499229066.
9. Gaines, BR (2013) [1969]. "Sistemas de computación estocástica". En Tou, Julius (ed.). Avances en la ciencia de los sistemas de información . Vol. 2. Springer. ISBN 9781489958433.
10. van Daalen, M.; Jeavons, P.; Shawe-Taylor, J. (1993). "Una arquitectura neuronal estocástica que explota FPGAs dinámicamente reconfigurables". [1993] Actas del taller IEEE sobre FPGAs para máquinas de computación personalizadas . págs. 202–211. doi :10.1109/FPGA.1993.279462. ISBN . 0-8186-3890-7. Número de identificación del sujeto  14929278.
11. Gaudet, Vincent; Rapley, Anthony (febrero de 2003). "Decodificación iterativa mediante computación estocástica". Electronics Letters . 39 (3): 299–301. Bibcode :2003ElL....39..299G. doi :10.1049/el:20030217.
12. Alaghi, A.; Li, C.; Hayes, JP (2013). "Circuitos estocásticos para aplicaciones de procesamiento de imágenes en tiempo real". Actas de la 50.ª Conferencia Anual de Automatización del Diseño sobre DAC '13 . pág. 1. doi :10.1145/2463209.2488901. ISBN 9781450320719.S2CID 18174415  .
13. Najafi, MH; Salehi, ME (2016). "Una arquitectura rápida y tolerante a fallos para el algoritmo de umbralización de imágenes locales Sauvola mediante computación estocástica". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 24 (2): 808–812. doi :10.1109/TVLSI.2015.2415932. S2CID  6591306.
14. Najafi, MH; Lilja, DJ; Riedel, MD; Bazargan, K. (2016). "Circuitos estocásticos polisincrónicos". 2016 21.ª Conferencia de Automatización de Diseño de Asia y el Pacífico Sur (ASP-DAC) . pp. 492–498. doi :10.1109/ASPDAC.2016.7428060. ISBN 978-1-4673-9569-4.S2CID8973285  .​
15. Alaghi, A.; Hayes, JP (2013). "Estudio de computación estocástica". ACM Transactions on Embedded Computing Systems . 12 (2s): 1. CiteSeerX 10.1.1.296.4448 . doi :10.1145/2465787.2465794. S2CID  4689958. 
16. Winstead, C.; Rapley, A.; Gaudet, V.; Schlegel, C. (septiembre de 2005). "Decodificadores iterativos estocásticos". Actas. Simposio internacional sobre teoría de la información, 2005. ISIT 2005. Adelaida, Australia. págs. 1116–1120. arXiv : cs/0501090 . doi :10.1109/ISIT.2005.1523513. ISBN . 0-7803-9151-9. Número de identificación del sujeto  16390484.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
17. Gaudet, Vincent; Rapley, Anthony (febrero de 2003). "Decodificación iterativa mediante computación estocástica". Electronics Letters . 39 (3): 299–301. Bibcode :2003ElL....39..299G. doi :10.1049/el:20030217.
18. Gross, W.; Gaudet, V.; Milner, A. (2006). "Implementación estocástica de decodificadores LDPC". Acta de la 39.ª Conferencia de Asilomar sobre señales, sistemas y computadoras .
19. Najafi, M. Hassan; Jenson, Devon; Lilja, David J.; Riedel, Marc D. (diciembre de 2019). "Realización de cálculos estocásticos de forma determinista". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 27 (12): 2925–2938. doi : 10.1109/tvlsi.2019.2929354 . ISSN  1063-8210. S2CID  201888463.
20. Jenson, Devon; Riedel, Marc (7 de noviembre de 2016). "Un enfoque determinista para el cálculo estocástico". Actas de la 35.ª Conferencia internacional sobre diseño asistido por ordenador . Nueva York, NY, EE. UU.: ACM. págs. 1–8. doi :10.1145/2966986.2966988. ISBN 978-1-4503-4466-1.S2CID11281124  .​
21. Najafi, M. Hassan; Jamali-Zavareh, Shiva; Lilja, David J.; Riedel, Marc D.; Bazargan, Kia; Harjani, Ramesh (mayo de 2017). "Valores codificados en el tiempo para circuitos estocásticos de alta eficiencia". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 25 (5): 1644–1657. doi : 10.1109/tvlsi.2016.2645902 . ISSN  1063-8210. S2CID  5672761.
22. Najafi, M. Hassan; Lilja, David (2018). "Reducción de la calidad de la muestra para enfoques deterministas de la computación estocástica". IEEE Transactions on Emerging Topics in Computing . 9 : 7–14. doi : 10.1109/tetc.2017.2789243 . ISSN  2168-6750.
23. Najafi, M. Hassan; Lilja, David J.; Riedel, Marc (5 de noviembre de 2018). "Métodos deterministas para computación estocástica utilizando secuencias de baja discrepancia". Actas de la Conferencia Internacional sobre Diseño Asistido por Computadora . Nueva York, NY, EE. UU.: ACM. págs. 1–8. doi : 10.1145/3240765.3240797 . ISBN. 978-1-4503-5950-4.S2CID 53236540  .

Lectura adicional

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