автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Графовые модели размещения информации во внешних накопителях вычислительных систем

> «а-

^ Рязанская государственная радиотехническая академия

На правах рукописи

ПАПАНОВ Владимир Анатольевич

ГРА0О8ИЕ МОДЕЛИ РАЗМЕЩЕНИЯ ИНФОРНАЦИИ ВО ВНЕИНИХ НАКОПИТЕЛЯХ ВиМИСЛИТЕЛЫШХ СИСТЕМ

Специальноеть 05.¡5.13 Вычислительны«! папины, комплексы, системи и сети

Автореферат диссертации на соискании ученой степени кандидата технических наук

Рязань 1934

Работа выполнена в Особом конструкторской бвро "Спектр" при Рязанской государственной радиотехнической академии

Научный руководитель

доктор технических наук, профессор, член-корреспондент ЛТП Р© КОРЯЧКО В. П.

Официальные оппоненты

- доктор технических наук, профессор Торхов Б. Л.

- кандидат технических наук, доцент Телков И. Л.

Вадукая организация ¡¡ИИ "Аргон" НПО "Персей", г. Иосква

Зацмта состоится ЧР'Л^Л^Р 1934 г. в '-/О' часов на заседании специализированного Сонета К.003.92.01 Рязанской государственной радиотехнической академии но адресу; 330005,г. Рязань, у*. Гагарина,59/1

С диссертацией мо*но ознакомиться в научно-технической библиотеке акадеыии.

Автореферат разослан " " 1934 г.

Учений секретарь специализированного

Совета __

кандидат технических наук, доцент й. Столяров

ОСШ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы и задачи исследования. Ьыстрмй рост производительности центрального процессора (ЦП) современных ЗВК резко обострил проблему несоответствия производительности ЦП с системой ввода-вывода и внешней памяти. В то время как производительность ЦП непрерывно возрастает, время доступа к запоминающим устройствам на магнитных дисках остается пракгически неизменным. Данное несоответствие приводит к фактической недогрузке ЦП при обработке больших массивов информации в задачах, где дола арифметико-логических операций незначительна по отношении к операциям обмена с внешней наняты!. Это задачи внешней сортировки, векторно-матричные операции над операндами больгих размерностей, операции нац отношениями ь базах данных, операции конвертирования (структурно-семантического преобразования) данных и др. Основная часть потерь машинного времени вызвана холостыми перемещениями магнитных головок для подвода к нуяным записям файлов и ротационными задерлками накопителей.

Одним из методов, позволяющих частично преодолеть указанное несоответствие, является иегод оптимального размещения информации во вкеиней памяти с целью сокрацения непроизводительных затрат времени на перемещение органов считывания-записи для НМД (или носителя для ИМЯ) в процессе выполнения рабочих программ.

Ь настоящее вр.е«« для реиения задач оптимизации разнеч«ния информации нредликено несколько моделей, основывающихся на вероятностном тееретико-мноиественним подходе к анализу.

Для моделирования траекторий обхода файлов з детерминированных моделях известно два подхода:

- непосредственное задании траектории через последовательность обращений к файлам:

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

Икктзцконкое асоделирсвакке алгоркткоз с целя получения после-я.овательностк обращений к файлам (или матрицу взаимосвязей оэ'-.лу^; является весьма трудоемким по той причине, что последовательность обращений зависит от параметров алгоритма. Для построения параметрических коделей требуется больаое количество экспериментов.

Предстгзляег интерес исследовать подходы, связанные со структурным синтезом циклически-повторявцихся фрагментов алгоритма с цельс йналкза згеикосвяззй файлов а процессе их обработки. Для задания такого рода фрагментов к презедэния структурного синтеза предлагается использовать аппарат теории графов.

Настоящая работа посвяцена ксследованиа грефовух кетодгж оптк-

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

Теоретико-графовая интерпретация задач размещения позволяет выделить комбинаторное ядро проблемы размещения информации во внев-ней памяти - !№-полную задачу оптимальной укладки взвешенных неориентированных графов обмена. Многие скрытые теоретико-мновественнт подходом комбинаторные свойства задач размещения удается выявить I графовой интерпретации. К наиболее существенным, в частности, относятся: асимптотическая эффективность методов оптимизации, обусловленная математической природой укладки связанных между собой протя-менпых объектов в одномерную решетку; инвариантность комбинаторно! задачи оптимизации по отношении к критериям среднего и суммарное времени обращения к записям файлов; единая математическая природ оптимизационной задачи для детерминированных и стохастических моде лей; представление размещения связанных протяженных объектов в вид структурной композиции частичных укладок графов; возможность полу чения оценок критерия через оценки для частичных укладок графов структурная композиция графовой модели обмена из совокупности гра фов обмена для отдельных макроопераций алгоритма; возможность, соз дания каталога графовых моделей.

Разработанный метод структурной композиции графовых моделей об мена для класса детерминированных алгоритмов продемонстрирован * примерах алгоритмов аппарата векторно-матричной .алгебры, внешней . сортировки и некоторых элементарных операций над массивами.

С целью обобщения задач размещения информации на случай нес кольких накопителей предложена постановка задачи в условиях ма| ковской модели процесса обращений к файлам с критерием миниму) непроизводительных затрат времени в процессе реализации рабоч! программы. Показано, что в общем случае решение задачи распредел! ния файлов по накопителям не может быть сведено к известкой зада' разрезания графа обмена на фиксированное число кластеров-подграфо: Максимизация величины разреза как критерия распределения файлов накопителям('интунтивно ищущегося вполне обоснованным, ввиду раэр ва связей мекду парами файлов, через которые проходит наиболы» количество путей) не является эффективной . Дело в том, что размещ ние пари файлов, между которыми имеет место интенсивный обмен, разные накопители приводит к появление новых путей в каждом из н копителей, что эквивалентно появлению новых ребер в подграфа обусловленных разрезом.

