Массовая обработка данных. Алгебраические модели и методы

МАССОВАЯ ОБРАБОТКА 

ДАННЫХ

АЛГЕБРАИЧЕСКИЕ  
МОДЕЛИ И МЕТОДЫ

В.И. МУНЕРМАН

МОНОГРАФИЯ

Москва 
ИНФРА-М 

2023

УДК 519.61(075.4)
ББК 22.192
 
М90

Мунерман В.И.

М90  
Массовая обработка данных. Алгебраические модели и методы : 

монография / В.И. Мунерман. — Москва : ИНФРА-М, 2023. — 
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], 
программная си стема, предназначенная для создания и хранения 
базы данных на основе некоторой модели данных, обеспечения логической и физической целостности содержащихся в ней данных, 
надежного и эффективного использования ресурсов (данных, пространства памяти и вычислительных ресурсов). В книге рассматриваются именно методы эффективной реализации МОД с использованием современных аппаратных и программных средств. 
Повышение эффективности достигается за счет предложения и использования специальных моделей данных.