Методы и средства создания параллельно-конвейерных программ для решения графовых NP-полных задач на реконфигурируемых вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Касаркин Алексей Викторович

• Касаркин Алексей Викторович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Касаркин Алексей Викторович

ВЕДЕНИЕ

1. МЕТОДЫ И СРЕДСТВА РЕШЕНИЯ ГРАФОВЫХ №-ПОЛНЫХ ЗАДАЧ

1.1 Задачи теории графов

1.2 Многопроцессорные вычислительные системы, используемые для решения графовых задач

1.3 Реконфигурируемые вычислительные системы

1.4. Языки программирования реконфигурируемых вычислительных систем

1.5. Принципы решения графовых №-полных задач на реконфигурируемых вычислительных системах

1.6 Выводы

2. БАЗОВЫЕ МАКРООПЕРАЦИИ ТЕОРИИ МНОЖЕСТВ

2.1 Обобщение операций добавления и удаления элемента из множества

2.2 Операция объединения множеств

2.3 Операция разность множеств

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

2.5 Выводы

3. РЕШЕНИЕ ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ КЛИК ГРАФА МЕТОДОМ РАСПАРАЛЛЕЛИВАНИЯ ПО СЛОЯМ

3.1 Сравнение алгоритмов

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

3.3 Реализация задачи поиска максимальных клик графа на РВС методом распараллеливания по слоям

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

3.5 Выводы

4. РЕШЕНИЕ ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ КЛИК ГРАФА ИТЕРАЦИОННЫМИ МЕТОДАМИ

4.1. Предел роста производительности метода распараллеливания по слоям

4.2. Метод распараллеливания по итерациям

4.3. Реализация алгоритма задачи поиска максимальных клик графа на РВС итерационными методами

4.4. Модернизации метода распараллеливания по итерациям графовых ЫР-полных задач

4.5. Экспериментальные исследования метода распараллеливания по итерациям

4.6. Методика выбора эффективного варианта распараллеливания

4.7. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1. Макрооперации теории множеств

П.1.1. Операция определения принадлежности потока элементов множеству

П.1.2. Операция добавления элемента в множество

П.1.3. Операция удаления элемента из множества

П.1.4. Операция пересечение множеств

П.1.5. Операция симметрическая разность множеств

ПРИЛОЖЕНИЕ 2. Теоретическая оценка времени решения задачи поиска

максимальных клик графа на современном процессоре

ПРИЛОЖЕНИЕ 3. Подготовка начальных данных для алгоритма Брона-

Кербоша на основе упорядочивания по вырождению

ПРИЛОЖЕНИЕ 4. Расчет предела роста производительности метода

распараллеливания по слоям

ПРИЛОЖЕНИЕ 5. Акты о внедрении и использовании результатов диссертации

ВЕДЕНИЕ

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

Актуальность темы.

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

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

Одной из групп графовых задач являются задачи, связанные с обработкой социальных графов. Данная группа включает такие задачи, как: идентификация пользователей; поиск профилей человека в разных социальных сетях; поиск социальных объектов с помощью анализа набора связей между объектами; генерация рекомендаций, которая активно применяется в маркетинге; создание графа интересов, который используется, например, в задаче выявления «настоящих» связей межу пользователями, друзьями, родственниками, такая задача является одной из основных в подходе «разведка на основе открытых источников» (OSINT).

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

В схемотехнике топология межсоединений элементов на печатной плате или микросхеме представляет собой граф. Различные проектные и оптимизационные задачи при определении расположения схемотехнических элементов и связей между ними являются графовыми задачами. Современные ПЛИС и СБИС содержат миллионы логических элементов, поэтому при проектировании для размещения элементов и трассировки связей применяется соответствующий кристаллу САПР, а разработчику достаточно задать функциональное описание схемы на языке описания аппаратуры (HDL). В процессе работы САПР приходится решать NP-полные задачи, например, такие, как раскраска графа, поиск клик в графе. Это приводит к тому, что процесс размещения элементов и трассировки связей может длиться сутками, что значительно увеличивает время разработки, так как маршрут проектирования ПЛИС и СБИС предполагает многократную модификацию функционального описания с повторным размещением элементов и трассировкой связей.

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

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

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

Актуальность графовых задач подтверждается тем, что для оценки производительности суперкомпьютеров на графовых задачах был даже создан рейтинговый список Graph500, в качестве вычислительного ядра реализации которого используется тест «поиск в ширину» в графе. Рейтинг суперкомпьютеров Graph500 публикуется два раза в год, а места в списке распределяются с учетом размера графа и полученной производительности суперкомпьютера при его обработке (единица измерения — TEPS, то есть количество пройденных дуг в секунду). Бенчмарк, используемый при составлении Graph500, в отличие от бенчмарка списка Top500, в большей степени нагружает коммуникационную подсистему компьютера и не зависит от количества исполняемых в секунду операций над числами с плавающей запятой. Таким образом, списки отличаются, например, первое место в Graph500 занимает суперкомпьютер Sunway TaihuLight, а в Top500 он находится на третьем месте, и наоборот: первое место в Top500 у суперкомпьютера Summit, а в Graph500 он занимает четвертое место.

Решение многих практических графовых задач сводится к решению типовых NP-полных задач. Данные переборные задачи являются наиболее

трудновычислимыми, так как в настоящее время ни одна из них не может быть решена за полиномиальное время. Многие такие задачи вынужденно приходится решать приближенными алгоритмами, так как точное решение может быть сравнимо с временем жизни вселенной. Например, в Институте проблем передачи информации имени А.А. Харкевича РАН для решения задач медицины, фармакологии используют модели функционирования клетки, которая включает в себя и NP-полные задачи, например, такую как поиск клик в многодольном графе. Это приводит к тому, что результат каждого моделирования приходится ждать сутками, несмотря на то что оно выполняется на суперкомпьютере МВС-100К (10572 процессорных ядер, 152 GPU).

При решении NP-полных задач на многопроцессорных системах возникает ряд проблем, связанных с их масштабируемостью, которые приводят к тому, что при превышении определенного числа используемых вычислительных ядер рост производительности останавливается. В ряде исследований показано, что при решении NP-полной задачи выполнимости булевых формул увеличение числа потоков в процессоре семейства Intel Xeon Phi (до 72 ядер в одном кристалле) в некоторых случаях замедляет решение, а при попытке решить ту же задачу на графическом ускорителе NVIDIA GeForce GTX 1070 демонстрируют не очень качественную масштабируемость (всего двукратный прирост производительности при использовании 60 потоков). Это связано с тем, что NP-полные задачи в значительной степени нагружают коммутационные структуры, это приводит к тому, что при превышении некоторого числа потоков затраты на организацию межпроцессорного обмена начинают превышать затраты на собственно вычисления, а транзакционная организация вычислений не позволяет начать выполнять новую операцию, пока процессор не завершит предыдущую операцию.

Одним из вариантов решения проблемы распараллеливания может стать использование специализированных устройств или проблемно-ориентированных процессоров на основе заказных кристаллов (Application Specific Integrated Circuit, ASIC), однако длительное время и высокая цена разработки заказных схем

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

Трудности при решении рассмотренных графовых задач могут быть преодолены при использовании программируемых логических интегральных схем (ПЛИС типа FPGA), которые обеспечивают возможность структурной реализации вычислений за счет обеспечения эффективного обмена данными между вычислительными узлами и адаптации вычислительного поля под структуру задачи. Существуют РВС различных производителей, например, таких как Nallatech, Pico Computing, Convey, Maxeler Technologies, SRC Computers, Berkeley Wireless Research Center. Однако недостатками РВС перечисленных производителей является то, что их системы содержат небольшое число ПЛИС: от одной до четырех, что не позволит существенно ускорить вычислительноёмкие графовые NP-полные задачи. Одними из наиболее производительных РВС являются системы, произведенные НИЦ СЭ и НК. Такие системы объединяют сотни ПЛИС в единое вычислительное поле, в котором ПЛИС являются основным элементом вычислений, а не сопроцессором. Такая организация потенциально позволяет эффективно масштабировать графовые NP-полные задачи, предоставляя возможность размещения множества вычислительных конвейеров.

Основными макрооперациями в графовых задачах являются объединение, разность, пересечение и симметрическая разность множеств. Множества имеют ряд существенных отличий от массивов: множества являются неупорядоченными структурами: элементы множеств могут располагаться в произвольном порядке; в каждый момент времени множество может содержать различное число элементов; при выполнении операций над множествами необходимо следить, чтобы в множестве не появилось двух одинаковых элементов. В языках высокого уровня для программирования ПЛИС (ImpulseC, SystemC, Cynlib, Handle-C, Mitrion-C, Catapult C Synthesis, COLAMO) используются методы на основе обработки массивов данных, в которых множество индексируется и перебор элементов осуществляется по их адресам. Размер массива определяется потенциально

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

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

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

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

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

Целью работы является минимизация времени решения графовых полных задач.

Объектом исследований является программное обеспечение реконфигурируемых вычислительных систем.

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

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

Для достижения поставленной цели и решения научной задачи необходимо:

1) провести анализ существующих вычислительных средств, потенциально позволяющих решать графовые №-полные задачи;

