Принципы организации и методология применения вычислительных систем со множественным потоком команд и одиночным потоком данных тема диссертации и автореферата по ВАК РФ 05.13.15, доктор наук Попов Алексей Юрьевич

• Попов Алексей Юрьевич
• доктор наук
• 2021

Оглавление диссертации доктор наук Попов Алексей Юрьевич

Введение

Глава 1. Определение предметной области и постановка задачи

1.1 История развития вычислительных систем обработки больших объемов данных

1.2 Проблемы развития вычислительной техники

1.3 Влияние архитектуры ЭВМ на эффективность обработки данных

1.4 Критический анализ исследований и разработок в области аппаратного ускорения обработки данных

1.5 Обоснование выбора темы исследования

Глава 2. Анализ методов и средств аппаратной поддержки обработки

множеств и структур данных

2.1 Вычислительные аспекты реализации операций дискретной математики в ЭВМ

2.2 Анализ элементной базы для реализации аппаратной обработки множеств и структур данных

2.3 Варианты организации аппаратной обработки множеств и

структур данных

2.4 Исследование принципов организации памяти и доступа к структурам данных

2.5 Цикл выполнения команд Процессора обработки структур

2.6 Выводы по главе

Глава 3. Архитектура вычислительной системы со множественным

потоком команд и одиночным потоком данных

3.1 Принципы функционирования вычислительной системы с аппаратной поддержкой операций над структурами данных

3.2 Выбор вариантов взаимодействия устройств в вычислительной системе со множественным потоком команд и одиночным

потоком данных

3.2.1 Топология общей шины

3.2.2 Топология независимых шин

3.2.3 Топология с иерархией шин

3.3 Принципы функционирования Процессора обработки структур

3.3.1 Функциональная декомпозиция Процессора обработки структур

3.3.2 Принципы хранения структур данных

3.4 Аппаратные средства реализации основных операций в вычислительной системе со множественным потоком команд и одиночным потоком данных

3.4.1 Функциональная схема Процессора обработки структур

3.4.2 Принцип функционирования Каталога

3.4.3 Принцип функционирования Операционного буфера

3.4.4 Принцип функционирования Устройства выборки команд

и определение форматов

3.4.5 Набор машинных команд

3.4.6 Реализация команды Добавление

3.4.7 Реализация команды Удаление

3.5 Реализация центрального устройства управления Процессора обработки структур

3.6 Принципы организации высокопроизводительных вычислительных систем со множественным потоком команд и множественным потоком данных

3.7 Выводы по главе

Глава 4. Оптимизация алгоритмов в вычислительной системе с множественным потоком команд и одиночным потоком данных

4.1 Цели и принципы оптимизации алгоритмов в вычислительной системе со множественным потоком команд и одиночным

потоком данных

4.1.1 Особенности представления алгоритмов в

вычислительной системе со множественным потоком команд и одиночным потоком данных

4.1.2 Анализ существующих подходов к разработке параллельных алгоритмов в вычислительных системах

4.1.3 Общие вопросы ускорения вычислительного процесса

при организации параллельной обработки

4.1.4 Методика модификации алгоритмов для вычислительной системы со множественным потоком команд и одиночным потоком данных

4.2 Вопросы представления программы ЭВМ со множественным

потоком команд и одиночным потоком данных

4.2.1 Представление алгоритмов со множественным потоком команд и одиночным потоком данных в виде псевдокодов

4.2.2 Формальная постановка задачи декомпозиции информационного графа программы

4.2.3 Преобразование декомпозиции информационного графа программы и критерии получения оптимальной декомпозиции информационного графа алгоритма

4.2.4 Преобразование декомпозиции информационного графа программы для вычислительной системы со множественным потоком команд и одиночным потоком данных

4.3 Реализация алгоритмов оптимизации на сетях и графах

4.3.1 Алгоритм Дейкстры

4.3.2 Алгоритмы обхода графа

4.3.3 Алгоритм Форда-Фалкерсона

4.3.4 Алгоритмы поиска минимального остовного дерева

4.4 Вопросы применения вычислительной системы со

множественным потоком команд и одиночным потоком данных в

программно-аппаратных системах

4.4.1 Применение Процессора обработки структур для аппаратного ускорения баз данных

4.4.2 Защита данных в системах обработки информации

4.4.3 Применение вычислительной системы со множественным

потоком команд и одиночным потоком данных в роботехнических системах

4.5 Выводы по главе

Глава 5. Реализация и экспериментальные исследования эффективности вычислительной системы со множественным потоком команд и одиночным потоком данных

5.1 Реализации вычислительной системы со множественным

потоком команд и одиночным потоком данных

5.1.1 Этапы проектирования системы со множественным

потоком команд и одиночным потоком данных

5.1.2 Основные технические параметры реализации Процессора обработки структур

5.1.3 Язык ассемблера и машинные коды команд Процессора обработки структур

5.2 Верификация Процессора обработки структур и вычислительной

системы со множественным потоком команд и одиночным

потоком данных

5.2.1 Верификация модели системы

5.2.2 Отладка прототипа на макете

5.3 Экспериментальные исследования эффективности

вычислительной системы со множественным потоком команд и

одиночным потоком данных

5.3.1 Экспериментальное исследование временной сложности основных операций

5.3.2 Исследование производительности Процессора обработки структур на алгоритмах поиска минимального остовного дерева

5.3.3 Исследование производительности Процессора обработки структур на алгоритмах обхода графа

5.4 Выводы по главе

Заключение

Список сокращений и условных обозначений

Список литературы

Введение

Посвящается моей семье!

Актуальность темы исследования. Вычислительная техника в начале XXI века продолжает свое стремительное развитие, начавшееся с момента появления первых электронных вычислительных машин в 40-е годы XX века. Современные микропроцессорные СБИС достигают емкости в 109 вентилей и тактовой частоты до 7 ГГЦ при выпуске массовой продукции (опытные образцы достигают большей емкости и тактовой частоты). Технологии проектирования и изготовления таких узлов современных ЭВМ является особо ценной интеллектуальной собственностью крупных фирм производителей электронных компонентов, обеспечивающей им конкурентные преимущества на мировом рынке ИТ технологий. Такие крупные производители, как Intel, IBM, AMD, TI удерживают лидерство и диктуют, таким образом, архитектурные принципы построения вычислительных машин и систем на основе выпускаемых ими микропроцессорных комплектов.

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

