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

Введение

Глава I. Современные параллельные архитектуры, методы и 5 задачи, требующие большой вычислительной мощности.

§ 1. Параллельные архитектуры и распараллеливание 5 алгоритмов.

1.1. Архитектура - функциональная арифметика.

1.2. Другие виды параллельных архитектур.

1.3. Распараллеливание алгоритмов.

§ 2. Задача исследования эволюции осадочных бассейнов.

2.1. Описание задачи.

2.2. Постановка задачи.

2.3. Решение одномерной задачи.

2.4. Решение двумерной задачи.

§ 3. Выводы по главе I.

Глава П. Параллельные методы геометрической интерпретации 91 задач, основанные на степени отображения.

§ 1. Геометрические постановки задач и параллельность.

§ 2. Использование «степени отображения» для решения 93 систем линейных алгебраических задач.

2.1. Постановка задачи.

2.2. Теория.

2.3. Применение общей формулы.

2.4. Итерационный алгоритм.

2.5. Алгоритм с размножением.

2.6. Модификация алгоритмов.

§ 3. Выводы по главе П.

Глава Ш. Исследование метода, основанного на степени 107 отображения.

§ 1. Программный комплекс для исследования метода.

§ 2. Результаты исследования метода.

§ 3. Выводы по главе III.

Глава IV. Реализация метода степени отображения на 124 параллельных структурах.

§. Анализ параллельных реализаций метода.

§ 2. Архитектура вычислительной системы ТКС.

§ 3. Выводы по главе IV.

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

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

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

Разрабатываемый в рамках первого направления метод основан на применении дискретного преобразования Фурье (ДПФ) к разностной схеме дифференциального уравнения. Этот подход описан в научно-технической литературе применительно к численному решению эллиптического уравнения 2-го порядка с постоянными коэффициентами (уравнения Пуассона). Уравнения, описывающие рассматриваемые модели содержат переменные коэффициенты. В данной работе предлагается применить ДПФ для случая переменных коэффициентов, что ранее не делалось. Данный метод основан на использовании существующих алгоритмах быстрого преобразования Фурье (БПФ), которые, как известно, обладают параллелизмом.

В рамках второго направления исследования предлагается параллельный метод решения систем линейных алгебраических уравнений (СЛАУ), основанный на геометрической интерпретации задачи. Данный метод продолжает цикл идей, связанных с организацией параллельных структур и параллельных вычислений, изложенных в [1]. Эти идеи уходят своими корнями еще в методику создания многопроцессорной машины М-10 [2].

Развитие электронной базы - микроэлектроники и особенно наноэлектроники (квантовой электроники) - позволит сосредоточить в одном компьютере миллиарды процессоров, что потребует соответствующей широты параллелизма вычислений.

Становится актуальной задача пересмотра предметной области вычислений, т.е. создания принципиально новых вычислительных методов с учетом возможности их реализации на столь мощных параллельных структурах. В то же время архитектура самих многопроцессорных систем, организация взаимосвязи процессоров может быть в принципе выполнена самыми различными способами. Таким образом, при создании новых параллельных методов следует предусматривать возможность создания архитектуры многопроцессорной системы, адекватной предлагаемому 4 методу. Итак, новые параллельные вычислительные методы и архитектура многопроцессорных систем должны развиваться бок о бок, соответственно влияя друг на друга.

В основе предлагаемого здесь метода является переформулировка алгебраических задач в геометрических терминах. В свое время аналитическая геометрия была создана для решения геометрических задач с помощью алгебры. То, что предлагается здесь, является, по существу, чем-то обратным. Суть метода геометрической интерпретации состоит в применении к чисто вычислительным задачам методов современной геометрии. Эта интерпретация основана на использовании свойств степени симплициальных отображений [3, 4].

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

Работа, изначально направленная на повышение эффективности реализации модели эволюции осадочных бассейнов, по сути вышла за рамки этого исследования. Поскольку здесь предложен более общий и универсальный метод решения СЛАУ, основанный на геометрической интерпретации задачи, который обладает естественным параллелизмом.

