Стохастические вычисления

Вычисления с использованием случайных битовых потоков

Стохастические вычисления — это набор методов, которые представляют непрерывные значения потоками случайных битов. Затем сложные вычисления могут быть выполнены с помощью простых побитовых операций над потоками. Стохастические вычисления отличаются от изучения рандомизированных алгоритмов .

Мотивация и простой пример

Предположим, что дано, и мы хотим вычислить . Стохастические вычисления выполняют эту операцию, используя вероятность вместо арифметики. ${\displaystyle p,q\in [0,1]}$ ${\displaystyle p\times q}$

В частности, предположим, что существуют два случайных, независимых битовых потока, называемых стохастическим числом s (т.е. процессы Бернулли ), где вероятность единицы в первом потоке равна , а вероятность во втором потоке равна . Мы можем взять логическое И для двух потоков. ${\displaystyle p}$ ${\displaystyle q}$

Вероятность появления единицы в выходном потоке равна . Наблюдая за достаточным количеством выходных битов и измеряя частоту 1 с, можно произвести оценку с произвольной точностью. ${\displaystyle pq}$ ${\displaystyle pq}$

Приведенная выше операция преобразует довольно сложное вычисление (умножение и ) в серию очень простых операций (вычисление ) со случайными битами. Взглянем на другую точку зрения, предполагая таблицу истинности вентиля И. Традиционная интерпретация заключается в том, что выходные данные истинны тогда и только тогда, когда входные данные A и B истинны. Однако если таблица интерпретируется вертикально, (0011) И (0101) равно (0001), т. е. 1/2 x 1/2 = 1/4, что является в точности арифметическим умножением. Поскольку информация представлена ​​в виде распределения вероятностей, умножение вероятностей представляет собой буквально операцию «И». ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle a_{i}\land b_{i}}$

В более общем смысле, стохастические вычисления представляют числа как потоки случайных битов и восстанавливают числа путем вычисления частот. Вычисления выполняются над потоками и преобразуют сложные операции в простые операции над их потоковыми представлениями. (Из-за метода реконструкции устройства, выполняющие эти операции, иногда называют процессорами стохастического усреднения.) Говоря современным языком, стохастические вычисления можно рассматривать как интерпретацию вычислений в вероятностных терминах, которые затем оцениваются с помощью сэмплера Гиббса . Его также можно интерпретировать как гибридный аналого - цифровой компьютер. ${\displaystyle p}$ ${\displaystyle q}$

История

Стохастический компьютер RASCEL, около 1969 года.

Стохастические вычисления были впервые представлены в новаторской статье Джона фон Неймана в 1953 году. ^[1] Однако теория не могла быть полностью разработана до тех пор, пока не были достигнуты успехи в области вычислений в 1960-х годах, ^{[2] [3]} в основном посредством серии одновременных и параллельных вычислений. усилия в США ^[4] и Великобритании. ^[5] К концу 1960-х годов внимание переключилось на разработку специального оборудования для выполнения стохастических вычислений. Множество ^[6] этих машин было построено в период с 1969 по 1974 год; RASCEL ^[7] изображен в этой статье.

Несмотря на большой интерес в 1960-х и 1970-х годах, стохастические вычисления в конечном итоге не смогли конкурировать с более традиционной цифровой логикой по причинам, изложенным ниже. Первый (и последний) Международный симпозиум по стохастическим вычислениям ^[8] состоялся в 1978 году; В течение следующих нескольких лет активные исследования в этой области сократились.

Хотя стохастические вычисления как общий метод вычислений пришли в упадок, они показали себя многообещающими в нескольких приложениях. Исследования традиционно фокусируются на определенных задачах машинного обучения и управления. ^{[9] [10]} Сравнительно недавно интерес обратился к стохастическому декодированию, которое применяет стохастические вычисления к декодированию кодов с исправлением ошибок. ^[11] Совсем недавно стохастические схемы успешно использовались в задачах обработки изображений , таких как обнаружение краев ^[12] и определение порога изображения . ^[13] Недавние достижения в области стохастических схем также демонстрируют многообещающие преимущества в скорости и энергоэффективности при аппаратном ускорении искусственного интеллекта (ИИ) в периферийных вычислениях.

