автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Система управления параллельной обработки данных в локальных вычислительных сетях

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

'< О 0 „ МИРОШНИКОВ АНДРЕЙ СЕРГЕЕВИЧ

СИСТЕМА УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ В ЛОКАЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ

Специальность: 05.13.01 - Упра ;£■■ е в техгипе^'.-'х й-гсте-.'.г'

у>ВТОРЕ>'»Е'. " дис. ;ртаи'Ч 1 ? „'ни -з\ие тено'; степени .санди ;. та технических нг /к

Владикавказ - 2000

Работа выполнена в Северо-Кавказском ордена Дружбы народов государственном технологическом университете.

Научный руководитель: д.т.н, проф. Гроппен В.О.

Официальные оппоненты: д.т.н, проф. Алкацев М.И.

к.т.н., Кузнецов С.Н.

Ведущая организация: Государственный комитет РСО-Алания

Защита состоится 27 июня 2000 г. в 1330 на заседании диссертационного совет? № 063.12.03 в Северо-Кавказском ордена Дружбы народов госуда'. с гиенном технологическом университете, по адресу: 362021, 1 ч'.О Ачания, г. Владикавказ ул. Николаева, 44, СКГТУ. Ф.'.'сс: (867 1) ' Ку45

С диссертацией м..\:но ознакомиться в бяблио: :ке Северг-Кавк«зг.к< 1 о ордена Дружбы народов I.глудг¡: стве-нтго гехноло*-и\ .кого уш.т epi.it 'ей

Автореферат р дослан 22 мая 2000 г.

Ученый секретарь диссертационного совета

по статистике

д.т.н., проф.

Хасцаев Б.Д.

г

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Развитие однопроцессорных вычислительных систем (ВС) и сравнительная простота реализации алгоритмов для них привели к доминированию аппаратного и программного обеспечения класса 81БО над их многопроцессорными и параллельными аналогами. Скорость вычислений в однопроцессорных ВС напрямую зависит от тактовой частоты процессора, объема оперативной памяти, архитектуры ВС и других параметров.

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

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

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

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

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

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

Практическая ценность. Результаты работы позволили на базе ЛВС создать СОПОИ, которая по своим эксплуатационным характеристикам превосходит функционально близкие пакеты СОЮЗА и БСОМ, позволяя более эффективно, по сравнению с последними, использовать ресурсы ЛВС в соответствии с выбранными целями. Ее применение также упрощает и ускоряет процесс создания прикладных программ, основанных на распараллеливании вычислений. При этом последние оптимизируются по стоимости или времени решения задач. Кроме того, следует отметить возможность решения задач с заданной надежностью. Применение СОПОИ позволяет более эффективно использовать ресурсы ЛВС и сократить затраты на обработку информации в реальном режиме времени.

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

зования предложенных в диссертации методик, алгоритмов и программных средств.

Реализация результатов работы. Научные и практические результаты диссертационной работы положены в основу создания СОПОИ, которая используется в учебном процессе СевероКавказского государственного технологического университета. Реализация системы осуществлена для IBM-совместимых компьютеров, работающих в операционных средах Microsoft Windows 9x/NT/2000 и объединенных в ЛВС. Базовый язык - объектный Паскаль. Программный пакет СОПОИ внедрен в ТФ ОМС РСО-Алания для ускорения обработки статистических данных о застрахованных лицах.

Апробация работы. Основные результаты диссертации докладывались на научных конференциях СКГТУ 1998 - 2000 г.г. Апробация диссертационной работы в целом проведена в учебном процессе СКГТУ.

Публикации. По результатам выполненных исследований опубликовано 5 печатных работ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 106 наименований, 4 приложений, содержит 36 рисунков, 7 таблиц и 157 страниц текста.

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

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

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

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

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

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

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

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

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

Xj - число процессоров, используемых МВК для решения /-ой задачи (V/, Х,<Р)\ а - стоимость коллективно используемых ресурсов МВК (винчестера, сервера, коммуникационной сети и т. п.); Ъ - стоимость индивидуально используемых процессором ресурсов (сам процессор, его локальная память, т. п.); с - среднее время, затрачиваемое МВК на организацию вычислений;

d¡ - время решения /-ой задачи одним процессором; п - число задач в пакете; к - коэффициент пропорциональности; 5 - стоимость решения задачи;

Исследуемые ниже модели опираются на следующие допущения:

а). Время - решения /-ой задачи X¡ процессорами МВК в первом приближении обратно пропорционален их количеству:

б). Стоимость единицы времени МВК, используемого для решения /-ой задачи линейно зависит от величины Хс.

в). Все процессоры МВК однородны.

г). Все X,- процессоров завершают работу одновременно, т.е. ее-

0)

А,=к(а+ЬХ,),

(2)

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

Пусть требуется определить оптимальное используемое для решения некоторого пакета задач число рабочих станций в СОПОИ, если:

1. Стоимость обработки пакета задач должна быть минимальна.

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

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

5 = tk(a + ЬХ,)

шах X, < Р

С +

лг.

т т

(3)

V /, X, > 1, целое Если все п задач в пакете решаются параллельно, то формальная постановка задачи оптимизации стоимости вычислений имеет вид:

5 = +

С + — ->• Ш1П

X,

(4)

1=1

V/, х1 > 1, целое ,

При распараллеливании пакета задач минимизацию стоимости вычислений целесообразно проводить с учетом ограничения на время решения каждой задачи. Пусть Г; - это верхняя граница времени решения ьой задачи, тога системы (3) и (4) можно преобразовать к виду (5) и (6) соответственно.

г

S = Yk{a + bX,)

c + -

X,

—> mm

V'.I

c+-

X

<T,

i J

maxXrSP V/, x, > 1, целое

S = ^k{a + bXt)

V/, с + — < T,

X, '

c + -

->min

(6)

Z X.&P

V/, > 1, целое

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

Решения систем (3) - (6) используются при создании пакета прикладных программ, входящего в состав СОПОИ и предназначенного для параллельного вычисления определенных интегралов, выполнения матричные операций, решения задач нелинейного программирования и обработки графической информации.

Системы (3) - (6) относятся к минимизации стоимости параллельной обработки. В главе также рассмотрены задачи связанные с минимизацией времени решения как единичных задач пользователя, так и пакетов этих задач.

В простейшем случае, когда решение одной задачи производится X процессорами, то время ее решения определяется (1). Учитывая,

что величина X не должна превосходить общего числа Р рабочих станций СОПОИ, получим модель минимизации времени решения одной задачи:

Т = с +--> лип

X

(7)

Х<Р Х>\, целое

Очевидно, что решением задачи (7) является Х= Р. Вводя в систему (7) ограничение на стоимость решения задачи, получим:

Т = с +--ишп

X

к(а + ЬХ)\с +

(8)

Х<Р

целое

Решением системы (8) является (9): 1,/<1

Х = \Р,/>Р (9)

/,1</<Р

где/= тах{А,1, Х2}. X \ и Хг - корни квадратного уравнения (10), с учетом целочисленности.

ЬсХ2 +1 ас + Ьс!--\Х + а(1 = 0

(10)

При анализе минимизации времени пакета задач, целесообразно рассмотреть два варианта:

а) все задачи взаимосвязаны, результаты решения одних являются исходными данными для других и поэтому при распараллеливании решаются последовательно одна за другой;

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

г

леливании решаются одновременно.

Если все задачи решаются последовательно, причем порядок решения определяется перестановкой л(п), то формальная постановка задачи имеет вид:

л (

с + -

Х<

-> ГП1П

1Ха+ьх>)

тах X, < Р

с+— |<5 X,

(И)

V/, X> 1, целое

Во втором случае, если все задачи решаются параллельно и перераспределение рабочих станций в ходе решения запрещено, то минимизации времени обработки пакета отвечает система (12):

4

тах с + ■

!£,<;* X,

■тт

с + -

X,

<5

(12)

1=1

V/, Х1 > 1, целое

Для решения систем (11) и (12) в работе такжи предложены специальные алгоритмы, которые позволяет исключить полный перебор.

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

Пусть требуется определить минимальное число рабочих станций СОПОИ, для решения пакета из п последовательно решаемых задач, если каждая рабочая станция имеет надежность работы />,, а для каждой из задач пакета известно время решения Г, с заданной надежностью <3-

Формальная постановка данной задачи имеет вид:

Р

шш

■М

с + -

<Т,

(13)

ыч

\<д<Р, д и Р-целые Преобразуя первые п неравенств системы (13) к виду:

¿4-

V/, + — Ч

определ) ;м ■: eJ --.чину д следующим о С разом:

(14)

д = тах

IX

м

(15)

Т, -¿с

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