Одним из перспективных способов повышения производительности ЭВМ является применение аппаратных ускорителей вычислений (акселераторов). Целью применения акселераторов является увеличение скорости обработки данных благодаря применению более производительных и параллельных аппаратных механизмов. Одновременная обработка данных позволяет снять часть вычислительной нагрузки с процессоров и перенести их на программное и аппаратное обеспечение ускорителей. В данной работе предпринята попытка создания

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

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

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

V/ р» V/

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

Введение диссертации (часть автореферата) на тему «Принципы организации и методология применения вычислительных систем со множественным потоком команд и одиночным потоком данных»

Цели работы:

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

- Разработка базового организационно-методического, программного и лингвистического обеспечения вычислительных систем данного класса.

- Исследование эффективности программных и аппаратных средств вычислительных систем со множественным потоком команд и одиночным потоком данных для решения задач оптимизации.

Задачи исследования:

- Исследование эффективности существующих средств вычислительной техники, подходов к ускорению вычислений и обработке больших объемов данных.

- Анализ современной элементной базы и выбор вариантов реализации устройств ускорения вычислений.

- Разработка моделей и принципов функционирования вычислительных систем с аппаратной поддержкой операций над множествами и структурами данных.

- Разработка принципов функционирования аппаратного устройства обработки множеств и структур данных: Процессора обработки структур.

- Определение архитектурных параметров системы со множественным потоком команд и одиночным потоком данных для решения задач различной размерности.

- Разработка моделей устройств, их верификация, разработка опытного образца вычислительной системы со множественным потоком команд и одиночным потоком данных (МКОД) на основе Процессора обработки структур.

- Разработка лингвистического обеспечения вычислительной системы МКОД для решения задач дискретной оптимизации.

- Создание методики и средств проектирования программ, функционирующих в вычислительной системе МКОД.

- Исследование эффективности и область применения вычислительной системы МКОД.

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

Научная новизна работы:

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

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

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

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

Разработана архитектура специализированного Процессор обработки структур, включающего ряд уникальных аппаратных устройств. Разработан набор команд Процессор обработки структур, выполняющего аппаратную обработку множеств и структур данных. Новизна устройства подтверждена патентом РФ на полезную модель. Разработаны параметризованные модели устройств: Каталога, Устройства загрузки команд, Операционного буфера, устройства микропрограммного управления, что позволило реализовать Процессор обработки структур и вычислительную систему со множественным потоком команд и одиночным потоком данных.

Реализован прототип вычислительной системы МКОД, язык ассемблера и средства компиляции программ МКОД системы, что позволило разработать лингвистическое обеспечение системы.

Разработаны алгоритмы оптимизации МКОД системы, для которых проведено тестирование и сравнение полученного решения с существующими универсальными вычислительными системами. Определены общие принципы применения МКОД систем для СУБД и систем обработки информации, геоинформационных и робототехниче-ских систем.

- Создана методика преобразования алгоритмов дискретной оптимизации, составляющая организационно-методическое обеспечение МКОД системы.

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

Положения, выносимые на защиту:

- Уточненная формальная модель вычислителя, выполняющего обработку структур данных.

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

- Принципы функционирования вычислительной системы с аппаратной поддержкой операций над множествами и структурами данных.

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

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

- Принципы аппаратной обработки структуры B+дерева в составе Процессора обработки структур, позволившие впервые реализовать устройства: Каталог, Операционный буфер и Устройство загрузки команд.

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

- Методика преобразования декомпозиции информационного графа программы для ЭВМ МКОД.

- Алгоритмы дискретной оптимизации на сетях и графах, оптимизированные для МКОД системы: алгоритмы Крускала, Прима, Форда-Фалкерсо-на, Дейкстры, алгоритмы обхода графа в ширину и глубину.

Практическая значимость работы. Наибольшую практическую значимость имеют следующие результаты работы:

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

- Действующий образец вычислительной системы со множественным потоком команд и одиночным потоком данных, методика модификации алгоритмов и методика преобразования декомпозиции информационного графа программы для ЭВМ МКОД, позволяющие разработать и реализовать параллельные варианты алгоритмов дискретной оптимизации.

- Транслятор ассемблера Процессора обработки структур.

- Действующие программы реализации алгоритмов Форда-Фалкерсона, Дейкстры, Крускала, Прима, и других алгоритмов для МКОД системы.

Апробация работы. Основные положения диссертационной работы обсуждены на второй международной научно-технической конференции, посвященной 95-летию со дня рождения академика В.Н.Челомея (г. Москва 2009), международной конференции ICACON 2015 (Будапешт, 2015), международной научной конференции Hawaii International Conference on System Science «HICSS50» (Гавайи, 2017), международной выставке «Армия 2017» (Москва, 2017), международной выставке «ChipExpo 2017» (Москва, 2017), международной конфренции IEEE MMET 2018 (Санкт-Петербург, 2018), международной конфренции IEEE EIConRus 2019 (Москва, 2019), международной конференции «Математические методы в технике и технологиях 2019 (Санкт-Петербург, 2019), международной конференции IEEE EIConRus 2020 (Москва, 2020).

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

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

стрированы в ходе проведения выставок, приведены автором в периодических изданиях и открыто демонстрируются на действующих образцах в Центре обработки данных МГТУ им. Н.Э.Баумана.

Реализация и внедрения. Теоретические и практические результаты работы, полученные автором, нашли применение при исследовании факторов активного долголетия в ФГБУ ФНКЦ ФХМ ФМБА России, при проведении научно-исследовательской деятельности АО «БАЙКАЛ ЭЛЕКТРОНИКС», в научно-исследовательской и коммерческой деятельности компании ООО «ИБС Софт», при реализации программно-технического комплекса по предотвращению угроз, реализуемом УИ-ВЦ МГТУ им. Н.Э. Баумана, в учебном процессе кафедры «Компьютерные системы и сети« МГТУ им. Н.Э.Баумана.

Публикации автора по теме диссертации. По результатам диссертационной работы автором опубликовано 17 работ, в том числе 12 работ в журналах, входящих в список научных журналов ВАК Минобрнауки России и патент Российской Федерации. Общий объем: 10.0 п.л.

Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, занимающих 394 страницы текста, в том числе 83 рисунков и 53 таблицы, список литературы из 132 наименований на 14 страницах.