Сильные и слабые стороны

Хотя стохастические вычисления потерпели историческую неудачу, они все еще могут оставаться актуальными для решения определенных проблем. Чтобы понять, когда это остается актуальным, полезно сравнить стохастические вычисления с более традиционными методами цифровых вычислений.

Сильные стороны

Предположим, мы хотим умножить два числа, каждое с точностью до бита. Используя типичный метод длинного умножения , нам нужно выполнить операции. С помощью стохастических вычислений мы можем И объединить любое количество битов, и ожидаемое значение всегда будет правильным. (Однако при небольшом количестве выборок дисперсия сделает фактический результат весьма неточным). ${\displaystyle n}$ ${\displaystyle n^{2}}$

Более того, базовыми операциями цифрового умножителя являются полные сумматоры , тогда как для стохастического компьютера требуется только логический элемент И. Кроме того, цифровой умножитель ^по наивности потребует входных проводов, тогда как стохастический умножитель потребует только два ^{входных провода} . (Однако если бы цифровой умножитель сериализовал свой выходной сигнал, ему также потребовалось бы только два входных провода.) ${\displaystyle 2n}$

Кроме того, стохастические вычисления устойчивы к шуму; если несколько битов в потоке перевернуты, эти ошибки не окажут существенного влияния на решение.

Более того, элементы стохастических вычислений могут допускать перекос во времени поступления входных данных. Схемы работают правильно, даже если входы временно не выровнены. В результате стохастические системы могут быть спроектированы для работы с недорогими локально генерируемыми часами вместо использования глобальных часов и дорогой сети распределения часов. ^[14]

Наконец, стохастические вычисления дают оценку решения, которая становится более точной по мере расширения потока битов. В частности, он очень быстро дает приблизительную оценку. Это свойство обычно называют прогрессивной точностью , что предполагает, что точность стохастических чисел (битовых потоков) увеличивается по мере выполнения вычислений. ^[15] Это похоже на то, как будто старшие биты числа появляются раньше младших ; в отличие от обычных арифметических схем , где наиболее значимые биты обычно поступают последними. В некоторых итерационных системах частичные решения, полученные за счет прогрессивной точности, могут обеспечить более быструю обратную связь, чем традиционные методы вычислений, что приводит к более быстрой сходимости.

Недостатки

Стохастические вычисления по своей природе случайны. Когда мы исследуем случайный поток битов и пытаемся восстановить лежащее в его основе значение, эффективная точность может быть измерена дисперсией нашей выборки. В приведенном выше примере цифровой умножитель вычисляет число с точностью до бита, поэтому точность равна . Если мы используем случайный поток битов для оценки числа и хотим, чтобы стандартное отклонение нашей оценки решения было не менее , нам потребуются выборки. Это означает экспоненциальное увеличение объема работы. Однако в некоторых приложениях свойство прогрессивной точности стохастических вычислений можно использовать для компенсации этих экспоненциальных потерь. ${\displaystyle 2n}$ ${\displaystyle 2^{-2n}}$ ${\displaystyle 2^{-2n}}$ ${\displaystyle O(2^{4n})}$

Во-вторых, стохастические вычисления требуют метода генерации случайных смещенных битовых потоков. На практике эти потоки генерируются с помощью генераторов псевдослучайных чисел . К сожалению, генерация (псевдо)случайных битов обходится довольно дорого (по сравнению, например, с затратами на полный сумматор). Таким образом, преимущество стохастических вычислений на уровне вентилей обычно теряется.