2) разработать библиотеку основных макроопераций над множествами для решения графовых задач на реконфигурируемых вычислительных системах;

3) разработать метод создания параллельно-конвейерных программ для РВС на основе распараллеливания по слоям для решения графовых №-полных задач с битовым представлением множеств;

4) разработать метод создания параллельно-конвейерных программ для РВС на основе распараллеливания по итерациям для решения графовых №-полных задач с символьным представлением множеств;

5) провести анализ методов распараллеливания по слоям и распараллеливания по итерациям и разработать методику, позволяющую

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

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

Научная новизна диссертационной работы заключается в том, что в ней разработаны:

1) модернизированный метод создания параллельно-конвейерных программ для РВС на основе распараллеливания по слоям для решения графовых №-полных задач с битовым представлением множеств, отличающийся сочетанием мультиконвейерного и макроконвейерного методов распараллеливания и введением коммутатора для переключения информационных потоков и буферной памяти для хранения промежуточных результатов с целью равномерного распределения нагрузки между вычислительными подструктурами в процессе вычислений;

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

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

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

высокопроизводительных вычислительных систем при решении графовых ЫР-полных задач. Автором доказано, что при применении стандартных методов

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

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

Практическая значимость:

1) использование модернизированного метод распараллеливания по слоям для синтеза параллельно-конвейерных программ для РВС позволило сократить время решения задачи поиска максимальных клик по сравнению с многопроцессорной реализацией. В частности, выигрыш по времени решения задачи поиска всех максимальных клик графа Муна-Мозера с 51 вершиной на РК «Терциус-2Т» (8 ПЛИС XVKU095) по сравнению с кластерной системой (32 процессора Intel Xeon E5504) составил 15 раз, а для графа с 300 вершинами и вероятностью ребра 0,6 - 6 раз. Анализ показал, что для графов с 300 вершинами при использовании эффективного1 числа ПЛИС (96 ПЛИС XCVU9P), выигрыш по сравнению с кластерной системой возрастает до 37 раз. Максимальный размер графов, обрабатываемых методом распараллеливания по слоям, ограничен необходимостью размещения матрицы плотности во внутренней памяти ПЛИС: при использовании ПЛИС XCKU095 возможна обработка графов до 1000 вершин;

2) новый метод распараллеливания по итерациям для синтеза параллельно-конвейерных программ для РВС имеет значительно большее число эффективного вычислительного ресурса по сравнению с методом распараллеливания по слоям. Экспериментальные исследования метода распараллеливания по итерациям для

1 Под «эффективным числом» понимается такое количество вычислительного ресурса, при превышении которого рост производительности существенно замедляется.

синтеза конвейерно-параллельных программ для РВС показали, что использование данного метода позволило обеспечить выигрыш во времени решения задачи поиска всех максимальных клик графа по сравнению с кластерной системой (32 процессора Intel Xeon E5504) при решении графа с 300 вершинами и вероятностью ребра 0,6 на 64% на ВМ «Сегин» (8 ПЛИС XCVU9P). Анализ показал, что при обработке графа на 4000 вершин с вероятностью ребра 0,5 при использовании эффективного количества вычислительного ресурса время решения задачи перечисления максимальных клик по сравнению с методом распараллеливания по слоям сократится в 10 раз (600 ПЛИС XCVU9P), а по сравнению с кластерной системой (300 процессоров Intel Xeon E5504) - в 43 раза. Максимальный размер графов, обрабатываемых методом распараллеливания по итерациям, ограничен необходимостью размещения одной вычислительной подструктуры в пределах одной ПЛИС: при использовании ПЛИС XCKU095 возможна обработка графов с числом вершин до 4600. Таким образом, новый метод распараллеливания по итерациям позволяет обрабатывать графовые задачи большей размерности за приемлемое время;

3) методика выбора наиболее эффективного метода распараллеливания (по слоям или по итерациям) в зависимости от доступного вычислительного ресурса и параметров решаемых графов;

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

Использование результатов работы.

Результаты диссертационного исследования внедрены при выполнении ряда НИОКР в Научно-исследовательском центре супер-ЭВМ и нейрокомпьютеров (НИЦ СЭ и НК), а именно:

- СЧ ОКР по созданию системы обработки сетевого трафика, шифр «Ликование-СН-Н/Т» (контракт №16/14-р от 16.09.2016);

- НИР по созданию высокопроизводительного настольного реконфигурируемого компьютера, шифр «Терциус», №НЦ-170210 от 01.12.2017;

- НИОКР «Анализ возможности построения и разработка узлов и блоков высокопроизводительных реконфигурируемых вычислительных систем на основе ПЛИС уровня UltraScale+ с погружной жидкостной системой охлаждения», шифр «Арктур», №НЦ-170201 от 18.01.2017;

- НИР «Теоретические исследования высокопроизводительных вычислительных систем «СКИФ-ГЕО», обеспечивающих формирование оптимальных конфигураций аппаратных средств и программного обеспечения для решения расчетных геолого-геофизических задач и входящих в состав комплекса программных и технических средств, предназначенного для построения программно-аппаратных комплексов семейства «СКИФ-НЕДРА»», № гос. рег. AAAA-A16-116062010007-4 по договору № 2-53-10-СКИФ/НИР/16 от 01.01.2016, Таганрог, НИЦ СЭ и НК, шифр «Нефть».

Материалы диссертации использованы в Южном научном центре Российской академии наук (ЮНЦ РАН), а именно:

- НИР «Разработка научных основ создания средств систем мониторинга и прогнозирования опасных процессов и обеспечения безопасности населения и береговой инфраструктуры на базе технологий цифровой экономики», № госрег. AAAA-A18-1180601960106-3;

- НИР «Методы и средства построения высоконадежных реконфигурируемых систем мониторинга и диагностики на базе технологий «цифровой экономики», № госрег. AAAA-A19-119011190173-6.

Результаты диссертации использованы в учебном процессе кафедры интеллектуальных и многопроцессорных систем (ИМС) Института компьютерных технологий и информационной безопасности (ИКТИБ) Южного федерального университета (ЮФУ) в лекционном курсе по дисциплине «Современные проблемы прикладной математики и информатики» (тема № 6

«Проблема P и NP задач»), для подготовки магистров направления подготовки 01.04.02 Прикладная математика и информатика (образовательные программы «Прикладная математика для высокопроизводительных вычислительных систем», «Математическое моделирование в инженерных науках»).

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

Апробация работы.

Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских научно-технических конференциях: XIII, XIV, XV и XVI ежегодных молодежных научных конференциях студентов, аспирантов и молодых ученых ЮНЦ РАН, Ростов-на-Дону; на пленарном заседании XIV ежегодной молодежной научной конференции студентов, аспирантов и молодых ученых ЮНЦ РАН, Ростов-на-Дону; 10-й всероссийской мультиконференции по проблемам управления (МКПУ-2017), с. Дивноморское, Геленджик, 2017 г.; 12-й всероссийской мультиконференции по проблемам управления (МКПУ-2019), с. Дивноморское, Геленджик, 2019 г; на Донецком международном круглом столе «Искусственный интеллект: теоретические аспекты и практическое применение» (ИИ-2020), online, 2020 г.

Наиболее значительными публикациями по теме диссертации являются:

1. Kasarkin A.V., Levin I.I., Sorokin D.A. New iteration parallel-based method for solving graph NP-complete problems with reconfigurable computer systems // IOP Conf. Series: Materials Science and Engineering. - 2020. - Vol. 919(1). - P. 052007(1-7). doi: 10.1088/1757-899X/919/5/052007 (научное рецензируемое издание, индексируемое в базе Scopus).

В работе Касаркиным А.В. описан метод создания параллельно-конвейерных программ на основе принципа распараллеливания по итерациям для решения графовых №-полных задач на РВС.

2. Касаркин А.В., Левин И.И. Структурная реализация задачи нахождения всех максимальных клик графа на реконфигурируемых вычислительных системах // Вестник компьютерных и информационных технологий. - 2018. - № 10. - С. 3-10. (ведущий рецензируемый журнал, входит в перечень ВАК).

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

3. Касаркин А.В., Левин И.И. Реализация алгоритма Брона-Кербоша на реконфигурируемых вычислительных системах // Известия ЮФУ. Технические науки. - 2019. - №7 (209). - С. 143-152. (ведущий рецензируемый журнал, входит в перечень ВАК).

В работе Касаркиным А.В. описано применение метода распараллеливания по слоям для реализации алгоритма Брона-Кербоша на РВС.

4. Свидетельство о государственной регистрации программ для ЭВМ № 2017618283, РФ. Среда разработки прикладных программ для реконфигурируемых вычислительных систем // Левин И.И., Дордопуло А.И., Бовкун А.В., Касаркин А.В. Зарегистр. в Реестре программ для ЭВМ 26.07.2017 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

Вклад Касаркина А.В. в создание зарегистрированной программы для ЭВМ состоит в создании библиотеки макроопераций для решения задач теории множеств на РВС для системы COLAMO.

5. Свидетельство о государственной регистрации программ для ЭВМ № 2020615198, РФ. Программная модель для решения графовых задач на реконфигурируемых вычислительных системах // Касаркин А.В., Левин И.И.,

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Чередникова А.В. Введение в теорию графов: учеб.-метод. пособие /