Теоретически обоснован иной критерий - максимизация числа а тиваций накопителей, при котором межфайловые перемещения магнить головок отсутствуют. Показана связь этого критерия с величиной рс

реза графа обмена. В целом реиение задачи сводится к декомпозиции задачи на две подзадачи: распределение Файлов по накопителям и задач размещения файлов в кэхдом из накопителей.

Исследование графовых моделей проведено в работе дчя двух распространенных стратегий поиска файлов: "блуждающий поиск" и "поиск через начало носителя".

Для решения задачи оптимизации размещения информации на графовых моделях предлонены оптимальные и приближенные алгоритмы. Один из разделов работы посвящен решение частных задлч. иинвцих алгоритмы решения с полиномиальной временной сложностью.

В задачу экспериментальных исследований входила оценка точности приближенных алгоритм"? пчтрч имитационного кодслирсвонкз. оцзк-ка коэффициннгв оптимизации вариационной части критерия, 3?«т фициент указывает верхнюю границу эффективности методов опти! ,зации размещения информации. Действительная эффективность методов оптимизации из-за наличия постоянной составляющей в критерии оказывается ниже. Предложена приближенная оценка эффективности методов оптимизации.

Цель работы. Целью диссертационной работы является повышение производительности систем автоматизации испытаний путем оптимизации законов Функционирования внешних магнитных накопителей. Для дости-аеиия цели разработаны графовые методы анализа и оптимизации размещения информации.

Методика исследований. Для решения поставленных задач проводились теоретические и экспериментальные исследования. Теиретичи кке исследования осуществлялись с привлечением теории графов, комбинаторного анализа, методов теории вероятностей и математической статистики, методин линейной алгебр», теории полиномиальной сьодимостк комбинаторных задач.

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

Научная новизна работы состоит з следующем:

- разработаны графовые методы анализа и ошимизации размено-ния информации во внешней памяти на магнитных дисках или лентах для двух распространенных стратегий поиска файлов: "блумдающий поиск" и "поиск через начало носителя";

- р.чзрабчТ'-'Н метод структурной композиции графовых моделей иб-чена для дгтерчииированннх алгоритмов; на основе этого метода синтезированы графы обмена для операций векторно-матричной алгебры, внешне!': сортирнвки и некоторых элементарных операций над мак.ивами;

- оптимизация размещения информации сведена к М-полной аДаче укладки взвешенных неориентированных графов обмена;

- разработаны точные и приближенные алгоритмы оптимизации графовых моделей, получены полиномиальные алгоритмы ряда частных задач;

- предложено обобщение задачи размещения файлов на случай нескольких накопителей в условиях марковского процесса обращений к Файлам; обоснован -шристический критерий декомпозиции задачи - максимизации числа активаций накопителей, при котором мемфайловые перемещения отсутствуют;

- предложены аналитические оценки эффективности оптимизации размещения информации в зависимости от параметров используемого накопителя. количества и объемов обрабатываемых файлов.

Практическая ценность полученных результатов состоит в следующем:

- разработаны вычислительные алгоритмы оптимизации размещения информации на магнитных дисках или лентах для двух стратегий поиска флйлс.и. позволяющие сократить непроизводительные затраты времени на механической перемещение органов считывания-записи или носителя при совместной обработке больших массивов информации;

- синтезированы графы обмена для операций векторно-ыатричной алгебры, внешней сортировки и некоторых элементарных операций над массивами. Полученные топологические структуры графов обмена могут слукить каталогом для структурного синтеза более сложных макроопераций над Файлами;

- предложен алгоритм распределения файлов по нескольким накопителям в условиях марковского процесса обращения к файлам;

- получена оценка эффективности методов оптимизации размещения информации но магнитном диске для стратегии "блуждающий поиск".

Б работе автор запихает следующие положения:

- теоретико-графовый подход к анализу и оптимизации размещения информации во внешних накопителях на магнитных дисках или лентах. Аналитические графовие модели свертки траектории перемещения органов считывания-записи (или носителя) в виде взвешенных неориентированных графов обмена для двух стратегий поиска файлов: "блуждающий поиск" и "поиск через начало носителя";

- оптимизационную модель размещения информации в интерпретации НР-полной задачи укладки взвешенных неориентированных графов;

- методику оценки параметров графовых моделей для стохастически); и детерминированных моделей;

- полиномиальные алгоритмы решения ряда частных задач в классе полных графов с временной сложностью 0(п1овгп);

- точный алгоритм укладки взвеиенных неориентированных графов по методу ветвей и границ:

- эвристические алгоритмы укладки графов, основанные на идеях градиентного и итерационного поиска решения с временной сложностью

£ я

0(n ) и Oín j соответственно;

- метод структурной КОМПОЗИЦИИ 1>1фОВИХ »»дияк-а И I МИ е'Лфи-ванные с его помощью графы обмена для алгоритмов и-к i щтч-м.! ¡ рнч-ной алгебры, внесшей сортировки и некоторых элементарных оперли,!" над массивами;

- аналитические оценки эффективности методом ишими.мции размещения информации на диске д/,-л стратегии "блуядляций novtnr;

- эвристический критерий декомпозиции мары'искоги прицеп,.) в задаче размещения информации по нескольким накопителям;

