Методы и средства обработки больших разреженных неструктурированных матриц на реконфигурируемых вычислительных системах тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Подопригора Александр Владимирович

• Подопригора Александр Владимирович
• кандидат наук
• 2024

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

ВВЕДЕНИЕ

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.3 Библиотека ускоренных базовых операций обработки БРН-матриц на РВС

3.4 Выводы

4. РЕШЕНИЕ ПРИКЛАДНЫХ ЗАДАЧ ОБРАБОТКИ БРН-МАТРИЦ НА РВС

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

4.2 Задача решения СЛАУ с БРН-матрицей коэффициентов на РВС

4.3 Задача нахождения собственных векторов с БРН-матрицами на РВС

4.4 Выводы

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

229

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

ВВЕДЕНИЕ

Актуальность темы исследования. В различных областях науки и техники, таких как машинное обучение, генетика, электротехника, экономика, социология, широко применяются методы математического моделирования объектов и процессов. [1,2]. Цифровой образ модели в вычислительной системе хранится в виде матрицы [3,4]. Матрица это -структурированное представление данных в виде прямоугольной таблицы элементов, в которой на пересечении строк и столбцов находятся элементы. Эффективная обработка матриц с использованием вычислительных систем должна учитывать все значащие элементы структуры, однако структура матрицы может быть разреженной. Разреженной называется матрица, которая содержит большое количество нулевых элементов относительно общего количество элементов. Точного математического определения разреженной матрицы не существует, в общем случае понятно, что число ненулевых элементов для матрицы п-го порядка обозначается как О(п) [5].

В процессе анализа сложных вычислительных задач, связанных с разработкой технических комплексов и построением экономических, социальных и естественных моделей [6], было выявлено, что плотность матрицы или количество ненулевых элементов не превышает 10% от общего числа элементов. Более того, в процессе моделирования масштабных задач возникают матрицы большой размерности, портреты которых не имеют видимой структуры.

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

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

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

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

для кэша памяти, формат хранения разреженных данных ELLPACK и т.д.), используемых для разного рода аппаратных средств, таких как CPU (central processing unit), GPU (graphics processing unit), FPGA (field-programmable gate array).

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

Использование алгоритмы оптимизации сводятся к поиску баланса скорости работы памяти и процессора. При обработке БРН матриц на кластерных МВС реализация алгоритмов становится недостаточно эффективной из-за потребности помещать большое количество неструктурированных данных в память процессора при недостающей скорости передачи данных. В результате производительность кластерной МВС на задаче обработки неструктурированных матриц не превышает 15% от пиковой. Использование специализированных библиотек, в которых используются методы распараллеливания вычислений и форматы представления неструктурированных разреженных матриц, ведет к увеличению производительности, однако в сравнении с пиковой производительностью вычислительной системы она не является существенной [8,9,10].

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

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

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

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

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

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

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

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

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

1) провести анализ существующих методов и средств, потенциально позволяющих обрабатывать большие разреженные неструктурированные матрицы;

2) разработать метод создания параллельно-конвейерных программ с постоянной интенсивностью потоков данных при обработке БРН-матриц на РВС;

3) разработать метод создания параллельно-конвейерных программ с максимальной постоянной интенсивностью потоков данных при обработке БРН-матриц на РВС;

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

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

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

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

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

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

- параллельно-конвейерный алгоритм решения СЛАУ методом Якоби с БРН-матрицей коэффициентов при использовании библиотеки ускоренных базовых операций с БРН-матрицами для реконфигурируемых вычислительных систем (РВС), отличающийся распараллеливанием по итерациям информационного графа алгоритма;

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

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

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

1. Разработанный метод обработки БРН-матриц, при решении задач линейной алгебры позволяет получать соотношение реальной производительности РВС относительно пиковой порядка 0.5.

2. Разработанный метод ускоренной обработки БРН-матриц при решении задач линейной алгебры позволяет получать соотношение реальной производительности РВС относительно пиковой, близкое к 1.

3. Разработана библиотека ускоренных базовых операций с БРН-матрицами на основании метода ускоренной обработки БРН-матриц на РВС. Библиотека включает в себя операцию сложения БРН-матриц, операцию произведения Адамара БРН-матриц, операцию скалярного умножения БРН-матриц, операцию умножения БРН-матрицы на плотный вектор и операцию транспонирования БРН-матрицы. Библиотека базовых операций над БРН-матрицами была реализована на языке VHDL для ПЛИС семейства UltraScale и UltraScale+;

4. Синтезирована параллельно-конвейерная программа решения СЛАУ методом Якоби с БРН-матрицей коэффициентов (Свидетельство о государственной регистрации программы для ЭВМ № 2024613962, РФ), для которой использовалась операция умножения БРН-матрицы на вектор из библиотеки ускоренных базовых операций с БРН-матрицами. Полученная вычислительная структура базового подграфа задачи решения СЛАУ методом Якоби была распараллелена по слоям и по итерациям информационного графа и показала реальную производительность РВС «Арктур» порядка 87% от пиковой и близкий к линейному рост при увеличении ресурса РВС. Сравнение реальной производительности РВС «Арктур» с графическим процессором Nvidia Tesla k40 показало эффективность использования разработанного метода ускоренной обработки БРН-матриц на РВС. Ускорение вычислений при решении СЛАУ методом Якоби одной ПЛИС РВБ «Арктур» к графическому ускорителю Nvidia Tesla k40 составило 134 раз.

5. Синтезирована параллельно-конвейерная программа для поиска собственных векторов степенным методом с БРН-матрицей коэффициентов (Свидетельство о государственной регистрации программы для ЭВМ № 2024614041, РФ), для которой использовались операции умножения БРН-матрицы на плотный вектор и умножения БРН-матриц из библиотеки ускоренных базовых операций с БРН-матрацами. Полученная вычислительная структура базового подграфа задачи поиска собственных

векторов степенным методом с БРН-матрицей коэффициентов была распараллелена по слоям и по итерациям информационного графа и показала реальную производительность РВС «Арктур» порядка 90% от пиковой и близкий к линейному рост при увеличении ресурса РВС. Сравнение реальной производительности РВС с кластерным суперкомпьютером «Фугаку» для поиска собственных векторов степенным методом для алгоритма PageRank показал большее ускорение при распараллеливании задачи. Ускорение вычислений при поиске собственных векторов степенным методом одной ПЛИС РВБ «Арктур» к одному процессору суперкомпьютера «Фугаку» Fujitsu A64FX составило 39 раз.

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

В НИЦ СЭ и НК, акт о внедрении от «21» августа 2023 г., утвержден техническим директором НИЦ СЭ и НК. Материалы диссертации использовались при выполнении ряда НИОКР, а именно:

1) ОКР «Разработка высокопроизводительного реконфигурируемого компьютера на основе ПЛИС UltraScale», шифр «Терциус»;

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

3) НИОКР «Разработка нового поколения программного обеспечения РВС для решения ресурсоемких научно-технических задач различных предметных областей», шифр «Поколение».

В учебном процессе кафедры интеллектуальных и многопроцессорных систем (ИМС) Института компьютерных технологий и информационной безопасности (ИКТИБ) Южного федерального университета (ЮФУ), акт от 17 мая 2024 г., утвержден директором ИКТИБ ЮФУ. Материалы диссертации используются в лекционном курсе по дисциплине «ПЛИС-технологии и методы создания эффективных прикладных программ для

РВС» (тема 3 «Методы проектирования устройств на ПЛИС с использованием 1Р ядер» в рамках модуля 2 «Организация РВС на ПЛИС») для подготовки магистров направления подготовки 01.04.02 Прикладная математика и информатика («Прикладная математика для высокопроизводительных вычислительных систем»).

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

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

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских научно-технических конференциях: Суперкомпьютерные технологии (СКТ-2018): 5-я Всероссийская научно-техническая конференция, Дивноморское, Геленджик, 2018; XII Мультиконференция по проблемам управления (МКПУ-2019) Дивноморское, г. Геленджик, 2019; XVI Ежегодная молодежная научная конференция «Юг России: вызовы времени, открытия, перспективы» г. Ростов-на-Дону, 2020; XIV Всероссийская мультиконференция по проблемам управления (МКПУ-2021) 2021; XVII Ежегодная молодежная научная конференция «Наука и технологии юга России» г. Ростов-на-Дону, 2021; XVIII Ежегодная молодежная научная конференция «Наука юга России: достижения и перспективы» г. Ростов-на-Дону, 2022; Всероссийская научно-техническая конференция «Многопроцессорные вычислительные и управляющие системы», г.

Таганрог, 2022; XIX Ежегодная молодежная научная конференция «Угрозы и риски на Юге России в условиях геополитического кризиса» г. Ростов-на-Дону, 2023; Всероссийская Мультиконференция по проблемам управления (МКПУ-2023), г. Волгоград 2023 г.

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

1. Левин И.И. Модифицированный метод обработки больших разреженных неструктурированных матриц на реконфигурируемых вычислительных системах / И.И. Левин, А.В. Подопригора // Вычислительные методы и программирование. 2024.25, № 2. С.-142-154. DOI: 10.26089/ЫитМе^25г212. (ведущий рецензируемый журнал, входит в перечень ВАК категории К1).

2. Подопригора А.В. Решение разреженных СЛАУ большой и сверхбольшой размерности многосеточным методом на РВС / А.В. Подопригора, М.Д. Чекина // Известия ЮФУ. Технические науки. - 2018. -№ 8 (202). - С. 212-218. - 001: 10.23683/2311-3103-2018-8-212-221 (ведущий рецензируемый журнал, входящий в Перечень ВАК РФ категории К2).