В третьей главе экспериментально проверена эффективность реализации в СОПОИ рассматриваемых в диссертационной работе параллельных алгоритмов, а также поставленных оптимизационных задач.

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

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

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

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

Четвертая глава посвящена описанию СОПОИ. Рассмотрены цели создания системы, ее разработка и использование.

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

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

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

На этапе реализации выбранной пользователем стратегии, серверная компонента непрерывно контролирует процессы, развернутые

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

СОПОИ включает в себя следующие элементы:

- локальную вычислительную сеть. Она служит базой для создания МВК, т.к. содержит все необходимые для этого компоненты: сервер, рабочие станции, каналы связи и сетевую операционную систему. Данный элемент является аппаратной частью СОПОИ. Его создание не рассматривается в работе, а подразумевается использование существующей сети, удовлетворяющей определенным требованиям. Эти требования будут рассмотрены в разделе, посвященном ЛВС;

- сетевую операционную систему связи (СОСС). СОСС расширяет возможности ЛВС до МВК и выполняет системные функции по распараллеливанию вычислений в сети. Предоставляет приложениям СОПОИ прикладной программный интерфейс. С его помощью осуществляется управление и контроль за работой параллельных процессов;

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

нению с последовательной;

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

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

Рассмотрены такие основные задачи СОПОИ, как:

— учет подключения машин к СОПОИ и отключения от нее;

— регистрацию прикладных программ в СОПОИ;

— запуск и выгрузка приложений параллельных процессов;

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

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

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

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

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

По итогам работы получены следующие результаты:

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

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

3. Разработанные алгоритмы программно реализованы в рамках пакета СОПОИ, позволяющего эффективно организовывать параллельные вычисления в локальных вычислительных сетях.

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

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

высокую эффективность алгоритмов поиска оптимальных стратегий распараллеливания.

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

1. Мирошников A.C. Оценка эффективности параллельной обработки вычислений при решении некоторых задач // Владикавказ, Труды СКГТУ, 1999. - Вып. 6.

2. Мирошников A.C. Система оптимальной параллельной обработки информации СКГТУ // Владикавказ, Труды СКГТУ, 2000. -Вып. 7.

3. Гроппен В.О., Мирошников A.C. Модели управления системой оптимальной параллельной обработки информации в ЛВС СКГТУ// Владикавказ, Труды СКГТУ, 2000. - Вып. 7.

4. Мирошников A.C. Система оптимальной параллельной обработки информации // Сб. трудов аспирантов. - Владикавказ: Терек. 2000 г.

5. Гроппен В.О. Мирошников A.C. Надежность параллельных вычислений // Сб. трудов аспирантов. - Владикавказ: Терек. 2000 г.

Подписано к печати 20.05.2000 г. Объем 1 п.л. Тираж 100 экз. Заказ № 832. Подразделение оперативной полиграфии СКГТУ «Терек». РСО-Алания, г. Владикавказ, ул. Николаева, 44.

Введение.

Глава 1. Распараллеливание алгоритмов и программ.

1.1. Введение.

1.2. Организация параллельных процессов.

1.3. Диспетчеризация и синхронизация.

1.4. Анализ программ для распараллеливания.

1.5. Структуризация программ.

1.6. Инициализация и завершение параллельных процессов.

1.7. Численное интегрирование.

1.8. Матричные операции.

1.9. Решение задач нелинейного программирования.

1.10. Фильтрация точечных помех.

Выводы.

Глава 2. Задачи оптимизации параллельных вычислений.

2.1. Введение.

2.2. Обозначения, определения и допущения.

2.3. Минимизация стоимости решения задач.

2.4. Минимизация времени решения задач.

2.5. Надежность параллельных вычислений.

Выводы.

Глава 3. Экспериментальный анализ эффективности параллельных вычислений в СОПОИ.

3.1. Численное интегрирование.

3.2. Матричные операции.

3.3. Решение задач нелинейного программирования.

3.4. Фильтрация помех.

Выводы.

Глава 4. Система оптимальной параллельной обработки информации.

4.1. Цели создания СОПОИ.

4.2. Выбор стратегии построения СОПОИ.

4.3. Составные части СОПОИ.

4.4. Локальная вычислительная сеть.

4.5. Сетевая операционная система связи.

4.6. Прикладной программный интерфейс СОПОИ.

4.7. Работа СОПОИ.

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

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

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

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

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

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

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

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

