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

г в' ^

МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ

ДОНЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

ТРУБ Илья Иосифович

МЕТОДУ ПРИБЛИЖЕННОГО АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ И ЛСВШГОШ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ВЫЧИОШтНЫХ СИСТЕМ с ПАРАЛЛЕЛЬНОЙ ОБРАБОТКОЙ ДАННЫХ ( СТОХАСТИЧЕСКИЕ И ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ )

Специальность 05.13.13' Рячислительнне маштак, комплексы, систем*; и с«ти

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

Доноцк - 1994

^&шишдолнена на кафедре прикладной математики и информатики Донецкого государственного техничаскогсГ^ниверсцтота

Диссертацией является рукопись

Научный руководитель: доктор технических наук, профессор ФЕЛЬДМАН Л.П.

Официальные оппоненты: доктор технических наук, профессор

СКОБЦОВ Ю.А.

кандидат технических наук, доцент БАРКАЛОВ A.A.

Ведущая организация: Институт проблем моделировании о анер готике АЛ Украины (г. Киев)

fulb

Защита состоцтся"27" октября 1994 года в 1 ~ часов на заседании специализированного Совета К 06.04.01 при Донецком государственном техническом университете по адресу: 340UOG, Донецк, ул. Артема, 58, ауд. 1.201.

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

Автореферат разослан "27" сентября 1994 г.

Ваш отзыв в одном экземпляре, заверенный печатью, просим ш слать по указанному адресу: 340000, Донецк, ул. Артема. М, Ученому секретарю ДонГТУ.

Ученый секретарь специализированного Совета, кандидат технических наук

Мокрый РЛ)

ОБЩАЯ ХАРМТЕРИСТИКА РАБОТЫ Актуальность техы. Задачи, рассматриваемые в работе, относятся к общей проблеме повышения эффективности функциони-эования вычислительных систем, более полного использования заложенных в них потенциальных возможностей. Научное направление, к которому относятся эти задачи, получило название 'Оценка качества и оптимизация вычислительных систем". Исследуемые в нем1проблемы весьма разнообразны и направлены на ювышение производительности ВС. Одни из них решаются на этапе проектирования систем,' другие возникают в процессе экс-хпуатации, когда выясняется, что какие-либо'параметры не ивляются удовлетворительными и их следует улучшить. Наиболее значимым из этих параметров является производительность. Су-цествует множество путей повышения производительности систем. { ним относится в первую очередь совершенствование технологической базы, на которой строятся ЭВМ и системы. Однако, эпыт нескольких десятилетий применения средств вычислите-вьной техники привел к выводу, что увеличение производитель-юсти за счет развития технологической базы происходит в ср-5днем в 5 раз за 10 лет, что не является удовлетворительным ря гораздо более быстро растущих потребностей науки, техники, промышленности, экономики. В связи с этим в настоящее зремя широко известные методы повышения эффективного быстродействия ВС опираются на распараллеливание вычислений путем зовмещения во времени выполнения различных операций, новые архитектурные решения при проектировании ВС, увеличение уро-зней иерархии и расслоения памяти, совмещение ввода - вывода : работой центрального процессора и др. Однако, ограничения, 1рисущие конкретным реализациям ВС, наличие конфликтных ■ситуаций, несоответствие алгоритмов и программ архитектуре мо-

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

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

Основными задачами исследования являются:

- анализ известных подходов и методов оценки производит льности ВС, оценка их трудоемкости;

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

- разработка методов исследования аМхэктивности рабе параллельной машинной памяти при различных режимах адреса;

- исследование процессов в ВС с нетрадиционной архитек' рей, анализ влияния различных параметров этих систем и д цишшн обслуживания на производительность;

- создание пакета прикладных программ, реализующего модели и метода, предложенные в работе;

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

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

Теоретическая и практическая ценность исследовсогия, научная новизна. Научное значение работы заключается в описании и исследовании новых типов систем массового обслуживания, моделирующих работу параллельных вычислительных систем, установлении, теоретическом и численном обосновании законов, которыми описывается поведение таких систем при различных исходных параметрах'.

Положения:

1.Необходимым и достаточным условием существования стационарного режима в вычислительной системе, управляемой потоком операндов, является выполнение соотношения <1, где Р - средняя местность команд программы (число входных операндов) , q - средняя ширина параллелизма алгоритма.

2. В вычислительной системе, управляемой потоком запросов,