Содержание работы. Во введении обоснована актуальность темы диссертации, сформулированы основные задачи и научные результаты, дано краткое содержание глав.

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

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

реализации функций обработки множеств и структур данных. Анализ элементной базы для реализации аппаратной обработки множеств и структур данных показал, что наиболее перспективными технологиями для вывода проекта на рынок является первичная реализация на ПЛИС и БМК с последующим переводом на ASIC/ASSP решения.

Рассмотренные в разделе 2.3 алгоритмы выполнения операций в B+дереве позволили выявить возможность повторения однотипных действий над различными уровнями дерева. Это показывает возможность разработки универсальных обрабатывающих устройств (Вершинных процессоров), которые будут заниматься поиском и модификацией структуры дерева на разных его уровнях.

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

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

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

В разделе 3.1 приведены основные функции Процессора обработки структур, определен и доказан принцип, согласно которому в вычислительной системе с аппаратной поддержкой операций над структурами один поток данных обрабатывается несколькими потоками команд. Анализ классификации Флинна позволил сформулировать принцип иерархической вложенности вычислитель-

ных систем различных классов, который впервые показывает один из возможных вариантов отношений всех четырех классов архитектур.

Анализ способов взаимодействия устройств и вариантов обмена информацией в МКОД системе, проведенный в разделе 3.2, позволил определить три режима работы: режим сопроцессора, режим МКОД и комбинированный режим. Показаны и выявлены достоинства и недостатки трех вариантов организации топологии МКОД системы: общей шины; независимых шин и иерархии шин.

В разделе 3.3 представлен состав, принципы взаимодействия и функциональное назначение блоков, входящих в СП. Согласно предложенным принципам, Процессор обработки структур данных подключён к локальным ЗУ, в которых хранятся структуры данных и команды. ЗУ команд представляет собой адресную память, в которой располагаются отдельные процедуры управления СП, составляющие поток команд обработки структурной информации. Доступ к содержимому адресного ЗУ структур выполняется с помощью уникальных ключей.

В разделе 3.4 представлены варианты реализации Каталога, Операционного буфера, и Устройства загрузки команд. Были определены 6 форматов команд процессора обработки структур и набор из 19 машинных команд высокого уров-

В разделе 3.4.5 рассмотрены вопросы организации управления блоками СП. Выполнена декомпозиция функций управления на четыре иерархических подчиненных уровня: центральное устройство управления, устройство управление уровнями дерева, управление Каталогом и управление Операционным буфером. Показано, что при реализации микропрограммных управляющих автоматов на ПЛИС типа FPGA возможности языковых средств и САПР существенно ограничены. В связи с этим в разделе 3.5 была разработана специальная технология микропрограммирования, направленная на ускоренное создание, модификацию и отладку таких устройств.

В разделе 3.6 рассмотрены вопросы построения вычислительных комплексов на основе гибридных устройств, включающих как узлы с Фон-Неймановской архитектурой, так и с МКОД архитектурой. Рассмотрены достоинства и недостатки возможных вариантов интеграции архитектуры МКОД в современные вычислительные комплексы: в виде ускорителей вычислений, в виде специальных блоков на одном кристалле с универсальным микропроцессором, а также в виде отдельного узла в кластерной вычислительной системе. Также

рассмотрены перспективы применения МКОД архитектуры в более далекой перспективе, в частности, при реализации масштабной концепции Интернета вещей, для аппаратной поддержки различных сервисов в рамках архитектуры SOA и для реализации функций в цепочках устройств в рамках направления Device democracy.

р» u w

В четвертой главе исследуются варианты реализации решений на основе новой архитектуры по наиболее перспективным направлениям: при построении аналитических систем, в системах хранения и обработки данных, в робототех-нических системах. Рассмотрены общие принципы организации программного обеспечения, учитывающего особенности архитектуры со множественным потоком команд и одиночным потоком данных. Показаны особенности функционирования гетерогенной вычислительной системы с различными наборами команд, принципы функционирование СП в режиме сопроцессора и режиме МКОД, а также показана необходимость раздельной компиляции кода СП и ЦП. На основе этого можно сделать вывод о необходимости создания специальной технологии разработки программного обеспечения в МКОД системе.

В разделе 4.1.4 предложена методика, позволяющая модифицировать существующие алгоритмы, представленные в парадигме исполнения одного потока команд над одиночным потоком данных, в алгоритмы со множественным потоком команд и одиночным потоком данных. Приведены примеры описания алгоритмов в параллельном псевдокоде и в виде информационного графа. На основе графового представления сформирована методика преобразования декомпозиции информационного графа программы для ЭВМ МКОД.

В разделе 4.3 проведены исследования реализации алгоритмов Форда-Фал-керсона, Дейкстры, алгоритмов обхода графов в ширину и глубину, а также алгоритмы Крускала и Прима. Исследования показали возможность решения задач на графах на основе параллельно и независимо работающих ЦП и СП в МКОД системе. На основе общей схемы алгоритма удалось получить модифицированную версию, представленную в базисных операциях над структурами данных, а также версию с двумя потоками команд и одиночным потоком данных. Также рассмотрены принципы реализации баз данных на основе МКОД системы (раздел 4.4.1). Показано, что планы выполнения SQL запросов могут использовать аппаратные команды СП, что приводит к большей параллельности обработки запросов в целом.

В разделе 4.4.2 приводится структура распределенной информационно-аналитической системы, в которой применение СП позволяет реализовать механизмы защиты данных на основе ролевой, мандатной или дискреционной моделей. В разделе 4.4.3 рассмотрен алгоритм построения графа видимости, используемый в робототехнических системах. Показана возможность реализации такого алгоритма на основе МКОД архитектуры. Вместе с этим выявлен сценарий, реализуемый неэффективно в существующей архитектуре МКОД: реализация динамически переупорядочиваемого множества на основе статических индексов. Предложен вариант реализации такого алгоритма при размещении структуры в локальной памяти ЦП. Вместе с этим предложен вариант модификации СП для поддержки подробного рода структур.

В пятой главе представлены результаты и последовательность схемно-топологического и конструкторского проектирования опытного образца МКОД системы. В разделе 5.1 приведено описание последовательности этапов проектирования, раскрывающее трудоемкость проведенных научно-исследовательских и опытно-конструкторских работ. В разделе 5.2 приводятся результаты комплекса процедур верификации модели Процессора обработки структур и опытного образца и представлен состав тестов. В разделе 5.3 приведены результаты экспериментальных исследований полученной МКОД системы с помощью специально разработанных программных тестов.