Реализация результатов работы. Научные и практические результаты диссертационной работы положены в основу создания СОПОИ, которая используется в учебном процессе Северо-Кавказского государственного технологического университета. Реализация системы осуществлена для IBM-совместимых компьютеров, работающих в операционных средах Microsoft Windows 9x/NT72000 и объединенных в ЛВС. Базовый язык - объектный Паскаль. Программный пакет СОПОИ внедрен в ТФ ОМС РСО-Алания для ускорения обработки статистических данных о застрахованных лицах.

Апробация работы. Основные результаты диссертации докладывались на научных конференциях СКГТУ 1998 - 2000 г.г. Апробация диссертационной работы в целом проведена в учебном процессе СКГТУ.

Публикации. По результатам выполненных исследований опубликовано 5 печатных работ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 106 наименований, 4 приложений, содержит 36 рисунков, 7 таблиц и 157 страниц текста.

Выводы

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

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

3. Созданы прикладные программы использующие систему оптимальной параллельной обработки информации.

4. В системе управления СОПОИ используются и развиваются идей оптимизации параллельной обработки информации, изложенные в [87, 88, 101, 102].

5. СОПОИ внедрена и опробована в учебном процессе СКГТУ на кафедре Автоматизированной обработки информации при проведении лабораторных работ, практических занятий, курсового и дипломного проектирования.

- 117 — ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработанные алгоритмы программно реализованы в рамках пакета СОПОИ, позволяющего эффективно организовывать параллельные вычисления в локальных вычислительных сетях.

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

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

1. Бурцев B.C. Принципы построения многопроцессорных вычислительных комплексов «Эльбрус». - Препринт. - М:. 1977. - 53с.

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

3. Игнатущенко В.В., Точева К.Т. Организация однородных решающих полей и оценка их эффективности // Вопросы кибернетики. Вычислительные машины и системы с перестраиваемой структурой / НС по комплексной проблеме «Кибернетика» АН СССР. М„ 1978. - С. 83-90.

4. Каляев A.B. Организация многопроцессорных систем на принципах потока данных и программирования архитектуры // Высокопроизводительные вычислительные системы: Тез. докл. 2-го Все-союз. совещания. Батуми, 1984. - С. 19-20.

5. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. - 519 с.

6. Ершов А.П. Трансформационная машина: тема и вариации // Проблемы теоретического и системного Программирования / Вычислительный центр СО АН СССР. Новосибирск, 1982. - С. 5-24.

7. Прангишвили И.В., Виленкин С .Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Энергоатомиздат, 1983. - 312 с.

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

9. Бабаян Б.А. Основные принципы программного обеспечения МВК. «Эльбрус». Препринт. - М., 1977. - 12 с.

10. Бабаян Б.А., Сахин Ю.Х. Система «Эльбрус» // Программирование 1980 - № 6. - С. 72-86.

11. Барский А.Б. Монопрограммные высокопараллельные локально-асинхронные вычислительные структуры // Вопросы кибернетики. Эффективные вычисления на супер-ЭВМ / НС по комплексной проблеме «Кибернетика» АН СССР М:. 1988. - С. 148-170.

12. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. - 192 с.

13. Барский А.Б. Потоковая обработка информации в ВС на асинхронном решающем поле // Вопросы кибернетики. Проблемы организации высокопроизводительных ЭВМ / НС по комплексной проблеме «Кибернетика» АН СССР. М., 1984.-С. 119- 141.

14. Башарин Г.П., Богуславский Я.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных систем // Автоматика и вычислительная техника. 1980. - № 6, - С. 27-32.

15. Вейцман К. Распределенные системы мини- и микроЭВМ / Пер. с англ. под ред. Г. П. Васильева. М.: Финансы и статистика, 1983. - 382 с.

16. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980. - 520 с.

17. Вальковский В.А. Практические методы усовершенствования параллельных структур программ // Изв. АН СССР. Техническая кибернетика. 1980. - № 5. - С. 130-137.

18. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. -272 с.

19. Бакенрот В.Ю. Организация вычислительного процесса в однородных вычислительных системах при решении пакета сложных задач // Изв. АН СССР Техническая кибернетика. 1983. - № 4. -С. 112-119.

20. Бакенрот В.Ю., Чефранов А.Г. Эффективность приближенных алгоритмов распределения программ в однородной вычислительной системе // Изв. АН СССР. Техническая кибернетика. 1985. - № 4. - С. 135-148.

