Automata: специализированный процессор для обработки «больших данных»

В конце 2012 года компания Micron, крупный американский производитель модулей памяти и флэш-накопителей, продемонстрировала на конференции Supercomputing 2013 интереснейшее устройство — специализированный процессор под названием Automata.

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

Сайт Micron перечисляет потенциальные сферы применения Automata: биоинформатика, распознавание образов на видео в реальном времени, системы сетевой безопасности. Сторонние эксперты добавляют, что новым процессором наверняка заинтересуются спецслужбы. Он идеально подходит для того типа анализа коммуникаций, которым занимаются в АНБ.

Разработка Automata продолжалась около семи лет, и это были не самые простые для Micron времена. Однако команду создателей этого процессора не коснулись ни массовые увольнения в разгар финансового кризиса 2008 года, ни последовавшее за ним «затягивание поясов» на фоне многолетних убытков. Это позволило компании опередить конкурентов. Аналогов Automata, судя по всему, пока не существует.

Что же в нём особенного? Каждая микросхема Automata содержит тысячи, а то и миллионы примитивных процессоров, связи между которыми можно перестраивать в зависимости от поставленной цели. Каждый из элементов по совместительству является ячейкой памяти. Это значит, что данные не приходится то и дело гонять между ОЗУ и регистрами процессора — обработка происходит на месте.

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

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

Каждая вершина этого графа соответствует состоянию автомата, а цифры над дугами обозначают символ, поступивший на вход. Если на вход поступил символ 1, то состояние меняется на другое по стрелке, помеченной цифрой 1.

Вот чуть более наглядное описание. Представьте сеть дорог, которую пытается преодолеть путник. Чтобы добраться до своей цели, на каждой развилке он заглядывает в инструкцию, которая сообщает, что на первой развилке нужно свернуть на дорогу А, на второй — на дорогу Б, и так далее.

В этой метафоре развилка, на которой стоит путник, соответствует текущему состоянию автомата, а его инструкция — цепочке символов, поступающих на вход. Каждый раз, заглянув в инструкцию, путник отправляется к следующей развилке, и состояние автомата меняется. Важный момент: смысл указаний, которые содержатся в инструкции, зависит от того, где именно он их читает. Дорога, помеченная буквой А, на одной развилке может вести направо, на другой — налево.

Так вот, если наш путник попадёт в недетерминированный конечный автомат, его ждёт неприятный сюрприз: на некоторых развилках он может обнаружить сразу несколько дорог с нужным названием, а на некоторых — ни одной. Иными словами, при одном и том же состоянии автомата один и тот же символ, поступивший на вход, может вызывать переход не к одному, а к нескольким различным состояниям.

Это недетерминированный конечный автомат: из первой вершины исходят две дуги, помеченные цифрой 1. Его функциональность эквивалентна детерминированному автомату, схема которого приведена выше.

Что дальше? Путник не может разорваться на части. Он не знает, какая из одноимённых дорог ведёт к цели, поэтому ему приходится выбрать одну из них наугад. Этот выбор определяет, какой путь он проделает дальше. Одна и та же инструкция может привести его в совершенно различные места — всё зависит от того, куда он свернул.

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

Именно поэтому при моделировании недетерминированных конечных автоматов желательно использовать не последовательные, а параллельные вычисления. Это позволяет одновременно прослеживать все пути изменения состояний, которые допускает данный автомат. Если такая возможность есть, то недетерминированные автоматы предпочтительнее, потому что они всегда многократно проще эквивалентных детерминированных автоматов. А это, в свою очередь, полезно потому, что конечные автоматы идеально подходят для решения некоторых задач, связанных с анализом данных.

По своему устройству процессоры Automata напоминают микросхемы памяти SDRAM. Предполагается даже, что они будут распространяться в виде модулей DIMM, но сходство на этом не заканчивается. Основу SDRAM составляет двумерная матрица ячеек памяти. В Automata аналогичную матрицу образуют так называемые элементы смены состояния.

Чтобы обратиться к определённой ячейке в SDRAM, требуется знать её адрес в матрице по вертикали и по горизонтали. В Automata адресу по вертикали соответствует символ, поступающий в конечный автомат. Что касается адреса по горизонтали, то его определяет перепрограммируемая маршрутизирующая матрица. 

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

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

Схема Automata. Аббревиатурой STE обозначены элементы смены состояния. Routing matrix — это маршрутизирующая матрица. 

Существующие образцы Automata способны перемалывать поток восьмиразрядных символов со скоростью 1 гигабит в секунду на каждую микросхему (всего их на модуле DIMM восемь). Это опережает не только программную реализацию на обычном компьютере, но и сравнимые по функциональности аппаратные решения на базе перепрограммируемых вентильных матриц (FPGA).

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

Точнее, будет ускорять. Пока существуют лишь прототипы, но в течение 2014 года Micron обещает предоставить сторонним разработчикам работоспособные образцы. Массовое производство Automata начнётся не раньше следующего года.