Зображення обкладинки

Измерение производительности параллельных компьютеров с распределенной памятью

Розглянуто основні механізми вимірювання продуктивності паралельних комп’ютерів із розподіленою пам’яттю. Показано, що результати, отримані на де-факто стандартному тесті LINPACK, здебільшого мало пов’язані з ефективністю програм і застосувань. В результаті знову набули актуальності моделі та методи...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Кибернетика и системный анализ
Дата:2009
Автор: Ющенко, Р.А.
Формат: Стаття
Мова:Російська
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2009
Теми:
Программно-технические комплексы
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/44488
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Измерение производительности параллельных компьютеров с распределенной памятью / Р.А. Ющенко // Кибернетика и системный анализ. — 2009. — № 6. — С. 106-117. — Бібліогр.: 16 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859591467018747904
author Ющенко, Р.А.
author_facet Ющенко, Р.А.
citation_txt Измерение производительности параллельных компьютеров с распределенной памятью / Р.А. Ющенко // Кибернетика и системный анализ. — 2009. — № 6. — С. 106-117. — Бібліогр.: 16 назв. — рос.
collection DSpace DC
container_title Кибернетика и системный анализ
description Розглянуто основні механізми вимірювання продуктивності паралельних комп’ютерів із розподіленою пам’яттю. Показано, що результати, отримані на де-факто стандартному тесті LINPACK, здебільшого мало пов’язані з ефективністю програм і застосувань. В результаті знову набули актуальності моделі та методи макроконвеєрних обчислень, сформульовані В.М. Глушковим ще наприкінці 1970-х років Результати цих досліджень висвітлено з позицій сучасної архітектури кластерних комплексів. The basic techniques for measuring the performance of distributed memory parallel computers are reviewed. The results obtained via de-facto standard LINPACK benchmark suite are shown to be weakly related to the efficiency of applied parallel programs. As a result, models and methods of macro-piping computations proposed by V.M. Glushkov in the late 1970s become topical again. These results are presented in the context of the modern architecture of cluster complexes.
first_indexed 2025-11-27T15:16:46Z
format Article
fulltext ÓÄÊ 681.3 Ð. À. ÞÙÅÍÊÎ ÈÇÌÅÐÅÍÈÅ ÏÐÎÈÇÂÎÄÈÒÅËÜÍÎÑÒÈ ÏÀÐÀËËÅËÜÍÛÕ ÊÎÌÏÜÞÒÅÐÎÂ Ñ ÐÀÑÏÐÅÄÅËÅÍÍÎÉ ÏÀÌßÒÜÞ Êëþ÷åâûå ñëîâà: ïàðàëëåëüíûå âû÷èñëåíèÿ, ïðîèçâîäèòåëüíîñòü, îïòèìèçàöèÿ, êîììóíèêàöèîííûå çàòðàòû, êëàñòåðû, ñóïåðêîìïüþòåðû, âûñîêîïðîèçâîäè- òåëüíûå âû÷èñëåíèÿ, îáðàáîòêà äàííûõ, MIMD, HPC. ÂÂÅÄÅÍÈÅ Ñóïåðêîìïüþòåðû èñïîëüçóþò äëÿ ðåøåíèÿ çàäà÷ â òàêîé ïîñòàíîâêå, îáúåìàõ è äåòàëèçàöèè, ñ êîòîðûìè ïåðñîíàëüíûé êîìïüþòåð íå ìîæåò ñïðàâèòüñÿ â ïðèíöèïå èç-çà îãðàíè÷åíèé ïàìÿòè è ïðîèçâîäèòåëüíîñòè. Ñêîðîñòü ñó- ïåðêîìïüþòåðîâ ñóùåñòâåííî âîçðîñëà çà ïîñëåäíåå âðåìÿ è ïðîäîëæàåò ðàñòè áûñòðûìè òåìïàìè. Õîòÿ òàêòîâàÿ ÷àñòîòà ïðîöåññîðîâ äîñòèãëà ôèçè÷åñêîãî ïðåäåëà, ðàñïàðàëëåëèâàíèå àëãîðèòìîâ îòêðûëî âîçìîæíîñòè äëÿ äàëüíåéøåãî óâåëè÷åíèÿ ïðîèçâîäèòåëüíîñòè. Òàêàÿ òåíäåíöèÿ â ðàâíîé ñòåïåíè çàòðîíóëà ñóïåðêîìïüþòåðû ñ ìàññîâûì ïàðàëëåëèçìîì, êëàñòåðíûå êîìïëåêñû è ïåðñî- íàëüíûå êîìïüþòåðû. Ïîÿâèëèñü ñóïåðêîìïüþòåðû, ïðîèçâîäèòåëüíîñòü êîòî- ðûõ ïðåâûøàåò 1 ÏÔëîïñ. Ïðèçíàííûé àâòîðèòåò â îáëàñòè ëèíåéíîé àëãåáðû è âûñîêîïðîèçâîäèòåëüíûõ âû÷èñëåíèé Äæ. Äîíãàððà ïðèâåë ðÿä èíòåðåñíûõ ôàêòîâ.  ñðåäíåì êîìïüþòåð, ëè- äèðóþùèé ïî ïðîèçâîäèòåëüíîñòè â ñïèñêå «Top-500», çà 6–8 ëåò çàíèìàåò â íåì ïî- ñëåäíåå ìåñòî. Ñóïåðêîìïüþòåð, çàíèìàâøèé ïîñëåäíåå ìåñòî â ýòîì ñïèñêå, ÷åðåç 8–10 ëåò ïî ìîùíîñòè ñðàâíèâàåòñÿ ñ ïåðñîíàëüíûì êîìïüþòåðîì [1]. Ïîñêîëüêó ïîòðåáëÿåìàÿ ìîùíîñòü ïðîöåññîðà ïðîïîðöèîíàëüíà êóáó òàêòîâîé ÷àñòîòû, à õîðîøåå ðàñïàðàëëåëèâàíèå äàåò ëèíåéíîå óâåëè÷åíèå ñêîðîñòè, èñïîëü- çîâàíèå áîëüøîãî êîëè÷åñòâà ïðîöåññîðîâ ñ ïîíèæåííîé òàêòîâîé ÷àñòîòîé ïîçâî- ëÿåò çíà÷èòåëüíî óâåëè÷èòü ïðîèçâîäèòåëüíîñòü ïðè ìàëûõ ýíåðãåòè÷åñêèõ çàòðà- òàõ. Òàê, êîìïàíèÿ Intel èìååò ýêñïåðèìåíòàëüíûé îáðàçåö ïðîöåññîðà, ñîäåðæàùåãî 80 ÿäåð, ïèêîâîé ïðîèçâîäèòåëüíîñòüþ â 1 ÒÔëîïñ è ïîòðåáëÿþùåãî âñåãî 67 Âò ýëåêòðîýíåðãèè. Íî ìèð ïðîãðàììíîãî îáåñïå÷åíèÿ îêàçàëñÿ íå ãîòîâ ýêñïëóàòèðî- âàòü ïàðàëëåëèçì, ïîñêîëüêó çà âðåìÿ èñïîëüçîâàíèÿ îáû÷íûõ êîìïüþòåðîâ íàêîï- ëåí îãðîìíûé áàãàæ ãîòîâûõ ïîñëåäîâàòåëüíûõ ïðîãðàìì. Ôîðìàëüíûå ìåòîäû ðàñ- ïàðàëëåëèâàíèÿ ïîñëåäîâàòåëüíûõ ïðîãðàìì íà ïðàêòèêå íå ïîçâîëÿþò ïîëó÷èòü ñó- ùåñòâåííîãî óñêîðåíèÿ. Óñëîæíÿåò ñèòóàöèþ è ÷àñòàÿ ñìåíà ñëîæèâøèõñÿ òåõíîëîãèé ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ äëÿ ñóïåðêîìïüþòåðîâ, ïîýòîìó ïðî- ãðàììû ÷àñòî ïðèõîäèòñÿ ïåðåïèñûâàòü. Îäíàêî êîìïüþòåðíûé ìèð óæå ñòàë ïàðàë- ëåëüíûì è èíîãî ïóòè äîñòèæåíèÿ ìàêñèìàëüíîé ïðîèçâîäèòåëüíîñòè íåò. Öåëü ñòàòüè — ðàññìîòðåòü âîïðîñû, ñâÿçàííûå ñ ïðîèçâîäèòåëüíîñòüþ ïà- ðàëëåëüíûõ êîìïüþòåðîâ, âëèÿþùèå íà íåå ôàêòîðû, èñïîëüçóåìûå äëÿ åå èçìåðåíèÿ èíñòðóìåíòû. ÎÏÐÅÄÅËÅÍÈÅ ÏÐÎÈÇÂÎÄÈÒÅËÜÍÎÑÒÈ Ïîä ïðîèçâîäèòåëüíîñòüþ êîìïüþòåðà (â òîì ÷èñëå ïàðàëëåëüíîãî) ïîíèìàåòñÿ êîëè÷åñòâî (àðèôìåòè÷åñêèõ) îïåðàöèé â ñåêóíäó. Ïîä îïåðàöèÿìè ïðèíÿòî ïî- íèìàòü êàê ñëîæåíèå, òàê è óìíîæåíèå. Òèï îïåðàíäîâ îïðåäåëÿåò åäèíèöó èç- ìåðåíèÿ: ìèïñû — äëÿ öåëûõ ÷èñåë, ôëîïñû — äëÿ ÷èñåë ñ ïëàâàþùåé çàïÿ- òîé1. Ñïîñîá èçìåðåíèÿ êîëè÷åñòâà îïåðàöèé îïðåäåëÿåò òèï ïðîèçâîäèòåëüíîñ- 106 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 1Äàëåå, åñëè íå óêàçàíî ñïåöèàëüíî, ïîäðàçóìåâàþòñÿ îïåðàíäû äâîéíîé òî÷íîñòè (double precision). © Ð. À. Þùåíêî, 2009 òè. Ïîä ïèêîâîé (èäåàëüíîé) ïðîèçâîäèòåëüíîñòüþ ïîíèìàþò ìàêñèìàëüíóþ òåîðåòè÷åñêè äîñòèæèìóþ ïðîèçâîäèòåëüíîñòü, èñõîäÿ èç ñïåöèôèêàöèè ïðîöåñ- ñîðà ïðè óñëîâèè ìàêñèìàëüíîé çàãðóæåííîñòè, ìîìåíòàëüíîé ñêîðîñòè äîñòóïà ê ïàìÿòè è îòñóòñòâèè ëþáûõ íàêëàäíûõ ðàñõîäîâ. Ïèêîâàÿ ïðîèçâîäèòåëüíîñòü îäíîãî ïðîöåññîðà âû÷èñëÿåòñÿ êàê R F n kc cpeak � , ãäå Fc — òàêòîâàÿ ÷àñòîòà ÿäðà, nc — êîëè÷åñòâî ÿäåð, k — ôèêñèðîâàííàÿ êîíñòàíòà, çàâèñÿùàÿ îò àðõè- òåêòóðû ïðîöåññîðà. Ïèêîâàÿ ïðîèçâîäèòåëüíîñòü ïàðàëëåëüíîãî êîìïüþòåðà âû÷èñëÿåòñÿ êàê ñóììà ïðîèçâîäèòåëüíîñòè åãî ïðîöåññîðîâ. Äàëåå äëÿ ïðîñòî- òû ïðîöåññîð — ëþáîå óñòðîéñòâî, ãåíåðèðóþùåå ïîòîê èíñòðóêöèé (óçåë êëàñ- òåðà, ïðîöåññîð, ÿäðî). Ñðàâíèâàòü ïèêîâûå ïðîèçâîäèòåëüíîñòè íåêîððåêòíî, åñëè àðõèòåêòóðû ñðàâíèâàåìûõ ïðîöåññîðîâ ðàçëè÷àþòñÿ (â àíãëèéñêîì æàðãîíå áûòóåò ñëîâî machoflops, èðîíèçèðóþùåå íàä çàâûøåííûìè ïîêàçàòåëÿìè ïèêîâîé ïðîèçâîäè- òåëüíîñòè). Íî äëÿ ïîçèöèîíèðîâàíèÿ êîìïüþòåðîâ íà ðûíêå íåîáõîäèì óíèôèöè- ðîâàííûé èíäèêàòîð ïðîèçâîäèòåëüíîñòè. Ñòàíäàðòîì äå-ôàêòî ïðè ñðàâíåíèè ïðîèçâîäèòåëüíîñòè êîìïüþòåðîâ ñ÷èòàþò ðåçóëüòàòû ïàêåòà LINPACK Benchmark (äàëåå — òåñò LINPACK).  îïåðàòèâíîé ïàìÿòè ïàêåò ãåíåðèðóåò ñèñ- òåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé (ÑËÀÓ) ñ ïëîòíîé ìàòðèöåé êîýôôèöè- åíòîâ, çàïîëíåííóþ ïñåâäîñëó÷àéíûìè ÷èñëàìè, è ðåøàåò åå ìåòîäîì LU-ðàçëîæå- íèÿ. Ýòîò àëãîðèòì èíòåíñèâíî èñïîëüçóåò ïðîöåññîð, îïåðàòèâíóþ ïàìÿòü è êîììóíèêàöèîííûå êàíàëû, îñòàâàÿñü âåñüìà ýôôåêòèâíûì, ïîñêîëüêó íàãðóçêà íà ïðîöåññîð ïðåîáëàäàåò íàä îñòàëüíûìè. Îòìåòèì, ÷òî ãîâîðèòü î ïðèìåíåíèè ðåçóëüòàòîâ ëþáûõ òåñòîâûõ ïàêåòîâ (â òîì ÷èñëå LINPACK), ïðåäíàçíà÷åííûõ äëÿ èçìåðåíèÿ «ðåàëüíîé» ïðîèçâîäè- òåëüíîñòè, äëÿ èçó÷åíèÿ êîíêðåòíîé ïàðàëëåëüíîé ïðîãðàììû ìîæíî ëèøü ïîñëå äîïîëíèòåëüíîãî èññëåäîâàíèÿ êîððåëÿöèîííîé çàâèñèìîñòè ìåæäó ðåçóëüòàòàìè òåñòîâîãî ïàêåòà è ïðîèçâîäèòåëüíîñòüþ ïðîãðàììû. Ýòî ïîêàçàíî äàëåå äëÿ îòíîøåíèÿ èçîýôôåêòèâíîñòè. Äîñòè÷ü âûñîêîé ïðîèçâîäèòåëüíîñòè êîìïüþòåðà ìîæíî òîëüêî â èñêóññòâåííûõ óñëîâèÿõ2, ïîýòîìó äëÿ ïàðàëëåëüíûõ ïðîãðàìì îáû÷íî ãîâîðÿò íå î ïðîèçâîäèòåëüíîñ- òè, à îá ýôôåêòèâíîñòè. Äîñòèæåíèå âûñîêîé ýôôåêòèâíîñòè ïàðàëëåëüíîé ïðîãðàììû íà÷èíàåòñÿ ñ îïòèìèçàöèè ïîñëåäîâàòåëüíîé ïðîãðàììû, âêëþ÷àþùåé ýêñïëóàòàöèþ êýø-ïàìÿòè è âåêòîðíûõ îïåðàöèé ïðîöåññîðà. Îáû÷íî ýòó ðàáîòó ïåðåêëàäûâàþò íà êîìïèëÿòîð. Ïî ðåçóëüòàòàì èññëåäîâàíèé, ïðîâåäåííûõ â ÌÃÓ, èñïîëüçîâàíèå êîìïè- ëÿòîðà, îïòèìèçèðóþùåãî ïðîãðàììó ïîä êîíêðåòíóþ àðõèòåêòóðó, ìîæåò óâåëè÷èòü ñêîðîñòü âû÷èñëåíèé íà ïîðÿ- äîê, ïîçâîëÿÿ, òàêèì îáðàçîì, ëó÷øå ýêñïëóàòèðîâàòü èìåþùå- åñÿ «æåëåçî». Èññëåäîâàíèÿ òàêæå ïîêà- çàëè, ÷òî íàèáîëüøàÿ ýôôåêòèâ- íîñòü äîñòèãàåòñÿ íà çàäà÷àõ, â êîòîðûõ êîëè÷åñòâî àðèôìå- òè÷åñêèõ îïåðàöèé çíà÷èòåëüíî ïðåâûøàåò äîñòóï ê îïåðàòèâ- íîé ïàìÿòè. Íà ðèñ. 1 óñëîâíî ïîêàçàíû êðèâûå ñêîðîñòè àðèôìåòè÷åñêèõ îïåðàöèé ïðî- öåññîðà ïî ñðàâíåíèþ ñî ñêî- ðîñòüþ äîñòóïà ê ïàìÿòè, è î÷å- âèäíî, ÷òî ïîñëåäíÿÿ ðàñòåò ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 107 0.1 1 10 100 1000 1975 1980 1985 1990 1995 2000 2005 Ãîä Ñ ê î ð î ñ òü Ïðîöåññîð Îïåðàòèâíàÿ ïàìÿòü Ðèñ. 1 Ïðîöåññîð Îïåðàòèâíàÿ ïàìÿòü Ñ ê î ð î ñò ü Ãîä 2 Íàïðèìåð, ðåøàÿ çàäà÷ó x a b� � , ìîæíî óâåëè÷èòü ïðîèçâîäèòåëüíîñòü, ïåðåïèñàâ âûðàæåíèå: x a b� �1 1 . Òîãäà áóäåò çàãðóæåí íå òîëüêî ñóììàòîð, íî è óìíîæèòåëü, à ïðîöåññîð ñìîæåò ðàñïàðàëëåëèòü âû÷èñëåíèå. ìåäëåííåå. Îäíàêî ìíîãèå àëãîðèòìû ìîæíî îïòèìèçèðîâàòü äëÿ ýôôåêòèâíîãî èñ- ïîëüçîâàíèÿ êýø-ïàìÿòè ïðîöåññîðà, íà ïîðÿäîê óâåëè÷èâ ñêîðîñòü âû÷èñëåíèé. Äëÿ ìíîãèõ ìàòåìàòè÷åñêèõ çàäà÷ ñóùåñòâóþò ãîòîâûå áèáëèîòåêè. Íàïðèìåð, äëÿ îïåðà- öèé ñ âåêòîðàìè è ìàòðèöàìè ïðèíÿò ñòàíäàðò äå-ôàêòî BLAS ñî ìíîæåñòâîì ðåàëè- çàöèé. Îäíà èç ðåàëèçàöèé, ATLAS, ïðè ñáîðêå àâòîìàòè÷åñêè îïòèìèçèðóåòñÿ äëÿ êîíêðåòíîé ïëàòôîðìû. ÎÖÅÍÊÀ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÏÀÐÀËËÅËÜÍÛÕ ÏÐÎÃÐÀÌÌ Ýôôåêòèâíîñòü ïàðàëëåëüíîé ïðîãðàììû ÷àñòî îöåíèâàþò, ñðàâíèâàÿ åå ñêî- ðîñòü ñ ïîñëåäîâàòåëüíîé ëèáî ïàðàëëåëüíîé ïðîãðàììîé, íî âûïîëíÿþùåéñÿ íà îäíîì ÿäðå. Òàêèì îáðàçîì, ìîæíî îöåíèòü ïåðñïåêòèâû ðàñïàðàëëåëèâàíèÿ, à òàêæå îïòèìàëüíîå êîëè÷åñòâî ÿäåð. Ïóñòü ïàðàëëåëüíàÿ ïðîãðàììà âûïîëíÿåòñÿ íà N ÿäðàõ çà âðåìÿ T N TN( ) � .  ñëó÷àå èäåàëüíîãî ïàðàëëåëèçìà âðåìÿ ðåøåíèÿ ðàâíî T T NN � 1 / . Íî òàêîãî íà ïðàêòèêå íåëüçÿ äîáèòüñÿ äàæå òîãäà, êîãäà ðåøàåìàÿ çàäà÷à íå èìååò îáìåíîâ ìåæäó ÿäðàìè (â ëèòåðàòóðå äåêîìïîçèöèþ, íå èìåþùóþ îáìåíîâ ìåæäó ÿäðàìè, íàçûâàþò òðèâèàëüíûì ïàðàëëåëèçìîì). Íàïðèìåð, êàæäûé îòäåëüíûé ïðîãîí ñî- âåðøåííî íåçàâèñèì ïðè ìîäåëèðîâàíèè ìåòîäîì Ìîíòå-Êàðëî. Åñëè âûïîëíÿòü êàæäûé ïðîãîí íà îòäåëüíîì ÿäðå, ìîæíî ïîëó÷èòü õîðîøåå âðåìÿ ðàñïàðàëëåëè- âàíèÿ, íî îíî âñå ðàâíî áóäåò íå èäåàëüíûì, ïîñêîëüêó ðàçíûå ïðîãîíû ìîãóò âûïîëíÿòüñÿ çà ðàçíîå âðåìÿ. Äëÿ îöåíèâàíèÿ ýôôåêòà ðàñïàðàëëåëèâàíèÿ ðàññìàòðèâàþò ïîíÿòèÿ óñêîðå- íèÿ ( ( ))S N è ýôôåêòèâíîñòè ( ( ))E N : S N T TN ( ) � 1 , (1) E N S N N T N TN ( ) ( ) � � 1 . (2) Ýôôåêòèâíîñòü ìîæåò çíà÷èòåëüíî îãðàíè÷èòü ïîñëåäîâàòåëüíàÿ ÷àñòü ïðî- ãðàììû, ò.å. îñòàþùàÿñÿ ïîñëåäîâàòåëüíîé ÷àñòü, ïîñêîëüêó ñ÷èòàþò, ÷òî âðåìÿ åå âûïîëíåíèÿ íåñóùåñòâåííî ëèáî ðàñïàðàëëåëèâàòü åå «íåèíòåðåñíî». Íàïðèìåð, ýòî ñëó÷àåòñÿ ïðè ðåøåíèè êîíå÷íî-ðàçíîñòíûõ è êîíå÷íî-ýëåìåíòíûõ çàäà÷, åñëè âû÷èñëèòåëüíàÿ ðåøåòêà ãåíåðèðóåòñÿ ïîñëåäîâàòåëüíî, à ñàì ðàñ÷åò âûïîëíÿåòñÿ ïàðàëëåëüíî. Åñëè ÷èñëî ÿäåð âåëèêî, òî âû÷èñëåíèÿ çàíèìàþò íàìíîãî ìåíüøå âðåìåíè, ÷åì ãåíåðàöèÿ âû÷èñëèòåëüíîé ðåøåòêè. Ñåðèÿ îòíîøåíèé è òåîðåì, ïðåäëîæåííûõ Àìäàëîì â 1967 ã. è âïîñëåäñòâèè ñòàâøèõ èçâåñòíûìè êàê çàêîíû Àìäàëà, óñòàíàâëèâàåò òåîðåòè- ÷åñêóþ âåðõíþþ ãðàíèöó ðàñïà- ðàëëåëèâàíèÿ ïðè ôèêñèðîâàí- íîé äîëå ïîñëåäîâàòåëüíûõ âû- ÷èñëåíèé: S N N ( ) � � � 1 1 � � , (3) ãäå � — äîëÿ ïîñëåäîâàòåëü- íûõ âû÷èñëåíèé. Íà ðèñ. 2 ïðèâåäåíà çàâè- ñèìîñòü óñêîðåíèÿ (S) îò êîëè- ÷åñòâà ÿäåð ( )N ïðè ðàçëè÷íûõ çíà÷åíèÿõ ôèêñèðîâàííîé 108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 0 2 4 6 8 10 12 14 16 18 20 22 1 10 100 1000 10000 100000 Êîëè÷åñòâî ÿäåð, N Ó ñ ê î ð å í è å , S (N ) ?=50% ?=25% ?=10% ?=5% Ðèñ. 2 Êîëè÷åñòâî ÿäåð, N Ó ñê î ð åí è å, S N( ) � � 50% � � 25% � � 10% � � 5% äîëè ïîñëåäîâàòåëüíûõ âû- ÷èñëåíèé ( )� , à íà ðèñ. 3 — ýôôåêòèâíîñòè ( )Å îò êîëè- ÷åñòâà ÿäåð ( )N . Âåñüìà ïåññèìèñòè÷íûì âûãëÿäèò òî, ÷òî, åñëè ïîñëåäîâàòåëüíàÿ äîëÿ âû÷èñëåíèé ñîñòàâëÿåò âñåãî 5%, óæå íà 120 ÿäðàõ èìååì ýô- ôåêòèâíîñòü ìåíåå 15%. Íà ïðàêòèêå äîëÿ ïîñëå- äîâàòåëüíûõ âû÷èñëåíèé â ïðîãðàììå óìåíüøàåòñÿ ñ ðîñòîì ðàçìåðîâ çàäà÷è ( )n . Äëÿ ïîëó÷åíèÿ òðåáóåìîé ýô- ôåêòèâíîñòè ìîæíî óâåëè- ÷èòü n , íàïðèìåð, ñäåëàâ ìî- äåëü áîëåå äåòàëüíîé. Ýòîò ïðèíöèï ïîëîæåí â îñíîâó çàêîíà Ãóñòàâñîíà–Áàðñèñà, ïðåäëîæåííîãî â 1988 ã. Èñïîëüçóÿ ýòîò çàêîí, ìîæíî ïîäáèðàòü êîëè÷åñòâî ÿäåð èëè ðàçìåð çàäà÷è äëÿ äîñòèæåíèÿ íóæíîé ýôôåêòèâíîñòè. Ïóñòü s — äîëÿ âðåìåíè âûïîëíåíèÿ ïîñëåäîâàòåëüíîé ÷àñòè ïàðàëëåëüíîé ïðîãðàììû, s n n n n N ( ) ( ) ( ) ( ) � � � � � , ãäå �( )n — äîëÿ ïàðàëëåëüíûõ âû÷èñëåíèé, �( )n — äîëÿ ïîñëåäîâàòåëüíûõ âû- ÷èñëåíèé. Òîãäà îöåíêà ìàñøòàáèðóåìîãî óñêîðåíèÿ Ãóñòàâñîíà–Áàðñèñà èìååò âèä S T T s N s N N s N � � � � � � � 1 1 1( ) ( ) . (4) Çàêîí Ãóñòàâñîíà–Áàðñèñà èñõîäèò èç òîãî, ÷òî äëÿ ëþáîãî ÷èñëà ÿäåð ìîæíî ïîäîáðàòü çàäà÷ó äîñòàòî÷íî áîëüøîãî ðàçìåðà, ÷òîáû îíà âûïîëíÿëàñü ýôôåêòèâ- íî. Îäíàêî íà ïðàêòèêå îöåíêè ÷àñòî ÷åðåñ÷óð îïòèìèñòè÷íû. Àëüòåðíàòèâíîé êîíöåïöèåé ïàðàëëåëèçìà ñ÷èòàþò ïðèíöèï ìàêðîêîíâåéåð- íûõ âû÷èñëåíèé, ïðåäëîæåííûé Â.Ì. Ãëóøêîâûì â 1978 ã. è èññëåäóåìûé ñîòðóä- íèêàìè Èíñòèòóòà êèáåðíåòèêè â 1980-õ ãã. Ìàêðîêîíâåéåð — ìîäåëü ïàðàëëåëü- íîãî êîìïüþòåðà ñ ðàñïðåäåëåííîé ïàìÿòüþ, â êîòîðîé ïðîöåññîðû ñîåäèíåíû êîììóíèêàöèîííûìè êàíàëàìè. Êàæäîå âû÷èñëèòåëüíîå óñòðîéñòâî îáëàäàåò ñâî- åé ëîêàëüíîé ïàìÿòüþ, à äàííûå ìåæäó óñòðîéñòâàìè ïåðåäàþòñÿ ïî êàíàëàì. Êðî- ìå òîãî, êîíöåïöèÿ ïîäðàçóìåâàåò íàëè÷èå âõîäíîãî êàíàëà äëÿ èñõîäíûõ äàííûõ è âûõîäíîãî — äëÿ ðåçóëüòàòîâ. Ìîäåëü ìàêðîêîíâåéåðíûõ âû÷èñëåíèé âåñüìà òî÷íî îòðàæàåò ïðè÷èíû íèç- êîé ïðîèçâîäèòåëüíîñòè òàêèõ ñèñòåì — íàêëàäíûå êîììóíèêàöèîííûå çàòðàòû. Ïîä êîììóíèêàöèîííûìè çàòðàòàìè �( , )n N ïîäðàçóìåâàþò çàäåðæêè, ñâÿçàííûå ñ ïåðåñûëêîé äàííûõ ïî êàíàëàì è ñèíõðîíèçàöèåé ïðîöåññîâ.  çàâèñèìîñòè îò ñïîñîáà ðàñïàðàëëåëèâàíèÿ è òîïîëîãèè ñâÿçåé ìåæäó âû÷èñëèòåëÿìè ðàññìàòðè- âàþò èòåðàòèâíûå, âîëíîâûå è ñìåøàííûå ìàêðîêîíâåéåðû ñ ñèíõðîííûì ëèáî àñèíõðîííûì îáìåíîì äàííûìè. Äëÿ êàæäîãî èç íèõ íàéäåíû îöåíêè âåðõíåé ãðàíèöû ýôôåêòèâíîñòè [2]. Ïî ñóòè, ìàêðîêîíâåéåð âîïëîùàåò ìîäåëü ïåðâîãî â ÑÑÑÐ êîìïüþòåðà ñ ðàñ- ïðåäåëåííîé ïàìÿòüþ, àðõèòåêòóðíî àíàëîãè÷íîãî ñîâðåìåííûì êëàñòåðíûì êîì- ïëåêñàì. Åùå â 1980-õ ãã. Â.Ì. Ãëóøêîâ âèäåë ïåðñïåêòèâû òàêèõ êîìïüþòåðîâ, ñïîñîáíûõ ìàñøòàáèðîâàòü âû÷èñëåíèÿ íà ñîòíÿõ è òûñÿ÷àõ ïðîöåññîðîâ ïðè ïðàêòè÷åñêè ëèíåéíîì ðîñòå ñòîèìîñòè. Îí òàêæå ïðåäâèäåë ïðîáëåìû, âîçíèêàþ- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 109 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 20 40 60 80 100 120 140 Êîëè÷åñòâî ÿäåð, N Ý ô ô å ê òè â í î ñ òü , E (N ) ?=50% ?=25% ?=10% ?=5% Ðèñ. 3 Êîëè÷åñòâî ÿäåð, N Ý ô ô åê òè â í î ñò ü , E N( ) � � 50% � � 25% � � 10% � � 5% ùèå ïðè ðàçðàáîòêå ïàðàëëåëüíûõ àëãîðèòìîâ è ïðîãðàìì.  íàñòîÿùåå âðåìÿ, êîãäà ïîÿâèëèñü ïàðàëëåëüíûå êîìïüþòåðû ñ ñîòíÿìè òûñÿ÷ ïðîöåññîðîâ, îïòèìè- çàöèÿ ìàêðîêîíâåéåðíûõ ñåòåé ÿâëÿåòñÿ îñîáî àêòóàëüíîé çàäà÷åé, è ê íåé ÷àñòî âîçâðàùàþòñÿ â ïóáëèêàöèÿõ, íî èñïîëüçóÿ íîâóþ òåðìèíîëîãèþ [3]. Îòíîøåíèå èçîýôôåêòèâíîñòè ïîçâîëÿåò îïðåäåëèòü äèàïàçîí ÿäåð, íà êîòî- ðîì äîñòèãàåòñÿ íåîáõîäèìàÿ ýôôåêòèâíîñòü [4]. Äëÿ ýòîãî óñêîðåíèå ðàññìàòðè- âàåòñÿ êàê ôóíêöèÿ S n N( , ) , ãäå n — ðàçìåð çàäà÷è, à N — êîëè÷åñòâî ïðîöåññîðîâ. Âû÷èñëèòåëüíîé ñèñòåìîé íàçîâåì ïàðàëëåëüíóþ ïðîãðàììó, âûïîëíÿåìóþ íà ïàðàëëåëüíîì êîìïüþòåðå. Ïîä ìàñøòàáèðóåìîñòüþ âû÷èñëèòåëüíîé ñèñòåìû ïîíè- ìàþò åå ñïîñîáíîñòü ñîõðàíÿòü ýôôåêòèâíîñòü âû÷èñëåíèé ïðè íàðàùèâàíèè N . Îïðåäåëèì íàêëàäíûå çàòðàòû êàê T n N N n N n N0 1( , ) ( ) ( ) ( , )� � �� � . Ïîäñòà- âèì èõ çíà÷åíèå â ôîðìóëó óñêîðåíèÿ S n N T n T n N N n n n n T n N ( , ) ( , ) ( , ) ( ( ) ( )) ( ) ( ) ( , ) � � � � � 1 0 � � � � . Ïðåäïîëîæèì, ýôôåêòèâíîñòü (2) ïîñòîÿííà. Òîãäà âûïîëíÿåòñÿ íåðàâåíñòâî T n CT n N( , ) ( , )1 0� , (5) íàçûâàåìîå íåðàâåíñòâîì èçîýôôåêòèâíîñòè. Îòíîøåíèå èçîýôôåêòèâíîñòè èñ- ïîëüçóþò äëÿ îïðåäåëåíèÿ ñòåïåíè ìàñøòàáèðóåìîñòè âû÷èñëèòåëüíîé ñèñòåìû. Äëÿ ýòîãî íåðàâåíñòâî èçîýôôåêòèâíîñòè (5) ðàññìàòðèâàþò â âèäå n f N� ( ) , ãäå f N( ) — íåêîòîðàÿ ôóíêöèÿ. Ôóíêöèÿ M n( ) çàäàåò îáúåì ïàìÿòè, íåîáõîäèìûé äëÿ ðåøåíèÿ çàäà÷è ðàçìåð- íîñòè n, à ôóíêöèÿ ìàñøòàáèðóåìîñòè �( ) ( ( )) N M f N N � — îáúåì ïàìÿòè, íåîáõî- äèìûé îäíîìó ÿäðó äëÿ ñîõðàíåíèÿ ýôôåêòèâíîñòè. ×òîáû ñîõðàíèòü ýôôåêòèâ- íîñòü ïðè óâåëè÷åíèè N , íóæíî íàðàùèâàòü ðàçìåð çàäà÷è â ñîîòâåòñòâèè ñ íåðà- âåíñòâîì èçîýôôåêòèâíîñòè. Íà ðèñ. 4 ôóíêöèÿ �( )N ïðî- èëëþñòðèðîâàíà íà íåñêîëüêèõ ïðèìåðàõ. Øòðèõîì óñëîâíî ïîêà- çàí îáúåì ïàìÿòè êîìïüþòåðà. Êàê âèäíî èç ãðàôèêà, ïðè ëèíåéíîì è âûøå ðîñòå �( )N âû÷èñëèòåëüíàÿ ñèñòåìà òåðÿåò ýôôåêòèâíîñòü [4]. Ôóíêöèþ ìàñøòàáèðóåìîñòè çàäàþò äëÿ âû÷èñëèòåëüíîé ñèñòå- ìû, èñõîäÿ èç âû÷èñëèòåëüíîé ñëîæíîñòè ïîñëåäîâàòåëüíîãî è ïà- ðàëëåëüíîãî àëãîðèòìîâ, ñëîæíîñ- òè çàòðàò íà êîììóíèêàöèþ. Õîðîøåé ìåðîé îöåíêè äîñ- òèãíóòîé ýôôåêòèâíîñòè äëÿ ãîòî- âîé ïàðàëëåëüíîé ïðîãðàììû ïðè åå ðàáîòå íà êîíêðåòíîì ïàðàëëåëüíîì êîìïüþ- òåðå ñ÷èòàåòñÿ ìåòðèêà Êàðïà–Ôëàòòà, ïðåäëîæåííàÿ â 1990 ã. Îíà ïîçâîëÿåò ýêñ- ïåðèìåíòàëüíî îöåíèòü ïîñëåäîâàòåëüíóþ ÷àñòü â ïðîãðàììå è äîëþ çàòðàò íà êîììóíèêàöèþ: e n N n n N n n S n N N N T n TN( , ) ( ) ( , ) ( ) ( ) ( , ) ( ) � � � � � � � � � � � 1 1 1 1 1 ( )n N N � � 1 1 1 . (6) Ðåçóëüòàòû (1)–(6) äàþò ïðåäñòàâëåíèå î ïàðàëëåëèçìå è îöåíêå íàêëàäíûõ çà- òðàò. Íî äëÿ íåêîòîðûõ ïðèêëàäíûõ çàäà÷ îáðàáîòêè äàííûõ áîëüøèõ îáúåìîâ 110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 C Clog(N) CN CNlog(N) Êîëè÷åñòâî ÿäåð, N Òåðÿåò ýôôåêòèâíîñòü Ñîõðàíÿåò ýôôåêòèâíîñòü Ï àì ÿ òü ä ë ÿ î ä í î ãî ÿ ä ð à, ? (N ) Ðèñ. 4 � ( ) N êðèòè÷íûì ðåñóðñîì ÿâëÿåòñÿ ñèñòåìà äèñêîâîãî õðàíåíèÿ äàííûõ. Òàêèå çàäà÷è îáëàäàþò íèçêîé ìàêðîêîíâåéåðíîñòüþ, ïîýòîìó óâåëè÷åíèå ÷èñëà ÿäåð ìîæåò ïðèâåñòè ê òîìó, ÷òî ñèñòåìà õðàíåíèÿ äàííûõ ñòàíåò óçêèì ìåñòîì âû÷èñëåíèé, à èñïîëüçîâàíèå á�ëüøåãî ÷èñëà ïðîöåññîðîâ äëÿ ðàñ÷åòà ìîæåò íå òîëüêî íå óâå- ëè÷èòü, íî äàæå óìåíüøèòü âðåìÿ âû÷èñëåíèé. Ìåòîäèêà îöåíèâàíèÿ ýôôåêòèâíîñòè ïàðàëëåëüíûõ ïðîãðàìì ñ îäíîðîäíîé îáðàáîòêîé äàííûõ [5] ïîçâîëÿåò îöåíèòü âðåìÿ âûïîëíåíèÿ ïàðàëëåëüíîé ïðî- ãðàììû íà îñíîâå íåáîëüøîãî ÷èñëà ýêñïåðèìåíòîâ. Èäåÿ ìåòîäèêè ñîñòîèò â òîì, ÷òî íà êîìïüþòåðå, íàçûâàåìîì áàçîâûì, ïðîâîäÿò ñåðèþ ýêñïåðèìåíòîâ ñ ïîñëå- äîâàòåëüíîé èëè ïàðàëëåëüíîé ïðîãðàììîé. Ïðè âûïîëíåíèè ýòîé ïðîãðàììû ñî- áèðàþò ðàçíûå ïðîôèëüíûå äàííûå, íàïðèìåð âðåìÿ âûïîëíåíèÿ, äîëÿ âðåìåíè äîñòóïà ê äèñêîâîé ïàìÿòè è ïð. Äëÿ èçìåðåíèÿ âñòðàèâàþò ñ÷åò÷èêè íåïîñðåä- ñòâåííî â òåêñò ïðîãðàììû ëèáî èñïîëüçóþò ñðåäñòâî ïðîôèëèðîâàíèÿ. Äëÿ ïðî- ãíîçà âðåìåíè âûïîëíåíèÿ íà ïðîèçâîëüíîì êëàñòåðå â ôîðìóëû îöåíîê ýôôåêòèâ- íîñòè ïîäñòàâëÿþò êîýôôèöèåíòû õàðàêòåðèñòèê áàçîâîãî êîìïüþòåðà è óçëà êëàñòåðà, à òàêæå ïðîôèëüíûå äàííûå.  ðåçóëüòàòå ïîëó÷èì îöåíî÷íîå âðåìÿ ïðî- ãðàììû êàê ôóíêöèþ îò ÷èñëà ïðîöåññîðîâ. Äëÿ íåå ìîæíî ïîäîáðàòü îïòèìàëü- íîå N . Îäíàêî ìåòîäèêà [5] èìååò ïðèíöèïèàëüíûé íåäîñòàòîê, ïîñêîëüêó íå ó÷è- òûâàåò äèíàìè÷åñêèõ õàðàêòåðèñòèê ïàðàëëåëüíîãî àëãîðèòìà, à çíà÷èò, ðåçóëüòà- òû íåëüçÿ ïðèìåíèòü, åñëè ðàçìåð ðåøàåìîé çàäà÷è ÿâëÿåòñÿ ïåðåìåííûì. Ïîýòîìó äàííàÿ ìåòîäèêà íåñêîëüêî ðàñøèðåíà è äëÿ áîëüøåé òî÷íîñòè ðåçóëüòàòîâ ðàçðàáîòà- íû îöåíêè äëÿ ðàçíûõ ïàòòåðíîâ ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ [6]. Òåðìèí «ïàòòåðí» âïåðâûå ïðåäëîæèë àðõèòåêòîð Ê. Àëåêñàíäð â 1977 ã.; îí îçíà÷àåò ãîòîâûå øàáëîíû ðåøåíèé äëÿ êîíêðåòíûõ ñòðîèòåëüíûõ îáúåêòîâ. Êàæäûé «àëåêñàíäðîâñêèé» ïàòòåðí îáëàäàåò òðåìÿ îáÿçàòåëüíûìè ýëåìåíòàìè: íàçâàíèå, îïè- ñàíèå òèïè÷íîé ïðîáëåìû è øàáëîí òèïîâîãî ðåøåíèÿ. Ìåæäó îïèñàíèåì ïðîáëåìû è åå ðåøåíèåì Ê. Àëåêñàíäð ïèñàë çàãëàâíûìè áóêâàìè ñëîâî «ÏÎÝÒÎÌÓ». Èñïîëüçîâàíèå ïàòòåðíîâ â ïðîãðàììèðîâàíèè îáóñëîâëåíî òåì, ÷òî ñîâðåìåí- íûå ÿçûêè ïðîãðàììèðîâàíèÿ íàñûùåíû àáñòðàêöèÿìè, êîòîðûìè íåîáõîäèìî îïåðè- ðîâàòü äëÿ ýôôåêòèâíîãî íàïèñàíèÿ íàäåæíûõ ïðîãðàìì. Îñîáåííî ýòî îòíîñèòñÿ ê ÿçûêàì âûñîêîãî óðîâíÿ âðîäå C#. Îáû÷íîå ïðåäñòàâëåíèå ïðîãðàììû â âèäå áëîê-ñõåìû óäîáíî äëÿ äåòàëüíîãî îïèñàíèÿ ñëîæíûõ àëãîðèòìîâ çàäà÷, íî äàëåêî íå- äîñòàòî÷íî äëÿ îïèñàíèÿ êîìïëåêñîâ ïðîãðàììíûõ ñèñòåì. Ñîâðåìåííûå ÿçûêè ïðåä- îñòàâëÿþò ìîùíûå ñðåäñòâà, èñïîëüçóÿ êîòîðûå ìîæíî ñîçäàâàòü èçÿùíûå è óäîáíûå ñïîñîáû ðåøåíèÿ çàäà÷.  ðàáîòàõ Ê. Áåêà è Ó. Êàííèíãåìà, à òàêæå â çíàìåíèòîé ðà- áîòå Å. Ãàììà, Ð. Õåëüìà, Ð. Äæîíñîíà [7] àêêóìóëèðîâàí ïðîãðàììèñòñêèé îïûò â âèäå êàðêàñîâ äëÿ ðåøåíèÿ çàäà÷ íà îñíîâå îáúåêòíî-îðèåíòèðîâàííîãî ïîäõîäà. Òåðìèí «ïàòòåðí» (øàáëîí) èñïîëüçîâàí â îáúåêòíî-îðèåíòèðîâàííîì ïðîåê- òèðîâàíèè äëÿ îïèñàíèÿ øàáëîíîâ êëàññîâ è âçàèìîñâÿçåé ìåæäó íèìè ïðè ðåøå- íèè òèïè÷íûõ çàäà÷. Òàêîé øàáëîí çàäàåò îïèñàíèå êëàññà èëè îáúåêòà, åãî îòíî- øåíèå ñ äðóãèìè êëàññàìè ëèáî îáúåêòàìè (àãðåãèðîâàíèå, ñóïåðïîçèöèÿ, àññîöèà- öèÿ, íàñëåäîâàíèå è äð.) è ñöåíàðèè èõ âçàèìîäåéñòâèÿ äëÿ ðåøåíèÿ êëàññîâ çàäà÷. Òàê, ïàòòåðí «àäàïòåð» — ýòî êëàññ, çàäà÷à êîòîðîãî — îáåñïå÷åíèå åäèíîãî èíòåð- ôåéñà äëÿ ìíîæåñòâà êëàññîâ ñî ñõîäíûìè ôóíêöèÿìè, íî ðàçëè÷íûìè èíòåðôåéñà- ìè. Íàçâàíèÿ ïàòòåðíîâ, îïèñàííûõ â ðàáîòàõ Å. Ãàììà, âîøëè â ëåêñèêîí îáúåê- òíî-îðèåíòèðîâàííîãî ïðîåêòèðîâàíèÿ, à òàêèå, êàê «ñèíãëåòîí», — â ãðàììàòèêó ÿçûêîâ ïðîãðàììèðîâàíèÿ.  ïîääåðæêó ðàçâèòèÿ ïàòòåðíîâ ïðîãðàììèðîâàíèÿ â 1993 ã. îñíîâàíà íåêîììåð÷åñêàÿ îðãàíèçàöèÿ Hillside Group, ïðîâîäÿùàÿ åæå- ãîäíûå êîíôåðåíöèè Pattern Language of Programs (PLoP). Îáëàñòü ïðèìåíåíèÿ ïàòòåðíîâ Ãàììà — îáúåêòíî-îðèåíòèðîâàííîå ïðîåêòè- ðîâàíèå.  ïàðàëëåëüíîì ïðîãðàììèðîâàíèè âîçìîæíîãî ðàçíîîáðàçèÿ ðåøåíèé è èíñòðóìåíòîâ íàìíîãî áîëüøå, ïîýòîìó ðàáîòà Ò. Ìýòòñîíà [8] ñòàëà êðàéíå ïîïó- ëÿðíà è öèòèðóåìà. Ïðåäëîæåííàÿ â íåé êàñêàäíàÿ òåõíîëîãèÿ ïðîåêòèðîâàíèÿ ïà- ðàëëåëüíûõ ïðîãðàìì, îñíîâàííàÿ íà ÿçûêå ïàòòåðíîâ, ïîäðàçóìåâàåò ÷åòûðå ñòà- äèè ïðîåêòèðîâàíèÿ: ïîèñê ïàðàëëåëüíîñòè, ñõåìà àëãîðèòìà, âñïîìîãàòåëüíûå ñòðóêòóðû è ìåõàíèçìû ðåàëèçàöèè. Îäíàêî ïðîöåäóðà ïðîåêòèðîâàíèÿ íà îñíîâå ïàòòåðíîâ íå ãàðàíòèðóåò ïîëó÷åíèå íàèëó÷øåãî ïðîåêòà. Íàïðèìåð, àëãîðèòì ðàñ- ïàðàëëåëèâàíèÿ, èäåàëüíî ïîäõîäÿùèé ê çàäà÷å, ìîæåò îêàçàòüñÿ íåýôôåêòèâíûì ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 111 ïðè ðåàëèçàöèè íà êîíêðåòíîì êîìïüþòåðå. Äëÿ ïîëó÷åíèÿ îöåíêè ýôôåêòèâíîñòè ïàðàëëåëüíîé ïðîãðàììû íà êëàñòåðå íóæíî ðàññìîòðåòü ïàòòåðíû, èñõîäÿ, ïðåæäå âñåãî, èç ñðåäñòâ ðåàëèçàöèè. Äëÿ çàäà÷ îäíîðîäíîé îáðàáîòêè äàííûõ ðåçóëüòàòû èññëåäîâàíèé ïîêàçàëè, ÷òî íàèáîëåå öåëåñîîáðàçíû ïàòòåðíû «ìàñòåð-ðàáî÷èé», «îäíà ïðîãðàììà — ìíîãî äàííûõ» è «ðàçäåëÿé è âëàñòâóé». Ïî ðåçóëüòàòàì ìîäåëèðîâàíèÿ ìåòîäîì Ìîíòå-Êàðëî â ñðåäå GPSS äëÿ ïàò- òåðíîâ ñòàäèè ïðîåêòèðîâàíèÿ ñòðóêòóð ïðîãðàìì «ìàñòåð-ðàáî÷èé» (ÌÐ), «îäíà ïðîãðàììà — ìíîãî äàííûõ» (ÎÏÌÄ), «ðàçäåëÿé è âëàñòâóé» (ÐÂ) ñôîðìóëèðîâà- íû ðåêîìåíäàöèè, ïðèâåäåííûå íèæå. Ïàòòåðíû, îáëàäàþùèå ïðåèìóùåñòâîì, ïîêàçàíû ïåðâûìè. Ïðåèìóùåñòâî ïàòòåðíîâ ñ ðàçíûõ òî÷åê çðåíèÿ Ïî òðåáîâàíèÿì ê äèñêîâîé ïàìÿòè Ïî áàëàíñèðîâêå çàãðóçêè Ïî çàòðàòàì íà êîììóíèêàöèþ Ïî ìàñøòàáèðóåìîñòè РÌÐ ÎÏÌÄ ÌÐ ÌÐ ÎÏÌÄ ÌÐ ÎÏÌÄ ÎÏÌÄ Ð Ð Ð Ý. Êîåèíã ïðåäëîæèë êîíöåïöèþ «àíòèïàòòåðíîâ», êîòîðûå ïîìèìî ñóòè ïðî- áëåìû è òèïîâîãî ðåøåíèÿ ñîäåðæàò îïèñàíèå òèïîâûõ íåâåðíûõ ðåøåíèé.  ðóñ- ëå ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ èìååì àíòèïàòòåðíû ëèøü äëÿ ìíîãîïîòîêî- âîãî ïðîãðàììèðîâàíèÿ. ÏÐÎÃÐÀÌÌÍÛÅ ÏÀÊÅÒÛ ÈÇÌÅÐÅÍÈß ÏÐÎÈÇÂÎÄÈÒÅËÜÍÎÑÒÈ Ñóùåñòâóåò ðàçíîîáðàçèå ïðîãðàììíîãî îáå÷ïå÷åíèÿ, ïîçâîëÿþùåãî îöåíèòü ïðîèçâî- äèòåëüíîñòü ïàðàëëåëüíûõ êîìïüþòåðîâ. Êàê ïðàâèëî, òàêîå èçìåðåíèå ïðîâîäÿò â äâà ýòàïà. Ïåðâûé — èçìåðåíèå ïðîèçâîäèòåëüíîñòè îòäåëüíûõ óçëîâ è êîìïîíåíòîâ, âêëþ÷àÿ ïðîöåññîðû, îïåðàòèâíóþ ïàìÿòü, ñåòü, äèñêîâûå ìàññèâû. Çàäà÷à ýòîãî ýòà- ïà — âûÿâèòü ñáîè â êîìïîíåíòàõ êîìïëåêñà, íå îáÿçàòåëüíî ïðèâîäÿùèå ê ïîòåðå ðàáîòîñïîñîáíîñòè: ÷àñòî êîìïüþòåð ïðîäîëæàåò ðàáîòàòü ñî ñíèæåííîé ñêîðîñòüþ. Âòîðîé ýòàï — òåñòèðîâàíèå ïðîèçâîäèòåëüíîñòè â öåëîì. Äëÿ òåñòèðîâàíèÿ ïðîöåññîðà èñïîëüçóþò îäíîïðîöåññîðíóþ è SMP-âåðñèè òåñòà LINPACK, à îïåðàòèâíîé ïàìÿòè — óòèëèòó MEMTEST86, STREAM èëè RandomAccess. Öåëü ýêñïåðèìåíòîâ — óáåäèòüñÿ, ÷òî âñå êîìïîíåíòû èìåþò îäè- íàêîâûå ïîêàçàòåëè ñêîðîñòè. Ñêîðîñòü ñåòè êðèòè÷íà äëÿ ìíîãèõ ïàðàëëåëüíûõ âû÷èñëåíèé íà êîìïüþòå- ðàõ ñ ðàñïðåäåëåííîé ïàìÿòüþ, ïîñêîëüêó îíà ôàêòè÷åñêè îïðåäåëÿåò êîììóíèêà- öèîííûå çàòðàòû. Îáû÷íî èçìåðÿþò ëàòåíòíîñòü — çàäåðæêó ïðè ïåðåäà÷å ñîîá- ùåíèÿ ìèíèìàëüíîé äëèíû è ïðîïóñêíóþ ñïîñîáíîñòü — ìàêñèìàëüíîå êîëè÷å- ñòâî áàéòîâ, ïåðåäàâàåìûõ çà åäèíèöó âðåìåíè. Åñëè ïàðàëëåëüíàÿ ñðåäà ïîäðàçóìåâàåò îáìåí äàííûìè â ðàìêàõ ñòåêà ïðîòîêîëîâ TCP/IP, èçìåðèòü ëàòåí- òíîñòü è ïðîïóñêíóþ ñïîñîáíîñòü ìîæíî ñ ïîìîùüþ óòèëèòû «beff». Íî ÷àñòî äëÿ äîñòèæåíèÿ ìàêñèìàëüíîé ñêîðîñòè âû÷èñëèòåëüíàÿ ñðåäà èñïîëüçóåò ñåòü, ìèíóÿ ñòåê TCP/IP. Òîãäà èñïîëüçóþò óòèëèòû ñîâìåñòíî ñ ñåòåâûì îáîðóäîâàíèåì, íà- ïðèìåð ïðîãðàììó «bw», âõîäÿùóþ â ñîñòàâ êîìïëåêòà ïðîãðàìì OFÀ3. Ïîñêîëüêó ïàðàëëåëüíûå ïðîãðàììû âûïîëíÿþòñÿ â âû÷èñëèòåëüíîé ñðåäå, îíà êàê ôàêòîð âëèÿåò íà ïðîèçâîäèòåëüíîñòü. Ðàññìîòðèì MPI (Message Passing Interface) êàê ñòàíäàðò äå-ôàêòî äëÿ ðàñïàðàëëåëèâàíèÿ íà êîìïüþòåðàõ ñ ðàñïðå- äåëåííîé ïàìÿòüþ.  íàñòîÿùåå âðåìÿ ñîñóùåñòâóþò äâå ñïåöèôèêàöèè MPI: MPI 1.2, íàñ÷èòûâàþùàÿ ïîðÿäêà 128 ôóíêöèé äëÿ îáìåíà ñîîáùåíèÿìè, è MPI 2.0 (áîëåå 500 ôóíêöèé). Èíòåíñèâíîñòü èõ èñïîëüçîâàíèÿ çàâèñèò, ïðåæäå âñåãî, îò ëîãèêè (ìîäåëè ðàñïàðàëëåëèâàíèÿ) ïàðàëëåëüíîé ïðîãðàììû. Èññëåäîâàíèå ñêî- ðîñòè âûïîëíåíèÿ âàæíî, âî-ïåðâûõ, äëÿ âûáîðà íàèáîëåå ïîäõîäÿùåé ìîäåëè ðàñïàðàëëåëèâàíèÿ, à âî-âòîðûõ, ÷òîáû óáåäèòüñÿ, ÷òî âñå íåîáõîäèìûå äëÿ ðåàëè- çàöèè ïàðàëëåëüíîé ïðîãðàììû ôóíêöèè ðàáîòàþò äîëæíûì îáðàçîì è ñ îæèäàå- 112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 3 Open Fabric Alliance (OFÀ) — ìåæäóíàðîäíàÿ íåêîììåð÷åñêàÿ îðãàíèçàöèÿ, ôèíàíñèðóåìàÿ ðàçðàáîò÷èêàìè âûñîêîñêîðîñòíûõ òåõíîëîãèé. Åå çàäà÷à — óíèôèêàöèÿ ïðîòîêîëîâ âûñîêîñêîðîñòíîãî îáìåíà äàííûìè äëÿ ðàçëè÷íûõ ñåòåâûõ òåõíîëîãèé. ìîé ýôôåêòèâíîñòüþ äëÿ çàäàííûõ îáúåìîâ äàííûõ. Àâòîð ñòàëêèâàëñÿ ñî ñëó÷àÿ- ìè, êîãäà èç-çà îøèáîê â ðåàëèçàöèè MPI îïåðàöèè êîëëåêòèâíîãî îáìåíà (MPI_Bcast) âûïîëíÿëèñü íàìíîãî ìåäëåííåå ïîñëåäîâàòåëüíîé ðàññûëêè îïåðàöè- ÿìè òèïà «òî÷êà-òî÷êà» (MPI sub Send/MPI sub Recv). Ïàêåò SKaMPI [9] ïðåäíàçíà÷åí äëÿ óãëóáëåííîãî òåñòèðîâàíèÿ ôóíêöèé MPI. Âåðñèÿ 4 îò 2001 ã. âêëþ÷àåò ïîëíîñòüþ àâòîìàòèçèðîâàííûé ïðîöåññ òåñòèðîâà- íèÿ ñ ãåíåðàöèåé îò÷åòà â ôîðìàòå PostScript (.ps). Ïîñëåäíÿÿ, ïÿòàÿ, âåðñèÿ îáëà- äàåò ñëîæíûì ìåõàíèçìîì íàñòðîåê äëÿ îïèñàíèÿ çàäà÷è òåñòèðîâàíèÿ, ÷òî ïîçâîëÿåò ñôîêóñèðîâàòü èññëåäî- âàíèÿ íà îïðåäåëåííóþ ôóíêöèî- íàëüíîñòü. Ïðîâåäåííûå íà êîìïëåêñå Èíïàðêîì-64 ýêñïåðèìåíòû ñâèäå- òåëüñòâóþò, ÷òî ýôôåêòèâíîñòü ðàçíûõ ðåàëèçàöèé MPI ìîæåò âåñüìà îòëè÷àòüñÿ. Íà pèñ. 5 ïðèâå- äåíû ðåçóëüòàòû ñðàâíåíèÿ ñêîðîñ- òè ïåðåäà÷è ñîîáùåíèÿ äëÿ ðàçíûõ ðåàëèçàöèé MPI, ïîääåðæèâàþùèõ ñåòè InfiniBand. Êðèâûìè ïðîèëëþ- ñòðèðîâàíà çàâèñèìîñòü âðåìåíè ïå- ðåäà÷è ñîîáùåíèÿ îò åãî îáúåìà â áàéòàõ.  òàáë. 1 ïåðå÷èñëåíû ðåà- ëèçàöèè MPI, ïðèìåíÿÿ êîòîðûå óäà- ëîñü äîñòè÷ü ìàêñèìàëüíîé ñêîðîñòè îòäåëüíûõ îïåðàöèé. Äëÿ íåêîòîðûõ çàäà÷, îñîáåííî ñâÿçàííûõ ñ îäíîðîäíîé îáðàáîòêîé äàííûõ áîëüøîãî îáúåìà, êðàéíå âàæíà ñêîðîñòü äîñòóïà ê äèñêîâîé ïàìÿòè. Îäíà èç ïðî- ñòûõ óòèëèò èçìåðåíèÿ ñêîðîñòè äèñêîâîé ïàìÿòè — Bonnie. Ïðîãðàììíûé ïàêåò IoMeter èñïîëüçóþò äëÿ èçó÷åíèÿ äîñòóïà ê äèñêîâîé ïà- ìÿòè, ìèíóÿ ôàéëîâóþ ñèñòåìó. Òàêæå ïàêåò ïîçâîëÿåò òåñòèðîâàòü äîñòóï ê äèñ- êîâîé ïàìÿòè ñîãëàñíî ïàòòåðíó, îïðåäåëÿåìîìó äîëåé ÷òåíèÿ/çàïèñè è óðîâíåì «ñëó÷àéíîñòè» äîñòóïà. Ïðîâåäåííîå NERSC âûÿâëåíèå òèïè÷íûõ ïàòòåðíîâ ðàáîòû ñ äèñêîâîé ïà- ìÿòüþ îñíîâàíî íà ïðàêòèêå ñîáñòâåííîãî èññëåäîâàòåëüñêîãî öåíòðà â îáñëóæè- âàíèè íàó÷íî-èññëåäîâàòåëüñêèõ ðàñ÷åòîâ äëÿ áîëåå 300 ïîëüçîâàòåëåé, èç êîòî- ðûõ âûáðàíî 50 íàèáîëåå èíòåíñèâíî èñïîëüçóþùèõ äèñêîâóþ ïàìÿòü [9]. Ðåçóëü- òàòîì ñòàë èçâåñòíûé ïàêåò IOR äëÿ èçìåðåíèÿ ñêîðîñòè äèñêîâîé ïàìÿòè, îðèåíòèðîâàííûé íà âûñîêîïðîèçâîäèòåëüíûå âû÷èñëåíèÿ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 113 0 2 4 6 8 10 12 14 16 0 2 4 6 8 10 Ðàçìåð ñîîáùåíèÿ, Ìá  ð å ì ÿ , ñ OpenMPI LAM MPI MPICH Pèñ. 5 Ðàçìåð ñîîáùåíèÿ, Ìá  ð åì ÿ , ñ Ò à á ë è ö à 1 . Ðåàëèçàöèè MPI, íàèáîëåå áûñòðûå ïðè âûïîëíåíèè îïåðàöèé Îïåðàöèè MPI Îáùàÿ ïàìÿòü Ðàñïðåäåëåííàÿ ïàìÿòü Ëàòåíòíîñòü Ïðîïóñêíàÿ ñïîñîáíîñòü Ëàòåíòíîñòü Ïðîïóñêíàÿ ñïîñîáíîñòü MPI_Send/MPI_Recv LAM MPI OpenMPI LAM MPI OpenMPI MPI_Bsendrecv LAM MPI MPICH LAM MPI MPICH MPI_Barrier OpenMPI – OpenMPI – MPI_Bcast LAM MPI OpenMPI LAM MPI OpenMPI MPI_Reduce LAM MPI OpenMPI LAM MPI OpenMPI MPI_Allreduce LAM MPI OpenMPI LAM MPI OpenMPI MPI_Gather LAM MPI OpenMPI LAM MPI OpenMPI MPI_AllToAll OpenMPI OpenMPI MPICH OpenMPI Ïîñëå ïðîâåðêè êàæäîãî êîìïîíåíòà êàæäîãî óçëà ìîæíî ïðèñòóïàòü ê òåñòè- ðîâàíèþ ïðîèçâîäèòåëüíîñòè â öåëîì. Òåñò LINPACK, â íåêîòîðîì ñìûñëå, ÿâëÿåòñÿ ñëó÷àéíîñòüþ, ïîñêîëüêó èçíà- ÷àëüíî çàäóìàí êàê âñïîìîãàòåëüíàÿ óòèëèòà äëÿ îöåíêè âðåìåíè ðåøåíèÿ ñèñòåì ëèíåéíûõ óðàâíåíèé ñ èñïîëüçîâàíèåì áèáëèîòåêè LINPACK [11]. Ðóêîâîäñòâî ïî áèáëèîòåêå LINPACK çà 1979 ã. ñîäåðæàëî ðåçóëüòàòû ïî ÑËÀÓ 100-ãî ïîðÿäêà äëÿ ðàñïðîñòðàíåííûõ â òî âðåìÿ êîìïüþòåðîâ. Çíàÿ ýòè ðåçóëüòàòû, ïîëüçîâàòåëè ìîãëè âûáðàòü ïîäõîäÿùèé êîìïüþòåð äëÿ ðåøåíèÿ èõ çàäà÷ è îöåíèòü âðåìÿ ðå- øåíèÿ, ýêñòðàïîëèðóÿ äàííûå èç ðóêîâîäñòâà. Ñî âðåìåíåì ñïèñîê «ïðîèçâîäè- òåëüíîñòè íà òåñòå LINPACK» ðàñøèðÿëñÿ íà äîáðîâîëüíûõ íà÷àëàõ è äîñòèã ïî- ðÿäêà 1300 êîìïüþòåðîâ.  íàñòîÿùåå âðåìÿ òåñò LINPACK4 ÿâëÿåòñÿ ñòàíäàðòîì äå-ôàêòî äëÿ âû÷èñëåíèÿ ñêîððåêòèðîâàííîé ïèêîâîé ïðîèçâîäèòåëüíîñòè ïðè ñðàâíåíèè ðàçíûõ êîìïüþòåðîâ. Ïðîåêò «Top-500», íà÷àòûé â 1993 ã., îòñëåæèâàåò 500 íàèáîëåå ìîùíûõ ñóïåðêîì- ïüþòåðîâ â ìèðå è ïóáëèêóåò ðåçóëüòàòû äâàæäû â ãîä.  2008 ã. íà÷àë ôóíêöèîíèðî- âàòü ïðîåêò Green500, ó÷àñòíèêè êîòîðîãî ïóáëèêóþò ðåéòèíã 500 ñóïåðêîìïüþòåðîâ èç ñïèñêà «Top-500», â ïîðÿäêå ïðîèçâîäèòåëüíîñòè íà âàòò ýëåêòðîýíåðãèè. Òåñò LINPACK ïîçâîëÿåò ïîëó÷èòü õîðîøóþ êîððåêöèþ ïèêîâîé ïðîèçâîäè- òåëüíîñòè, ïðèâîäÿ ôàêòè÷åñêè âåðõíþþ ãðàíèöó âîçìîæíîãî ðàñïàðàëëåëèâàíèÿ ïðèêëàäíûõ çàäà÷. Óòâåðäèëñÿ ìèô, ÷òî, èñïîëüçóÿ ïðîèçâîäèòåëüíîñòü, êîòîðîé óäàëîñü äîñòè÷ü íà òåñòå LINPACK è êîòîðóþ ñïåêóëÿòèâíî íàçûâàþò «ðåàëüíîé», ìîæíî àäåêâàòíî ñïðîãíîçèðîâàòü ýôôåêòèâíîñòü ïðèêëàäíîãî ïðèëîæåíèÿ. Ýòî äàëåêî íå âñåãäà òàê, äàæå åñëè ðåøàåìàÿ çàäà÷à — íàõîæäåíèå ðåøåíèÿ ÑËÀÓ. Íà ïðàêòèêå óäà÷íûìè ìîæíî ñ÷èòàòü òå ïðèêëàäíûå ïðîãðàììû, ïðîèçâîäèòåëü- íîñòü êîòîðûõ ïðåâûøàåò 10% ïðîèçâîäèòåëüíîñòè, ïîêàçàííîé òåñòîì LINPACK. Ýòî ïðîèñõîäèò ïî ðÿäó ïðè÷èí. 1. Ðåçóëüòàòû, èìåþùèå ìàêñè- ìàëüíóþ ïðîèçâîäèòåëüíîñòü, ïîëó- ÷àþò ïîäáîðîì ðàçìåðà çàäà÷è. Íà ïðàêòèêå, åñëè çàäàííûé ðàçìåð çàäà- ÷è îòëè÷àåòñÿ îò îïòèìàëüíîãî â áîëüøóþ èëè ìåíüøóþ ñòîðîíó, ïðîèçâîäèòåëüíîñòü îêàçûâàåòñÿ íèæå îïòèìàëüíîé. Íà ðèñ. 6 ïîêàçàíû ðåçóëüòàòû ýêñïåðèìåíòîâ íà òåñòå LINPACK, ïðîâåäåííûõ íà êîìïëåêñå Èíïàð- êîì-128 íà âñåõ ÿäðàõ. Èç ãðàôèêà âèäíî, ÷òî ìàêñèìàëüíàÿ ýôôåê- òèâíîñòü äîñòèãàåòñÿ, òîëüêî åñëè çàäà÷à äîñòàòî÷íî áîëüøàÿ, ÷òîáû çàíÿòü âñþ îïåðàòèâíóþ ïàìÿòü êîìïëåêñà. Åñëè çàäà÷à íàñòîëüêî áîëüøàÿ, ÷òî íå ïîìåùàåòñÿ â îïåðàòèâíóþ ïàìÿòü, âðåìÿ ðåøåíèÿ ñòðåìèòåëüíî ïàäàåò. 2. Ðåçóëüòàòû ïîëó÷åíû íà òåñòå LINPACK ïåðåáîðîì ìíîãî÷èñëåííûõ ïàðà- ìåòðîâ, âëèÿþùèõ íà ïðîèçâîäèòåëüíîñòü (ñðåäè íèõ: ðàçìåð áëîêà, êîíôèãóðàöèÿ ðàçáèåíèÿ íà áëîêè, òîïîëîãèÿ îáìåíîâ). Ïîäáîð ïàðàìåòðîâ — äëèòåëüíûé ïðîöåññ (äî íåäåëü) «èñêóñíîãî» ïîëó÷åíèÿ ìàêñèìàëüíîé ïðîèçâîäèòåëüíîñòè íà òåñòå LINPACK. Äëÿ ðåàëüíûõ çàäà÷ çàíèìàòüñÿ ïåðåáîðîì íå õâàòàåò âðåìåíè. 3. Ïðîèçâîäèòåëüíîñòü ïàðàëëåëüíîé ïðîãðàììû çàâèñèò îò áàëàíñèðîâêè íàãðóçêè ðàçíûõ ðåñóðñîâ ïàðàëëåëüíîãî êîìïüþòåðà: ÿäåð, îïåðàòèâíîé ïàìÿòè, ñåòè, äèñêîâ. Òåñò LINPACK îáëàäàåò ôèêñèðîâàííûì ñîîòíîøåíèåì èíòåíñèâíîñòè èñïîëüçîâàíèÿ ýòèõ ðåñóðñîâ, êîòîðîå ðåäêî ñîâïàäàåò ñ ñîîòíîøåíèÿìè ïðèêëàäíûõ çàäà÷. 114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 0 200 400 600 800 1000 1200 1400 0 50000 100000 150000 200000 Ïîðÿäîê ÑËÀÓ (n) Ï ð î è çâ î ä è òå ë ü í î ñ òü , Ã Ô ë î ï ñ Ïðîèçâîäèòåëüíîñòü íà òåñòå LINPACK Ïèêîâàÿ ïðîèçâîäèòåëüíîñòü Ðèñ. 6 Ïîðÿäîê ÑËÀÓ, ( )n Ï ð î è çâ î ä è òå ë ü í î ñò ü , Ã Ô ë î ï ñ Ïðîèçâîäèòåëüíîñòü íà òåñòå LINPACK Ïèêîâàÿ ïðîèçâîäèòåëüíîñòü 4  çàâèñèìîñòè îò àðõèòåêòóðû ïàðàëëåëüíîãî êîìïüþòåðà ñóùåñòâóþò ðàçíûå ðåàëèçàöèè «LINPACK Benchmark», íàçûâàåìûå ïî-ðàçíîìó, íàïðèìåð: «LINPACK 100», «LINPACK 1000», «LINPACK Parallel», «HPL». 4. Äîñòóï ê äèñêîâîé ïàìÿòè íå ó÷èòûâàåòñÿ. Äàæå ìàòðèöó ÑËÀÓ äëÿ òåñòà LINPACK â îïåðàòèâíîé ïàìÿòè ñîçäàåò ãåíåðàòîð ïñåâäîñëó÷àéíûõ ÷èñåë, à íà ïðàêòè- êå åå ñ÷èòûâàþò ñ äèñêà. Ïðè äîñòàòî÷íî áîëüøèõ îáúåìàõ (äåñÿòêè è ñîòíè Ãá) ÷òåíèå èñõîäíûõ äàííûõ è ñîõðàíåíèå ðåçóëüòàòîâ ñîñòàâëÿåò âåñîìóþ äîëþ âû÷èñëåíèé. 5. Ïðîèçâîäèòåëüíîñòü ïî òåñòó LINPACK ìîæåò äàòü òîëüêî êà÷åñòâåííîå ïðåäñòàâëåíèå î ïðîèçâîäèòåëüíîñòè ïðèêëàäíîé ïðîãðàììû, ïîñêîëüêó, âî-ïåð- âûõ, ñëîæíî èçìåðèòü ïðîèçâîäèòåëüíîñòü ïðèêëàäíîé ïðîãðàììû (âî ôëîïñàõ), à èíîãäà è íåâîçìîæíî; âî-âòîðûõ, äëÿ ïðèêëàäíîé ïðîãðàììû âàæíî âðåìÿ âû- ïîëíåíèÿ, íåëèíåéíî çàâèñÿùåå îò ïðîèçâîäèòåëüíîñòè. Ïðîèçâîäèòåëüíîñòü ïàðàëëåëüíîãî êîìïüþòåðà íåâîçìîæíî ïðåäñòàâèòü îäíèì ÷èñëîì. Ïîñêîëüêó òåñò LINPACK ÷àñòî èñïîëüçóþò íå ïî íàçíà÷åíèþ, îøèáî÷íî íàäåÿñü äîáèòüñÿ ýôôåêòèâíîñòè, ñðàâíèìîé ñ åãî ïîêàçàòåëÿìè, ðàçðà- áîò÷èêè LINPACK ïðåäëîæèëè íîâûé ïàêåò òåñòèðîâàíèÿ HPCC (HPC Challenge Benchmark Suite) [12]. Åãî çàäà÷à — èçìåðåíèå ïðîèçâîäèòåëüíîñòè ðàçíûõ êîìïî- íåíòîâ ïàðàëëåëüíîãî êîìïüþòåðà, ñïîñîáíûõ îãðàíè÷èòü âûïîëíåíèå ïðèêëàäíûõ ïðîãðàìì. Ýòîò ïàêåò ñîñòîèò èç íåñêîëüêèõ èçâåñòíûõ ïàêåòîâ, èçìåðÿþùèõ îò- äåëüíûå àñïåêòû ïðîèçâîäèòåëüíîñòè, à òàêæå ïðåäîñòàâëÿåò ñðåäó äëÿ ïîäêëþ÷å- íèÿ äîïîëíèòåëüíûõ òåñòîâ.  ÷àñòíîñòè, ïàêåò HPCC âêëþ÷àåò òàêèå èçâåñòíûå ïðîãðàììû èçìåðåíèÿ ïðîèçâîäèòåëüíîñòè, êàê STREAM (ñêîðîñòü îïåðàòèâíîé ïàìÿòè), HPL, DGEMM (óìíîæåíèå ìàòðèö), PTRANS (òðàíñïîíèðîâàíèå ìàòðèö, FFT, RandomAccess (ñêîðîñòü ïðîèçâîëüíîãî äîñòóïà ê ïàìÿòè), b_eff (ëàòåíòíîñòü è ïðîïóñêíàÿ ñïîñîáíîñòü êàíàëîâ). Ðåçóëüòàò èçìåðåíèÿ ïðîèçâîäèòåëüíîñòè â HPCC — íå îäíî, à ðÿä çíà÷åíèé ïðîèçâîäèòåëüíîñòè. Êîììåð÷åñêèé ïàêåò SPEC CPU 2006 âêëþ÷àåò ðÿä ïàðàëëåëüíûõ ðàñ÷åòíûõ ìîäóëåé äëÿ èçâåñòíûõ ïðèêëàäíûõ ïðîãðàìì. Ïðè èññëåäîâàíèè êîìïüþòåðà ýòîò ïàêåò ïîñëåäîâàòåëüíî âûïîëíÿåò êîíòðîëüíûå ïðèìåðû êëàññîâ çàäà÷ ãèäðîäèíà- ìèêè, êâàíòîâîé õèìèè, áèîëîãèè, êîíå÷íî-ðàçíîñòíûõ è êîíå÷íî-ýëåìåíòíûõ ñõåì, ëèíåéíîãî ïðîãðàììèðîâàíèÿ, ðàñïîçíàâàíèÿ îáðàçîâ. Ðåçóëüòàòû èññëåäîâà- íèé â ýòîì ïàêåòå äàþò êàðòèíó ïðîèçâîäèòåëüíîñòè êîìïüþòåðà, ïðèîáðåòàåìîãî ïîä ðåøåíèå êëàññà çàäà÷. (Íà ìîìåíò íàïèñàíèÿ ñòàòüè óêàçàííûé ïàêåò ïîääåð- æèâàåò òîëüêî êîìïüþòåðû ñ îáùåé ïàìÿòüþ.) ÈÑÑËÅÄÎÂÀÍÈÅ ÏÐÎÈÇÂÎÄÈÒÅËÜÍÎÑÒÈ ÃÎÒÎÂÛÕ ÏÐÎÃÐÀÌÌ Èíïàðêîì (Èíòåëëåêòóàëüíûé ïàðàëëåëüíûé êîìïüþòåð) — ñåìåéñòâî àïïàðàòíî-ïðî- ãðàììíûõ êîìïëåêñîâ, ðàçðàáîòàííûõ Èíñòèòóòîì êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû ñîâìåñòíî ñ ÃÍÏÏ «Ýëåêòðîíìàø». Èíòåëëåêòóàëüíîå ïðîãðàììíîå îáåñïå÷åíèå êîìïëåêñîâ Èíïàðêîì ïîçâîëÿåò èññëåäîâàòü è ðåøàòü ðÿä àêòóàëüíûõ â íàóêå è èíæåíåðèè ìàòåìàòè÷åñêèõ çàäà÷ [13]. Íà äàííûé ìîìåíò êîìïëåêñû Èíïàðêîì ãîòîâû ê ñåðèéíîìó ïðîèçâîäñòâó (òàáë. 2). Äëÿ êîìïëåêñîâ Èíïàðêîì ðåàëèçîâàíà ñèñòåìà óïðàâëåíèÿ êëàñòåðîì ACMS ñ öåíòðàëèçîâàííûì óïðàâëåíèåì ðåñóðñàìè è ìîíèòîðèíãîì [14].  ñîñòàâ ACMS âêëþ÷åí ïîëüçîâàòåëüñêèé èíòåðôåéñ äëÿ èçó÷åíèÿ ýôôåêòèâíîñòè ïàðàëëåëüíîé ïðîãðàììû, ïðîãíîçà ýôôåêòèâíîñòè, óñêîðåíèÿ è âðåìåíè âûïîëíåíèÿ ïàðàëëåëü- íîé ïðîãðàììû íà ðàçíîì ÷èñëå ÿäåð. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 115 Ò à á ë è ö à 2 . Ëèíåéêà êîìïëåêñîâ ñåìåéñòâà Èíïàðêîì Íàçâàíèå êîìïëåêñà Êîëè÷åñòâî óçëîâ Êîëè÷åñòâî ÿäåð Äèñêîâîå õðàíèëèùå Ïðîèçâîäèòåëüíîñòü, ÃÔëîïñ Ãîä ñäà÷è Ïèêîâàÿ LINPACK Èíïàðêîì-8 1 8 – 75 63 2008 Èíïàðêîì-16 16 16 – 102 82 2005 Èíïàðêîì-32 16 32 – 205 161 2006 Èíïàðêîì-64 8 64 îò 1 Òá 596 486 2007 Èíïàðêîì-128 16 128 îò 1 Òá 1193 970 2008 Èíïàðêîì-256 32 256 îò 1 Òá 2386 1854 2008 Äëÿ çàïóñêà ïàðàëëåëüíîé ïðîãðàììû íà êîìïëåêñå Èíïàðêîì íóæíî ñîçäàòü òàê íàçûâàåìûé ïðîôèëü çàäàíèÿ, â êîòîðîì óêàçàòü ÷èñëî ÿäåð äëÿ âûïîëíåíèÿ ïðîãðàììû. Åñëè âûïîëíåí îäèí ïðîôèëü íà ðàçíîì ÷èñëå ÿäåð, àâòîìàòè÷åñêè ñî- áèðàåòñÿ ñòàòèñòèêà è àíàëèçèðóåòñÿ ýôôåêòèâíîñòü. Íà ðèñ. 7 ïîêàçàíî âðåìÿ âû- ïîëíåíèÿ òåñòà LINPACK íà ðàçíîì ÷èñëå ÿäåð. Ïî ãðàôèêó âðåìåíè âûïîëíåíèÿ ïðîãðàììû äëÿ ðàçíîãî ÷èñëà ïðîöåññîðîâ ñëîæíî ÷òî-ëèáî ñêàçàòü îá ýôôåêòèâ- íîñòè, ïîýòîìó â ïðîòîêîëå èññëåäîâàíèé íà ðèñ. 8 ïîêàçàíû òàêæå ãðàôèêè óñêî- ðåíèÿ ýôôåêòèâíîñòè è íàêëàäíûõ çàòðàò. Íà ðèñ. 7, 8 ïðèâåäåíû ãðàôèêè äëÿ òåñòà LINPACK. Ìàêñèìàëüíîå óñêîðåíèå íà êîìïëåêñå Èíïàðêîì-256 íå äîñòèãíóòî, çíà÷èò, óâåëè÷èâ ÷èñëî ïðîöåññîðîâ óêàçàííîé àðõèòåêòóðû, ïîëó÷èì ëó÷øèå ðåçóëüòàòû ïî òåñòó LINPACK, äàæå íå íàðàùèâàÿ ðàçìåðíîñòü çàäà÷è. 116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 Ðèñ. 7 Ðèñ. 8 Ðèñ. 9 Íà ðèñ. 9 ïðèâåäåíû ãðàôèêè óñêîðåíèÿ è ýôôåêòèâíîñòè äëÿ îäíîé èç ïðè- êëàäíûõ çàäà÷, ðåøåííîé íà êîìïëåêñå. Îïòèìàëüíîå ÷èñëî ÿäåð äëÿ ýòîé çàäà- ÷è — ïðèìåðíî 80. ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåå âðåìÿ ïðîèñõîäèò ñìåíà ïàðàäèãì ïðîãðàììèðîâàíèÿ, à ýâîëþöèÿ îáîðóäîâàíèÿ îïåðåæàåò ïðîãðàììíûå ñðåäñòâà, êîìïüþòåðû ñ ðàçäåëåííîé ïà- ìÿòüþ âûøëè çà ïðåäåëû ïðîèçâîäèòåëüíîñòè â 1 ÏÔëîïñ. Ñíîâà àêòóàëüíû ïðîáëåìû, êîòîðûìè çàíèìàëèñü îòå÷åñòâåííûå ó÷åíûå â 1970–1980 ãã., ñðåäè íèõ ïðîåêòèðîâàíèå è îïòèìèçàöèÿ ìàêðîêîíâåéåðíûõ ñåòåé Â.Ì. Ãëóøêîâà äëÿ ðàçðàáîòêè ýôôåêòèâíûõ ïàðàëëåëüíûõ àëãîðèòìîâ ñ êîíòðîëüíûìè òî÷êàìè è âîçîáíîâëåíèåì ïîñëå ñáîåâ íà ñâåðõáîëüøîì ÷èñëå ïðîöåññîðîâ [15]. Ïðîâî- äÿòñÿ íîâûå èññëåäîâàíèÿ äîñòîâåðíîñòè ðåçóëüòàòîâ (â ÷àñòíîñòè, àíàëèç ÷èñëà îáóñëîâëåííîñòåé), à òàêæå ýìóëèðóåìîé è èíòåðâàëüíîé àðèôìåòèêè, àðèôìå- òèêè ñî ñìåøàííîé ðàçðÿäíîñòüþ [16]. ×òî êàñàåòñÿ ïðîèçâîäèòåëüíîñòè êîìïüþòåðîâ, òî íå ñóùåñòâóåò îäíîãî ÷èñ- ëà, äîñòàòî÷íîãî äëÿ õàðàêòåðèñòèêè ïàðàëëåëüíîãî êîìïüþòåðà. Áóäóùåå çà ìíî- ãîêðèòåðèàëüíûì ñðàâíåíèåì ïðîèçâîäèòåëüíîñòè ïîä êîíêðåòíûé êëàññ çàäà÷ íà îñíîâå ðåçóëüòàòîâ òàêèõ ðàñøèðåííûõ ïàêåòîâ èçìåðåíèÿ ïðîèçâîäèòåëüíîñòè, êàê HPCC. Èíòåëëåêòóàëüíûå ñðåäñòâà èññëåäîâàíèÿ è ïðîãíîçèðîâàíèÿ ïðîèçâî- äèòåëüíîñòè îòêðûâàþò íîâûå âîçìîæíîñòè â âûáîðå îïòèìàëüíîãî ÷èñëà ïðîöåñ- ñîðîâ, ïëàíèðîâàíèè çàäàíèé è áàëàíñèðîâêå çàãðóçêè. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. P e r f o r m a n c e of various computers using standard linear equations software: LINPACK benchmark report / J. Dongarra; Univ. of Tennessee. — 2008. — 89 p. 2. à ë ó ø ê î â  . Ì . , Ê à ï è ò î í î â à Þ .  . , Ë å ò è ÷ å â ñ ê è é À . À . Ê òåîðèè ïðîåêòèðîâàíèÿ ñõåìíîãî è ïðîãðàììíîãî îáîðóäîâàíèÿ ìíîãîïðîöåññîðíûõ ÝÂÌ // Êèáåðíåòèêà. — 1978. — ¹ 6. — Ñ. 1–15. 3. S o m e issues in dense linear algebra for multicore and special purpose architectures: EECS Tech. Report LAWN #200 / M. Baboulin, J. Dongarra, S. Tomov. — 2008. — 615 p. 4. G r a m a A . Y . , G u p t a A . , K u m a r V . Isoefficiency: Measuring the scalability of parallel algo- rithms and architectures // EEE Computer Soc. Press. — 1993. — 1, N 3. — P. 12–21. 5. Ï å ð å â î ç ÷ è ê î â à Î . Ë . , Ò ó ë ü ÷ è í ñ ê è é  . à . , Þ ù å í ê î Ð . À . Ïîñòðîåíèå è îïòè- ìèçàöèÿ ïàðàëëåëüíûõ êîìïüþòåðîâ äëÿ îáðàáîòêè áîëüøèõ îáúåìîâ äàííûõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 4. — Ñ. 117–129. 6. Þ ù å í ê î Ð . À . Îöåíêà ýôôåêòèâíîñòè ñóïåðêîìïüþòåðíûõ àðõèòåêòóð äëÿ ðàçëè÷íûõ ïàò- òåðíîâ ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ // Èñêóññòâ. èíòåëëåêò. — 2007. — ¹ 3. — Ñ. 447–453. 7. G a m m a E . , H e l m R . , J o h n s o n R . , e t a l . Design patterns: Elements on reusable object-ori- ented software. — New York: Addison–Wesley, 1995. — 385 p. 8. M a t t s o n T . , S a n d e r s B . , M a s s i n g i l B . L . Patterns for parallel programming. — New York: Addison-Wesley, 2004. — 355 p. 9. R e u s s n e r R . , S a n d e r s P . , P r e c h e l t L . , e t a l . SKaMPI: A detailed, accurate MPI benchmark // Proc. Int. Conf. “EuroPVM/MPI’98”. — Liverpool: Kluwer Acad. Pub., 1998. — P. 83–93. 10. S h a n H . , S h a l f J . Using IOR to Analyze the I/O performance for HPC Platforms / Lawrence Berkeley Nat. Lab. — Paper LBNL-62647. — 2007. (http://repositories.cdlib.org/lbnl/LBNL-62647) 11. D o n g a r r a J . , L u s z c z e k P . , P e t i t e t A . The LINPACK Benchmark: Past, present, and future // Concurrency and Computation: Practice and Experience. — 2002. — 15, N 9. — P. 803–820. 12. I n t r o d u c t i o n to the HPC Challenge Benchmark Suite / P. Luszczek, J.J. Dongarra, D. Koester, et al. // http://icl.cs.utk.edu/projectsfiles/hpcc/pubs/hpcc-challenge-benchmark05.pdf 13. × è ñ ë å í í î å ïðîãðàììíîå îáåñïå÷åíèå MIMD-êîìïüþòåðà Èíïàðêîì / À.Í. Õèìè÷, È.Í. Ìîë- ÷àíîâ, Â.È. Ìîâà, Î.Ë. Ïåðåâîç÷èêîâà è äð. — Êèåâ: Íàóê. äóìêà, 2007. — 221 ñ. 14. Þ ù å í ê î Ð . À . Ñèñòåìà óïðàâëåíèÿ êëàñòåðîì äëÿ êîìïëåêñîâ Èíïàðêîì // Êîìïüþòåðíàÿ ìàòåìàòèêà. — 2007. — ¹ 1. — Ñ. 96–103. 15. A l g o r i t h m i c based fault tolerance applied to high performance computing / G. Bosilca, R. Delmas, J. Dongarra, J. Langou // LAPACK Working Note. — 2008. — N 205. — P. 5–17. 16. A c c e l e r a t i n g scientific computations with mixed precision algorithms / M. Baboulin, A. Buttari, J. Dongarra, et al. // Computational Physics. — 2008. — P. 35–49. Ïîñòóïèëà 07.07.2009 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 117
id nasplib_isofts_kiev_ua-123456789-44488
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 0023-1274
language Russian
last_indexed 2025-11-27T15:16:46Z
publishDate 2009
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
record_format dspace
spelling Ющенко, Р.А.
2013-06-02T09:16:35Z
2013-06-02T09:16:35Z
2009
Измерение производительности параллельных компьютеров с распределенной памятью / Р.А. Ющенко // Кибернетика и системный анализ. — 2009. — № 6. — С. 106-117. — Бібліогр.: 16 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/44488
681.3
Розглянуто основні механізми вимірювання продуктивності паралельних комп’ютерів із розподіленою пам’яттю. Показано, що результати, отримані на де-факто стандартному тесті LINPACK, здебільшого мало пов’язані з ефективністю програм і застосувань. В результаті знову набули актуальності моделі та методи макроконвеєрних обчислень, сформульовані В.М. Глушковим ще наприкінці 1970-х років Результати цих досліджень висвітлено з позицій сучасної архітектури кластерних комплексів.
The basic techniques for measuring the performance of distributed memory parallel computers are reviewed. The results obtained via de-facto standard LINPACK benchmark suite are shown to be weakly related to the efficiency of applied parallel programs. As a result, models and methods of macro-piping computations proposed by V.M. Glushkov in the late 1970s become topical again. These results are presented in the context of the modern architecture of cluster complexes.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Программно-технические комплексы
Измерение производительности параллельных компьютеров с распределенной памятью
Вимірювання продуктивності паралельних комп’ютерів з розподіленою пам’яттю
Performance measurement for distributed memory parallel computers
Article
published earlier
spellingShingle Измерение производительности параллельных компьютеров с распределенной памятью
Ющенко, Р.А.
Программно-технические комплексы
title Измерение производительности параллельных компьютеров с распределенной памятью
title_alt Вимірювання продуктивності паралельних комп’ютерів з розподіленою пам’яттю
Performance measurement for distributed memory parallel computers
title_full Измерение производительности параллельных компьютеров с распределенной памятью
title_fullStr Измерение производительности параллельных компьютеров с распределенной памятью
title_full_unstemmed Измерение производительности параллельных компьютеров с распределенной памятью
title_short Измерение производительности параллельных компьютеров с распределенной памятью
title_sort измерение производительности параллельных компьютеров с распределенной памятью
topic Программно-технические комплексы
topic_facet Программно-технические комплексы
url https://nasplib.isofts.kiev.ua/handle/123456789/44488
work_keys_str_mv AT ûŝenkora izmerenieproizvoditelʹnostiparallelʹnyhkompʹûterovsraspredelennoipamâtʹû
AT ûŝenkora vimírûvannâproduktivnostíparalelʹnihkompûterívzrozpodílenoûpamâttû
AT ûŝenkora performancemeasurementfordistributedmemoryparallelcomputers

Схожі ресурси