автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Эффективные алгоритмы и технология сортировки данных в АСУ

ВВЕДЕНИЕ

Глава 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Д. Задача переразмещения

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

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

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

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

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

3.7. Алгоритм 6.

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

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

3.10. Выв оды.

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

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

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

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

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

4.5. Выводы.

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

СОРТИРОВКИ.

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

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

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

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

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

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

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

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

Вопросам теории и практики сортировки посвящено немало фундаментальных трудов, среди которых следует отметить работы советских ученых В.М.Глушкова [14] , А.А.Папернова и

B.А.Лодымова [39] , С.С.Лаврова и И.Л.Гончаровой [32] ,

C.Н.Селеткова и Б.Г.Волкова [43] , Э.А.Трахтенгерца [48] , а также американских ученых Д.Кнута [25] , Г.Лорина [Зб] и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные результаты проведенных в настоящей работе разработок и исследований заключаются в следующем.

1) Обоснованы возможности и пути повышения эффективности процедуры сортировки в АСУ.

2) Разработаны и исследованы алгоритмы сортировки в ограниченной по объему и конфигурации внешней памяти. Применение данных методов позволяет уменьшить на 10-20$ общее время сортировки и повысить в среднем в 1,5-2,0 раза коэффициент нагрузки рабочей памяти сортировки.

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

4) Разработаны эффективные алгоритмы переразмещения данных, минимизирующие суммарное время переразмещения за счет уменьшения времени поиска порядка переразмещения данных.

5) Разработан и исследован ряд общих методов повышения эффективности сортировки данных, использование которых позволяет увеличить в 3-6 раз коэффициент нагрузки рабочей памяти сортировки и уменьшить на 20-50$ общее время сортировки. в) Проведен сравнительный анализ основных алгоритмов параллельной сортировки с точки зрения оценки эффективности их функционирования в МВС. Даны рекомендации по применению этих алгоритмов в МВС с различным числом процессоров.

7) Сформулированы основные принципы построения ГС. Это позволило создать достаточно гибкий и развитый программный аппарат ГС, универсальность которого с точки зрения параметров среды функционирования дает основание считать его программным продуктом, предназначенным для широкого применения.

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

ЗАКЛЮЧЕНИЕ

1. Основные направления экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года. -М.: Политиздат, 1981. 95 с.

2. Материалы внеочередного Пленума Центрального Комитета КПСС, 13 февраля 1984 года. М.: Политиздат, 1984, -32 с.

3. АВЕН О.И., ГУРИН Н.Н., КОГАН Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

4. АЛЬЯНАХ И.Н. Внешние запоминающие устройства ЕС ЭВМ. М.: Сов.радио, 1979. - 208 с.

5. АНДОН Ф.И., ДЕРЕЦКИЙ В.А., КРАСНОКУТСКИЙ Н.Г., НЕЧИТАЙЛО А.В. Опыт внедрения системы интегрированной мультипрограммной обработки данных. УСиМ, 1984, № I, с. II2-II5.

6. АВДОН Ф.И., ДЕРЕЦКИЙ В.А., ПОЛЯЧЕНКО Б.Е. Интегрированное мультипрограммирование в ОС ЕС. УСиМ, 1982, № 5, с. 5862.

7. АТОВМЯН И.О., ВАЙРАДЯН А.С., ОНЫКИЙ Б.Н. Мультипроцессорные вычислительные системы/Под ред. Я.А.Хетагурова. М.: Энергия, 1971. - 320 с.

8. АХО А., ХЛОПКРОФТ Дж., УЛЬМАН Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

9. БИТЕЛЬ Ю.И., ВОЮШ В.И., ГОРБУНОВА Р.В. и др. Операционная система ДОС ЕС: Справочник. М.: Статистика, 1977. -272 с.

10. БРИЧ З.С., ВОЮШ В.И., ДЕГТЯРЕВА B.C. и др. Программирование на языке Ассемблера ЕС ЭШ. М.: Статистика, 1975. -296 с.