В-третьих, анализ стохастических вычислений предполагает, что потоки битов независимы (некоррелированы). Если это предположение не выполняется, стохастические вычисления могут потерпеть неудачу. Например, если мы попытаемся вычислить, умножив битовый поток на самого себя, процесс потерпит неудачу: поскольку стохастическое вычисление даст , что обычно неверно (кроме случаев 0 или 1). В системах с обратной связью проблема декорреляции может проявляться более сложным образом. Системы стохастических процессоров склонны к блокировке , когда обратная связь между различными компонентами может привести к тупиковому состоянию. ^[16] Чтобы попытаться исправить фиксацию, необходимо приложить немало усилий для корректировки связи системы. ${\displaystyle p^{2}}$ ${\displaystyle p}$ ${\displaystyle a_{i}\land a_{i}=a_{i}}$ ${\displaystyle p\times p=p}$ ${\displaystyle p=}$

В-четвертых, хотя некоторые цифровые функции имеют очень простые стохастические аналоги (например, перевод между умножением и логическим элементом И), у многих их нет. Попытка выразить эти функции стохастически может привести к различным патологиям. Например, стохастическое декодирование требует вычисления функции . Не существует однобитовой операции, которая могла бы вычислить эту функцию; обычное решение предполагает создание коррелированных выходных битов, что, как мы видели выше, может вызвать множество проблем. ${\displaystyle f(p,q)\rightarrow pq/(pq+(1-p)(1-q))}$

Другие функции (например, оператор усреднения) требуют либо прореживания потока, либо инфляции. Нахождение компромисса между точностью и памятью может оказаться сложной задачей. ${\displaystyle f(p,q)\rightarrow (p+q)/2}$

Стохастическое декодирование

Хотя стохастические вычисления имеют ряд недостатков, если рассматривать их как метод общих вычислений, существуют определенные приложения, которые подчеркивают их сильные стороны. Один примечательный случай имеет место при декодировании некоторых кодов исправления ошибок.

В разработках, не связанных со стохастическими вычислениями, были разработаны высокоэффективные методы декодирования LDPC-кодов с использованием алгоритма распространения доверия . Распространение убеждений в этом контексте включает итеративную переоценку определенных параметров с использованием двух основных операций (по сути, вероятностной операции XOR и операции усреднения).

В 2003 году исследователи поняли, что эти две операции можно очень просто смоделировать с помощью стохастических вычислений. ^[17] Более того, поскольку алгоритм распространения убеждений является итеративным, стохастические вычисления предоставляют частичные решения, которые могут привести к более быстрой сходимости. Аппаратные реализации стохастических декодеров построены на FPGA . ^[18] Сторонники этих методов утверждают, что производительность стохастического декодирования конкурентоспособна по сравнению с цифровыми альтернативами.

Детерминированные методы стохастических вычислений

Детерминированные методы SC были разработаны для выполнения абсолютно точных вычислений с использованием цепей SC. ^[19] Основной принцип этих методов заключается в том, что каждый бит одного битового потока взаимодействует с каждым битом другого битового потока ровно один раз. Чтобы получить полностью точный результат с помощью этих методов, операция должна выполняться для произведения длины входных битовых потоков. Детерминированные методы разрабатываются на основе унарных битовых потоков, ^{[20] [21]} псевдослучайных битовых потоков, ^[22] и битовых потоков с низким расхождением. ^[23]

Варианты стохастических вычислений

Существует несколько вариантов базовой парадигмы стохастических вычислений. Дополнительную информацию можно найти в справочной книге Марса и Поппельбаума.

Пакетная обработка предполагает отправку фиксированного количества битов вместо потока. Одним из преимуществ этого подхода является повышение точности. Чтобы понять почему, предположим, что мы передаем биты. В обычных стохастических вычислениях мы можем представлять точность примерно разных значений из-за дисперсии оценки. При пакетной обработке мы можем представить точность . Однако пакетная обработка сохраняет ту же устойчивость к ошибкам, что и обычная стохастическая обработка. ${\displaystyle s}$ ${\displaystyle O(1/{\sqrt {s}})}$ ${\displaystyle 1/s}$

Эргодическая обработка предполагает отправку потока пакетов, что позволяет использовать преимущества обычной стохастической обработки и обработки пакетов.

Пакетная обработка кодирует число с помощью возрастающего потока с более высокой базой. Например, мы бы закодировали число 4.3 десятью десятичными цифрами как

4444444555

