Эффективные алгоритмы и технология сортировки данных в АСУ

• Автор: Краснокутский, Николай Григорьевич
• Шифр специальности: 05.13.06
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 159 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ .

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

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

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

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

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

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

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

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

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

1.9. Постановка задач разработки и исследования .
Глава 2. АЛГОРИТМЫ СОРТИРОВКИ В ОГРАНИЧЕННОЙ ПО ОБЪЕМУ
И КОНФИГУРАЦИИ ВНЕШНЕЙ ПАМЯТИ .
2.1. Анализ балансного слияния .
2.2. Алгоритмы сортировки в ограниченной по объему внешней памяти .
2.3. Алгоритм сортировки в ограниченной по конфигурации дисковой памяти
2.4. Выводы.
Стр.
Глава 3. АЛГОРИТМЫ ПЕРЕРАЗМЕЩЕНИЯ ДАННЫХ .
3.1. Задача переразмещения .
3.2. Алгоритм I.
3.3. Алгоритм 2 .
3.4. Алгоритм 3.
3.5. Алгоритм 4 . .
3.6. Алгоритм 5.
3.7. Алгоритм б.
3.8. Алгоритм 7.
3.9. Оценка эффективности алгоритмов переразмещения .
3 Выв оды.
Глава 4. ОБЩИЕ МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРОЦЕДУРЫ СОРТИРОВКИ.
4.1. Сжатие данных
4.2. Мультизадачный режим в алгоритме перекрестного слияния.
4.3. Метод динамического управления ОП в мультизадачной среде.
4.4. Загрузка буферного пула с использованием каталога ключей .
4.5. Выводы
Глава 5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ
СОРТИРОВКИ.
Глава б. ПРИНЦИПЫ ПОСТРОЕНИЯ И ОРГАНИЗАЦИИ ГС . .
6.1. Принципы построения ГС
6.2. Общая организация ГС ПО
6.3. Функции и возможности ГС
6.4. Некоторые выводы и рекомендации
ЗАКЛЮЧЕНИЕ.
СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


В то же время резервы повышения эффективности процедуры сортировки с точки зрения увеличения быстродействия и более экономного расходования внешней рабочей памяти в ППС ОС ЕС далеко не исчерпаны. ОП). Цель работы* Целью настоящей работы является разработка и исследование алгоритмов и программных средств сортировки, позволяющих увеличить коэффициент нагрузки рабочей памяти и быстродействие сортировки в среде ОС ЕС. Методы разработки и исследования: построение алгоритмов и аналитических моделей на базе основных положений теории чисел, комбинаторного анализа и теории вероятностей. Научная новизна работы. Под коэффициентом нагрузки рабочей памяти сортировки будем понимать отношение объема (в байтах) входного НД к суммарному объему (в байтах) рабочих НД. ГС) для ЕС ЭВМ. ГС, эксплуатируемое в составах АСУ Киевского авиапроизводственного объединения, Таганрогского механического завода, Киевского производственного объединения реле и автоматики и Рошальского химкомбината. Суммарный годовой экономический эффект от внедрения ГС составляет в настоящее время около тыс. Апробация_работы. Банки данных" (Ташкент, ИК АН УзССР, ). Работа включает в себя, помимо введения, шесть глав, заключение и два приложения. В первой главе делается обзор и критический анализ эффективных алгоритмов внутренней и внешней сортировки, алгоритмов переразмешрния, общих (технологических) методов повышения эффективности сортировки данных и высокопроизводительных программных средств сортировки. Показывается их взаимосвязь при сортировке ВД. Рассматриваются их характерные особенности. Формулируется постановка конкретных задач разработки и исследования. Во второй главе описываются алгоритмы сортировки в ограниченной по объему и конфигурации внешней памяти, подробно освещены и проанализированы особенности балансного слияния. Даются рекомендации по использованию полученных характеристик балансного слияния для уменьшения объема внешней рабочей памяти. Описывается модифицированный алгоритм балансного слияния, потребляющий вдвое меньшую по объему внешнюю память по сравнению с используемым в ППС ОС ЕС алгоритмом стандартного балансного слияния. В четвертой главе рассматриваются общие (технологические) методы повышения эффективности процедуры сортировки. Описывается разностный метод сжатия, позволяющий значительно повысить коэффициент нагрузки рабочей памяти сортировки. Приводятся его экспериментальные характеристики. Рассматриваются особенности использования мультизадачного режима в алгоритмах внешней сортировки. Приведена схема динамического управления ОП, позволяющая повысить эффективность выполнения сортировки в мультизадачной среде типа, например, среды СИМОД [б] • Подробно описывается алгоритм эффективной загрузки буферного пула. В пятой главе анализируются некоторые алгоритмы параллельной сортировки, ориентированные на использование в МВС. Даются рекомендации по практическому использованию этих алгоритмов в МВС. В шестой главе формулируются основные принципы построения ГС. Приводятся его функциональная структура и состав. В заключении освещаются основные теоретические и практические результаты работы. В приложения включены распечатки модулей ГС и акты внедрения. Глава I. Под сортировкой или упорядочением понимается процесс распределения множества элементов по группам в соответствии с некоторыми определенными правилами [II] . В формализованном виде задача сортировки определяется следующим образом. Пусть дано множество, состоящее из записей х Ин. При этом запись ? М ^ ^ ях(н) . В случае упорядочения физических записей задача сортировки сводится к задаче переразмещения [, ] отождествлением членов соотношения (1. Под записью будем понимать не только логическую, но и физическую запись, представляющую собой множество логических записей в виде блока записей,ЦЦ и т. Здесь и далее будем считать, что упорядочение выполняется, если это не оговаривается отдельно, по возрастанию ключей. Переразмещение используется для уменьшения времени последующих обращений к переразмещенным данным. СОД конвейерного типа, одной из которых является СИМОД).