Массовая обработка данных. Алгебраические модели и методы
Алгебраический подход к массовой обработке данных: от теории к программно-аппаратным комплексам
В современной парадигме Big Data эффективность обработки структурированных данных критически зависит от согласованности математических моделей и архитектуры вычислительных систем. Монография В.И. Мунермана «Массовая обработка данных. Алгебраические модели и методы» предлагает системный взгляд на решение этой проблемы через призму алгебраического аппарата.
Математическая формализация как ключ к производительности
Автор утверждает, что традиционные подходы к оптимизации запросов, часто основанные на эвристиках, не позволяют в полной мере использовать потенциал современных параллельных архитектур. Решение заключается в построении формализованных алгебраических моделей, которые обеспечивают изоморфизм между задачей и моделью вычислений. В книге подробно рассматриваются две такие модели: теоретико-множественная (файловая) и многомерно-матричная. Первая ориентирована на работу с упорядоченными последовательностями записей, вторая — на высокопроизводительные операции над многомерными структурами. Аксиоматический подход, предложенный автором, позволяет доказать эквивалентность этих моделей, что дает возможность гибко выбирать инструмент в зависимости от специфики предметной области.
Методы оптимизации и параллелизма
Центральное место в работе занимает проблема оптимизации процессов массовой обработки данных (МОД). Автор предлагает двухуровневый подход: оптимизацию отдельных операций и синтез оптимальных последовательностей операций (процессов). Для решения задач синтеза успешно применяется метод динамического программирования, который позволяет находить оптимальные планы выполнения запросов.
Особое внимание уделено принципу «симметричного горизонтального распределения данных». Этот метод позволяет эффективно распараллеливать наиболее ресурсоемкие операции, такие как слияние нестрого упорядоченных файлов (аналог SQL-операции JOIN). Экспериментальные данные, приведенные в монографии, подтверждают, что данный подход обеспечивает равномерную загрузку вычислительных узлов и значительно сокращает время выполнения запросов по сравнению со стандартными средствами СУБД.
Архитектурные решения
Книга не ограничивается теорией, предлагая конкретные архитектуры программно-аппаратных комплексов. Для реализации многомерно-матричной модели предлагаются структуры на базе SMP-архитектур, а для файловой модели — гибридные решения, сочетающие свойства SMP и MPP. Автор также демонстрирует возможности использования современных технологий, таких как CUDA для графических процессоров и ассоциативные вычислительные системы (ВСАРР), для ускорения операций поиска и обработки данных.
Прикладное значение
Практическая ценность работы подтверждается решением ряда классических и прикладных задач: от поиска кратчайших путей в графах до вывода ассоциативных правил и шифрования данных по алгоритму Хилла. Использование алгебры многомерных матриц для шифрования, в частности, открывает новые горизонты в повышении криптостойкости за счет использования свойств гипердетерминантов и многообразия обратных матриц.
Монография В.И. Мунермана представляет собой фундаментальное исследование, объединяющее дискретную математику, теорию алгоритмов и архитектуру ЭВМ. Предложенные методы синтеза и оптимизации процессов МОД являются мощным инструментом для разработчиков высокопроизводительных аналитических систем, позволяя перевести процесс проектирования программно-аппаратных комплексов с уровня интуитивных решений на уровень строгой инженерной дисциплины.
- ВО - Магистратура
- 01.04.02: Прикладная математика и информатика
- 27.04.03: Системный анализ и управление
- 27.04.07: Наукоемкие технологии и экономика инноваций
- 45.04.04: Интеллектуальные системы в гуманитарной сфере
- Аспирантура
- 01.06.01: Математика и механика
МАССОВАЯ ОБРАБОТКА ДАННЫХ АЛГЕБРАИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ В.И. МУНЕРМАН МОНОГРАФИЯ Москва ИНФРА-М 2026
УДК 519.61(075.4) ББК 22.192 М90 Мунерман В.И. М90 Массовая обработка данных. Алгебраические модели и методы : монография / В.И. Мунерман. — Москва — 229 с. — (Научная мысль). — DOI 10.12737/1906037. ISBN 978-5-16-018035-9 (print) ISBN 978-5-16-111050-8 (online) Монография посвящена математической и алгоритмической поддержке массовой обработки данных на основе алгебраических моделей. Рассматривается один из самых распространенных классов массовой обработки – обработка высокоактивных структурированных данных. Анализируются построение алгебраических моделей данных и вычислений и методы доказательства их соответствия. Изучаются три алгебраические системы, которые могут быть использованы и как модели данных, и как модели вычислений. Исследуются алгебраический и аксиоматический методы доказательства соответствия этих моделей. Дается доказательство их соответствия: гомоморфизма и изоморфизма. Поднимается проблема оптимизации процессов массовой обработки данных, представленных в виде алгебраических выражений в предложенный алгебрахмоделях. Подробно описываются алгоритмы синтеза и оптимизации вычисления этих выражений, метод симметричного горизонтального распределения данных, обеспечивающий параллельную реализацию вычисления алгебраических выражений и обобщение блочного алгоритма параллельного умножения матриц на случай умножения многомерных матриц. Предлагаются архитектуры программно-аппаратных комплексов для эффективной параллельной реализации операций в рассмотренных алгебрах-моделях. Приводится ряд реальных примеров, иллюстрирующих применение предложенных методов. Для студентов, аспирантов и преподавателей технических и физико-математических вузов и факультетов. УДК 519.61(075.4) ББК 22.192 Р е ц е н з е н т ы: Борисов В.В., доктор технических наук, профессор, профессор кафедры вычислительной техники Смоленского филиала Национального исследовательского университета «МЭИ»; Кононова А.И., доктор физико-математических наук, доцент, профессор Национального исследовательского университета «Московский институт электронной техники» ISBN 978-5-16-018035-9 (print) ISBN 978-5-16-111050-8 (online) © Мунерман В.И., 2023
ОГЛАВЛЕНИЕ ВВЕДЕНИЕ.................................................................................................................6 Глава 1. МАССОВАЯ ОБРАБОТКА ДАННЫХ: ОПРЕДЕЛЕНИЕ, МЕТОДЫ ОПИСАНИЯ, АНАЛИЗ ПРОБЛЕМ...........................................................................9 1.1. Понятие массовой обработки данных ............................................................................................9 1.2. Связь моделей МОД с архитектурами программно-аппаратных комплексов ..........19 1.2.1. Логически последовательный метод доступа ...........................................................19 1.2.2. Архитектуры вычислительных комплексов для реализации логически последовательного метода доступа ...............................................................................22 1.3. Проблемы оптимизации процессов массовой обработки данных .................................29 1.4. Требования к моделям массовой обработки данных ...........................................................34 Глава 2. АЛГЕБРАИЧЕСКИЕ МОДЕЛИ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ ПРОГРАММНО-АППАРАТНЫХ КОМПЛЕКСОВ................................................. 39 2.1. Основные алгебраические понятия................................................................................................39 2.1.1. Универсальные алгебры и алгебраические системы..............................................39 2.1.2. Интуитивный подход к объектно-ориентированному моделированию, проектированию и программированию........................................................................42 2.1.3. Алгебраический (формальный) подход к объектно-ориентированному моделированию, проектированию и программированию...................................44 2.1.4. Объектно-ориентированный подход к разработке моделей данных ...........46 2.2. Файловая (теоретико-множественная) модель данных........................................................52 2.2.1. Анализ определений файла ................................................................................................52 2.2.2. Определение файла.................................................................................................................54 2.2.3. Описание операций над файлами....................................................................................56 2.3. Многомерно матричная модель данных......................................................................................60 2.3.1. Задачи многомерно матричного представления данных.....................................60 2.3.2. Алгебра многомерных матриц...........................................................................................62 2.4. Соответствие моделей данных .........................................................................................................68 2.4.1. Соответствие теоретико-множественной и многомерно-матричной моделей ........................................................................................................................................68 2.4.2. Соответствие промежуточных моделей данных высокоуровневым моделям ........................................................................................................................................74 2.5. Аксиоматический подход к формализации моделей данных для МОД........................77 2.5.1. Соответствие аксиоматического и алгебраического подходов к формализации МОД.............................................................................................................78 2.5.2. Определение аксиоматической теории МОД.............................................................79 2.5.3. Интерпретация формул аксиоматической теории МОД.......................................80 2.5.4. Аксиомы теории массовой обработки данных..........................................................81 2.5.5. Теоремы аксиоматической теории МОД.......................................................................84 2.5.6. Эквивалентность моделей МОД........................................................................................85 Глава 3. МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ МАССОВОЙ ОБРАБОТКИ ДАННЫХ......................................................................................... 88 3.1. Проблемы повышения эффективности обработки данных.................................................88 3.2. Синтез и оптимизация процесса МОД...........................................................................................92 3.2.1. Модель и метод построения процесса МОД...............................................................92 3.2.2. Формальное описание метода синтеза и оптимизации процесса МОД........95
3.2.3. Реализация метода синтеза и оптимизации процесса МОД................................99 3.3. Выбор параллельных алгоритмов для реализации операций МОД............................103 3.4. Алгоритм параллельного умножения многомерных матриц..........................................105 3.4.1. Выбор алгоритма умножения многомерных матриц...........................................105 3.4.2. Описание алгоритма умножения многомерных матриц....................................109 3.5. Алгоритм параллельной реализации операции слияния нестрого упорядоченных файлов......................................................................................................................124 3.5.1. Анализ алгоритмов параллельной реализации операции слияния нестрого упорядоченных файлов..................................................................................124 3.5.2. Организация данных для параллельной реализации операции слияния нестрого упорядоченных файлов...............................................................126 3.5.3. Параллельный алгоритм реализации операции слияния нестрого упорядоченных файлов......................................................................................................129 3.6. Алгоритм параллельной реализации операции соединения в реляционной модели SQL...............................................................................................................................................139 3.7. Стратегия повышения эффективности процессов МОД....................................................144 Глава 4. АРХИТЕКТУРЫ ПРОГРАММНО-АППАРАТНЫХ КОМПЛЕКСОВ ДЛЯ МАССОВОЙ ОБРАБОТКИ ДАННЫХ......................................................... 146 4.1. Этапы построения программно-аппаратных комплексов................................................146 4.2. Архитектура программно-аппаратного комплекса для реализации многомерно-матричной модели данных...................................................................................148 4.3. Архитектуры программно-аппаратных комплексов для реализации простых операций теоретико-множественной модели данных.......................................................151 4.3.1. Параллельная реализация внешней сортировки .................................................151 4.3.2. Параллельная реализация операций выборки, слияния строго упорядоченных файлов и сечения................................................................................155 4.4. Параллельная реализация операции слияния нестрого упорядоченных файлов в теоретико-множественной и реляционной моделях данных.....................157 4.4.1. Параллельная реализация операции слияния нестрого упорядоченных файлов алгоритмом черпака.........................................................159 4.4.2. Параллельная реализация последовательности операций слияния нестрого упорядоченных файлов .................................................................................163 4.4.3. Параллельная реализация операции слияния нестрого упорядоченных файлов с использованием ассоциативных вычислительных систем...........165 Глава 5. ЭКСПЕРИМЕНТАЛЬНЫЙ АНАЛИЗ ПРОГРАММНО-АППАРАТНЫХ РЕАЛИЗАЦИЙ МАССОВОЙ ОБРАБОТКИ ДАННЫХ........................................ 169 5.1. Анализ параллельной реализации операции умножения многомерных матриц.........................................................................................................................................................169 5.2. Анализ параллельной реализации операции слияния нестрого упорядоченных файлов ....................................................................................................................171 5.3. Анализ параллельной реализации операции слияния нестрого упорядоченных файлов средствами СУБД и SMP-архитектуры.....................................171 5.4. Анализ параллельной реализации операции слияния нестрого упорядоченных файлов с использованием MPP-архитектуры в облачной среде..................................................................................................................................175 5.5. Анализ параллельной реализации операции слияния нестрого упорядоченных файлов с использованием SMP-архитектуры в облачной среде..................................................................................................................................179
5.6. Анализ параллельной реализации операции слияния нестрого упорядоченных файлов с использованием SMP-архитектуры и многоядерных графических процессоров................................................................................................................181 Глава 6. ПРИМЕНЕНИЕ АЛГЕБРАИЧЕСКОГО ПОДХОДА ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ....................................................................................... 183 6.1. Использование предложенного метода для решения задач о кратчайшем пути..............................................................................................................................................................183 6.1.1. Решение традиционной задачи......................................................................................183 6.1.2. Решение задачи с одновременным построением пути......................................187 6.2. Использование предложенного метода для решения задачи вывода ассоциативных правил.......................................................................................................................195 6.3. Использование предложенного метода для решения задачи поиска изображений в базах данных .........................................................................................................199 6.3.1. Архитектура программно-аппаратного комплекса для поиска изображений в базах данных .........................................................................................199 6.3.2. Параллельное сравнение ключей изображений....................................................202 6.3.3. Реализация и анализ метода поиска изображений в базе данных...............204 6.4. Реализация алгоритма шифрования Хилла на основе алгебры многомерных матриц.........................................................................................................................................................207 6.4.1. Краткое описание алгоритма шифрования Хилла................................................207 6.4.2. Дополнительные элементы алгебры многомерных матриц ...........................208 Заключение........................................................................................................ 214 Список использованной литературы............................................................ 215
ВВЕДЕНИЕ В книге рассматриваются математическая и алгоритмическая поддержка массовой обработки данных на основе алгебраических моделей. Традиционно массовую обработку данных связывают с параллельными вычислениями и чаще всего определяют следующим образом: массовая параллельная обработка — способ параллельной обработки больших объемов данных большим числом процессоров. В настоящее время массовую обработку данных связывают с направлением, получившим название Big data. Big data (большие данные) — общий термин, который обозначает вновь создающиеся структурированные, неструктурированные и полуструктурированные данные сверхбольших и постоянно возрастающих объемов. Загрузка неструктурированных и полуструктурированных данные в обычную (например, реляционную) базу данных и последующая обработка требуют слишком больших затрат ресурсов вычислительных комплексов. Поэтому книга посвящена рассмотрению одного самого распространенного из классов массовой обработки — обработке высокоактивных структурированных данных. Высокая активность данных означает, что при выполнении операций над данными в обработку включается их большая, близкая к ста процентам. Большие данные (Big data) — не только неотъемлемая часть современного мира обработки данных, но и основная его часть. Комплекс сложных научно-технических проблем, связанных с решением задач на основе обработки больших данных, при переходе к информационному обществу не только сохраняет, но и усиливает свою актуальность. Об этом свидетельствуют интенсивные научные исследования в области баз данных, проводимые в России и за рубежом. Требования к обработке больших данных существенно влияют на технологию разработки программных и аппаратных вычислительных средств, ее реализующих. Решение сложных вычислительных задач [1–3], информационно-логических задач, к которым относятся обработка транзакционных запросов и запросов, требующих больших рабочих нагрузок [4, 5], а также задач в области искусственного интеллекта [6, 7], таких как переобучение сверточных нейронных сетей [8, 9], обусловили необходимость использования параллельной обработки и обработки в основной (оперативной) памяти. Важное значение в обработке больших данных
имеют параллельные и распределенные базы данных [10], для которых создаются специализированные программно-аппаратные комплексы — машины баз данных. При разработке параллельных вычислительных систем особую роль играет повышение эффективности реализации отдельных операций, имеющих большую вычислительную сложность, о чем свидетельствуют многие публикации, например, [11–15]. К этим операциям относятся такие, как многомерное дискретное преобразование Фурье, свертки в процессе обучения нейронных сетей, операция Join в реляционных системах баз данных. Современные аппаратные средства, такие как многопоточные процессоры архитектур, подобных x86 и ARMv8, а также графические процессоры и ускорители, позволяют проектировать параллельные вычислительные системы, которые обеспечивают решение многих из перечисленных задач [16, 24]. Важное направление основано на использовании современных программируемых логических интегральных схем (ПЛИС/FPGA). Относительная простота программирования [25, 26] позволяет использовать их для решения как вычислительных, так и информационно-логических задач, и создания центров обработки данных (Data Center) [27–30]. Особую роль современные ПЛИС играют в решении проблемы построения быстро реконфигурируемых вычислительных систем [31]. Так, в машине баз данных IBM Netezza [32] ПЛИС позволяет быстро перестраивать процессор обмена и подготовки данных S-Blade, превращая его в специализированный процессор для выполнения конкретного запроса, полученного от случайного пользователя. Рассмотренные важные задачи требуют для своего решения построения программно-аппаратных комплексов, основное свойство которых заключается в достижении эффективного баланса программного и аппаратного обеспечения [33, 34]. Эта эффективность достигается тогда, когда, как сказано в [35]: «Для всех конкретных параллельных вычислительных систем степень согласованности структуры алгоритмов с архитектурой систем играет самую важную роль в достижении наивысших скоростей». Формальная постановка этой проблемы предложена в [36]: «Одним из основных источников задач прикладной теории алгоритмов является проблема оптимального перевода с одного языка на другой, которая может быть сформулирована следующим образом: существуют два алгоритмических языка и некоторый алгоритм, написанный на одном из них; требуется найти оптимальную по заданным критериям реализацию этого алгоритма на другом языке. В программировании обычно первым является некоторый язык программирования, ориентированный
на тот или иной круг задач, а вторым — внутренний язык машины, на которой решаются данные задачи. Поиск причин возникновения трудностей при решении задач на вычислительной технике параллельной архитектуры неизбежно приводит к выводу, что как истоки этих причин, так и пути их преодоления надо искать в математических знаниях об алгоритмах». Эти две посылки позволяют сделать заключение, состоящее в следующем: Алгебраическая система, в которой формализована решаемая задача, и модель вычислений (алгебраическая система, реализованная в системе команд вычислительной системы или комплекса) должны в наибольшей степени соответствовать друг другу. Эти алгебраические системы должны быть по крайней мере гомоморфными, в идеальном случае, когда достигается полное соответствие — изоморфными. Для обработки больших данных традиционно используется массовая обработка данных (massively data processing, massively data computing) — способ параллельной обработки больших объемов данных большим числом процессоров [37, 38]. Для ее реализации проектируются и используются специализированные программноаппаратные комплексы [39–41]. Область, в которой применение массовой обработки данных имеет важное значение — это обработка высокоактивных данных. Активность данных определяется отношением числа обращений элементу данных (записи файла, элементу матрицы, строки таблицы) к общему числу обращений к информации (файлу, матрице, базе данных) в единицу времени [42, 43]. В соответствии со сказанным монография содержит подробное описание развития формализованного математического, а именно алгебраического аппарата, который обеспечит наилучшее соответствие характера данных и свойств вычислительных средств для реализации массовой обработки данных.
Глава 1 МАССОВАЯ ОБРАБОТКА ДАННЫХ: ОПРЕДЕЛЕНИЕ, МЕТОДЫ ОПИСАНИЯ, АНАЛИЗ ПРОБЛЕМ 1.1. ПОНЯТИЕ МАССОВОЙ ОБРАБОТКИ ДАННЫХ Традиционно массовую обработку данных связывают с параллельными вычислениями и чаще всего определяют следующим образом: массовая параллельная обработка — способ параллельной обработки больших объемов данных большим числом процессоров. В настоящее время массовую обработку данных связывают с направлением, получившим название Big data. Big data (большие данные) — общий термин, который обозначает вновь создающиеся структурированные, неструктурированные и полуструктурированные данные сверхбольших и постоянно возрастающих объемов; загрузка их в обычную (например, реляционную) базу данных и последующая обработка требуют слишком больших затрат ресурсов вычислительных комплексов. В работе рассматривается один из классов массовой обработки — обработка структурированных данных. Исторически обработка структурированных данных — один из самых ранних классов обработки. Первые математические (алгебраические) модели для него появились еще в начале 60-х годов ХХ века и в конечном счете привели к современным реляционным и объектным моделям данных. Технологические решения также развивались в основном применительно к обработке структурированных данных. К числу таких решений можно отнести формализацию методов доступа к данным. Разделение их на последовательный, индексный и индексно-последовательный позволило существенно повысить производительность вычислительных комплексов, так как метод доступа определялся характером решаемой задачи. Это позволяло выбирать наиболее эффективный алгоритм обработки данных для каждой операции из последовательности операций, приводящих к решению прикладной задачи. Далее в работе речь будет идти только о массовой обработке структурированных данных, поэтому под термином «массовая обработка данных» (МОД) будет пониматься только обработка структурированных данных.
Традиционно МОД широко используется для решения многих задач в различных предметных областях в тех случаях, когда в вычисления включается значительная часть данных. К числу таких задач относятся, например: • • оперативная статистическая обработка экспериментальных данных, таких как виброзащитные характеристики, оперативно получаемые в ходе летных испытаний [44]; • • в банковской сфере, задача «Операционный день банка» требует ежедневной обработки от 40 до 90% всей базы данных банка [45, 46]; • • ежедневные задачи учета и планирования производства в современных системах управления (стандарты ERP [47, 48]), при решении которых процент обрабатываемых данных всегда близок к 100; • • задачи статистического анализа и синтеза подсистем послепродажного обслуживания в системах интегрированной логистической поддержки наукоемкой продукции [49]. Таким образом, особенность этих классов задач заключается в том, что: 1) при их решении в обработку включаются практически все данные, характеризующие объекты этих задач; 2) объемы обрабатываемых данных очень велики, то есть можно утверждать, что они (эти классы) относятся к области исследований, связанной с обработкой данных больших объемов (Big data). В работе рассматривается такая разновидность МОД, которая позволяет учесть эти особенности и, основываясь на свойствах и структурах данных, присущих рассмотренным классам задач, обеспечивает эффективную реализацию вычислительных процессов решения этих задач. Далее предполагается, что используемые и обрабатываемые в задачах МОД данные хранятся в базах данных (БД) и обрабатываются системами управления базами данных (СУБД). Под СУБД понимается, в соответствии с международными стандартами [50], программная система, предназначенная для создания и хранения базы данных на основе некоторой модели данных, обеспечения логической и физической целостности содержащихся в ней данных, надежного и эффективного использования ресурсов (данных, пространства памяти и вычислительных ресурсов). В книге рассматриваются именно методы эффективной реализации МОД с использованием современных аппаратных и программных средств. Повышение эффективности достигается за счет предложения и использования специальных моделей данных.