- результаты экспериментальных исследований по оценке точности ЭВрИСТИЧеСККХ аЛГОрИТМи» И Диапазона изцнНРНИЯ KIS'fWWTJi оптимизации вариационной части критерия для исследуемых стратегий поиска.

Внедрение работы. Научные результаты, изложенные в диссертации, получены автором в процессе выполнения в ОКБ "Смект;" при РГРТА опытно-конструкторских работ: "Программные средства подготовки рабочих программ" (тема "Циклид-С"), "Разработка системы автоматизированного анализа измерительной информации ЦНА-ЗР" (тема "Цик-лид-Р"), "Разработка системы сбора к обработки внутристанционных измерений ЗР-4бК"(тема "АЗОВ").

Основные полоаения диссертационной работу «спользоь^.ны н процессе разработки автором пакета еторкчиий и6(м0итки рездло гu i и» измерений системы 3P-4ÜM, Систеиа 3ÍM8M ршраОа! ыисн-ъ.» ь UÜ0 "Спектр" при РГРТй, заказчиком чилявтс» "йом.жр" ir. Йчм;н«»>. Практическое исниль^ивоние репулычиив я«< се|н<м|«<жнии ¡•.•.(>г>\« н>.дi -верядается соответствукцими актами о внедрении.

Публикации. По м/П«рИчЛам диссер ыции ииумикенаИ'' / раОщ.

Структура к о б та; к 1).|бц|», /¡иссерт ационнач риьиы u-en-Hi m введения. ий!цей характеристики (мЧотк, ¡ i.tü, ^илш'к'нт! и

приложения, сидерит 200 страниц манинипиим о гексто, ькякчипцего 62 рисунка, 1? таблиц, списка литературы по главам диссертации (к введению и обцей характеристике работы 18 наименований, к гл. i -33, к гл; 2 - 13, к гд. 3 - 8, к г л. 4 - 14 },

КРАТКОЕ СОДЕРВАНИЕ РАБОТЫ

Во введении дается сравнительный анализ методов опткятаиии размещения информации по отношений к другим »«годин, н<ицм«л?Ш1ы» на частичное иди полное устранение иесоитввитвия Щаниводишн-жл.-ти вычислительного ядре современных ВС с системой ввода-виьида и внешней памяти.

В обце.З характеристике работы обосковыааьтся актуальное ib темы и задачи исследования, научная новизна, практическая ценность, формулируются положения, подлежащие защите, приводятся сведения о пуб-

- В -

ликациях и внедрении результатов работ«.

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

Во второй главе рассматривается постановка задачи оптимизации размещения информации в теоретико-графовой интерпретации.

Задано мноиество файлов Я%пУ. каждый из которых характеризуется физической длиной С/п. Траекторию обхода обра-бзгывагчых Файлов в процессе решения некоторой задачи можно представить как последовательность фаз , причем в как-дой из фаз производится однократное обращение к файлу для записи или считывания порции данных, т. е. задано отображение совокупности Ф на К такое, что каждой фазе Д соответствует некоторый Файл Г н ^ — ^ , I = ¿т/,п.

Графовой моделью обмена называется взвешенный неориентированный граф К.5), причем пара является ребром графа & . если между возможен путь, вершинам и ребрам графа поставлены в соответствие веса СI и Су соответственно. Веса вершин имеют интерпретации физических длин обрабатываемых файлов.

Веса ребер в зависимости от критерия оптимальности размещения файлов ь накопителе могут иметь'следующую интерпретацию: •

а> вероятность пути между парой файлов и

б) количество путей (или его математическое ожидание) между

парой

Сказанным весовым характеристикам однозначно соответствуют два критерия оптимальности:

- минимум среднего времени на холостое перемещение органов считывания-записи при обращении к файлу из множества £ ;

- минимум суммарного времени на холостые перемещения органов счигывапия-записи в процессе совместной обработки множества файлов.

Графовые модели рассматриваются для двух стратегий поиска фай-' лов: "близдавщий поиск", когда перемещение от одного файла к другому осуществляется по кратчайшему пути, и "поиск через начало носителя", когда перемещение от одного файла к другому осуществляется через начало носителя. Первая стратегия моделируется в общем случае графами с произвольной структурой, а вторая графами типа "звезда".

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

Формальная постановка задачи оптимизации размещения файлов на одном накопителе следующая.

Стратегия "блуидавций поиск". Назовем укладкой графа & последовательность такую, что для всякого ребра ииеет место £<£. . При ¿С^С , где С - емкость накопи-

- ? -

Таблица 1. Параметры графовых коделей

Стратегия поиска Файлов Модель обращений к файлам Стр-ра графа обмена Критерий опт ими -зации Веса ребер графа обмена

Стохастич, модель при независим, обращениях Полный граф Среднее 1 ремя ибращения С!}-2Р!Р}, )<}-! ,п. где Р! - вероятность обращения к I- му файлу. Ы'.п

блундаа- , щий поиск Стохастич. мидель при зависимых обращениях Полный гра$ Среднее время обращения си = Р1Ри+Р]Р1), 1<] = Г7г1. где Р1-вероятнпсть обращения к 1- му файлу. Р1^-вероятность обращения к з - ¡»у файлу после 1- го

Суммарное время обращения С13 =М!Р13+И]Р]!, I<] = ГГп. где Р1]-вероятность обращения к ]- му файлу после 1- го, Ш-мат. ожидание кол.-ва обращений к 1- му файлу, определяемое решением 1-Рт ГРо, где Ро-вектор начального распределения вероятностей