3. Подопригора А.В. Метод организации дискретно-событийных вычислений для обработки больших разреженных неструктурированных матриц на РВС / А.В. Подопригора // Известия ЮФУ. Технические науки. -2021. - № 7 (224). - С. 189-197. - Б01: 10.18522/2311-3103-2021-7-189-197 (ведущий рецензируемый журнал, входящий в Перечень ВАК РФ категории К2).

4. Подопригора А.В. Метод распараллеливания по базовым макрооперациям для обработки больших разреженных неструктурированных матриц на РВС / И.И. Левин, А.В. Подопригора // Известия ЮФУ. Технические науки. - 2022. - № 6 (230). - С. 72-83. - Б01: 10.18522/23113103-2022-6-72-83 (ведущий рецензируемый журнал, входящий в Перечень ВАК РФ категории К2).

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

6. Свидетельство о государственной регистрации программ для ЭВМ № 2024613962, РФ. Программа решения СЛАУ методом Якоби/ А.В. Подопригора, И.И. Левин // Зарегистр. в Реестре программ для ЭВМ 19.02.2024 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

Личный вклад автора. Все представленные в диссертации результаты получены автором лично.

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

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

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

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

Результаты, выдвигаемые для защиты:

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

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

- параллельно-конвейерный алгоритм решения СЛАУ методом Якоби с БРН-матрицей коэффициентов при использовании библиотеки ускоренных базовых операций с БРН-матрицами для реконфигурируемых вычислительных систем (РВС), отличающийся распараллеливанием по итерациям информационного графа алгоритма;

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

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

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

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

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

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

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

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

Описан метод, который позволяет получить сбалансированную вычислительную структуру и прикладную конвейерную программу обработки БРН-матриц. Этот метод включает в себя структурную организацию вычислений, специальный формат хранения БРН-матриц -модифицированный ELLPACK, дискретно-событийное преобразование входного потока данных для синхронизации ненулевых элементов матрицы при выполнении матричных операций и баланс интенсивности входного потока ненулевых элементов относительно интенсивности обработки данных.

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

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

Список литературы диссертационного исследования кандидат наук Подопригора Александр Владимирович, 2024 год

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

1. Christoph G. Coupling DuMuX and DUNE-PDELab to investigate evaporation at the interface between Darcy and Navier-Stokes flow Christoph G.,Thomas F.,Bernd F.,Rainer H. Stuttgart Research Centre for Simulation Technology (SRC SimTech);2017 pp -16.

2. Sarda P., Development of a Dynamic Model and Control System for Load-Following Studies of Supercritical Pulverized Coal Power Plants Sarda P., Hedrick E., Reynolds K., Bhattacharyya D., Zitney S., Omell B. Special Issue "Modeling and Simulation of Energy Systems" https://doi.org/10.3390/pr6110226 17 November 2018.

3. Жуков В.Т. Параллельный многосеточный метод для разностных эллиптических уравнений. Часть I. Основные элементы алгоритма/ В.Т. Жуков, Н.Д. Новикова, О.Б. Феодоритова // Препринты ИПМ им. М.В. Келдыша, 2012. - № 30. - 32 с.

4. Самарский А. А. Введение в численные методы. Спб.: изд.«Лань», 2005г. - 288 с.

5. Тьюарсон Р.П. Разреженные матрицы. (Sparse Matrices, 1973)/ П. Тьюарсон (Reginald Prabhakar Tewarson). Перевод с английского Э.М. Пейсаховича под редакцией Х.Д. Икрамова. Художник К. Сиротов. (Москва: Издательство «Мир»: Редакция литературы по математическим наукам, 1977).

6. Ахунов Р.Р. Многократное решение систем линейных алгебраических уравнений итерационными методами с предобусловливанием в задачах электромагнитной совместимости (Монография) / Р.Р. Ахунов, С.П. Куксенко, Т.Р. Газизов, П.Е. // Орлов Томск: Изд-во Томск. гос. ун-та систем упр. и радиоэлектроники, 2015. - 152 с. ISBN 978-5-86889-720-7.

7. Абухазим М.М. Методы моделирования систем на основе методов декомпозиции и компактной обработки разреженных матриц [Текст]

/ В.Н.Гридин, В.И. Анисимов, М.М. Абухазим //Информационные технологии в проектировании и производстве № 1 2016 с.3-8.

8. Bethune I. Porting of the DBCSR library for Sparse Matrix-Matrix Multiplications to Intel Xeon Phi systems / I. Bethune, A. Gloss, J. Hutter, A. Lazzaro, H. Pabst, F. Reid - Submitted to the ParCo2017 conference. Distributed, Parallel, and Cluster Computing (cs.DC) - 2017 Italy Bologna 12-15 September 2017 DOI: 10.3233/978-1-61499-843-3-47.

9. Chung E. S. An FPGA Drop-In Replacement for Universal Matrix-Vector Multiplication E. S. Chung, J. D. Davis, Kestur Computer Architecture and Reconfigurable Logic (CARL 2012) D0I:10.1109/FCCM.2012.12.

10. Kunchum R. On Improving Sparse Matrix-Matrix Multiplication on GPUs (Thesis). The Ohio State University. - 2017. - P. 36-42 -https://etd.ohiolink.edu/!etd.send_file?accession=osu1492694387445938&disposit ion=inline.

11. Максимов Д.Ю Исследование нелинейных многосеточных методов решения задач однофазной фильтрации/ Д.Ю. Максимов, М.А. Филатов // Препринты ИПМ им. М. В. Келдыша, 2011. - № 43. - 26 с. URL: http://library.keldysh.ru/preprint.asp?id=2011-43 (дата обращения: 12.10.2017).

12. Alegna A., Asymmetric Matrix-Valued Covariances for Multivariate Random Fields on Spheres / A. Alegr'ia, E. Porcu, R. Furrer // Journal of Statistical Computation and Simulation 88(10) DOI: 10.1080/00949655.2017.1406488 June 2017.

13. Weber V. Semiempirical Molecular Dynamics (SEMD) I: Midpoint-Based Parallel Sparse Matrix-Matrix Multiplication Algorithm for Matrices with Decay / V. Weber, T. Laino, A. Pozdneev, I. Fedulova, A. Curioni // Journal of chemical theory and computation 2015 Jul 14;11(7):3145-52. DOI: 10.1021/ACS.JCTC.5B00382. EPUB 2015 Jun 17.

14. Zangiabadi E. Computational Fluid Dynamics and Visualization of Coastal Flows in Tidal Channels Supporting Ocean Energy Development E. Zangiabadi, M. Edmunds, I. A. Fairley, M. Togneri, A. J. Williams, I. Masters, N.

Croft // Tools and Techniques for Economic Delivery of Ocean Energy 18 June 2015 5997-6012; D0I:10.3390/EN8065997.

15. Самарский А.А. Введение в теорию разностных схем. - М.: Наука, 1971. - 552 с. Научная библиотека диссертаций и авторефератов disserCat http://www.dissercat.com/content/razrabotka-i-issledovanie-ekonomichnykh-algoritmov-resheniya-setochnykh-zadach-na-klastere-r#ixzz5Wv0BEVuA (дата обращения: 23.11.2023).

16. Сухинов А. И. Математическое моделирование условий формирования заморов в мелководных водоемах на многопроцессорной вычислительной системе / А.И. Сухинов, А.В. Никитина, А.Е. Чистяков, И.С. Семенов // Выч. мет. программирование, 14:1 (2013), 103-112.

17. Сухинов А.И. Математическое моделирование транспорта наносов в прибрежных водных системах на многопроцессорной вычислительной системе/ А.И. Сухинов, А.Е. Чистяков, Е.А. Проценко //статья - Выч. мет. программирование, 15:4 (2014), 610-620.

18. Favino M. Multiscale modeling, discretization, and algorithms: a survey in biomechanics / M. Favino, A. Quaglino, S. Pozzi, I. V.Pivkin, R. Krause // Institute of Computational Science, Universifa della Svizzera italiana https://www.researchgate.net/publication/326066080 (дата обращения: 12.07.2023).

19. Jones I. A note on the use of non-uniform grids in finite difference calculations. Boundary and Interior Layers / I. Jones, C. Thompson// Computational and Asymptotic Methods. 1980 - 332-341 pp.

20. Тихонов, А.Н. Уравнения математической физики [Электронный ресурс] / А.Н. Тихонов, А.А. Самарский. - Москва: Издательство Московского университета, 1999. 6-е изд. - 798 с. Научная библиотека диссертаций и авторефератов disserCat. - URL: https://elar.urfu.ru/bitstream/10995/42951/1/978-5-321-02475-1_2016.pdf (дата обращения: 15.10.2022).

21. Davis T. The University of Florida Sparse Matrix Collection / T. Davis, Y. Hu. //New York ACM Transactions on Mathematical Software 38, 1, Article, 2011. - 1-25 pp.

22. База разреженных матриц. Матрица группы Williams - webbase-1M. by T. Davis, https://www.cise.ufl.edu/research/sparse/matrices/Williams/webbase-1M.html (дата обращения: 10.11.2023).

23. Duff I., Users' guide for the Harwell-Boeing sparse matrix collection (Release 1) / I. Duff, R. Grimes, J. G. Lewis // Technical Report TR/PA/92/86 from CERFACS, 42 Ave G Coriolis, 31057 Toulouse Cedex, France 1992 - RAL 92-086.