Глава 1. Определение предметной области и постановка задачи

1.1 История развития вычислительных систем обработки больших объемов

данных

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

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

Согласно ГОСТ 15971-90 [1], данные - это информация, представленная в виде, пригодном для обработки автоматическими средствами при возможном участии человека. В ряде случаев термины информация и данные используются как синонимы, если не оговаривается явно выраженного смыслового различия между этими понятиями. Например, в случае фильтрации входных данных и выявления пригодной для анализа ее части, можно говорить о получении

информации. Иными словами, термин информация может употребляться для определения результата преобразования и анализа данных.

Согласно [1], обработка информации, это систематическое выполнение операций над данными, представляющими предназначенную для обработки информацию. В некоторых случаях термин данные применяют, чтобы подчеркнуть

' С/ V/ и гр

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

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

Зарождение первых систем обработки данных началось в 50-е годы 20-го века, когда стали очевидны преимущества применения вычислительной техники, осознана роль информации при организации предприятий, хозяйственной и научной деятельности и военной сфере. В это время проекты по созданию вычислительных машин привели к формированию базовых принципов организации вычислительного процесса, сформулированные в документе, который назывался «Первый проект отчёта о EDVAC — отчет для Баллистической Лаборатории Армии США» и в работе «Предварительное рассмотрение логической конструкции электронно-вычислительного устройства» [2; 3], получившие название «Принципов Фон-Неймана». Вычислительные машины первого поколения строились преимущественно на базе электромагнитных реле и электронных ламп, и функциональность их ограничивалась выполнением основных арифметических команд (+,-,/,*) и построенных на их основе более

сложных действий. В работе [2] описаны также принципы реализации устройств для извлечения корня.

Первым примером успешной реализации системы обработки данных можно считать ЭВМ LEO I (сокращенно от английского Lyons Electronic Office I). Проект был реализован в 1947 году британской фирмой J. Lyons and Co., которая использовала его для расчёта цен, зарплаты сотрудников, учёта товаров [4]. В течении рабочего дня из магазинов розничной сети компании собирались заказы, которые использовались для расчёта требований количества продукции на следующий день. ЭВМ обеспечивала планирование поставок, обрабатывала счета и отчёты для руководителей магазинов.

ЭВМ LEO I применялась центром обработки звонков компании, поэтому должна была обладать способностью одновременной обработки нескольких потоков данных, идущих как на ввод, так и на вывод. Поэтому при ее создании было решено использовать несколько буферов ввода-вывода, которые были связаны со скоростными считывателями бумажной перфоленты, перфораторами и табулятором, печатающим 100 строк в минуту. В следующих поколениях были добавлены устройства для работы с магнитной лентой. Также потребовалось применить быстродействующую по тем временам память на ртутных линиях задержки (2K 35-битных слов). По архитектуре LEO I соответствовала классическим принципам Фон-Неймана. Первый опыт создания систем оперативной обработки данных показал:

- необходимость параллельного ввода и вывода в темпе, не меньшим скорости поступления информации и потребности в результатах обработки;

Список литературы диссертационного исследования доктор наук Попов Алексей Юрьевич, 2021 год

Список литературы

1. ГОСТ 15971-90. Системы обработки информации. Термины и определения; Введ. 1992-01-01. М : Изд-во стандартов, 1991. С. 12.

2. Neumann, J. von. First Draft of a Report on the EDVAC / J. von Neumann // Report / ed. by N. B. Stern. Digital Press, 1981. P. 27—76.

3. Burks, A. W. Preliminary Discussion of the Logical Design of an Electronic Computing Instrument : tech. rep. / A. W. Burks, H. H. Goldstine, J. von Neumann ; Institute for Advanced Study. Princeton, New Jersey, 06/1946. P. 97-142.

4. Powell, P. LEO: The First Business Computer: Hasler Publishing, Wokingham (1994) 272 pp ISBN 0 9521651 0 4. / P. Powell // J. Strategic Inf. Sys. 1995. Vol. 4, no. 2. P. 201—202.

5. Ceruzzi, P. E. A History of Modern Computing (2. ed.). / P. E. Ceruzzi. MIT Press, 2003. P. I-XI, 1-445.

6. Architecture of the PSC: A Programmable Systolic Chip / A. L. Fisher [et al.] // ISCA / ed. by H. W. L. Jr. [et al.]. ACM, 1983. P. 48-53.

7. Graham, I. S. The transputer handbook. / I. S. Graham, T. King. Prentice Hall, 1990. P. I-XI, 1-200.

8. Fast track to the future. The 2012 IBM Tech Trends Report : tech. rep. 2012. P. 12.

9. Цилькер, Б. Я. Организация ЭВМ и систем : Учебник для вузов / Б.Я. Цилькер, С.А. Орлов. - 2-е изд. / Б. Я. Цилькер. СПб. : Питер, 2011. С. 688.

10. A digital neurosynaptic core using embedded crossbar memory with 45pJ per spike in 45nm. / P. Merolla [et al.] // CICC / ed. by R. Patel, T. Andre, A. Khan. IEEE, 2011. P. 1—4.

11. StatSoft. Революция Big Data: Как извлечь необходимую информацию из Больших Данных? / StatSoft. URL: http://www.statsoft.ru/products/ Enterprise/big-data.php (дата обр. 27.02.2020).

12. FPGA-based hardware acceleration for Boolean satisfiability. / K. Gulati [et al.] // ACM Trans. Design Autom. Electr. Syst. 2009. Apr. 14. Vol. 14, no. 2. 33:1-33:11.

13. Mandlem, A. R. FPGA Based Hardware Acceleration: A Case Study in Protein Identification : tech. rep. / A. R. Mandlem ; Division of Engineering at Brown University. 04/2008. P. 50.

14. Accelerating High-Performance Computing With FPGAs // White Paper / Altera Corporation. WP-01029-1.1 : tech. rep. 10/2007. P. 8.

15. Understanding Big Data - Analytics for Enterprise Class Hadoop and Streaming Data / P. C. Zikopoulos [et al.]. 2012. P. 4.