действующей в режиме активизации вычислительной процедуры любым гтотрвОителемГопт[шальной- дисци1шшюй_Еыбора _запросов из очереди является выбор запроса с максимальной длиной остаточного пути.

Результаты:

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

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

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

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

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

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

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

Реализация результатов работы. Результаты, полученные в диссертационной работе были использованы в Институте шахтных информационно - управляющих систем Госуглепрома Украины при разработке систем распределенной обработки информации в АСУ ТП шахта; в Научно-исследовательском институте 'горной геома-ханики им М.М.Федорова при проектировании параллельного спектрального анализатора, работающего в режиме реального времени, в Институте прикладной математики и механики НАН Украины при выполнении ряда НИР. Основные положения' диссертации и разработанное программное обеспечение внедрены в учебный процесс на кафедре прикладной математики и информатики в Донецком Государственном Техническом Университете, в филиале кафедры "Прикладная математика и теория систем управления" Донецкого Государственного Университета при ИГОМ НАН Украины

Апробация. Основные результаты работы докладывались и оОсу-адались на научно-исследовательском семинаре по дискретной математике (Южный центр АН Украины, Одесса, 1993), I Международной конференции "Компьютерные программы учебного назначения" (Мариуполь, 1993), научных, семинарах в. ИПММ. НАН Украины (Донецк, 1993)', .«афедры --а дгвСрн . и-теории вероятностей Донецкого государственного-университета (1992-93 гг.), кафедры , прикладной математики и информатики Донецкого государственного технического .университета (1992-93 гг.).

е

Публикации. Содержание диссертации отражено в 8 опублико-

апруит;ура ц объел работ. Структура и объем работы определяются решаемыми в ней задачами и включают введение, четыре главы, заключение,'список использованной литературы, 7 приложений. Основной материал изложен на 184 страницах, содержит 62 рисунка, 16 таблиц, 14В наименований в списке использованной литературы.

Изложенные в работе результаты получены диссертантом самостоятельно.

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

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

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

ванных работах.

СОДЕРЖАНИЕ РАБОТЫ

Подобные ВС проектировались и использовались в 50-70 годы на базе больших ЭВМ, в настоящее время такой базой являются сети персональных компьютеров и рабочих станций.

Эффективность функционирования ВС во многом определяется выбором дисциплины обслуживания. Начиная с первой работы А. Шерра в этом направлении, большое количество результатов получено в предположении простейшей дисциплины РСРБ, дисциплин с приоритетами. В дайной работе предполагается циклическая дисциплина обслуживания Ий, дающая, как известно, преимущество коротким заявкам.' Учет особенностей циклической дисциплины требует более тонких средств анализа," чем уравнения баланса, на которых основывается большинство методов расчета сетей. Методика исследования является дальнейшим развитием подхода, предложенного В.$. Яшковым. . .,'.■*

В соответствии о'дисциплиной НН все требования, поступающие как случайный входящий поток, занимают место в конце очереди к процессору. Каждому требованию отводится для обслуживания квант времени процессора. Если требование не обслу-жится полностью за время кванта, то оно переходит в конец очереди. Бели же обработка требования заканчивается, то оно покидает систему, и немедленно начинается обслуживание следующего требования. Важной задачей анализа таких систем является нахождение распределения времени пребывания к-тре-бования в ней, т.е. такого требования, для полного обслуживания которого необходимо к назначений кванта.Подход к ее решению связан с разложением случайной-величины Ук на сумму элементов задержки, связанных с каждым из требований, находящихся в системе в начальный момент времени, и помеченным требованием. Основным результатом является теорема:, условное распределение времени пребывания к-требовония в системе И/Ы/1

РИС.1. Структура ВС коллективного пользования

с дисциплиной ГШ при условии, что в момент своего прихода она застает в системе 1 других требований, имеет Ш1С г ^(з), 1=0 1 где ф (а)1 ф*(зК „ (а) _ щс

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

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

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

( р<0.7 ) хорошо описывается линейной зависимостью по к, все состайччюцие которой легко получить прямым вычислением;

б) надал'нь'вее средне? время отклика достигается для заявок,

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

В связи с этим важной задачей является выбор оптимальной величины кванта обслуживания. Однако, в данном случае совсем не очевидно, что следует«понимать под оптимальностью. С одной стороны, уменьшение размера кванта при учете затрат времени на переключение увеличивает безусловное среднее время отклика, уменьшая тем самым производительность. С другой стороны, в результате увеличения размера кванта нивелируется различие между дисциплинами ЯН и ГСГЗ. Поэтому критерий выбора кванта должен учитывать оба этих обстоятельства. Выразить его можно так:

т = д -П?Р- + а —Ь!— + а—— + ...+ а ——— , где ° а 1 Т(0) 1 Т(О) к Т(<3)

Та - величина, подлежащая минимизации выбором кванта, Т(0) -

безусловное среднее время отклика, - среднее время отк-

V

лика на требование длины 1;., 1=Т71с, а4, а2,...,а]с - весовые коэффициенты. Предложенная форма записи критерия, разумеется не является единственно возможной.

В § 1.2 предложена дискретная модель неоднородной ВО. Эта нвородность состоит в том, что времена обдумывания пользователей распределены по разному, чта при построении точной марковской модели приводит к показательной зависимости числа состояний от размерности ВС. Предложен метод расчета показателей загруженности и быстродействия отдельных устройств вн-

_.чцсли1мыюй структурЕХ, заключающийся в решении системы нелинейных алгебраических уравнений специального"вида:---

- г. т1^

"-1

-ут^— -А- , , и

, 2. т: I пт " 1 ■ —

1=1 I . _

где: .

- Т.-среднее время цикла 1-ой заявки. Это есть время, прошедшее между двумя последовательными моментами попадания этой заявки на обдумывание к своему (т.е. 1-ому) пользователю. Т. - неизвестные системы;

- qi - параметр геометрического распределения времени обдумывания;

- 2 - параметр геометрического распределения времени обслуживания;

- М - число заявок, циркулирующих в замкнутой системе.

Проведенные исследования показали, что эта неоднородность

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

I

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

ifflx адресов J, jИ ,.., J+N-1 приходятся на li различных модулей. Можно достичь в п раз большей скорости обмени с памятно а целом, чем у отдельного модуля, если обеспечить одновременное обращение к дашшм в каждом из модулей. 'Но этот резуль тат недостижим в действующа ВС ввиду наличия конфликтов доступа. Поэтому реальная производительность модульной памяти сказывается ниже максимально возможной. Одним из инструментов исследования эффективности использования модульной памп-га является стохастическое моделирование. Наиболее важный параметр таких моделей - адресный поток обращений процессоров { памяти, который зависит от равномерности расположения Дании и качества программного обеспечения.

Широкое распространение получили две модели обращения. Согласно первой из них любой запрос от процессора обращается к яюбому из N модулей с вероятностью 1/N. Такая модель аппроксимирует модульную организацию памяти при слабой регулярности размещения данных. Предположением, более адекватно omscu-завдим поток адресов, является локализация обращений, эаклю-1ающаяся в том, что если k-ий запрос приходится на j-ый мо-1уль, то (к>1 )-ый запрос обращается к (ЗИ )-ому модулю с бо-гсыцей вероятностью, чем к остальным. Эта модель хорошо аппроксимирует модульную память команд. Если испрльауется горизонтальная нумерация ячеек, то на линейном .'участке программы обеспечивается последовательное циклическое использование «одулей памяти. Нарушает же эту цикличность, например, номада. замыкающая цикл, или команда перехода.

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

_дяятся_чис.лoJ*oдyлe{^ цикла Т, которое пред-

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

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

{при ия-1 подчеркнутого слагаемого нет);

N

X X.. , =1

% 1 .

1+1

X . ц __

_ =о, (при ЫМ подчеркнутого слагаемого _______ нот )

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

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

В результате численного анализа установлено следутоее: а) при равновероятном обращении горизонатальное расслоен™ памяти не достегает эффекта ввиду частых блокировок, я болэ< половины модулей остаются незагруженными; увеличение числ модулей но ведет к увелитештг пропускной способности;.-б) при прочих равных условиях производительность модуль

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

В § 2.3 построена марковская модель для модульной памяти с локализованными обращениями. Разработанная модель представляет систему <2НН ) уравнений, 2!! из которых- линейные, одно - нелинейное. Для решения системы сформулирован быстро сходящийся итерационный алгоритм.

При численном анализе модели исследовались две основные характеристики: N - среднее число загруженных модулей и РШ

с р

- вероятность того, что система не заблокирована. Отмечено, что Г!?-» 0 при д -* 0 и РЯ-И при а N N при и Нср-»1 при q -» 1, т. е. крайнее значение q, минимизируя максимизирует Р?Р и наоборот. Поэтому для характеристики эффективности Функционирования.модульной памяти предложен "сборный" мультипликативный критерий: КМ - • Кср. Рассмотрена