24. Batagelj V. Analyzing the Structure of U.S. Patents Network / V. Batagelj, N. Kej^zar, S. Korenjak-Cerne, M. Zaver^snik // Data Science and Classification DOI:10.1007/3-540-34416-0_16 pp.141-148 January 2006.

25. Dixon P.B. ORANI, A General Equilibrium Model of the Australian Economy: Current Specification and Illustrations of use for Policy Analysis / P.B. Dixon, B.R. Parmenter, G.J. Ryland, J. Sutton, // Vol. 2 of the First Progress Report of the IMPACT Project, Australian Government Publishing Service, Canberra, November 2000 - 297.

26. Абухазим М.М. Методы повышения производительности систем моделирования больших интегральных схем на основе компактной обработки разреженных матриц [Текст] / В.Н. Гридин, В.И. Анисимов, М.М. Абухазим // Известия ЮФУ. Технические науки. 2018 №4 с.24-38 УДК 681.5.01:658.512.2.

27. Pozdneev A. IBM Blue Gene: Architecture and Software Overview International Summer Supercomputing Academy June 23, 2017.

28. Воеводин В.В. Характеристики типовых алгоритмических структур // Вестник Нижегородского университета им. Н.И. Лобачевского. -Нижний Новгород: Изд-во Нижегородского ун-та,2011. - Том1, No2. С.181 -189.

29. Nvidia. NVIDIA TITAN V // Copyright © 2018 NVIDIA Corporation https://www.nvidia.com/ru-ru/titan/titan-v/ (дата обращения: 10.11.2023).

30. Сударева О.Ю. Встречная оптимизация класса задач трехмерного моделирования для архитектур многоядерных процессов // На правах рукописи. - 2018. - С. 101-118. http://www.ispras.ru/dcouncil/docs/diss/2018/sudareva/dissertacija-sudareva.pdf (дата обращения: 23.11.2023).

31. Wu X. A Parallel Generator of Non-Hermitian Matrices computed from Given Spectra / X. Wu, S. Petiton, Y. Lu. // A VECPAR 2018: 13th International Meeting on High Performance Computing for Computational Science, Sep 2018, Sao Paulo, Brazil. ffhal-01867967.

32. Lazzaro A. Increasing the Efficiency of Sparse Matrix-Matrix Multiplication with a 2.5D Algorithm and One-Sided MPI A. Lazzaro, J. V. Vondele, J. Hutter, O. Schuett // In Proceedings of PASC '17, Lugano, Switzerland, June 26-28, 2017, 10 pages, 4 figures https://doi.org/10.48550/arXiv.1705.10218.

33. Dyer T. Bounded Verification of Sparse Matrix Computations / T. Dyer, A. Altuntas, J. Baugh // 2019 IEEE/ACM Third International Workshop on Software Correctness for HPC Applications (Correctness) DOI:10.1109/CORRECTNESS49594.2019.00010 November 2019.

34. Townsend K. R., Computing SpMV on FPGAs Graduate Theses and Dissertations. 15227. https://lib.dr.iastate.edu/etd/15227 2016 pp 4 -17.

35. Kestyn J. PFEAST: A High Performance Sparse Eigenvalue Solver Using Distributed-Memory Linear Solvers / J. Kestyn, V. Kalantzis, E. Polizzi, Y. // Saad Conference: SC16: International Conference for High Performance Computing, Networking, Storage and Analysis November 2016 DOI:10.1109/SC.2016.15.

36. Demchik V. Out-of-core singular value decomposition / V. Demchik, M. Bac^ak, S. Bordag // Mathematical Software (cs.MS); Numerical Analysis (math.NA) https://doi.org/10.48550/arXiv.1907.06470 Jul 2019.

37. Somers G. W. Acceleration of Block-Aware Matrix Factorization on Heterogeneous Platforms Master of Applied Science degree in Electrical and Computer Engineering / School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada Ottawa, Canada, 2016-32-39.

38. Golnari P. Sparse Matrix to Matrix Multiplication: A Representation and Architecture for Acceleration Hardware Architecture (cs.AR) June 2019 https://doi.org/10.48550/arXiv.1906.00327.

39. Rennich S. Accelerating Sparse Cholesky Factorization on GPUs / S. Rennich, D. Stosic, T. Davis // Parallel Computing 59 June 2016 DOI:10.1016/J.PARCO.2016.06.004.

40. Параллельные вычисления CUDA / NVIDIA Corporation. - 2018. -URL: http://www.nvidia.ru/object/cuda-parallel-computing-ru.html (дата обращения: 18.10.2022).

41. Yang C. Design Principles for Sparse Matrix Multiplication on the GPU / C. Yang, A. Buluc, J. Owens // Turin: International European Conference on Parallel and Distributed Computing, - 2018. - p. 12.

42. Fowers J. A High Memory Bandwidth FPGA Accelerator for Sparse Matrix-Vector Multiplication / J. Fowers, K. Ovtcharov, K. Strauss, E. S. Chung, G. Stitt // 2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines Published 11 May 2014 DOI:10.1109/FCCM.2014.23.

43. Georgopoulos L. Enhancing multi-threaded sparse matrix multiplication for knowledge graph oriented algorithms and analytics IBM Research / L. Georgopoulos, A. Sobczyk, D. Christofidellis, M. Dolfi, C. Auer, P. Staar, C. Bekas // Zurich Saumerstrasse 4 CH-8803 Ruschlikon Switzerland 2019 - 11 p.

44. Сорокин Д.А. Методы решения задач с переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах: диссертация на соискание ученой степени кандидата технических наук, по специальности 05.13.11 "Математическое и программное

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

45. Гузик В.Ф. Реконфигурируемые вычислительные системы / В.Ф. Гузик, И.А. Каляев, И.И. Левин // под редакцией И.А. Каляева. Южный федеральный университет. - Таганрог: Издательство Южного Федерального Университета, 2016 - 472 с.

46. Kalyaev, I.A. FPGA-based reconfigurable computer systems / I.A. Kalyaev, I.I. Levin; A.I. Dordopulo, L.M. Slasten // Science and Information Conference - 2013 - SAI 2013 pp. 148-155.

47. Беликов Д.А Высокопроизводительные вычисления на кластерах Учебное пособие / под ред. А.В. Старченко. Томск: Изд-во Томского университета, 2008. - 198 с.

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

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

50. НИЦ СЭ и НК. Терциус 2. © Copyright 2004-2023. ООО "НИЦ супер-ЭВМ и нейрокомпьютеров" http://superevm.ru/index.php?page=tertsius-2 (дата обращения: 2.05.2023).

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

52. Левин И.И. Реконфигурируемые компьютеры на основе ПЛИС 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.

53. Левин И.И Решение задачи LU-декомпозиции на реконфигурируемых вычислительных системах: оценка и перспективы / И.И. Левин, А.В. Пелипец, Д.А. Сорокин // Известия ЮФУ. Технические науки. 2015. № 7 (168). С. 62-70.

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

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

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

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

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

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

60. Дордопуло А.И. Программирование вычислительных систем гибридного типа на основе метода редукции производительности/ А.И. Дордопуло, И.И. Левин, И.А. Каляев, В.А. Гудков, А.А. Гуленок // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. - С. 131-140.

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

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

63. Подопригора А.В. Решение больших и сверхбольших разреженных СЛАУ на реконфигурируемых вычислительных системах[Тезисы] / А.В. Подопригора, М.Д. Чекина //Суперкомпьютерные технологии (СКТ-2018): материалы 5-ой Всероссийской научно-технической конференции: в 2 т. (17-22 сентября 2018 г.)с. 201 - Ростов-на-дону: Издательство Южного федерального университета, 2018.

64. Подопригора А.В. Методы и средства обработки больших разреженных матриц на реконфигурируемой вычислительной системе / XVI Ежегодная молодежная научная конференция «Юг России: вызовы времени,

открытия, перспективы»: материалы конференции (г. Ростов-на-Дону, 13-28 апреля 2020 г.). - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2020. - 168 с. - ISBN 978-5-4358-0196-5.

65. Писсанецки С. Технология разреженных матриц: Пер. с англ.— М.: Мир, 1988. —410 с , ил. ISBN 5-03-000960-4.

66. Подопригора А.В. Управление потоками данных при решении большой разреженной СЛАУ многосеточным методом на реконфигурируемых вычислительных системах / А.В. Подопригора, Д.А. Сорокин // XII мультиконференция по проблемам управления (МКПУ-2019) : материалы XII мультиконференции (Дивноморское, Геленджик, 23-28 сентября 2019 г.) : в 4 т. / Южный федеральный университет [редкол.: И.А. Каляев, В.Г. Пешехонов и др.]. - Ростов-на-Дону; Таганрог: Издательство Южного федерального университета, 2019.ISBN 978-5-9275-3188-2 Т. 3: -232 с. ISBN 978-5-9275-3191-2 (Т. 3) С 120 -122.

67. Клейнрок Л. Теория массового обслуживания / пер. с англ. И. И. Грушко ; под ред. В. И. Неймана М.: Машиностроение, 1979 432 с.

68. Подопригора А.В. Метод организации дискретно-событийных вычислений для обработки больших разреженных неструктурированных матриц на РВС Известия ЮФУ. Технические науки № 7 (224). 2021 DOI 10.18522/2311-3103-2021-7-189-197 с. 189 - 197.

