Содержание к диссертации
стр.
ВВЕДЕНИЕ 5
I. МЕТОДИКА ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНЫХ ПАРАМЕТРОВ ФАЙЛОВ
(БАЗ ДАННЫХ) ДЛЯ РЕГУЛЯРНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОБРАБОТКИ ДАННЫХ
-
Постановка общей задачи определения оптимальных параметров файлов (баз данных)для регулярной последовательности обработки данных 13
-
Многоуровневое проектирование информационного
фонда АСУ 25
1.3. Задачи сокращения времени доступа за счет выбора
оптимальных параметров файлов (баз данных) 33
Краткие выводы 44
'П. МЕТОД ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ БЛОКОВ В ФАЙЛЕ ПРЯМОГО ДОСТУПА
2.1. Постановка задачи оптимального размещения блоков
в файле прямого доступа 45
-
Сведение задачи оптимального размещения блоков по цилиндрам МД к набору задач линейного целочисленного программирования 52
-
Метод решения задачи оптимального размещения блоков
в файле прямого доступа 56
Краткие выводы 67
Ш. АЛГОРИТМ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ БЛОКОВ ФИКСИРОВАННОЙ ДЛИНЫ В ФАЙЛЕ ПРЯМОГО ДОСТУПА ЗЛ. Свойства множества перестановок блоков фиксирован- 68
ной длины
-
Доказательство сходимости алгоритма 71
-
Оптимальное размещение блоков в группе с фиксированным корневым элементов 74
-
Оптимальное размещение блоков в группе со
свободным корневым элементом 76
-
Алгоритм переноса элементов в группе со свободным корневым элементом 84
-
Свойства множества эквивалентных перестановок 90
-
Оценка временной сложности алгоритма 93
-
Эвристические алгоритмы задачи размещения блоков ....
в файле прямого доступа 98
Краткие выводы 105
IV. АЛГОРИТМ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ БЛОКОВ ПЕРЕМЕННОЙ
ДЛИНЫ В ФАЙЛЕ ПРЯМОГО ДОСТУПА
-
Свойства множества перестановок блоков переменной длины 106
-
Определение достаточных условий оптимальности Ю9
-
Свойства множества эквивалентных перестановок Ц4
4.4 Оценка временной сложности алгоритма 115
Краткие выводы 117
V. ОБЛАСТЬ ПРИМЕНЕНИЯ АЛГОРИТМОВ
-
Измерение времени доступа, связанного с перемещением механизма доступа МД 121
-
Модификация метода доступа ЫЗАМ ОС ЕС J22
-
Схема использования в СУБД ОКА или СУБД IMS 127
-
Схема использования в СУБД ИНЕС 131
-
Схема использования в СУБД A"DABAS
-
Программное обеспечение алгоритма оптимального
размещения блоков фиксированной длины в файле
прямого доступа и алгоритма блокирования запи
сей в файле прямого доступа 135
5.7 Расчет экономической эффективности 146
Краткие выводы 148
ЗАКЛЮЧЕНИЕ 150
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 153
ПРИЛОЖЕНИЯ 166
Введение к работе
Возросший за последние годы интерес к проблеме индустриальных методов проектирования АСУ объясняется стремлением формализованно учесть наибольшее количество факторов, влияющих на процессы обработки информации в АСУ и их взаимосвязи, с целью выработки оптимального по стоимостным критериям информационного, программного и технического обеспечения АСУ, ориентированного на объект управления. Актуальность всей проблемы подчеркивается в документе "Основные направления экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года", в котором указана "необходимость совершенствования вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации".
Одной из наиболее важных задач в рамках решения этой проблемы является задача сокращения времени доступа при обработке данных в АСУ* Актуальность этой задачи подчеркивается тем, что коэффициент отношения процессорного времени к общему времени выполнения программы для большинства программ обработки данных в АСУ колеблется в пределах от 0,2 до 0,5 (по статистике, взятой из ОАСУчермет), и, следовательно, минимизация времени доступа, вносит основной вклад в сокращение машинного времени при обработке информации.
На пути решения проблемы сокращения времени доступа при обработке данных в АСУ встречается ряд трудностей организационного и методологического характера, одна из которых - отсутствие формализованного представления входной информации об объекте управления, необходимой для решения оптимизационных задач. Другая трудность заключается в том, что проблема сокращения времени доступа является многоаспектной и решается на разных уровнях проектирования АСУ. Наиболее конструктивным подходом решения этой проблемы является многоуровневое проектирование информационного фонда (МФ) АСУ, в результате которого создается ряд моделей: информационная, концептуальная, логическая и физическая. Наибольшее количество составляющих времени доступа оптимизируется на уровне физической модели ИФ, представленной совокупностью файлов или баз данных (БД) и их параметров, таких как: организация файла, длина блока в, файле, размер файла в блоках, размещение файлов на магнитных дисках, размещение блоков в файлах, число файлов.
Целью работы является разработка методики решения общей задачи сокращения времени доступа группы функциональных программ АСУ, относящихся к некоторой подсистеме АСУ, путем определения вышеперечисленных оптимальных параметров файлов или баз данных, а также разработка метода и алгоритмов решения задачи оптимального размещения блоков в файле прямого доступа (ФДЦ) и задачи блокирования записей в ФЦЦ по критерию сокращения времени доступа группы функциональных программ АСУ, обращающихся к одним записям или блокам, размещенным в ФДЦ.
Примерами ФДЦ являются: прямой набор данных ОС ЕС [42] , VIO - файл СУБД ИНЕС [48] , БЦ НИ AM СУ&ДЩ&7], "область хранения данных" СУБД Ад А В AS [&9]*
В основу исследования положено использование некоторых методов математического анализа, комбинаторики и дискретной оптимизации.
Результатами работы являются: - постановка общей задачи сокращения времени доступа группы функциональных программ АСУ с регулярной последовательностью обработки данных за счет определения оптимальных параметров
7 файлов или БД (длина блока, размещение блоков в ФЦЦ, состав блоков ФЦЦ в записях, размер файла в блоках, организация файлов и размещение их на МД)> разработка методологической схемы решения этой задачи; разработка метода оптимального размещения блоков в ФЦЦ по критерию сокращения времени доступа группы функциональных программ с регулярной последовательностью обработки данных в ФЦЦ; разработка универсального алгоритма нахождения приближенного и точного решения задачи оптимального размещения блоков фиксированной длины в ФЦЦ, временная сложность которого при поиске приближенного решения оценивается величиной порядка /7 , а при поиске точного решения зависит экспоненциально от числа цилиндров т , распределенных ФЦЦ, где
П - число блоков в ФЦЦ; К - число блоков на цилиндре МД; /? и М связаны следующим соотношением: П = т*К разработка алгоритма оптимального размещения блоков переменной длины в ФЦЦ; создание эвристического алгоритма и программы определения оптимального состава блоков в ФПД; разработка и создание программного обеспечения оптимального размещения блоков фиксированной длины в ФЦЦ, функционирующего в пакетном и диалоговом режиме; создание программы-измерителя коэффициента отношения времени доступа, связанного с перемещением механизма доступа МД, к общему времени доступа к блокам в ФПД, определяющей корректность выбора способа размещения блоков в ФЦЦ с точки зрения минимизации времени доступа; разработка рекомендаций по применению алгоритма размещения блоков фиксированной длины в СУБД ЙНЕС, ОКА,IMS, ADA&AS, имеющих ФПД,и схемы модификации, существующего в ОС ЕС метода доступа ЬВАМ »с целью его более эффективного применения в АСУ в задачах с регулярной последовательностью обработки данных; - вывод формулы расчета экономической эффективности, достигає -мой за счет сокращения времени обработки данных в ФПД при помощи операций блокирования и размещения блоков в ФПД.
Работа состоит из введения, пяти глав, заключения, списка литературы из 128 наименований и б-ти приложений*
В первой главе проведена классификация составляющих времени доступа и классификация существующих методов и алгоритмов оптимизации отдельных составляющих времени доступа. При использовании этой классификации выполнен обзор литературы, представлена схема многоуровневого проектирования ИФ АСУ, даны определения информационной, концептуальной, логической и физической моделей, поставлены новые задачи оптимизации отдельных составляющих вре-менти доступа* Найдена методологическая схема конструирования физической модели ЙФ АСУ по критерию минимизации времени доступа к данным группы; функциональных программ и выявлена унифицированная форма представления входной информации для решения задач оптимизации* Определен класс подсистем АСУ для применения схемы конструирования физической модели ИФ АСУ по вышеупомянутому критерию.
Во второй главе представлен метод решения одной из центральных и незавершенных в настоящий момент задач физической модели ИФ АСУ - задачи оптимизации размещения блоков в ФПД по критерию сокращения времени доступа группы функциональных программ, обращающихся к ФЦД.
9 Реализация метода включает следующие шаги: - На основании свойств составляющих времени доступа, сведение поставленной задачи к задаче оптимального размещения блоков информации по цилиндрам Щ по критерию минимизации суммарного пути, проходимого механизмом доступа при решении группы функ циональных программ; ~ нахождение аналитического выражения пути, проходимого механизмом доступа Щ для заданной регулярной последовательности выполнения информационно~зависимых функциональных программ на ЭВМ в однопрограммном режиме и последовательности обращения программ к данным; постановку задачи оптимального размещения блоков по цилиндрам Щ, в терминах целочисленного программирования; решение поставленной задачи методом ветвей и границ с учетом свойств, обеспечивающих сокращение числа перестановок при поиске приближенного и точного решения; разработку стандартной методологической схемы применения программного обеспечения алгоритма размещения блоков фиксированной длины в промышленных СУБД;
В третьей главе изложен алгоритм оптимального размещения блоков фиксированной длины в ФЦЦ, основанный на методе вєтеєй и границ со стратегией ветвления - выбор наименьшей нижней грани.
На основе известной в теории методов дискретной оптимизации теоремы о достаточном условии минимума некоторого функционала, заданного над множеством перестановок [20] , построена на более узком множестве перестановок монотонная оценочная функция функционала, выражающего путь, проходимый механизмом доступа МД, позволяющая производить отсечения в методе ветвей и границ по оценке на всех уровнях дерева ветвлений.
Оценочная функция сконструирована таким образом, что на нижнем уровне дерева ветвлений: ее значение совпадает со значением функционала на перестановке, соответствующей исследуемой ветви дерева, что позволяет исключить из рассмотрения традиционный признак оптимальности метода ветвей и границ [28] , требующий значительное число вычислительных операций. На основе свойства перестановок блоков на цилиндрах МД, в результате которого перестановка двух блоков на одном цилиндре не меняет значения функционала, выражающего путь, проходимый механизмом доступа МД, сформулирована и доказана теорема, определяющая верхнюю оценку временной сложности алгоритма ветвей и границ, зависящую экспоненциально от числа цилиндров, распределенных ФПД,
В заключении третьей главы представлены эвристические алгоритмы решения задачи размещения блоков фиксированной длины в ФЦП,, а также эвристический алгоритм определения оптимального состава блоков ФДД в записях по критерию сокраіцения времени доступа группы функциональных программ АСУ.
В четвертой главе рассматривается алгоритм оптимального размещения блоков переменной длины в ШЩ, Представлены свойства перестановок блоков переменной длины и их отличия от перестановок блоков фиксированной длины. Определены достаточные условия оптимальности функционала, заданного над множеством перестановок блоков переменной длины, На основании достаточных условий оптимальности и идеи фиктивного расширения фиксированного объема цилиндра в случае, когда длина блока больше объема оставшегося свободного пространства на цилиндре, сконструирована монотонная оценочная функция функционала, позволяющая производить отсечения по оценке на всех уровнях дерева ветвлений* На основе свойства перестановок блоков переменной длины,в результате кото- рого оптимальное решение задачи находится с точностью до перестановки блоков в пределах цилиндра, сформулирована и доказана теорема о верхней оценке числа просмотренных кустов дерева ветвлений при поиске точного решения задачи.
В пятой главе приведено обоснование универсальности разработанного алгоритма размещения блоков фиксированной длины в <ЖЩ и выделена область его применения, включающая следующие сферы: реализацию программного способа измерения коэффициента отношения, которое составляет время доступа, связанное с перемещением механизма доступа Щ к общему времени доступа группы функциональных программ, позволяющего определить корректность выбора способа размещения блоков в ФЩ с точки зрения сокращения времени доступа; модификацию существующего в ОС ЕС метода доступа 6DAM с целью более эффективного его применения в АСУ организационного типа для группы программ с регулярной последовательностью обработки блоков; схемы применения в промышленных СУБД: ОКА,IMS, ИНЕС, AUABAS, а также применение в любых других СУБД, имеющих ФГЩ, таких как: БАНК ОС, СЕДАН, СЕТОР и др.
В заключении пятой главы представлена формула для расчета экономической эффективности, достигаемой за счет сокращения времени обработки данных в ФПД с помощью операций блокирования и размещения блоков.
В приложениях представлены: - справка об использовании теоретических и практических резуль татов диссертационной работы в рамках темы; "Разработка техно- рабочего проекта на комплекс задач, обеспечивающих взаимодей ствие АСУ-металл и ОАСУчермет", осуществляемой в соответствии с Постановлением Госкомитета по науке и технике и Госплана СССР от 6.11.81г. №211/425; программа 0.80.02 задание 03.02.А5; доказательства теорем, определяющих верхнюю оценку временной сложности алгоритма оптимального размещения блоков фиксированной длины в ФПД; структуры таблиц, необходимых для метода ветвей и границ, оценки объемной сложности алгоритмов, блок-схема алгоритма размещения блоков переменной длины в ФДЦ и тексты программ.
Работа выполнена на кафедре инженерной кибернетики Московського института стали и сплавов*
Автор выражает благодарность научному консультанту, доценту МИСиС, к.физ.-мат.н. М.А.Зайцеву за ценные советы в области методов дискретной оптимизации.