A.В. Чередникова, И.В. Землякова. - Кострома: КГТУ, 2012. - 28 с.

2. Нефедов В.Н. Курс дискретной математики: Учеб пособие /

B.Н. Нефедов, В.А. Осипова. - М: Изд-во МАИ, 1992.

3. Яблонский Г.С., Быков В.И., Горбань А.Н. Кинетические модели каталитических реакций. - Новосибирск: Наука (Сиб. отделение), 1983.- 255 c.

4. Гладких О.Б., Белых О.Н. Основные понятия теории графов: Учебное пособие. - Елец: ЕГУ им. И.А. Бунина, 2008. -175 с.

5. Соколова О.Д. Графовые модели для задач функционирования современных сетей передачи данных // Труды 9-й Азиатской международной школы-семинара "Проблемы оптимизации сложных систем". - Алма-Ата (Казахстан), 2013. - С. 314-318.

6. Кирьянов А.Г., Ляхов А.И., Некрасов П.О., Платов Д.А. и др. Протокол многоадресной маршрутизации Proximity-based Groupcast in MANET // Информационные процессы. 2012. к 3. - Т.12. - С. 213-228.

7. Попков В.К. Математические модели связности. - Новосибирск: Изд-во ИВМиМГ СО РАН, 2006.

8. Sokolova O., Podkorytov D., Rodionov A., Yurgenson A. Using Agent-Oriented Simulation System AGNES for Evaluation of Sensor Networks // Lecture Notes in Computer Science. Berlin; Heidelberg: Springer Verlag. 2010. V. 6235. P. 247-250.

9. Колегов Д.Н. Проблемы синтеза и анализа графов атак // Вестник Томского университета. Приложение. 2007. к 23. С. 180-188.

10. Соколова О.Д., Перемыслова М.В. Моделирование сетей на Network Simulator и анализ их уязвимостей с помощью графов атак // Материалы междунар. научно-практ. конф. «Исследование, разработка и применение высоких

технологий в промышленности». - Санкт-Петербург, 28-30 апреля 2009. - С. 7374.

11. Raniwala A., Gopalan K., Chiueh T. Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks // Mobile Computing and Communications Review. N 2. V. 8.

12. Shakhov V.V., Hyunseung Choo. Analytical Approach for Channel Assignments in Cellular Networks // Computational Science. ICCS 2003, International Conference, Melbourne, Australia, and St. Petersburg, Russia, June 2-4, 2003. Proc., Part I.

13. Amin Bahmanian Graph and Hypergraph Models for Scheduling Problems in Wireless Networks / [Elect. res.]. http://www.eng.auburn.edu/\~pagrawal/seminar/2011 (дата обращения 01.02.2021).

14. Qiao Li, Rohit Negi: Maximal Scheduling in Wireless Ad Hoc Networks With Hypergraph Interference Models / IEEE T. Vehicular Technology. N 61.

15. Erdos P., Renyi A. On random graphs 1 // Publ. Math. 1959. Debrecen 6. P. 290-297.

16. Иванова И.А., Шестаков А.А. Построение дерева передачи данных в беспроводных сенсорных сетях // Автоматизация и управление в технических системах. 2013. к 4.

17. Райгородский А.М. Модели случайных графов и их применение.

18. Barabasi L.A., Albert R., Jeong H. Scale-free characteristics of random networks: the topology of the world-wide web // Physica A. 2000. V. 28 1. P. 69-77.

19. Huson M.L., Sen A. Broadcast scheduling algorithms for radio networks / Military Communications Conf, IEEE MILCOM. 1995. V. 2, P. 647-651.

20. Xu X., Wang Y., Du H., Wan P.-J. etc. Approximations for node-weighted Steiner tree in unit disk graphs // Optimization Letters. 2010. N. 4(3). P. 405-416.

21. Gupta R., Walrand J., Goldschmidt O. Maximal cliques in unit disk graphs: Polynomial approximation // Proceedings INOC. 2005.

22. Шахов В.В., Юргенсон А.Н., Соколова О.Д. Эффективный метод для генерации псевдо-случайных UDG-графов / Материалы конф. " Информационные технологии и системы". Калининград, 2013.

23. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. - М.: Радио и связь, 1990. - 216 с.

24. UltraFast Design Methodology Guide for the Vivado Design Suite // UG949 (v2019.2) December 6, 2019 [Электронный ресурс] URL: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2019_2/ug949-vivado-design-methodology.pdf (дата обращения 01.02.2021).

25. Любецкий В.А. Компьютерное моделирование в задачах регуляции работы генов и эволюции организмов // Вестник РАЕН, 2012, том 12, №4. - С.108-115.

26. Фролов А., Семенов А., Мошкин Д., Кабыкин В. Суперкомпьютеры для графовых задач // Открытые системы. СУБД, №07, 2011 [Электронный ресурс] URL: https://www.osp.ru/os/2011/07/13010498/ (дата обращения 01.02.2021).

27. Feo J., Harper D., Kahan S., Konecny P. Eldorado. Proceedings of the 2nd Conference on Computing Frontiers. New York, NY, USA: ACM, 2005.

28. Jason Bakos, High-Performance Heterogeneous Computing with the Convey HC-1. Computing in Science and Engineering, 2010, Vol. 12, No. 6.

29. Семенов А.С., Соколов А.А., Эйсымонт Л.К. Архитектура глобально адресуемой памяти мультитредово-потокового суперкомпьютера // Электроника: Наука, Технология, Бизнес. - 2009. - №1.

30. Симонов А.С., Жабин И.А., Куштанов Е.Р., Макагон Д.В., Семенов А.С., Щербак А.Н. Высокоскоростная сеть Ангара: архитектура и результаты применения // Вопросы кибербезопасности. 2019. №4 (32).

31. Мукосей А.В., Семенов А.С., Симонов А.С. Имитационное моделирование подсети коллективных операций сети «Ангара» // Вестник ЮУрГУ, Вычислительная математика и информатика. Т. 4, №3, 2015. - С. 40-55.

32. Harris M. Mapping computational concepts to GPUs // ACM SIGGRAPH 2005 Courses (SIGGRAPH '05), John Fu-jii (Ed.). ACM, New York, NY, USA, 2005. Article 50. DOI: 10.1145/1198555.1198768.

33. Официальное руководство по программированию на CUDA, вер. 1.1 [Электронный ресурс] // CUDA Programming Guide. Chapter 1. Introduction to CUDA ^ 1.2 CUDA: A New Architecture for Computing on the GPU. URL: http: //developer. download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_P rogramming_Guide.pdf (дата обращения: 01.02.2021).

34. Боресков А.В., Харламов А.А., Марковский Н.Д. и др. Параллельные вычисления на GPU. Архитектура и программная модель CUDA. - М.: Издательство МГУ, 2015. - 336 с.

35. Boyer V., El Baz D., Elkihel M. Solving knapsack problems on GPU // Computers & Operations Research. 2012. Vol. 39, is-sue 1. Pp. 42-47. DOI: 10.1016/j.cor.2011.03.014

36. Lalami M.E., El-Baz D. GPU Implementation of the branch and bound method for knapsack problems // Proceedings of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), Shanghai, China, 2012. Pp. 1769-1777. DOI: 10.1109/IPDPSW.2012.219

37. Попов М.В., Посыпкин М.А. Эффективная реализация точных алгоритмов решения задач дискретной оптимизации на графических ускорителях // Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 14, n. 2, p. 408-418, june 2018. ISSN 2411-1473.

38. Кирюшин Н.К., Михалев И.В. Использование многоядерных ускорителей для решения задачи пропозициональной выполнимости // Проблемы Науки. 2017. №22 (104).

39. Dasari N. S., Ranjan D., Mohammad Z. Maximal Clique Enumeration for Large Graphs on Hadoop Framework // Proc. of the First Workshop on Parallel Programming for Analytics Applications. 2014. Р. 21-30. DOI: 10.1145/2567634.2567640.

40. Rossi R. A., Gleich D. F., Gebremedhin A. H. Parallel Maximum clique Algorithms with Applications to Network Analysis // SIAM J. Sci. Comput. 2015. V. 37, No. 5. Р. 589 - 616. DOI: 10.1137/14100018X

41. Kovacs L., Szabo G. Conceptualization with Incremental Bron-Kerbosch Algorithm in Big Data Architecture // Acta Polytechnica Hungarica. 2016. V. 13, No. 2. Р. 139 - 158. DOI: 10.12700/aph.13.2.2016.2.8.

42. Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection / B. Pattabiraman et al. // Internet Mathematics. 2015. V. 11, No. 4-5. P. 421 - 448. DOI: 10.1080/15427951.2014.986778.

43. Dasari N. S., Zubair M., Ranjan D. A Novel Parallel Algorithm for Maximal Clique Enumeration on Multicore and Distributed Memory Architectures. [Электронный ресурс]. 10 р. URL: https://pdfs.semanticscholar.org/9827/9e2cedb14085886fcb4473f1ba483a3df195.pdf (дата обращения 01.02.2021).

