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

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

Розглянуто паралельні алгоритми прямих методів дослідження і розв’язування задач лінійної алгебри з розрідженими симетричними матрицями нерегулярної структури. Досліджено ефективність даних алгоритмів, отримано оцінки зверху коефіцієнтів прискорення і ефективності паралельного алгоритму трикутного р...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Кибернетика и системный анализ
Datum:2011
Hauptverfasser: Химич, А.Н., Попов, А.В., Полянко, В.В.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Schlagworte:
Программно-технические комплексы
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/84261
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры / А.Н. Химич, А.В. Попов, В.В. Полянко // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 159-174. — Бібліогр.: 18 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-84261
record_format dspace
spelling Химич, А.Н.
Попов, А.В.
Полянко, В.В.
2015-07-04T14:52:37Z
2015-07-04T14:52:37Z
2011
Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры / А.Н. Химич, А.В. Попов, В.В. Полянко // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 159-174. — Бібліогр.: 18 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/84261
519.6
Розглянуто паралельні алгоритми прямих методів дослідження і розв’язування задач лінійної алгебри з розрідженими симетричними матрицями нерегулярної структури. Досліджено ефективність даних алгоритмів, отримано оцінки зверху коефіцієнтів прискорення і ефективності паралельного алгоритму трикутного розвинення розрідженої матриці. Наведено деякі результати чисельних експериментів на MIMD-комп’ютері.
Parallel algorithms for direct methods of the analysis and solution of linear algebra problems with sparse symmetric matrices of irregular structure are considered. The performance of the algorithms is investigated. The upper estimates of the coefficients of acceleration and efficiency of the parallel algorithm for the triangular decomposition of sparse matrices are obtained. Some results of numerical experiments carried out on a MIMD-computer are given.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Программно-технические комплексы
Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
Алгоритми паралельних обчислень для задач лінійної алгебри з матрицями нерегулярної структури
Algorithms of parallel computations for linear algebra problems with matrices of irregular structure
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
spellingShingle Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
Химич, А.Н.
Попов, А.В.
Полянко, В.В.
Программно-технические комплексы
title_short Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
title_full Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
title_fullStr Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
title_full_unstemmed Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
title_sort алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры
author Химич, А.Н.
Попов, А.В.
Полянко, В.В.
author_facet Химич, А.Н.
Попов, А.В.
Полянко, В.В.
topic Программно-технические комплексы
topic_facet Программно-технические комплексы
publishDate 2011
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Алгоритми паралельних обчислень для задач лінійної алгебри з матрицями нерегулярної структури
Algorithms of parallel computations for linear algebra problems with matrices of irregular structure
description Розглянуто паралельні алгоритми прямих методів дослідження і розв’язування задач лінійної алгебри з розрідженими симетричними матрицями нерегулярної структури. Досліджено ефективність даних алгоритмів, отримано оцінки зверху коефіцієнтів прискорення і ефективності паралельного алгоритму трикутного розвинення розрідженої матриці. Наведено деякі результати чисельних експериментів на MIMD-комп’ютері. Parallel algorithms for direct methods of the analysis and solution of linear algebra problems with sparse symmetric matrices of irregular structure are considered. The performance of the algorithms is investigated. The upper estimates of the coefficients of acceleration and efficiency of the parallel algorithm for the triangular decomposition of sparse matrices are obtained. Some results of numerical experiments carried out on a MIMD-computer are given.
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/84261
citation_txt Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры / А.Н. Химич, А.В. Попов, В.В. Полянко // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 159-174. — Бібліогр.: 18 назв. — рос.
work_keys_str_mv AT himičan algoritmyparallelʹnyhvyčisleniidlâzadačlineinoialgebrysmatricamineregulârnoistruktury
AT popovav algoritmyparallelʹnyhvyčisleniidlâzadačlineinoialgebrysmatricamineregulârnoistruktury
AT polânkovv algoritmyparallelʹnyhvyčisleniidlâzadačlineinoialgebrysmatricamineregulârnoistruktury
AT himičan algoritmiparalelʹnihobčislenʹdlâzadačlíníinoíalgebrizmatricâmineregulârnoístrukturi
AT popovav algoritmiparalelʹnihobčislenʹdlâzadačlíníinoíalgebrizmatricâmineregulârnoístrukturi
AT polânkovv algoritmiparalelʹnihobčislenʹdlâzadačlíníinoíalgebrizmatricâmineregulârnoístrukturi
AT himičan algorithmsofparallelcomputationsforlinearalgebraproblemswithmatricesofirregularstructure
AT popovav algorithmsofparallelcomputationsforlinearalgebraproblemswithmatricesofirregularstructure
AT polânkovv algorithmsofparallelcomputationsforlinearalgebraproblemswithmatricesofirregularstructure
first_indexed 2025-11-26T04:34:34Z
last_indexed 2025-11-26T04:34:34Z
_version_ 1850611948153995264
fulltext ÓÄÊ 519.6 À.Í. ÕÈÌÈ×, À.Â. ÏÎÏÎÂ, Â.Â. ÏÎËßÍÊÎ ÀËÃÎÐÈÒÌÛ ÏÀÐÀËËÅËÜÍÛÕ ÂÛ×ÈÑËÅÍÈÉ ÄËß ÇÀÄÀ× ËÈÍÅÉÍÎÉ ÀËÃÅÁÐÛ Ñ ÌÀÒÐÈÖÀÌÈ ÍÅÐÅÃÓËßÐÍÎÉ ÑÒÐÓÊÒÓÐÛ Êëþ÷åâûå ñëîâà: ëèíåéíàÿ àëãåáðà, ðàçðåæåííûå ñèììåòðè÷íûå ìàòðèöû, ïàðàëëåëüíûå àëãîðèòìû, ýôôåêòèâíîñòü. ÂÂÅÄÅÍÈÅ Ïðè ÷èñëåííîì ðåøåíèè íàó÷íî-òåõíè÷åñêèõ çàäà÷ ÷àñòî âîçíèêàåò íåîáõîäè- ìîñòü â ðåøåíèè çàäà÷è (èëè íåñêîëüêèõ çàäà÷) ëèíåéíîé àëãåáðû — ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé (ÑËÀÓ) èëè ÷àñòè÷íîé â îáùåì ñëó÷àå îáîáùåííîé àëãåáðàè÷åñêîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé (ÀÏÑÇ). Êàê ïðàâèëî, äëÿ ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû òðåáóåòñÿ íå ìåíåå 50 % âðå- ìåíè ðåøåíèÿ âñåé çàäà÷è â öåëîì. Íàïðèìåð, çàäà÷è ëèíåéíîé àëãåáðû âîç- íèêàþò ïðè äèñêðåòèçàöèè êðàåâûõ çàäà÷ èëè çàäà÷ íà ñîáñòâåííûå çíà÷åíèÿ ïðîåêöèîííî-ðàçíîñòíûì ìåòîäîì (êîíå÷íûõ ðàçíîñòåé, êîíå÷íûõ ýëåìåíòîâ). Òàêæå ïðè èñïîëüçîâàíèè èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ íåëèíåéíûõ çàäà÷ ÷àñòî íà êàæäîé èòåðàöèè ðåøàåòñÿ ëèíåàðèçîâàííàÿ çàäà÷à — ÑËÀÓ. Âàæíî îòìåòèòü, ÷òî äëÿ çàäà÷ ëèíåéíîé àëãåáðû, âîçíèêàþùèõ ïðè äèñ- êðåòèçàöèè, êîëè÷åñòâî íåíóëåâûõ ýëåìåíòîâ ìàòðèö ñîñòàâëÿåò kn, ãäå k n�� , à n — ïîðÿäîê ìàòðèöû, ò.å. ìàòðèöû ÿâëÿþòñÿ ðàçðåæåííûìè. Ñòðóêòóðà ðàçðå- æåííîé ìàòðèöû îïðåäåëÿåòñÿ íóìåðàöèåé íåèçâåñòíûõ çàäà÷è è ÷àñòî ìîæåò áûòü ëåíòî÷íîé, áëî÷íî-äèàãîíàëüíîé ñ îêàéìëåíèåì, ïðîôèëüíîé è ò.ä. Âî ìíîãèõ ñëó÷àÿõ ìàòðèöû äèñêðåòíûõ çàäà÷ ñèììåòðè÷íû è ïîëîæèòåëüíî îïðåäåëåíû èëè ïîëîæèòåëüíî ïîëóîïðåäåëåíû. Äðóãîé îñîáåííîñòüþ ÿâëÿåòñÿ âûñîêèé ïîðÿäîê ìàòðèö çàäà÷ — äî äåñÿò- êîâ ìèëëèîíîâ. Ýòî âûçâàíî öåëåñîîáðàçíîñòüþ îïåðèðîâàíèÿ áîëåå òî÷íûìè äèñêðåòíûìè ìîäåëÿìè, ÷òî ïîçâîëÿåò ïîëó÷àòü ïðèáëèæåííûå ðåøåíèÿ, áîëåå áëèçêèå ê ðåøåíèÿì èñõîäíûõ çàäà÷, ó÷èòûâàòü ëîêàëüíûå îñîáåííîñòè äàííîãî ïðîöåññà èëè ÿâëåíèÿ. Ââèäó âûñîêèõ ïîðÿäêîâ, íåñìîòðÿ íà ðàçðåæåííóþ ñòðóêòóðó ìàòðèö, ðå- øåíèå òàêèõ çàäà÷ òðåáóåò çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ ðåñóðñîâ, êîòîðûå ìî- ãóò áûòü ïðåäîñòàâëåíû ñîâðåìåííûìè ïàðàëëåëüíûìè êîìïüþòåðàìè, â ÷àñò- íîñòè êîìïüþòåðàìè MIMD-àðõèòåêòóðû. Ïðè ýòîì, îäíàêî, ðàçâèòèå âû÷èñëè- òåëüíîé òåõíèêè — ïîÿâëåíèå ìíîãîÿäåðíûõ ïðîöåññîðîâ — äèêòóåò íåîáõîäèìîñòü ðàñïàðàëëåëèâàíèÿ äëÿ ýôôåêòèâíîãî èñïîëüçîâàíèÿ âûñîêîïðî- èçâîäèòåëüíîãî âû÷èñëèòåëüíîãî ðåñóðñà. Âîçíèêàåò ïðîáëåìà àäàïòàöèè ñó- ùåñòâóþùåãî ïðîãðàììíîãî îáåñïå÷åíèÿ ê íîâîé àðõèòåêòóðå êîìïüþòåðîâ. Ïîñêîëüêó âî ìíîãèõ ïðèêëàäíûõ ïðîãðàììíûõ ñðåäñòâàõ ìîæíî âûäåëèòü òðè ÷àñòè: ïðåïðîöåññîð, ïðîöåññîð (ðåøàòåëü) è ïîñòïðîöåññîð, òî ïðîáëåìó àäàï- òàöèè ìîæíî äîñòàòî÷íî áûñòðî ðåøèòü çàìåíîé ðåøàòåëÿ èëè îòäåëüíûõ åãî ìîäóëåé ñîîòâåòñòâóþùèìè ïàðàëëåëüíûìè àíàëîãàìè. Ïîýòîìó ÿâëÿåòñÿ àêòóàëüíûì ñîçäàíèå äëÿ MIMD-êîìïüþòåðîâ ýôôåêòèâíûõ ïàðàëëåëüíûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû ñ ðàçðåæåííûìè ìàòðèöàìè. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 159 © À.Í. Õèìè÷, À.Â. Ïîïîâ, Â.Â. Ïîëÿíêî, 2011 Ïîä ýôôåêòèâíûì àëãîðèòìîì ðåøåíèÿ ïîíèìàåòñÿ àëãîðèòì, êîòîðûé ïî- çâîëÿåò ïîëó÷èòü äîñòîâåðíîå ðåøåíèå çàäà÷è ñ ìèíèìàëüíûì èñïîëüçîâàíèåì ðåñóðñîâ êîìïüþòåðà — ïðîöåññîðîâ, ïàìÿòè, âðåìåíè. Êà÷åñòâî ïàðàëëåëüíûõ àëãîðèòìîâ îöåíèâàåòñÿ, êàê ïðàâèëî, êîýôôèöèåíòàìè óñêîðåíèÿ è ýôôåêòèâ- íîñòè [1]. Âàæíî òàêæå îïðåäåëèòü, êàêîé àëãîðèòì íàèáîëåå ýôôåêòèâåí äëÿ ðåøåíèÿ êîíêðåòíîé çàäà÷è. Ýôôåêòèâíîñòü ïàðàëëåëüíûõ àëãîðèòìîâ â çíà÷èòåëüíîé ñòåïåíè çàâèñèò îò ñáàëàíñèðîâàííîñòè çàãðóçêè ïðîöåññîðîâ, êîòîðàÿ ïðè ðåøåíèè çàäà÷ ëèíåé- íîé àëãåáðû âî ìíîãîì îïðåäåëÿåòñÿ ñïîñîáàìè ðàñïðåäåëåíèÿ ìåæäó ïðîöåññà- ìè, õðàíåíèÿ è îáðàáîòêè ìàòðèö è âåêòîðîâ ðåøàåìîé çàäà÷è. Ïðè ýòîì íåîáõî- äèìî ñòðåìèòüñÿ ê ðàâíîìåðíîé çàãðóçêå â êàæäûé ìîìåíò âðåìåíè âñåõ ïðîöåñ- ñîðîâ, ó÷àñòâóþùèõ â ðåøåíèè çàäà÷è, ìèíèìèçèðóÿ âðåìÿ ïðåáûâàíèÿ ïðîöåññîðîâ â ñîñòîÿíèè îæèäàíèÿ. Òàêæå ïðè ðàçðàáîòêå ïàðàëëåëüíûõ ðåøà- òåëåé äëÿ ñóùåñòâóþùèõ ïðîãðàììíûõ ñðåäñòâ íåîáõîäèìî ó÷èòûâàòü ñòðóêòóðó ðàçðåæåííûõ ìàòðèö, ôîðìèðóåìûõ ýòèìè ïðîãðàììíûìè ñðåäñòâàìè âî èçáåæàíèå äîïîëíèòåëüíûõ ïåðåôîðìèðîâàíèé. ÌÅÒÎÄÛ ÐÅØÅÍÈß ÍÅÊÎÒÎÐÛÕ ÇÀÄÀ× ËÈÍÅÉÍÎÉ ÀËÃÅÁÐÛ Ñðåäè ìíîæåñòâà çàäà÷ ëèíåéíîé àëãåáðû ñ ðàçðåæåííûìè ìàòðèöàìè êëþ÷å- âîå ìåñòî çàíèìàåò ðåøåíèå ÑËÀÓ ñ ñèììåòðè÷íûìè ïîëîæèòåëüíî-îïðåäå- ëåííûìè ìàòðèöàìè. Ðàññìîòðèì ðåøåíèå ÑËÀÓ Ax b� ñ ïîëóîïðåäåëåííîé ìàòðèöåé ìåòîäîì òðåõýòàïíîé ðåãóëÿðèçàöèè [2, 3]. Ýòîò ìåòîä ñîñòîèò â ïîñëåäîâàòåëüíîì âûïîëíåíèè ñëåäóþùèõ øàãîâ: 1) ïîñëåäîâàòåëüíîå ðåøåíèå äâóõ ÑËÀÓ: ( )A I z bk� �� 0 è ( )A I u Az� �� 0 ïðè ïðîèçâîëüíî âûáðàííîì ïàðàìåòðå � 0 0� (íàïðèìåð, � 0 0 01� , ) ; 2) ðåøåíèå ÑËÀÓ ( )A I w uÍ� �� 0 è âû÷èñëåíèå � � max i iw| | , ãäå u u uH i i� � � � � max| | 1 ; 3) ïðîâåðêà âûïîëíåíèÿ íåðàâåíñòâà ( | | | | )2 0� � � �� �A b ; åñëè íåðàâåíñòâî âûïîëíÿåòñÿ, òî íåîáõîäèìàÿ òî÷íîñòü � äîñòèãàåòñÿ ïðè âûáðàííîì � 0 ; åñëè íåðàâåíñòâî íå âûïîëíÿåòñÿ, òî ïî ôîðìóëå � � � �1 1 2 � � � � �| | | |A b îïðåäåëÿåòñÿ íîâîå çíà÷åíèå ñäâèãà �1 è ïîâòîðÿåòñÿ ïåðâûé øàã ñ ìàòðèöåé A I� �1 — âû- ÷èñëÿåòñÿ íîâîå ïðèáëèæåíèå u, êîòîðîå îáåñïå÷èâàåò íåîáõîäèìóþ òî÷íîñòü � íîðìàëüíîãî ïñåâäîðåøåíèÿ. Òàêèì îáðàçîì, íåîáõîäèìî íàõîäèòü ðåøåíèÿ ïî ìåíüøåé ìåðå òðåõ ÑËÀÓ ñ ïîëîæèòåëüíî-îïðåäåëåííîé ìàòðèöåé. Êðîìå òîãî, ñëåäóåò îáðàòèòü âíèìàíèå íà âû÷èñëåíèå ïðîèçâåäåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû íà âåêòîð. Äëÿ ðåøåíèÿ ÷àñòè÷íîé îáîáùåííîé ÀÏÑÇ Ax Bx� � ìîæíî èñïîëüçîâàòü ìåòîä èòåðàöèé íà ïîäïðîñòðàíñòâå [2, 4], êîòîðûé çàêëþ÷àåòñÿ â ïîñòðîåíèè ïîñëåäîâàòåëüíîñòè ïîäïðîñòðàíñòâ E tt ( , , )�1 2 � , ñõîäÿùåéñÿ ê ïîäïðîñòðàí- ñòâó E� , êîòîðîå ñîäåðæèò èñêîìûå ñîáñòâåííûå âåêòîðû. Äëÿ ýòîãî íà t-é èòå- ðàöèè âû÷èñëÿåòñÿ îðòîíîðìèðîâàííûé áàçèñ ïîäïðîñòðàíñòâà Et è, åñëè âû- ïîëíÿþòñÿ óñëîâèÿ îêîí÷àíèÿ èòåðàöèîííîãî ïðîöåññà | |( ) ( ) ( ) � � � �i t i t i t � 1 ( , , ,i r� �1 2 , à ñîáñòâåííûå çíà÷åíèÿ óïîðÿäî÷åíû ïî âîçðàñòàíèþ 0 1 2� � ��� ��� � � r ), îïðåäåëÿþòñÿ ïðèáëèæåíèÿ ê èñêîìûì ñîáñòâåííûì ïàðàì. Òàêèì îáðàçîì, äëÿ t � �1 2, , âûïîëíÿþòñÿ ñëåäóþùèå îïåðàöèè: 160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 1) ðåøåíèå ÑËÀÓ AX Yt t� 1; 2) âû÷èñëåíèå ïðÿìîóãîëüíîé ìàòðèöû W BXt t� ; 3) ðåøåíèå ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé A Z B Zt t t t t� � äëÿ ïðî- åêöèé ìàòðèö À è B íà ïîäïðîñòðàíñòâî Et (A X Y X AXt t t t t� � T T 1 , Bt � � �X W X BXt t t t T T ); 4) âû÷èñëåíèå Y W Zt t t� ; 5) ïðîâåðêà óñëîâèé îêîí÷àíèÿ èòåðàöèîííîãî ïðîöåññà; åñëè ýòè óñëîâèÿ âûïîëíÿþòñÿ ïîñëå t èòåðàöèé, òî â êà÷åñòâå ïðèáëèæåííîãî ðåøåíèÿ çàäà÷è ïðèíèìàþòñÿ � �i i t* ( )� �1 , X X Zt t * � � �1 1 ( , , , )i r� �1 2 . Òàêèì îáðàçîì, è â ýòîì ñëó÷àå íà êàæäîé èòåðàöèè ðåøàåòñÿ ÑËÀÓ ñ ïîëî- æèòåëüíî-îïðåäåëåííîé ìàòðèöåé. Åñëè ìàòðèöà B íå ÿâëÿåòñÿ äèàãîíàëüíîé, íà êàæäîé èòåðàöèè äîëæíî âû÷èñëÿòüñÿ ïðîèçâåäåíèå ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû íà ïëîòíóþ ïðÿìîóãîëüíóþ ìàòðèöó. Êðîìå ñîáñòâåííî ðåøåíèÿ çàäà÷è ëèíåéíîé àëãåáðû, äëÿ ãàðàíòèðîâàíèÿ äîñòîâåðíîñòè ðåçóëüòàòîâ íåîáõîäèìî ïðîâîäèòü èññëåäîâàíèÿ ìàòåìàòè÷åñêèõ ñâîéñòâ êîìïüþòåðíîé ìîäåëè çàäà÷è. Ìåòîäû è àëãîðèòìû òàêèõ èññëåäîâàíèé ïðåäñòàâëåíû â [2], ãäå ìíîãèå èç íèõ áàçèðóþòñÿ íà ðåøåíèè ÑËÀÓ. Òàêæå ðåøåíèå ÑËÀÓ ñ ðàçðåæåííûìè ñèììåòðè÷íûìè ïîëîæèòåëü- íî-îïðåäåëåííûìè ìàòðèöàìè èñïîëüçóåòñÿ â àëãîðèòìàõ ðåøåíèÿ íåëèíåéíûõ ñèñòåì óðàâíåíèé, ïðè èíòåãðèðîâàíèè ñèñòåì äèôôåðåíöèàëüíûõ óðàâíåíèé è äðóãèõ çàäà÷àõ. Ïîýòîìó äàëåå ðàññìîòðèì áîëåå ïîäðîáíî ðåøåíèå ÑËÀÓ ñ ðàçðåæåííûìè ñèììåòðè÷íûìè ïîëîæèòåëüíî-îïðåäåëåííûìè ìàòðèöàìè. ÌÅÒÎÄÛ ÐÅØÅÍÈß ÑËÀÓ Ñ ÐÀÇÐÅÆÅÍÍÛÌÈ ÑÈÌÌÅÒÐÈ×ÍÛÌÈ ÏÎËÎÆÈÒÅËÜÍÎ-ÎÏÐÅÄÅËÅÍÍÛÌÈ ÌÀÒÐÈÖÀÌÈ Ïðîáëåìà ðàçðàáîòêè ýôôåêòèâíûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ñèììåòðè÷íûìè ïîëîæèòåëüíî-îïðåäåëåííûìè ìàòðèöàìè ÿâëÿåòñÿ âåñüìà àê- òóàëüíîé, î ÷åì ñâèäåòåëüñòâóåò áîëüøîå ÷èñëî ïóáëèêàöèé. Ïåðâûå äåòàëü- íûå èññëåäîâàíèÿ ìåòîäîâ ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ìàòðèöàìè íà÷àëè ïðîâîäèòüñÿ ñ ïîÿâëåíèåì è ðàçâèòèåì ÝÂÌ. Ââèäó îãðàíè÷åííûõ âîçìîæ- íîñòåé ÝÂÌ âûïóñêà 50-70 ãîäîâ ïðîøëîãî âåêà ïåðâîíà÷àëüíî ðàçâèòèå ïî- ëó÷èëè èòåðàöèîííûå ìåòîäû. Îäíàêî ýôôåêòèâíîñòü èòåðàöèîííûõ ìåòîäîâ ñóùåñòâåííî çàâèñèò îò àïðèîðíîé èíôîðìàöèè î ñâîéñòâàõ ìàòðèöû çàäà÷è. Êðîìå òîãî, â ñëó÷àå ìíîãîêðàòíîãî ðåøåíèÿ, êàê è â ïðèâåäåííûõ âûøå ïðè- ìåðàõ, äëÿ ÑËÀÓ ñ îäíîé è òîé æå ìàòðèöåé è ðàçëè÷íûìè ïðàâûìè ÷àñòÿìè ïðÿìûå ìåòîäû îêàçûâàþòñÿ íàìíîãî ýôôåêòèâíåå. Ïîýòîìó ïî ìåðå íàðàùèâà- íèÿ âû÷èñëèòåëüíûõ ðåñóðñîâ êîìïüþòåðîâ âñå áîëåå øèðîêîå ðàçâèòèå ïîëó- ÷àþò àëãîðèòìû ïðÿìûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ìàòðèöàìè.  80-å ãîäû ïðîøëîãî âåêà áûë îïóáëèêîâàí ðÿä ôóíäàìåíòàëüíûõ ðàáîò, êîòîðûå îñâåùàëè îñíîâíûå äîñòèæåíèÿ â ýòîì íàïðàâëåíèè.  ìîíîãðàôèè [5] îïèñàíî áîëüøèíñòâî îñíîâíûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ñèì- ìåòðè÷íûìè ïîëîæèòåëüíî-îïðåäåëåííûìè ìàòðèöàìè áîëüøèõ ðàçìåðîâ. Ðàáî- òà [6] ïîñâÿùåíà ðàññìîòðåíèþ îñíîâíûõ ìåòîäîâ ðåøåíèÿ àëãåáðàè÷åñêèõ çà- äà÷ ñ ðàçðåæåííûìè ìàòðèöàìè è òåõíîëîãèè èõ ïðèìåíåíèÿ. Èññëåäîâàíèå ïðÿ- ìûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ èçëîæåíû â êíèãå [7], à ìîíîãðàôèÿ [8] ïîñâÿùåíà ïðîáëåìàì ðåàëèçàöèè ïðèâåäåííûõ ìåòîäîâ íà ïàðàëëåëüíûõ êîìïüþòåðàõ. Íà îñíîâå íàêîïëåííîãî ìàòåðèàëà áûë îïðåäåëåí ðÿä ýôôåêòèâíûõ àëãî- ðèòìîâ ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ìàòðèöàìè, ñïîñîáû õðàíåíèÿ ðàçðå- æåííûõ äàííûõ, à òàêæå ðàçëè÷íûå àëãîðèòìû îïòèìèçàöèè çàïîëíåíèÿ. Ïîäàâ- ëÿþùåå áîëüøèíñòâî íîâûõ ðàçðàáîòîê áàçèðóåòñÿ íà ðàáîòàõ [9–11], â êîòîðûõ ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 161 ïðîâåäåí øèðîêèé îáçîð ñîâðåìåííûõ àëãîðèòìîâ ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ìàòðèöàìè. Ðàññìîòðèì ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé Àx b� (1) ñ ñèììåòðè÷íîé ïîëîæèòåëüíî-îïðåäåëåííîé ìàòðèöåé A ïîðÿäêà n. Íàèáîëåå ýôôåêòèâíûì ïðÿìûì ìåòîäîì ðåøåíèÿ òàêîé çàäà÷è ÿâëÿåòñÿ, êàê èçâåñòíî [12], ìåòîä Õîëåöêîãî.  âàðèàíòå LDLT ìåòîäà Õîëåöêîãî (â íåêîòîðûõ ñëó÷àÿõ öåëåñîîáðàçíî èñïîëüçîâàòü âìåñòî íèæíåé òðåóãîëüíîé ìàòðèöû L âåðõíþþ òðåóãîëüíóþ ìàò- ðèöóU L� T , òîãäà ìîæíî ãîâîðèòü î âåðñèè ìåòîäà Õîëåöêîãî U DUT ) ðåøåíèå ñèñòåìû (1) ñîñòîèò â ðåøåíèè ñëåäóþùèõ òðåõ ïîäçàäà÷: • òðåóãîëüíîå ðàçëîæåíèå ìàòðèöû ñèñòåìû A LDL� T èëè A U DU� T (2) (D — äèàãîíàëüíàÿ ìàòðèöà); • ðåøåíèå òðåóãîëüíîé ñèñòåìû Ly b� èëè DUy b� ; (3) • ðåøåíèå òðåóãîëüíîé ñèñòåìû L x D yT � 1 èëè U x yÒ � . (4) Ýëåìåíòû LDLT -ðàçëîæåíèÿ (2) âû÷èñëÿþòñÿ ïî ôîðìóëàì l t d k iik ik k� � � / , , ,1 1, d a l ti ii ik ik k i � � � 1 1 ; t a l tji ji ik jk k j � � � 1 1 , j i n i n� � � � �1 1 2, , , , , , , (5) ãäå lik — ýëåìåíò ìàòðèöû L di, — äèàãîíàëüíûé ýëåìåíò ìàòðèöû D. Ó÷è- òûâàÿ, ÷òî U L� T , ìîæíî ëåãêî ïîëó÷èòü àíàëîãè÷íûå ôîðìóëû äëÿ âû÷èñëå- íèÿ ýëåìåíòîâ U DUT -ðàçëîæåíèÿ (2) ìàòðèöû ÑËÀÓ.  ñëó÷àå ðàçðåæåííûõ ñèììåòðè÷íûõ ìàòðèö îáùèé îáúåì âû÷èñëåíèé ñó- ùåñòâåííî ñîêðàùàåòñÿ, åñëè âû÷èñëåíèÿ ïî ôîðìóëàì (5) âûïîëíÿòü òîëüêî ñ çàâåäîìî íåíóëåâûìè ýëåìåíòàìè ðàçëîæåíèÿ ìàòðèöû. Îáîçíà÷èì Z Li ( ) ìíî- æåñòâî âòîðûõ èíäåêñîâ íåíóëåâûõ ïîääèàãîíàëüíûõ ýëåìåíòîâ i-é ñòðîêè íè- æíåé òðåóãîëüíîé ìàòðèöû L. Òîãäà ñóììèðîâàíèå â ôîðìóëàõ (5) ïðîâîäèòñÿ òîëüêî äëÿ k Z Li� ( ) èëè k Z L Z Li j� �( ) ( ) . Òàêèì îáðàçîì, ýëåìåíò lij � 0, åñëè aij � 0 è Z L Z Li j( ) ( )� � �. Åñëè â ñòðîêàõ íèæíåé òðåóãîëüíîé ìàòðèöû L ñîäåðæèòñÿ ìíîãî íåðåãó- ëÿðíî ðàñïîëîæåííûõ íóëåâûõ ýëåìåíòîâ, òî ïðè âû÷èñëåíèÿõ ïî ôîðìóëàì (5) ñóùåñòâåííî âîçðàñòàþò íàêëàäíûå ðàñõîäû íà ïîèñê ñîîòâåòñòâóþùèõ ïàð íå- íóëåâûõ ýëåìåíòîâ.  ýòîì ñëó÷àå öåëåñîîáðàçíî èñïîëüçîâàòü äðóãîé ïîðÿäîê âû÷èñëåíèé ýëåìåíòîâ òðåóãîëüíîãî ðàçëîæåíèÿ, ïðè÷åì áîëåå ðàöèîíàëüíî íà- õîäèòü âåðõíþþ òðåóãîëüíóþ ìàòðèöó U . Òàêèì îáðàçîì, ýëåìåíòû U DUT -ðàç- ëîæåíèÿ ìîæíî âû÷èñëèòü ïî ñëåäóþùèì ôîðìóëàì (ïðè t aij ij ( )0 � ): d t u t d k i ni ii i ik ik i i� � � � � ( ) ( ), / , , , ,1 1 1 (6) t t u t k j n j i n i jk i jk i ik ij i( ) ( ) ( ) , , , , , , , ,� � � � � � � 1 1 1 1 2, , .� n (7) 162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 Ýòè âûðàæåíèÿ ëåãêî ïîëó÷èòü èç ôîðìóë äëÿ âû÷èñëåíèÿ ýëåìåíòîâ òðå- óãîëüíîãî ðàçëîæåíèÿ àëãîðèòìîì Õîëåöêîãî â âèäå âíåøíèõ ïðîèçâåäåíèé. Ëåãêî óâèäåòü, ÷òî âñå íóëåâûå ýëåìåíòû èñõîäíîé ìàòðèöû, ðàñïîëîæåí- íûå â ñòðîêàõ ëåâåå èëè â ñòîëáöàõ âûøå ïåðâîãî íåíóëåâîãî ýëåìåíòà, îñòàþò- ñÿ íóëåâûìè â ñîîòâåòñòâóþùåì òðåóãîëüíîì ðàçëîæåíèè. Ïîýòîìó ýòè ýëåìåí- òû â âû÷èñëåíèÿõ íå ó÷àñòâóþò, à ïåðâûå íåíóëåâûå ýëåìåíòû (ëåâûå â ñòðîêàõ èëè âåðõíèå â ñòîëáöàõ) îïðåäåëÿþò ïðîôèëü ðàçðåæåííîé ìàòðèöû. Ôîðìóëû (5) èëè (6), (7) ñâèäåòåëüñòâóþò, ÷òî ïðîôèëè èñõîäíîé ìàòðèöû è åå òðåóãîëü- íîãî ðàçëîæåíèÿ ñîâïàäàþò. Ïðè ýòîì çàïîëíåííîñòü ïðîôèëÿ òðåóãîëüíîãî ðàç- ëîæåíèÿ ðàçðåæåííîé ìàòðèöû âîçðàñòàåò ïî ñðàâíåíèþ ñ èñõîäíîé ðàçðåæåí- íîé ìàòðèöåé, õîòÿ íåêîòîðûå âíóòðåííèå ýëåìåíòû ïðîôèëÿ òðåóãîëüíîãî ðàç- ëîæåíèÿ ìîãóò îñòàâàòüñÿ íóëåâûìè. Çàïîëíåííîñòü ïðîôèëÿ òðåóãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ìàòðèöû çàâèñèò îò ñâÿçåé ìåæäó íåèçâåñòíûìè ñèñòå- ìû è ðåãóëèðóåòñÿ èõ íóìåðàöèåé. Ñóùåñòâóþò (íàïðèìåð, [5]) ðàçëè÷íûå àëãî- ðèòìû ïåðåóïîðÿäî÷åíèÿ íåèçâåñòíûõ, êîòîðûå ïîçâîëÿþò êàê óìåíüøèòü çàïîëíåííîñòü ïðîôèëÿ, òàê è óëó÷øèòü äðóãèå õàðàêòåðèñòèêè ïðîôèëÿ òðåóãîëüíîãî ðàçëîæåíèÿ, âëèÿþùèå íà îáùåå êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé ïðè ðåøåíèè ÑËÀÓ. Äëÿ ðåøåíèÿ òðåóãîëüíûõ ñèñòåì (3) è (4) ìîæíî âûïèñàòü ôîðìóëû, àíàëî- ãè÷íûå ôîðìóëàì (5) èëè (6), (7). Ïîñêîëüêó êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé ïðè ðåøåíèè ñèñòåì ñ òðåóãîëüíûìè ìàòðèöàìè ñóùåñòâåííî ìåíüøå (íàïðèìåð, äëÿ ëåíòî÷íûõ ìàòðèö â m ðàç, m — øèðèíà ëåíòû), ÷åì ïðè òðåóãîëüíîì ðàçëîæå- íèè ìàòðèöû èñõîäíîé ñèñòåìû, òî äàëåå àêöåíòèðóåì âíèìàíèå íà ïàðàëëåëüíûõ àëãîðèòìàõ òðåóãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû. ÑÒÐÓÊÒÓÐÛ ÐÀÇÐÅÆÅÍÍÛÕ ÌÀÒÐÈÖ È ÔÎÐÌÀÒÛ ÇÀÄÀÍÈß ÄÀÍÍÛÕ Ïðè ðàçðàáîòêå àëãîðèòìîâ ðåøåíèÿ çàäà÷ ñ ðàçðåæåííûìè ìàòðèöàìè îñîáîå çíà÷åíèå èìååò âûáîð ñïîñîáîâ çàäàíèÿ è õðàíåíèÿ íåíóëåâûõ ýëåìåíòîâ. Ýòè ñïîñîáû îïðåäåëÿþòñÿ ñòðóêòóðîé (ðàçìåùåíèåì íåíóëåâûõ ýëåìåíòîâ) ðàçðå- æåííîé ìàòðèöû è òðåáîâàíèÿìè àëãîðèòìà ðåøåíèÿ çàäà÷è ñ òàêîé ìàòðèöåé.  îáùåì ñëó÷àå êàæäûé íåíóëåâîé ýëåìåíò aij ðàçðåæåííîé ìàòðèöû îïðå- äåëÿåòñÿ ñâîèì çíà÷åíèåì è çíà÷åíèÿìè èíäåêñîâ i è j. Îäíîé èç íàèáîëåå óíè- âåðñàëüíûõ ñõåì õðàíåíèÿ ðàçðåæåííûõ ìàòðèö ÿâëÿåòñÿ ðàçðåæåííûé ñòðî÷íûé ôîðìàò [10], êîòîðûé ïîçâîëÿåò íåñêîëüêî óìåíüøèòü îáúåì õðàíèìîé èíôîð- ìàöèè.  ñîîòâåòñòâèè ñ ýòèì çíà÷åíèÿ íåíóëåâûõ ýëåìåíòîâ ìàòðèöû è âòîðûõ èíäåêñîâ j õðàíÿòñÿ â äâóõ ìàññèâàõ: AN è JA. Èñïîëüçóåòñÿ òàêæå ìàññèâ óêà- çàòåëåé IA, îòìå÷àþùèõ ïîçèöèè ìàññèâîâ AN è JA, ñ êîòîðûõ íà÷èíàåòñÿ îïè- ñàíèå î÷åðåäíîé ñòðîêè. Ðàçðåæåííûé ñòðî÷íûé ôîðìàò ïðåäñòàâëÿåò ñîáîé îäíó èç íàèáîëåå èñïîëüçóåìûõ ñõåì õðàíåíèÿ ðàçðåæåííûõ ìàòðèö. Ýòà ñõåìà ïðåäúÿâëÿåò íåâûñîêèå òðåáîâàíèÿ ê ïàìÿòè è ïðè ýòîì îêàçûâàåòñÿ ÷ðåçâû÷àé- íî óäîáíîé äëÿ íåêîòîðûõ âàæíûõ îïåðàöèé ñ ðàçðåæåííûìè ìàòðèöàìè: ñëîæå- íèå, óìíîæåíèå, ïåðåñòàíîâêà ñòðîê è ò.ï. Îìåòèì, ÷òî òàêèå óíèâåðñàëüíûå ñõåìû õðàíåíèÿ äàííûõ, êàê ðàçðåæåí- íûé ñòðî÷íûé ôîðìàò, íå ó÷èòûâàþò ñïåöèôèêè ñòðóêòóðû (ïîðòðåòà) ìàòðèöû, êîòîðàÿ èìååò âàæíîå çíà÷åíèå ïðè ðàçðàáîòêå àëãîðèòìà ðåøåíèÿ çàäà÷è, è ïîý- òîìó òàêèå ñõåìû íå âñåãäà óäîáíû äëÿ ðåøåíèÿ ÑËÀÓ. Ñîâðåìåííûå êîìïüþ- òåðû èìåþò ñëîæíóþ ìíîãîóðîâíåâóþ ïàìÿòü. Ïðè âûïîëíåíèè âû÷èñëåíèé îíè ñòðåìÿòñÿ ìàêñèìàëüíî èñïîëüçîâàòü ñàìóþ áûñòðóþ ïàìÿòü — ðåãèñòðû, êýø-ïàìÿòü ïåðâîãî óðîâíÿ, ìèíèìèçèðóÿ êîëè÷åñòâî îáðàùåíèé ê ìåäëåííîé ïàìÿòè. Îäíàêî â ïðàêòè÷åñêèõ çàäà÷àõ ÷àñòî íåíóëåâûå ýëåìåíòû ñòðîê òðå- óãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû ðàñïîëîæåíû êîì- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 163 ïàêòíî ãðóïïàìè èëè ñîñòàâëÿþò îäíó ãðóïïó. Èñïîëüçîâàíèå òàêîé èíôîðìà- öèè îá îñîáåííîñòÿõ ñòðóêòóðû òðåóãîëüíîãî ðàçëîæåíèÿ ïîçâîëÿåò óïðîñòèòü àëãîðèòìû ðåøåíèÿ, óñêîðèòü äîñòóï ê ýëåìåíòàì ýòîé ìàòðèöû è âûïîëíåíèå îïåðàöèé íàä íèìè. Åñëè êîëè÷åñòâî íóëåâûõ ýëåìåíòîâ âíóòðè ïðîôèëÿ òðåóãîëüíîãî ðàçëîæå- íèÿ ðàçðåæåííîé ìàòðèöû ñðàâíèòåëüíî íåâåëèêî, òî âñå âíóòðåííèå ýëåìåíòû ñ÷èòàþòñÿ íåíóëåâûìè. Ìàòðèöó òàêîé ñòðóêòóðû ÷àñòî íàçûâàþò ïðîôèëüíîé. Ïðîôèëüíûé ôîðìàò äàííûõ ïðåäóñìàòðèâàåò õðàíåíèå çíà÷åíèé âíóòðåííèõ ýëåìåíòîâ ïðîôèëÿ, à òàêæå ÷èñëî òàêèõ ýëåìåíòîâ â êàæäîé ñòðîêå (â ÿâíîé èëè íåÿâíîé ôîðìå). Åñëè ìàêñèìàëüíîå êîëè÷åñòâî ýòèõ ýëåìåíòîâ â îäíîé ñòðîêå íå áîëåå ÷åì â 1,2 ðàçà ïðåâûøàåò èõ ñðåäíåå êîëè÷åñòâî, òî ïðàêòè÷åñêèå ðàñ- ÷åòû ïîêàçûâàþò, ÷òî òàêóþ ìàòðèöó ìîæíî ñ÷èòàòü ëåíòî÷íîé. Òîãäà òàêîå ìàêñèìàëüíîå êîëè÷åñòâî íåíóëåâûõ ýëåìåíòîâ â îäíîé ñòðîêå áóäåò ñîñòàâëÿòü øèðèíó ëåíòû òðåóãîëüíîãî ðàçëîæåíèÿ è ïîëóøèðèíó ëåíòû èñõîäíîé ìàòðè- öû. Ëåíòî÷íûé ôîðìàò ïðåäóñìàòðèâàåò õðàíåíèå çíà÷åíèé ýëåìåíòîâ ëåíòû ìàòðèöû è çíà÷åíèÿ øèðèíû ëåíòû. Ìàòðèöû òàêîé ñòðóêòóðû ÷àñòî ïîëó÷àþò ïðè èñõîäíîé íóìåðàöèè íåèçâåñòíûõ, à òàêæå ïðè èñïîëüçîâàíèè äëÿ îïòèìèçà- öèè ñòðóêòóðû ìàòðèöû àëãîðèòìà ôàêòîð-äåðåâüåâ èëè àëãîðèòìà Êàòõèë- ëà–Ìàêêè [5], êîòîðûå îáåñïå÷èâàþò êîíöåíòðàöèþ íåíóëåâûõ ýëåìåíòîâ âáëèçè ãëàâíîé äèàãîíàëè. ×àñòî íà ïðàêòèêå, íàïðèìåð ïðè ðàñ÷åòå êîíñòðóêöèé, âîçíèêàþò çàäà÷è ñ ñèììåòðè÷- íûìè ìàòðèöàìè îñîáîé ñòðóêòóðû (ðèñ. 1).  âåðõíåì òðåóãîëüíèêå òàêèõ ìàòðèö íåíó- ëåâûå çíà÷åíèÿ ðàçìåùàþòñÿ âåðòèêàëüíî ïî íåñêîëüêî ñòîëáöîâ ïîäðÿä, ïî âíåøíåìó âèäó íàïîìèíàÿ íåáîñêðåáû (ïîýòîìó ìàòðè- öû òàêîé ñòðóêòóðû èíîãäà íàçûâàþò «íåáî- ñêðåáíûìè»). Òàêèì îáðàçîì, ëþáàÿ ñòðîêà âåðõíåãî òðåóãîëüíèêà ñîñòîèò èç ïîñëåäîâà- òåëüíûõ ãðóïï íåíóëåâûõ è íóëåâûõ ýëåìåí- òîâ. Ïîñêîëüêó íåíóëåâûå ýëåìåíòû ñîõðàíÿ- þòñÿ ãðóïïàìè, òî íåò íåîáõîäèìîñòè õðàíèòü èíäåêñû êàæäîãî ýëåìåíòà, ÷òî ïîçâîëÿåò óìåíüøèòü ðàçìåðû èíäåêñíûõ ìàññèâîâ. Òà- êóþ ñòðóêòóðó ìàòðèö ìîæíî ïîëó÷èòü â ñëó÷àå èñïîëüçîâàíèÿ àëãîðèòìà ìèíè- ìàëüíîé ñòåïåíè [5], êîòîðûé ìèíèìèçèðóåò êîëè÷åñòâî íåíóëåâûõ ýëåìåíòîâ â ïðîôèëå òðåóãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ìàòðèöû. Ñõåìà çàäàíèÿ íåíóëåâûõ ýëåìåíòîâ ãðóïïàìè ÿâëÿåòñÿ ìîäèôèêàöèåé ðàçðå- æåííîãî ñòðî÷íîãî ôîðìàòà äëÿ ñëó÷àÿ ìàòðèö îïèñàííîãî âèäà. Äëÿ çàäàíèÿ êàæ- äîé ñòðîêè ðàçðåæåííîé ìàòðèöû â ýòîé ñõåìå èñïîëüçóþòñÿ çíà÷åíèÿ è êîëè÷å- ñòâî íåíóëåâûõ ýëåìåíòîâ ìàòðèöû â ñòðîêå, êîëè÷åñòâî ãðóïï íåíóëåâûõ ýëå- ìåíòîâ ìàòðèöû â ñòðîêå, êîëè÷åñòâî ýëåìåíòîâ â êàæäîé ãðóïïå íåíóëåâûõ èëè íóëåâûõ ýëåìåíòîâ. Òàêèì îáðàçîì, åñëè ãðóïïû íåíóëåâûõ ýëåìåíòîâ âêëþ÷àþò òðè èëè áîëåå ýëåìåíòîâ, òî â ðàññìàòðèâàåìîé ñõåìå çàäàåòñÿ ìåíüøèé îáúåì äàííûõ, ÷åì ïðè èñïîëüçîâàíèè ðàçðåæåííîãî ñòðî÷íîãî ôîðìàòà. ÐÀÑÏÐÅÄÅËÅÍÈÅ ÄÀÍÍÛÕ ÏÐÈ ÏÀÐÀËËÅËÜÍÛÕ ÂÛ×ÈÑËÅÍÈßÕ Êàê îòìå÷àëîñü âûøå, ýôôåêòèâíîñòü ïàðàëëåëüíûõ àëãîðèòìîâ â çíà÷èòåëü- íîé ñòåïåíè çàâèñèò îò ñáàëàíñèðîâàííîñòè çàãðóçêè ïðîöåññîâ. Ïðè ðåøåíèè ÑËÀÓ ðåøàþùóþ ðîëü â áàëàíñèðîâàíèè çàãðóçêè ïðîöåññîâ, ó÷èòûâàÿ îá- 164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 Ðèñ. 1. Ïðèìåð ñòðóêòóðû íåáîñêðåá- íîé ìàòðèöû ùåå êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé, èãðàåò ðàñïðåäåëåíèå äàííûõ ìåæ- äó ïðîöåññàìè ïðè âûïîëíåíèè òðåóãîëüíîãî ðàçëîæåíèÿ ìàòðèöû. Ïðè ýòîì ðàñïðåäåëåíèå ìåæäó ïðîöåññàìè ýëåìåíòîâ òðåóãîëüíîãî ðàçëîæåíèÿ ðàçðå- æåííîé ìàòðèöû îïðåäåëÿåò ðàñïðåäåëåíèå âñåõ îñòàëüíûõ äàííûõ, ó÷àñòâóþ- ùèõ â âû÷èñëåíèÿõ.  çàâèñèìîñòè îò ðàñïðåäåëåíèÿ äàííûõ ìîæíî ïîëó÷èòü òó èëè èíóþ àëãîðèòìè÷åñêóþ ðåàëèçàöèþ îïðåäåëåííîãî ìåòîäà. Íàèáîëåå ïðîñòûì èç ñóùåñòâóþùèõ ðàñïðåäåëåíèé ÿâëÿåòñÿ îäíîìåðíîå áëî÷íîå ðàñïðåäåëåíèå ýëåìåíòîâ ìàòðèöû (ðèñ. 2, à).  ýòîì ñëó÷àå êàæäûé ïðîöåññ ñîäåðæèò òîëüêî îäèí áëîê ñòðîê ìàòðèöû. Ñòðîêà k ðàçìåùåíà â ïðî- öåññå ñ íîìåðîì k tc/ , ãäå t n ñc � / — ìàêñèìàëüíîå ÷èñëî ñòðîê, ðàçìåùåííûõ â ïðîöåññå, ñ — êîëè÷åñòâî ïðîöåññîâ. Îäíàêî ýòà ñõåìà íå äàåò äîñòàòî÷íîé ñáà- ëàíñèðîâàííîñòè çàãðóçêè ïðîöåññîâ ââèäó òàê íàçûâàåìîãî ýôôåêòà Ãàéäíà. Îí çàêëþ÷àåòñÿ â òîì, ÷òî êàê òîëüêî ïåðâûå tc ñòðîê îáðàáàòûâàþòñÿ, 0-é ïðîöåññ çàêàí÷èâàåò ðàáîòó, çàòåì ïîñëå îáðàáîòêè ñëåäóþùèõ tc ñòðîê çàêàí÷èâàåò ðà- áîòó ïåðâûé ïðîöåññ è ò.ä. Ïðè ýòîì â ñëó÷àå ðàçðåæåííîé ìàòðèöû ïðîöåññû íå òîëüêî îäíîâðåìåííî íå çàêàí÷èâàþò ðàáîòó, íî è íå íà÷èíàþò åå. Îïðåäåëåííûì âûõîäîì èç òàêîé ñèòóàöèè ïîñëóæèëî ïðåäñòàâëåíèå ðàçðå- æåííîé ìàòðèöû â âèäå áëî÷íî-äèàãîíàëüíîé ñ îêàéìëåíèåì [2, 13] (ðèñ. 2, á).  ýòîì ñëó÷àå êîëè÷åñòâî äèàãîíàëüíûõ áëîêîâ ðàâíî êîëè÷åñòâó èñïîëüçóåìûõ ïðîöåññîâ. Òàêîå ïðåäñòàâëåíèå ìîæíî ïîëó÷èòü, èñïîëüçóÿ äëÿ îïòèìèçàöèè ñòðóêòóðû ìàòðèöû àëãîðèòì ïàðàëëåëüíûõ ñå÷åíèé [5]. Îäíàêî ïàðàëëåëüíûå àëãîðèòìû òðåóãîëüíîãî ðàçëîæåíèÿ ìàòðèö òàêîé ñòðóêòóðû äîñòàòî÷íî ýôôåê- òèâíû òîëüêî äëÿ ñðàâíèòåëüíî íåáîëüøîãî ðàçìåðà îáðàìëåíèÿ è ìàëîãî êîëè- ÷åñòâà ïðîöåññîâ (äî 20–30). Çíà÷èòåëüíûì øàãîì ê óëó÷øåíèþ áàëàíñèðîâàíèÿ çàãðóçêè ïðîöåññîâ, à ñëåäîâàòåëüíî è ýôôåêòèâíîñòè âû÷èñëèòåëüíûõ àëãîðèòìîâ, ÿâëÿåòñÿ öèêëè- ÷åñêèé ñïîñîá õðàíåíèÿ è îáðàáîòêè ìàòðèö, ÷òî ïðèâîäèò ê ñáàëàíñèðîâàííîé ñõåìå àëãîðèòìà [13].  ñîîòâåòñòâèè ñî ñòðî÷íî-öèêëè÷åñêîé ñõåìîé ìàòðèöà ðàñïðåäåëÿåòñÿ ìåæäó p ïðîöåññàìè ñëåäóþùèì îáðàçîì: â i-ì ïðîöåññå ðàçìå- ùàþòñÿ ñòðîêè ñ íîìåðàìè i i p i p i p p, , , , ( )� � � 2 1� .  ðåçóëüòàòå äîñòèãàåòñÿ ïî÷òè îäèíàêîâûé îáúåì âû÷èñëåíèé â êàæäîì ïðîöåññå ïðè ðåàëèçàöèè àëãî- ðèòìîâ, ò.å. ïðàêòè÷åñêè èñêëþ÷àåòñÿ âëèÿíèå ýôôåêòà Ãàéäíà. Îäíàêî â ñòðî÷- íî-öèêëè÷åñêîì ñïîñîáå îòñóòñòâèå ýôôåêòà Ãàéäíà «êîìïåíñèðóåòñÿ» äðóãèì íåäîñòàòêîì — ñëèøêîì áîëüøèì êîëè÷åñòâîì ñèíõðîíèçàöèé ìåæäó ïðîöåññà- ìè. Òîãäà êàê è â áëî÷íîé ñõåìå îáìåíû ìåæäó ïðîöåññàìè âûïîëíÿþòñÿ ëèøü ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 165 Ðèñ. 2. Ñõåìà îäíîìåðíîãî áëî÷íîãî (à) è áëî÷íî-äèàãîíàëüíîãî ñ îêàéìëåíèåì (á) ïðåäñòàâëåíèÿ ìàòðèöû a á îäèí ðàç çà p øàãîâ, ñòðî÷íî-öèêëè÷åñêàÿ ñõåìà òðåáóåò ïåðåñûëêè äàííûõ ïðè ïðåîáðàçîâàíèè êàæäîé ñòðîêè ìàòðèöû. Êîìïðîìèññîì ìåæäó îäíîìåðíûì áëî÷íûì è ñòðî÷íî-öèêëè÷åñêèì ïðåä- ñòàâëåíèÿìè ÿâëÿåòñÿ îäíîìåðíîå áëî÷íî-öèêëè÷åñêîå ïðåäñòàâëåíèå, ïðè êîòî- ðîì äàííûå ðàñïðåäåëÿþòñÿ ìåæäó ïðîöåññàìè öèêëè÷åñêè, íî áëîêàìè (ðèñ. 3). Èçìåíåíèåì ðàçìåðà áëîêà ìîæíî ïîëó÷èòü êàê áëî÷íûé, òàê è ñòðî÷íî-öèêëè- ÷åñêèé âàðèàíò. Óäà÷íî ïîäîáðàííàÿ âåëè÷èíà ðàçìåðà áëîêà ïîçâîëÿåò ïðàêòè- ÷åñêè óñòðàíèòü ýôôåêò Ãàéäíà, ïðè ýòîì ñîõðàíÿÿ êîëè÷åñòâî ñèíõðîíèçàöèé íà äîïóñòèìîì óðîâíå. ÏÀÐÀËËÅËÜÍÛÅ ÀËÃÎÐÈÒÌÛ ÒÐÅÓÃÎËÜÍÎÃÎ ÐÀÇËÎÆÅÍÈß ÐÀÇÐÅÆÅÍÍÛÕ ÑÈÌÌÅÒÐÈ×ÍÛÕ ÌÀÒÐÈÖ Ïàðàëëåëüíûå àëãîðèòìû èññëåäîâàíèÿ è ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû ñ ñèììåòðè÷íûìè ìàòðèöàìè äîñòàòî÷íî ïîëíî ïðåäñòàâëåíû â ìîíîãðàôèÿõ [2, 13]. Ïîýòîìó àêöåíòèðóåì âíèìàíèå íà ïàðàëëåëüíûõ àëãîðèòìàõ òðå- óãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû, îòìåòèâ àëãî- ðèòìû, êîòîðûå íå îïèñàíû â íàçâàííûõ âûøå ìîíîãðàôèÿõ. Èñòîðè÷åñêè ïåðâûå ïàðàëëåëüíûå àëãîðèòìû òðåóãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû áûëè ðàçðàáîòàíû äëÿ áëî÷íî-äèàãîíàëü- íîãî ñ îêàéìëåíèåì ïðåäñòàâëåíèÿ òàêîé ìàòðèöû [13, 14]. Äîñòàòî÷íî ïîäðîá- íî òàêîé àëãîðèòì îïèñàí òàêæå â ðàáîòå [2] äëÿ ðåøåíèÿ çàäà÷ ñ óçêèìè ëåíòî÷- íûìè ìàòðèöàìè. Îäíàêî âîçìîæíîñòè ïàðàëëåëüíûõ àëãîðèòìîâ ýòîé ãðóïïû îãðàíè÷åíû ââèäó ïîÿâëåíèÿ â ïðîöåññå ðàçëîæåíèÿ ïðèâåäåííîé ìàòðèöû, ïî- ðÿäîê êîòîðîé ðàâåí êîëè÷åñòâó ñòðîê (ñòîëáöîâ) â îêàéìëåíèè. Òðåóãîëüíîå ðàçëîæåíèå òàêîé ìàòðèöû ìîæåò áûòü âûïîëíåíî èëè â ïîñëåäîâàòåëüíîì ðå- æèìå (åñëè åå ïîðÿäîê ñðàâíèòåëüíî íåáîëüøîé), èëè â ïàðàëëåëüíîì, íî äëÿ ýòîãî íåîáõîäèìî ïåðåðàñïðåäåëèòü äàííûå ìåæäó ïðîöåññàìè è èñïîëüçîâàòü ïàðàëëåëüíûé àëãîðèòì äëÿ ïëîòíûõ ñèììåòðè÷íûõ ìàòðèö.  [15, 16] ðàññìîòðåí ñòðî÷íî-öèêëè÷åñêèé ïàðàëëåëüíûé àëãîðèòì ìåòîäà Õîëåöêîãî äëÿ ëåíòî÷íûõ ñèììåòðè÷íûõ ìàòðèö.  äàëüíåéøåì íà áàçå ýòîãî àëãîðèòìà áûë ðàçðàáîòàí îäíîìåðíûé áëî÷íûé öèêëè÷åñêèé àëãîðèòì ìåòîäà Õîëåöêîãî äëÿ ëåíòî÷íûõ è ïðîôèëüíûõ ñèììåòðè÷íûõ ìàòðèö (íàïðèìåð, [2]). Îäíîìåðíûå áëî÷íûå öèêëè÷åñêèå ïàðàëëåëüíûå àëãîðèòìû LDLT -ðàçëî- æåíèÿ ëåíòî÷íîé è ïðîôèëüíîé ñèììåòðè÷íûõ ìàòðèö ïðàêòè÷åñêè ñîâïàäàþò, íî âû÷èñëåíèÿ ïî ôîðìóëàì (5) ïðîâîäÿòñÿ òîëüêî äëÿ ýëåìåíòîâ ñîîòâåòñòâåí- 166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 Ðèñ. 3. Ñõåìà ñòðî÷íî-öèêëè÷åñêîãî (à) è îäíîìåðíîãî áëî÷íî-öèêëè÷åñêîãî (á) ïðåäñòàâëåíèÿ ìàòðèöû a á íî ëåíòû èëè ïðîôèëÿ ìàòðèöû. Èòàê, äëÿ êàæäîãî I s s N� �0 2, , , , , N s n s� � �( ) /1 (çäåñü s — ÷èñëî ñòðîê â áëîêå è çíà÷åíèå � �a ðàâíî öåëîé ÷àñ- òè ÷èñëà a) âûïîëíÿåòñÿ ñëåäóþùàÿ ïîñëåäîâàòåëüíîñòü îïåðàöèé: 1) ïðè I � 0 êàæäûì ïðîöåññîì ñîãëàñíî (5) âû÷èñëÿþòñÿ çíà÷åíèÿ âõîäÿ- ùèõ â ëåíòó èëè ïðîôèëü ýëåìåíòîâ ìàòðèöû tij ( j I s I� � �1, , ; i I n� � �1, , ) â ñîîòâåòñòâèè ñî ñõåìîé ðàñïðåäåëåíèÿ ýëåìåíòîâ èñõîäíîé ìàòðèöû A; 2) çàâåðøàåòñÿ âû÷èñëåíèå âåäóùèì ïðîöåññîì ýëåìåíòîâ lik è di ( , ,k i� � 1 1; i I I s n� � � �1, , min{ , }), âõîäÿùèõ ñîîòâåòñòâåííî â ëåíòó èëè ïðîôèëü ìàòðèöû âåäóùåãî áëîêà ìàòðèö ïî ôîðìóëàì (5); 3) ñ ïîìîùüþ îïåðàöèè ìóëüòèðàññûëêè âû÷èñëåííûé âåäóùèì ïðîöåññîì ìàññèâ ýëåìåíòîâ lik è di (k i� � 1 1, , ; i I I s n� � � �1, , min{ , }) âåäóùåãî áëîêà ðàññûëàåòñÿ âñåì ïðîöåññàì; 4) ïðîâåðêà âûïîëíåíèÿ óñëîâèé ïîëîæèòåëüíîé îïðåäåëåííîñòè (di � 0) èëè íåâûðîæäåííîñòè ( | | | | | |d Ai � macheps ) èñõîäíîé ìàòðèöû A îäíîâðåìåííî âñåìè ïðîöåññàìè äëÿ i I I s n� � � �1, , min{ , }.  ýòîì àëãîðèòìå âû÷èñëåíèÿ ìîæíî ïðîâîäèòü òîëüêî ñ çàâåäîìî íåíóëå- âûìè ýëåìåíòàìè ìàòðèö (èñõîäíîé è òðåóãîëüíîãî ðàçëîæåíèÿ), èñïîëüçóÿ, íà- ïðèìåð, ñõåìó çàäàíèÿ ãðóïïàìè òàêèõ ýëåìåíòîâ. Îäíàêî íàêëàäíûå ðàñõîäû íà ïîèñê òàêèõ ýëåìåíòîâ ìîãóò ïðåâûñèòü âûèãðûø îò ñîêðàùåíèÿ êîëè÷åñòâà àðèôìåòè÷åñêèõ îïåðàöèé. Ýôôåêòèâíîå èñïîëüçîâàíèå îäíîìåðíûõ áëî÷íûõ àëãîðèòìîâ âîçìîæíî ïðè õîðîøåé ñáàëàíñèðîâàííîñòè çàãðóçêè ïðîöåññîâ, íå äîïóñêàþùåé ïðîñòîåâ îòäåëüíûõ ïðîöåññîâ ïðè âûïîëíåíèè âû÷èñëåíèé.  îáùåì ñëó÷àå ýòîãî ìîæíî äîñòè÷ü äëÿ ëåíòî÷íûõ ìàòðèö. Åñëè êîëè÷åñòâî ýëåìåíòîâ, ñ êîòîðûìè ïðîâî- äÿòñÿ îïåðàöèè, â ñòðîêàõ ïðîôèëÿ ìàòðèöû ñóùåñòâåííî îòëè÷àåòñÿ, òî âû÷èñ- ëåíèÿ ìîãóò ïîòðåáîâàòü òàêîãî æå âðåìåíè, êàê è â ñëó÷àå ëåíòî÷íîé ìàòðèöû ñ øèðèíîé ëåíòû, ðàâíîé ìàêñèìàëüíîìó êîëè÷åñòâó ýëåìåíòîâ ïðîôèëÿ â îäíîé ñòðîêå. Äëÿ ðàçðåæåííûõ ñèììåòðè÷íûõ ìàòðèö íåðåãóëÿðíîé ñòðóêòóðû ÷àñòî ìîæíî äîñòè÷ü ëó÷øåé ñáàëàíñèðîâàííîñòè, åñëè îïåðèðîâàòü âåðõíåé òðå- óãîëüíîé ìàòðèöåé U è èñïîëüçîâàòü U DUT -ðàçëîæåíèå ìàòðèöû.  ýòîì ñëó- ÷àå ïðè èñïîëüçîâàíèè ñõåìû çàäàíèÿ íåíóëåâûõ ýëåìåíòîâ ãðóïïàìè è îäíî- ìåðíîãî áëî÷íîãî öèêëè÷åñêîãî èëè ñòðî÷íî-öèêëè÷åñêîãî ðàñïðåäåëåíèÿ äàí- íûõ äëÿ ìàòðèöû U ìåæäó ïðîöåññàìè ìîæíî äîñòè÷ü áîëåå ðàâíîìåðíîé çàãðóçêè ïðîöåññîâ. Íèæå ïðèâåäåí îäíîìåðíûé áëî÷íûé öèêëè÷åñêèé ïàðàëëåëüíûé àëãîðèòì äëÿ ýòîãî ñëó÷àÿ. Äëÿ êàæäîãî I s s N N s n s� � � � �0 2 1, , , , , ( ) / (çäåñü, êàê è âûøå, s — ÷èñëî ñòðîê â áëîêå è çíà÷åíèå � �a ðàâíî öåëîé ÷àñòè ÷èñëà a) âûïîëíÿåòñÿ ïîñëåäîâà- òåëüíîñòü îïåðàöèé: 1) ñ ïîìîùüþ îïåðàöèè ìóëüòèðàññûëêè ìàññèâ íåíóëåâûõ ýëåìåíòîâ èç (7) t ik I( ) (k I n� � �1, , ; i I I s n� � � �1, , min{ , }) ( / )I s�1 -ãî áëîêà, êîòîðûé äàëåå íà- çûâàåòñÿ âåäóùèì, ðàññûëàåòñÿ âñåì ïðîöåññàì; 2) äëÿ i I I s n� � � �1, , min{ , } • êàæäûì ïðîöåññîì ïðîâîäèòñÿ ïðîâåðêà âûïîëíåíèÿ óñëîâèé ïîëîæè- òåëüíîé îïðåäåëåííîñòè (di � 0) èëè íåâûðîæäåííîñòè (| | | | | |d Ai � macheps ) èñõîäíîé ìàòðèöû A; • êàæäûì ïðîöåññîì ïî ôîðìóëàì (6) âû÷èñëÿþòñÿ çíà÷åíèÿ 1/ di è íåíó- ëåâûõ ýëåìåíòîâ èik (k i n� � �1, , ), âõîäÿùèõ â ( )i I -þ ñòðîêó âåäóùåãî áëîêà òðåóãîëüíîãî ðàçëîæåíèÿ; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 167 • êàæäûì ïðîöåññîì âû÷èñëÿþòñÿ çíà÷åíèÿ íåíóëåâûõ ýëåìåíòîâ t jk i( ) ( , , ; , ,k i n j i n� � � � � �1 1 ) ïî ôîðìóëàì (7) âåäóùåãî áëîêà è îñòàëü- íûõ áëîêîâ â ñîîòâåòñòâèè ñî ñõåìîé ðàñïðåäåëåíèÿ ìåæäó ïðîöåññàìè ýëåìåíòîâ èñõîäíîé ìàòðèöû A. ÝÔÔÅÊÒÈÂÍÎÑÒÜ ÀËÃÎÐÈÒÌΠÄëÿ îöåíêè êà÷åñòâà ïàðàëëåëüíûõ àëãîðèòìîâ èñïîëüçóþòñÿ òàêèå êðèòåðèè, êàê êîýôôèöèåíòû óñêîðåíèÿ è ýôôåêòèâíîñòè, êîòîðûå ñîîòâåòñòâåííî ìîãóò áûòü îïðåäåëåíû ñëåäóþùèì îáðàçîì: S Ò Òð ð� 1 / , (8) E S ðð ð� / , (9) ãäå ð — êîëè÷åñòâî ïðîöåññîâ, èñïîëüçóåìûõ äëÿ ðåøåíèÿ çàäà÷è, Ò ð — âðåìÿ ðåøåíèÿ çàäà÷è íà MIMD-êîìïüþòåðå ñ èñïîëüçîâàíèåì ð ïðîöåññîâ, Ò1 — âðåìÿ ðåøåíèÿ òîé æå çàäà÷è íà ãèïîòåòè÷åñêîì ïîñëåäîâàòåëüíîì êîìïüþòåðå ñ áûñòðîäåéñòâèåì îäíîãî ïðîöåññîðà è îïåðàòèâíîé ïàìÿòüþ, êîòîðàÿ ðàâíà ñóììàðíîé ïàìÿòè, èñïîëüçóåìîé ð ïðîöåññàìè. Âû÷ècëèì âðåìåíà âûïîëíåíèÿ ïîñëåäîâàòåëüíîãî è ïàðàëëåëüíîãî àëãî- ðèòìîâ äëÿ íàõîæäåíèÿ êîýôôèöèåíòîâ (8) è (9) (èñïîëüçóÿ îáîçíà÷åíèÿ èç [2]) T O t1 1� , (10) T O t O t O tp p� � �o o c c, (11) ãäå t — ñðåäíåå âðåìÿ âûïîëíåíèÿ îäíîé àðèôìåòè÷åñêîé îïåðàöèè (ñëîæå- íèå èëè óìíîæåíèå) ñ ïëàâàþùåé çàïÿòîé, O1 è O p — êîëè÷åñòâî òàêèõ àðèôìåòè÷åñêèõ îïåðàöèé, âûïîëíÿåìûõ îäíèì ïðîöåññîì, äëÿ ïîñëåäîâà- òåëüíîãî è ïàðàëëåëüíîãî àëãîðèòìîâ ñîîòâåòñòâåííî, tî — âðåìÿ, íåîáõîäè- ìîå äëÿ îáìåíà îäíèì ìàøèííûì ñëîâîì ìåæäó äâóìÿ ïðîöåññàìè, Oo — êî- ëè÷åñòâî òàêèõ îáìåíîâ, âûïîëíÿåìûõ îäíèì ïðîöåññîì, tc — âðåìÿ, íåîá- õîäèìîå äëÿ ñèíõðîíèçàöèè äâóõ ïðîöåññîâ, Oc — êîëè÷åñòâî òàêèõ ñèíõðîíèçàöèé, âûïîëíÿåìûõ îäíèì ïðîöåññîì. Îáîçíà÷èì � i êîëè÷åñòâî íåíóëåâûõ ýëåìåíòîâ â i-é ñòðîêå âåðõíåé òðåóãîëü- íîé ìàòðèöû U DUT -ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû. Òîãäà ñïðà- âåäëèâà òåîðåìà, àíàëîãè÷íàÿ òåîðåìå 2.1.2 èç [5] äëÿ LLT -ðàçëîæåíèÿ. Òåîðåìà 1. Äëÿ LDLT -ðàçëîæåíèÿ èëè U DUT -ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû òðåáóåòñÿ O i i n 1 2 1 � � � � àðèôìåòè÷åñêèõ îïåðàöèé ñ ïëàâà- þùåé çàïÿòîé. Äîêàçàòåëüñòâî. Ëåãêî óâèäåòü, ÷òî ôîðìóëû (6), (7) ìîãóò áûòü ïîëó÷åíû èç (5) è íàîáîðîò — ìåíÿåòñÿ òîëüêî ïîðÿäîê âû÷èñëåíèé. Ñëåäîâàòåëüíî, êîëè- ÷åñòâà àðèôìåòè÷åñêèõ îïåðàöèé ïðè LDLT -ðàçëîæåíèè è U DUT -ðàçëîæåíèè ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû ñîâïàäàþò. Ïîýòîìó ïîäñ÷èòàåì êîëè÷å- ñòâî ýòèõ îïåðàöèé ïðè U DUT -ðàçëîæåíèè. Íà i-ì (i n� �1 2, , , ) øàãå äëÿ ïðåîáðàçîâàíèÿ âåäóùåé ñòðîêè ñîãëàñíî (6) íåîáõîäèìî âûïîëíèòü îäíî äåëåíèå è � i 1 óìíîæåíèå. À äëÿ ïðåîáðàçîâàíèÿ ñîãëàñíî (7) ýëåìåíòîâ k-é èç � i 1 ñòðîêè, íîìåðà êîòîðûõ ñîîòâåòñòâóþò èí- äåêñàì íåíóëåâûõ ýëåìåíòîâ âåäóùåé ñòðîêè, — ïî � i k óìíîæåíèé è ñëîæå- 168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 íèé, ãäå k i� � 1 2 1, , , � . Òàêèì îáðàçîì, îáùåå êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé ñ ïëàâàþùåé çàïÿòîé íà i-ì øàãå ñîñòàâëÿåò � � � �i i i i� �( )1 2 . Îòñþ- äà èìååì O i i n 1 2 1 � � � � . � Çàìåòèì, ÷òî äëÿ ëåíòî÷íîé ñèììåòðè÷íîé ìàòðèöû � i m n i� �min{ , } 1 . Ñëåäîâàòåëüíî, äëÿ òðåóãîëüíîãî ðàçëîæåíèÿ (LDLT èëè U DUT ) òðåáóåòñÿ O nm O nm m1 2 2� � �( ) àðèôìåòè÷åñêèõ îïåðàöèé ñ ïëàâàþùåé çàïÿòîé. Äàëåå, äëÿ îïðåäåëåíèÿ Ò ð èç (8) íåîáõîäèìî îöåíèòü O O Op , ,ñ î èç (11).  èäåàëüíîì ñëó÷àå O O pp � 1 / . Îäíàêî ýòî âîçìîæíî ïðè ïîëíîé ñáàëàíñèðî- âàííîñòè çàãðóçêè ïðîöåññîâ íà êàæäîì øàãå àëãîðèòìà. Íàïðèìåð, â ïðèâåäåí- íûõ âûøå àëãîðèòìàõ ÷àñòü âû÷èñëåíèé âûïîëíÿåòñÿ áåç ðàñïàðàëëåëèâàíèÿ — èëè òîëüêî îäíèì ïðîöåññîì, èëè âñå ïðîöåññû âûïîëíÿþò îäíè è òå æå âû÷èñëåíèÿ ñ îäíèìè è òåìè æå äàííûìè.  ìîíîãðàôèè [2] ïðèâåäåíû îöåíêè çíà÷åíèé O O Op , ,ñ î è êîýôôèöèåíòîâ óñêîðåíèÿ è ýôôåêòèâíîñòè óïîìÿíóòûõ âûøå àëãîðèòìîâ LDLT -ðàçëîæåíèÿ ëåíòî÷íûõ, ïðîôèëüíûõ è áëî÷íî-äèàãîíàëüíûõ ñ îêàéìëåíèåì ñèììåòðè÷íûõ ìàòðèö. Íàïðèìåð, êîýôôèöèåíòû óñêîðåíèÿ è ýôôåêòèâíîñòè îäíîìåðíîãî áëî÷íîãî ïàðàëëåëüíîãî àëãîðèòìà LDLT -ðàçëîæåíèÿ ëåíòî÷íîé ñèììåòðè÷íîé ìàòðèöû ïðè n sp� 2 è m sp� ìîæíî îöåíèòü êàê S p p s m p p m p b� � � � ( ( )( ) )1 2 1 1 2 1 1log � , E S p p p � , ãäå m — øèðèíà ëåíòû, s — êîëè÷åñòâî ñòðîê â áëîêå, �1 1 b t t sm t t � �o c , à áëî÷íîãî ïàðàëëåëüíîãî àëãîðèòìà LDLT -ðàçëîæåíèÿ óçêîé ëåíòî÷íîé ñèì- ìåòðè÷íîé ìàòðèöû êàê S p m p n p m p p � � � � � � � � � � � � 4 1 1 2 1 4 7 18 3 2 1 1 � , E S p p p � ; åñëè 1 2 1 4 7 18 3 2 11 m p n p m p � � � � � ���� , òî E m p n p m p p � � � � � �0 25 1 8 1 16 7 18 3 2 1, � , ãäå �1 2 2 � � t t m t t o c . Áîëåå ïîäðîáíî îñòàíîâèìñÿ íà îöåíêàõ O O Op , ,ñ î äëÿ ïðåäëîæåííîãî âûøå îäíîìåðíîãî áëî÷íî-öèêëè÷åñêîãî àëãîðèòìà U DUT -ðàçëîæåíèÿ ìàòðè- öû (â ôîðìå âíåøíèõ ïðîèçâåäåíèé). Òåîðåìà 2. Îäíîìåðíûé áëî÷íûé öèêëè÷åñêèé àëãîðèòì U DUT -ðàçëîæåíèÿ ðàçðåæåííîé ìàòðèöû òðåáóåò âûïîëíåíèÿ íå ìåíåå O p pp i i n i i n 0 2 1 1 1 1� � � � � � � � � � �� �( ) àðèôìåòè÷åñêèõ îïåðàöèé ñ ïëàâàþùåé çàïÿòîé, ò.å. O Op p� 0 . Äîêàçàòåëüñòâî. Âñå p ïðîöåññîâ ïðè U DUT -ðàçëîæåíèè ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû îäíîìåðíûì áëî÷íûì öèêëè÷åñêèì ïàðàëëåëüíûì àëãî- ðèòìîì âûïîëíÿþò O p O1 1� �( ) ( ) àðèôìåòè÷åñêèõ îïåðàöèé ñ ïëàâàþùåé çà- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 169 ïÿòîé, ãäå O ( )� — êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé ñ ïëàâàþùåé çàïÿòîé, êîòîðûå âûïîëíÿþòñÿ áåç ðàñïàðàëëåëèâàíèÿ — èëè òîëüêî îäíèì ïðîöåññîì, èëè âñåìè ïðîöåññàìè ñ îäíèìè è òåìè æå äàííûìè. Ýòè ïðåîáðàçîâàíèÿ ïðîâî- äÿòñÿ ïî ôîðìóëàì (6) è (7) íåíóëåâûõ ýëåìåíòîâ âåäóùåãî áëîêà. Ëåãêî óâè- äåòü, ÷òî O ( )� îãðàíè÷åíî ñíèçó âåëè÷èíîé � �i i I I s n I s n s i i n � � � � � � � �� �� 10 1 1 min{ },( )/ — êîëè÷å- ñòâîì îïåðàöèé, âûïîëíÿåìûõ ïî ïðåîáðàçîâàíèÿì (6). Ýòà âåëè÷èíà óâåëè÷èâà- åòñÿ íà êîëè÷åñòâî îïåðàöèé â ïðåîáðàçîâàíèÿõ (7) íåíóëåâûõ ýëåìåíòîâ ñòðîê âåäóùåãî áëîêà, íîìåðà êîòîðûõ ñîîòâåòñòâóþò èíäåêñàì íåíóëåâûõ ýëåìåíòîâ òåêóùåé âåäóùåé ñòðîêè. Ñëåäîâàòåëüíî, O i i n ( )� � � � � 1 .  ïðåäïîëîæåíèè ïîë- íîé ñáàëàíñèðîâàííîñòè çàãðóçêè ïðîöåññîâ íà êàæäîì øàãå àëãîðèòìà êàæäûé ïðîöåññ âûïîëíÿåò íå ìåíåå ( ( ) ) /( )O p O p O p1 01� �� àðèôìåòè÷åñêèõ îïåðà- öèé ñ ïëàâàþùåé çàïÿòîé.  îáùåì ñëó÷àå âåëè÷èíà O p1 / çàìåíÿåòñÿ ñóììîé íàèáîëüøèõ êîëè÷åñòâ îïåðàöèé, âûïîëíÿåìûõ îäíèì ïðîöåññîì íà êàæäîì øàãå öèêëà ïî I. Òàêèì îáðàçîì, O O p O p Op p� � ��( ( ) ) /( ) 1 01 . � Òåîðåìà 3. Åñëè äëÿ ìóëüòèðàññûëêè íåíóëåâûõ ýëåìåíòîâ âåäóùåãî áëîêà èñïîëüçóåòñÿ àëãîðèòì äåðåâà, òî êîëè÷åñòâî îáìåíîâ (ñèíõðîíèçàöèé) ìåæäó ïðîöåññàìè äëÿ îäíîìåðíîãî áëî÷íî-öèêëè÷åñêîãî ïàðàëëåëüíîãî àëãîðèòìà U DUT -ðàçëîæåíèÿ ðàçðåæåííîé ìàòðèöû îöåíèâàåòñÿ âåëè÷èíîé O n s pc log� 2 , à îáùåå êîëè÷åñòâî äàííûõ, êîòîðûìè îáìåíèâàþòñÿ ïðîöåññû, ñîñòàâëÿåò ïðè- áëèçèòåëüíî O p i i n o log� � �2 1 � äâîéíûõ ñëîâ. Äîêàçàòåëüñòâî. Íà êàæäîì øàãå öèêëà ïî I âûïîëíÿåòñÿ ïî îäíîé îïåðà- öèè ìóëüòèðàññûëêè ìàññèâà èç � i i I I s n � � � � 1 min{ }, íåíóëåâûõ ýëåìåíòîâ âåäóùåãî áëîêà. Åñëè äëÿ ýòîé îïåðàöèè èñïîëüçóåòñÿ àëãîðèòì äåðåâà [17], òî ïðè îäíîé ìóëü- òèðàññûëêå âûïîëíÿåòñÿ ïðèáëèçèòåëüíî log 2 p ñèíõðîíèçàöèé, à îáùåå ÷èñëî äàííûõ, êîòîðûìè ïðîöåññû îáìåíèâàþòñÿ, ñîñòàâëÿþò ïðèáëèçèòåëüíî log min{ } 2 1 p i i I I s n � � � � � , . Ñëåäîâàòåëüíî, îáùåå êîëè÷åñòâî ñèíõðîíèçàöèé îöåíèâàåòñÿ âåëè÷èíîé O n s pñ log� ( / ) 2 , ïðè ýòîì îáùåå êîëè÷åñòâî äàííûõ, êîòîðûìè îá- ìåíèâàþòñÿ ïðîöåññû, ñîñòàâëÿåò ïðèáëèçèòåëüíî O p i i n o log� � �2 1 � . � Òàêèì îáðàçîì, èñïîëüçóÿ ðåçóëüòàòû òåîðåì 2 è 3 è ñ ó÷åòîì (11), èìååì T t p p t p n s tp i i n i i n � � � � � � � � � � � � �� �2 1 1 21( ) c olog log 2 1 p i i n � � � . Ñëåäîâàòåëüíî, ñ ó÷åòîì òàêæå ðåçóëüòàòîâ òåîðåìû 1 è âûðàæåíèé (8)–(10) äëÿ êîýôôèöèåíòà óñêîðåíèÿ îäíîìåðíîãî áëî÷íîãî öèêëè÷åñêîãî ïàðàëëåëüíî- ãî àëãîðèòìà U DUT -ðàçëîæåíèÿ ðàçðåæåííîé ñèììåòðè÷íîé ìàòðèöû ñïðàâåä- ëèâà îöåíêà ñâåðõó S p p O p p O p i i n s� � � � � � � � � �1 1 1 1 2 1 1 1 � � log , (12) 170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 à òàêæå îöåíêà E p O p p O p i i n s� � � � � � � � �1 1 1 1 2 1 1� � log äëÿ êîýôôèöèåíòà ýôôåêòèâíîñòè, ãäå � �1 1 s i i nt t n s t t � � � �c o . ÀÏÐÎÁÀÖÈß ÀËÃÎÐÈÒÌΠÍà îñíîâå ïðåäëîæåííûõ ïàðàëëåëüíûõ àëãîðèòìîâ ðàçðàáîòàíî ñîîòâåòñòâó- þùåå ïðîãðàììíîå îáåñïå÷åíèå äëÿ ñðåäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ Ìв. Ïîëó÷åíû ðåøåíèÿ ðÿäà çàäà÷ íà êëàñòåðå ÑÊÈÒ è èíòåëëåêòóàëüíîì ïàðàëëåëüíîì êîìïüþòåðå Èíïàðêîì [18].  ðàáîòàõ [2, 15, 16, 18] ïðèâåäåíû ìíîãî÷èñëåííûå ðåçóëüòàòû àïðîáàöèè ïðåäëîæåííûõ ïàðàëëåëüíûõ àëãîðèòìîâ. Íèæå äàíû ðåçóëüòàòû òåñòèðîâàíèÿ îäíîìåðíîãî áëî÷íîãî öèêëè÷åñêîãî ïàðàëëåëüíîãî àëãîðèòìà ðåøåíèÿ ÑËÀÓ ñ ðàçðåæåííûìè ìàòðèöàìè, êîòîðûé èñïîëüçóåò U DUT -ðàçëîæåíèå ìàòðèöû.  òàáë. 1 ïðèâåäåíû ðåçóëüòàòû àïðîáàöèè îäíîìåðíîãî áëî÷íîãî öèêëè÷åñ- êîãî ïàðàëëåëüíîãî àëãîðèòìà íà ðåøåíèè íåñêîëüêèõ ÑËÀÓ ñ ðàçðåæåííûìè ìàòðèöàìè. Ïðè ýòîì äëÿ êàæäîé èç çàäà÷ ïðîâîäèëîñü ðåøåíèå ñ ìàòðèöåé èñ- õîäíîé (íåîïòèìèçèðîâàííîé) ñòðóêòóðû è ïåðåóïîðÿäî÷åííîé (îïòèìèçèðîâàí- íîé) ñòðóêòóðû ñ ïîìîùüþ àëãîðèòìà ìèíèìàëüíîé ñòåïåíè — â òàáëèöå ýòè ñëó- ÷àè ðàçëè÷àþòñÿ çíà÷åíèÿìè øèðèíû ëåíòû è çàïîëíåííîñòè ïðîôèëÿ ìàòðèö. Ò à á ë è ö à 1 Ïîðÿäîê ñèñòåìû Çíà÷åíèå øèðèíû ëåíòû Çàïîë- íåííîñòü, % Âðåìÿ (ìèí) ðàáîòû ïðîãðàììû äëÿ ïðîöåññîâ 1 8 16 32 64 128 44 436 4 475 21 2,17 0,38 0,30 0,22 0,20 0,18 44 436 37 580 2 0,95 0,17 0,12 0,12 0,12 0,08 283 031 19 530 7 32,00 5,95 3,27 2,30 2,03 2,05 283 031 281 341 1 9,67 2,20 1,05 0,68 0,67 0,58 661 590 34 242 5 98,80 17,60 10,08 6,57 5,45 5,22 661 590 541 257 1 56,20 14,67 7,12 3,80 2,57 2,10 Ïðèâåäåííûå â òàáëèöå âðåìåíà ïîëó÷åíû ïðè ðàçìåðå áëîêà s �1.  îòëè- ÷èå îò ïëîòíûõ ìàòðèö, ëåíòî÷íîãî èëè ïðîôèëüíîãî ïðåäñòàâëåíèÿ ìàòðèö â ðàññìàòðèâàåìîì ñëó÷àå îïòèìàëüíûé ðàçìåð áëîêà íåîáõîäèìî ïîäáèðàòü äëÿ êàæäîé êîíêðåòíîé çàäà÷è â çàâèñèìîñòè îò ðàçìåùåíèÿ íåíóëåâûõ ýëåìåíòîâ. Ïîýòîìó äëÿ ñðàâíåíèÿ ïðîèçâîäèòåëüíîñòè àëãîðèòìà íà ðàçëè÷íûõ çàäà÷àõ èñ- ïîëüçîâàëñÿ èìåííî ñòðî÷íî-öèêëè÷åñêèé âàðèàíò, êîòîðûé îáåñïå÷èâàåò, êàê ïðàâèëî, íàèëó÷øóþ ñáàëàíñèðîâàííîñòü çàãðóçêè ïðîöåññîâ. Íà ðèñ. 4 ïðèâåäåíû çàâèñèìîñòè óñêîðåíèÿ è ýôôåêòèâíîñòè àëãîðèòìà îò êîëè÷åñòâà ïðîöåññîâ äëÿ ïðèâåäåííûõ â òàáë. 1 äâóõ çàäà÷: ñ ìàòðèöåé èñõîä- íîé ñòðóêòóðû (è) è ñ ïåðåóïîðÿäî÷åííîé ñòðóêòóðîé (ï). Íà ðèñ. 5 ïðèâåäåíû çàâèñèìîñòè óñêîðåíèÿ ðàññìàòðèâàåìîãî àëãîðèòìà îò êîëè÷åñòâà ïðîöåññîâ ïðè ðàçëè÷íûõ ïîðÿäêàõ ÑËÀÓ, ïðèâåäåííûõ â òàáë. 1 (ñ ïåðåóïîðÿäî÷åííîé ìàòðèöåé). Ïðèâåäåííûå â òàáë. 1 è íà ðèñ. 4, 5 ðåçóëüòàòû äåìîíñòðèðóþò çàâèñèìîñòü õà- ðàêòåðèñòèê àëãîðèòìà (âðåìåíè ðåøåíèÿ, óñêîðåíèÿ, ýôôåêòèâíîñòè) îò ñáàëàíñèðî- âàííîñòè çàãðóçêè ïðîöåññîâ. Ïðè ýòîì ÷åì ìåíüøå ïîðÿäîê ñèñòåìû, òåì òðóäíåå äîñòè÷ü ñáàëàíñèðîâàííîñòè ïðè íàðàùèâàíèè ÷èñëà ïðîöåññîâ (ñì. ðèñ. 5). ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 171 Ñëåäóåò òàêæå îòìåòèòü, ÷òî â íåêîòîðûõ ñëó÷àÿõ ïðè ëó÷øåé ñáàëàíñèðî- âàííîñòè çàãðóçêè ïðîöåññîâ ìîãóò áûòü äîñòèãíóòû ëó÷øèå âðåìåííûå ïîêàçà- òåëè ïðè ïðîôèëüíîì ïðåäñòàâëåíèè ìàòðèöû ñèñòåìû è èñïîëüçîâàíèè ñîîò- 172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 0 2 4 6 8 10 12 14 1 8 16 32 64 128 êîëè÷åñòâî ïðîöåññîâ Ó ñ êî ð å í è å 0,00 0,20 0,40 0,60 0,80 1,00 1,20 Ý ô ô å êò è â í î ñ òü Óñêîðåíèå (è) Óñêîðåíèå (ï) Ýôôåêòèâíîñòü (è) Ýôôåêòèâíîñòü (ï) 0 5 10 15 20 25 30 1 8 16 32 64 128 Êîëè÷åñòâî ïðîöåññîâ Ó ñ êî ð å í è å 0,00 0,20 0,40 0,60 0,80 1,00 1,20 Ý ô ô å êò è â í î ñ ò ü Ðèñ 4. Çàâèñèìîñòè óñêîðåíèÿ è ýôôåêòèâíîñòè àëãîðèòìà îò êîëè÷åñòâà ïðîöåññîâ äëÿ ÑËÀÓ ïîðÿäêà 44 436 (à) è äëÿ ÑËÀÓ ïîðÿäêà 661590 (á) a á 0 5 10 15 20 25 30 1 8 16 32 64 128 Êîëè÷åñòâî ïðîöåññîâ Ó ñ êî ð å í è å n = 44436 n = 283 031 n = 661 590 Ðèñ. 5. Çàâèñèìîñòè óñêîðåíèÿ àëãîðèòìà îò êîëè÷åñòâà ïðîöåññîâ äëÿ ÑËÀÓ ðàçëè÷íûõ ïîðÿäêîâ âåòñòâóþùåãî ïàðàëëåëüíîãî àëãîðèòìà (îäíîìåðíîãî áëî÷íîãî öèêëè÷åñêîãî). Òàê, èñïîëüçóÿ 16 ïðîöåññîâ äëÿ ðåøåíèÿ ÑËÀÓ ñ èñõîäíîé (íåïåðåóïîðÿäî÷åí- íîé) ñòðóêòóðîé ìàòðèöû ïîðÿäêà 44 436 ïîòðåáîâàëîñü 0,16 ìèí, ñèñòåìû ïî- ðÿäêà 283 031 — 1,29 ìèí è äëÿ ñèñòåìû ïîðÿäêà 661 590 — 6,00 ìèí. Âûáîð íàèáîëåå ýôôåêòèâíîãî ïàðàëëåëüíîãî àëãîðèòìà ìîæíî ñäåëàòü ëèøü íà îñíî- âàíèè ýêñïåðèìåíòàëüíûõ äàííûõ, òàê êàê ñáàëàíñèðîâàííîñòü çàãðóçêè ìîæåò ñóùåñòâåííî ìåíÿòüñÿ ïðè èçìåíåíèè êîëè÷åñòâà ïðîöåññîâ. Ïðèâåäåì ðåçóëüòàòû ðåøåíèÿ äâóõ çàäà÷ áîëüøîãî îáúåìà.  òàáë. 2 äàíû âðåìåííûå õàðàêòåðèñòèêè ðåøåíèÿ ÑËÀÓ ñ 5 371 727 íåèçâåñòíûìè ïðè ðàñ÷å- òå íà ïðî÷íîñòü êîíñòðóêöèè äåëîâîãî öåíòðà, ñîñòîÿùåé èç äâóõ áàøåí. Âðåìÿ ðåøåíèÿ ýòîé çàäà÷è áåç ðàñïàðàëëåëèâàíèÿ ñîñòàâëÿåò ïðèáëèçèòåëüíî 115 ÷àñ.  òàáë. 3 ïðèâåäåíû âðåìåííûå õàðàêòåðèñòèêè ðåøåíèÿ ÷àñòè÷íîé îáîáùåííîé ÀÏÑÇ ïîðÿäêà 2 385 822 ñ èñïîëüçîâàíèåì 247 ïðîöåññîâ. Äëÿ ïðîôèëüíîãî ïðåäñòàâëåíèÿ ìàòðèöû øèðèíà ëåíòû ñîñòàâëÿåò 115480 ÷àñ, çàïîëíåííîñòü — 3 %. Äëÿ íåáîñêðåáíîãî ïðåäñòàâëåíèÿ øèðèíà ëåíòû 2 051 632 ÷àñ, çàïîëíåííîñòü — ìåíåå 1%). Ïðè èññëåäîâàíèè äîñòîâåðíîñòè â ñëó÷àå íåáîñêðåáíîãî ïðåäñòàâëåíèÿ îïðåäåëÿëèñü òîëüêî îöåíêè âû÷èñëèòåëüíîé ïîãðåøíîñòè. Âðåìÿ ðåøåíèÿ ýòîé çàäà÷è áåç ðàñïàðàëëåëèâàíèÿ ïðåâûøàåò 15 ÷àñ. ÇÀÊËÞ×ÅÍÈÅ Äëÿ çàäà÷ ñ ðàçðåæåííûìè ñèììåòðè÷íûìè ìàòðèöàìè ïðåäëîæåíû ðàçëè÷íûå ïà- ðàëëåëüíûå àëãîðèòìû, êîòîðûå îáåñïå÷èâàþò âûñîêóþ ýôôåêòèâíîñòü ðàñïàðàë- ëåëèâàíèÿ, ó÷èòûâàþò ñòðóêòóðó ðàçðåæåííûõ ìàòðèö è èõ çàïîëíåííîñòü. Îïðå- äåëåíû íåêîòîðûå êðèòåðèè âûáîðà àëãîðèòìîâ äëÿ ðåøåíèÿ êîíêðåòíîé çàäà÷è. Äëÿ ðàçðåæåííûõ ìàòðèö íåðåãóëÿðíîé ñòðóêòóðû ðàçðàáîòàí è ïðîãðàììíî ðåàëèçîâàí îäíîìåðíûé áëî÷íûé öèêëè÷åñêèé ïàðàëëåëüíûé àëãîðèòì, â ðÿäå ñëó÷àåâ îáåñïå÷èâàþùèé ëó÷øåå áàëàíñèðîâàíèå ïðîöåññîâ äëÿ ðàçðåæåííîãî ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 173 Ò à á ë è ö à 2 Ýòàïû àëãîðèòìà Âðåìÿ (÷àñ:ìèí) ðåøåíèÿ (äëÿ ïðîöåññîâ) 48 64 96 128 192 224 256 ×òåíèå äàííûõ èç ôàéëà 0:32 0:32 0:44 0:44 0:42 0:42 0:42 Òðåóãîëüíîå ðàçëîæåíèå ìàòðèöû 9:14 8:22 6:24 5:12 4:38 4:19 4:07 Èññëåäîâàíèå ñâîéñòâ ÑËÀÓ 0:23 0:20 0:13 0:09 0:06 0:05 0:04 Ðåøåíèå òðåóãîëüíûõ ñèñòåì 0:11 0:10 0:06 0:04 0:03 0:02 0:02 Âñåãî âðåìåíè 10:22 9:24 7:27 6:09 5:29 5:08 4:55 Ò à á ë è ö à 3 Ýòàïû ðåøåíèÿ çàäà÷è Âðåìÿ (÷àñ:ìèí) ðåøåíèÿ ÀÏÑÇ ïîðÿäêà 2 385 822 Ïðîôèëüíîå ïðåäñòàâëåíèå Íåáîñêðåáíîå ïðåäñòàâëåíèå ×òåíèå äàííûõ Ðåøåíèå ÀÏÑÇ: 0:38,2 0:06,2 Òðåóãîëüíîå ðàçëîæåíèå ìàòðèöû 0:25,6 0:13,3 Èòåðàöèîííûå ïðîöåññû 0:03,9 0:18,9 Èññëåäîâàíèå äîñòîâåðíîñòè 0:48,3 0:03,7 Ñîõðàíåíèå ðåçóëüòàòîâ ðåøåíèÿ 1:35,5 1:22,3 òèïà äàííûõ. Ðàçðàáîòàííûé àëãîðèòì ïîçâîëÿåò ðàñïðåäåëèòü ìåæäó ïðîöåññà- ìè íåíóëåâûå ýëåìåíòû òðåóãîëüíîãî ðàçëîæåíèÿ ðàçðåæåííîé ìàòðèöû òàêèì îáðàçîì, ÷òîáû âû÷èñëåíèÿ ïðîâîäèëèñü îäíîâðåìåííî áîëüøèíñòâîì ïðîöåñ- ñîâ. Ïðåäëîæåíû ýôôåêòèâíûå ñõåìû ðàñïðåäåëåíèÿ äàííûõ ìåæäó ïðîöåññàìè. Ïîëó÷åíû îöåíêè ñâåðõó êîýôôèöèåíòîâ óñêîðåíèÿ è ýôôåêòèâíîñòè ðàññìàòðè- âàåìûõ ïàðàëëåëüíûõ àëãîðèòìîâ. Äàëüíåéøèå èññëåäîâàíèÿ, íàïðàâëåííûå íà ïîèñê àëãîðèòìîâ ïåðåóïîðÿ- äî÷åíèÿ ðàçðåæåííûõ ìàòðèö, îáåñïå÷àò âûñîêóþ ýôôåêòèâíîñòü òîãî èëè èíîãî ïàðàëëåëüíîãî àëãîðèòìà ðåøåíèÿ çàäà÷è ëèíåéíîé àëãåáðû â ïåðâóþ î÷åðåäü çà ñ÷åò ñáàëàíñèðîâàííîñòè çàãðóçêè ïðîöåññîâ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ì î ë ÷ à í î â È . Í . , Õ è ì è ÷ À . Í . , Ï î ï î â À .  . è ä ð . Îá ýôôåêòèâíîé ðåàëèçàöèè âû÷èñëèòåëüíûõ àëãîðèòìîâ íà MIMD-êîìïüþòåðàõ // Èñêóññòâåííûé èíòåëëåêò. — 2005. — ¹ 3. — Ñ. 175–184. 2. Õ è ì è ÷ À . Í . , Ì î ë ÷ à í î â È . Í . , Ï î ï î â À .  . è ä ð . Ïàðàëëåëüíûå àëãîðèòìû ðåøåíèÿ çàäà÷ âû÷èñëèòåëüíîé ìàòåìàòèêè. — Ê.: Íàóê. äóìêà, 2008. — 248 ñ. 3. Ï î ï î â À .  . , Õ è ì è ÷ À . Í . Èññëåäîâàíèå è ðåøåíèå ïåðâîé îñíîâíîé çàäà÷è òåîðèè óïðóãîñòè // Êîìïüþòåðíàÿ ìàòåìàòèêà. — 2003. — ¹ 2. — Ñ. 105–114 4. Ì î ë ÷ à í î â È . Í . , Ï î ï î â À .  . , Õ è ì è ÷ À . Í . Àëãîðèòì ðåøåíèÿ ÷àñòè÷íîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé äëÿ áîëüøèõ ëåíòî÷íûõ ìàòðèö // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1992. — ¹ 2. — Ñ. 141–147. 5. Ä æ î ð ä æ À . , Ë þ Ä æ . ×èñëåííîå ðåøåíèå áîëüøèõ ðàçðåæåííûõ ñèñòåì óðàâíåíèé. — Ì.: Ìèð, 1984. — 334 ñ. 6. Ï è ñ à í å ö ê è Ñ . Òåõíîëîãèÿ ðàçðåæåííûõ ìàòðèö. — Ì.: Ìèð, 1988. — 410 ñ. 7. Ý ñ ò å ð á þ Î . , Ç ë à ò å â Ç . Ïðÿìûå ìåòîäû äëÿ ðàçðåæåííûõ ìàòðèö. — Ì.: Ìèð, 1987. — 118 ñ. 8. Î ð ò å ã à Ä æ . Ââåäåíèå â ïàðàëëåëüíûå è âåêòîðíûå ìåòîäû ðåøåíèÿ ëèíåéíûõ ñèñòåì. — Ì.: Ìèð, 1991. — 367 ñ. 9. Á à ë à í ä è í Ì . Þ . , Ø ó ð è í à Ý . Ï . Ìåòîäû ðåøåíèÿ ÑËÀÓ áîëüøîé ðàçìåðíîñòè. — Íîâîñèáèðñê: Èçä-âî ÍÃÒÓ, 2000. — 70 ñ. 10. à ë ó ø à ê î â à Ò . Í . , Ý ê ñ à ð å â ñ ê à ÿ Ì . Å . Ìåòîäû ðàáîòû ñ ðàçðåæåííûìè ìàòðèöàìè ïðîèçâîëüíîãî òèïà. — Âîðîíåæ: Âîðîíåæñêèé ãîñ. óí-ò, 2005. — 44 ñ. 11. à ë ó ø à ê î â à Ò . Í . , Á ë à ò î â à È . À . Ìåòîäû ðåøåíèÿ ñèñòåì ñ ðàçðåæåííûìè ìàòðèöàìè. — Âîðîíåæ: Âîðîíåæñêèé ãîñ. óí-ò, 2000. — 36 ñ. 12. Ó è ë ê è í ñ î í Ä æ . Õ . , Ð à é í ø Ê . Ñïðàâî÷íèê àëãîðèòìîâ íà ÿçûêå Àëãîë. Ëèíåéíàÿ àëãåáðà. — Ì.: Ìàøèíîñòðîåíèå, 1976. — 389 ñ. 13. × è ñ ë å í í û å ìåòîäû äëÿ ìíîãîïðîöåññîðíîãî âû÷èñëèòåëüíîãî êîìïëåêñà ÅÑ / Â.Ñ. Ìèõàëåâè÷, … , È.Â. Ñåðãèåíêî, …, À.Í. Õèìè÷ è äð. / Ïîä ðåä. È.Í. Ìîë÷àíîâà. — Ì.: Èçä. ÂÂÈÀ èì. Í.Å. Æóêîâñêîãî, 1986. — 401 ñ. 14. http://www.netlib.org/scalapack 15. Ñ å ð ã è å í ê î È .  . , Ä å é í å ê à  . Ñ . , Õ è ì è ÷ À . Í . è ä ð . Èññëåäîâàíèå ñ ïîìîùüþ ìíîãîïðîöåññîðíîãî âû÷èñëèòåëüíîãî êîìïëåêñà ðàñïðåäåëåííûõ ñèñòåì ñ áîëüøèìè îáúåìàìè ñâÿçàííûõ äàííûõ. — Êèåâ, 2005. — 33 ñ. — (Ïðåïð. / ÍÀÍ Óêðàèíû, Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà; 2005-1). 16. Ï î ï î â À .  . , Õ è ì è ÷ À . Í . Ïàðàëëåëüíûé àëãîðèòì ðåøåíèÿ ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé ñ ëåíòî÷íîé ñèììåòðè÷íîé ìàòðèöåé // Êîìïüþòåðíàÿ ìàòåìàòèêà. — 2005. — ¹ 2. — Ñ. 52–59. 17. http://www.mcs.anl.gov/mpi/mpich 18. Õ è ì è ÷ À . Í . , Ì î ë ÷ à í î â È . Í . , Ì î â à  . È . è ä ð . ×èñëåííîå ïðîãðàììíîå îáåñïå÷åíèå MIMD–êîìïüþòåðà Èíïàðêîì. — Êèåâ: Íàóê. äóìêà, 2007. — 222 ñ. Ïîñòóïèëà 04.08.2010 174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6

Ähnliche Einträge