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

СПОСОБ ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ МИНИМИЗАЦИИ ЕЕ СТОИМОСТИ Патент Российской Федерации
Суть изобретения:	Изобретение относится к системам параллельной обработки информации. Его использование в локальных вычислительных сетях позволяет получить технический результат в виде оптимального использования ресурсов локальной вычислительной сети. Способ предназначен для использования в локальных вычислительных сетях, содержащих рабочие станции, среди которых имеется одна главная рабочая станция и удаленные рабочие станции, между которыми главная рабочая станция распределяет отдельные вычислительные процессы, на которые разбивают решаемую задачу, включающий в себя определение оптимального количества параллельно выполняемых на рабочих станциях процессов обработки информации. Технический результат достигается благодаря тому, что распределение отдельных вычислительных процессов осуществляют на удаленные рабочие станции с наименьшей загрузкой в плане использования процессорного времени выполняющимися на них задачами, а определение оптимального количества (Х_опт) параллельно выполняемых процессов осуществляют на главной рабочей станции согласно заранее заданным условиям. 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) состоит из рабочих станции (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; - при потере параллельных процессов БУ ГРС может пересмотреть план их распараллеливания для достижения минимальной стоимости решения задачи. Использование предложенного способа позволит, по сравнению с прототипом, снизить стоимость параллельной обработки информации при решении выбранной задачи, а также повысить быстродействие даже при использовании локальной вычислительной сети с более "слабыми", но дешевыми рабочими станциями.
Формула изобретения:	Способ минимизации стоимости параллельной обработки информации, предназначенный для использования в локальных вычислительных сетях, содержащих рабочие станции, среди которых имеется одна главная рабочая станция и удаленные рабочие станции, между которыми главная рабочая станция распределяет отдельные вычислительные процессы, на которые разбивают решаемую задачу, включающий в себя определение оптимального количества параллельно выполняемых на рабочих станциях процессов обработки информации, отличающийся тем, что распределение отдельных вычислительных процессов осуществляют на удаленные рабочие станции с наименьшей загрузкой в плане использования процессорного времени выполняющимися на них задачами, а определение оптимального количества (Х_опт) параллельно выполняемых процессов осуществляют на главной рабочей станции согласно условиям: где f представляет собой целую часть от исходя из условий оптимизации: где S - стоимость решения задачи; Р - количество рабочих станций в комплексе; k - коэффициент пропорциональности; а - стоимость одной рабочей станции; b - стоимость коллективно используемых ресурсов: каналов связи, общих устройств ввода информации, общих устройств памяти и общих устройств вывода информации; с - время, затрачиваемое на подготовку вычислений; d - время решения задачи одной рабочей станции.