21. Казаринов JI.C. Мерензон М.Н. Планирование параллельных вычислений в управляющих МВС при дефиците ресурсов надежности // Управляющие системы и машины. 1988. -№ 2. - С.22-26.

22. Моисеев Н.В. Эффективность планирования последовательности выдачи команд для конвейерной ЭВМ // Вопросы кибернетики. Эффективное использование высокопроизводительных ЭВМ / НС по комплексной проблеме «Кибернетика» АН СССР. М:. 1985. -С. 89-110.

23. Иванов JI.M. Техника оптимизации алгоритмов процессорных элементов с асинхронно-модульной структурой // Кибернетика. -1980.-№ 2.-С. 108-117.

24. Глушков В.М., Капитонова Ю.В., Летичевский A.A., Горлач С.П. Макроконвейерные вычисления функций над структурами данных//Кибернетика. 1981. -№ 4. - С. 13-21.

25. Торгашев В.А. Управление вычислительными процессами в машинах с динамической архитектурой. Препринт. - Л.: 1982. -14 с (ЛНИВЦ АН СССР, № 33).

26. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989. -320 с.

27. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981. -254 с.

28. Барбан А.П. Метод диспетчеризации параллельных структурированных программ, в однородных вычислительных системах // Электронное моделирование 1983. - № 2. - С. 21-27.

29. Барский А.Б. О построении диспетчеров для вычислительных систем // Изв. АН СССР. Техническая кибернетика. 1971. -№1. -С. 113-118.

30. Каган Е.М., Крейнин А.Я. Модели конфликтов в памяти мультипроцессорных систем // Автоматика и вычислительная техника.1982. -№ 2. -С. 59-65.

31. Максименков A.B. Анализ алгоритмов диспетчеризации задач мультипроцессорной ЭВМ // Управляющие системы и машины. -1978.-№3.-С. 62-68.

32. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. М: Наука, 1987. - 272 с.

33. Елькин О.Г., Коношенко М.П. Исследование структуры алгоритма для выявления возможности его распараллеливания // Кибернетика. 1983. - № 2. - С. 29-36.

34. Митяева С.А. К вопросу о распараллеливании программ для многопроцессорных вычислительных систем // Кибернетика. 1980. -№2.-С. 47-50.

35. Параллельная обработка информации. Т. 1. Распараллеливание алгоритмов обработки информации / Под ред. А.Н. Свенсона. -Киев: Наукова думка, 1985. 280 с.

36. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков H.H. Элементы параллельного программирования М.: Радио и связь,1983.-240 с.

37. Janicki R. Transforming Sequential Systems Into Concurrent Systems // Theor. Comp. Sc. 1985. - Vol. 36, № 1. - p. 27-57.

38. Flynn M. J., Hennessy J.L. Parallelism and Representation Problems in Distributed Systems // IEEE Trans. 1980. - Vol. C.-29, № 12. -P. 1080-1086.

39. Hammer C., Raebel G. Code Generation for Partially Vectorizable Loops in the Vectorizing Pascal-XT compiler // LNCS, Vol. 237. CONPAR-86 Conf. Proc., Aachen, 1986. Berlin: Springer-Verlag.—1986. - P. 295-302.

40. Juelich O.C., Foulk C.R. Computation of Acyclic Smooth Programs for Parallel Execution // ACM Trans, on Programming Languages and Systems. 1981. - Vol. 3, № 1. - P. 24-48.

41. Keller R.M. Parallel Program Schemata and Maximal Parallelism // JACM 1973. - Vol. 20, № 3. - P. 514-537.

42. Kuck D.J. Automatic Program Restructuring for High-speed Computation // LNCS, Vol. 11. CONPAR-81. 1981. - Berlin: Springer-Verlag. - P. 66-84.

43. Lecou H.P. SAUGE: How to use the Parallelism of Sequential Programs // LNCS, Vol. 11. CONPAR-81. Berlin: Springer-Verlag. -1981. - P. 231-244.

44. Padua D.A., Kuck D.J., Lawrie D.H. High-speed Multiprocessors and Compilation Techniques // IEEE Trans. 1980. - Vol. C - 29, № 9. -P. 763-776.

45. Williams S.A., Evans D.J. An Implicit Approach to the Determination of Parallelism // Int. J. Comput. Math. 1980. - № 1. - P. 51-59.

