Эффективные алгоритмы и технология сортировки данных в АСУ Краснокутский Николай Григорьевич

Содержание к диссертации

Введение

Глава I. ОСНОВНЫЕ МЕТОДЫ И СРЕДСТВА ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРОЦЕДУРЫ СОРТИРОВКИ II

1.1. Задача упорядочения II

1.2. Основные показатели функционирования процедуры сортировки 12

1.3. Классификация методов и средств повышения эффективности сортировки 13

1*4. Быстродействующие алгоритмы внутренней

сортировки 14

1.5. Эффективные алгоритмы внешней сортировки 26

1.6. Анализ алгоритмов переразмещения .... 34

1.7. Анализ общих методов повышения эффективности сортировки данных 36

1.8. Высокопроизводительные программные средства сортировки 39

1.9. Постановка задач разработки и исследования 41

Глава 2. АЛГОРИТМЫ СОРТИРОВКИ В ОГРАНИЧЕННОЙ ПО ОБЪЕМУ

И КОНФИГУРАЦИИ ВНЕШНЕЙ ПАМЯТИ 43

2.1. Анализ балансного слияния 43

2.2. Алгоритмы сортировки в ограниченной по объему внешней памяти 54

2.3. Алгоритм сортировки в ограниченной по конфигурации дисковой памяти 74

2.4. Выводы 80

Глава 3. АЛГОРИТМЫ ПЕРЕРАЗМЕЩЕНИЯ ДАННЫХ 82

3.1. Задача переразмещения 82

3.2. Алгоритм I 83

3.3. Алгоритм 2 84

3.4. Алгоритм 3 84

3.5. Алгоритм 4 86

3.6. Алгоритм 5 87

3.7. Алгоритм б 87

3.8. Алгоритм 7 87

3.9. Оценка эффективности алгоритмов переразмещения 89

3.10.Выводы 90

Глава 4. ОБЩИЕ МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРОЦЕДУРЫ СОРТИРОВКИ 91

4.1. Сжатие данных 91

4.2. Мультизадачный режим в алгоритме перекрестного слияния 93

4.3. Метод динамического управления ОП в мультизадачной среде 93

4.4. Загрузка буферного пула с использованием каталога ключей 94

4.5. Выводы 100

Глава 5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ 102

Глава 6. ПРИНЦИПЫ ПОСТРОЕНИЯ И ОРГАНИЗАЦИИ ГС ... . 108

6.1. Принципы построения ГС 108

6.2. Общая организация ГС НО

6.3. Функции и возможности ГС 123

6.4. Некоторые выводы и рекомендации .... 124

ЗАКЛЮЧЕНИЕ 126

СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 128

ПРИЛОЖЕНИЕ I. ТЕКСТЫ ПРОГРАММНЫХ МОДУЛЕЙ ГС 138

ПРИЛОЖЕНИЕ 2. АКТЫ ВНЕДРЕНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

ГС 149

• Задача упорядочения
• Анализ балансного слияния
• Сжатие данных
• СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ
• Принципы построения ГС

Введение к работе

В "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года" отмечается, что одной из составляющих задачи ускорения научно-технического прогресса и перевода экономики на интенсивный путь развития является "...совершенствование вычислительной техники, ее элементной базы и математического обеспечения" [I, с. 23] .

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

42У5ьность_проблемы. На сегодняшний день разработано и широко используется множество типовых процедур обработки данных [12, 14, 4б] , наиболее распространенной и часто используемой среди которых является сортировка. Эта процедура представляет собой неотъемлемую часть абсолютного большинства систем обработки данных (СОД), без которой практически невозможно функционирование такого сложного управляющего комплекса, каким является АСУ.

Вопросам теории и практики сортировки посвящено немало фундаментальных трудов, среди которых следует отметить работы советских ученых В.М.Глушкова [14] , А.А.Папернова и В.А.Подымова [39] , С.СЛаврова и И.Л.Гончаровой [32] , С.Н.Селеткова и Б.Г.Волкова [43] , Э.А.Трахтенгерца [48] , а также американских ученых Д.Кнута [25] , Г.Лорина [Зб] и др.