69. Подопригора А.В. Объединение базовых БРН-матричных макроопераций / А.В. Подопригора "Многопроцессорные вычислительные и управляющие системы" материалы Всероссийской научно-технической конференции (г.Таганрог 27-30 июня 2022 г) Ростов-на-Дону - Таганрог: Издательство Южного федерального университета, 2022 ISBN 978-5-92754144-7 - 252 с. - С. 103.

70. Коннов, А. Л. Методы расчета показателей производительности сетей ЭВМ с неоднородным трафиком / А. Л. Коннов, Ю. А. Ушаков; Оренбургский гос. ун-т. - Оренбург : ОГУ, 2013. - 139 с.

71. Подопригора А.В. Принцип распараллеливания по базовым макрооперациям для задачи обработки больших разреженных неструктурированных матриц на РВС / Всероссийской конференции с международным участием «Угрозы и риски на Юге России в условиях геополитического кризиса»: материалы докладов (г. Ростов-на-Дону, 15-18 марта, 26-29 апреля 2023 г.); XIX Ежегодной молодежной научной конференции «Достижения и перспективы научных исследований молодых ученых Юга России»: тезисы докладов (г. Ростов-на-Дону, 17-28 апреля 2023 г.) / [гл. ред. акад. Г.Г. Матишов]. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2023. - 352 с. - ISBN 978-5-4358-0251-1.

72. Дордопуло А.И. Семейство многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой / А.И. Дордопуло, И.А. Каляев, И.И. Левин, Е.А. Семерников // Многопроцессорные вычислительные и управляющие системы: Материалы научно-технической конференции. - Таганрог, 2007. - С. 11-17.

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

74. Подопригора А.В. Управление процессом обработки разреженных матриц в дискретно-событийных матричных операциях // XIV Всероссийская мультиконференция по проблемам управления (МКПУ-2021) : материалы XIV мультиконференции (Дивноморское, Геленджик, 27 сентября - 2 октября 2021 г.) : в 4 т. / Южный федеральный университет [редкол.: И. А. Каляев, В. Г. Пешехонов и др.]. - Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2021. ISBN 978-5-92753846-1 Т. 2: - 284 с. - С. 276-278.

75. Dongarra J. A Sparse Matrix Library in C++ for High Performance Architectures, (38K, compressed postscript.) / J. Dongarra, A. Lumsdaine, R. Pozo,

K. Remington // Proceedings of the Second Object Oriented Numerics Conference, pp. 214-218, 1994.

76. Davis T. Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, PA, 2006.

77. Sparse matrices (scipy.sparse) https://docs.scipy.org/doc/scipy/reference/sparse.html (дата обращения: 15.04.2023).

78. Подопригора А.В. Метод распараллеливания по базовым макрооперациям для обработки больших разреженных неструктурированных матриц на РВС / И.И. Левин, А.В. Подопригора // Известия ЮФУ. Технические науки № 6 (230). 2022 г DOI 10.18522/2311-3103-2022-6-72-83 -с. 72 - 83.

79. Доронченко Ю.И. Метод операционно-графового описания одновременных вычислений для многопроцессорных систем. // Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы 2007». - Таганрог: Изд-во ТТИ ЮФУ , 2007. - Т. 1. - С. 11-17.

80. Левин И.И. Модифицированный метод обработки больших разреженных неструктурированных матриц на реконфигурируемых вычислительных системах /И.И. Левин, А.В. Подопригора// Вычислительные методы и программирование. 2024.25, No 2. 142-154. doi 10.26089/NumMet.v25r212.

81. Подопригора А.В. Решение разреженных СЛАУ большой и сверхбольшой размерности многосеточным методом на РВС / А.В. Подопригора, М.Д. Чекина // Известия ЮФУ. Технические науки DOI 10.23683/2311-3103-2018-8-212-221 - с. 212 - 218.

82. Шуп Т.Е. Прикладные численные методы в физике и технике. -М.: Высшая школа, 1990, 255.

83. Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные структуры [Текст]: монография / И.А. Каляев, И.И. Левин,

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

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

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

86. Подопригора А.В. Общий подход к обработке больших разреженных неструктурированных матриц на РВС // XVII Ежегодная молодежная научная конференция «Наука и технологии Юга России»: тезисы докладов (Ростов-на-Дону, 15-30 апреля 2021 г). - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2021. - 348 с. - ISBN 978-5-4358-0209-2.

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

88. Касаркин А.В. Метод решения графовых NP-полных задач на реконфигурируемых вычислительных системах на основе принципа распараллеливания по итерациям // Известия ЮФУ. Технические науки. -2020. - №7 (217). - С. 121-129.

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

90. Коваленко А.Г. Структурно-процедурная реализация задачи фильтрации жидкости в пористой среде // Матер. Междунар. науч.-техн.

конф. "Многопроцессорные вычислительные и управляющие системы — 2007". Таганрог: Изд-во ТТИ ЮФУ, 2007. Т. 1. С. 293-297.

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

92. Алексеев К.Н. Методы и средства создания параллельно-конвейерных программ для решения задач реального времени на реконфигурируемых вычислительных системах: диссертация на соискание ученой степени кандидата технических наук, по специальности 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И. - Таганрог, 2020. - 213 с.

93. Подопригора А.В. Методы распараллеливания вычислений для обработки больших разреженных неструктурированных матриц на РВС / XVIII Ежегодная молодежная научная конференция «НАУКА ЮГА РОССИИ: ДОСТИЖЕНИЯ И ПЕРСПЕКТИВЫ» материалы конференции (г. Ростов-на-Дону, 18-29 апреля 2022 г.). - Ростов-на-Дону: Издательство ЮНЦ РАН, 2022. ISBN 978-5-4358-0233-7. - 298 с. - С.262.

94. Самарский А. А.Численные методы математической физики / А.А. Самарский, А.В. Гулин // - М : Науч. мир, 2003.

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

96. Гудков В.А. Расширения структурно-процедурного языка программирования ARGUS для многопроцессорных вычислительных систем

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

97. Левин И.И. Программирование перспективных вычислительных систем с реконфигурируемой архитектурой на языке COLAMO/ И.И. Левин, А.И. Дордопуло// Материалы XI международной научной и практической конференции «Современная европейская наука (Modern european science -2015)», 30 июня-7 июля 2015, Шеффилд, Англия. С. 3-9.

98. Kolodziej S. The SuiteSparse Matrix Collection Website Interface / S. P. Kolodziej, M. Aznaveh, M. Bullock, J. David, T.A. Davis, M. Henderson, Y. Hu, and R. Sandstrom // Journal of Open Source Software 4, 35 (March 2019) https://doi.org/10.21105/joss.01244 (дата обращения: 02.12.2023).

99. Chowa E. Using Jacobi Iterations and Blocking for Solving Sparse Triangular Systems in Incomplete Factorization Preconditioning / E. Chowa, H. Anztb, J. Scottd, J. Dongarra // Journal of Parallel and Distributed Computing April 30, 2018.

100. Whitepaper NVIDIA's Next Generation CUDATM Compute Architecture: Kepler TM GK110/210 2014 NVIDIA Corporation. https://www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/tesla-product-literature/NVIDIA-Kepler-GK 110-GK210-Architecture-Whitepaper.pdf (дата обращения: 7.07.2023).

101. Levin I. Design Technology for Reconfigurable Computer Systems with Immersion Cooling / I. Levin, A. Dordopulo, A. Fedorov, Y. Doronchenko // In: Voevodin V., Sobolev S. (eds) Supercomputing. RuSCDays 2018. Communications in Computer and Information Science, vol 965. Springer, Cham.

102. Левин И.И. Перспективные высокопроизводительные реконфигурируемые вычислители с иммерсионным охлаждением/ И.И. Левин, А.М. Федоров, Ю.И. Доронченко, М.К. Раскладкин // Известия ЮФУ. Технические науки. - Ростов/Д: Изд-во ЮФУ, 2020. - №7(2020). - С. 6-19.

DOI 10.18522/2311-3103-2020-7-6-19. http://www.izv-

tn.tti. sfedu.ru/index.php/izv_tn/article/view/427/559.

103. Беклемишев Д.В. Дополнительные главы линейной алгебры М.: Наука. Главная редакция физико-математической литературы, 1983. - 336 с.

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

105. Page L. The pagerank citation ranking: Bringing order to the web / L. Page, S. Brin, R. Motwani, T. Winograd// Tech. rep., Stanford InfoLab (1999).

106. Ma N. Bringing PAGERANK to the citation analysis / N. Ma, J. Guan, Y. Zhao//. Information Processing & Management 44(2), 800-810 (2008).

107. Klicpera J. Predict then propagate: Graph neural networks meet personalized pagerank /J. Klicpera, A Bojchevski., S. Gunnemann // arXiv preprint arXiv:1810.05997 (2018).

108. Vandromme M. Scaling the PageRank Algorithm for Very Large Graphs on the Fugaku Supercomputer M. Vandromme, J. Gurhem, M. Tsuji, S. Petiton, M. Sato // Computational Science - ICCS 2022 (pp.389-402) January 2022 DOI: 10.1007/978-3-031-08751-6_28.

109. Highlights - June 2023 [электронный ресурс]. - Режим доступа: https://www.top500.org/lists/top500/.

110. Sorokin A. Elements of a Digital Photonic Computer Dmitriy / D. A. Sorokin, A.V. Kasarkin, A.V. Podoprigora//Supercomputing frontiers and innovations DOI: https://doi.org/10.14529/jsfi2302 September 2023.

ПРИЛОЖЕНИЕ 1

