Вероятностный процессор: триумф байесовской логики

Автор: Олег Нечай

Опубликовано 23 августа 2010 года

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

В чём же заключаются отличия и преимущества гипотетического вероятностного процессора от традиционного чипа, оперирующего с двоичной логикой? Напомним, что базовый принцип работы вычислительных систем уже на протяжении более шестидесяти лет - это закон исключения третьего булевой алгебры, который гласит, что логические переменные могут принимать только два значения: "да" или "нет", "истина" или "ложь", 1 или 0. В Lyric Semiconductor нашли возможность использовать при вычислениях промежуточные значения между "нулём" и "единицей", "истиной или правдой". Смысл этих промежуточных значений состоит в определении степени вероятности истинности тех или иных выражений.

Подход разработчиков основывается на одной из ключевых теорем теории вероятностей - теоремы Байеса, доказанной триста лет назад английским математиком и священником Томасом Байесом. Выведенная им формула позволяет, исходя из известных фактов, вычислить вероятность того, что они были вызваны конкретной причиной. Теорема даёт возможность оценивать вероятность событий, когда известна лишь часть информации о них, полученная эмпирическим путём.

Главный недостаток предложенной Байесом формулы заключался в том, что для получения более менее точных результатов необходимо множество вычислений, поэтому о ней вспомнили только к концу восьмидесятых, когда компьютерная техника достигла уровня, позволяющего использовать её на практике. С тех пор теорема Байеса стала широко применяться в самом разном программном обеспечении. Банальнейший пример - надоедливый Скрепыш, система контекстно-зависимых советов из пакета офисных программ Microsoft Office.

В дальнейшем программисты Microsoft использовали байесовскую логику для диагностики неполадок в операционных системах начиная с Windows XP. Теоретическая база, созданная провинциальным английским пастором триста лет назад, легла в основу сложнейших систем анализа массивов данных, способных вычислять вероятностные связи между огромным множеством фактов. Контекстная реклама на страницах в интернете тоже использует принципы байесовской логики: программный движок анализирует содержание страницы и предлагает наиболее близкие к нему рекламные объявления. Среди прочих примеров - интернет-магазины, предлагающие посетителям товары на основе сведений о предыдущих покупках и посещённых страницах, и, конечно же, почтовые спам-фильтры, отправляющие в корзину мусорные письма на основе анализа вероятности.

Но если в программном обеспечении теорема Байеса применяется уже давно, то в микропроцессорах она до последнего времени не использовалась. Как утверждают в Lyric Semiconductor, инженеры компании создали такой тип транзисторных логических цепей, который может оперировать не с двоичной, а с байесовской логикой. То есть транзисторы работают в них не в режиме выключателей, а в режиме реостатов. Конструкторы перенесли вероятностные принципы вычислений на аппаратный уровень, что должно существенно ускорить выполнение операций с элементами вероятностей, чем в нынешней ситуации, когда соответствующий софт выполняется на чипах с бинарной логикой.

Работу над вероятностным процессором один из основателей Lyric Semiconductor Бен Вигода начал много лет назад в Массачусетском технологическом институте, однако воплотить свою идею "в железе" он смог лишь в 2006 году, когда перспективной разработкой заинтересовались американские военные. В Пентагоне посчитали, что такие чипы могут оказаться чрезвычайно полезными в системах противоракетной обороны, выделяя вражеские боеголовки из множества объектов и случайных помех в атмосфере. В результате Агентство по перспективным оборонным научно-исследовательским проектам DARPA выделило 18 миллионов долларов, на которые и была создана компания.

Первым реальным плодом деятельности Lyric Semiconductor стал микропроцессор коррекции ошибок Lyric Error Correction (LEC) для работы с флэш-памятью. Почему именно такой чип стал первенцем компании? Дело в том, что для получающей всё большее распространение твёрдотельной памяти характерно наличие ошибок, в среднем, в одном бите из тысячи - в современных микросхемах разница между единицей и нулём заключена всего в сотне электронов. Для их исправления процессор коррекции на основе уникального кода, записываемого одновременно с данными, вычисляет контрольную сумму и устанавливает, в какой из ячеек вместо нуля записана единица и наоборот.

Однако в будущем с повышением плотности хранения данных число ошибок будет неизбежно возрастать, даже в чипах следующего поколения ошибочным может оказаться один бит на каждую сотню, из-за чего придётся усложнять микросхемы коррекции и увеличивать их площадь. Более того, при использовании традиционных технологий исправление ошибок становится узким местом на пути повышения скорости записи/чтения в твёрдотельной памяти.

Именно для таких вероятностных вычислений и создан LEC, который в 30 раз меньше обычных современных микросхем коррекции и потребляет в 12 раз меньше электроэнергии. В отличие от чипов на базе двоичной логики, LEC, созданный на основе логических вентилей "байесовский NAND", значительно быстрее вычисляет ошибочные биты, поскольку из процесса исключается громоздкая схема с записью кода и вычислением контрольной суммы и заменяется вероятностной схемой. При этом, хотя LEC работают на основе кардинально иных принципов, чем бинарные чипы, они полностью совместимы с обычными электронными компонентами.

Компания Lyric Semiconductor уже готова продавать лицензии на LEC с 12-месячной технической поддержкой по интеграции чипа в конкретную продукцию. Между тем, на подходе уже универсальный микропроцессор GP5, образцы которого планируется представить не позже 2013 года. Как утверждают разработчики, эта микросхема будет способна эффективно рассчитывать вероятности в любых типах приложений - от поиска в интернете до секвенирования ДНК. Уже сегодня заявлена в тысячу раз большая производительность таких расчётов по сравнению с обычными современными x86-совместимыми системами на процессорах AMD и Intel.

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