СПОСОБ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ МИНИМИЗАЦИИ ЕЕ СТОИМОСТИ Российский патент 2002 года по МПК G06F17/00 

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

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

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

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

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

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

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

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

где f представляет собой целую часть от исходя из условий оптимизации:

где S - стоимость решения задачи;
Р - количество PC в комплексе;
k - коэффициент пропорциональности;
а - стоимость одной PC;
b - стоимость коллективно используемых ресурсов: каналов связи (КС), общих устройств ввода информации (ОУВ), общих устройств памяти (ОУП) и общих устройств вывода информации (ОУВв);
с - время, затрачиваемое на подготовку вычислений;
d - время решения задачи одной PC.

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

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

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

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

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

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

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

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

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

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

где f представляет собой целую часть от исходя из условий оптимизации:

где S - стоимость решения задачи;
Р - количество PC в комплексе;
k - коэффициент пропорциональности;
а - стоимость одной PC;
b - стоимость коллективно используемых ресурсов: КС, ОУВ, ОУП и ОУВв;
с - время затрачиваемое на подготовку вычислений;
d - время решения задачи одной PC.

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

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

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

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

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

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

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

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

где f представляет собой целую часть от исходя из условий оптимизации:

где S - стоимость решения задачи;
Р - количество рабочих станций в комплексе;
k - коэффициент пропорциональности;
а - стоимость одной рабочей станции;
b - стоимость коллективно используемых ресурсов: каналов связи, общих устройств ввода информации, общих устройств памяти и общих устройств вывода информации;
с - время, затрачиваемое на подготовку вычислений;
d - время решения задачи одной рабочей станции.