3 года назад 19 ноября 2015 в 1:17 476

Справка: Алексей Юрьевич Попов родился в 1974 году, окончил МГТУ им. Н.Э. Баумана. Кандидат технических наук, доцент кафедры «Компьютерные системы и сети». Автор 28 научных работ в области разработки программно-аппаратных средств вычислительной техники.

Эпоха, когда компьютер с принципиально новой архитектурой можно было собрать у себя в гараже, миновала. Доцент кафедры «Компьютерные системы и сети» МГТУ им. Баумана Алексей Попов не пытался опровергнуть это утверждение. У него просто появилась идея, которая, как ему показалось, позволяет ускорить работу компьютера, и он старался реализовать ее шаг за шагом. А в итоге собрал работающий прототип нового процессора с принципиально другой архитектурой, не похожей на повсеместно используемую сейчас архитектуру фон Неймана.

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

Сноска: МКОД (MISD, Multiple Instruction Single Data) – вычислительная система со множественным потоком команд и одиночным потоком данных, одна из четырех архитектур ЭВМ по классификации М. Флинна. Три остальные – это: ОКОД (SISD, Single Instruction Stream over a Single Data Stream) – вычислительная система с одиночным потоком команд и одиночным потоком данных, к которой относятся традиционные, привычные нам компьютеры фон-неймановской архитектуры; ОКМД (SIMD, Single Instruction Multiple Data) – вычислительная система с одиночным потоком команд и множественным потоком данных, к которой относятся векторные процессоры; и МКМД (MIMD, Multiple Instruction Multiple Data) – вычислительная система со множественным потоком команд и множественным потоком данных, к которой относятся многоядерные процессоры и мультипроцессорные машины. Из всех четырех МКОД – самая «провальная» архитектура. Попытки создать компьютер МКОД предпринимались неоднократно, одна из самых удачных была в 1970-х, когда Ксян-Цунг Кунг (Hsiang-Tsung Kung) и Чарльз Лейзерсон (Charles Eric Leiserson) разработали систолические матрицы. Если проводить аналогию между структурами вычислительной системы и живого организма, то памяти можно отвести роль сердца, множеству процессорных элементов – роль тканей, а поток данных следует рассматривать как циркулирующую кровь. Отсюда и происходит название «систолическая матрица» (систола – сокращение предсердий и желудочков сердца, при котором кровь нагнетается в артерии). Но систолические матрицы не универсальны и сегодня практически не используются.

Помимо MISD – довольно экзотической архитектуры, которая сегодня в виде работающих устройств практически не реализована, – в схеме Попова бросается в глаза и другое решение – сопроцессор. Идея сопроцессора отнюдь не нова. До 1997 года математический сопроцессор (сначала в виде отдельного чипа, потом в виде схемы, выполненной на том же кристалле, что и центральный процессор) был практически в каждом персональном компьютере и служил для выполнения операций над вещественными числами. Потом от него отказались и дружно перешли на единый универсальный процессор, который выполняет любые операции с любыми типами данных.

Но в сентябре 2013 года Apple в Айфоне 5S обнародовала чип M7, который представлял из себя сопроцессор, собирающий, обрабатывающий и сохраняющий данные сенсоров телефона (гироскопа, акселерометра и т. д.). Чип позволял обрабатывать информацию о движении телефона в пространстве в тот момент, когда телефон находился в спящем режиме, а значит, экономить кучу энергии.

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

Главная особенность процессора обработки структур данных (ПОСД) в том, что на аппаратном уровне (то есть когда программа вшита прямо в чип) он хранит информацию не последовательно в ячейках памяти, как обычный процессор, а в виде так называемого B+ дерева. B+ деревья используются повсеместно для работы с большим количеством данных. Их применяют для хранения информации практически все современные файловые системы и базы банных. Также в ПОСД на аппаратном уровне реализованы команды добавления, удаления и поиска данных. Это позволяет достичь максимальной скорости работы с данными без операционных систем и задействования дополнительных ресурсов. Программная начинка микросхемы и ее способность работать параллельно с центральным процессором (ЦП) позволяют получить ощутимый прирост производительности при решении трудоемких задач. А одной из самых трудоемких задач для обычного процессора является поиск данных. Кроме того, это задача чрезвычайно распространенная. Поиск данных лежит в основе многих алгоритмов, начиная от самых простых и заканчивая самыми сложными. Хранение данных в виде B+ дерева позволяет уменьшить количество шагов, затрачиваемых машиной на поиск, причем уменьшить на порядок. Важно, что в случае с ПОСД с увеличением количества элементов, среди которых осуществляется поиск, время поиска возрастает незначительно.

