Горб Павел Евгеньевич |
Автобиография
Библиотека
Ссылки, отчет о поиске
Индивидуальное задание
СОДЕРЖАНИЕ
1. Постановка задачи
2. Часть Первая. Анализ задачи
3. Часть Первая. Программная реализация
4. Часть Вторая. Анализ задачи
5. Часть Вторая. Программная реализация
Заключение
Литература
ВВЕДЕНИЕ
Рассматривается технология решения больших систем линейных алгебраических уравнений вида:
Задача решения систем уравнений вида (1) достаточно распространена. Она возникает при описании нескольких процессов, каждый из которых описывается линейным уравнением. Сюда относится изучение процессов, протекающих в линейных электрических схемах, аппроксимация систем дифференциальных уравнений, в частности, описывающих процессы теплопроводности.
Известно, что при увеличении числа уравнений, входящих в систему, эффективность решения сильно снижается. При этом требуются значительные вычислительные ресурсы и время. Для сохранения эффективности необходимо решать подобные задачи с применением распараллеливания. Это позволяет сократить время, затрачиваемое на решение и снизить требования к составу вычислительных средств.
ПОСТАНОВКА ЗАДАЧИ
Первая часть магистерской работы состоит в том, чтобы получить программный проект, позволяющий решать СЛАУ методом простой итерации, изложенным выше, с применением многопоточных параллельных вычислений. Для этого применяется среда разработки Delphi7, а также библиотека классов Gala (Ссылка), позволяющая организовать параллельные вычисления.
Вторая часть магистерской работы заключается в создании распределенной вычислительной системы для решения СЛАУ итерационным методом. Разработка подобной программы также осуществляется с помощью Delphi7 с применением средств технологии COM (Component Object Model).
ЧАСТЬ ПЕРВАЯ. АНАЛИЗ ЗАДАЧИ
Предположим есть некоторый главный процесс. Он принимает исходные данные от пользователя. Далее главный процесс производит их предварительную обработку, преобразуя исходную систему вида (1) в систему вида (2), удобную для итерации. После этого главный процесс создает необходимое число процессов-рабочих, которые и будут решать систему, т.е. каждый процесс решает заданное число уравнений системы (2). Каждому процессу-рабочему пересылаются исходные данные от главного процесса. После чего главный процесс ждет ответы от рабочих. Каждый рабочий выполняет итерацию (или несколько итераций) над своей частью системы и пересылает результат главному процессу. Главный процесс, в свою очередь, ожидает, пока поступят ответы от всех рабочих, затем вычисляет точность решения этой итерации, с целью определения необходимости дальнейших вычислений. Если точность достигнута, то выводится результат, вычисления прекращаются. Если точность не достигнута, то полученные на данном шаге результаты становятся исходными данными для следующей итерации, процесс вычислений аналогично повторяется.
Описанная модель позволяет наглядно распараллелить вычисления при использовании метода простой итерации. Здесь применен принцип взаимодействия: «Управляющий-рабочие».
Реализация осуществляется с помощью библиотеки классов Gala (автор: С. Гурин, Томск) для среды Delphi. Она предназначена для программирования задач, требующих решения при наличии параллельных процессов и их взаимодействий. При этом, сохраняется удобство работы с параллельными процессами, почти такое же как и при работе со специальными средствами разработки для параллельных вычислений. Библиотека классов Gala распространяется свободно с исходными кодами. Ее можно скачать отсюда: http://gurin.tomsknet.ru/gala.html
ЧАСТЬ ПЕРВАЯ. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
На рисунке 2 представлена схема программного проекта, реализующего метод простой итерации решения СЛАУ. В модуле class_lib описаны необходимые структуры данных для организации взаимодействия между процессами. Как описано выше, взаимодействие между процессами осуществляется с помощью сообщений. В модуле func_lib1 представлены функции, реализующие метод простой итерации, а также функция вычисления ошибки. В модуле slau_2 описаны функции, реализующие действия главного процесса, действия процессов-производителей, их взаимодействие и контроль получения решения.
Здесь же описаны классы TProducer и TMainProcessor, которые являются потомками классов TProducer1 и TMainProcessor1 соответственно, описанных в модуле clas_lib. Класс TMainProcessor имеет виртуальную процедуру Execute, в которой описаны его действия. Т.о. после создания объекта класса TMainProcess происходит считывание данных с главной формы программы. За это отвечает процедура без параметров
procedure TMainProcessor.FillDataSet; После этого исходные данные преобразуются к виду, удобному для итерации, с помощью процедуры Matrix_To_Iterations
По окончании преобразований, выполняется создание необходимого числа процессов-рабочих. На данном этапе разработки деление исходной матрицы на блоки с последующим решением на одном процессе нескольких уравнений системы не выполняется. Процессов-рабочих создается столько же, сколько и уравнений в исходной системе.
Prod[i] := TProducer.Create(Group,nil);
После создания процессов формируются сообщения с исходными данными для текущей итерации и присходит отправка сообщений рабочим:
for i := 0 to N-1 dobegin
Messages[i].mA := copy(sA);
Messages[i].vb := copy(sb);
Messages[i].vXk := copy(sXk);
Messages[i].al := al;
Prod[i].Prod_Exch_Channel.Send(Self, Self.Messages[i], INFINITE);
end;
После отправки главный процесс ожидает ответы от рабочих. Это организовано функцией ожидания по каналу
Когда все рабочие отчитаются, производится анализ необходимости продолжения вычислений – Need_Next_Xk. Если данная функция возвращает True, то наращивается счетчик итераций, переприсваиваются исходные данные и процедура вычисления повторяется с момента формирования и отправки сообщений производителям. В функции Need_Next_Xk используется функция Simple_Error. Она возвращает максимальное значение ошибки на данном шаге. Если это значение превышает необходимую точность, то необходима следующая итерация и Need_Next_Xk возвращает True. Иначе – текущее приближение является результатом решения исходной системы и возвращается False.
Решение системы выводится в журнал обмена данными на главной форме.
Класс TProducer также имеет метод Execute. Но данный метод проще, нежели у главного процесса TMainProcessor. В методе Execute класса TProducer выполняется расчет следующей итерации для одного уравнения исходной системы, т. е. для одного Xi, где i совпадает с номером процесса-рабочего. Т.о. рабочий после создания ожидает поступления исходных данных от главного процесса. Это организовано аналогичным вышеприведенному методом
Далее вычисляется следующая итерация:
sNextXk := Simple_Iteration(rA, rb, rXk, N, number);и готовится сообщение для главного процесса:
Ready_Message.Next_Xk := sNextXk;
Готовое сообщение отсылается главному процессу:
После этого рабочий снова ждет данные для следующей итерации.
Также в модуле slau_2 предусмотрены процедуры для ввода данных из файла и для сохранения в файл введенных вручную в форму данных.
ЧАСТЬ ВТОРАЯ. АНАЛИЗ ЗАДАЧИ
Перевод модели «управляющий-рабочие» на язык COM подразумевает следующее. Управляющий процесс должен быть реализован как COM-клиент, рабочие процессы, выполняющие вычисления, реализуются как COM-серверы, предоставляющие свои услуги через интерфейсы. COM-клиент принимает исходную систему от пользователя, выполняет преобразование к виду, удобному для итерации, делит систему на блоки, рассылает части исходных данных COM-серверам, используя их интерфейсы. Когда ответ получен, клиент выполняет сборку результатов и анализ точности полученного решения. При достижении заданной точности процесс вычислений прекращается. Важно, что в данном случае COM-клиент реализуется как одиночное приложение, использующее услуги нескольких удаленных COM-серверов, что показано на рисунке 3.
Следует отметить, что при такой реализации решение отдельных блоков уравнений исходной системы осуществляется на разных хостах распределенной системы. Это позволяет производить вычисления параллельно и независимо.
ЧАСТЬ ВТОРАЯ. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
Программная реализация распределенной системы, представленной на рисунке 3, предполагает наличие двух программ. Одна из них отвечает за работу вычислительного сервера. Вторая – реализует функции клиента.
Приложение-клиент распределенной вычислительной системы распо-лагается на одном из хостов компьютерной сети и выполняет следующие функции:
- осуществление общения с пользователем;
- подготовка исходных данных к вычислительному процессу;
- распределение работы между независимыми вычислительными серверами;
- анализ результатов вычислений;
- формирование конечного результата и предоставление его пользователю.
Подготовка исходных данных к вычислительному процессу включает в себя выполнение процедуры подготовки исходной системы вида (1), к системе, удобной для итерации.
Распределение работы между вычислительными серверами осуществляется путем выполнения одной из двух процедур. Одна из них выполняет решение системы уравнений путем использования вычислительных серверов, в количестве, равном числу уравнений, входящих в систему. Вторая процедура предусматривает разбиение исходной системы на блоки по нескольку уравнений. Поэтому данная процедура использует вычислительные сервера в количестве, равном числу блоков, на которые разбивается исходная система. В каждой из двух вышеуказанных процедур осуществляется передача серверам части исходных данных, над которыми будут выполнены вычисления.
После получения результатов от серверов, выполняется проверка на точность полученного решения: (abs(Xk[i - 1] - Res[i])) < eps, где Xk – вектор неизвестных предыдущего шага, Res – вектор неизвестных текущего шага, eps – желаемая точность результатов. Если точность не достигнута, то принимается решение о продолжении вычислений. Если точность решения удовлетворяет значению, указанному пользователем, то процесс вычисления прекращается, а результат представляется пользователю, с указанием количества итераций и времени, затраченного на решение.
Реализуемая распределенная система предусматривает существование нескольких вычислительных серверов, располагающихся на различных хостах компьютерной сети. В функции сервера входят:
- прием данных от клиента;
- выполнение требуемой вычислительной процедуры;
- отправка результатов клиенту.
TCalcServer = class(TAutoObject, ICalcServer)
protected
function SingleIteration(A: OleVariant; Bi: Double; Xk: OleVariant; size: Integer): Double; safecall;
function BlockIteration(A, b, Xk: OleVariant; sz, num, blocksz: Integer): OleVariant; safecall;
end;
Рассмотрим функции, входящие в класс TCalcServer:
Первая функция:
function SingleIteration(A: OleVariant; Bi: Double; Xk: OleVariant; size: Integer): Double;
Функция возвращает значение Xi на данной итерации и имеет параметрами:
A – соответствующая строка матрицы коэффициентов;
Bi – соответствующее строке значение вектора свободных членов;
Xk – соответствующее строке значение вектора приближения предыдущего шага;
size - размер матрицы;
Вторая функция:
function BlockIteration(A, b, Xk: OleVariant; sz, num, blocksz: Integer): OleVariant;
Функция выполняет итерацию над блоком уравнений исходной системы и возвращает массив значений Xi на данной итерации. Имеет параметрами:
A – матрица коэффициентов;
b – вектор свободных членов;
Xk – вектор приближения предыдущего шага;
sz - размер матрицы;
num – номер уравнения, с которого начинается блок;
blocksz – размер блока (кол-во уравнений, входящих в блок).
Для взаимодействия с клиентом, COM-объект содержит интерфейсы. Интерфейсы ICalcServer, а также интерфейса диспетчеризации ICalcServerDisp, применяемого в технологии автоматизации для использования методов объекта, описаны в библиотеке типов server_prj_TLB.pas. С точки зрения клиента, работающего в среде Windows, сервер - это Automation Object (объект автоматизации), поэтому их взаимоотношения определяются правилами COM – технологии.
Библиотека типов включается в раздел Uses приложения-клиента, что-бы стало возможным использование методов объекта сервера с применением раннего связывания, что повышает быстродействие операций обмена.
ЗАКЛЮЧЕНИЕ
В результате проделанной работы, получены два программных проекта, решающих системы линейных алгебраических уравнений различными способами: с применением многопоточных параллельных вычислений и с применением вычислений в распределенной среде. Для организации решения используются итерационные методы. Решение осуществляется с заданной точностью. Имеются функции для сохранения и загрузки исходных данных, а также для сохранения полученных результатов.
В дальнейшем возможно увеличение числа функций, входящих в программы для получения дополнительных результатов либо для повышения эффективности вычислительных процедур. Предполагается сравнение результатов, полученных вышеописанными программами для определения достоинств и недостатков использования различных технологий программирования при организации подобных вычислений.
ЛИТЕРАТУРА
- Демидович Б. П., Марон И. А. Основы вычислительной математики. М.: Наука, 1966 Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ. – М.: Мир, 1991.
- Валях Е. Последовательно-параллельные вычисления. – М.: Мир, 1985.
- Реинжиниринговая технология распределенных вычислений в локальной сети.
-
DCOM технология : Статья с примерами реализации в Delphi. Copyright (c) 1997 by Charlie Calvert
http://homepages.borland.com/ccalvert/TechPapers/Delphi/DCOM.html