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

МАССОВАЯ ОБРАБОТКА 
ДАННЫХ
АЛГЕБРАИЧЕСКИЕ  
МОДЕЛИ И МЕТОДЫ
В.И. МУНЕРМАН
МОНОГРАФИЯ
Москва 
ИНФРА-М 
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], 
программная си-стема, предназначенная для создания и хранения 
базы данных на основе некоторой модели данных, обеспечения логической и физической целостности содержащихся в ней данных, 
надежного и эффективного использования ресурсов (данных, пространства памяти и вычислительных ресурсов). В книге рассматриваются именно методы эффективной реализации МОД с  использованием современных аппаратных и программных средств. 
Повышение эффективности достигается за счет предложения и использования специальных моделей данных.