44. Dasari N.S., Desh R., Z. M, pbitMCE: A bit-based approach for maximal clique enumeration on multicore processors, in: Proc. 20th IEEE International Conference on Parallel and Distributed Systems (ICPADS 2014), 2014, pp. 478-485. DOI: 10.1109/PADSW.2014.7097844.

45. Moon J. W., Moser L. On Cliques in Graphs // Israel J. Math. 1965. V. 3. P. 23 - 28.

46. Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров [электронный ресурс]. - Режим доступа: http://superevm.ru.

47. Левин И.И., Дордопуло А.И., Каляев И.А., Гудков В.А. Высокопроизводительные реконфигурируемые вычислительные системы на основе ПЛИС VIRTEX-7 // Программная инженерия. 2014, № 6. - С. 3-8.

48. Доронченко Ю.И., Каляев И.А., Левин И.И., Семерников Е.А. Вычислительные системы с реконфигурируемой архитектурой на основе современных и перспективных ПЛИС // Тезисы докладов 3-го национального суперкомпьютерного форума НСКФ-2014, Переславль-Залесский, 2014.

49. Итоговый отчет об ОКР «Модульно-наращиваемая многопроцессорная вычислительная система с программируемой архитектурой на основе реконфигурируемой элементной базы», № гос. рег. 0122.0510630, инв. № 0220.0601017,Таганрог, НИИ МВС ТРТУ, шифр «Медведь», 2006 г.

50. «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», Итоговый отчет об ОКР, № гос. рег. 01.2.007 05707, инв. № 0220.0900079, Таганрог, НИИ МВС ЮФУ, шифр «Большая Медведица», 2007 г.

51. «Разработка теоретических основ построения сверхвысокопроизводительных реконфигурируемых вычислительных систем», Отчет о НИР, № гос. рег. 01201153442, Таганрог, НИИ МВС ЮФУ, шифр «Маска», 2012 г.

52. Левин И.И., Дордопуло А.И., Федоров А.М., Доронченко Ю.И. Развитие технологии построения реконфигурируемых вычислительных систем с жидкостным охлаждением // Суперкомпьютерные технологии (СКТ-2018): материалы 5-й Всероссийской научно-технической конференции: в 2 т. - Ростов-на-Дону; Таганрог: Изд-во ЮФУ, 2018. - Т. 1. - С. 184-187. ISBN 978-5-9275-28349 (Т. 1).

53. Левин И.И., Дордопуло А.И., Сорокин Д.А., Каляев З.В., Доронченко Ю.И. Реконфигурируемые компьютеры на основе ПЛИС Xilinx Virtex UltraScale // Parallel Computational Technologies (13th International Conference, PCT 2019, Immanuel Kant Baltic Federal University, Kaliningrad, Russia, April 2-4, 2019. - Pp. 288-298. http://omega.sp.susu.ru/pavt2019/short/144.pdf.

54. ГОСТ Р 50754-95. Язык описания аппаратуры цифровых систем VKDL. Описание языка [Текст] / Российский НИИ информационных систем (РосНИИ ИС); Всероссийская ассоциация организаций, заинтересованных в применении языка VHDL (ВАЯПС), 01.01.1996.

55. Рубанов В.В. Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки [Электронный ресурс] -http://citforum.ru/programming/embedded/languages/2.shtml (дата обращения 11.06.2020).

56. Open SystemC Initiative. http://www.systemc.org. (дата обращения 11.06.2020)

57. http://www.sai.msu.su/sal/Z/1/CYNLIB.html (дата обращения 11.06.2020)

58. http: //agilityds. com/products/c_based_products/dk_design_suite/handel-c.aspx (дата обращения 11.06.2020)

59. http://www.mitrionics.com (дата обращения 11.06.2020)

60. http://www.mentor.com (дата обращения 11.06.2020)

61. Левин, И.И. Язык программирования высокого уровня для многопроцессорной системы с программируемой архитектурой [Текст]: сборник трудов / И.И. Левин, В.Ф. Гузик, О.О. Сафронов // Распределенная обработка информации. Новосибирск, 1991.

62. Левин, И.И. Язык параллельного программирования высокого уровня для структурно-процедурной организации вычислений [Текст] / И.И. Левин // Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения", Черноголовка. - М.: Изд-во МГУ, 2000. - С. 108112.

63. Левин, И.И. Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений [Текст]: диссертация на соискание ученой степени доктора технических наук: 05.13.11, 05.13.15: защищена 8.10.2004: утверждена 8.04.2005 / Левин Илья Израилевич. - Таганрог, 2004. - 363 с. - Библиогр.: с. 285-300.

64. Каляев, И.А. Реконфигурируемые мультиконвейерные вычислительные структуры [Текст]: монография / И.А. Каляев, И.И. Левин, Е.А. Семерников, В.И. Шмойлов; под общ. ред. И.А. Каляева. - 2-е изд., перераб. и доп. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009. - 344 с.

65. Левин, И.И. О языке макроассемблера комплекта БИС с программно-перестраиваемой структурой [Текст] / И.И. Левин, О.О. Сафронов // Архитектура ЭВМ и машинное моделирование. - Таганрог: Изд-во ТРТИ, 1989.

66. Гудков В.А. Расширения структурно-процедурного языка программирования ARGUS для многопроцессорных вычислительных систем с макрообъектной архитектурой [Текст] / В.А. Гудков // Материалы Третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. - Ростов/Д: Изд-во ЮНЦ РАН, 2007. - С. 135-136.

67. «Разработка методов и инструментальных систем для анализа эффективности работы параллельных программ и суперкомпьютеров», отчет о НИР, № гос. рег. И110519102540, Таганрог, НИИ МВС ЮФУ, шифр «Рамка», 2012 г.

68. «Разработка и исследование принципов построения программных средств для высокопроизводительных реконфигурируемых вычислительных комплексов», отчет о НИР, № гос. рег. 01201153442, Таганрог, НИИ МВС ЮФУ, шифр «Маска», 2013 г.

69. «Разработка и исследование методов синтеза прикладных программ для реконфигурируемых вычислительных систем на основе перспективных ПЛИС сверхвысокой степени интеграции», отчет о НИР, № гос. рег. 114061040060, Таганрог, НИИ МВС ЮФУ, шифр «Шкала», 2014 г.

70. Каляев А.В. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений [Текст]: монография / А.В. Каляев, И.И. Левин; под ред. А.В. Каляева. - М.: Янус-К, 2003. - 380 с.

71. Левин И.И. Пелипец А.В. Методология распараллеливания по итерациям при решении задач линейной алгебры на реконфигурируемых вычислительных системах // Вестник компьютерных и информационных технологий, 2016, № 7 (145), С.34-40.

72. Левин И.И., Доронченко Ю.И., Коваленко А.Г. Реализация задачи фильтрации жидкости в пористой среде на реконфигурируемой вычислительной системе // Вычислительные технологии, 2016 21 (3), С.45-55.

73. Левин И.И., Семерников Е.А. Устойчивость конвейерных рекурсивных фильтров. Вестник Южного научного центра Российской академии наук, 2005. - Т.1, вып. 2. - С. 28-40.

74. Куратовский К., Мостовский А. Теория множеств. - М.: Мир, 1970. -416 с.

75. http://comp-science.narod.ru/Progr/mn.htm (дата обращения 01.02.2021)

