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

Big Data / Технологии
автор: Кирилл Тихонов  24 января 2014

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

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

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

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

dimm

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Схема Automata.

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

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

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

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

Поделиться
Поделиться
Tweet
Google
 
Читайте также
LaCie 12big – 96 быстрых терабайт на столе
LaCie 12big – 96 быстрых терабайт на столе
Intel представила новую платформу для IoT
Intel представила новую платформу для IoT
Технологии резервного копирования больших данных
Технологии резервного копирования больших данных
  • Lepsik Baralgeen

    биткоины генерить или SHA3 ломать?

    • Denis Terebiy

      ИИ строить

  • ExMuser

    Да это ж прототип нейросети!

    • Олег Парамонов

      Не, это штука, которая очень быстро решает регулярные выражения.

      • ExMuser

        Ааа… Просто Вы расписали очень похоже…

        • Олег Парамонов

          в соседнем комментарии уже и квантовый компьютер разглядели

  • Андрей Иванов

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

  • Junker

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

    Идея, кстати, пришла из мысли поместить процессор прямо на винчестер как продолжение развития DMA. Скоро наверное появятся подобные модули памяти на основе SSD.

    • ExMuser

      Дык, статья же на днях была. Вы, наверное, там подсмотрели? ;)

      • Junker

        Нет, вот только что по вашей наводке нашел. Клево. :)
        Значит скоро будет ИИ.

        • ExMuser

          Хотелось бы надеяться. Пмсм, мы не разгадали принцип человеческого мышления, а наши алгоритмы ИИ пока ещё достаточно примитивны. Вы думаете, что увеличение объёма и скорости обмена информацией ускорит исследования?

          • Junker

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

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

          • ExMuser

            Именно это я и предполагал. Ибо физические носители разума бесконечно далеки друг от друга по всем характеристикам. Почему и заикнулся об алгоритмах.
            Про самолёт и птицу — аллегория понравилась. Не сомневаюсь, что через *-цать лет у нас будут симмонсовые ИскИны или головачёвские инки… :)

          • Junker

            Да, и ИИ решительно и смело начнет осваивать космос, ему там будет просторнее и комфортнее чем нам. Поэтому никакого терминатора можно не боятся. Мне больше нравится БиБи из Смешариков :)

          • ExMuser

            Ога. А потом пришельцы с космоса появятся. :)
            До смешариков не добрался, развёлся на Маше-и-медведе…

Хостинг "ИТ-ГРАД"
© ООО "Компьютерра-Онлайн", 1997-2017
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.
«Партнер Рамблера» Почта защищена сервером "СПАМОРЕЗ" Хостинг "Fornex"