Теория и практика параллельных вычислений

         

Блочная схема разделения данных


Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов (см. рис. 11.9). При этом столь радикальное изменение способа разбиения сетки практически не потребует каких-либо существенных корректировок рассмотренной схемы параллельных вычислений. Основной новый момент при блочном представлении данных состоит в увеличении количества граничных строк на каждом процессоре (для блока их количество становится равным 4), что приводит, соответственно, к большему числу операций передачи данных при обмене граничных строк. Сравнивая затраты на организацию передачи граничных строк, можно отметить, что при ленточной схеме для каждого процессора выполняется 4 операции приема-передачи данных, в каждой из которых пересылаются (N+2) значения. Для блочного же способа происходит 8 операций пересылки и объем каждого сообщения равен (N – количество внутренних узлов сетки, NP – число процессоров, размер всех блоков предполагается одинаковым). Тем самым, блочная схема представления области расчетов становится оправданной при большом количестве узлов сетки, когда увеличение количества коммуникационных операций приводит к снижению затрат на пересылку данных в силу сокращения размеров передаваемых сообщений. Результаты экспериментов при блочной схеме разделения данных приведены в табл. 11.5.

Таблица 11.5. Результаты экспериментов для систем с распределенной памятью, блочная схема разделения данных (p=4)

Размер сеткиПоследовательный метод Гаусса - Зейделя (алгоритм 11.1)Параллельный алгоритм с блочной схемой рассчета (см. п. 11.3.5)Параллельный алгоритм 11.9ktktSktS
1002100,062100,710,082100,600,10
2002730,352730,740,472731,060,33
3003050,923051,040,883052,010,46
4003181,693181,441,183182,630,64
5003432,883431,911,513433,600,80
6003364,043362,391,693364,630,87
7003445,683442,961,923445,810,98
8003437,373433,582,063437,650,96
9003589,943584,502,213589,571,04
100035111,873514,902,4235111,161,06
200036750,1936716,073,1236739,491,27
3000364113,1736439,252,8836485,721,32



Содержание  Назад  Вперед







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