БИБЛИОТЕКА БАЗОВЫХ ОПЕРАЦИЙ ОБРАБОТКИ БРН-МАТРИЦ

НА РВС.

ПОДОПРИГОРА АЛЕКСАНДР ВЛАДИМИРОВИЧ

МЕТОДЫ И СРЕДСТВА ОБРАБОТКИ БОЛЬШИХ РАЗРЕЖЕННЫХ НЕСТРУКТУРИРОВАННЫХ МАТРИЦ НА РЕКОНФИГУРИРУЕМОЙ

ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

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

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

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

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

Таганрог - 2024

П.1. БИБЛИОТЕКА БАЗОВЫХ ОПЕРАЦИЙ ОБРАБОТКИ БРН-МАТРИЦ

НА РВС

Алгоритм матричной операции векторного умножения БРН-матриц А и В (произведение Адамара)

Размерность БРН-матриц п х т, которая обозначается Q = |Л|х|Б|.

1. Установить значения индекса строки БРН-матрицы А I = 1;

2. Установить значения индекса строки БРН-матрицы В к = 1;

3. Установить значения индекса столбца БРН-матрицы А у = 1;

4. Установить значения индекса столбца БРН-матрицы В 1 = 1;

5. Получить элемент БРН-матрицы Ък,и

6. Получить элемент БРН-матрицы ау

7. Если полученный элемент БРН-матрицы А содержит признак конца матрицы = Д операция умножения типа Адамара завершена.

8. Если полученный элемент БРН-матрицы В содержит признак конца матрицы Ък,1 = Д операция умножения типа Адамара завершена.

9. Если полученный элемент БРН-матрицы А содержит признак конца строки матрицы а1у = ш, увеличить значение индекса строки I = I + 1для БРН-матрицы А и к = к + 1для БРН-матрицы В, перейти к пункту 3.

10. Если полученный элемент БРН-матрицы В содержит признак конца строки матрицы Ък1 = ш, увеличить значение индекса строки I = I + 1для БРН-матрицы А и к = к + 1для БРН-матрицы В, перейти к пункту 3.

11. Сравнить значения индекса столбцов I и у для ненулевых элементов аг,у и Ък,1.

12. Если I >], выполнить операцию ау х0, увеличить значение индекса столбца БРН-матрицы А у = у+1, загрузить элемент БРН-матрицы ау перейти к пункту 7.

13. Если I <у, выполнить операцию Ък,1 х0 увеличить значение индекса столбца БРН-матрицы В I = I + 1, загрузить элемент БРН-матрицы Ък1, перейти к пункту 7.

14. Если I = у, выполнить операцию ау хЬщ, записать результат операции с неизмененным значением индекса в память результата qij, увеличить значение индекса столбца БРН-матрицы А у = у+1 и БРН-матрицы В I = I + 1, загрузить элемент БРН-матрицы ау и Ьк,1, перейти к пункту 7.

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

Рисунок П.1.1. Структурная схема операции умножения Адамара для БРН-

матриц А и В

Вычислительная структура операции умножения Адамара для БРН-матриц А и В содержит идентичные компоненты, входные, внутренние и выходные сигналы вычислительной структуры операции сложения Адамара для БРН-матриц А и В.

Управляющий сигнал ЕО обозначает равенство позиций ненулевых элементов БРН-матриц А и В М_а0 = М_Ь0. Управляющий сигнал АМ обозначает, что позиция полученного элемента БРН-матрицы В меньше по значению М_а0 > М_Ь0, и элемент БРН-матрицы В находится первым в очереди на обработку относительно полученного элемента БРН-матрицы А, что приводит к нулевому результату при выполнении операции над ненулевым элементом. Управляющий сигнал ВМ обозначает, что позиция элемента БРН-матрицы А меньше по значению и М_а0 < М_Ь0, и элемент

БРН-матрицы А находится первым в очереди на обработку относительно элемента БРН-матрицы B, что также приводит к нулевому результату при выполнении операции над ненулевым элементом. Управляющий сигнал REA обозначает найденный символ конца строки для обрабатываемого вектора БРН-матрицы А, REB - для БРН-матрицы В, в результате чего обе строки считаются обработанными. Управляющий сигнал MEA обозначает что был найден символ конца БРН-матрицы в обрабатываемом векторе БРН-матрицы А, MEB - для БРН-матрицы В. Появление одного символа конца одной матрицы завершает выполнение операции. Управляющий сигнал формирования результата Smx формируется из сигналов REA, REB, MEA, MEB, EQ.

На входы вычислительной структуры поступают БРН-матрицы А и В по соответствующим каналам. Размерность обрабатываемых БРН-матриц n х m. На входы a, b, ind a, ind b БРН-матрицы передаются построчно в модифицированном формате ELLPACK со скважность подачи ненулевых элементов 2. Поток ненулевых элементов БРН-матриц А и В имеют следующий вид:

\A\=(<diji;ji>,<dij2;j2> ...<0;0>,<ш;ш> ...<ап^;]>,<0;0>,<П;П>;

|B| = {<e1J1;l1>,<e1J2;l2>.<0;0>,<œ;œ>.<elip;lp>,<0;0>,<û;û>}, где dljr - значения ненулевых элементов БРН-матрицы А; eiils - значения ненулевых элементов БРН-матрицы В;

i- номер строки ненулевого элемента БРН-матрицы А и БРН-матрицы В, где 1<i<n;

jr -номер столбца ненулевого элемента БРН-матрицы А, где jr принимает значения 1<jr<m, r принимает значения 1<r<mnspA, а spA - коэффициент разреженности БРН-матрицы А;

ls - номер столбца ненулевого элемента БРН-матрицы В, ls принимает значения 1< ls <m, s - принимает значения 1<s<mnspB, а spB - коэффициент разреженности БРН-матрицы B.

Значение ненулевого элемента aijr записывается в буфер синхронизации BUF A, значение ненулевого элемента e¡js записывается в буфер синхронизации BUFB. Значение позиции ненулевого элемента jr записывается в буфер синхронизации BUF_Ai, значение позиции ненулевого элемента ls в буфере BUF_Bi. Чтение ненулевого элемента и соответствующей ему позиции из буферной памяти BUF A и BUF_Ai для выполнения операции умножения выполняется, если позиции нулевых элементов БРН-матриц равны ls =jr или если позиция ненулевого элемента БРН-матрицы А меньше ls < jr. Чтение ненулевого элемента и соответствующей позиции из буферной памяти BUFB и BUF_Bi для выполнения операции осуществляется, если ls = jr или если позиция ненулевого элемента БРН-матрицы В меньше ls > jr. С прочитанными значениями из BUF A и BUF B выполняется операция aj х ei,ls. Результат выполнения операции над выданными значения ненулевых элементов поступает на мультиплексор MX1 формирования результата. Для формирования результата позиции ненулевого элемента используется текущее прочитанное значение из буфера BUF Ai, поскольку предполагается, что запись результата будет осуществляться, только когда значения индексов позиций значимый элементов равны ls =jr. В остальных случаях значение будет обнулено, как и результат умножения ненулевого элемента одной из БРН-матрицы на ноль. Управление МХ1 и МХ2 осуществляется сигналами Smx. Результат операции передается через регистры на выходы Q и ind Q для дальнейших вычислений или для записи в память.

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

ind_в с^^с^СЮ^^^^^С^Х^У

ind_At СОС^С^ 7 ind_Bt 5

ВЦ _I I_I Ь

ам вм

RВA RВB

0 X 2 >

о о хл^ о ><г^>

ь < о о

ц г о хд^ о

ind ^ < о УГ^ 0

Рисунок П. 1.2. Фрагмент временной диаграммы операции умножения БРН-