11. Вычислительная техника и обработка данных. Терминологический толковый словарь фирмы IBM. М.: Статистика, 1978. - 232 с.

12. ГЕНДЕЛЬ Е.Г., ЛЕВИН Н.А. Оптимизация технологии обработки информации в АСУ. М.: Статистика, 1977. - 232 с.

13. ГЛУШКОВ В.М. Индустрия переработки информации. Коммунист, 1977, № 12, с. 14-19.

14. ГЛУШКОВ В.М., ГЛАДУН В.П., ЛОЗИНСКИЙ Л.С. и др. Обработка информационных массивов в автоматизированных системах управления. Киев: Наукова думка, 1970. - 250 с.

15. ГУДМАН С., ХИДЕТНИЕМИ С. Введение в анализ и разработку алгоритмов. М.: Мир, 1978. - 368 с.

16. ГУКАСОВ В.Г., ТИЩЕНКО С.П. Поиск и сортировка информации в ЭВМ. М.: ЦНИИ; атоминформ, 1975. - 109 с.

17. ДАНИЛОЧКИН В.П., МИТРОФАНОВ В.В., ОДИНЦОВ Б.В. и др. Операционная система ОС ЕС: Справочное пособие/Под ред. Л.Д. Райкова. М.: Статистика, 1980. - 480 с.

18. ДАНИЛОЧКИН В.П., ОДИНЦОВ Б.В., ПЕЩОВ Г.В. Справочник системного программиста по операционной системе ОС ЕС/ Под ред. Л.Д.Райкова. М.: Статистика, 1982. - 288 с.

19. ДВДЦ Д. Работа с файлами. М.: Мир, 1975. - 144 с.

20. ДОНОВАН Дж., МЭДНИК С. Операционные системы. М.: Мир, 1978. - 792 с.

21. ЕНИКЕЕВА Е.Х., ЗАГАЦКИЙ Б.А., ЛАРИОНОВ К.А. и др. Единая система ЭВМ/Под ред. А.М.Ларионова. М.: Статистика, 1974. - 136 с.

22. ЗАЙЦЕВА ffi.H. Программирование в ОС ЕС на базе языка Ассемблера. М,: Финансы и статистика, 1981. - 320 с.

23. КАТЦАН Г. Операционные системы. М.: Мир, 1976. - 472 с.

24. КНУТ Д. Искусство программирования для ЭВМ: Основные алгоритмы. М.: Мир, 1976. - Т. I, 736 с.

25. КНУТ Д. Искусство программирования для ЭВМ: Сортировка и поиск. М.: Мир, 1978. - Т. 3, 844 с.

26. КРАСНОКУТСКИЙ Н.Г. Балансное слияние с однократным резервом рабочей памяти. УСиМ, 1982, № 3, с. 89-92.

27. КРАСНОКУТСКИЙ Н.Г. Некоторые принципы построения генератора сортировки комбинированного типа. В кн.: Теоретические и прикладные вопросы проектирования АСУ. Киев: Институт автоматики, 1983, с. 49-52.

28. КРАСНОКУТСКИЙ Н.Г. Сортировка на дисках с ограниченным объемом рабочей памяти. В кн.: Теоретические и прикладные вопросы проектирования АСУ. Киев: Институт автоматики, 1983, с. 42-49.

29. КРАСНОКУТСКИЙ Н.Г. Сравнительный анализ некоторых методов параллельной сортировки. В кн.: Распределенные банки данных и информационно-поисковые системы. Киев: ИК АН УССР, 1982, с. 61-71.

30. КРАСНОКУТСКИЙ Н.Г., МИЛЮТИН В.В., ПОЛОСЬМАК В.М., РЕПЕЦ-КИЙ В.Л., РОГАЧЕВ В.И. Программно-аппаратный комплекс на базе ЭВМ "Минск-32" и EC-I022. УСиМ, 1979, № 2, с. 107109.