Детерминированная модель Структур,ч оиред. алгоритмом Суммарное время обращения С1] определяется числом пар С Н1Ш .Р1) а последовательности фаз обращений к файлам Ф, к] = 1 ,п

поиск через начало „ носителя' Стохастич. модель при независим. обращениях Среднее время обращения Со! =Р1. 1 - Сп, где Р1-вероятность обращения к 1- му файлу

Стохастич. модель при зависимых обращениях Граф типа "звезда" Суммарное время обращения Со)=ЯШ, ыТп. где N1 -мат. ояидание количества обращений к 1- му файлу

Среднее время обращения Со! =Н!/Ск. .+N0), где Щ-мат. ожидание количества обращений к 1- му Файлу

Детерминированная модель Суммарное время обращения Со1-удвоенное количество встречающихся в Ф файлов 1 = !Тп

теля, любая укладка графа G определяет допустимое размещение файлов.

С каждой укладкой свякем Функционал

I(l(G))~2l т = Г I 27 % п (1)

где <!f/i^i¿ ~ величина холостых перемещений для пары файлов, она равна 0. если файлы являются смежными, т. е. /, и равна

(¿W/ fСчь-э* если ыевди и расположены другие

Для достихения максимальной производительности вычислительной системы при совместной обработке множества файлов необходимо найти такую уклодку LopT(G), для которой функционал (1) достигает своего минимума.

Для вкиеизлояенных критериев оптимизации критерий (1) справедлив для случая линейной аппроксимации характеристики времени траверса голосок считывания-записи (ГСЗ) от числа пересекаемых цилиндров. Линейная аппроксимация указанной зависимости является приемлемой для большинства накопителей с позиционерами соленоидного типа и является точной для позиционеров с маговым двигателем.

Стратегия "поиск через начало носителя". Назовем укладкой графа 1 типа "зв£эда" последовательность

кую. что для всякого ребралюбой из файлов A/¿ расположен правее файла

Оптимизируемый функционал для этой стратегии имеет вид: л

Ш Ш) = — <2)

Метод структурной композиции графовых моделей

Предлагаемый метод позволяет аналитически синтезировать детерминированные графовые модели обмена. Идея его основана На двух свойствах графов обмена для детерминированных алгоритмов.

Свойство 2.1 (аддитивности). Вес ребра(R¿} Rj) графа обмена равен количеству пар в последовательности фаз Ф, для..ко-

торых . или

Свойство 2.2 (направленности). В графе обмена Í? можно указать две вершины Ü¿ , . для которых f( ¿¿ •• Граф обмена

йЧЙ,^', ) назовем направленным.

Суть метода. Разобьем последовательность Ф на ряд подпоследовательностей Фр(р = <,к). каждая из которых соответствует некоторой макрооперации над участвующими в ней файлами,и соединим указанные последовательности посредством двухэлементныхФ^Н , Пост-

роим для каждой подпоследовательности Фр направленный граф обмена

весами ребер Су . а затем для двухэлементных подпоследовательностей ^Л/ графы-ребра ^ ^ / с единичными снгими.

Результирующий граф обмена 5 для всей последовательности 'Г ьм полняемых Фаз моио' рассматривать как структурную композицию графов

йр, $¿,¡.+4, Р = •

С помощью указанного метода получены графы обмена для операнд,! векторно-матричной алгебры, :иевней сортировки и некоторых элем?н тарных операций над массивами (см. таблицу 2).

В третьей главе рассматриваются алгоритма оптимизации грачиных моделей.

Для стратегии "поиск через начало носителя" привидится точное -решение с полиномиальной временной сложностью полученное

на основе следующей теоремы.

Теорема 3.1. Пусть 1.(2.некоторая произвольная укладк- графа типа "звезда". а Ц укладка, полученная из Ь посредством перестановки^' - й ий вершин. . Тогда, если существует такая Функция V, что из

следует и уклад-

ка ¿.'(С?)такова, что в ней ¿/-вершина предшествует 4?- й, если УСчМ^^г,^). то является оптимальной. Функцией ¥ для

взвешенного графа/? является следующая:

где О£ и 4£>/ номера переставляемых вершин.

Условие теоремы

эквивалентно нераненгтну Сои^/Со^ % . Т. о. упорядочение Файлов в порчдкг

убывания отношения С(у/Су минимизирует целевую функцию.

Для стратегии "блуждающий поиск" исследованы две полиномиально-разрешимые задачи в классе полных графов с 0(п1о^п).

') Для Б полного с весами вершин > О и весами ребер ¿у-"/ реиение устанавливается следующей теоремой.

- Теорема 3.2. Если 5с$ перестановка весов вершин, соответствующая убивающей последовательности Cif - ¿-¿п . перестановка чисел ¿у ) в возрастающей последовательное ги ¿¿^¿¡гЪ... £ 'гДе - число ребер, проходящих над вершиной в укладке полного графа. Тогда суперпозиция определяет оптимальную в смысле критерия (1) перестановку файлов

Следствие. Оптимальной перестановке соответствует рлм.^пчгие весов вврвкн в неубиьасяей последпвзт'гльности по слирдли .1ди.и»-;'мгг целочисленной решетки, т. е. если £ ¿¿г ^ ■• ^ ^¿/х. , то Lap¿ (Ог) .., ^¡г>--> ) или симкетричноя ей

Задача соответствует стохастической модели с независимыми равновероятными обращениями к Файлам.

Таблица 2. Синтезированные графовые модели обмена

N Операция Смысловая интерпретация' Граф обмена

1 Копирование массива Массив, размещенный В go и разделенный на t порций, переписывается в ¿7 4 0--—о

2 Копирование массива с расслоение* Массив, размеренный в Ко и Разделенный на С порций, переписывается в п Файлов, причем в Kl файл переписывается ггц послед, порций к, ^^ : *

3 Слияние массивов п упорядоченных массива, разме- кенные в .....Rf, и разделенные на ; tn порций,сливаются в один упор, массив ко а • 7 £/> Ч

4 Конкатенация массивов п массивов ...^последовательно сочленяются в один массив Ra ■

5 Сравнение массивов п одинаковых по длине массивов и разделенных на £ порций сравниваются между собой Ч-< е/ъ-г * \ £ У

6 Декартово произведение порций файлов Над совокупностью файлов К«-, разделенных на Si порций каа-дый, выполняется операция. Результат операции замечается в ОЗУ ht % R{ </ » \ ¿А 5>/ \ - T^V^ti « Р ix-ï', „ \ п/:(геп.г{)

Продлозение таблицы 2

Слоаение. вычитание, кронекеров-ское произведение матриц и векторов

Над операндами

выполняются поэлементные операции, каядыя разделен на порций обмена

Умножение матрицы на вектор

Матрица |М|1п»п. умножается на вектор В длиной и элементсв.1 Размер порции обмена Р . ' целое. В зависимости от упорядоченности элементов возможно два случая графовых моделей обмена

Плго^-пм с однократные обме..им А н в

кй ь , /

¿5—е-о——'----о

Алгоритм с однократным обменом Й и п-кратным обменом В д

а) п кратно р

Ж

Умножение матриц

Матрица ЦА Нпхт умножается на матрицу Н В Нт»£-Результатом является НС11и*£. Размер порции р

10

Внешняя сортировка массива. транспонирование

матриц

Сортировка массива по методу двухпутево!с балансного слияния с четырьмя рабочими Файлами. р0 - исходный, Й>- резильтир.

рабочие файлы. Число порций -1 Число стадий Н = 1 + [ 1 О Й2 ) ]

