«Лирический процессор», ошибки и сложные вычисления

Недавно (в августе 2010 г.) компания Lyric Semiconductors представила новый чип (вместе с соответствующим математическим обеспечением), который, по замыслу производителей, решает алгоритмически сложные задачи типа коррекции ошибок или распознавания образов гораздо быстрее и эффективнее, нежели все известные на сегодня устройства. Подробности, касающиеся процессора, не разглашаются, однако известно, что его работа базируется на аналоговой логике.

Рис. 1. Граф, иллюстрирующий схему постановки диагноза. Пациент страдает одышкой (Од), и рентгенограмма (Х) у него не в порядке. Причиной тому может быть туберкулез (Т), рак легких (Р) или бронхит (Б). Туберкулез и рак легких имеют схожие симптомы и могут возникать одновременно (О). Причиной туберкулеза мог быть поездка пациента в Азию (А), а рак легких и бронхит с определенной вероятностью возникают вследствие курения (К)

Информацию можно обрабатывать с помощью цифровых и аналоговых устройств. В цифровых входным сигналом является набор нулей и единиц, над которыми внутри процессора выполняются логические операции по правилам булевой логики. Вычисления носят характер математических преобразований. Аналоговые же обрабатывают непрерывные сигналы. По сути, они моделируют сложные процессы с помощью систем, поведение которых аналогично поведению исследуемой системы. Каждый из способов обработки имеет свои преимущества и недостатки. Аналоговые вычисления в 5–10 быстрее цифровых и потребляют, как правило, существенно меньше энергии. Основной недостаток – специфичность таких вычислений. Иными словами, под каждую задачу требуется своя модель (архитектура) процессора. В отличие от этого цифровые вычисления являются универсальными. Любой вычислительный алгоритм можно реализовать из набора стандартных базовых операций (типа AND или XOR), выполняемых с помощью опять же стандартных элементов типа транзисторов и диодов. Именно универсальность цифровых вычислительных машин привела к их доминированию. Сегодня аналоговые вычисления применяются главным образом для решения узкого круга инженерных задач (к примеру, теплопроводности или гидродинамики).

Однако несмотря на свои безусловные преимущества, современные компьютеры могут справиться далеко не со всякими задачами. Любые задачи, требующие перебора (так называемые NP и NP-полные задачи), даже на самых мощных компьютерах занимают нереально большое время и ресурсы. Именно на таких сложных вычислениях и построена криптография сегодня. Важные алгоритмически сложные задачи встречаются в фармацевтике, биологии, в экспертных системах, при помехоустойчивом кодировании и коррекции ошибок. Все это заставило исследователей в начале XXI в., практически после полувекового господства цифровых вычислений, вновь обратить внимание на аналоговые устройства и именно среди них искать альтернативу современным компьютерам.

Что же препятствует цифровым и аналоговым вычислениям? Самый главный недостаток первых – ограничение по скорости, которое определяется двумя факторами: тактовой частотой процессора и временем распространения сигнала между двумя наиболее удаленными битами. Аналоговые вычисления лишены этого, однако в них нет «логики» (логических операций) и они не программируемы. При цифровых вычислениях любой физический сигнал внутри процессора округляется (до логических нуля или единицы), что существенно повышает их помехоустойчивость. Аналоговые сигналы чувствительны к шуму, кроме того, считывание непрерывного сигнала требует гораздо больше времени, нежели дискретного.

Бен Вигода (Ben Vigoda) нашел способ объединить преимущества аналоговых и цифровых вычислений и смог воплотить в «железе» свои идеи. Фактически он увидел три важных момента:

• многие алгоритмически сложные задачи сводятся к анализу графов, и этот анализ можно представить в виде набора небольшого количества логических операций, выполняемых не в булевой, а в байесовской (вероятностной) логике;

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

• с помощью тех же транзисторов и диодов можно довольно быстро и точно определять значение аналогового сигнала даже при наличии шума – достаточно пропустить сигнал через так называемую петлю обратной связи.

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

Поясним подробнее, как работает новый процессор. Допустим, нам надо решить задачу о «причинно-следственных» связях, например поставить диагноз, если известны ряд симптомов и некоторые сведения из истории болезни пациента. Разные заболевания могут вызывать схожие симптомы с той или иной вероятностью, а одни и те же вредные привычки – приводить к целому букету болезней. Для выяснения наиболее вероятного заболевания можно воспользоваться графом, в вершинах которого будут расположены болезни, симптомы, события, а ребра устанавливают связь между причиной и следствием (например, болезнью и симптомом), как это изображено на рис. 1. Если каждому ребру присвоить вероятность, то, проанализировав все возможные пути от корней дерева к его вершине, можно определить наиболее вероятное заболевание. Для цифрового компьютера подобная задача сводится к перебору огромного количества вариантов и потому является алгоритмически сложной. Однако анализ такого дерева допускает альтернативный алгоритмический подход. Действительно, при вычислении вероятности того или иного пути на графе приходится перемножать и суммировать вероятности. Подобные операции можно свести к стандартным логическим операциям, очень похожим на булевы операции AND, XOR и т. п., но с поправкой на вероятность. Рассмотрим, например, операцию XOR – сложение по модулю 2. Результатом ее выполнения будет «0», если оба входящих числа (обозначим их x и y) одинаковы, и «1», если x и y разные. Теперь представим себе, что x и y принимают значения «0» и «1» с некоторой вероятностью. В этом случае результат сложения (обозначенный как z) равен «0» с вероятностью

p(z=0)=p(x=0)p(y=0)+p(x=1)p(y=1)

и равен «1» с вероятностью

p(z=1)=p(x=0)p(y=1)+p(x=0)p(y=1).

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

Эту операцию можно назвать байесовским (или нечетким) XOR. Похожим образом вводятся и другие аналоги булевых операций. Важно, что все дерево вероятностей можно разбить на отдельные блоки, соответствующие нечетким логическим операциям, набор таких операций и будет осуществлять «нечеткий» алгоритм.

Следующий шаг состоит в создании элементов (физических устройств), которые будут выполнять такие нечеткие операции. В «булевых» (цифровых) компьютерах основными элементами являются транзисторы, имеющие два режима – открытый и закрытый, соответствующих логическим «0» и «1». Для нечетких операций Вигода предложил использовать те же транзисторы, но измерять не просто факт протекания тока (т. е. вентиль открыт или закрыт), а силу тока. Значение тока, проходящего через транзистор, сопоставляется с величиной вероятности p. Пример узла, выполняющего нечеткий XOR, приведен на рис. 2. Схема имеет четыре входа (кодирующие вероятности появления логических «0» и «1» в элементах x и y) и два выхода (соответствующие вероятностям p(z=0) и p(z=1)). Несмотря на большее количество транзисторов (по сравнению с булевым сумматором), такая схема гораздо быстрее, чем цифровая: время срабатывания определяется временем протекания токов.

На сегодняшний день предложенная компанией Lyric Semiconductors реализация вероятностного процессора имеет, по словам производителей, весьма специфическое предназначение – корректировать ошибки. Сделано ли это путем «жесткой прошивки» алгоритма, или просто созданный универсальный образец был запрограммирован таким образом, неизвестно. Тем не менее «лирический процессор» является целиком и полностью совместимым с «обычными компьютерами». В будущем предполагается расширить область применимости вероятностных CPU для решения, например, задач фильтрации спама, распознавания образов и пр. Пока «лирический процессор» мыслится как специализированное дополнительное устройство, однако не исключено, что со временем такие процессоры обретут необходимую универсальность – будут программируемы и смогут расширить наши возможности в области «механизации» интеллектуальных задач.

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365