задача оптимизации: 0 = га а х КМ (И,р). Показано, что КМ до~

0<д<1

стигает максимума на таком ч, при котором решение системы

уравнений удовлетворяет соотношению < я

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

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

•1С

ции инициируется наличием ее операндов; заранее последоьате--льность- выполнииия команд .не задается . При управлении потоком датшх в качестве операндов команда указываются не адреса ячеек памяти, а команда, результаты которых являются операндами данной команды. Типичная ЭВМ УВД представляет собой мультипроцессорную систему, состоящую из четырех основных компонент (рис. 2):

- командный блок (КБ), включающий множество блоков памяти, чье сг.н.'ртт**! чкздотсл г. сок-иуиаоаш исаолштсмим графом потока данных; блок памяти содержит код операции, порты вх-

Рис. 2. Структурная схема ЭВМ У11Д.

одных дашшх и адреса назначения ;

- селекторная сать, по которой готовые к выполнению команда передаются в один из процессорных элементов;

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

- распределительная сеть, по которой результаты расходятся

по своим адресам назначения в КБ.

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

I

уднено ее показательной трудоемкостью.

Модель с линейным зависимостью трудоемкости от И, где Н -максимально возможная местнсть команд, предложена в § 3.3 в виде системы нелинейных уравнений: а =

М-к Г р , р а" . . 1

к.-к- .+ тяг" —-~ + 0--~-•

1+1 алч ( (ГМИ-де-а) 1 (К-1) I (М-а) ^ Ч

1=ТТ1ГТ;

к.ачД. „ а.

' 4 • к =-—--; к +> к. = и.

(М-к0)ц _ (N-1)1 .(Я-а)

Неизвестные: а -среднее число загруженных процессоров; ка-среднее число заблокированных токенов; к* - среднее число активизированных блоков памяти; - среднее количество блоков памяти, которым до завершения формирваяия токенй осталось получить 1 операндов, 1=Т7Н, и ц - быстродействия процессора и памяти соответственно, N - число процессоров, М -- число блоков памяти, q - средний коэффициент размножения результата, полученного процессором. Доказана следующая тео-

рема:

необходимым~и~достаточным условием существовашм решения _ системы урапппний, ссс компонент которого положительны, яв-ляотся выполнение соотношения -в = рл^ <1, где Р -средняя местность команд в программе.

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

На основе предложенной модели разработана методика получения оценки для оптимального количества процессорны* элементов. Исследованы зависимости характеристик ЭВМ УВД от распределения местности команд, соотношения X и ц и др.

В § 3.4 предложена нестационарная модель ЭВМ УВД, позволяющая оценить время выполнения отдельной программы, оптимальное число процессоров и другие характеристики. При построении- стационарной модели предполагалось, что любой блок памяти может сколько угодно раз формировать токен и посылать его на выполнение в процессор, таким образом, вычислительный процесс не прекращается. Ясно, однако, что при выполнении одной программы каждая из команд выполняется конечное число раз. Когда "отработанными" окажутся все команды программы,- вычислительный процесс завершается ( хотя достаточно длительный

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

Математическая модель получена в виде системы обыкновенных дифференциальных уравнений. Число неизвестных функций -- (R2+3R+2)/2.

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

В четвертой главе рассматривается потоковая модель вычислений с управлением запросами. Концепция управления запросами является альтернативной управлению потоком операндов. В режиме потока операндов (eager) команда может быть выполнена как только доступны все ее операнды. С другой стороны, • при потоке запросов ( lazy ), команда выполняется только тогда, когда ее результат требуется другой, вызыващей командой. Ьагу-программа представляет собой смешанный граф потока операндов и запросов с_обратными дугами запросов и прямыми ' дугами передачи данных. Выполнение программы заключается в распространении 'запросов и дэнных в узлы графа. Преимущество lazy-вычислений состоит в потенциальном исключении лишней работы благодаря вычислению только тех данных, которые требуются. Кроме того, lazy-модель делает возможным интерактивный режим ввода/вывода. К недостаткам относится замедление работы по сравнению с eager из-за дополнительных затрат времени на генерацию, передачу и обработку запросов.

Главным объектом исследования является смешанный граф потока "запросов - и - данных. - В - § -4.2.. дано _ формальиое_определешю_ класса таких орграфов Ь(Х,и), X - множество вершин, и - множество робор, п -число вершин. Вершинам графа соответствуют исполняемые вычислительные процедуры. На множестве вершин, задана весовая функция р: Х-» Вое вершины соответствует времени, затрачиваемому на выполнение процедуры. Дуги орграфа имеют следующий смысл : если для выполнения процедуры а требуется предварительно получить результат, вычисляемый процедурой р, то вершины аир соединяются направленной из а в р дугой. Всем дугам назначен вес - время пересылки по ним от вершины к вершине запроса и результата, которые для простоты полагаются равными друг другу. Для моделирования процесса выполнения программы для узлов введены понятия активного, пассивного и рабочего состояния.

Ошшюм условия, которым должен удовлетворять класс исследуемых орграфов Ь*:

1) не допускается наличия орциклов, ибо это означало бы, что некоторая процедура обращается к самой себе; в то же время в графе Ь циклы допускаются;

2) в орграфе существует один и только один почин;

3) из каждой вершины в каждую другую может идти не более одной дуги;

4) отсутствуют петли;

5) Для любой вершины х существует ормаршрут <3(Е,х), начи-нащийся в Е и заканчивающийся в х.

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

Выделены две дисциплины обслуживания запросов, выбор той или иной из которой зависит от конкретного алгоритма:

1) активизация вершины по запросу от любого потребителя;

2) активизация вершины по запросу от всех потребителей.

Во втором случае вершина ж переходит в активное состояние

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

Исследованы следующие задачи:

а) расчет полного времени работы для режима !;

б) расчет полного времени работы для режима 2;

в) задача оптимального выбора запросов из очереди для режима 1 по критерию максимального быстродействия.

Показано, что решение задачи б) можно свести к задаче вычисления логического определителя с ограничениями на область теория которых основывается на работах В.И. Левина. Введен новый тип логических определителей, т.к. те, что рассмотрены В.И.Левиным не подходят для решения поставленной задачи. Разработан алгоритм полиномиальной сложности вычисления таких определителей.

Для задачи-в) показана ее содержательность и предложен эв- -ристический алгоритм. Он состоит в следующем:

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

запрос т с максимальной я-длиной ормаршрута д(0(Е,х) Я(и)

+ £ р(у)- р(Е)-р(х) - сумма весов дуг л вершин, .входящих в

и £с>

С

ормаршрут 0(Е,х), за исключением весов оконечных Берлин.

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

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

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

б) повышение быстродействия в режиме 1 распараллеливанием: построить в заданном взвешенном орграфе множество таких вершин, расщепление которых приводит к сокращению полного времени работы. Дано формальное описание операции расщепления;

