способ оптимизации параллельной обработки информации для минимизации ее времени

Формула изобретения

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



где Т - время решения задачи;

S - максимальная стоимость решения задачи;

Р - количество PC в комплексе;

k - коэффициент пропорциональности;

а - стоимость одной PC;

b - стоимость коллективно используемых ресурсов: каналов связи (КС), общих устройств ввода информации (ОУВ), общих устройств памяти (ОУП) и общих устройств вывода информации (ОУВв);

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

d - время решения задачи одной PC.

Описание изобретения к патенту

Изобретение относится к вычислительной технике, в частности к системам параллельной обработки информации, и может быть использовано в локальных вычислительных сетях (ЛВС).

Известен способ функционирования объектной модели, включающий размещение на рабочих станциях сети серверных и клиентских компонентов (см. Френк Хэйес. Distributed Component Object Model. Computerworld, Россия, 24, 1999, с. 30).

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

Наиболее близким к заявленному способу является способ оптимального формирования визуального изображения, включающий определение оптимального числа процессоров, используемых для обработки визуальной информации (см. патент РФ 2045095, МПК 6 G 06 T 1/20, опубл. 27.09.95 г., БИ 27).

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

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

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

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



где Т - время решения задачи;

S - максимальная стоимость решения задачи;

Р - количество PC в комплексе;

k - коэффициент пропорциональности;

а - стоимость одной PC;

b - стоимость коллективно используемых ресурсов: каналов связи (КС), общих устройств ввода информации (ОУВ), общих устройств памяти (ОУП) и общих устройств вывода информации (ОУВв);

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

d - время решения задачи одной PC.

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

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

Аппаратно-программный комплекс (см. фиг.1) состоит из рабочих станции (PC₁), (PC₂),...(PC_n) - персональных компьютеров, каналов связи (КС) - проводные, беспроводные и оптические каналы связи, которые обеспечивают передачу цифровой информации между рабочими станциями (PC₁), (PC₂),...(PC_n), а также общими устройствами ввода информации (ОУВ), общими устройствами памяти (ОУП) и общими устройствами вывода информации (ОУВв).

Рабочие станции (РС₁), (РС₂), . ..(РС_n), входящие в состав комплекса, состоят из следующих устройств (см. фиг.2): блока управления (БУ) - один или несколько центральных процессоров, контролеры памяти, магнитных дисков, устройств ввода/вывода и т.п.; запоминающих устройств (ЗУ), постоянно запоминающих устройств (ПЗУ), оперативно запоминающих устройств (ОЗУ), накопителей информации на магнитных дисках и лентах, на оптических дисках и т.п.; устройств ввода информации (УВ); устройств вывода информации (УВв); устройства подключения и передачи информации по КС (УПКС).

К общим устройствам комплекса по КС имеют неограниченный доступ все PC.

PC соединяют между собой КС по типу: "кольцо", "звезда", "общая шина", "матрица" и т.п.

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

Пример конкретного выполнения способа.

При решении отдельной задачи, например вычисления определенного интеграла, в вычислительном комплексе из всех PC выбирается одна главная PC (ГРС), которая будет отвечать за решение задачи в целом. На остальных, удаленных рабочих станциях (УРС) в ходе решения задачи выполняются параллельные процессы.

ГРС выполняет следующие действия:

1. С помощью устройств УВ в ЗУ вводятся исходные данные задачи и информация об оптимизации: минимизации времени решения задачи.

2. БУ ГРС анализирует введенную и хранящуюся в ЗУ исходную информацию, разбивает решение задачи на отдельные вычислительные процессы и начинает решение задачи. Исходные данные, которые будут использоваться несколькими параллельными процессами, сохраняются БУ в ОУП. При разбиении задачи используется информация о распараллеливании вычислений. БУ первоначально создает число параллельных процессов, удовлетворяющее условиям:



где Т - время решения задачи;

S - максимальная стоимость решения задачи;

Р - количество PC в комплексе;

k - коэффициент пропорциональности;

а - стоимость одной PC;

b - стоимость коллективно используемых ресурсов: каналов связи (КС), общих устройств ввода информации (ОУВ), общих устройств памяти (ОУП) и общих устройств вывода информации (ОУВв);

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

d - время решения задачи одной PC.

Так, при следующих значениях: Р=10; k=0,001; а=700; b=1000; с=1; d=30, S= 31,5, оптимальное число параллельных процессов составляет 8, а время решения задачи Т равно 4,75, что в 6,53 раза меньше, чем при однопроцессной обработке.

3. Выполнение каждого параллельного процесса протекает по следующей схеме:

- БУ ГРС выбирает наименее загруженную УРС в плане использования процессорного времени выполняющимися на ней задачами;

- с помощью УПКС через КС БУ передает выбранной УРС исходные данные параллельного процесса и сигнал "выполнить";

- БУ ГРС переходит в состояние приема через КС и УПКС сигнала "выполнено" от выбранной УРС;

- получив сигнал "выполнено", БУ ГРС принимает через КС и УПКС результирующую информацию или считывает ее с ОУП и сохраняет полученные данные в ЗУ.

4. После получения от всех УРС результатов ГРС обрабатывает их и выводит на УВв или ОУВв. На этом решение задачи закончено.

Работа УРС при получении сигнала "выполнить" заключается в следующем:

- через КС и УПКС от ГРС принимается входная информация для параллельного процесса и сохраняется БУ в ЗУ;

- БУ УРС анализирует принятую информацию и при необходимости загружает в ЗУ дополнительную информацию с УВ, ОУВ или ОУП;

- после определения всей исходной информации, необходимой для начала решения, БУ УРС переходит к решению задачи;

- в ходе решения промежуточные результаты выводятся БУ на УВв, ОУВв, ОУП или передаются ГРС. Дополнительные исходные данные БУ загружает в ЗУ с УВ, ОУВ или ОУП;

- после решения задачи в целом БУ УРС, подготовив в ЗУ результирующую информацию, посылает ее в месте с сигналом "выполнено" на ГРС.

Каждая PC, входящая в состав комплекса, выполняет дополнительные действия:

- БУ через определенные кванты времени посылает другим PC сигнал "проверка" и в течение определенного времени ожидает ответный сигнал "проверка" от каждой PC;

- если сигнал "проверка" не поступает в БУ с УРС, то БУ инициирует сигнал "ошибка" с данной УРС;

- если БУ по каким-либо причинам не может выполнить задачу или параллельный процесс, то всем PC рассылается сигнал "ошибка";

- если сигнал "ошибка" получен от PC, которая является ГРС по отношению к выполняемым БУ параллельным процессам, то соответствующие задачи снимаются БУ с решения;

- если сигнал "ошибка" получен ГРС от УРС, на которой выполнялись параллельные процессы, то БУ передает исходную информацию потерянных процессов и сигнал "выполнить" другим PC;

- при потере параллельных процессов БУ ГРС может пересмотреть план их распараллеливания для достижения минимального времени решения задачи.

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