Вору в помощь

Предположим, нам нужно решить достаточно простую задачу: в богатый дом, охраняемый огромными злыми собаками, забрался вор с большим рюкзаком. Собак он усыпил, но ненадолго. По этой причине вор не может сделать несколько ходок, он унесет с собой ровно столько, сколько сможет поднять. Задача состоит в том, чтобы унести поклажи на максимальную стоимость. Как будет решать эту задачу обычный процессор? Сначала основной алгоритм запускает алгоритм поиска вещи с максимальной стоимостью. Когда вещь найдена, основной алгоритм «укладывает» ее в рюкзак и снова запускает алгоритм поиска максимума. И так до того момента, пока задача не будет решена. Причем для поиска максимума компьютеру придется последовательно перебрать все вещи, находящиеся в доме. В процессоре обработки структур алгоритм поиска максимума заложен аппаратно. Поэтому в случае решения задачи с его участием ЦП беспрерывно занимается одним – укладывает в рюкзак максимально дорогие вещи, которые подкладывает ему ПОСД. А поскольку алгоритм поиска максимума, реализованный на ПОСД, работает намного быстрее, чем подобный алгоритм на обычном процессоре, то очередь дорогих вещей выстраивается им наперед, с опережением. ЦП остается только брать готовые значения и оперировать ими, пока задача не будет решена. То есть время решения задачи уменьшается на то значение, которое было бы потрачено ЦП на поиск, а, как мы уже говорили, поиск – одна из самых трудоемких и времязатратных задач для обычного процессора. Конечно, ПОСД позволяет решать гораздо более сложные и запутанные задачи, но приведенная задача о воре дает возможность наглядно показать, как за счет ПОСД достигается параллельность работы.

«Сейчас много задач, которые невозможно решать в потоке, – говорит Попов. – Например, на улицах и во дворах Москвы около 140 000 камер. Дата-центр, куда с них поступает вся информация, хранит ее только 5 суток. Если что-то произошло, но им не успели сказать: «Мне нужно вот это видео!», то информация удаляется. А задач, которые можно бы было решать, имея возможность обрабатывать информацию с камер в режиме реального времени, очень много. Например, школьник Петя пошел в гости к Васе, а маме ничего не сказал и забыл дома телефон. Мама Пети бьет тревогу, звонит в полицию. Полиция просит фотографию Пети, пробивает по фотографии и сообщает, что Петя зашел в синий подъезд такого-то дома по такой-то улице и пока из него не выходил. И мама понимает, что Петя сидит у Васи. Если мы успеем эту информацию проанализировать на ходу, отсеивая зерна от плевел, – момент, когда Петя зашел в подъезд, от долгих минут, когда на видео просто закрытая синяя дверь подъезда, в которую никто не заходит и из которой никто не выходит, – то мы сможем хранить значимую информацию с камер не 5, а 100 суток. Применим аналитику и создадим базу данных с определенными маркерами, к которой можно будет обратиться с фотографией Пети, и база данных сама скажет нам, где он находится в данный момент».

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

Также с его помощью можно увеличить скорость обработки базы данных за счет ускоренной индексации данных, реализовывать базы данных «ключ-значение» аппаратно. ПОСД мог бы стать частью принципиально новых суперкомпьютеров, основой быстродействующих сетевых устройств и новой аппаратной операционной системы. Также он, возможно, позволит ускорять существующие операционные системы, в том числе в режиме реального времени: планирование задач в системе, реализация очередей событий и реестров.

Битва с гигантами