поскольку среднее значение предыдущего потока равно 4,3. Такое представление дает различные преимущества: нет рандомизации, поскольку числа появляются в порядке возрастания, поэтому можно избежать проблем с ГПСЧ, но сохраняются многие преимущества стохастических вычислений (например, частичные оценки решения). Кроме того, он сохраняет линейную точность пакетной и эргодической обработки.

Смотрите также

• Нетрадиционные вычисления

Рекомендации

1. фон Нейман, Дж. (1963). «Вероятностная логика и синтез надежных организмов из ненадежных компонентов». Собрание сочинений Джона фон Неймана . Макмиллан. ISBN 978-0-393-05169-8.
2. Петрович, Р.; Силяк, Д. (1962). «Умножение посредством совпадения». АКТЕС Учеб. 3-го Межд. Аналоговый комп. Встреча .
3. Афусо, К. (1964), Кварт. Тех. Прог. Представитель , факультет компьютерных наук, Университет Иллинойса, Урбана, Иллинойс{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
4. Поппельбаум, В.; Афусо, К.; Эш, Дж. (1967). «Стохастические вычислительные элементы и системы». Материалы осенней совместной компьютерной конференции AFIPS '67 (осень), состоявшейся 14–16 ноября 1967 г. Том. 31. С. 635–644. дои : 10.1145/1465611.1465696. ISBN 9781450378963. S2CID  8504153.
5. Гейнс, Б. (1967). «Стохастические вычисления». Материалы весенней совместной компьютерной конференции AFIPS '67 (Весна) , состоявшейся 18–20 апреля 1967 г. Том. 30. С. 149–156. дои : 10.1145/1465482.1465505. ISBN 9781450378956. S2CID  832296.
6. Марс, П.; Поппельбаум, В. (1981). Стохастические и детерминированные усредняющие процессоры . П. Перегринус. ISBN 978-0-906048-44-3.
7. Эш, Джон В. (1969). RASCEL, программируемый аналоговый компьютер, основанный на регулярном массиве логики стохастических вычислительных элементов (доктор философии). Университет Иллинойса, Урбана, Иллинойс. ААИ700084.
8. Труды первого Международного симпозиума по стохастическим вычислениям и их приложениям . Тулуза, Франция. 1978. OCLC  499229066.
9. Гейнс, БР (2013) [1969]. «Стохастические вычислительные системы». В Тоу, Юлиус (ред.). Достижения в области науки об информационных системах . Том. 2. Спрингер. ISBN 9781489958433.
10. ван Даален, М.; Дживонс, П.; Шоу-Тейлор, Дж. (1993). «Стохастическая нейронная архитектура, использующая динамически реконфигурируемые FPGA». [1993] Труды семинара IEEE по FPGA для специализированных вычислительных машин . стр. 202–211. doi : 10.1109/FPGA.1993.279462. ISBN 0-8186-3890-7. S2CID  14929278.
11. Годе, Винсент; Рэпли, Энтони (февраль 2003 г.). «Итеративное декодирование с использованием стохастических вычислений». Электронные письма . 39 (3): 299–301. Бибкод : 2003ElL....39..299G. дои : 10.1049/эл: 20030217.
12. Алаги, А.; Ли, К.; Хейс, JP (2013). «Стохастические схемы для приложений обработки изображений в реальном времени». Материалы 50-й ежегодной конференции по автоматизации проектирования - DAC '13 . п. 1. дои : 10.1145/2463209.2488901. ISBN 9781450320719. S2CID  18174415.
13. Наджафи, Миннесота; Салехи, Мэн (2016). «Быстрая отказоустойчивая архитектура для алгоритма порогового значения локального изображения Сауволы с использованием стохастических вычислений». Транзакции IEEE в системах очень большой интеграции (VLSI) . 24 (2): 808–812. дои : 10.1109/TVLSI.2015.2415932. S2CID  6591306.
14. Наджафи, Миннесота; Лиля, диджей; Ридель, доктор медицины; Базарган, К. (2016). «Полисинхронные стохастические схемы». 2016 21-я Азиатско-Тихоокеанская конференция по автоматизации проектирования (ASP-DAC) . стр. 492–498. doi : 10.1109/ASPDAC.2016.7428060. ISBN 978-1-4673-9569-4. S2CID  8973285.
15. Алаги, А.; Хейс, JP (2013). «Обзор стохастических вычислений». Транзакции ACM во встроенных вычислительных системах . 12 (2 с): 1. CiteSeerX 10.1.1.296.4448 . дои : 10.1145/2465787.2465794. S2CID  4689958. 
16. Уинстед, К.; Рэпли, А.; Годе, В.; Шлегель, К. (сентябрь 2005 г.). «Стохастические итеративные декодеры». Слушания. Международный симпозиум по теории информации, 2005 г. ISIT 2005 г. Аделаида Австралия. стр. 1116–1120. arXiv : cs/0501090 . дои : 10.1109/ISIT.2005.1523513. ISBN 0-7803-9151-9. S2CID  16390484.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
17. Годе, Винсент; Рэпли, Энтони (февраль 2003 г.). «Итеративное декодирование с использованием стохастических вычислений». Электронные письма . 39 (3): 299–301. Бибкод : 2003ElL....39..299G. дои : 10.1049/эл: 20030217.
18. Гросс, В.; Годе, В.; Милнер, А. (2006). «Стохастическая реализация декодеров LDPC». Протокол конференции тридцать девятой асиломарской конференции по сигналам, системам и компьютерам .
19. Наджафи, М. Хасан; Дженсон, Девон; Лилья, Дэвид Дж.; Ридель, Марк Д. (декабрь 2019 г.). «Детерминированное выполнение стохастических вычислений». Транзакции IEEE в системах очень большой интеграции (СБИС) . 27 (12): 2925–2938. дои : 10.1109/tvlsi.2019.2929354 . ISSN  1063-8210. S2CID  201888463.
20. Дженсон, Девон; Ридель, Марк (07 ноября 2016 г.). «Детерминистический подход к стохастическим вычислениям». Материалы 35-й Международной конференции по компьютерному проектированию . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 1–8. дои : 10.1145/2966986.2966988. ISBN 978-1-4503-4466-1. S2CID  11281124.
21. Наджафи, М. Хасан; Джамали-Заваре, Шива; Лилья, Дэвид Дж.; Ридель, Марк Д.; Базарган, Киа; Харджани, Рамеш (май 2017 г.). «Закодированные во времени значения для высокоэффективных стохастических схем». Транзакции IEEE в системах очень большой интеграции (VLSI) . 25 (5): 1644–1657. дои : 10.1109/tvlsi.2016.2645902 . ISSN  1063-8210. S2CID  5672761.
22. Наджафи, М. Хасан; Лилья, Дэвид (2018). «Высококачественная понижающая выборка для детерминированных подходов к стохастическим вычислениям». Транзакции IEEE по новым темам вычислительной техники . 9 :7–14. дои : 10.1109/tetc.2017.2789243 . ISSN  2168-6750.
23. Наджафи, М. Хасан; Лилья, Дэвид Дж.; Ридель, Марк (05.11.2018). «Детерминистические методы стохастических вычислений с использованием последовательностей с низким расхождением». Материалы международной конференции по компьютерному проектированию . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 1–8. дои : 10.1145/3240765.3240797 . ISBN 978-1-4503-5950-4. S2CID  53236540.

дальнейшее чтение

• Гейнс, Брайан Р. (1967). «Методы идентификации с помощью стохастического компьютера» (PDF) . Материалы симпозиума МФБ «Проблемы идентификации в системах автоматического управления», Секция 6 «Специальные средства идентификации», Прага, 12–19 июня 1967 г. Проверено 11 ноября 2013 г.
• Алаги, Армин; Хейс, Джон П. (2013). «Обзор стохастических вычислений» (PDF) . Транзакции ACM во встроенных вычислительных системах . 12 (2с): 1–19. CiteSeerX  10.1.1.296.4448 . дои : 10.1145/2465787.2465794. S2CID  4689958 . Проверено 11 ноября 2013 г.