46. Conf. Proc., Aachen, 1986. Berlin: Springer-Verlag. - 1986. - P. 295-302.

47. Барский А.Б. Параллельные процессы в Вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. -256 с.

48. Верлань А.Ф., Горячев В.Ф., Ефимов И.Е. Об одной реализацииметода автоматического распараллеливания алгоритмов и программ // Электронное моделирование. 1981. - № 2, - С. 23-25.

49. Иткин В.Э. Динамическое распараллеливание программ методом смешанных вычислений // Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ / Вычислительный центр СО АН СССР. Новосибирск, 1983. - С. 110-126.

50. Колесник A.M., Шкут Н.В. Трансляция АЛГОЛ-программ в параллельные программы // Кибернетика. 1985. - №3. - С. 112-113.

51. Крат С.П. Об организации процесса динамического распараллеливания последовательных программ // Развитие теории многопроцессорных систем. Киев, 1984. - С. 20-26.

52. Мерензон М. Н. Алгоритм динамического программирования составления оптимального расписания для неоднородной вычислительной системы // Изв. АН СССР. Техническая кибернетика. -1986.-№ 1.-С. 17-20.

53. Годлевский А.Б., Крат С. П. Об одном подходе к реализации динамического распараллеливания программ на многопроцессорных системах // Кибернетика. 1984. - № 3. - С. 114-117.

54. Барбан А.П., Игнатущенко В.В. Распараллеливание структурированных программ // Электронное моделирование. 1982. - № 2. -С. 28-35.

55. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. - 176 с.

56. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. -М.: Наука, 1982.-340 с.

57. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

58. Игнатущенко В.В. Конвейерная организация управления скалярными командами для многопроцессорных вычислительных систем // Автоматика и телемеханика. 1983. - № 2. - С. 27-63.

59. Тюляева В.В. Алгоритм выделения параллельных линейных участков ФОРТРАН-программ // Методы решения задач математической физики и их программное обеспечение. М.: МГУ, 1984. -С. 113-114.

60. Хорошавина Г.Ф. Об одном практическом методе анализа и преобразования последовательных программ к параллельному виду // Программирование. 1981. - № 1. - С. 42-47.

61. Коарбан А.П., Игнатущенко В.В. Распараллеливание структурированных программ // Электронное моделирование. -1982.-№2.-С. 28-35.

62. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Алгебра алгоритмов и динамическое распараллеливание последовательных программ // Кибернетика. 1982. - № 5. - С. 5-10.

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

64. Афанасьева Т.Ф. Анализ циклических участков ФОРТРАН-программ // Многопроцессорные вычислительные структуры. -Таганрог, 1982. С. 3-11. (Межвуз. темат. науч. сб. Вып. 4).

65. Бабичев A.B., Лебедев В.Г. Распараллеливание программных циклов // Программирование. 1983. - № 5. - С. 52-64.

66. Дорошенко А.Е. О преобразованиях циклических операторов к параллельному виду // Кибернетика. 1982. - № 4. - С. 22-28.

67. Миренков H.H., Симонов С.А. Выявление параллелизма в циклах методом имитации их выполнения // Кибернетика. 1981. - № 3. -С, 28-33.

68. Капитонова Ю.В., Летичевский A.A., Бублик В.В., Коляда C.B. Об алгоритме максимальной десеквенции бесповоротных циклических операторов // Кибернетика. 1983. - № 4. - С. 11

69. Петрова Г.Б. О распараллеливании циклов с регулярной информационной зависимостью операторов // Управление в сложных нелинейных системах. М.: Наука, 1984. - С. 60-63.

70. Тодоров Г.А. Анализ параллелизма вычислительных процессов в циклических программных структурах // Программирование. -1980.-№ 1.-С. 11-23.

71. Di Manzo, Frisiani A.L., Olimpo G. Loop Optimization for Parallel Processing // Comput. J. 1979. - Vol. 22, № 3. - P. 324-339.

72. Foulk P.W., Nassar S.M. Analysis of Parallelism in Nested DO Loops // J. Syst. and Software. 1985. - Vol. 5, № 1. - P. 73-80.

73. Вальковский В.А. Параллельное выполнение циклов. Метод параллелепипедов // Кибернетика. 1982. - № 2. - С. 51-62.

74. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 272.

75. Светозарова Г.И., Мельников A.A., Козловский A.B. Практикум по программированию на языке Бейсик: Учебное пособие для вузов М: Наука, Гл. ред. физ.-мат. лит., 1988. - 368 с.