Помимо алгоритма поиска максимума в работающем прототипе ПОСД аппаратно реализован алгоритм, позволяющий решать задачи маршрутизации, – алгоритм Дейкстры. Это алгоритм на графах, который находит кратчайшие пути от одной из вершин графа до всех остальных. Проще говоря, с помощью этого алгоритма можно проложить кратчайший маршрут из одного города в другой. Или решить более сложную задачу: имея некоторое количество авиарейсов между городами мира, для каждого из которых известна стоимость, найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула (учитывая, что стоимость перелета из A в B может быть не равна стоимости перелета из B в A). Также этот алгоритм позволяет решать задачи маршрутизации в сетях и другие задачи. По сути, задача поиска минимального пути – одна из краеугольных задач в науке разработки алгоритмов. Оптимальное решение такой задачи позволит повысить производительность любой компьютерной сети без замены серверов, роутеров, сетевых кабелей (нужно будет лишь «перепрошить» сетевые устройства новой программой, которая находит пути в сетях гораздо быстрее предыдущей версии). Именно поэтому данный алгоритм был выбран в качестве одного из сравнительных тестов, позволяющих продемонстрировать возможности ПСОД. Такие тесты всегда проводятся производителями, а также независимыми аналитиками при выпуске нового железа, будь то новый чип для ускорения генерации трехмерных образов, новое поколение центральных процессоров или сетевая карта.

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

Соперниками ПОСД в этих тестах выступили два домашних центральных процессора и один микропроцессор на аппаратной основе ПЛИС*.

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

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

Время, потраченное на добавление, окупается быстрым удалением и, что самое важное, поиском. Эти операции ПОСД выполняет лишь немного медленнее такого «гиганта», как Core i5, работающего на частоте, более чем в 20 раз превышающей частоту работы ПОСД.

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

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

Сравнение среднего времени работы процессора обработки структур и микропрограммных ЭВМ для количества ключей от 105 до 2*106

ЭВМ Добавление (секунды) Удаление (секунды) Поиск (секунды)

Процессор обработки структур, 100 МГц, 256 Мбайт ОЗУ

14,6080 0,0091 0,0059

Core i5, 2530 МГц, 4 Гбайт ОЗУ

1,9803 0,0045 0,0024

Pentium 4, 1500 МГц, 256 Мбайт ОЗУ

5,9302 0,0143 0,0064

Microblaze, 100 МГц, 256 Мбайт ОЗУ

576,1835 1,5665 0,1827

«Я сам себе пытался доказать и доказал, что не зря все эти годы проектировал, что ПОСД работает и стоит идти дальше, – комментирует результаты тестов Попов. – Я уже знаю, где ПОСД можно оптимизировать, и раза в три-четыре я его ускорю спокойно. Там есть механизм, который в следующей версии можно сделать иначе».

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

***

Мне в одиночку пришлось пройти полный путь вычислительной техники, с нуля до работающего прототипа, – рассказывает Попов. – Когда я эту кашу шесть лет назад заварил, я не очень владел проектированием. Я, конечно, учился этому, я инженер по образованию, но все равно это очень специфическая и сложная тема с множеством нюансов: тактовые частоты, тактовые домены, задержки и т. д. Это не программа, которую написал и она заработала. Это вся схемотехника и электроника, это на порядок сложнее, чем написать программу. То, что я собрал прототип и он заработал, – это было для меня чудом».

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

Как показывают результаты тестов, несколько часов в день, которые Попов в течение шести лет тратил на разработку своего процессора обработки структур данных, прошли не зря. Конечно, на данный момент ПОСД – это узкоспециализированный механизм, заточенный под выполнение, по сути, одной задачи: работы с данными в виде оптимальной структуры – B+ дерево. Но удача Попова состоит в том, что ему удалось найти именно ту задачу, которую приходится выполнять чаще всего и на выполнение которой обычно уходит много времени и ресурсов. Именно поэтому ее выполнение имеет смысл перепоручить отдельному устройству, которое сможет разгрузить центральный процессор и существенно ускорить работу всей системы в целом.

* Core i5, 2530 МГц, 4 Гбабйт RAM
Pentium 4, 1500 МГц, 256 Мбайт RAM
Microblaze, 100 МГц, 256 Мбайт RAM

Никто не прокомментировал материал. Есть мысли?

Хм, а насколько такой сопроцессор аппаратно совместим с текущими импортными процами? Есть ли реальная возможность выпустить, скажем, плату расширения с таким камешком, который серьезно ускорит работу уже существующего компа?

Были же в свое время видеокарты с дополнительным процессором для просчета физики… Вуду, кажется, назывался…