матриц А и В Адамара Со скважностью подачи данных, равной двум, по каналу А БРН-матрица передается в следующем виде {<а"ц,1> <а1,4,4> <а1,7,7>...} и по каналу В - {< в1>5, 5> <в 1,6,6> <в'1,7,7> <в 1у8,8>...}. Из буферов выдаются позиции ненулевых элементов по шинам М_А1 и М_В1. Сравнение позиций формирует управляющие сигналы EQ, АМ и ВМ. Значение ВМ = 1, когда по каналу М_В1 = 5, а М_А1 = 1 и М_А1 = 4. Значение АМ = 1, когда по каналу М_А1 = 7, а М_В1 = 5 и М_В1 = 6 и в строке БРН-матрицы А ненулевые элементы были обработаны. Значение EQ = 1 в двух случаях, когда по каналу М_А1 = М_В1 = 7, в обоих строках находятся нулевые элементы, обеспечивающие единую длину операнда и найден символ конца обрабатываемых строк ю БРН-матриц А и В. Результат выполнения операции умножения а х Ь будет формироваться, когда EQ = 1, а именно, в 7-м такте. При получении символа конца строки ю от одного из векторов БРН-матриц, обработка текущих строк БРН-матриц А и В будет закончена.

Эффективность базовой операции умножения Адамара определяется таким же образом, как и для матричной базовой операции сложения Адамара. Интенсивность обработки определяется по наименьшей возможной границе ц = 1, интенсивность входного потока данных составляет два ненулевых элемента в такт X = 2. Компенсация недостаточной интенсивности обработки данных ц выполняется с помощью снижения интенсивности входного потока X введением скважности подачи данных с = 2. В результате чего значение загруженности базовой матричной операции р = 1. Такая недостаточно стабильная система компенсируется за счет использования буфера, размер которого определяется наибольшей длиной сжатого модифицированным форматом ELLPACK вектора. Дополнением операции умножения матриц типа Адамара является Xout выдачи данных, интенсивность которой определяется пересечением по позициям ненулевых элементов БРН-матриц А и В.

Операции произведения Адамара являются вторым типом из основных матричных операций над БРН-матрицами. В операциях этого типа участвуют два операнда в сжатом модернизированном формате ELLPACK. В качестве операндов могут выступать две БРН-матрицы, два БРН-вектора или БРН-матрица и БРН-вектор. При выполнении операции скалярного умножения двух БРН-матриц предполагается, что вектора БРН-матрицы А в сжатом формате формируются из строк, а вектора БРН-матрицы B в сжатом формате формируются из столбцов. Позиции ненулевых элементов операнд БРН-матриц А и В с большой долей вероятности не соотносятся между собой и выполняется преобразование к дискретно-событийному виду.

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

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

Алгоритм матричной операции скалярного умножения БРН-матриц А и

В

Размерность БРН-матриц n х m, которая обозначается Q = |Л| • |ß|.

1. Установить значения индекса строки БРН-матрицы А i = 1;

2. Установить значения индекса строки БРН-матрицы В k = 1;

3. Установить значения индекса столбца БРН-матрицы А j = 1;

4. Установить значения индекса столбца БРН-матрицы В l = 1;

4. Установить значение промежуточного результата БРН-матрицы Q qt = 0;

5. Получить элемент БРН-матрицы bkl;

6. Получить элемент БРН-матрицы aj

7. Если элемент БРН-матрицы А содержит признак конца матрицы a, = Q, операция умножения скалярного типа завершена;

8 Если элемент БРН-матрицы А содержит признак конца строки матрицы a, = m или элемент БРН-матрицы В содержит признак конца строки матрицы bk,l = m, сумма произведений формирует результат операции qitk c индексами обрабатываемой строки БРН-матрицы А - i и индексом обрабатываемого столбца БРН-матрицы В - k, увеличить значение индекса строки к = к + 1для БРН-матрицы В, перейти к пункту 3;

9. Если загруженный элемент БРН-матрицы В содержит признак конца матрицы bk,i = Q, сумма произведений формирует результат операции qitk c индексами обрабатываемой строки БРН-матрицы А - i и индексом обрабатываемого столбца БРН-матрицы В - k, увеличить значение индекса строки БРН-матрицы А i = i + 1, перейти к пункту 2;

10. Сравнить значения индекса столбцов l и j для ненулевых элементов

atj и bkl;

11. Если l > j, выполнить операцию qt'i,k= qtitk+aij х0, увеличить значение индекса столбца БРН-матрицы А j = j+1, перейти к пункту 6;

12. Если I <у, выполнить операцию qt,i,k= дЬ,к+Ьк,1 х0 увеличить значение индекса столбца БРН-матрицы В I = I + 1, перейти к пункту 5;

13. Если I = у, выполнить операцию qt,i,k= qt^,k+a^j хЬк1 увеличить значение индекса столбца БРН-матрицы А у = у+1 и БРН-матрицы В I = I + 1, перейти к пункту 5;

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

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

БРН-матриц А и В Вычислительная структура содержит входные буферы памяти ненулевых элементов обрабатываемых БРН-матриц А и В BUF A и BUFB, а также входные буферы памяти позиций ненулевых элементов BUF_Ai и BUF_Bi, регистры FD, умножитель, сумматор, счетчик CNT для определения номера обрабатываемого столбца для формирования позиции результата, группу компараторов для анализа позиций ненулевых элементов и логические элементы «or» для организации дискретно-событийных потоков данных.

Входные данные обрабатываемых БРН-матриц передаются по каналам А и В - потоки ненулевых элементов, и ind a и ind_b - потоки позиции ненулевых элементов. При сравнении позиций ненулевых элементов и анализ

их на наличие символов конца строки ю и конца матрицы Q формируются управляющие сигналы. Эти сигналы формируют управляющую последовательность для преобразования входного потока в синхронизированный дискретно-событийный поток, а также для формирования результата вычислений в модернизированном формате ELLPACK. Управляющий сигнал EQ обозначает равенство позиций ненулевых элементов БРН-матриц А и В ind_ao = ind_bo. Управляющий сигнал AM обозначает, что позиция полученного элемента БРН-матрицы В меньше по значению ind_ao > ind_bo, и элемент БРН-матрицы В находится первым в очереди на обработку относительно полученного элемента БРН-матрицы А. Управляющий сигнал BM обозначает, что позиция полученного элемента БРН-матрицы A меньше по значению и ind_ao < ind_bo, и элемент БРН-матрицы А находится первым в очереди на обработку относительно элемента БРН-матрицы B. Управляющий сигнал REA обозначает, что был найден символ конца строки для обрабатываемого вектора БРН-матрицы А, REB - для БРН-матрицы В. Управляющий сигнал MEA обозначает, что был найден символ конца БРН-матрицы в обрабатываемом векторе БРН-матрицы А, MEB - для БРН-матрицы В. Управляющий сигнал формирования результата Smx и записи полученного элемента результата Qw формируется из сигналов REA, REB, MEA,MEB.

На входы вычислительной структуры поступают БРН-матрицы А и В по соответствующим каналам. Размерность обрабатываемых БРН-матриц n х m. На входы a, ind a, БРН-матрица передается построчно, на входы b, ind b БРН-матрица передается по столбцам. Обе матрицы представлены в модифицированном формате ELLPACK со скважностью подачи ненулевых элементов 2. Поток ненулевых элементов БРН-матриц А и В имеют следующий вид:

\A\={<dlJ1;j1>,<dlj2;j2>.<0;0>,<m;m>.<dnjt;jt>,<d;0>,<Q;n>;

\B\ = {<e1M;l1>,<e1j2;l2>.<0;0>,<m;m>.<enjp;lp>,<0;0>,<Q;Q>},

где aj - значения ненулевых элементов БРН-матрицы А; s¡js - значения ненулевых элементов БРН-матрицы В;

i- номер строки ненулевого элемента БРН-матрицы А и БРН-матрицы В, где 1<i<n;

jr -номер столбца ненулевого элемента БРН-матрицы А, где jr принимает значения 1<jr<m, r принимает значения 1<r<mnspA, а spA - коэффициент разреженности БРН-матрицы А;

ls - номер столбца ненулевого элемента БРН-матрицы В, ls принимает значения 1< ls <m, s - принимает значения 1<s<mnspB, а spB - коэффициент разреженности БРН-матрицы B.

Значение ненулевого элемента aijr записывается в буфер синхронизации BUF A, значение ненулевого элемента &¡js записывается в буфер синхронизации BUFB. Значение позиции ненулевого элемента jr записывается в буфер синхронизации BUF_Ai, значение позиции ненулевого элемента ls BUF_Bi.

Чтение ненулевого элемента и соответствующей ему позиции из буферной памяти BUF A и BUF_Ai для выполнения операции умножении и получения частичных сумм происходит, если позиции нулевых элементов БРН-матриц равны ls = jr или если позиция ненулевого элемента БРН-матрицы А меньше ls < jr. Чтение ненулевого элемента и соответствующей позиции из буферной памяти BUFB и BUF_Bi для выполнения операции умножении и получения частичных сумм происходит, если позиции нулевых элементов БРН-матриц равны ls =jr или если позиция ненулевого элемента БРН-матрицы В меньше ls > jr. С прочитанными значениями из BUF A и BUF B выполняется операция qt'i,k= qti,k+ai,j xbkj. Результат выполнения операции над выданными значениями ненулевых элементов поступает на мультиплексор MX1 формирования результата. Управление МХ1 и МХ2 осуществляется сигналами Smx. Выходы мультиплексоров МХ1 и МХ2 поступают на буфер выходных данных, в которых накапливается одна строка

результата для дальнейших вычислений или записи в результирующую память. Полученное значение ненулевого элемента матрицы результата записывается в буфер ВиБ_<2 по сигналу который возникает при достижении конца строки или конца столбца для текущих обрабатываемых векторов БРН-матриц А или В. Значение позиции ненулевого элемента определяется с помощью подсчета номера обрабатываемого столбца по сигналу КЕБ, при переходе к формированию следующей строки по сигналу МЕВ значение обнуляется. Полученное значение позиции ненулевого элемента с МХ2 передается на вход ВиБ_01.

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

сое

тс1_А1 тс1_В1 ЕЦ АМ ВМ REA

REB ^

^тх

а Ь qt

Qw

Х9>

с

X

X

>

< о "Х^Г^

N С

хо

ц с

тсЩ

Х^

хо

Рисунок П 1.4. Фрагмент временной диаграммы операции умножения БРН-

матриц А и В по скалярного типу

о

2

о

1

о

о

Со скважностью подачи данных равной двум по каналу А БРН-матрица передается в следующем виде {<а 1,1,1> <а1,4,4> <а1,5,5> <а1,7,7>...} и по каналу B - {< в5,1, 5> <в"б,1,6> <в~7,1,7> <в"з,1,8>...}. Из буферов выдаются позиции ненулевых элементов по шинам indAt и indBt. Сравнение позиций ненулевых элементов формирует управляющие сигналы EQ, AM и BM. Значение BM = 1, когда по каналу ind Bt = 5, а indAt = 1 и indAt = 4. Значение AM = 1, когда по каналу ind At = 7, ind Bt = 6 , а также когда все ненулевые элементы в буфере БРН-матрицы А были обработаны, при том что в буфере содержались необработанные элементы БРН-матрицы В. Значение EQ = 1, когда по каналу ind At = ind Bt = 7, ind At = ind Bt = 5, а также при символе конца обрабатываемых строк ю БРН-матриц А и В. Произведение ненулевых элементов a х b записывается во временную переменную qt, которая в начальный момент времени равняется нулю. Следующее совпадение позиций ненулевых элементов строки БРН-матрицы А и столбца БРН-матрицы увеличивает значение qt на полученное произведение qt2 = qt1 + a х b. Получения символа конца строки ю от одного из векторов обрабатываемых БРН-матриц формирует значение Qw для записи полученного ненулевого элемента БРН-матрицы Q в буфер BUF_Q и позиции ненулевого элемента в BUF_Qi.

Эффективность базовой операции скалярного умножения определяется соотношением интенсивности поступления данных и интенсивностью обработки данных. Интенсивность входного потока данных составляет два ненулевых элемента в такт X = 2, интенсивность обработки определяется по наименьшей возможной границе ^ = 1. Входной поток БРН-матриц поступает со скважностью с = 2, в результате чего значение загруженности базовой матричной операции р = 1. В таком случае размер буфера входных данных определяется наибольшей длиной сжатого модифицированным форматом ELLPACK вектора.

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

Операция произведения Кронекера является одной из основных матричных операций с БРН-матрицами. В операциях этого типа участвует одна БРН-матрица в модернизированном формате ELLPACK. Для матричных операций этого типа, для каждого элемента обрабатываемой БРН-матрицы выполняется операция со скалярными значением. Для операции типа Кронекера не используется преобразование входного потока в дискретно -событийный, поскольку нет необходимости синхронизировать неструктурированность обрабатываемой матрицы со скалярным значением. Матричные операции типа Кронекера предполагают выполнение операции БРН-матрицы со скалярной величиной, которая может быть как отдельной величиной, так и множеством скалярных значений, находящихся в составе вектора или другой матрицы. На практике к таким типам базовых операций могут относиться математические операции типа умножение, сложение, деление, вычитание между БРН-матрицей и скалярной величиной. Алгоритм матричной операции Кронекера c БРН-матрицей А Размерность БРН-матрицы n х m, которая обозначается Q = 0(\А |, Ь)

1. Установить скалярную величину b;

2. Установить значения индекса строки БРН-матрицы А i = 1;

3. Установить значения индекса столбца БРН-матрицы А у = 1;

4. Получить элемент БРН-матрицы ау ;

5. Выполнить операцию ау хЪ и сформировать результат операции с неизмененным значением индекса в память результата ;

6. Увеличить значение индекса столбца БРН-матрицы у = у+1, получить элемент БРН-матрицы а

7. Если загруженный элемент не содержит признак конца строки афш, тогда и перейти к пункту 5, иначе I = I + 1, перейти к пункту 3;

8. Если загруженный элемент не содержит признак конца матрицы а■ ф Д, тогда и перейти к пункту 5, иначе обработки БРН-матрицы А закончена.

В соответствии с алгоритмом была разработана вычислительная структура операции 0 по типу Кронекера, показанная рисунке П 1.5.

Рисунок П 1.5. Структурная схема операции над одной матрицей Кронекера Вычислительная структура содержит регистры FD для синхронизации потоков базовой матричной операции и операцию 0 - на месте которой может быть сумматор, умножитель, вычитатель, делитель и другие. Входной поток БРН-матрицы А передаётся по двум каналам - ind a позиций значимых элементов и a значимых элементов. Для базовых операции типа Кронекера вектор позиций значимых элементов ind a остается неизменным и присваивается в indq. Для ненулевых элементов a выполняется определенная арифметическая операция О с загруженной скалярной величиной b. Результат операции передается по каналу q через регистр дальнейших вычислений или для записи в память.

По входу а вычислительной структуры в модернизированном формате БЬЬРЛСК построчно передается БРН-матрица А, размерностью п х т. Поток ненулевых элементов БРН-матриц А имеет следующий вид:

где - значения ненулевых элементов БРН-матрицы А;

¡- номер строки ненулевого элемента БРН-матрицы А, где 1<Кп;

]г - номер столбца ненулевого элемента БРН-матрицы А, где / принимает

значения 1</г<т, г принимает значения 1<г<тп^рА, а 8рА - коэффициент

разреженности БРН-матрицы А. Некоторая операция 0 выполняется со

значением ненулевого элемента а/ и Ь. Полученное значение передается

через регистр в по каналу д и тё д.

Рассмотрим фрагмент примера временной диаграммы матричной операции типа Кронекера, где 0 - операция умножения БРН-матрицы на скаляр, который показан на рисунке П 1.6.

а

¡пс1_а Ь

¡пС_д

ча1,1/\а1,4/\а1,7

"о"

,а2,^/\а2,8/

о о

о о

; о ) < О