16. Loshin, D. Big Data Analytics: From Strategic Planning to Enterprise Integration with Tools, Techniques, NoSQL, and Graph / D. Loshin. Amsterdam : Morgan Kaufmann, 2013. P. 208.

17. Kumar, S. A thesis on acceleration of network processing algorithm : PhD thesis / Kumar S. Department of Computer Science, Engineering : Washington University, 05/2008. P. 180.

18. Coole, J. A Traversal Cache Framework for FPGA Acceleration of Pointer Data Structures: A Case Study on Barnes-Hut N-body Simulation. / J. Coole, J. R. Wernsing, G. Stitt // ReConFig / ed. by V. K. Prasanna, L. Torres, R. Cumplido. IEEE Computer Society, 2009. P. 143—148.

19. A quantitative analysis of the speedup factors of FPGAs over processors. / Z. Guo [et al.] // FPGA / ed. by R. Tessier, H. Schmit. ACM, 02/13/2006. P. 162-170.

20. Characterization of Fixed and Reconfigurable Multi-Core Devices for Application Acceleration. / J. Williams [et al.] // TRETS. 2010. Vol. 3, no. 4. P. 19.

21. Уваров, С. С. Проектирование реконфигурируемых отказоустойчивых систем на ПЛИС с резервированием на уровне ячеек : дис. ... канд. / Уваров Сергей Сергеевич. Москва, 2007. С. 164.

22. Костин, А. Е. Организация и обработка структур данных в вычислительных системах / А. Е. Костин, В. Ф. Шаньгин. М. : Высшая школа, 1987. С. 248.

23. Овчинников, В. А. Исследование вычислительной сложности алгоритмов двоичной свертки схем ЭВМ / В. А. Овчинников, К. В. Николаев, А. Ю. Попов // Вестник МГТУ им. Н.Э.Баумана. Сер. Приборостроение. 1997. №2. С. 113-120.

24. Овчинников, В. А. Применение метода ветвей и границ для решения задачи дихотомического разрезания гиперграфа / В. А. Овчинников, Г. С. Иванова, А. Ю. Попов // Вестник МГТУ им. Н.Э.Баумана. Сер. Приборостроение. 1999. № 2. С. 78-91.

25. Introduction to Algorithms / T. H. Cormen [et al.]. MIT Press, 2001. P. 960.

26. Попов, А. Ю. Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ : дис. ... канд. / Попов Алексей Юрьевич. Москва, 2003. С. 176.

27. Электронная вычислительная машина с многими потоками команд и одним потоком данных [Текст] : пат. 71016 Рос. Федерация : МПК7 G 06 F 15/16 / А. Ю. Попов. № 2006115810 ; заявл. 06.05.2006 ; опубл. 20.02.2008, Бюл. № 5. 1 с.: ил.

28. Методы ситуационного анализа и графической визуализации потоков больших данных / А. Пролетарский [и др.] // Вестник МГТУ им. Н.Э.Баумана. Сер. Приборостроение. 2018. 2(119). С. 98-103.

29. Литвак, Э. С. Модуль обработки информации с навигационной системой лазерного дальномера / Э. С. Литвак, А. Ю. Попов, А. Д. Левкович // Вестник Московского государственного университета леса. М., 2012. Т. 89, № 6. С. 145-149.

30. Popov, A. An Introduction to the MISD Technology / A. Popov // HICSS50. Proceedings of the 50th Hawaii International Conference on System Sciences, 2017. P. 1003-1012.

31. Хорошевский, B. Г. Архитектура вычислительных систел.: Учеб. пособие. 2-e изд., перераб. и доп. / B. Г. Хорошевский. Москва : Изд-во МГТУ им. Н.Э. Баумана, 2008. С. 520.

32. Попов, А. Ю. Применение гетерогенной вычислительной системы с набором команд дискретной математики для решения задач на графах / А. Ю. Попов // Информационные технологии. 2019. Т. 25, № 11. С. 682-690.

33. Decision Support System to Prevent Crisis Situations in the Socio-political Sphere / A. Proletarsky [et al.] // Cyber-Physical Systems: Industry 4.0 Challenges. Studies in Systems, Decision and Control. Vol. 260 / ed. by

A. G. Kravets, A. A. Bolshakov, M. V. Shcherbakov. Springer International Publishing, 2019. P. 301-314.

34. Integrated Cryptographic and Compression Accelerators on Intel Architecture Platforms. Intel Corporation, 2013. P. 5.

35. The SIMD accelerator for business analytics on the IBM z13 / E. Schwarz [et al.] // IBM J. Res. Dev. 2015. Vol. 59. 2:1-2:16.

36. SQRL: Hardware Accelerator for Collecting Software Data Structures / S. Kumar [et al.] // Proceedings of the 23rd International Conference on Parallel Architectures and Compilation. Edmonton, AB, Canada : ACM, 2014. P. 475-476. (PACT '14).

37. Carvalho, C. The Gap between Processor and Memory Speeds / C. Carvalho // 3rd Internal Conference on Computer Architecture (ICCA). 2002. P. 27—34.

38. RAP.2 - An Associative Processor for Databases and Its Applications / S. A. Schuster [et al.] // IEEE Transactions on Computers. 1979. Vol. C—28. P. 446-458.

39. Singh, M. Introduction to the IBM Netezza warehouse appliance. / M. Singh,

B. Leonhardi // CASCON / ed. by J. W. Ng [et al.]. IBM / ACM, 2011. P. 385-386.

40. IBM Netezza 1000. High-performance business intelligence and advanced analytics for the enterprise. IBM Corporation. Software Group., 2011. P. 35.

41. Bordawekar, R. Analyzing Analytics / R. Bordawekar, B. Blainey, R. Puri. Morgan & Claypool Publishers, 2015. P. 9.

42. DB2 with BLU Acceleration: So Much More than Just a Column Store. / V. Raman [et al.] // PVLDB. 2013. Vol. 6, no. 11. P. 1080-1091.

43. DB2 10.5 with BLU Acceleration - New Dynamic In-Memory Analytics for the Era of Big Data / P. Zikopoulos [et al.]. McGraw-Hill Osborne Media, 2013. P. 35-78.

44. Выходцев, А. Технологии и Архитектура Netezza / А. Выходцев. URL: https://www.ibm.com/ru/events/presentations/storage2012/bigdata.pdf; (дата обр. 27.02.2020).