г йз ш^-гн

Ра) Н-четнп , , 0

б) Н-нечетно

2) Для 6 полного с весами вершин 4 и весами ребер Су = P¿ (где - некоторая дополнительная весовая

характеристика вершины) критерий оптимизации примет вид

ки&))¿и —(4)

где £.-£-1 .

Решение находится на основе леммы о комплементарных последовательностях.

Лемма 3.1. Линейная перестановочная форма вида

Л

гдС£п)н(<*/<,последовательности элементов множеств,

достигает минимума, если выполняются неравенства:

. __________________у

Для (4) комплементарными последовательностями являются следующие:

Р;аРц»...>Рс„.2* ЯД * & А »• ■ ■ * Рч Р^п.

Индукция по П- дает следующее условие оптимальности. Если Р^Рг^--^ Рп, , то оптимальной укладке соответствует (п>- *3, "-У ) или симметричная ей.

Если р£ ¿-^п интерпретировать как вероятности независимых обращений к Файлам, то задача соответствует стохастической модели с независимыми обращениями~к файлам одинаковой длины.

Для общего случая задачи предлокены следующие алгоритмы. В основе градиентного эвристического алгоритма левит идея поэлементного построения.укладки с минимизацией полного веса вершины, включаемой в качестве очередной в частично-построенную укладку. Под полным весом вериины понимается произведение веса вервины на суммарный вес ребер, проходящих над ней.

Выбор вершины Ч, для включения в ¿(в) на -к - м шаге осуществляется с помощью функции-градиента: ,

ъ = егай (5)

Р„ = тШ Рс. (В)

В (5) Иб- множество вераин, не включенных на/?- м ваге вериин, Р^ - полный вес вериины

Начальна:. вершинаЗна шаге -к =1 выбирается с помощью условия Сс^м&хС^ (?)

Слоиность алгоритма 0(пг),

Итерационный эвристический алгоритм предполагает улучшение значения критерия (1) на какдом шаге алгоритма некоторой процеду-

рой, порождающей новое решение. В качестве такой процедуры используется транспозиция двух вершин, посредством которой достигается наибольвее уменьмение критерия. Алгоритм заканчивается ч том случае, если не найдется ни одной пары вершин с требуемым сиойьтвон. Экспериментальна полученная оценка сложности алгоритма - (Кп3).

Оптимальный алгоритм, реализованный по методу ветвей и границ, структурируется в виде семерки правил А=(1.,В,е,Х,Г,0,Н).

1) Представление состояния (I.) укладке И&) ветви дерева в виде композиции 2-х частичных укладок . / ,, . . \

Ц ¿2 ¿и. ¿4+1 ¿У ¿У«4/ Ал-/ ¿л.

Укладке соответствует мн-во вершин Ня {,4, включенных в исследуемую ветчь дерева с величиной критерия Хн .

2) Правило ветвления (В) соответствует поиску по глубине. В корневом узле дерева (ярус и=0) ин-во всех укладок ¿"п. разбивается на IV подмножеств. На следующем ярусе (11=1) каядое из и. подмножеств разбивается на п- •/ подмножеств и т. д. Допустимому реиенив в таком дереье соответствует ветвь .,., ¿п. ) • гДе - ьервина

на II— и ярусе дерева, с/л/^п

3) Правило выбора состояний (6Г из множества активных осуществляется с помощью функции (5) йгас1сЛ^), где Лг/ - мн-во активных направлений ветвления.

4) Функция характеристики состояния (X) -.

5) Граничная функция (Р): ,

1н ' 1н +1н, . (8)

