автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Параллельно-поточная интерпретация решения интегральных уравнений Фредгольма второго рода

РГ6 од

П .1 шли <ПП0 ЕРЕВАНСКИЙ ФИЗИЧЕСКИЙ ИНСТИТУТ

2 Й 1110II 1993

На правах рукописи МХИТАРЯН МАРИНЕ АКОПОВНА

ПАРАЛЛЕЛЬНО-ПОТОЧНАЯ ИНТЕРПРЕТАЦИЯ РЕШЕНИЯ ИНТЕГРАЛЬНЫХ •• УРАВНЕНИЙ ФРЕДГОЛЬМА ВТОРОГО РОДА

Специальность: 05.13.16

Применение вычислительной техники, ' математического моделирования и математических методов в научных исследованиях.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических><йаук

ЕРЕВАН - 1993

яогэеш ■

■Ai

Работа выполнена в Ереванском Физическом Институте

Научный руководитель; член-корреспондент АН РА,

доктор физико-математических наук НЕРСЕСЯН А. Б.

Официальные оппоненты: доктор физико-математических "наук

ПОГОСЯН Э. М.. <ИПИА АН РА)

кандидат физико-математических наук БДДАЛЯН С. Г. (ЕрФИ)

"Ведущая организация: ВЦ СО АН России

/цОО Защита состоится

1993г. в

'^_£~часов на заседании спещализированного совета К 034.03.01. при Ереванском Физическом Институте (375036, г. Ереван, ул. Братьев Алиханянсв, д. 2).

С диссертацией можно ознакомиться в библиотеке Ереванского Физического Института.

Автореферат разослан с1993 г.

Ученый секретарь специализированного совета, кандагат физико-математических -наук

ОБЦАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность темы.В последние года стремительно развивается вычислительная физика /computational phvaics/. Вбирая В арсенал расчетного инструментария суперЭВМ и другие коммуникационно-вычислительные структуры, разработанные на принципах параллельной обработки данных.

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

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

На сегодняшний день для решения задач вычислительной физики, требующих большого объема вычислений, разработано достаточно много параллельных вычислительных систем: мультипроцессор pax. спецпроцессор dap, система moses. ориентированная на решение систем нелинейных дифференциальных уравнений и предназначенная для решеточных моделей в теоретической физике, gf и и т. д.

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

В работ© гп были предложены новые алгоритмы численного решния интегральных уравнений Фредгольма второго рода, в частности, выделен особый класс уравнений с ядрами теплицэва типа. Реализация предложенных алгоритмов была осуществлена на последовтельной ЭВМ с одним потоком команд и одним потоком данных Г21, причем сами алгоритмы были изначально

распараллелены.

Немалая операционная сложность этих алгоритмов - порядка , octf)(n - исходный размер задачи) - диктует необходимость разработки параллельных вычислительных структур, на которых за достаточно приемлемое время становится возможным и реальным осуществление вычислений. В частности, ' ' реализуемость вычислителей на СБИС /VLSI - Very Large Scale Integration/ дает возможность повысить скорость обработки данных на несколько порядков. Данная тематика активно разрабатывается в научной литературе [31.

Целью настоящей диссертационной работы является разработка алгоритмов численного решения интегральных уравнений Фредгольма второго рода, в том числе с ядрами теплицэва типа, в ' смысле параллельно-поточной интерпретации на

коммуникационно-вычислительных структурах на базе СБИС с оптимальными характеристиками реализации.

Были поставлены следующие задачи: параллельно-поточная интерпретация четырех алгоритмов факторизации интегрального оператора второго рода*(с операционной сложностью ' порядка otN3)) на систолических ■ структурах из otN2) процессоров с временем реализации. 0(Ю и достижением максимального коэффициента эффективности в случае алгоритма : самой высокой точности огь*) относительно других трех! -'•

-"параллельно-поточная интерпретация деух алгоритмов решения интегрального уравнения Фредгольма второго рода, с ядром теплицэва типа (операционная сложность которых - порядка о(Л)на систолических массивах из cxn) вычислителей с временем реализации порядка orm и достижением" коэффициентов эффективности, сравнимых с таковыми первой группы алгоритмов. ■ ' " Научная новизна работы. '

I. Представлены четыре вычислительные .сети • из cxn2) процессоров ~'с необходимой коммуникацией для параллельно-поточной реализации соответственно четырех алгоритмов факторизации интегрального оператора второго ра^^разяичноа/лхяносгги<••..(00»); ''0(h;oih*)) с ' вроменем ' интерпретации' порядка осю ва предложенных

структурах. В случае алгоритма точности огь*) . получен самый высокий коэффициент эффективности относительно предыдущих трех (к^йо.23).