45. Выходцев, А. Платформа для Больших Данных / А. Выходцев // Открытые системы. СУБД. 2013. № 9. URL: http://www.osp.ru/os/2012/06/13017013 (дата обр. 27.02.2020).

46. Линев, А. В. Технологии параллельного программирования для процессоров новых архитектур / А. В. Линев, Д. К. Боголепов, С. И. Бастраков ; под ред. В. Гергеля. М. : Издательство Московского университета, 2010. С. 160.

47. Сандерс, Д. Технология CUDA в примерах / Д. Сандерс, Э. Кэндрот. М. : Изд-во 'ДМК', 2011. С. 313.

48. Калачев, А. В. Многоядерные процессоры : учебное пособие / А. В. Кала-чев. Москва : Интернет-университет информационных технологий, 2010. С. 247.

49. Performance evaluation of sparse matrix-vector product (SpMV) computation on GPU architecture / N. Kasmi [et al.] // Second World Conference on Complex Systems (WCCS). Agadir, 2014. P. 23-27.

50. Vasilyev, N. P. Software platform VAR for heterogeneous GPGPU-systems / N. P. Vasilyev, M. M. Rovnyagin // 2016 6th International Conference - Cloud System and Big Data Engineering (Confluence). 2016. С. 624—629.

51. Sitaridi, E. A. Hardware Acceleration of Database Analytics / E. A. Sitaridi // 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 2017. P. 1616-1616.

52. Heterogeneous System Architecture. Wikipedia. URL: http://en.wikipedia.org/ wiki/Heterogeneous_System_Architecture (дата обр. 27.02.2020).

53. Палташев, Т. Гетерогенная архитектура для CPU, GPU и DSP / Т. Пал-ташев, И. Перминов // Открытые системы. СУБД. 2013. № 8. URL: http: //www.osp.ru/os/2013/08/13037850 (дата обр. 27.02.2020).

54. Krikelis, A. Associative Processing and Processors / A. Krikelis, C. Weems. London : IEEE Computer Society Press, 1997. P. 480.

55. Yavits, L. Computer Architecture with Associative Processor Replacing Last-Level Cache and SIMD Accelerator / L. Yavits, A. Morad, R. Ginosar // IEEE Transactions on Computers. 2015. Vol. 64. P. 368—381.

56. Kankowski, P. x86 Machine Code Statistics / P. Kankowski. 2009. URL: http: //www.strchr.com/x86_machine_code_statistics (дата обр. 27.02.2020).

57. Huang, I. J. Analysis of x86 instruction set usage for DOS/Windows applications and its implication on superscalar design /1. J. Huang, T. C. Peng // IEICE Transactions on Information and Systems. 2002. Vol. E85—D, no. 6. P. 929-939.

58. Associative Co-processor on the Basis of Programmable Logical Integrated Circuits for Special Purpose Computer Systems / A. I. Martyshkin [et al.] // 2018 Global Smart Industry Conference (GloSIC). 2018. P. 1-5.

59. Hsiue, K. D. FPGA-based hardware acceleration for a key-value store database : Master's thesis / Hsiue Kevin D. Massachusetts Institute of Technology, USA, 2014. P. 1-90.

60. ASF: AMD64 Extension for Lock-Free Data Structures and Transactional Memory / J.-W. Chung [et al.] // 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture. 2010. P. 39—50.

61. The irregular Z-buffer: Hardware acceleration for irregular data structures / G. Johnson [et al.] // ACM Trans. Graph. 2005. Vol. 24. P. 1462—1482.

62. Non-Boolean Associative Processing: Circuits, System Architecture, and Algorithms / Y. Fang [et al.] // IEEE Journal on Exploratory Solid-State Computational Devices and Circuits. 2015. Vol. 1. P. 94—102.

63. Knuth, D. E. Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition) / D. E. Knuth. Addison-Wesley Professional, 04/1998. P. 824.

64. GraphStep: A System Architecture for Sparse-Graph Algorithms / M. De-Lorimier [et al.] // 2006 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. 2006. P. 143—151.

65. Novel graph processor architecture, prototype system, and results / W. S. Song [et al.] // 2016 IEEE High Performance Extreme Computing Conference (HPEC). 2016. P. 1-7.

66. Patel, R. Visualizing the effect of dependency in superscalar pipelining / R. Patel, S. Kumar // 4th International Conference on Information Technology (RAIT). Dhanbad, 2018. P. 1-5.

67. Patel, G. R. The Effect of Dependency on Scalar Pipeline Architecture / G. R. Patel, S. Kumar // IUP Journal of Computer Sciences. 2017. Т. 11, № 1. С. 38-50.

68. Harish, P. Accelerating Large Graph Algorithms on the GPU Using CUDA / P. Harish, P. J. Narayanan // High Performance Computing - HiPC 2007. Lecture Notes in Computer Science. Vol. 4873 / ed. by S. Aluru [et al.]. Berlin, Heidelberg : Springer, 2007. P. 197—208.

69. Operation (mathematics). Wikipedia. URL: http: / / en. wikipedia. org / wiki / Operation_(mathematics) (дата обр. 27.02.2020).

70. Gutmann, P. Cryptographic Security Architecture. Design and Verification / P. Gutmann. Springer, 2004. P. 320.

71. ASF: AMD64 Extension for Lock-Free Data Structures and Transactional Memory. / J.-W. Chung [et al.] // MICRO. IEEE Computer Society, 2010. P. 39-50.

72. The irregular Z-buffer: Hardware acceleration for irregular data structures. / G. S. Johnson [et al.] // ACM Trans. Graph. 2006. Apr. 3. Vol. 24, no. 4. P. 1462-1482.

73. Hu, J. Solution of partial differential equations using reconfigurable computing. : PhD thesis / Hu Jing. British Library, EThOS, University of Birmingham, UK, 2011. P. 12.

74. Palmer, S. Accelerating Implicit Finite Difference Schemes Using a Hardware Optimised Implementation of the Thomas Algorithm for FPGAs : тех. отч. / S. Palmer, D. Thomas. 02.2014. С. 8. URL: http://adsabs.harvard.edu/abs/ 2014arXiv1402.5094P (дата обр. 27.02.2020).

75. Carrion, B. S. Acceleration of the Discrete Element Method (DEM) on a reconfigurable co-processor / B. S. Carrion, A. H. C. Chan, S. F. Quigley // Computers and Structures Journal. 2004. Vol. 82, no. 20/21. P. 1707—1718.