где (9)

Кг) ^-^ Ш\2)

Ы 1ц*г 1п Ая-/

Укладке 1.орКг) соответствует согласно теореме 3.1 упорядочение вер-зин в порядке > ¿ШИ. > ч

Ъ^Г^с^ ^ ■ -

Оценку где£"С\2Г- произвольный граф, почию получить

из первой полиномиально-разрешимой задачи следующим образом. Преобразуем взвешенный граф &-((},Б) в мультиграф £ путем росщепленим целочисленных весов ребер Су .

Тогда оценку J^(LC(r)) mosho представить в виде С т л

L(L(G))=- "и п-<>тг

Qy если n-fzira (10)

где Д^ - оценка полного веса дуги мультиребра, который определяет ся суммарный весом вершин, расположенных в укладке под этой дугой Точные J)i£ известны из реиения для полного графа. Полные вес дуг на уровнях укладки можно записать в виде вектора (в порядк убивания уровней) (

5= Пп1. ПИИ

Уровень дуги определяется значением У"»^ глг^п-4

Упорядочим элементы вектора Х> в следующей последовательности заменой двумерных индексов одномерными в интервале от п до nCn-fl/Z

Теореьа 3.3. Лля укладки любого взвешенного на вершинах граф G с числом вериин п и ребер в первые к=ш-п+1 элементов последова тельности (12) являются нижними оценками-Ul^^n,™, п$т 6) Правило (D) отсечения состояний. Если

1н>1о, где. 1о - тек

наилучиее значение критерия, то ветвление прекращается и осуцествля ется возврат на предыдущий ярус дерева.

„ 7) Правило (N) выбора текущего наилучиего реиения. Если для L(> 1Й№))<Ь . где то Jo=IH(L'(G)) .

Алгоритм имеет экспоненциальную сложность с нижней границей!2(п*).

В главе 3 рассмотрено обобщение задачи размещения на случай нескольких накопителей в условиях марковского процесса обращения к данным и стратегии "блундающий поиск" с критерием минимума ' суммарного времени обращений к файлам в процессе реализации алгоритма.

Для мн-ва файлов lRI=n известны матрица переходных вероятностей ¡I Piy'ilnH и вектор начального распределения вероятностей fo^CPo-t» Рог»---» Ri/i+^З'' причем <2+-/-е состояние является единственным поглощающим состоянием. Требуется найти распределение мн-ва файлов и 1 накопителям (m < n)SGR)-^...,^/*)), где £ , причем ¿¿j> Для некоторого критерия 1($(R))-гта* (обосновывается ниже) при ограничении 21 Lk , где Lfe свободная емкость памяти Д - го накопителя

На основании анализа модели активности накопителей в процессе реализаций алгоритма доказывается следующая тг трема.

Теорема 3.4. Математическое ожидание числа активаций (переключений) накопителей Q определяется величиной разреза графа обмена

алгорит а на кластеры-подграфы <Х^>, <Х^>..... <ХЛ1>, т. е.

т-4 /г?

d-L 2. £I Z £ к.

V^eXi щеХу M^lh VP^K, V&e'y, №

где. А^к - мат. ояидание количества обращений к му Файлу за время реализации алгоритма, С#£ - вес реора в графе обмена, определяемого соотношением С$£ - Р&£ + }

Числе активаций накопителей 0 состоит из двух сос.авляюцих , где во соответствует случаю, когда при переходе от файла к фсйлу С , $ .¿¿у ) головки активизиру-