31. КРАСНОКУТСКИЙ Н.Г., ПОЛОСЬМАК В.М., РЕПЕЦКИЙ В.Л. Опыт разработки системы конвертирования данных. УСиМ, 1979, № 4, с. 134-136.

32. ЛАВРОВ С.С., ГОНЧАРОВА Л.И. Автоматическая обработка данных: Хранение информации в памяти ЭВМ. М.: Наука, 1971. - 160 с.

33. ЛЕСЮК В.Г., МАРКОВ А.С., ПЕЩОВ Г.В. и др. Система математического обеспечения ЕС ЭВМ/Под ред. А.М.Ларионова. -М.: Статистика, 1974. 216 с.

34. ЛИТВИНОВ В.А. Алгоритм оптимизации размещения массивовданных на магнитной ленте. Кибернетика, 1970, № 4, с. 120-123.

35. ЛИТВИНОВ В.А., КРАСНОКУТСКИЙ Н.Г., САФОНОВА А.В. Алгоритмы перекомпоновки данных во внешней памяти методом групповой выборки. В кн.: Модели и алгоритмы автоматизированных систем в промышленности. Киев: ИК АН УССР, 1982, с. 33-41.

36. ЛОРИН Г. Сортировка и системы сортировки. М.: Наука, 1983. - 384 с.

37. МАРТИН Дж. Организация баз данных в вычислительных системах. 2-е изд., доп. - М.: Мир, 1980. - 662 с.

38. МИТРОФАНОВ В.В., ОДИНЦОВ Б.В. Программы обслуживания ОС ЕС ЭВМ. М.: Статистика, 1977. - 136 с.

39. ПАПЕРНОВ А.А,, ПОДЫМОВ В.А. Методы упорядочения информации в цифровых системах. М.: Наука, 1973. - 384 с.

40. ПЕРВИН Ю.'А., ШЕВЯКОВА Т.К. Динамические информационные системы на предприятии. М.: Статистика, 1975. - 232 с.

41. ПОСПЕЛОВ Д.А. Введение в теорию вычислительных систем. -М.: Сов.радио, 1972. 300 с.

42. ПРЖИЯЛКОВСКИЙ В.В., ЛОМОВ Ю.С. Технические и программные средства Единой системы ЭВМ. М.: Статистика, 1980, -230 с.

43. СЕЛЕТКОВ С.Н., ВОЛКОВ Б.Г. Организация хранения и поиска данных в информационно-логических системах. М.: Сов.ра-дио, 1971, - 224 с.

44. Система ИБМ-360. Введение в запоминающие устройства цря-мого доступа и методы организации данных. М.: Статистика, 1974. - 127 с.

45. ТИМОФЕЕВ Б.Б., ЛИТВИНОВ В.А. К вопросу об оптимизации размещения массивов информации в памяти на магнитных лентах.- Кибернетика, 1969, J5 4, с. 32-40.

46. ТИМОФЕЕВ Б.Б., ЛИТВИНОВ В.Л. Технология обработки данных в ЛСУП. Киев: Техника, 1978. - 176 с.

47. ТШШЕЕВ Б.Б., ЛИТВИНОВ В.А., САПОШИКОВ А.С. Оптимизация марковского процесса обращений к памяти с последовательным доступом. Кибернетика, 1972, JS 2, с. 40-50.

48. ТРАХТЕКГЕРЦ Э.А. Программное обеспечение автоматизированных систем управления. М.: Статистика, 1974. - 288 с.

49. ХОЛЛ П. Вычислительные структуры: Введение в нечисленное программирование. Ы.: Мир, 1978. - 214 с.

50. ХУСАИНОВ Б.С. Программирование ввода-вывода в ОС ЕС ЭШ на языке Ассемблера. М.: Статистика, 1980. - 264 с.51 . BATCHER К. Sorting networks and their applications. -Proc. AFIPS, 1968, v. 32, p. 307~314.