76. Sethumadhavan, S. A Case for Hybrid Discrete-Continuous Architectures. / S. Sethumadhavan, R. Roberts, Y. P. Tsividis // Computer Architecture Letters. 2012. Vol. 11, no. 1. P. 1-4.

77. Skiena, S. S. The Algorithm Design Manual / S. S. Skiena. 2nd. Springer, 08/2008. P. 800.

78. Caprara, A. Algorithms for the Set Covering Problem. / A. Caprara, P. Toth, M. Fischetti // Annals OR. 2000. Vol. 98, no. 1—4. P. 353—371.

79. Algorithms for railway crew management. / A. Caprara [et al.] // Math. Program. 1997. Vol. 79. P. 125—141.

80. Chen, J. Vertex cover: further observations and further improvements : tech. rep. / J. Chen, I. Kanj, W. Jia. 2001. P. 19.

81. Попов, А. Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных / А. Ю. Попов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 9. С. 162-180.

82. Pinedo, M. Scheduling : theory, algorithms, and systems / M. Pinedo. Prentice-Hall, Englewood Cliffs, 1995. P. 676.

83. West, D. B. Coloring of Graphs / D. B. West // Introduction to Graph Theory. Second. Pearson, 2000. Chap. 5. P. 191—232.

84. Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems. / Z.-Y. Wu [et al.] // J. Optimization Theory and Applications. 2011. Vol. 151, no. 2. P. 241-259.

85. Сигал, И. Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: 2-е изд., испр. и доп. / И. Х. Сигал, А. П. Иванова. М. : ФИЗМАТЛИТ, 2007. С. 304.

86. Ahuja, R. K. Network flows - theory, algorithms and applications. / R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Prentice Hall, 1993. P. I—XV, 1-846.

87. Aho, A. V. The Design and Analysis of Computer Algorithms. / A. V. Aho, J. E. Hopcroft, J. D. Ullman. Addison-Wesley, 01/03/2002. P. 480.

88. Schrijver, A. Combinatorial Optimization - Polyhedra and Efficiency / A. Schrijver. Springer, 2003. P. 1879.

89. Овчинников, В. А. Графы в задачах анализа и синтеза структур сложных систем / В. А. Овчинников. М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. С. 423.

90. Новиков, Ф. А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. / Ф. А. Новиков. СПб. : Питер, 2009. С. 384.

91. Иванова, Г. С. Оптимизирующие преобразования алгоритмов, использующие свойства множеств, предикатов и операций над ними / Г. С. Иванова, В. А. Овчинников // Вестник МГТУ им. Н.Э. Баумана. Сер. 'Приборостроение'. 2013. № 4. С. 53—66.

92. Knuth, D. E. The art of computer programming, Volume II: Seminumerical Algorithms, 3rd Edition. / D. E. Knuth. Addison-Wesley, 1998. P. I—XIII, 1-762.

93. Crespo, A. Dynamic Memory Management for Embedded Real-Time Systems. / A. Crespo, I. Ripoll, M. Masmano // DIPES, IFIP. Vol. 225 / ed. by B. Kleinjohann [et al.]. Springer, 07/04/2007. P. 195—204.

94. Leis, V. The adaptive radix tree: ARTful indexing for main-memory databases / V. Leis, A. Kemper, T. Neumann // 2013 IEEE 29th International Conference on Data Engineering (ICDE). 2013. P. 38—49.

95. Попов, А. Ю. Принципы организации гетерогенной вычислительной системы с набором команд дискретной математики / А. Ю. Попов // Информационные технологии. 2020. Т. 26, № 2. С. 67—79.

96. Угрюмов, Е. П. Цифровая схемотехника : Учеб. пособие для вузов. 2-е изд., перераб. и доп. / Е. П. Угрюмов. СПб. : БХВ-Петербург, 2004. С. 800.

97. Грушвицкий, Р. И. Проектирование систем на микросхемах с программируемой структурой / Р. И. Грушвицкий, А. Х. Мурсаев, Е. П. Угрюмов. СПб. : БХВ-Петербург, 2006. С. 708.

98. Пазников, А. А. Алгоритмы организации функционирования мультикла-стерных вычислительных систем с иерархической структурой : дис. . . . канд. / Пазников Алексей Александрович. Новосибирск, 2013. С. 146.

99. Virtex-7 T and XT FPGAs Data Sheet: DC and AC Switching Characteristics. Product Specification. DS183 (v1.21). URL: http://www.xilinx.com/support/ documentation/ data_ sheets / ds183 _ Virtex _ 7 _ Data_ Sheet. pdf (дата обр. 27.02.2020).

100. Xilinx 7 Series FPGAs Overview. Product Specification. DS180 (v1.16.1). URL: http: //www. xilinx. com/support/documentation/data_sheets/ds180_ 7Series_Overview.pdf (дата обр. 27.02.2020).

101. Li, J. Alternative Approach to Solving Computer Vision Tasks Using Graph Structures / J. Li, M. Makarychev, A. Popov // Cyber-Physical Systems: Industry 4.0 Challenges. Studies in Systems, Decision and Control. Vol. 260 / ed. by A. G. Kravets, A. A. Bolshakov, M. V. Shcherbakov. Springer International Publishing, 2020. P. 63-78.

102. Stratix V Device Handbook. Volume 1: Device Interfaces and Intégration. Product Specification. SV5V1. URL: http://www.altera.com/literature/hb/ stratix-v/stx5_core.pdf (дата обр. 27.02.2020).

103. Попов, А. Ю. Электронная вычислительная машина с аппаратной поддержкой операций над структурами данных / А. Ю. Попов // Аэрокосмические технологии : Тр. Второй Междунар. научно-техн. конф., посвященной 95-летию со дня рождения академика В.Н. Челомея (2009). Т. 1. ОАО ВПК 'НПО машиностроения'. МГТУ им. Н.Э. Баумана, 2012. С. 296-301.

104. Бортовое устройство контроля параметров движения транспортного средства при дорожно-транспортном происшествии [Текст] : пат. 113230 Рос. Федерация : МПК7 B 62 D 41/00, G 07 C 5/08 / В. А. Солда-тенков [и др.] ; заявитель и патентообладатель Открытое акционерное общество НПО 'Геофизика-НВ'. № 2011141679 ; заявл. 14.10.2011 ; опубл. 27.04.2013, Бюл. № 6. 1 с.: ил.