в) задача исследования комбинированного режима: множество

Ь входных дуг вершины А разбивается на к непересекающихся к

подмножеств Ь1, Д^Ь^Ь, Кк^Ь. Крайние значения к = 1 и к=Ь соответствуют режимам 1 и 2. Вершина активизируется по получении запросов по всем дугам любого из подмножеств. Таким образом, запроси как бы обслуживаются в режиме 1 относительно не отдельного запроса, а их к групп, но каждая группа, взятая в отдельности обслуживается в режиме 2. Такой смешанный режим возникает из преобразований графов потоков данных.

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

Число таких объединений определяется выбранным уровнем параллелизма.

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

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

В диссертации получены следующие основ!ше научные и практические результаты:

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

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

3.Разработана нестационарная модель ЭВМ потока данных, и на ее основе получены оценки производительности, загрузки и других характеристик, внярлпнн важные закономерности."

4. Разработаны алгоритмы временного моделирования на нагруженных графа? вычислительных систем, управляемых" потоком гагтрчгоп, упю.п рг'гппиир дчя тализл прорзовдательности. Ис-глрдояпнц рпгли*иш« режимы обслуживания запросов и предложе-

но достаточно близкое к оптимальному расписание. К анализу графов—потоков -данных—впврвые_применена^_теория[^логических определителей, получившая в работе расширение и дальнейшее развитие. Поставлен ряд новых задач оптимизации на графах потоков данных, решение которых позволит улучшить показатели эффективности ВС.

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

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

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

7. Разработано программное обеспечение, реализующее предложенные в диссертации модели и методы. Пакет используется в

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

Теоретические результаты, полученные при исследовании вре-(

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

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

1. Фельдман Л.П., Труб И.И. Исследование стационарного режима в вычислительной системе, управляемой потоком данных. - Электронное моделирование, %5, 199^.

2. Фельдман Л.П., Труб И.И. О распределении времени оки-дания в вычислительноый системе с разделением времени, обслуживающей переменное число задач. - Деп. в ГНТБ Украины, $ 164, 1992.

3. Фельдман Л.П., Труб И.И. Вероятностная модель функцио- ' нирования модульной памяти с постоянным временем обслуживания запросов. - Деп. в ГНТБ Украины, й 308, 1993.

4. Фельдман Л. Л., Труб И.И. Аналитическая модель вычислительной системы с разделением времени, обслукивзющей постоянное число задач. - Деп. в ГНТБ Украины, £ 649, 1993.' — " 5. Труб И.И. Исследование нестационарного режима в вычислительной системе, управляемой потоком данных. - Деп. в ГНТБ Украины, Я 1378, 1993.

6. Фельдман Л.П., Труб И.И. Вычислительная система, управляемая потоком запросов: редукция к задаче на графе, алго-

ритмы анализа и оптимизации. -'Деп. в ГНТБ Украины, * 2349,

-----------------------------L--------------

7. Фальдаан Л.П., Сашенко H.A., Труб И.И. Разработка компьютерных технология обучения по курсу "Высокопроизводительные вычислительные системы"// Компьютерные программы учебного назначения; Тезисы докладов I Международной конференции. - Донецк, ДонГУ, 1993.

8. Методические указания по курсу "Высокопроизводительные

вычислительные системы ( Для студентов специальности 2204 )

/ Сост.: Л.П. Фельдман, И.И. Труб, О.Г. Щербакова. - Донецк, ДГТУ, 1993.

Труб И.И. Методы приближенного анализа производительности и повышения эффективности функционирования вычислительных сип-тем с параллельной обработкой данных (стохастические и дете -рминированнне модели) ^ _ •

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

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

Ключов! олова:

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

Trub I.I. Approximational performance evaluation methods for computer systems with parallel data processing (probabilistic and deterministic approaches).

PhD thesis contains, computational methods for multiaccess and multiprocessor computer systems, in particular, with non von Neumann architecture, created by means of queuing and graph theory. The results of Investigations based on the Implemented approaches are presented. It la determined that the necessary and sufficient condition of steady-state of Dataflow process Is following: the average arlty of program Instructions roust be exceeded, by the average number of Instruction result propagation. Proposed computational methoda are realized In software application package.

Введение.

ГЛАВА 1. Методы оценки быстродействия диалоговых вычислительных систем с циклической дисциплиной обслуживание.

1.1 Распределение времени ожидания в открытой вычислительной системе.

1.1.1. Аналитические результаты.

1.1.2. Результаты численных экспериментов.

1.2. Анализ неоднородной вычислительной системы коллективного пользования.

ГЛАВА 2. Аналитические модели функционирования оперативной памяти модульной структуры.

2.1. Обзор основных методов исследования.-2.2. Модель функционирования модульной с равновероятными обращениями к каждому модулю.

2.2.1. Постановка задачи.—

2.2.2. Определение множеств состояния и событий.

2.2.3. Построение системы уравнений.

2.2.4. Сведение к системе линейных уравнений

2.2.5. Анализ основных характеристик системы.

2.3. Исследование функционирования модульной памяти с неравновероятными обращениями.

2.3.1. Постановка задачи.

2.3.2. Анализ особенностей системы. Определение множества состояний.

2.3.3. Построение системы уравнений для. вероятностей состояний

2.3.4. Вывод уравнения для ъ.

2.3.5. Критерий эффективности.

ГЛАВА 3. Анализ производительности ЭВМ,. управляемой потоком операндов

3.1. Введение и обзор литературы.—

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

3.2.1. Постановка задачи.—

3.2.2. Математическая модель для случая А,<р,.

3.2.3. Случай различного быстродействия. процессоров

3.2.4. Учет быстродействия блоков памяти

3.2.5. Анализ средних.

3.2.6. Численные эксперименты.

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

3.3.1. Постановка задачи

3.3.2. Математическая модель.

3.3.3. Численные эксперименты.

ГЛАВА 4. Вычислительная система, управляемая потоком запросов: редукция к задаче на графе, алгоритмы анализа и оптимизации

4.1. Введение и обзор литературы.~

4.2. Математическая модель. Основные определения.

4.3. Режимы обслуживания запросов.

4.4. Расчет времени работы для режима 1.

Дисциплина FCFS

4.5. Расписания на графах потоков данных.

4.6. Стратегия оптимизации.

4.7. Моделирование обслуживания запросов в режиме

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

Актуальность темы. Задачи, рассматриваемые в работе, относятся к общей проблеме повышения эффективности функционирования вычислительных систем, более полного использования заложенных в них потенциальных возможностей. Научное направление, к которому относятся эти задачи, получило название "Оценка качества и оптимизация вычислительных систем". Исследуемые в нем проблемы весьма разнообразны и направлены на повышение производительности ВС. Одни из них решаются на этапе проектирования систем, другие возникают в процессе эксплуатации, когда выясняется, что какие-либо параметры не являются удовлетворительными, и их следует улучшить. Наиболее значимым из этих параметров является быстродействие, прямо связанное с общей производительностью ВС. Существует множество путей повышения быстродействия систем. К ним относится в первую очередь совершенствование технологической базы, на которой строятся ЭВМ и системы. Однако, опыт нескольких десятилетий применения средств вычислительной техники привел к выводу, что увеличение быстродействия за счет развития технологической базы происходит в среднем в 5 раз за 10 лет, что не является удовлетворительным для гораздо более быстро растущих потребностей науки, техники, промышленности, экономики. В связи с этим в настоящее время широко известные методы повышения эффективного быстродействия ВС опираются на распараллеливание вычислений путем совмещения во времени выполнения различных операций, новые архитектурные решения при проектировании ВС, увеличение уровней иерархии и расслоения памяти, совмещение ввода-вывода с работой центрального процессора и др. Однако, ограничения, присущие конкретным реализациям ВС, наличие конфликтных ситуаций, несоответствие алгоритмов и программ архитектуре могут привести к быстродействию, значительно худшему максимально возможного. С учетом этих условий большую важность приобретают оценки и рекомендации, получаемые на стадии проектирования. Наиболее быстрый и удобный способ получения таких оценок связан с разработкой аналитических методов исследования, которые хорошо зарекомендовали себя для анализа производительности ВС преимущественно с последовательной обработкой данных.

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

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

Основными задачами исследования являются:

- анализ йзвестных подходов и методов оценки производительности ВС оценка их трудоемкости;

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

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

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

- создание пакета прикладных программ, реализующего модели и методы, предложенные в работе;

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

Защищаемые научные положения и результаты, их новизна:

Положения:

1. Необходимым и достаточным условием существования стационарного режима в вычислительной системе, управляемой потоком операндов, является выполнение соотношения Р/ц < 1, где Б - средняя местность команд программы (число входных операндов), q - средняя ширина параллелизма алгоритма.

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

Результаты:

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

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

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

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

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

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

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

Реализация результатов работы. Результаты, полученные в диссертационной работа, были использованы в Институте шахтных информационно-управляющих систем Госуглепрома Украины при разработке систем распределенной обработки информации в АСУ ТП шахты; в научно-исследовательском институте горной геомеханики им М.М.Федорова при проектировании параллельного спектрального анализатора, работающего в режиме реального времени, в Институте прикладной математики и механики АН Украины при выполнении ряда НИР. Основные положения диссертации и разработанное программное обеспечение внедрены в учебный процесс на кафедре прикладной математики и информатики в Донецком Государственном Техническом Университете, в филиале кафедры "Прикладная математика и теория систем управления" Донецкого Государственного Университета при ИПММ НАН Украины.

Апробация. Основные результаты работы докладывались и обсуждались на научно-исследовательском семинаре по дискретной математике (Южный центр АН Украина, Одесса, 1993), I Международной конференции "Компьютерные программы учебного назначения" (Мариуполь, 1993), научных семинарах в ИПММ АН Украины (Донецк, 1993), кафедры алгебры и теории вероятностей Донецкого государственного университета (1992-1993 гг.), кафедры прикладной математики и информатики Донецкого технического университета (1992-1993 гг.).

Публикации. Содержание диссертации отражено в 8 опубликованных работах.

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

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

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

Третья и четвертая главы работы посвящены разработке математических моделей вычислительных систем, управляемых потоком данных (УПД), методы аналитического исследования которых находятся пока в начальной стадии развития. В третьей главе построена вероятностная модель вычислительной машины УПД и предложена эффективная методика расчета производительности, а также оптимального вычислительного ресурса - числа процессоров, требующихся для работы системы без блокировок. Рассмотрены модели стационарного и нестационарного режимов работы ЭВМ УПД. В связи с тем, что системы массового обслуживания, которыми моделируются ЭВМ УПД имеют особую специфику, в работе выделены наиболее интересные из этих особенностей, в частности, введено специальное понятие стационарного режима для таких систем и получено условие его существования, напоминающее по форме классическое условие стационарности для системы М/М/1, но с совершенно другим смыслом входящих в него параметров. Разработанные модели имеют приемлемую трудоемкость - число уравнений линейно зависит от максимальной местности команд, выполняемых процессором.

В четвертой главе построена детерминированная модель вычислительной системы, управляемой потоком запросов. Основным объектом исследования является ориентированный граф - граф потока данных, вершины которого соответствуют переменным, выражениям, функциям и процедурам программы, которые могут обрабатываться с заданной степенью параллелизма. Определен класс графов, элементы которого могут служить моделью редукционных 1 вычислений, причем отмечено, что он является подклассом антисимметрических графов Бержа. Основной исследуемой характеристикой здесь также является производительность. При этом поставлены и решены многие оригинальные задачи, в частности, задача оптимальной дисциплины обслуживания очередей запросов в узлах. Методологической основой исследования служат теория графов, методы дискретной оптимизации, теория логических определителей.

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

В заключении сформулированы основные результаты диссертации.

ЗАКЛЮЧЕНИЕ

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

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

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

3.Разработана нестационарная модель ЭВМ потока данных, и на ее основе получены оценки производительности, загрузки и других характеристик, выявлены важные закономерности.

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

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

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

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

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

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

1. Авен О.И., Гурин Н.Н., Коган Я.А. Оценка качества и оптимизация ычислительных систем. М.: Наука, 1982.

2. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычис-тельных сетях. М.: Наука, 1989.

3. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания: эория и применение к сетям ЭВМ. М.: Радио и связь, 1988.

4. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979

5. Клейнрок Л. Теория массового обслуживания. Л.: Машиностроение, 979.6. "Компьютер-пресс", Л 5, 1993.

6. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: аука, 1975.

7. Сигнаевский В.А., Коган Я.А. Методы оценки быстродействия вычис-ательных систем. М.: Наука, 1991.

8. Фельдман Л.П., Дедшцев В.А. Математическое обеспечение САПР: мо-злирование вычислительных и управляющих систем. Киев, УЖ ВО, 1992

9. Шерр А. Анализ вычислительных систем с разделением времени.- М.: яр, 1970.

10. Яшков С.Ф. Анализ очередей в ЭВМ. М.: "Радио и связь", 1989.

11. Bhat U.N. "Elements of Applied Stochastic Processes". Wiley, 2W York, 1972.

12. Ochi M.K. "Applied Probability and Stochastic Processes in Engl-serlng and Physical Sciences". Wiley, New York, 1990.

13. Taylor H.M., Karlin S. "An Introduction to Stochastic Modeling" Academic Press, New York, 1984.

14. Tipper D., Smdareshan M.K. "Numerical Methods for Modeling Com-iter Networks Under Nonstationary Conditions". IEEE Journal on Seated Areas in Communication, J 9, 1990.1. К главе 2

15. Авен О.И., Гурин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

16. Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978.

17. Барлоу Р.Х. Оценка производительности параллельных алгоритмов. В кн. Системы параллельной обработки (Под ред. Д.Ивенса). М.: Мир, 1985.

18. Гилмор П. Высокопараллельный процессор МРР.- В кн. СуперЭВМ: аппаратная и программная организация (Под ред. С. Фернбаха). М.: Радио и связь, 1991.

19. Дегтярев Е.К. Оценка средней скорости многосекционной памяти ЦВМ. Известия АН СССР. Техническая кибернетика, 1970, N 2.

20. Мгнатущешсо В.В. Организация структур управляющих многопроцессорных вычислительных систем. М.: Энергия, 1984.

21. Кемени Д.Д., Снелл Д. Конечные цепи Маркова. М.: Наука, 1970

22. Коуги П. Архитектура конвейерных ЭВМ. М.: Радио и связь, 1985

23. Миура К. СуперЭВМ фирмы Fujitsu: векторная система РАСОМ (Там же где и 4.).

24. Миура К., Учида К. Векторный процессор РАСОМ. В кн. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ (Под ред. Я.Ковалика).- М.: Мир, 1988.

25. Остланд Н.С., Хиббэрд П.Г., Вайтсайд P.A. О применении сильносвязанных многопроцессорных систем для научных вычислений. В кн. Параллельные вычисления (Под ред. Г.Родрига) - М.: Наука, 1986.

26. Пом А., Агравал 0. Быстродействующие системы памяти. М.: Мир, 1987.

27. Фельдман Л.П. Методические указания по курсу "Структуры вычислительных систем и организация вычислительных процессов". Донецк, ДНИ, 1987.

28. Фельдман Л.П., Дедищев В.А. Математическое обеспечение САПР: моделирование вычислительных и управляющих систем. Киев, ШК ВО, 1992

29. Хокни Р., Джессхоуп К. Параллельные ЭВМ: архитектура, программирование и алгоритмы. М.: Радио и связь, 1986.

30. Bhandarkar D.P. "Analysis of Memory Interference in Multiprocessors". IEEE Transactions on Computers, N9, 1975.

31. Budnik P., Kuck D.J. "The Organization and Use of Parallel Memories". IEEE Transactions on Computers, N12, 1971.

32. Burnett G.J., Goffman E.J. "Analysis of Interleaved Memory Systems Using Blockage Buffers". Commun. Ass. Gomput.Mach., N2, 1975.

33. Censier L., Feautier P. "A New Solution to the Coherence Problem in Multicache Systems"-IEEE Transactions on Computers, N12, 1978

34. Chang D.Y., Kuck J., Lawrie D.H. "On the Effective Bandwidth of Parallel Memories". IEEE Transactions on Computers, N5, 1977.

35. Coffman E.G., Burnett G.J., Snowdon R.A. "On the Performance of Interleaved Memories with Multiple Word Bandwidths". IEEE Transactions on Computers, N12, 1971.

36. Coffman E.G., Denning P.J. "Operating System Theory". Engle-wood Cliffs NJ Prentice-Hall, 1973.

37. De-Lei Lee "Architecture of an Array Processor Using a Nonlinear Skewing Scheme" . IEEE Transactions on Computers, N 4, 1992.

38. Dubois M., Briggs P.A. "Effects of CacheCoherency In Multiprocessors". IEEE Transactions on Computers, N11, 1982.

39. Flynn M.J. "Some Computer Organizations and Their Effectiveness" IEEE Transactions on Computers, N9, 1972.

40. Gottlieb A., Grishman R., Kruskal C.P., McAuliffe K.P., Rudolph L., Snir M. "The NYU Ultracomputer Designing an MIMD Shared Memory Parallel Machine".- IEEE Transactions on Computers, N2, 1983

41. Harper D.T. "Increased Memory Performance During Vector Accesses Through the Use of Linear Address Transformations" IEEE TransactIcms on Computers, N2, 1992.

42. Harper D.T., Jump J.R. "Vector Access Performance In Parallel Memories Using a Skewed Storage Scheme".- IEEE Transactions on Computers, N 12, 1987.

43. Hoogendorn O.H. "A General Model for Memory Interference in Multiprocessors". IEEE Transactions on Computers, N10, 1977.

44. Hwang K., Brlggs I*.A. "Oomputer Architecture and Parallel Processing". Mc Graw Hill, 1984.

45. Kaplan K.R., Winder R.O. "Cache-based computer systems", Computer, N 3, 1973.

46. Khuth D.E., Rao G.S. "Activity in an Interleaved Memory" IEEE Transactions on Computers, N9, 1975.

47. Kurtsberg M. "On the Memory Conflict Problem in Multiprocessor Systems". IEEE Transactions on Computers, N3, 1974.

48. Lawrie D.H. "Access and Alignment of Data in Array Processor" IEEE Transactions on Computers, N12, 1975.

49. LiuY.-C., Jou C.-J. "Effective Memory Bandwidth and Processor Blocking Probability In Multiple-Bus System". IEEE Transactions on Gomputers, N6, 1987.

50. OedW., Lange 0. "On the Effective Bandwidth of Interleaved Memories in Vector Processor Systems" IEEE Transactions on Computers, N 10, 1985.

51. Patel J.M. "Analysis of Multiprocessors with Private Cache Memories". IEEE Transactions on Gomputers, N3, 1982.

52. Rau B.R. "Interleaved Memory Bandwidth in a Model of Multiprocessor Computer System". IEEE Transactions on Computers, N7, 1979.

53. Rau B.R. "Program Behavior and the Performance of Interleaved Memories".- IEEE Transactions on Gomputers, N3, 1979.

54. Ravi C.V. "On the Bandwidth and Interference in Interleaved Memory Systems". IEEE Transactions on Computers, N8, 1972.

55. Sethi A.S., Deo N. "Interference in a Multiprocessor System with Localized Memory Access Probabilities". IEEE Transactions on Computers, N2, 1979.

56. Shapiro H.D. "Theoretical Limitation on the Efficient Use of Parallel Memories".- IEEE Transactions on Computers, N5, 1978.

57. Smilauer B. "General Model for Memory Interference In Multiprocessors and Mean Value Analysis". IEEE Transactions on Computers, N8, 1985.

58. Smith A. "Cache Memories". Computing surveys, N 9, 1982.

59. Spirn J.R. "Program Behavior Models and Measurements" -New-York, Elsevier-North Holland, 1977.

60. Herman F.W. "A Study of Interleaved Memory Systems by Trace Driven Simulation". Fourth Symp. on Simulation of Computer Systems, August, 1976.

61. Watson W.J. "The TIASG A Highly Modular and Flexible Super Computer Architecture". - AFIPS, Proceeding FJCC, 1972.

62. Wijshoff H.A.G., Leeuwen van J. "The Structure of Periodic Storage Schemes for Parallel Memories". IEEE Transactions on Computers, N6, 1985.1. К главам 3 и 4

63. Брехов 0., Морару В. Определение граничной производительности ЭВМ управляемой потоком данных. Автоматика и телемеханика ,N6,1992.

64. Брехов 0., Морару В. Оценка структурных различий ЭВМ, управляемых потоком данных. Автоматика и телемеханика, N 7, 1992.

65. Бэбб Р. Параллельная обработка крупноструктурированных потоков данных на CRAY Х-МР. В кн. СуперЭВМ: аппаратная и программная реализация (Под ред. С.Фернбаха), М.: Радио и связь, 1991.

66. Валях Е. Последовательно-параллельные вычисления.- М.: Мир, 1985

67. Воеводин В.В. Математические модели и методы в параллельных процвссах. М.: Наука, 1Э86.

68. Диниччи Дэвид Loral Dataflo LDP 100.- В кн. Программирование на параллельных вычислительных системах (Под ред.Р.Бэбба) М. : Мир, 1991

69. Дэннис Дж., Шнабель Р. Численные метода безусловной оптимизации и решение нелинейных уравнений. М.: Мир, 1988.

70. Зыков A.A. Основы теории графов. М.: Наука, 1987.

71. Капитонова Ю.В., Летичевский A.A. Математическая теория проектирования вычислительных систем. М.: Наука, 1988.

72. Клейнрок Л. Теория массового обслуживания. Л.: Машиностроение, 1979.

73. Конвей Р.В., Максвелл Л.А., Миллер Л.В. Теория расписаний. М.: Наука, 1975.

74. Левин В.И. К планированию работы вычислительных систем. Ч. 1, 2, 3. Автоматика и вычислительная техника, 1982- N5; 1983 - N 2, 3.

75. Левин В.М. Структурно-логические методы исследования сложных систем с применением ЭВМ. М.: Наука, 1987.

76. Лекции по теории графов (Емеличев В.А., Мельников О.И. и др. ) -- М.: Наука, 1990.

77. Майерс Г. Архитектура современных ЭВМ. Т.2. М.: Мир, 1982.

78. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991.

79. Саати Т.Л. Элементы теории массового обслуживания и ее приложения М.: Советское радио, 1971.

80. Сир Ж.- К. Метод потока операндов в многопроцессорных системах типа MIMD. В кн. Системы параллельной обработки (Под ред. Д. Ивенса), М.: Мир, 1985.

81. Триливен Филип К. Модели параллельных вычислений ( Там же, где и 17.).

82. Ху T.G. Параллельное упорядочивание и проблемы линии сборки. -Кибернетический сборник, вып.4. М.: Мир, 1967.-АЪ^

83. Amamiya M., Hasegawa R. "Dataflow Computing and Eager and Lazy Evaluations" New Generation Computers, 1984.

84. Arvlnd, Nlkhil R.S. "Executing a Program on the MIT Tagged Token Dataflow Architecture" IEEE Transactions on Computers, N 3, 1990.

85. Baba T., Bing Yao S., Hevner A.R. "Design of a Functionally Distributed, Multiprocessor Database Machine Using Data Flow Analysis" -- IEEE Transactions on Computers, N 6, 1987.

86. Bhuyan L., Ghosal D. "Approximate Analysis of Single and Multiple Ring Networks" IEEE Transactions on Computers, N 7, 1989.

87. Bohm A.P.W., Sargeant J. "Code Optimization for Tagged Token Dataflow Machines" IEEE Transactions on Computers, N 1, 1989.

88. Brock J.D.,Montz L.B. "Translation and Optimization of Data Flow Programs" in Proc. 1979 Int. Conf. Parallel Processing, 1979.

89. Buehrer R., Ekanadham K. "Incorporating Data Flow Ideas Into yon Neumann Processors for Parallel Execution" IEEE Transactions on Computers, N 12, 1987.

90. Campbell M.L. "Static Allocation for a Data-Flow Multiprocessor" in Proc. 1985 Int. Conf. Parallel Processing, August, 1985.

91. Chang P.R., Lee C.S.G. "A Decomposition Approach for Balancing Large Scale Acyclic Data Flow Graphs" IEEE Transactions on Computers, N 1, 1990.

92. Coffman E.G. "Computer and Job-Shop Scheduling Theory" New York Wiley, 1976.

93. Comte D., Hlfdi N., Syre J.C. "The Data Driven LAU Multiprocessor System: Results and Perspectives" Proc. IFIP, 1980.

94. Cornish M. "The TI Dataflow Architectures: the Power of Concurrency for Avionics" Proc. 3rd Conf. on Digital Avionics Systems, IEEE, New York, 1979.

95. Dennis J.B. "Data Plow Supercomputer" IEEE Computer, N 11, 1980.

96. Dennis J.B. "First Version of a Data Plow Procedure Language" Lecture Notes in Computer Science, vol.19, Sprlnger-Verlag, 1974.

97. Dennis J.B., Gao C.-R., Todd K.W. "Modeling the Weather with a Data Plow Supercomputer" IEEE Transactions on Computers, N 7, 1984

98. Dennis J.B., Lim W.Y.P., Ackerman W.B. "The MIT Data Plow Engineering Model" IF IP Proc., 1983.

99. Ercegovac M.D., Patel D.R., Lang T. "Functional Language and Data Flow Architectures" Proc 1983 Summer Computer Simulation Conference, vol.2, 1983.

100. Friedman D.P.,Wise D.S. "Cons Should Not Evaluate Its Arguments" Automata Languages Programming, 1976.

101. Gaudiot J.-L. "Data-Driven Multicomputers in Digital Signal Processing" Proc. IEEE, N 9, 1987.

102. Gaudiot J.-L. "Structure Handling in Data-Flow System" IEEE Transactions on Computers, N 6, 1986.

103. Gaudiot J.-L., Ercegovac M.D. "Performance Analysis of a Data Flow Computer with Variable Reduction Actors" Proc. 4th Intl. Conf. Distributed Computing Systems, 1984.

104. Gaudiot J.-L., Vedder R.W., Tucker G.K., Finn D., Campbell M.L., "A Distributed VLSI Architecture for Efficient Signal and Data Processing" IEEE Transactions on Computers, N 12, 1985.

105. Gaudiot J.-L., Wei Y.-H. "Token Relabeling In Tagged Token Data-Flow Architecture" IEEE Transactions on Computers, N 9, 1989.

106. Ghosal D.,Bhuyan L.N. "Performance Evaluation of Dataflow Architecture". IEEE Transactions in Computers, N 5, 1990.

107. Gonzalez M.J. "Review on Deterministic Scheduling Theory" ACM- i 8S

108. Computer Surreys, N 3, 1977.

109. Gostelow К.P., Thomas R.E. "Performance of a Simulated Dataflow Computer" IEEE Transactions on Computers, N 10, 1980.

110. Granski M., Koren I., Silberman G.M. "The Effect of Operation Scheduling on the Performance of a Data Flow Computer" IEEE Transactions on Computers, N 9, 1987.

111. Gurd J.R., Kirkham C.C., Watson I. "The Manchester Prototype Dataflow Computer" Comm. ACM, N 1, 1985.

112. Ha S., Lee E.A. "Compile-Time Scheduling and Assignment of Dataflow Program Graphs with Data-Dependent Iteration" IEEE Transactions on Computers, N 11, 1991.

113. Hartimo I., Kronlof K., Simula 0., Skutta J. "DESP: A Data Flow Signal Processor" IEEE Transactions on Computers, N 1, 1986.

114. Hudak P. »Goldberg B. "Distributed Execution of Functional Programs Using Serial Comblnators" Transactions on Computers, N10, 1985.

115. IEEE Computer. Special Issue on Dataflow Computers.- N 2, 1982.

116. Jen C.W., Kwai D.M. "Data Flow Representation of Iterative Algorithms for Systolic Arrays" IEEE Transactions on Computers, N 3, 1992

117. Jess A.G., Keesh G.M. "A Data Structure for Parallel L/U decomposition" IEEE Transactions on Computers, N 3, 1982.

118. Johnsson T. "Efficient Computation of Lazy Evaluation" ACM SIG-PLAN Notices, N 6, 1984.

119. KanR. "Machine Scheduling Problems" Nethelands: Nijhoff, 1976.

120. Kavi K.M., Buckles B.P., Bhat U.N. "A Formal Definition of Dataflow Graph Model" IEEE Transactions on Computers, N 11, 1986.

121. King P.J.В., Mitrani I. "Modeling a Slotted Ring Local Area Network" IEEE Transactions on Computers, N 5, 1987.

122. Kohler W.H. "A Preliminary Evaluation of the CP Method for Scheduling Tasks on Multiprocessor Systems",' IEEE Transactions on Computers, N 12, 1975.

123. Lee E.A., Messerscbmitt D.G. "Static Scheduling of Synchronous Data Plow Programs for Digital Signal Processing" IEEE Transactions on Computers, N 1, 198T.

124. Loucks W.M., Hamacher V.G., Prelss В., Wang L. "Short-packet Transfer Performance in Local Area Ring Networks". IEEE Transactions on Computers, N 11, 1985.

125. Mago G.A. "A Network of Microprocessors to Execute Reduction Languages". Int. Journ. of Computer and Information Sciences, 8.5 and 8.6 (1979)

126. O'Leary D., Stewart G. "Data-Plow Algorithms for Parallel Matrix Computations" Commun ACM, N 6, 1985.

127. Parhl K.K.,Messerschmitt D.G. "Static Rate-Optimal Scheduling of Iterative Data-Plow Programs via Optimum Unfolding". -IEEE Transactions on Computers, N 2, 1991.

128. Patnaik L.M., Govindarajan R., Ramadoss N.S. "Design and Performance Evaluation of EXMAN: An Extended Manchester Data Plow Computer" IEEE Transactions on Computers, N 3, 1986.

129. Pingali K., Arvlnd "Efficient Demand-Driven Evaluation" Part 1, ACM Trans. Programming Language Systems, N 4, 1985; part 2, N 1,1986.

130. Ramamdarthy C.V., С handy K.M., Gonzalez M.J. "Optimal Scheduling Strategies In a Multiprocessor Systems" IEEE Transactions on Computers, N 2, 1972.

131. Rambaugh J.E. "Data Flow Multiprocessor". IEEE Transactions on Computers, N 2, 1977.

132. Reed D., Patrick M. "Iterative Solution of Large Sparse Linear Systems on a Static Data Flow Architectures:Performance Studies" IEEE Transactions on Computers, N 10, 1985.

133. Requa J.E., McGraw J.R. "The Piecewise Data Flow Architecture: Architectural Concepts" IEEE Transactions on Computers, N 5, 1983.

134. Sarkar V., Hennessy J. "Partitioning Parallel Programs for Macro&ataflow" in Proc. 1986 AGI Conf. Lisp Functional Programming, Cambridge, MA, Aug. 4-6, 1986.

135. Srinlvas M.A. "Optimal Parallel Scheduling of Gaussian Elimination DAG's" IEEE Transactions on Computers, N 12, 1983.

136. Takesue M. "Cache Memories for Data Plow Machines" IEEE Transactions on Computers, N 6, 1992.

137. Treleaven P.C., David B.R., Hopkins B.R. "Data driven and Demand-driven Computer Architecture" ACM Gomput. Surveys, N 3, 1982.

138. Turner D.A. "A Hew Implementation Technique for Applicative Languages" Software: Practice and Experience, N 9, 1979.

139. Ullman J.D. "MP-complete Scheduling Problems" Journal on Computer Systems Sciences, N 6, 1975.

140. Veen A.H. "Dataflow Machine Architecture" AGM Computer Survey, N 12, 1986.

141. Vegdahl S.R. "A Survey of Proposed Architectures for the Execution of Functional Languages" Transactions on Computers, N 12, 1984.

142. Wadge W.-W., Ashcroft E.A. "Lucid. The Dataflow Programming Language" London, England: Academic, 1985.

143. Wei Y.-H.,Gaudlot J.-L. "Demand-Driven Interpretation of PP Programs of a Data Plow Microprocessors" IEEE Transactions on Computers, N 8, 1988.

144. Wing 0., Huang J.W. "A Computation Model of Parallel Solution of Linear Equations" IEEE Transactions on Computers, N 7, 1980.1. S it