! о > < О

< о

< о

Рисунок П. 1.6. Фрагмент временной диаграммы операции умножения БРН-матриц А на скаляр Ь по типу Кронекера.

В вычислительное поле БРН-матрица А передает в сжатом формате построчно по каналу а - {<а^1>1,1> <а1,4,4> <а1,7,7> <0,0> <ю,ю><а2,5,5>...}, по каналу Ь загружается один элемент. С потоком ненулевых элементов БРН-матрицы А выполняется операция умножения на загруженную скалярную величину Ь. В результате выполнения операции умножения поток результата БРН-матрицы д равен {<а1,гв,1> <а1,4в,4> <а1,7в,7> <0,0> <т,ю> <а\ув,5>...}. После достижения символа конца матрицы О можно выполнить загрузку новой скалярной величины Ь.

Ь

Эффективность базовой операции типа Кронекера также может быть оценена по соотношению интенсивностей поступления данных и интенсивностью обработки данных. Для базовых матричных операций типа Кронекера обрабатывается одна БРН-матрица, и темп поступления будет равен темпу обработки данных. Такая структура является сбалансированной и не требует использования буферов, а процесс синхронизации может быть обеспечен регистрами.

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

ПРИЛОЖЕНИЕ 2

БИБЛИОТЕКА УСКОРЕННЫХ БАЗОВЫХ ОПЕРАЦИЙ ОБРАБОТКИ

БРН-МАТРИЦ НА РВС.

ПОДОПРИГОРА АЛЕКСАНДР ВЛАДИМИРОВИЧ

МЕТОДЫ И СРЕДСТВА ОБРАБОТКИ БОЛЬШИХ РАЗРЕЖЕННЫХ НЕСТРУКТУРИРОВАННЫХ МАТРИЦ НА РЕКОНФИГУРИРУЕМОЙ

ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

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

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

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

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

Таганрог - 2024

П.2. БИБЛИОТЕКА УСКОРЕННЫХ БАЗОВЫХ ОПЕРАЦИЙ ОБРАБОТКИ

БРН-МАТРИЦ НА РВС

Алгоритм матричной операции векторного умножения БРН-матриц А и В (произведение Адамара)

Размерность БРН-матриц п х т, которая обозначается Q = |Л|х|Б|.

1. Установить значения индекса строки БРН-матрицы А I = 1;

2. Установить значения индекса строки БРН-матрицы В к = 1;

3. Установить значения индекса столбца БРН-матрицы А у = 1;

4. Установить значения индекса столбца БРН-матрицы В 1 = 1;

5. Получить элемент БРН-матрицы Ьк,1;

6. Получить элемент БРН-матрицы ац;

7. Получить элемент БРН-матрицы Ьк,1+1;

8. Получить элемент БРН-матрицы ац+ь

8. Если полученный элемент БРН-матрицы А содержит признак конца матрицы = Д операция умножения типа Адамара завершена;

9. Если полученный элемент БРН-матрицы В содержит признак конца матрицы Ъщ = Д операция умножения типа Адамара завершена;

10. Если полученный элемент БРН-матрицы А содержит признак конца строки матрицы а1у = ш, увеличить значение индекса строки I = I + 1для БРН-матрицы А и к = к + 1для БРН-матрицы В, перейти к пункту 3;

11. Если полученный элемент БРН-матрицы В содержит признак конца строки матрицы Ък1 = ш, увеличить значение индекса строки I = I + 1для БРН-матрицы А и к = к + 1для БРН-матрицы В, перейти к пункту 3;

12. Сравнить значения фактические индексы столбцов I, 1+1, у, у+1 для ненулевых элементов ау а^+и Ък,1, Ък,1+1;

13. Если I <у;

13.1. Если элемент БРН-матрицы В содержит признак конца матрицы Ък>1+1 = Д операция умножения типа Адамара завершена;

13.2 Если элемент БРН-матрицы В содержит признак конца строки матрицы bk,i+i = ю, увеличить значение индекса строки i = i + 1для БРН-матрицы А и к = к + 1для БРН-матрицы В, перейти к пункту 3;

13.3. Если l+1 < j, увеличить значение индекса столбца БРН-матрицы В

l = l + 2;

13.4. Если l+1 = j, первый операнд t1 = aij, второй операнд t1 = Ьк1+1 увеличить значение индекса столбца БРН-матрицы A и В l = l + 1 и j = j + 1;

13.5. Если l+1 >j, увеличить значение индекса столбца БРН-матрицы A j = j + 1;

13.6 Выполнить операцию qk,l+1=t1 • t2, перейти к пункту 5;

14. Если l = j, первый операнд t1 = a,, второй операнд t1 = bk,l увеличить значение индекса столбца БРН-матрицы A и В l = l + 1 и j = j + 1;