105. Попов, А. Ю. Реализация электронной вычислительной машины с аппаратной поддержкой операций над структурами данных / А. Ю. Попов // Вестник МГТУ им. Н.Э.Баумана. Сер. Приборостроение. Спец. вып. Информационные технологии и компьютерные системы. 2011. С. 83—87.

106. Попов, А. Ю. Применение вычислительных систем с многими потоками команд и одним потоком данных для решения задач оптимизации / А. Ю. Попов // Инженерный журнал: наука и инновации (электронное издание). 2012. № 1. С. 146—154. URL: http://engjournal.ru/catalog/it/hidden/ 80.html (дата обр. 27.02.2020).

107. Попов, А. Ю. Исследование производительности процессора обработки структур в системе с многими потоками команд и одним потоком данных / А. Ю. Попов // Инженерный журнал: наука и инновации. 2013. № 11.

С. 1—14. URL: http://engjournal.ru/catalog/it/hidden/1048.html (дата обр. 27.02.2020).

108. Flynn, M. J. Very High-Speed Computing Systems / M. J. Flynn // Proceedings of the IEEE. 1966. Dec. Vol. 54, no. 12. P. 1901—1909.

109. Boundary addressable memory, US Patent 6,721,842 / A. E. Henderson, W. E. Croft. 04/2004.

110. Content limit addressable memory, US Patent 5,561,429 / J. E. Meister [et al.]. 10/1996.

111. Device democracy. Saving the future of the Internet of Things / IBM Global Business Services Executive Report : tech. rep. / IBM Institute for Business Value. 2014. P. 28.

112. Sorokin, A. Automation Beyond Web 2.0 / A. Sorokin // RAN Journal of Informatics And Applications. 2014. Vol. 8, no. 4. P. 114—125.

113. Fast Prototyping of the Internet of Things solutions with IBM Bluemix / A. Popov [et al.] // HICSS50. Proceedings of the 50th Hawaii International Conference on System Sciences, 2017. P. 1064—1072.

114. Popov, A. loud Based IT Learning Infrastructure to Support New Generation of Services / A. Popov, S. Belov, A. Sorokin //. 2018. Vol. 9, no. 6. P. 281-286.

115. Пакет программ для демонстрации работоспособности, автоматизации процедур настройки и контроля системы позиционирования / Р. А. Била-лов [и др.] // Вестник Московского государственного университета леса. 2009. № 6. С. 9—13.

116. Литвак, Э. Система на кристалле и алгоритм определения координат объекта в оптико-электронном устройстве наблюдения / Э. Литвак, А. Лев-кович, А. Ю. Попов // Вопросы оборонной техники. М., 2012. Т. 9, № 258. С. 120—124.

117. Попов, А. Ю. Реализация алгоритмов обхода графов в вычислительной системе с многими потоками команд и одним потоком данных / А. Ю. Попов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 10. С. 453—472.

118. Попов, А. Ю. Исследование вариантов реализации алгоритмов Крускала и Прима в вычислительной системе с многими потоками команд и одним потоком данных / А. Ю. Попов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 11. С. 505—527.

119. Подольский, В. Э. Методика декомпозиции информационного графа программы для организации параллельной обработки данных на ЭВМ МКОД / В. Э. Подольский, А. Ю. Попов // Вестник МГТУ им. Н.Э.Баумана. Сер. Приборостроение. 2016. 1(106). С. 112—128.

120. Стратегии оптимизации производительности СУБД MYSQL, применяемой в экологических исследованиях / В. В. Кожушко [и др.] // Известия Юго-Западного Государственного Университета. Серия: Управление, вычислительная техника, информатика. 2016. № 3. С. 84—95.

121. Подольский, В. Э. Об организации параллельной работы некоторых алгоритмов поиска кратчайшего пути на графе в вычислительной системе с многими потоками команд и одним потоком данных / В. Э. Подольский // Наука и Образование. Электронный журнал. 2015. № 4. С. 189—214.

122. Овчинников, В. А. Методика формального синтеза комбинированных структур данных для представления графов / В. А. Овчинников, Г. С. Иванова // Вестник МГТУ им.Н.Э.Баумана. Серия "Приборостроение". Спец.выпуск "Компьютерные системы и технологии". 2012. № 4. С. 135—145.

123. Knuth, D. E. The art of computer programming : 1. Fundamental algorithms : Donald E. Knuth / D. E. Knuth. 3. ed., 1. printing. Upper Saddle River, NJ [u.a.] : Addison-Wesley, 1997. P. 720.

124. Подольский, В. Э. Аппаратное ускорение выполнения SQL-запросов в MDM-системах на основе МКОД-решения / В. Э. Подольский, А. В. Са-мочадин, С. С. Колосков // Наука и Образование. Электронный журнал. 2015. № 12. С. 165—196.

125. Rasheed, B. Network Graph Datastore Using DISC Processor / B. Rasheed, A. Y. Popov // 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). 01/2019. P. 1582—1587.

126. McLellan, C. M2M and the Internet of Things: A guide / C. McLellan. URL: http: / / www. zdnet. com / article / m2m - and - the - internet - of - things - a - guide (дата обр. 27.02.2020).

127. System Administration Guide: Security Services. Official Guide. Oracle Corporation. Part No: 816-4557-19.Tech. rep. 2010. P. 718.

128. Principles of Robot Motion Theory, Algorithms, and Implementation / H. Choset [et al.]. London : The MIT Press, 2005. P. 616.

129. Davenport, J. H. A 'Piano Movers' Problem. / J. H. Davenport // ACM SIGSAM Bulletin. 1986. Vol. 20, no. 1/2. P. 15—17.

130. Abdymanapov, C. Motion Planning Algorithms Using DISC / C. Abdy-manapov, A. Popov // 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). 01/2019. P. 1844—1847.

131. Яковлев, К. С. Графовые модели в задаче планирования траектории на плоскости / К. С. Яковлев, Е. С. Баскин // Искусственный интеллект и принятие решений. 2013. № 1. С. 5—12.

132. Burgess, I. Regression Testing: Gate-Level Functional Verification Is Imperative and Equivalence Checking Provides the Solution. White Paper : tech. rep. /1. Burgess. 2004. P. 8.