76. Шрайнер П.А. Электронная книга ISBN: 978-5-9556-0034-5 (https://www.intuit.ru/studies/courses/44/44/lecture/32091) (дата обращения 01.02.2021)

77. Seibel P. Practical Common Lisp // Apress, C. 501, 2005.

78. Овчинников В.А. Операции над упорядоченными множествами // Электронное научно техническое издание «Наука и Образование». http://technomag.edu.ru/doc/188322.html (Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408)

79. Кук С. Сложность процедур вывода теорем // Кибернетический сб. Вып. 12. М. : Мир, 1975, С. 5-15

80. Chen Y. and Crippen G.M. A novel approach to structural alignment using realistic structural and environmental information. Protein Science, vol. 14, no. 12, p. 29352946, 2005.

81. Zhang B., Park B.H., T. V. Karpinets, and N. F. Samatova, "From pulldown data to protein interaction networks and complexes with biological relevance," Bioinformatics, vol. 24, no. 7, pp. 979-986, 2008.

82. Chen Z., Hendrix W., and Samatova N. F., "Community-based anomaly detection in evolutionary networks," J. Intell. Inf. Syst., vol. 39, no. 1, pp. 59-85, 2012.

83. Berry N., Ko T., Moy T., Smrcka J., Turn-ley J., and Wu B., "Emergent Clique Formation in Terrorist Recruitmen." National Conference on Artificial Intelligence, 2004. [Online]. Available: https://www.aaai.org/Papers/Workshops/2004/WS-04-02/WS04-02-005.pdf (дата обращения: 01.02.2021).

84. Pardalos P. M., Xue J. The maximum clique problem // Journal of Global Optimization. 1994. Vol. 4. P. 301-328.

85. Harary F., Ross I. C. A Procedure for Clique Detection Using the Group Matrix // Sociometry. 1957. Vol. 20. P. 205-215.

86. Auguston J. G., Minker J. An analysis of some graph theoretical clustering techniques // J. ACM. 1970. Vol. 17. №4. P. 571-588.

87. Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph // Comm of ACM. 1973. V. 16. P. 575 - 577.

88. Johnson D. S., Yannakakis M., Papadimitriou C. H. On Generating All Maximal Independent Sets // Information Processing Letters. 1988. Vol. 27. P. 119123.

89. Loukakis E., Tsouros C. A Depth First Search Algorithm to Generate the Family of Maximal Independent Sets of a Graph Lexicographically // Computing. 1981. Vol. 27. P. 249-266.

90. Harley E., Bonner A., Goodman N. Uniform integration of genome mapping data using intersection graphs // Bioinformatics. 2001. Vol. 17. P. 487-494.

91. Tomita E., Tanaka A., Takahashi H. The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments // Theoretical Computer Science. 2006. V. 363, No. 1. P. 28 - 42.

92. Пелипец А.В. Эффективное использование памяти в решении задач линейной алгебры на реконфигурируемых вычислительных системах // Развитие современной науки: теоретические и прикладные аспекты : сборник статей студентов, магистрантов, аспирантов, молодых ученых и преподавателей / Под общ. ред. Т.М. Сигитова. - Пермь : ИП Сигитов Т.М., 2016. - С. 12-14.

93. Гладков Л.А., Генетические алгоритмы / Гладков Л.А., Курейчик В. В., Курейчик В.М.; Под ред. В.М. Курейчика. - 2-е изд., исправл. и доп. - М. : ФИЗМАТЛИТ, 2006. - 320 с.

94. Курейчик В.М. Эволюционные методы построения клик и независимых множеств графов//Известия ТРТУ. 2003. -№2. -С.66-71.

95. Курейчик В.М. Новый подход к раскраске и определению клик графа на основе квантовых алгоритмов//Известия ТРТУ. 2004. №3. С. 29-34.

96. Современные и перспективные высокопроизводительные вычислительные системы с реконфигурируемой архитектурой / И. И. Левин и др. // Вестник Южно-Уральского государственного университета. Сер. Вычислительная математика и информатика. 2015. Т. 4, № 3. С. 24 - 39.

97. Гузик В. Ф., Каляев И. А., Левин И. И. Реконфигурируемые вычислительные системы // Под общ. ред. И.А. Каляева. Ростов н/Д: Изд-во ЮФУ, 2016. 472 с.

98. Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров [электронный ресурс]. http://superevm.ru (дата обращения 01.02.2021).

99. Касаркин А. В., Левин И. И. Структурная реализация задачи нахождения всех максимальных клик графа на реконфигурируемых вычислительных системах // Вестник компьютерных и информационных технологий. - 2018. - № 10. - С. 3-10.

100. Eppstein D., Lffler M., and Strash D., "Listing all maximal cliques in sparse graphs in near-optimal time," in Algorithms and Computation, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2010, vol. 6506, pp. 403-414.

101. Eppstein D. and Strash D., "Listing all maximal cliques in large sparse real-world graphs," in Proceedings of the 10th international conference on Experimental algorithms, ser. SEA'11. Berlin, Heidelberg: Springer-Verlag, 2011, pp. 364-375. [Online]. Available: http://dl.acm.org/citation.cfm?id=2008623.2008656 (дата обращения 01.02.2021).

102. Левин И.И., Дордопуло А.И., Каляев И.А., Доронченко Ю.И., Раскладкин М.К. Современные высокопроизводительные вычислительные системы с реконфигурируемой архитектурой на основе ПЛИС Xilinx Virtex-7 и Virtex UltraScale // Труды Международной конференции "Суперкомпьютерные дни в России". Москва: Издательство МГУ, 2015. С. 435-446.

103. Levin I., Dordopulo A., Fedorov A., Doronchenko Y. Design Technology for Reconfigurable Computer Systems with Immersion Cooling. In: Voevodin V.,

Sobolev S. (eds) Supercomputing. RuSCDays 2018. Communications in Computer and Information Science, vol 965. Springer, Cham

104. Сорокин Д.А. Методы решения задач с переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах: диссертация на соискание ученой степени кандидата технических наук, по специальности 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И. Дис. совет Д 212.208.24 ЮФУ от 15.06.2012 г., протокол № 5. - 165 с.

105. Левин И.И. Пелипец А.В. Эффективная реализация распараллеливания на реконфигурируемых системах // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2018. - № 8. - С. 11 - 16.

106. Пелипец А.В. Методы и средства решения задач линейной алгебры на высокопроизводительных реконфигурируемых вычислительных системах: диссертация на соискание ученой степени кандидата технических наук, по специальности 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И. - Таганрог, 2016. - 199 с.

107. Левин И.И., Доронченко Ю.И., Коваленко А.Г. Реализация задачи фильтрации жидкости в пористой среде на реконфигурируемой вычислительной системе // Вычислительные технологии, 2016. № 21 (3). - С.45-55.

108. Левин И.И., Семерников Е.А. Устойчивость конвейерных рекурсивных фильтров // Вестник Южного научного центра Российской академии наук, 2005. - Т.1, вып. 2. - С. 28-40.

109. Apurba Das, Seyed-Vahid Sanei-Mehri, Srikanta Tirthapura Shared-Memory Parallel Maximal Clique Enumeration from Static and Dynamic Graphs. https://arxiv.org/abs/2001.11433 (дата обращения 01.02.2021)

110. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. - М.: Янус-К, 2003. - 380 с.

111. Котляров А.С., Левин И.И. Оптимизированный метод обработки сетевых потоков данных в реконфигурируемых вычислительных системах // Вестник компьютерных и информационных технологий. - 2019. - № 6. - С. 39-46. DOI: 10.14489/vkit.2019.06.pp.039-046.

112. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры. Изд. 2-е, перераб. и доп. / Под общ. ред. И.,А. Каляева. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009.

113. Касаркин А.В., Левин И.И. Реализация алгоритма Брона-Кербоша на реконфигурируемых вычислительных системах // Известия ЮФУ. Технические науки. - 2019. - №7 (209). - С. 143-152.

114. Kasarkin A.V., Levin I.I., Sorokin D.A. New itération parallel-based method for solving graph NP-complete problems with reconfigurable computer systems // IOP Conf. Series: Materials Science and Engineering. - 2020. - Vol. 919(1). - P. 052007(1-7). doi: 10.1088/1757-899X/919/5/052007

115. Касаркин А.В. Реализация операций добавления и исключения элементов множества на реконфигурируемых вычислительных системах // Материалы 10-й Всероссийской мультиконференции по проблемам управления (МКПУ-2017), 11-16 сентября 2017 г. - Ростов/Д.: Изд-во ЮФУ, 2017. - Т.3. -С.134-137.

116. Касаркин А.В. Решение задачи поиска всех максимальных клик графа на реконфигурируемых вычислительных системах // Суперкомпьютерные технологии (СКТ-2018): материалы 5-й Всероссийской научно-технической конференции: в 2 т. - Ростов/Д; Таганрог: Изд-во ЮФУ, 2018. - Т. 1. - С. 162-165. ISBN 978-5-9275-2834-9 (Т. 1).

117. Касаркин А.В. Анализ информационного графа алгоритма Брона-Кербоша // XV ежегодная научная конференция молодых ученых «Вклад молодых ученных южного макрорегиона в реализацию стратегии развития Российской федерации: цели, задачи, результаты», г. Ростов-на-Дону, 15.04.2019 -26.04.2019 гг. - г. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2019. - С. 100.

118. Касаркин А.В. Анализ и управление потоками данных при решении NP-полных задач на реконфигурируемых вычислительных системах // 12-я Мультиконференция по проблемам управления (МКПУ-2019), 23 - 28 сентября 2019 г., с. Дивноморское, Россия. - Ростов-на-Дону; Таганрог: Изд-во ЮФУ, 2019. - Т. 3. - С. 100-102. ISBN 978-5-9275-3188-2 (Т. 3).

119. Левин И.И., Касаркин А.В. Решение интеллектуальных графовых NP полных задач на реконфигурируемых вычислительных системах // «Искусственный интеллект: теоретические аспекты, практическое применение : материалы Донецкого международного научного круглого стола» (ИИ-2020). -Донецк : ГУ ИПИИ, 2020. - С. 116-122.

120. Касаркин А.В. Эффективная реализация операций над множествами на реконфигурируемых вычислительных системах // XIII ежегодная научная конференция студентов, аспирантов и молодых ученых базовых кафедр ЮНЦ РАН «Исследования и разработки передовых научных направлений», 19-21 апреля 2017 г. - Ростов/Д: Изд-во ЮНЦ РАН, 2017. - С. 154.

121. Касаркин А.В. Реализация задачи о клике на реконфигурируемых вычислительных системах // XIV Ежегодная молодежная научная конференция студентов, аспирантов и молодых ученых «Достижения и перспективы молодых ученых в интересах развития Юга России»: тезисы докладов (г. Ростов/Д., 12-26 апреля 2018 г.). - Ростов/Д: Изд-во ЮНЦ РАН, 2018. - С. 73.

122. Касаркин А.В. Параллельно-конвейерная реализация алгоритма Брона-Кербоша // XVI Ежегодная молодежная научная конференция «Юг России: вызовы времени, открытия, перспективы»: материалы конференции - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2020. - 168 с. - ISBN 978-5-4358-0196-5. - С. 51.

123. Свидетельство о государственной регистрации программ для ЭВМ № 2017618283, РФ. Среда разработки прикладных программ для реконфигурируемых вычислительных систем // Левин И.И., Дордопуло А.И., Бовкун А.В., Касаркин А.В. Зарегистр. в Реестре программ для ЭВМ 26.07.2017 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

124. Свидетельство о государственной регистрации программ для ЭВМ № 2020615198, РФ. Программная модель для решения графовых задач на реконфигурируемых вычислительных системах // Касаркин А.В., Левин И.И., Леонтьев А.Л. Зарегистр. в Реестре программ для ЭВМ 18.05.2020 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

125. Касаркин А.В. Модернизация методов решения графовых NP-полных задач на реконфигурируемых вычислительных системах // Суперкомпьютерные технологии (СКТ-2020). Труды молодых ученых. - Ростов-на-Дону - Таганрог: Изд-во ЮФУ, 2020. - С. 111-115.

126. https://www.agner.org/optimize/instruction_tables.pdf (дата обращения 01.02.2021)

127. https://www.agner.org/optimize/microarchitecture.pdf (дата обращения 01.02.2021)

128. Batagelj V. and Zaversnik M., "An o(m) algorithm for cores decomposition of networks," 2003, cite arxiv:cs/0310049. [Online]. Available: http://arxiv.org/abs/cs/0310049 (дата обращения 01.02.2021).

ПРИЛОЖЕНИЕ 1 МАКРООПЕРАЦИИ ТЕОРИИ МНОЖЕСТВ

КАСАРКИН АЛЕКСЕЙ ВИКТОРОВИЧ

МЕТОДЫ И СРЕДСТВА СОЗДАНИЯ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ПРОГРАММ ДЛЯ РЕШЕНИЯ ГРАФОВЫХ ^-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

05.13.11 - Математическое и программное обеспечение вычислительных машин,

комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор Левин И.И.

П.1.1. ОПЕРАЦИЯ ОПРЕДЕЛЕНИЯ ПРИНАДЛЕЖНОСТИ ПОТОКА

ЭЛЕМЕНТОВ МНОЖЕСТВУ

Первичным понятием теории множеств является понятие принадлежности (а е А). При проведении операции определения принадлежности элемента множеству в качестве входных данных выступают множество и элемент, а результатом данной операции является предикат, который принимает значение «истина» («1»), если элемент принадлежит множеству, и «ложь» («0»), если элемент отсутствует во множестве.

Если необходимо определить принадлежность потока элементов {VI}, {У2}, {уз} ... {Уш} множеству А{а1, а2, аз ... ап}, то результатом данной операции станет поток предикатов Р{р1, р2, р3 ... рш}. Рассмотрим алгоритм определения принадлежности потока элементов множеству:

1. Принять очередной добавляемый элемент уу;

2. 1=1;

3. Если (1=п+1) перейти к пункту 1;

4. Если Уу=а1, то ру=1, иначе ру=0;

5. 1=1+1;

6. Перейти к пункту 3.

Временная диаграмма работы данного алгоритма в худшем случае представлена на рис. П. 1.1.

Рис. П. 1.1. Временная диаграмма определения принадлежности потока элементов

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

n*m операций сравнения. Поэтому общее количество операций сравнения (Lin) в наихудшем случае составляет

4 = n •m.

Вычислительную сложность операции определения принадлежности потока элементов множеству можно определить как O(m • n).

Для структурной реализации данной операции на РВС был разработан алгоритм работы вычислительного узла, который обрабатывает и хранит в ячейке один элемент множества ax. В алгоритме: vy - текущий элемент из потока, validy -признак наличия элемента в потоке, fullx - признак наличия элемента ax в данном узле, py - предикат принадлежности элемента vy множеству A.

1. Если ax=vy, то f1=1, иначе f1=0 (сравниваем элемент из потока с содержимым ячейки);

2. Если f1=1 и validy=1 и fullx=1, то py+1=1, иначе py+1=py (устанавливаем предикат в состояние «истина», если элемент присутствует во множестве).

Для реализации данного алгоритма была синтезирована схема блока обработки одного элемента множества «block_cell_in», представленная на рис. П. 1.2.

av

D Q wr

S Q R

fullx

a g A

Рис. П. 1.2. Структурная схема блока определения принадлежности

элемента «block cell in»

Временная диаграмма данной схемы представлена на рис. П. 1.3. На ней поток состоит из трех элементов: «о, «Ь», «о, причем третий элемент -мусорный, так как valid=0, а в ячейке находится один из элементов множества -

«о.

Рис. П. 1.3. Временная диаграмма работы блока «Ыock_ceП_m»

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

В общем виде структура соединения блоков «Ыock_ceП_m» представлена на рис. П. 1.4. На ней поток элементов V вместе с соответствующим элементу предикатом проходит через все блоки определения принадлежности «Ыock_ceП_m». Изначально предикат устанавливается равным нулю ^=0).