емого накопителя расположены над файлом Ц(> , а величина <?/ соответствует случаю, когда при переходе от к требуется ш»файловое перемещение головок от некоторого файла ^^ в Файл .

Вводится критерий 1(5(1Ш, соответствующей максимизации во , т. е. максимизации числа активаций накопителей, при котором межфай-лозне перемещения отсутствуют, т. е.

т. ь

/^(Ю) РЦ - Ри ) (141

где ГЦ - вероятность перехода вложенной марковской моде-

ли -к - го накопителя, Рц- вероятность перехода в исходной марко-аской модели. £

Вероятности Рц находятся для каждого накопителя путем построения зловенных марковских процессов в каждом из накопителей. Это осуществляется с помощью двух известных преобразований - исключение узлов и исключение петель. Временная сложность алгоритма построения вложенного марковского процесса 0(п2').

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

На основе вложенных марковских процессов строятся графовьс модели обмена для каждого из накопителей. Оптимизация последних п[о-изводится методами размещения для одного накопителя.

В четвертой главе приводятся хетодика и результаты сравнитесь-' него иодйг,и|>нвлнкя алгоритмов для исследуеикх стратегий поиска Ф-зй-/:ез„ оценки точности эвристических алгоритмов, оценка коэффициента оптимизации вариационной части критерия, оценка эффективности методов оптимизации размещения информации, практическое применение результатов исследований.

Для имитационного моделирования алгоритмов был разработан пакет программ, написанный на язык-? Фортрлн-Ш, функционирующий под управление« операционной системы ЯТ-И на ЭВМ СМ-1420.

Моделирование осуществлялось на множестве имитируемых псеьдо-елучаяных графоз £ = < К. Б ). =-п. |5| различной размерности, близких к полним (п=п(п-1)/4,,..,пСп-1 )/2). Формирование леегдзелучай-инх графов осуществлялось с помощью датчика с равномерным распреде-

лением путем удаления соответствующего количества ребер из полного графа, причем на каждой стадии удаления граф должен оставаться связник. Затем вершины и ребра взвешивались весами, генерируемыми датчиком с равномерным распределением.

Коэффициент оптимизации вариационной части критерия, характеризующий асимптотическую эффективность оптимизации размещения информации на одном накопителе, оценивался отношением в6=1ср /1о, гД( Icp - средняя величина критерия (1) или (2), полученная путем усред нения по 100 случайным размещениям файлов заданного графа обмена 1о - оптимальная величина критерия.

Точность эвристических алгоритмов оценивалась максимальной и средней относительнойпогрешностями:

Scp^Tcdp-Io')/!/] (16>

TJ TJ

где Jnp , Ц ~ приближенное и оптимальное значения критерия для j - й задачи, К - количество ревенных задач.

Для оценки временных характеристик алгоритмов принято минимальное, среднее и максимальное время решения по множеству задач фиксированной размерности.

Результаты экспериментов для стратегии "поиск через начало носителя" показали, что коэффициент сС колеблется в диапазоне от 1,44 до 2.18. Время решения точным алгоритмом при п=10...Ю0 не превышает 2 с, а при п-1000 нз более 3 мин.

Для стратегии "блуждающий поиск" коэффициент оптимизации вариационной части критерия сб колеблется в диапазоне от 3,9 до 6,3. Применение оптимального алгоритма для этой стратегии ограничено раз мерностью n =11. при этом максимальное время решения не более 10 мин При п=12, когда время реализации превысило 30 минут, эксперимент был остановлен.

Градиентный эвристический алгоритм имеет высокое быстродействи' (От*)), гак при n=11 время поиска не более 4 с, но низкую точность получаемых решений. По данным экспериментов Вер =40... 150 t. Его целесообразно использовать при большой размерности, когда приме нение других алгоритмов невозможно.

Итерационный эвристический алгоритм имеет среднее быстродейс твие (по данным экспериментов 0(п3)), но высокую точность поиска ( Вер. <2 %).11ри n= 11 преня реализации не более 16 с.

оценки эффективности методов оптимизации размещения инфор нации для стратегии "блуждающий поиск" использовалось отноиекие

X -Тер /Topt, (1'

где Topt - непроизводительные затраты времени в работе накопите"''

при.оптимальном размещении Файлов, Тер - среднее время непроизводительных затрат, полученное по всем возможным размещениям файлов.

Для оценки средней зффективности оптимизации (по ипоаеству графовых моделей) получено следующее аналитическое выражение

4 + Я * О/С Л

У = —г Яъ---=——-- • па)

В ( 10) приняты следующие обозначения: - коэффициенты линей-

ной аппроксимации характеристики времени I,,аверса голонпк диска от числа пересекаемых цилиндров £(о/)-00>-0,Ж\ С - средняя фи: нчесг.ая длина файлов (в цилиндрах диска); То/2 - среднее время ротационной задержки: оС - коэффициент 'оптимизации вариационной чло•и критерия.

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

Средняя эффективность оптимизации для стратегии "блуждающий поиск" и об =5 проанализирована на примере трех типов НМД: СМ5400 (2 . Мбайта), "Эл.-ка МС5406" С1 и Мбайт) и "Эл.-ка МС5405" (20 Мбайт). Для первого накопителя оптимальное разыев|ение в его объеме более 5 файлов приводит к сокращению непроизводительных затрат времени при работе накопителя в 1,2-1,3 раза,или на 20—2Г? процентов. Для второго типа НМД - в 1,4-1,95 раэа.;или'на 30-50 процентов. Дна третьего типа НМД - 1,45-2,35 раза,или на 30-60 процентов.

Практическая интерпретация разработанных графовых моделей разнесения информации осуществлялась в рамках разрабатываемой в ОКБ "Спектр" при РГРТЙ системы сбора и обработки внутристанционных измерений ЗР-48М при реализации пакета программ вторичной обработки измерительной информации (ИИ).

Для сокращения времени вторичной обработки ИИ возникает необходимость их предварительной обработки и упорядочения. Эти данные, появившись в результате регистрации в процессе испытания объекта, р • общем случае не упорядочены по нзобходимому признаку, а следуют в порядке, определяемом моментами съема информации с объекта. Операции, обработки больших массивов информации могут эффективно выполняться над упорядоченными по необходимому признаку данными.

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

Задачи предварительной обработки ИИ с целью распаковки, упорядочения. структурирования, форматирования, масштабирования данных получили обобщенное название конвертирования данных.

Файл с ИИ представляет собой покадровую выборку параметров па

интервале проведения сеанса эксперимента.

Программа КОНВЕРТОР ФАЙЛОВ включает следующие операции: сортировка описаний, затребованных для конвертирования параметров пс признаку местоположения в кадре с ИИ (Асорт.)

(Описание параметра включает : расположение в кадре, размещение разрядов в слове измерений, размещение разрядов в машинных словах, масштабный коэффициент,тип и формат параметра, а также единицы измерения. Описания размещены в реляционной базе данных.);

структурирование матрицы наблюдения, реализующая операции селекции и проекции.затребованных для конвертирования параметров на заданном интервале наблюдения (Астр.);

компоновка разрядов измерений в машинные слова (Акомп.); преобразование типов и Форматов данных измерений (Аформ.); масштабирование измерений параметров (Амасм.); транспонирование матрицы наблюдения (Атран.), В качестве алгоритма упорядочивания (внешней сортировки) использован алгоритм сбалансированного двухпутевого слияния с четырьмя рабочими файлами, основанный на идее быстрого алгоритма пирамидальной сортировки по Веллу. Операция транспонирования матрицы реализована через операцию внешней сортировки.

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

В заключении приведены основные выводы диссертационной работы.

В приложение вынесена классификация факторов производительности жестких дисков по П. Нортону.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТН

1. В диссертации предложены и исследова. ы графовые методы анализа и оптимизации размещения информации во внешних накопителях вычислительных систем. Основное внимание уделено оптимизации размещения .нформации в накопителях на магнитных дисках.

2. В рамках теоретико-графового подхода исследованы метод построения графов пбмена для стохастических процессов с зависимым и независимыми обращениями к данным, а такае для детерминировании

процессов. Предложен метод структурной композиции графовых моделей обмена для детерминированных алгоритмов совместной обработки множества файлов, позволявший аналитически синтезировать графи обмена, не прибегая к трудоемкому процессу имитационного моделирования.

3. На основе иетода структурной композиции получены графовые модели обмена для линейно-алгебраических операций, операций внешней сортировки и некоторых элементарных операций над массивами.

4. В рамках графового подхода исследованы две распространенные стратегии поиска информации в накопителях "блуждающий поиск" и "поиск через начало носителя".

5. Для указанных стратегий поиска предложены алгоритмы оптимизации графовых ноделеа. 3 их числе;

з)оптикзшшй алгоритм для зтороЯ стратегии, имеющий полиномиальную оценку временной сложности 0(п1одгп);

б)два приближенных алгоритма для первой стратегии с приемлемой для практики временной сложностью 0(п2) и 0(п3) соответственно. Первый из них (градиентный) имеет низкую точность поиска (относит, ошибка 40-150 У.), что позволя-т его использовать лииь для задач больвой размерности (30..,1000 файлов), для которых другие алгоритмы поиска по временным характеристикам неприменимы. Второй алгоритм (итерационный) характеризует высокая точность поиска реиения (относит. ошибка не превышает 2 'Л. Этот алгоритм целесообразно использовать при размерностях п<30;

в) оптимальный алгоритм для первой стратегии, имеющий спспо-ненциальную временную сложность с нижней границей О. (и*). Алгоритм реализован по методу ветвей и границ. Он эффективен при размерностях п< 12;

г) в классе моделей, представленных полными графами, исследованы две частные задачи, имеющие полиномиальные алгоритмы решения со сложностью 0(п1од^п).