Главным фактором, определяющим необходимость дальнейших разработок и исследований в области сортировки, является большой удельный вес времени сортировки в общем объеме времени, затрачиваемого на решение задач обработки данных. Как отмечается в [15, 25], эта величина превышает 25$. Б [49] подчеркивается, что несмотря на широкое распространение накопителей на магнитных дисках (НМД; и методов прямого доступа к данным, применение которых должно было привести к уменьшению удельного веса сортировки в общем объеме типовых процедур обработки данных, сортировка не теряет свое значение. Исследования [12, 44] показали, что методы прямого доступа к данным наиболее эффективны при обработке не всего набора данных (НД), а только его относительно небольшой части (например, при одиночных или групповых обращениях к данным;. Для обработки в определенной последовательности всего НД более целесообразно предварительно его упорядочить. Потребность же в такой обработке, особенно в АСУ, является насущной необходимостью.

В настоящее время процедура сортировки в СОД на базе ЕС ЭВМ выполняется с использованием пакета программ сортировки (ПІІСЛ ОС ЕС [17]. Этот пакет обеспечивает эффективное упорядочение НД как в ленточной, так и в дисковой рабочей памяти посредством быстродействующих алгоритмов внутренней и внешней сортировки. В то же время резервы повышения эффективности процедуры сортировки с точки зрения увеличения быстродействия и более экономного расходования внешней рабочей памяти в ППС ОС ЕС далеко не исчерпаны. К этим резервам, определяющим конкретные пути повышения эффективности процесса упорядочения НД, можно отнести: увеличение коэффициента нагрузки рабочей памяти сорти- ровки³⁶; повышение быстродействия в случае использования ограниченной по конфигурации дисковой памяти; уменьшение времени обмена с рабочими накопителями; более эффективное использование оперативной памяти (ОШ.

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

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

Научная новизна работы. Научная значимость работы определяется следующими основными результатами: обоснованы возможности и пути повышения эффективности процедуры сортировки в АСУ; разработаны и исследованы алгоритмы сортировки во внешней памяти ограниченного объема; разработан алгоритм магистральной сортировки, уменьшающий время выполнения сортировки в ограниченной по конфигурации дисковой памяти и общее время работы СОД конвейерного типа [5], использующих процедуру сортировки; получена аналитическая оценка объемов рабочих НД для балансного слияния, что дает возможность гибкого маневрирования магнитными носителями в процессе упорядочения; предложены эффективные алгоритмы переразмещения дан- ^х Под.коэффициентом нагрузки рабочей памяти сортировки будем понимать отношение объема (в байтах) входного НД к суммарному объему (в байтах) рабочих НД. ных, минимизирующие суммарное время переразмещения, включающее время как самого переразмещения, так и время поиска порядка переразмещения; проведен сравнительный анализ методов параллельной сортировки и даны рекомендации по их использованию в мультипроцессорных вычислительных системах (МВС); разработаны основные принципы построения генератора сортировки (ГС) для ЕС ЭВМ,

Практическая_ценность__>работы. Реализация разработанных методов в ГС позволила уменьшить суммарные затраты времени на сортировку данных в АСУ в среднем на 20%, а также увеличить в среднем в 4 раза коэффициент нагрузки рабочей памяти сортировки*

Е5изация_результатов__работы. На основе разработанных алгоритмов и полученных теоретических результатов создано программное обеспечение TG, эксплуатируемое в составах АСУ Киевского авиапроизводственного объединения, Таганрогского механического завода, Киевского производственного объединения реле и автоматики и Рошальского химкомбината. Суммарный годовой экономический эффект от внедрения ГС составляет в настоящее время около 60 тыс.руб. (акты внедрения прилагаются к диссертации).

Апробация_работы_л Основные результаты работы докладывались на следующих семинарах, и конференции: республиканском семинаре "Эффективные методы обработки данных в АСУ на базе ЕС ЭВМ" (Киев, РДЭНТП, 1979); республиканском семинаре "Эффективные методы и системы обработки данных" (Киев, РДЭНТП, 1980); постоянно действующем семинаре "Технология подготовки, хранения и обработки информации в АСУП" Научного Сове- та АН yCGP по проблеме "Кибернетика" (Киев, институт автоматики, 1981); постоянно действующем семинаре "Разработка и применение программных средств ЭВМ и систем" Научного Совета АН УССР по проблеме "Кибернетика" (Киев, ИК АН УССР, 1982); всесоюзной конференции "Банки данных" (Ташкент, ИК АН УзССР, 1983).

ЕВ3!ё9-2йЕ^й2-боты. Работа включает в себя, помимо введения, шесть глав, заключение и два приложения. В первой главе делается обзор и критический анализ эффективных алгоритмов внутренней и внешней сортировки, алгоритмов переразмешения, общих (технологических) методов повышения эффективности сортировки данных и высокопроизводительных программных средств сортировки. Показывается их взаимосвязь при сортировке ЦД. Рассматриваются их характерные особенности. Формулируется постановка конкретных задач разработки и исследования.

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

В третьей главе описываются эффективные алгоритмы переразмещения ЦД, определяются их сравнительные характеристики,

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

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

В шестой главе формулируются основные принципы построения ГС. Приводятся его функциональная структура и состав.

В заключении освещаются основные теоретические и практические результаты работы.

В приложения включены распечатки модулей ГС и акты внедрения.

Задача упорядочения

Под сортировкой или упорядочением понимается процесс распределения множества элементов по группам в соответствии с некоторыми определенными правилами [II] .

В формализованном виде задача сортировки определяется следующим образом. Пусть дано множество, состоящее из записей к R0 Ra, ..., R.N, При этом запись Hi , где і = f, N имеет ключ ki , представляющий собой некоторую часть записи. Задача сортировки состоит в получении такой перестановки Нх(1) R.r(z)..» Кх(ы) исходного множества ftlt Яг,..., Яы ключи элементов которой удовлетворяли бы следующему соотношению:

В случае упорядочения физических записей задача сортировки сводится к задаче переразмещения [12, 35] отождествлением членов соотношения (I.I) с порядковыми номерами физических записей в искомой перестановке.

В зависимости от типа используемой рабочей памяти сортировка подразделяется на два класса:

внутренняя сортировка; внешняя сортировка.

Внутренняя сортировка предполагает использование в качестве рабочей памяти только ОП, а внешняя - как оперативной, так и внешней памяти типа, например, ЩД и накопителей на магнитных лентах (НМЛ).

Основными практическими приложениями сортировки являются: обеспечение эффективной совместной обработки нескольких Щ (например, при актуализации ВД);

упорядочение информации при загрузке и реструктуризации баз данных;

упорядоченное представление данных, облегчающее их анализ (например, распечатка ведомостей в приемлемом для пользователя порядке);

группировка данных;

обеспечение эффективной последовательной обработки одного ВД в заданном порядке;

обеспечение эффективной внутренней обработки данных, представленных в виде таблиц, списков и других структур.

Переразмещение используется для уменьшения времени последующих обращений к переразмещенным данным. Типичными примерами переразмещений являются сжатие библиотечных Щ [20, 38] и размещение Щ на магнитном носителе в оптимальном порядке с точки зрения уменьшения времени их последующей совместной или мультипрограммной обработки [3, 37] .

class2 АЛГОРИТМЫ СОРТИРОВКИ В ОГРАНИЧЕННОЙ ПО ОБЪЕМУ

И КОНФИГУРАЦИИ ВНЕШНЕЙ ПАМЯТИ class2

Анализ балансного слияния

На рис. 2.1 показана схема балансного слияния при М=15, Q =6 и Р =3 (выражение вида т т обозначает сли тые последовательности с номерами от т., до тг ).

Анализ ЭТОГО примера показывает, что распределение последовательностей в один и тот же рабочий ЦЦ осуществляется неравномерно, Так, например, для ЦЦ Ff это распределение можно представить в виде выражения (5,0,9), где цифры обозначают число первоначальных последовательностей, записанных в этот ЦЦ во время выполнения соответственно первого, второго и третьего шагов слияния. Очевидно, что имеет смысл получить эту характеристику в виде зависимости числа первоначальных последовательностей, размещенных в рабочем ЦЦ, от номера соответствующего шага слияния, т.е. шага, на котором они были записаны в этот ЦЦ. Тогда, зная заранее длину первоначальной последовательности, а также величины М, P,L и Q. можно определить требуемый (минимально возможный) объем каждого рабочего ЦЦ. Это даст возможность более гибко и рационально использовать магнитные носители различной емкости . Кроме того, имея такую зависимость, можно решить и обратную задачу, т.е. при заданных длине первоначальной последовательности, величинах Р и Q , а также при заданных объемах Q рабочих ЦЦ определить максимальное число входных записей, которое можно упорядочить посредством балансного слияния.

Обозначим через Sn L (рис. 2.2) п -ю последовате льность (подстроку), записанную в I -й рабочий ЦЦ на j -м шаге слияния (здесь п. = I, МУ} , где М/ - об щее число последовательностей, записанных в і -й рабочий ЦЦ на j -м шаге слияния). Строкой /г /-го шага слияния назовем множество вида Dn =ort f , включающее в се бя все подстроки с номером п. , полученные на j -м шаге слияния. Заметим, что число таких подстрок (число значений і ) может быть равно или меньше бы на одном из циклов i -gJ \ h.J_1 , Где &,_, h f} то подстрока Sn L является неполной. Заметим, что на некотором шаге слияния формируется только одна неполная подстрока.

В свою очередь, если строка Вп состоит только из полных подстрок, число которых равно (}j , то эта строка является полной. Если же строка Dft включает в себя неполную подстроку или число подстрок в ней меньше , то строка Dn является неполной. При этом очевидно, что на некотором шаге слияния неполной может быть только одна строка.

Легко определить, что число p(j) первоначальных последовательностей в полной строке на первом шаге слияния равно Р , на втором P(Q-P) , на третьем - Р (Q-P) и т.д. Очевидно, что на J -м шаге слияния

Сжатие данных

Опишем метод сжатия х, разработанный на базе описанных в [ЮЗ] разностных методов. Сжатие данных при использовании компаративного метода осуществляется поблочно. При этом первая запись блока хранится в обычном, а остальные записи -в сжатом виде. Текущая запись упаковывается по отношению к предыдущей группами по восемь байт. Каждая сжатая запись включает в себя служебную часть, характеризующую определенным образом некоторые элементы этой записи, и информационную часть, включающую в себя байты текущей записи, несравнившие-ся с соответствующими байтами предыдущей записи. Структура блока, состоящего из п сжатых записей, показана на рис. 4.1 (в скобках указана длина соответствующего поля). Характеристика того или иного элемента записи может принимать два значения: 0 - при равенстве элемента текущей записи аналогичному элементу предыдущей записи и I - при неравенстве данных элементов (в случае, когда характеристика некоторой группы байт равна 0, соответствующие характеристики байт этой группы в служебную часть не включаются).

Очевидно, что компаративный метод можно использовать для сжатия не только рабочих ВД, но и, например, дерева сортировки, что дает возможность формировать более длинные первоначальные последовательности. Проанализируем целесообразность данного приложения метода. Известно [25] , что для

В дальнейшем будем называть этот метод компаративным.сортировки на дисках. Следовательно, для сжатых рабочих Щ при том же объеме сортируемого где k - усредненный коэффициент сжатия рабочих Щ. Таким образом, число просмотров при использовании компаративного метода уменьшается на величину, приблизительно равную $pk- В то же время выше отмечалось, что для ЦД, используемых в АСУ, коэффициент сжатия в среднем равен 4, Таким образом, сжатие дерева сортировки целесообразно производить при Р 4

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ

Для оценки эффективности выполнения в МВС основных алгоритмов параллельной сортировки выполним сравнительный анализ алгоритмов, описанных в гл. I, а именно простого двупутевого слияния, сетей сортировки и обменной сортировки со слиянием. При этом будем полагать, что число процессоров в МВС равно N/2. ( N - число сортируемых записей).

Введем следующие величины: число компараторов в сети сортировки N записей; среднее значение времени выполнения і -го алгоритма параллельной сортировки в однопроцессорной ЭВМ 3 идентифицирует соответственно простое двупутевое слияние, сеть и обменную сортировку со слиянием); среднее значение времени выполнения I-го алгоритма параллельной сортировки в оэффициент эффективности t-ro алгоритма параллельной сортировки, определяемый из выражения

Будем считать, что ветви анализируемых алгоритмов функционально эквивалентны и что время г выполнения каждой ветви является случайной величиной, определенной в соответствии с функцией F(r) равномерного распределения в интервале [nmtn, «« ] » гАе Ъпи . и г - соответственно нижняя и верхняя границы времени выполнения ветви при условии совместной обработки двух записей, а у коэффициент, учитывающий динамическое изменение числа последователь но выполняемых операций обработки записей в ветвях параллельной сортировки (для сети и обменной сортировки со слиянием

Для удобства анализа будем считать, что в процессе выполнения ветви перемещаются не сами записи, а их адреса, т.е. суммарное время пересылки пренебрежимо меньше суммарного времени сравнения записей. Следовательно, величина у/ определяет число сравнений х, выполняемых последовательно в одной ветви параллельной сортировки. Примем также N-2.n, где п - целое число, большее I.

Принципы построения ГС

В основу проектирования ГС положены следующие основные принципы.

1) ГС должен представлять собой программный продукт, реализующий разнообразные функции и возможности. Учитывая это, наиболее целесообразной является многоуровневая модульная организация ГС, на первом уровне которой необходимо разместить управляющий модуль ГС, на втором - фазы ГС (фазы распределения, промежуточного слияния и т.п.). Каждая фаза, в свою очередь, разбивается на модули, реализующие те или иные функции ГС (третий уровень). Программные секции или подпрограммы, из которых состоят модули, представляют четвертый уровень организации ГС.

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

3) Так как число модулей, составляющих одну фазу, по всей вероятности, должно быть довольно большим, то с целью экономного расходования ОП в ГС необходимо использовать оверлейный и динамический методы комбинирования программ, предполагающие использование гораздо меньшего объема ОП по сравнению с другими методами комбинирования программ [33]

4) Учитывая широкое распространение в сфере вычислительных услуг ЕС ЭВМ, ГС должен быть ориентирован на использованиє в СОД, техническую основу которых составляют модели именно этой системы ЭЕМ. Принимая во внимание это обстоятельство, ГС необходимо придать свойство моделенезависимой системы, способной функционировать на ЭВМ семейств как "Ряд-1", так и "Ряд-2" или "Ряд-3". При этом в случае функционирования ГС на ЭВМ семейств "Ряд-2" и "Ряд-3" целесообразно использовать расширенный набор команд этих ЭВМ, содержащий, в частности, команды, позволяющие резко уменьшить затраты процессорного времени на сжатие и распаковку записей х.

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

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

7) В число диагностических сообщений, выдаваемых в процессе работы ГС и позволяющих контролировать ход сортировки, необходимо ввести сообщения, использование которых носит статистический характер. Так, например, по окончании сортировки имеет смысл выдать сообщение о минимальном значении коэффициента сжатия рабочих ЦД, достигнутом в процессе сортировки. Это значение может быть использовано при последующей сортировке аналогичного НД для задания уточненной величины объема