Данная конвейерная схема каждый такт может принимать новое данное из потока, что видно на диаграмме (рис. П. 1.3). Таким образом, вычислительная сложность операции определения принадлежности элемента множеству при структурной реализации сводится к линейной O(n), где п - максимальное количество элементов во множестве.

block cell in block cell in block_cell_in block cell in

Рис. П. 1.4. Структурная схема операции принадлежности потока

элементов множеству

П.1.2. ОПЕРАЦИЯ ДОБАВЛЕНИЯ ЭЛЕМЕНТА В МНОЖЕСТВО

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

{а, Ь, с, й }и {¿} = {а, Ь, с, й}, {а, Ь, с, й }иМ = {а, Ь, с, й, у}.

Рассмотрим алгоритм добавления потока элементов {VI}, {У2}, {уз} ... {Уш} во множество А{а1, а2, а3 ... ап}, как он реализуется в классических вычислительных системах, где п - количество элементов во множестве, ш - длина потока элементов. Необходимо понимать, что в потоке элементы могут повторяться.

1. Принять очередной добавляемый элемент уу;

2. 1=1; 1=0;

3. Если (1=п+1) или (1=1) перейти к пункту 7;

4. Если Уу=а1, то 1=1;

5. 1=1+1;

6. Перейти к пункту 3;

7. Если 1=1, то перейти к пункту 1;

8. Добавить vy во множество A;

9. п=п+1;

10. Перейти к пункту 1.

Временная диаграмма работы данного алгоритма в худшем случае представлена на рис. П. 1.5.

Рис. П. 1.5. Временная диаграмма добавления потока элементов

Вычислительная сложность операции объединения двух множеств составляет ü{m ■ n) [78]. Однако в случае добавления потока элементов во множества, в отличие от объединения двух множеств, элементы в потоке могут повторяться. Поэтому в наихудшем случае, когда добавляются все элементы из потока, после каждого добавленного элемента необходимо совершать на одну операцию сравнения больше, чем на предыдущем шаге. Общее число дополнительных операций, по сравнению с операцией объединения двух множеств, является рядом

натуральных чисел и определяется как 0,5 ■ m ■{m +1) или ü(m2 + m). Таким образом, вычислительную сложность операции добавления потока во множество можно определить как

ü{m ■ n + m2 + m)= ü{m ■{n +1)+m2).

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

Однако реконфигурируемые вычислительные системы предоставляют возможность структурной реализации алгоритма. Это позволило перейти к нетранзакционным - потоковым вычислениям, создав вычислительный конвейер для решения данной задачи.

Алгоритм работы вычислительного узла, который обрабатывает и хранит в ячейке один элемент множества ах, представлен ниже. Расшифровка переменных: уу - текущий элемент из потока, уа11ёу - признак наличия элемента в потоке, у_геу2 - текущий элемент из обратного потока, уа11ё_геу2 - признак наличия элемента в обратном потоке, 1и11х - признак наличия элемента ах в данном узле. После того как прямой поток прошел через все вычислительные узлы (их количество определяется максимальной мощностью множества ах) от первого вычислительного узла к последнему, поток проходит по всем вычислительным узлам повторно, но в обратном направлении, от последнего вычислительного узла к первому, поэтому поток после такого разворота был назван обратным потоком элементов.

1. Если ах=уу, то 11=1, иначе 11=0 (сравниваем элемент из прямого потока с содержимым ячейки);

2. Если (уу=у_геу2 и уа11ёу=1) или (уу-1=у_геу2 и уа11ёу-1=1), то 12=1, иначе 12=0 (сравниваем текущий и предыдущий элемент из прямого потока с текущим элементом из обратного потока);

3. Если 11=1 и 1и11х=1, то уа11ёу+1=0, иначе уа11ёу+1= уаНёу (удаляем элемент из прямого потока, если он совпал с элементом в ячейке);

4. Если уа11ё_геу2=1 и 1и11х=0 и 12=0, то ах=уу и 1и11х=1 (добавляем элемент из обратного потока в ячейку, если ячейка свободна);

5. Если 12=0 и уа11ё_геу2=1 и 1и11х=1, то уа11ё_геу2+1=1, иначе уа11ё_геу2+1=0 (удаляем элемент из обратного потока, если он был добавлен в ячейку либо совпал с текущим или предыдущим элементом из прямого потока).