51. BAYES A. A generalized partial-pass block sort, CACM, 1968, v. 11, N 7, p. 491-493.

52. BEUS H. The use of information in sorting. JACM, 19-70, v. 17, N 3, P. 482-495.

53. ВЕШШТТ В., FRAZER W. Approximating optimal direct access merge perfomance. Proc. of the IFIP congress, 1971, v. 1, p. 450-453.

54. BLACK Ж. Optimum merging from mass storage. ~ CACM, 1970, v. 13, Ы 12, p. 745-749.

55. BROWN В., GUSTAVSON P., MANKIN E. Sorting in a paging environment. CACM, 1970, v. 13, N 8, p. 483-494.

56. BURGB W. Sorting, trees, and measures of order. Information and control, 1958, H 1, p. 181-197.

57. BURGE W. Analysis of compromise merge sort techniques. -Proc. of the IFIP congress, 1971, v. 1, p. 454-459,

58. COOKE W. A tape file merge pattern generator. CACM, 1963, v. 6, U 5, p. 227-230.

59. DINSMORE R. Longer strings from sorting. CACM, 1965, v. 8, N 1, p. 48.

60. EVEN S. Parallelism in tape-sorting. CACM, 1974, v. 17, N 4, p. 202-204.

61. PALKIN J., SAVASTANO S. Sorting with large volume, random access, drum storage. CACM, 1963, v. 6, И 5, p. 240-244.

62. FERGUSON D. Buffer allocation in merge sorting. CACM,1971, v. 14, N 7, P* 476-478.

63. FLORES I. Analysis of internal computer sorting. JACM, 1961, v. 8, N 1, p. 41-80.

64. FRAZER A. User control in a multi-access system. Сотр. J., 1968, v. 11, N 1, p. 12-16.

65. PRAZER Integrity of a mass storage filing system. Сотр. J., 1969, v. 12, N 1, p. 1-5.

66. PRAZER A. Data compression and automatic programming. -Сотр. J., 1967, v. 10, N 2, p. 165-167.

67. PRAZER W., BENNETT B. Bounds on optimal merge perfomance and a strategy for optimality. JACM, 1972, v. 19, N 4, p. 641-648.

68. PRAZER W., WONG C. Sorting Ъу natural selection. CACM,1972, v. 15, N 10, p. 910-912.

69. FRENCH N. Computer planned collates. CACM, 1963, v. 6, N 5, p. 225-226.

70. GASSNER B. Sorting by replacement selecting. CACM, 1967* v. 10, N 2, p. 89-93.

71. GAVRIL P. Merging with parallel processors. CACM, 1975, . v. 18, N 10, p. 588-591.73» GILSTAD R. Polyphase merge sorting an advanced technique.- Proc. APIPS, 1960, v. 18, p. 143-148.

72. GILSTAD R. Read-backward polyphase sorting. CACM, 1963,

73. V. 6, N 5, p. 220-223. 75» GOETZ M. Internal and tape sorting using the replacement-selection technique. CACM, 1963, v. 6, N 5, p. 201-206.

74. GOETZ M. Organization and structure of data on disk file memory systems for efficient sorting and other data processing programme. CACM, 1963» v. 6, N 5, p. 245-248.

75. GOETZ M. Design and characteristics of a variable-length record sort using new fixed-length record sort techniques.- CACM, 1963, v. 6, N 5, p. 264^267.

76. GOEIZ M. Some improvements in the technology of string merging and internal sorting. Proc. APIPS, 1964, v. 25,p. 599-607.

77. GOETZ M., TOIH G. A comparison between the polyphase and oscillating sort techniques. CACM, 1963, v. 6, N 5,p. 223-225.

78. GONGALEZ I., MARIO I., RAMAMOORTHY C. Program suitability for parallel processing. IEEE Trans, on сотр., 1971, v. c-20(6), N 6, p. 647-654.81.'GOODMAN J. Auditing magnetic tape systems. Сотр. J,, 1964j v. 7, N 1, p. 4-7.