2. Преджлюны две систолические структуры из скю вычислетелэа для паралаально-поточноа интерпретации двух алгоритмов решения интегрального уравнения второго рода с ядром теплицэва типа (точности о(ы. ооЛ) с временем реализации на представленных сетях порядка олп. Коэффициент эффективности алгоритма точности

ООО

s

г - а * 4 m + 4

при ю=1 (m-шстоянная) равен 0,45 , что превосходит значения ' ссгатветствукшр« величины других исследуемых в работе алгоритмов почти вдвое, а при m-*® k^+l

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

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

Апробация работы. Результаты работа, положенные в основу диссертации, докладывались на семинарах го теоретическое физике, ш автоматизации научных исследований и вычислительной техники ЕрФИ, на I-оа Всесоюзной конференции по однородным вычислительным средам и систолическим структурам (Львов - 1990).

Публикации. По материалам диссертации опубликовано. три работа Г4 - 61.

Объем работа. Диссертационная работа состоит, из введения, трех глав, заключения, списка литературы, содервиг 88 дачаггных страниц машинописного текста, в&аочая 18 рисунков и 2 тайлвд.

Содрщашю работы. Во введении дана обцая характеристика диссертации, обзор ее структуры и результатов работа.

В I главе даны постановки двух тфиыидшх задач, сводом* ж интегральным уравнениям. Первая из них - задача диЦиншп

электромагнитных волн на идеально проводадэй полосе, являющейся одной из основных моделей теории дифракции электромагнита волн.' Вторая - контактная, задача для сдвигового винклэровского основания, усиленного покрытием. Далее, в X главе, приведена классификация вычислительных структур по принципу того, как машинные команда увязываются с обрабатываемыми данными; вводятся основные понятия и определения из области параллельных вычислений; временной шаг работа вычислительной структуры, операционная сложность данного алгоритма: приводится также перечень матричных алгоритмов, поддающихся отображению на локально связные массивы на СБИС.

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

Во 2 главе параллельно-поточно интерпретированы четыре алгоритма различной точности (порядка 0(Ы. ось2). o(h4» приближенной треугольной факторизации интегрального оператора второго рода.

В частности, структура одного из алгоритмов точности от2) вычислэния Rfi.i.m-1) такова (пусть ш. .1, n)d='

d=fRfii+ )h, \ )h. nh). i. .1 n e Z): •

/входные данные.(начальное присваивание)/

for О < i. j < N-l do

/внутренние вычисления/

for О < n < N-2 do

for 1 < i. A < H-l do (i, i > n+11

Efi..1.n+lV-Kl.j,nl+ Rfbn.n) Rfn..1.n) . ш

-jj-- R(n.n.n)

/выходные вычислгаия (финальное присваивание)/

for 1 £ та S H-l do

begin

forli i, JS H do (i, Л > n) begin a. =RCi,n.nh (i ,=R(n,d.n) end

in ft J

end:

С вводом коэффициента <*"= , гда

, _ _ "

<»n= —i- -Efn.n.n), формула (I) запишется в вида

R(i,d,n+l)=R(iJ.nHa"R(n,J,nl (2).

Опэрационная сложность данного алгоритма о=-д— -ихн** а время последовательной его интерпретации на последовательное ЭВМ с одаим потоком данных совпадает с его огарационноа сложность» т,=а

Параллельно-поточная интерпретация данного алгоритма осущэствляется на систолической структуре из N* процессорных элементов (Рис. 1а). Дяя управления обработки данных введены булевы пэременные а. р. г: ч, г - внутренние регистры (l.dboro вычислэтеля (Рис. 16). В начальные момент времени г=ш.&охПроцэссорные злэменты, расположенные на главной диагонали ортогонального систолического массива, имеют регистр локальной памяти для запоминания Пэ реме иная г служит для изменения режима работы каждого продассорного элемента в зависимости от стадии обработки задача. Предполагается, что в Исходно» состоянии r=L Значения на вход» ячевки полечены меткой in, на выхода - out. Цунктараые линии - управление, спет—w -даянке. в течвниэ всего вычислительного продесса подается

б)

ч ч

êu

ас-

I -Lut

/

X

1 о

О

О «

« " *

•О

X

• о

X

О

а)

Л

и

4 о

• X •

• * • X X X

О О

\ I

О

m

X • X X-->

\ i ML

X

М--* (р)

(2,0)^ M

J

I

X.

(0 ZX W zzZ (P)

\ i <1

il

-ZZ fat)

Рис.

детерминированный поток нулей и единиц. Программа работы (i..D-ого вычислителя такова:

if r-l then

beein

if w =1 then begin q= -r- -r: end: m n

else

begin q=q *: b ,=q; ct -a. ; ft -ft. ; y=.0- q=0 end:

out out in oul in

if a -о then begin a =1; y=0: q=rb. : a =q; q=0 end:

m out in out ^

if /?. =0 then begin ft =1: y-0: b =r end;

in oul * out

if a. -f). =1 then begin а =а. : b =b. ; a -a • ft ,-ft. i