6. Имитационное моделирование алгоритмов осуществлялось с помощью разработанного пакета прикладных программ, реализованного на языке Фортран-4 в среде операционной системы НТ—11 на ЭВМ СМ-1420.

?. Результаты имитационного моделирования показали,, что козф-Фициент оптимизации вариационной части критерия (отнопение средней величины критерия к оптимальной) для стратегии "блуждающий поиск" колеблется в диапазоне от 3.9 до 6.5, а для стратегии'"'поиск-через начало носителя" от 1,44 до 2,2.

8. На основе оценки коэффициента оптимизации вариационной части критерия получено аналитическое выражение для приближенной сценки эффективности оптимизации для стратегии "блуждающий поиск".

3. Предлоаено обобщение задачи размещения информации на случай нескольких накопителей. Данное обобщение рассмотрено для марковспй

модели процесса обращений к файлам и стратегии "блуждающий поиск". 6 качестве критерия использовался минимум непроизводительных затрат времени при реализации алгоритма. Предложен эвристический критерий распределения файлов по накопителям - максимизация числа активаций накопителей, при котором мевфайловые перемещения магнитных головок отсутствует.

10. Эффективность методов оптимизации зависит от характеристик используемых накопителей. Для исследованных в работе накопителей за счет оптимизации достигается 20 - ВО-процентное сокращение непроизводительных затрат времени на перемещение магнитных головок или в 1,2 - 2,35 раза для стратегии "блуждающий поиск".

Основные материалы диссертации опубликованы в следующих работах:

1. Кабаноз В. й. Построение укладок взвеиенных неориентированных графов в задаче оптимального размещения файлов в накопителе на магнитных дисках. Деп. во Всесоюзном НИИ информации и экономики "Информприбор", N5052 (Опубликована в библиогр„ указателе ВИНИТИ "ДНР\. 1992, N5. С.56).

2. Кабанов В. Й. Комплекс программ оценки производительности к планирования распределения ресурсов многомашинной вычислительной системы при конвейерной обработке телеметрической информации/В кн. "Организационно-экономические проблемы проектирования вычислительных систем", М.. НТО РЭС им. Попова, 198?.

3. Кабанов В. й. , Олеринский Е. В. Устройство для распределения заявок по процессорам, йвторское свидетельство, N1121671 606 Р 9/46, 1982.

4. Кабанов В. й. Определение динамических характеристик последовательных программ. В эскизном проекте "Программные средства подготовки рабочих программ (ПСПРП)", АИ.00224-01 81 01. Рязань: ОКБ "Спектр" при РР1И, 1987.

. 5. Кабанов В. А. Повышение эффективности алгоритма решения задачи о наименьшем покрытии при введении обобщенного ограничения, ".п. во Всесоюзном НИИ информации и экономики "Информприбор", И4344.

Опубликована в библ. указателе ВИНИТИ "ДНР",1989, N1.)

6. Кабанов В, А. Формализованное задание на компоновку разрядов измерений в машинные слова. В техническом проекте "Программное обеспечение системы ЦНЙ-ЗР." Рязань: ОКБ "Спектр" при РРТИ, 1983.

7. Казанов В. й. Система ЗР-48К. Пакет программ вторичной обработки, ПИ1.400.023 36 01. Научно-технический отчет. Рязань: ОКБ "Спектр" при РГРТП, 1993.