14.1 Выполнить операцию qtemp=t1 • t2, перейти к пункту 5;

15. Если l > j;

15.1. Если элемент БРН-матрицы В содержит признак конца матрицы ai,j+1 = Д операция умножения типа Адамара завершена;

15.2 Если элемент БРН-матрицы В содержит признак конца строки матрицы aij+1 = ю, увеличить значение индекса строки i = i + 1 для БРН-матрицы А и к = к + 1для БРН-матрицы В перейти к пункту 3;

15.3. Если l < j+1, увеличить значение индекса столбца БРН-матрицы В

j = j + 2;

15.4. Если l = j+1, первый операнд t1 = ai,j+1, второй операнд t1 = bkyl увеличить значение индекса столбца БРН-матрицы A и В l = l + 1 и j = j + 1;

15.5. Если l > j+1, увеличить значение индекса столбца БРН-матрицы A

к = к + 1;

15.6 Выполнить операцию qi,j+1=t1 • t2, перейти к пункту 5.

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

Рисунок П 2.1. Структурная схема операции произведение Адамара для БРН-

матриц А и В

Вычислительная структура содержит функциональные компоненты, аналогичные для ускоренной базовой операции суммирования: входные буферы памяти ненулевых элементов обрабатываемых БРН-матриц А и В BUFA и BUFB, буферы памяти позиций ненулевых элементов BUF_Ai и BUF_Bi, разделенные на основной BUF_An и BUF_Bn, BUF_Ain и BUF_Bin и вспомогательный буфер BUF_Ac и BUF_Bc, BUF_Aic BUF_Bic, регистры FD, умножитель с плавающей точкой MUL, MUL mx logic - блок формирования управляющих последовательностей, логические элементы «or» и мультиплексоров МХ1- МХ8 для формирования выдачи результата.

Входные данные передаются по каналам А и В - потоки ненулевых элементов, и inda и ind_b - потоки позиции ненулевых элементов. После буферизации обработанные матрицы формируют основные каналы An, Bn, ind_an, ind_bn и вспомогательные каналы An+i, В n+i, ind a n+i, ind b n+i. На основании сравнения позиции ненулевых элементов между собой и со специально обозначенными символами конца строки ю и конца матрицы Q формируются управляющие сигналы. Эти сигналы формируют

управляющую последовательность для преобразования входного потока в синхронизированный дискретно-событийный поток и для формирования результата вычислений в модернизированном формате БЬЬРЛСК. Управляющий сигнал Е0а1Ъ1 обозначает равенство позиций ненулевых элементов БРН-матриц А и В М_ап = М_Ъп, управляющий сигнал Е0а1Ъ2 -М_ап = М_Ъп+1, управляющий сигнал Е0а2Ъ1 - М_ап+1 = М_Ъп. Управляющий сигнал АМа1Ъ1 обозначает, что позиция полученного элемента БРН-матрицы В меньше по значению относительно элемента БРН-матрицы А М_ап > М_Ъп, и элемент БРН-матрицы В находится может быть определен в очереди на обработку. Управляющий сигнал АМа1Ъ2 аналогично соответствует М_ап > М_Ъп+1 и АМа2Ъ1 - М_ап+1 > М_Ъп. Управляющий сигнал ВМа1Ъ1 обозначает, что позиция полученного элемента БРН-матрицы А меньше по значению относительно элемента БРН-матрицы В М_ап < М_Ъп, и элемент БРН-матрицы А будет обработан в первую очередь. Управляющий сигнал ВМа1Ъ2 соответствует М_ап < М_Ъп+1, а управляющий сигнал ВМа2Ъ1 -М_ап+1 < М_Ъп.

Управляющий сигнал ЯЕАп обозначает что был найден символ конца строки для обрабатываемого элемента в основном буфере БРН-матрицы Ап, Управляющий сигнал ЯЕАп+1 - для обрабатываемого элемента БРН-матрицы Ап+1. Управляющий сигнал ЯЕВп обозначает, что был найден символ конца строки для обрабатываемого элемента в основном буфере БРН-матрицы Вп, Управляющий сигнал ЯЕВп+1 - для обрабатываемого элемента БРН-матрицы Вп+1 Управляющий сигнал МЕАп обозначает, что был найден символ конца БРН-матрицы для обрабатываемого элемента в основном буфере БРН-матрицы Ап Управляющий сигнал МЕАп+1 - для обрабатываемого элемента БРН-матрицы Ап+1. Управляющий сигнал МЕВп обозначает, что был найден символ конца БРН-матрицы для обрабатываемого элемента в основном буфере БРН-матрицы Вп, Управляющий сигнал МЕВп+1 - для обрабатываемого элемента БРН-матрицы Вп+1.

На входы вычислительной структуры поступают БРН-матрицы А и В по соответствующим каналам. Размерность обрабатываемых БРН-матриц п х т. На входы а, Ь, тё а, тё Ь БРН-матрицы передаются построчно в модифицированном формате БЬЬРЛСК со скважностью подачи ненулевых

элементов 1. Поток ненулевых элементов БРН-матриц А и В имеют следующий вид:

\A\={<d^iji;ji>,<d^ij2;j2>^<0;0>,<m;m>^<a^njt;jt>,<0;0>,<ü;ü>; |B| = {<e^lu;li>,<e^li2;l2>^<0;0>,<m;m>^<e^nJp;lp>,<0;0>,<ü;ü>}, где dijr - значения ненулевых элементов БРН-матрицы А; e¡,ls - значения ненулевых элементов БРН-матрицы В;

i- номер строки ненулевого элемента БРН-матрицы А и БРН-матрицы В, где

i<i<n;

jr -номер столбца ненулевого элемента БРН-матрицы А, где jr принимает значения 1<jr<m, r принимает значения i<r<mnspA, а spA - коэффициент разреженности БРН-матрицы А;

ls - номер столбца ненулевого элемента БРН-матрицы В, ls принимает значения 1< ls <m, s - принимает значения i<s<mnspB, а spB - коэффициент разреженности БРН-матрицы B.

Плотный поток ненулевых элементов БРН-матриц А aj и dijr+i и так далее заполняют входной буфер BUF A а также разделенные буферы BUFAn и BUF_Ac. Аналогично происходит заполнение входного буфера БРН-матрицы В BUFB, BUF_Bn, BUF_Bc. После получения необходимого числа ненулевых элементов БРН-матриц в основном и вспомогательном буферах БРН-матриц А и В (по два ненулевых элемента от каждой БРН-матриц) выполняется чтение позиций ненулевых элементов ls, jr, ls+i, jr+i. После выполнения сравнений ls и jr, ls и jr+i, ls+i и jr анализируются значения полученных управляющих последовательностей. Сигналы EQaibi, EQaib2, EQa2bi формируют управляющие последовательности для MXi и МХ2 -формирования операнд сумматора. Сигналы EQaibi, EQaib2, EQa2bi, AMaibi, AMaib2, AMa2bi, BMaibi, BMaib2, BMa2bi формируют управляющие последовательности в блоке MUL mx logic для буферов выдачи ненулевых элементов, которые в качестве операндов для сумматора и функциональных устройств выдачи результат МХ3 - МХ6 для выдачи результатов умножения

Оп, Оп+1, 1пё дп, тё дп+1. Управление МХ7 и МХв осуществляется циклично повторяющимся сигналом, а результат операции передается через регистры на выходы О и тё О для дальнейших вычислений или для записи в память.

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

А

Ы_А В

Ы_В ¡г^_Ап

1|^_Ап+1 ¡п^Вп ¡П^Вп+1

АМ

ВМ ЕЦ КЕА КЕВ 11 12 13 Цп

Цп+1 ¡П^Цп

< 000 Х"оЮ<ГооО<ГооО<Г

> > > > > > > >

<~оо^<"оТ^ ооо Х~ооо~><Г

< ооо

С С

с с

с <

с <

с

оо

оо

Уоор^оооУ

> > > > > >

Рисунок П 2.2. Временная диаграмма операции ускоренного умножения БРН-

матриц А и В по типу Адамара.

Плотным потоком по каналу А БРН-матрица передается в следующем виде: {<а 1,1,1> <а1,4,4> <а1,7,7>...} и по каналу В - {< в1,5, 5> <вг 1,б,6> <в"1,7,7> <в\8,8>...}. Из основных и вспомогательных буферов выдаются позиции ненулевых элементов по шинам М_Ап, М_Вп, М_Ап+1 и М_Вп+1. Сравнение позиций формирует управляющие шины ЕО, АМ и ВМ, где шина ЕО состоит трех сигналов ЕОа1Ъ1, ЕОа1Ъ2, ЕОа2Ъ1, шина АМ из сигналов АМа1Ъ1, АМа1Ъ2, АМа2Ъ1 и шина ВМ из сигналов ВМа1Ъ1, ВМа1Ъ2, ВМа2Ъ1.

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

о

Для формирования результата необходимо анализировать значение шины EQ. Значение EQ = 001 появляется, когда позиция в канале ind_Bn равна позиции ind_An, в один такт формируются промежуточные операнды функционального устройства t1=bn, t2=an. В остальные моменты времени значения позиций ненулевых элементов не совпадают. Значение REA = 10 появляется, когда позиция в канале ind_An+1 равна символу конца обрабатываемых строк ю, что означает завершение операции обработки векторов БРН-матриц. В результате формируются две строки Qn+i, Qn, ind_qn+b ind_qn, которые содержат результат вычислений и могут быть объединены в один канал Q и ind_q.