Для реализации данного алгоритма была синтезирована схема блока обработки одного элемента множества «Ь1оск_се11_аёё», представленная на рис. П. 1.6.

Рис. П. 1.6. Структурная схема блока добавления элемента «Ыock_ceП_add»

Временная диаграмма данной схемы представлена на рис. П. 1.7. Рассмотрена следующая ситуация.

Такт 1: ячейка ax пустая, в прямом потоке V элемент «Ь», в обратном потоке Vrevz - «о, в результате элемент «о> с обратного потока добавлен в ячейку;

Такт 2: в прямом потоке «о, в обратном <^», в результате элемент «о> удален с прямого канала;

Такт 3: в прямой мусорный элемент «Ь», в обратном в результате элемент удален из обратного канала;

Такт 4: в прямом «e», в обратном <^», удаления/добавления отсутствуют.

Рис. П. 1.7. Временная диаграмма работы блока «block_cell_add»

В общем виде структура соединения блоков «block_cell_add» представлена на рис. П. 1.8.

block_cell add block cell add block cell add block cell add

V1> V2 „ V3 ъ V4, VN,

г ai Г ^ VrevN a2 г ^ VrevN-1 a3 Г г VrevN-2 ^Vrev2 aN Vrevi

ч ■■■ ч

Рис. П. 1.8. Структурная схема операции добавления потока элементов во

множество

Конвейер состоит из прямого V и обратного Угеу каналов данных, которые проходят через все блоки обработки элементов «Ь1оск_се11_аёё». Поочередное сравнение элемента из потока со всеми элементами множества происходит только в прямом канале, в случае совпадения элемент удаляется из потока. Если элемент из потока не был удален после сравнения со всеми элементами множества, он

направляется в обратный канал. В обратном канале элемент из потока поочередно сравнивается с идущим ему на встречу прямым потоком, причем как с текущим элементом прямого потока, так и с предыдущим. Если произошло совпадение, то элемент удаляется из обратного канала. Если неудаленный элемент из обратного канала попадает в пустой блок обработки элементов «block_cell_add» и не совпадает с элементом из прямого потока, то элемент из обратного канала записывается в ячейку хранения элементов множества и удаляется из обратного потока.

Данная конвейерная схема каждый такт может принимать новое данное из потока, что видно на диаграмме (рис. П. 1.7). Таким образом, при данной структурной реализации вычислительная сложность не зависит от количества элементов в потоке и сводится к линейной O(n), где п - максимальное количество элементов во множестве. При таком подходе при достаточном ресурсе РВС можно реализовать конвейер любой размерности.

П. 1.3. ОПЕРАЦИЯ УДАЛЕНИЯ ЭЛЕМЕНТА ИЗ МНОЖЕСТВА

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

Рассмотрим алгоритм удаления потока элементов {у2}, ... из множества A{a1, a2, aз ... an}, как он реализуется в классических вычислительных системах, где п - количество элементов во множестве, т - длина потока элементов.

{а, Ь, с, й }\{Ь) = {а, с, й},

1. Принять очередной удаляемый элемент уу;

2. 1=1; 1=0;

3. Если (1=п+1) или (1=1) перейти к пункту 7;

4. Если уу=а1, то 1=1;

5. 1=1+1;

6. Перейти к пункту 3;

7. Если 1=0, то перейти к пункту 1;

8. Удалить а1-1 из множества А;

9. п=п-1

10. Перейти к пункту 1.

Временная диаграмма работы данного алгоритма в худшем случае представлена на рис. П. 1.9.

Рисунок П. 1.9 Временная диаграмма удаления потока элементов

В худшем случае чтобы удалить один элемент из потока требуется п операций сравнения. Если поток содержит т элементов, необходимо выполнить п*т операций сравнения. В худшем случае элементы удаляться не будут, значит п останется прежним. Поэтому общее количество операций сравнения (Е<1е1) в наихудшем случае составляет

1м =п•т.

Таким образом, вычислительную сложность операции добавления потока во множество можно определить как

0(т • п).

Для структурной реализации данной операции на РВС был разработан алгоритм работы вычислительного узла, который обрабатывает и хранит в ячейке

один элемент множества ах. Расшифровка переменных: уу - текущий элемент из потока, уаНёу - признак наличия элемента в потоке, £и11х - признак наличия элемента ах в данном узле.

1. Если ах=уу, то £1=1, иначе £1=0 (сравниваем элемент из потока с содержимым ячейки);

2. Если £1=1 и уаНёу=1, то £и11х=0 (удаляем элемент из ячейки).

Для реализации данного алгоритма была синтезирована схема блока обработки одного элемента множества «Ь1оск_се11_аёё» представленная на рис. П. 1.10.

1----1

М1х

Рис. П. 1.10. Структурная схема блока удаления элемента «Ь1оск_се11_ёе1»

Временная диаграмма данной схемы представлена на рис. П. 1.11. На ней поток состоит из трех элементов «Ь», «с», «ё», а в ячейке находится один из элементов множества - «с». После того как элемент «с» из потока попал на обработку происходит очищение ячейки путем установки признака наличия элемента в ней £и11х в "0".

Рис. П. 1.11. Временная диаграмма работы блока «block_cell_del»

В общем виде структура соединения блоков «block_cell_add» представлена на рис. П. 1.12. На ней поток элементов V просто проходит через все блоки удаления элементов «block_cell_del».

block_cell_del block_cell_del block_cell_del block cell del

Vl> V2 , V3 3 ь VS VN(

ai a2 a3 aN

Рис. П. 1.12. Структурная схема операции удаления потока элементов из

множества

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

П. 1.4. ОПЕРАЦИЯ ПЕРЕСЕЧЕНИЕ МНОЖЕСТВ

Результатом операции пересечения множеств является множество, в котором содержатся элементы, присутствующие одновременно во всех исходных множествах (рис. П. 1.13).

А П В

Рис. П. 1.13. Диаграмма Эйлера-Вена для пересечения двух множеств

Рассмотрим алгоритм пересечения множеств А{а1, а2, аз ... ап} и Б(Ь1, Ь2, Ь3 ... Ьт} во множество С{с1; с2, с3 ... ск}, как он реализуется в классических вычислительных системах, где п и т - мощности множеств А и Б соответственно. Обозначается как с = А П В.

1. Ввод множеств А и Б;

2. 1=1, к=1;

3. Если (1=т+1), то перейти к пункту 12;

4. ]=1, 1=0;

5. Если 0=п+1) или 1=1, то перейти к пункту 9;

6. Если а]=Ь^ то 1=1;

7. Л+1;

8. Перейти к пункту 5;

9. Если 1=1, то ск= Ь (добавить во множество С элемент Ь^, к=к+1;

10. 1=1+1;

11. Перейти к пункту 3;

12. Вывод множества С.

Временная диаграмма работы данного алгоритма представлена на рис. П. 1.14.

Рис. П. 1.14. Временная диаграмма пересечения множеств

Вычислительная сложность операции пересечения двух множеств составляет в(т ■ п) [78].

Для структурной реализации данной операции на РВС был разработан алгоритм работы вычислительного узла, который обрабатывает и хранит в ячейке один элемент множества ^ - текущий обрабатываемый элемент из потока, validy - признак наличия элемента в потоке, - признак загружаемого

множества, если равен «1», означает, что элемент принадлежит первому множеству, «0» означает, что элемент принадлежит второму, МЬ - признак наличия элемента ^ в данном узле, full_tmpx - признак того, что в вычислительный узел записан элемент из первого множества, f_compx - признак, означающий, что данный элемент присутствует и в первом, и во втором исходном множествах.

1. Если ^=уу, то П=1, иначе П=0 (сравниваем элемент из потока с содержимым ячейки);

2. Если validy =1 и full_tmpx=0 и flagy=1, то Cx=Vy и full_tmpx=1 (добавляем элемент из потока в ячейку, если ячейка свободна);

3. Если full_tmpx=0 и 1^у=1, то validy+1=0, иначе validy+1=validy (удаляем элемент из потока, если он был добавлен в ячейку)

4. Если А=1 и validy=1 и 1^у=0 и full_tmpx=1, то f_compx=1 (подтверждаем, что элемент в ячейке принадлежит результирующему множеству ^ если он присутствует и в первом, и во втором множестве).

Для реализации данного алгоритма была синтезирована схема блока обработки одного элемента множества «Ь1оск_се11_ти11:» представленная на рис. П. 1.15.

Рис. П. 1.15. Структурная схема блока операции пересечения множеств

«Ь1оск_се11_тиИ»

Временная диаграмма данного блока представлена на рис. 2.16. В данном примере происходит следующее.

Такт 1: Ячейка сх пустая, в потоке Уу элемент «с» из первого множества, элемент «с» добавлен в ячейку и удален из потока;

Такт 2: В потоке запрос на добавление элемента «Ь» из первого множества, удаления/добавления отсутствуют;

Такт 3: В потоке запрос на добавление элемента «с» из второго множества, признак принадлежности элемента «с» множеству С установлен в состояние «истина»;

Такт 4: В потоке элемент «e» из второго множества, удаления/добавления отсутствуют.

Clock

Рис. П. 1.16. Временная диаграмма работы блока «block_cell_mult»

В общем виде структура соединения блоков «Ь1оск_се11_ти11:» представлена на рис. П. 1.17. Для того чтобы выполнить операцию пересечение множеств, необходимо в прямой поток вначале подать все элементы первого множества с признаком Аа§=1, затем подать все элементы второго множества с признаком

block_cell_diff block_cell_diff block_cell_diff block_cell_diff

Рис. П. 1.17. Структурная схема операции пересечения двух множеств

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

На основании четвертого принципа, приведённого в главе 1 диссертации, следует разработать библиотечный элемент, который будет выполнять операцию пересечения множеств с использованием битового представления множеств. Тогда для реализации операции пересечения множеств А и В достаточно будет произвести логическое умножение битовых векторов, соответствующих данным множествам, результатом будет битовый вектор результирующего множества С. Схема и диаграмма битовой реализации операции пересечения двух множеств представлены на рис. П. 1.18.

Рис. 2.18. Структурная схема и временная диаграмма операции пересечения двух

множеств.

На диаграмме показана следующая ситуация.

Такт 1: пересечение множеств {2,3,4,7} (шина данных А) и {2,3,5,7,8} (шина данных В), на следующем такте на шине данных С получен результат, множество {2,3,7};

Такт 2: пересечение множеств {1,6} (шина данных А) и {2,6,7,8} (шина данных В), на следующем такте на шине данных С получен результат, множество {6};

Такт 3: пересечение множеств {1,2,3,7,8} (шина данных А) и {3,4} (шина данных В), на следующем такте на шине данных С получен результат, множество {3}.

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

П.1.5. ОПЕРАЦИЯ СИММЕТРИЧЕСКАЯ РАЗНОСТЬ МНОЖЕСТВ

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

А А В

Рис. П. 1.19. Диаграмма Эйлера-Вена для пересечения двух множеств

Рассмотрим алгоритм симметрической разности множеств А{а1, а2, а3 ... ап} и В{Ь1, Ь2, Ь3 ... Ьт} во множество С{с1, с2, с3 ... ск}, как он реализуется в классических вычислительных системах, где п и т - мощности множеств А и В соответственно. Обозначается как С - ААВ.

1. Ввод множеств А и В;

2. 1=1, к=1;

3. Если (1=т+1), то перейти к пункту 12;

4. ]=1, £=0;