§ 3. Выводы по главе IV.

В описываемом методе просматривается трехуровневый параллелизм: а) "Крупнозернистый" параллелизм. В «-мерном пространстве одновременно размещается и обрабатывается сразу к многогранников. Где к -количество параллельных ветвей алгоритма. б) "Среднезернистый" параллелизм. Распараллеливается обработка одного многогранника. При этом одновременно обрабатываются разные вершины многогранника. в) "Мелкозернистый" параллелизм. В данном случае распараллеливание осуществляется на уровне матричных операций.

При реализации на вычислительных МРР кластерах ТКС целесообразно реализовать вариант распараллеливания а). Для случая комбинированных МРР-8МР кластеров ТКС следует реализовать двухуровневую параллельную схему. На верхнем уровне осуществляется распараллеливание метода по варианту а), на нижнем уровне - по варианту б).

Заключение.

1. Показаны актуальность и сложность проблемы использования параллельных компьютеров в задачах моделирования.

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

Сложность заключается в проблематичности эффективного распараллеливания существующих алгоритмов и неадекватности методов решения архитектурам компьютеров.

2. В диссертации рассмотрено два аспекта решения указанной выше проблемы. Первый аспект связан с применением существующих распараллеливаемых алгоритмов, для разработки численного метода. К таким алгоритмам относится БПФ. Второй аспект включает создание нового метода, изначально обладающего естественным параллелизмом, и разработку алгоритмов на основе данного метода.

3. Разработан и исследован метод, основанный на преобразовании Фурье, который применен в работе для решения задачи исследования эволюции осадочных бассейнов. Эта задача сводится с системе уравнений Стокса с переменными коэффициентами. Для решения этой системы были использованы алгоритмы быстрого преобразования Фурье. В результате исследования метода установлена его эффективность.

4. В качестве самостоятельного параллельного метода в работе предложен метод для приближенного решения СЛАУ. Метод основан на геометрической интерпретации задачи решения СЛАУ. Алгоритмы, разработанные на основе данного метода, позволяют определить, содержится или нет решение внутри шара или выпуклого многогранника заданных в >1-мерном евклидовом пространстве.

5. Создан комплекс программ, с помощью которого были проведены исследования метода основанного на геометрической интерпретации задачи решения СЛАУ и алгоритмов, основанных на данном методе. В результате исследования была установлена их работоспособность.

6. Проведен анализ уровней параллелизма, которые обеспечивает метод геометрической интерпретации задачи решения СЛАУ.

1. Гливенко Е.В. Параллельный процессор первичной обработки информации. М.: Радио и связь, 1992. 105 с.

2. Гливенко Е.В. Функциональная арифметика (машина М-10) и современные проблемы первичной обработки. // Вопросы радиоэлектроники. Серия ЭВТ Вып. 2. 1993. с. 44-40.

3. Дубровин Б.А., Новиков С.П., Фоменко А.Т. Современная геометрия. М.: Наука. 1979. 760 с.

4. Александров П.С. Комбинаторная топология. М.-Л.: ОГИЗ. 1947. 660с.

5. Гливенко Е.В., Мухтарулин B.C., Петрова Г.Н. Математическое моделирование и архитектура компьютера., М.: Изд-во "Нефть и газ" РГУ нефти и газа им. И.М. Губкина. 2000. 86 с.

6. Брик В.А., Лушпин Л.И., Златников В.М., Петрова Г.Н. Многопроцессорное арифметичекое устройство. // Вопросы радиоэлектроники. Серия ЭВТ. Вып. 5, 1972, с. 23-28.

7. Новиков А.А., Кондратьев А.Ф. Техничекая база высокопроизводительных вычислительных комплексов и устройств обработки символов//Проблемы информатизации, 1-2,1997.

8. ПАРС. Параллельная система. Основные технические сведения: Отчет НИИ "Научный Центр" (г. Зеленоград), 1991.