79. GOTLIEB C. Sorting on computers. CACM, 1963, v. 6, N 5, p. 194-201.

80. HALL Mm A method of comparing the time requirements of sorting methods. CACM, 1963, v. 6, N 5, p. 259-263.

81. HIBBARD T. Some combinatorial properties of certain trees with application to searching and sorting. JACM, 1962,1. Y. 9, N 1, p. 13-28.85» HIBBARD T. A simple sorting algorithm.- JACM, 1963» v. 10, N 2, p. 142-150.

82. HIBBARD I. An. empirical study of minimal storage sorting. CACM, 1963, v. 6, N 5, P. 206-213.87♦ HILDERBRANDT P., ISBITZ H. Radix exchange an internal sorting method for digital computers. — JACM, 19591 v. 6, N 2, p. 156-163♦

83. HIRSCHBERG D. Past parallel sorting algorithms. CACM, 1978, v. 21, N 8, p. 657-661.

84. HOOKER W. On the expected lengths of sequences generated in sorting by replacement selection. САШ, 1969, v. 12, N 7, p. 411-413.

85. HUBBARD G. Some characteristics of sorting in computing systems using random access storage devices. CACM, 1963, v. 6, N 5, p. 248-255.

86. IBM SYSTEM/360 OPERATING SYSTEM; OS sort/merge general information. Order No. GC33-4022-1. IBM Corp., White Plains, N. Y., 1973, - 204 p.

87. KNUTH D. Length of strings for a merge sort. CACM, 1963, v. 6, N 11, p. 685-688.

88. LOCKEMANN P., KNUTSEN W. Recovery of disk contents after system failure. CACM, 1968, v. 11, N 8, p. 542-549.

89. MACLAREN M. Internal sorting by radix plus shifting. -JACM, 1966, V. 13, N 3, p. 404-411•

90. MALCOLM W. String distribution for the polyphase sort. -CACM, 1963, v. 6, N 5, P. 217-220.

91. MANKER H. Multiphase sorting. CACM, 1963, v. 6, N 5, p. 214-217.

92. MARRON В., de MAINE P. Automatic data compression. CACM, 1967, v. 10, N 11, p. 711-721.

93. MARTIN W. Sorting. Сотр. surv., 1971, v. 3, N 4, p. 147-174.99* McALLESIER R. Polyphase sorting with overlapped rewind. -CACM, 1964, v. 7, N 3, p. 158-159.

94. MYERS W. Data compression by hardware and software. Datamation, 1966, v. 12, N 4, p. 39-43.

95. NICHOLS J., T3EDRICH A. A multivariant generalized sort program employing auxiliary drum storage. Proc. ACM 17th Nation, conf., 1962, p. 102-103.

96. RADKE C. Merge-sort analysis by matrix techniques. IBM Syst. J., 1966, v. 5, N 4, p. 226-247*

97. RAMAMOORIHY C., WAH B. Data management in distributed data bases. Proc. AFIPS, 1979, v. 48, p. 667-680.104* REYNOLDS S. A generalized polyphase merge algorithm. -CACM, 1961, v. 4, N 8, p. 347-349.

98. SCHICK 1. Disk file sorting. CACM, 1963, v. 6, N 5, p. 330-339.

99. SHELL D. Optimizing the polyphase sort* CACM, 1971, v. 14, N 11, p. 713-719.

100. SOBEL S. Oscillating sort a new sort merging technique. - JACM, 1962, v. 9, N 3, p. 372-375.

101. WAKS D. Conversion, reconversion and comparison techniques in variable-length sorting. CACM, 1963, v. 6, N 5,p. 267-272.

102. WOODRUM L. Internal sorting with minimal comparing. IBM Syst. J., 1969, v. 8, N 3, p. 189-203.

103. WOODRUM L. A model of floating buffering. IBM Syst. J.,1970, v. 9, N 2, p. 118-144.