76. Эберт К., Эдерер X. Компьютеры. Применение в химии: Пер. С нем. М.: Мир, 1988. - 416 с.

77. Дьяконов В.П. Справочник по программированию на языке Бейсик для персональных ЭВМ: Справочник. М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 240 с.

78. Берри Р.Я., Жабин И.А., Норкин С.Б. Элементы вычислительной математики М.: Высшая школа 1960. - 162 с.

79. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.- 318 с.

80. Ланкастер П. Теория матриц. М.: Наука, 1978. - 280 с.

81. Скорнуков Л.А. Системы линейных уравнений. М.: Наука, 1986.-64 с.

82. Боревич З.И. Определители и матрицы. М.: Наука, 1984. - 57 с.

83. Сидоров В.И., Ярославский Л.П. Адаптивные методы обработки изображений. М.: Наука, 1988. - 164 с.

84. Хуанг Т.С. быстрые алгоритмы в цифровой обработке изображений. М.: Радио и связь, 1984. - 216 с.

85. Гроппен В.О. Модели и алгоритмы минимизации стоимости решения некоторых задач на однородных многопроцессорных вычислительных системах // Автоматика и телемеханика. № 11, 1994, С. 136- 141.

86. Groppen V.O. Efficiency of parallel computations in solving extreme combinatorial problems. First World Conference on Parallel Computing in Engineering and engineering Education. UNESCO, Paris, France, 1990, p.127 131.

87. Фрэнк Хэйес. Distributed Component Object Model. COMPUTERWORLD, Россия, №24, 1999, стр. 30.

88. Фролов Ф.В., Фролов Г.В. Локальные сети персональных компьютеров. М.: «ДИАЛОГ-МИФИ», 1995. - 168 с.

89. Фролов Ф.В., Фролов Г.В. Локальные сети персональных компьютеров Использование протоколов IPX, SPX, NETBIOS. M.: «ДИАЛОГ-МИФИ», 1995. - 160 с.

90. Штольц К. Секреты сетей под Windows 95. Киев.: Диалектика, 1996.-480 с.

91. Флинт Д. Локальные сети ЭВМ: архитектура, принципы построения, реализация. М.: Финансы и статистика, 1986. - 359 с.

92. Ги К. Введение в локальные вычислительные сети. М.: Радио и связь, 1986. -176 с.

93. Sazegari S. Metropolitan Networking. Theory and Fractice // Data Communications. 1983, May. - p. 99-113.

94. Бойчевко E.B., Кальфа В., Овчинвиков В.В. Локальные вычислительные сети. М.: Радио и связь, 1985. - 304 с.

95. Thuiber К.Y., Freeman H.A. The Many Faces of Local Networking // Data communications. 1981, Dec. - p. 62-70.

96. Иванов В.В., Мячев А.А. Интерфейсы вычислительных систем на базе мини- и микроЭВМ. М.: Радио и связь, 1986. - 248 с.

97. ЮО.Страуструп Б. Язык программирования С++. Часть вторая. Пер. с англ. Киев: «ДиаСофт», 1993. - 296 с.

98. Гроппен В.О. Мирошников A.C. Модели управления системой оптимальной параллельной обработки информации в ЛВС СКГТУ // Труды Северо-Кавказского государственного технологического университета. Выпуск 7. Владикавказ, 2000.

99. Гроппен В.О. Специфика моделей поиска стратегии эффективного использования ресурсов локальных вычислительных сетей // Труды Северо-Кавказского государственного технологического университета. Выпуск 6. Владикавказ, 1999. - С. 249 - 253.

100. ЮЗ.Гроппен В. О. Мирошников A.C. Надежность параллельных вычислений // Сборник научных трудов аспирантов. СКГТУ. «Терек». Владикавказ, 2000.

101. Мирошников A.C. Оценка эффективности параллельной обработки вычислений при решении некоторых задач // Труды Северо-Кавказского государственного технологического университета. Выпуск 6. Владикавказ, 1999. - С. 230 - 235.

102. Мирошников A.C. Система оптимальной параллельной обработки информации СКГТУ // Труды Северо-Кавказского государственного технологического университета. Выпуск 7. Владикавказ, 2000.

103. Мирошников A.C. Система оптимальной параллельной обработки информации // Сборник научных трудов аспирантов. СКГТУ. «Терек». Владикавказ, 2000.