Главная страница  |  Описание сайта  |  Контакты
СПОСОБ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ МИНИМИЗАЦИИ ЕЕ СТОИМОСТИ
СПОСОБ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ МИНИМИЗАЦИИ ЕЕ СТОИМОСТИ

СПОСОБ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ МИНИМИЗАЦИИ ЕЕ СТОИМОСТИ

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2191424
Класс(ы) патента: G06F17/00
Номер заявки: 2000108256/09
Дата подачи заявки: 03.04.2000
Дата публикации: 20.10.2002
Заявитель(и): Северо-Кавказский региональный центр информатизации высшей школы; Северо-Кавказский государственный технологический университет
Автор(ы): Гроппен В.О.; Мирошников А.С.
Патентообладатель(и): Северо-Кавказский региональный центр информатизации высшей школы
Описание изобретения: Изобретение относится к вычислительной технике, в частности к системам параллельной обработки информации, и может быть использовано в локальных вычислительных сетях (ЛВС).
Известен способ функционирования объектной модели, включающий размещение на рабочих станциях сети серверных и клиентских компонентов (см. Френк Хэйес. 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) состоит из рабочих станции (PC1), (PC2),...(PCn) - персональных компьютеров, каналов связи (КС) - проводные, беспроводные и оптические каналы связи, которые обеспечивают передачу цифровой информации между рабочими станциями (PC1), (РС2),...(РСn), а также общими устройствами ввода информации (ОУВ), общими устройствами памяти (ОУП) и общими устройствами вывода информации (ОУВв).
Рабочие станции (PC1), (РС2), . ..(РС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;
- при потере параллельных процессов БУ ГРС может пересмотреть план их распараллеливания для достижения минимальной стоимости решения задачи.
Использование предложенного способа позволит, по сравнению с прототипом, снизить стоимость параллельной обработки информации при решении выбранной задачи, а также повысить быстродействие даже при использовании локальной вычислительной сети с более "слабыми", но дешевыми рабочими станциями.
Формула изобретения: Способ минимизации стоимости параллельной обработки информации, предназначенный для использования в локальных вычислительных сетях, содержащих рабочие станции, среди которых имеется одна главная рабочая станция и удаленные рабочие станции, между которыми главная рабочая станция распределяет отдельные вычислительные процессы, на которые разбивают решаемую задачу, включающий в себя определение оптимального количества параллельно выполняемых на рабочих станциях процессов обработки информации, отличающийся тем, что распределение отдельных вычислительных процессов осуществляют на удаленные рабочие станции с наименьшей загрузкой в плане использования процессорного времени выполняющимися на них задачами, а определение оптимального количества (Хопт) параллельно выполняемых процессов осуществляют на главной рабочей станции согласно условиям:

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

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