9. Златников В.М., Петрова Г.Н. Вариант организации машины реляционной базы данных на вычислительной системе ПАРС//Вопросы радиоэлектроники. Серия ЭВТ. вып. 4, 1994.

10. ЗАО НТЦ «Модуль», l№://www.module. vvmpel.msk.ru. РОССИЯ 1998.

11. Дорохин С.А. Высокопроизводительные процессоры цифровой обработки сигналов 2000 года//Цифровая обработка сигнала, 1, 1999.

12. Наймарк Б.М., Исмаил-заде А.Т. Усовершенствованная модель погружения тяжелых тел в астеносфере // Вычислительная сейсмология. Вып. 27. Теор. Пробл. Геодинамики и сейсмологии. М.: Наука, 1994. с. 56 -69.

13. Исмаил-заде А.Т., Наймарк Б.М. и др. Реализация трехмерной гидродинамической модели эволюции осадочных бассейнов // Журнал вычислительной математики и математической физики. 1998. т. 38. № 7, с. 1190- 1203.

14. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.

15. Воеводин В.В., Тартышников Е.Е. Вычислительные процессы с теплицевыми матрицами. М.: Наука, 1987.

16. Алексеев Г.Г., Гливенко Е.В., Демьянов В.Д., Петрова Г.Н. Реализация гидродинамической модели эволюции осадочных бассейнов и выбор рациональной структуры многопроцессорной ЭВМ // Вопросы радиоэлектроники. Серия ЭВТ, 1999. Вып. 1. с. 8 -17.

17. Тартышников Е.Е. Теплицевы матрицы, некоторые их аналоги и приложения. М.: Изд-во АН СССР, 1989. 184 с.

18. Гливенко Е.В., Демьянов B.JI. О параллельных алгоритмах геометрической интепретации//Информационные технологии. 1999 г. № 3.

19. Гливенко Е.В., Демьянов B.JI. Параллельный метод геометрической интерпретации в интерактивном режиме//Вопросы радиоэлектроники. Серия ЭВТ, 1999. Вып. 1.

20. Демьянов B.JI. О параллельном алгоритме решения систем уравнений. Участие в конференции «Новые технологии». Республика Саха, г. Якутск. 10-13 апреля 2000 г. Тезисы доклада опубликованы.

21. Axelsson О. Lindskog G. On the rate of convergence of the preconditioned conjugate gradient method // Numerische Mathematik. 1986. Vol. 48, p. 499-523.

22. Serra S. The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems // Numerische Mathematik. 1999. Vol. 81, p. 461 -495.

23. Четверушкин Б.Н., Милюкова О.Ю. Параллельный метод решения систем линейных алгебраических уравнений // Журнал вычислительной математики и математической физики. 1998. т. 38. № 2. с. 228 238.

24. Podvigina О.М., Zheligovsky V.A. An optimized iterative method for numerical solution of large systems of equations based on the extremal property of zeros of Chebyshev polinomials // Journal of Scientific Computing, in Press.

25. Федоренко Р.П. Введение в вычислительную физику. М.: Изд-во МФТИ, 1994. 526 с.133

26. Пасконов В.М., Полежаев В.И., Чудов Л. А. Численное моделирование процессов тепло- и массообмена. М.: Наука, 1984. 372 с.

27. Уоссерман Ф. Нейрокомпьютерная техника. Теория и практика. М.: Мир, 1992 г.

28. Галушкин А.И., Судариков В.А. Адаптивные нейросетевые алгоритмы решения задач линейной алгебры. // Нейрокомпьютер. 1992 г. № 2. с. 21-28.

29. Судариков В.А. Исследование адаптивных нейросетевых алгоритмов решения задач линейной алгебры. // Нейрокомпьтер. 1992 г. № 3,4. с. 13 — 20.

30. Галушкин А.И., Судариков В.А., Шабанов Е.В. Нейроматематика -методы решения задач на нейрокомпьютерах. // Математическое моделирование. 1991 г. т. 3, № 8, с. 101-106.

31. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», 1999. 311 с.