in in out in oul in out in out in

q=r+a b. ; r=q: q=0; Г-1 end

in in

end

else

begin a -a x ft ,-ft. : w =w ; r-0 end:

out in out in out in

Управление обработки данных обеспечивает независимость данной вычислительной структуры от размера решаемой задачи. Время параллельно-поточной интерпретации данного алгоритма на систолическом массиве из л2 ортогонально связанных процессоров равно т^г=4Н-з. а коэффициент эффективности кг<р= У2'

В третьей главе, рассмотрены два алгоритма (точности сш и опЛ) решения интегрального уравнения Фредгольма второго рода с ядром теплицэва типа, удовлетворяющим уравнению

В частности, второй алгоритм точности схь4) предназначен для решения интегрального уравнения с разностным ядром

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

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

1 цепь - ФIЧ,п+11: О^Сын-П «¿к£т);

2 цвпь - $^1.11+11 (ио'й

Л цепь - ^П.п+П (1>0);

4 цепь - у(1.п+1); PJi.ru-!) (1<к<т); уП.п+и

Для алгоритмов представлены и описаны типы и функции

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

В заключении резюмируются основные результаты работы: I. Проведена параллельно-поточная интерпретация алгоритма треугольной факторизации интегрального оператора второго • рода точности ооо с операционной сложностью порядка осы") на систолической структуре из ы*+2М процессоров с временем реализации порядка ооп.

2. Для двух алгоритмов (точности огь2)) треугольного разложения интегрального оператора второго рода с операционной сложность^ порядка <хм3 > предложены коммуникационно-вычислительные структуры из схыу2 процессоров с временем реализации порядка сит Практически одинаковые коэффициенты эффективности (-^2«

получены при ошрационной сложности одного алгоритма вдвое большей соответствующей величины другого алгоритма.

3. Параллэльно-поточно интерпретирован подобный алгоритм точности от4) на систолическом массиве из вы числителей с временем реализации порядка сш.В этом случае получен самый высокий коэффициент эффективности (кафго.23)(и, вообще, все параметры предложенного варианта реализации максимальны) относительно таковых величин интерпретации алгоритмов факторизации интегрального оператора второго рода.

4..Алгоритм решения интегрального уравнения Фредгольма второго рода с ядром теплицзва типа (точности осы и с операционной сложностью от2» интерпретирован

параллельно-поточно на цилиндрическом систолическом массиве из 4И+2 процессорных элементов с временем реализации порядка ст.- -Данный алгоритм имеет самый высокий коэффициент эффективности ■

5

К = т + 4Л эф Е1 + 4

по сравнению с подобными величинами исследуемых в работе алгоритмов, при т=1 кэ<р^о.45, а при ¡п+®

5. Реализация алгоритма решения интегрального уравнения второго рода с разностным ядром (точности ооЛ и с ошрационной сложностью порядка огы3» осуществлена на систолической структуре из 4И+1 фуннциойальных устройство временем реализации огти коэффициентом эффективности, практически равным таковому алгоритма одинаковой точности факторизации интегрального оператора.

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

7.Техническая реализация представленных вычислительных структур на базе СБИС делает возможным их использование для быстрого счета прикладных, в частности, физических задач, сводимых к интегральгым уравнениям Фредгольма второго рода.

.ЛИТЕРАТУРА

1. Нерсесян А. Б. Новые алгоритмы численного решения интегральных уравнений второго рода. ДАН Арм. ССР., 1989, т. 89, N 4, с. 174-176.

2. ГариЗян А. Б., Нерсесян А. Б. Численное решение интегральных уравнений Фредгольма второго рода с разностным ядром. Ереван, 1990, деп. в АрмНИИНТИ 08. 01. 90, N 1-Ар. 90, 20 с.

3. Кун С. Матричные процессоры на СБИС. Москва, Мир, 1991.

4. Мхитарян М. А., Нерсесян А. Б. Параллельно-поточная интерпретация некоторых алгоритмов треугольного. разложения интегральных операторов второго рода. Препринт ЕФЙ-1224(10)-90, 1989 , 21с. Сб: Тезисы I Всесоюзной конференции "Однородные вычислительные среда и систолические структуры", Львов, 1990, т. I, с. 101-104.

5. Мхитарян М. А. Параллельно-поточная интерпретация двух алгоритмов решения интегрального уравнения Фредгольма второго рода с ядром теплицева типа. Ереван, 1992, деп. в АрмНИИНТИ 27. 07. 92, N 25-Ар. 92, 52 с.

6. Мхитарян М. А. Параллельно-поточная интерпретация алгоритма решения интегрального уравнения Фредгольма второго рода с ядром теплицева типа. Доклада АН Армении, 1992, т. 94 (в печати).