5. Если 0=п+1) или £=1, то перейти к пункту 9;

6. Если а,=Ь1, то £=1;

7. ]=]+1;

8. Перейти к пункту 5;

9. Если 1=0, то ск= Ь (добавить во множество С элемент Ь^, к=к+1;

10. 1=1+1;

11. Перейти к пункту 3;

12. ]=1;

13. Если (]=п+1), то перейти к пункту 22;

14. 1=1, 1=0;

15. Если (1=т+1) или 1=1, то перейти к пункту 19;

16. Если а,=Ь1, то 1=1;

17. 1=1+1;

18. Перейти к пункту 15;

19. Если 1=0, то ск= а] (добавить во множество С элемент а^, к=к+1;

20. ]=]+1;

21. Перейти к пункту 13;

22. Вывод множества С.

Временная диаграмма работы данного алгоритма представлена на рис. П. 1.20.

Рис. П. 1.20. Временная диаграмма симметрической разности множеств

Вычислительная сложность операции пересечения двух множеств составляет й(т • п).

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

множества, если равен «1», означает, что элемент принадлежит первому множеству; «0» означает, что элемент принадлежит второму, у_геу2 - текущий элемент из обратного потока, уа11ё_геу2 - признак наличия элемента в обратном потоке, £и11х - признак наличия элемента сх в данном узле. После того как прямой поток прошел через все вычислительные узлы (их количество определяется максимальной мощностью множества сх) от первого вычислительного узла к последнему, поток проходит по всем вычислительным узлам повторно, но в обратном направлении от последнего вычислительного узла к первому, поэтому поток после такого разворота был назван обратным потоком элементов.

1. Если сх=уу, то £1=1, иначе £1=0 (сравниваем элемент из прямого потока с содержимым ячейки);

2. Если уа11ёу=1 и £1а§=1 и £и11х=0, то сх=уу и £и11х=1 (добавляем элемент из прямого потока в ячейку, если ячейка свободна и элемент принадлежит первому множеству);

3. Если (£1=1 и £и11х=1) или (£1а§=1 и £и11х=0), то уа11ёу+1=0, иначе уа11ёу+1=уа11ёу (удаляем элемент из прямого потока, если он совпал с элементом в ячейке или был добавлен в ячейку);

4. Если уа11ё_геу2=1 и £и11х=0, то сх=уу и £и11х=1 (добавляем элемент из обратного потока в ячейку, если ячейка свободна);

5. Если уа11ё_геу2=1 и £и11х=1, то уа11ё_геу2+1=1, иначе уа11ё_геу2+1=0 (удаляем элемент из обратного потока, если он был добавлен в ячейку);

6. Если £1=1 и уа11ёу=1, то £и11х=0 (удаляем элемент из ячейки, если он совпал с элементом из прямого потока).

Для реализации данного алгоритма была синтезирована схема блока обработки одного элемента множества «Ь1оск_се11_вутт_ё1££» представленная на рис. П. 1.21.

Рис. П. 1.21. Структурная схема блока обработки элемента «Ь1оск_се11_вутт_ё1££»

Временная диаграмма данного блока представлена на рис. П. 1.22. В данном примере происходит следующее.

Такт 1: Удаление из ячейки сх элемента «Ь», так как данный элемент присутствует во втором множестве;

Такт 2: Добавление в освободившуюся на предыдущем такте ячейку элемента «£» из обратного потока и удаление его из этого же потока;

Такт 3, такт 4: удаления/добавления отсутствуют.

Рис. П. 1.22. Временная диаграмма работы блока «Ыock_cell_symm_diff»

В общем виде структура соединения блоков «block_cell_symm_diff» представлена на рис. П. 1.23.

block_cell_symm_diff block_cell_symm_diff block_cell_symm_diff block_cell_symm_diff

Уь У2 > Уз У4. У к.

АайД) ,,, ^аЯк > Ск УгеО

С1 г ^ к С2 г У^ к-1 Сз У^ к-2 Vrev 2

Рис. П. 1.23. Структурная схема операции добавления потока элементов во

множество

Конвейер состоит из прямого V и обратного Угет канала данных, которые проходят через все блоки обработки элементов «block_cell_symm_diff». Элементы из каналов сравниваются с содержимым ячейки, если произошло совпадение, то

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

Для того чтобы выполнить операцию симметрическая разность множеств А и В, необходимо в прямой поток V вначале подать все элементы первого множества с признаком йа§=1, затем подать все элементы второго множества с признаком Аа§=0. После того как все элементы исходных множеств пройдут через канал, в ячейках блоков «Ь1оск_се11_вушш_ё1£Г» сформируется результат операции симметрическая разность - множество С.

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

На основании четвертого принципа, приведённого в главе 1 диссертации, следует разработать библиотечный элемент, который будет выполнять операцию симметрической разности множеств с использованием битового представления множеств. Тогда для реализации операции симметрической разности множеств А и В достаточно будет произвести сложение по модулю 2 битовых векторов соответствующих данным множествам, результатом будет битовый вектор результирующего множества С. Схема и диаграмма битовой реализации операции симметрической разности двух множеств представлены на рис. П. 1.24.

С1оск I_I I_I I_I

А <01110010Х10000100ХТТ100011>

в с

<01101011X01000111X00110000)-

<00011001XI 1оооо11ХТТ01оо11>

Рис. П. 1.24. Структурная схема и временная диаграмма операции симметрической разности двух множеств

На диаграмме показана следующая ситуация.

Такт 1: симметрическая разность множеств {2,3,4,7} (шина данных А) и {2,3,5,7,8} (шина данных В), на следующем такте на шине данных С получен результат, множество {4,5,8};

Такт 2: симметрическая разность множеств {1,6} (шина данных А) и {2,6,7,8} (шина данных В), на следующем такте на шине данных С получен результат, множество {1,2,7,8};

Такт 3: симметрическая разность множеств {1,2,3,7,8} (шина данных А) и {3,4} (шина данных В), на следующем такте на шине данных С получен результат, множество {1,2,4,7,8}.

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

ПРИЛОЖЕНИЕ 2

ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ВРЕМЕНИ РЕШЕНИЯ ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ КЛИК ГРАФА НА СОВРЕМЕННОМ ПРОЦЕССОРЕ

КАСАРКИН АЛЕКСЕЙ ВИКТОРОВИЧ

МЕТОДЫ И СРЕДСТВА СОЗДАНИЯ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ПРОГРАММ ДЛЯ РЕШЕНИЯ ГРАФОВЫХ ^-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

05.13.11 - Математическое и программное обеспечение вычислительных машин,

комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор Левин И.И.

П.2. ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ВРЕМЕНИ РЕШЕНИЯ ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ КЛИК ГРАФА НА СОВРЕМЕННОМ ПРОЦЕССОРЕ

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

С

с

Старт

1

Ьгоп

3

Ввод 7 ж /

a[size,size] /

ч *

K[0..size]=0,1...size

1 Г

bron(full,K,full)

1 Г

/ВыводV

С