Характеристика системных платформ для построения кластеров
В качестве системной платформы для построения кластеров используют обе наиболее распространенные в настоящий момент операционные системы Unix и Microsoft Windows. Далее в пособии подробно будет рассмотрено решение на основе ОС семейства Microsoft Windows; характеристика подхода на базе ОС Unix может быть получена, например, в [71].
Microsoft Compute Cluster Server 2003 (CCS) представляет собой интегрированную платформу для поддержки высокопроизводительных вычислений на кластерных системах. CCS состоит из операционной системы Microsoft Windows Server 2003 и Microsoft Compute Cluster Pack (CCP) – набора интерфейсов, утилит и инфраструктуры управления. Вместе с CCP поставляется SDK, содержащий необходимые инструменты разработки программ для CCS, включая собственную реализацию MPI (Microsoft MPI). Кроме того, к Microsoft Compute Cluster Server 2003 логически примыкает Microsoft Visual Studio 2005 — интегрированная среда разработки (IDE), содержащая компилятор и отладчик программ, разработанных с использованием технологий MPI и OpenMP.
В качестве вычислительных узлов кластера могут быть применены 64-битные процессоры семейства x86 c, как минимум, 512 Мб оперативной памяти и 4 Гб свободного дискового пространства.
На вычислительных узлах кластера должна быть установлена операционная система Microsoft Windows Server 2003 (Standard, Enterprise или Compute Cluster Edition).
В состав CCP входит Microsoft MPI – версия реализации стандарта MPI 2 от Argonne National Labs. MS MPI совместима с MPICH 2 и поддерживает полнофункциональный API с более чем 160 функциями. MS MPI в Windows Compute Cluster Server 2003 задействует WinSock Direct протокол для наилучшей производительности и эффективного использования центрального процессора. MS MPI может использовать любое Ethernet-соединение, поддерживаемое Windows Server 2003, а также такие соединения, как InfiniBand или Myrinet, с применением WinSock Direct драйверов, поставляемых производителями аппаратного обеспечения. MS MPI поддерживает языки программирования C, Fortran 77 и Fortran 90, а Microsoft Visual Studio 2005 включает в себя параллельный отладчик, работающий с MS MPI.
Разработчики могут запустить свое MPI- приложение на нескольких вычислительных узлах, и Visual Studio автоматически соединится с процессами на каждом узле, позволяя разработчику приостанавливать приложение и просматривать значения переменных в каждом процессе отдельно.
Кроме реализации MPI в состав CCP входит удобная система планирования заданий, позволяющая просматривать состояния всех запущенных задач, собирать статистику, назначать запуски программ на определенное время, завершать "зависшие" задачи и пр. В текущей версии работа возможна либо через графический интерфейс, либо через командную строку. В окончательной версии будет предусмотрена возможность обращения к системе и через другие интерфейсы: COM, web-сервис и др.
Windows Computer Cluster Server 2003 поддерживает 5 различных сетевых топологий, при этом каждый узел может иметь от 1 до 3 сетевых карточек. Правильный выбор используемой топологии необходим для оптимального функционирования вычислительного кластера.
Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах
В мультикомпьютерах для организации взаимодействия, синхронизации и взаимоисключения параллельно выполняемых процессов используется передача данных между процессорами вычислительной среды. Временные задержки при передаче данных по линиям связи могут оказаться существенными (по сравнению с быстродействием процессоров), и, как результат, коммуникационная трудоемкость алгоритма оказывает заметное влияние на выбор параллельных способов решения задач.
Характеристики топологии сети
В качестве основных характеристик топологии сети передачи данных наиболее широко используется следующий ряд показателей:
диаметр – показатель, определяемый как максимальное расстояние между двумя процессорами сети (под расстоянием обычно понимается величина кратчайшего пути между процессорами). Эта величина может характеризовать максимально необходимое время для передачи данных между процессорами, поскольку время передачи обычно прямо пропорционально длине пути;связность (connectivity) – показатель, характеризующий наличие разных маршрутов передачи данных между процессорами сети. Конкретный вид данного показателя может быть определен, например, как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области;ширина бинарного деления (bisection width) – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера;стоимость – показатель, который может быть определен, например, как общее количество линий передачи данных в многопроцессорной вычислительной системе.
Для сравнения в таблице 1.1 приводятся значения перечисленных показателей для различных топологий сети передачи данных.
| Полный граф | 1 | p2/4 | p–1 | p(p–1)/2 |
| Звезда | 2 | 1 | 1 | p–1 |
| Полное двоичное дерево | 2log((p+1)/2) | 1 | 1 | p–1 |
| Линейка | p–1 | 1 | 1 | p–1 |
| Кольцо | p/2 | 2 | 2 | p |
| Решетка N=2 | 2 | |||
| Решетка-тор N=2 | 4 | 2p | ||
| Гиперкуб | log p | p/2 | log p | (p log p)/2 |
Классификация вычислительных систем
Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (Flynn), в рамках которой основное внимание при анализе архитектуры вычислительных систем уделяется способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных. При таком подходе различают следующие основные типы систем (см. [2, 31, 59]):
SISD (Single Instruction, Single Data) – системы, в которых существует одиночный поток команд и одиночный поток данных. К такому типу можно отнести обычные последовательные ЭВМ;SIMD (Single Instruction, Multiple Data) – системы c одиночным потоком команд и множественным потоком данных. Подобный класс составляют многопроцессорные вычислительные системы, в которых в каждый момент времени может выполняться одна и та же команда для обработки нескольких информационных элементов; такой архитектурой обладают, например, многопроцессорные системы с единым устройством управления. Этот подход широко использовался в предшествующие годы (системы ILLIAC IV или CM-1 компании Thinking Machines), в последнее время его применение ограничено, в основном, созданием специализированных систем;MISD (Multiple Instruction, Single Data) – системы, в которых существует множественный поток команд и одиночный поток данных. Относительно этого типа систем нет единого мнения: ряд специалистов считает, что примеров конкретных ЭВМ, соответствующих данному типу вычислительных систем, не существует и введение подобного класса предпринимается для полноты классификации; другие же относят к данному типу, например, систолические вычислительные системы (см. [51, 52]) или системы с конвейерной обработкой данных;MIMD (Multiple Instruction, Multiple Data) – системы c множественным потоком команд и множественным потоком данных. К подобному классу относится большинство параллельных многопроцессорных вычислительных систем.
Рис. 1.4. Классификация многопроцессорных вычислительных систем
Следует отметить, что хотя систематика Флинна широко используется при конкретизации типов компьютерных систем, такая классификация приводит к тому, что практически все виды параллельных систем (несмотря на их существенную разнородность) оказываются отнесены к одной группе MIMD. Как результат, многими исследователями предпринимались неоднократные попытки детализации систематики Флинна. Так, например, для класса MIMD предложена практически общепризнанная структурная схема (см. [24, 75]), в которой дальнейшее разделение типов многопроцессорных систем основывается на используемых способах организации оперативной памяти в этих системах (см. рис. 1.4). Такой подход позволяет различать два важных типа многопроцессорных систем – multiprocessors (мультипроцессоры или системы с общей разделяемой памятью) и multicomputers (мультикомпьютеры или системы с распределенной памятью).
Кластер ACVelocity Cluster
Кластер AC3 Velocity Cluster, установленный в Корнельском университете (США) (http://www.tc.cornell.edu), стал результатом совместной деятельности университета и консорциума AC3 (Advanced Cluster Computing Consortium), образованного компаниями Dell, Intel, Microsoft, Giganet и еще 15 производителями ПО с целью интеграции различных технологий для создания кластерных архитектур для учебных и государственных учреждений.
Состав кластера:
64 четырехпроцессорных сервера Dell PowerEdge 6350 на базе Intel Pentium III Xeon 500 MHz, 4 GB RAM, 54 GB HDD, 100 Mbit Ethernet card;1 восьмипроцессорный сервер Dell PowerEdge 6350 на базе Intel Pentium III Xeon 550 MHz, 8 GB RAM, 36 GB HDD, 100 Mbit Ethernet card.
Четырехпроцессорные серверы смонтированы по восемь штук на стойку и работают под управлением ОС Microsoft Windows NT 4.0 Server Enterprise Edition. Между серверами установлено соединение на скорости 100 Мбайт/c через Cluster Switch компании Giganet.
Задания в кластере управляются с помощью Cluster ConNTroller, созданного в Корнельском университете. Пиковая производительность AC3 Velocity составляет 122 GFlops при стоимости в 4 – 5 раз меньше, чем у суперкомпьютеров с аналогичными показателями.
На момент ввода в строй (лето 2000 года) кластер с показателем производительности на тесте LINPACK в 47 GFlops занимал 381-ю строку списка Top 500.
Кластер Beowulf
Первым в мире кластером, по-видимому, является кластер, созданный под руководством Томаса Стерлинга и Дона Бекера в научно-космическом центре NASA – Goddard Space Flight Center – летом 1994 года. Названный в честь героя скандинавской саги, обладавшего, по преданию, силой тридцати человек, кластер состоял из 16 компьютеров на базе процессоров 486DX4 с тактовой частотой 100 MHz. Каждый узел имел 16 Mb оперативной памяти. Связь узлов обеспечивалась тремя параллельно работавшими 10 Mbit/s сетевыми адаптерами. Кластер функционировал под управлением операционной системы Linux, использовал GNU-компилятор и поддерживал параллельные программы на основе MPI. Процессоры узлов кластера были слишком быстрыми по сравнению с пропускной способностью обычной сети Ethernet, поэтому для балансировки системы Дон Бекер переписал драйверы Ethernet под Linux для создания дублированных каналов и распределения сетевого трафика.
Идея "собери суперкомпьютер своими руками" быстро пришлась по вкусу, в первую очередь академическому сообществу. Использование типовых массово выпускающихся компонентов, как аппаратных, так и программных, вело к значительному уменьшению стоимости разработки и внедрения системы. Вместе с тем производительность получающегося вычислительного комплекса была вполне достаточной для решения существенного количества задач, требовавших большого объема вычислений. Системы класса "кластер Beowulf" стали появляться по всему миру.
Четыре годя спустя в Лос-Аламосской национальной лаборатории (США) астрофизик Майкл Уоррен и другие ученые из группы теоретической астрофизики построили суперкомпьютер Avalon, который представлял собой Linux-кластер на базе процессоров Alpha 21164A с тактовой частотой 533 MHz. Первоначально включавший 68 процессоров, позднее Avalon был расширен до 140. Каждый узел содержал 256 Mb оперативной памяти, 3 Gb дисковой памяти, Fast Ethernet card. Общая стоимость проекта Avalon составила чуть более 300 тыс. долл.
На момент ввода в строй полной версии (осень 1998 года) с пиковой производительностью в 149 GFlops и показанной на тесте LINPACK производительностью 48,6 GFlops кластер занял 113-е место в списке Top 500.
В том же году на самой престижной конференции в области высокопроизводительных вычислений Supercomputing'98 создатели Avalon получили первую премию в номинации "наилучшее отношение цена/производительность".
В настоящее время под кластером типа Beowulf понимается система, которая состоит из одного серверного узла и одного или более клиентских узлов, соединенных при помощи Ethernet или некоторой другой сети. Это система, построенная из готовых серийно выпускающихся промышленных компонентов, на которых может работать ОС Linux, стандартных адаптеров Ethernet и коммутаторов. Она не содержит специфических аппаратных компонентов и легко воспроизводима. Серверный узел управляет всем кластером и является файл-сервером для клиентских узлов. Он также является консолью кластера и шлюзом во внешнюю сеть. Большие системы Beowulf могут иметь более одного серверного узла, а также, возможно, специализированные узлы, например консоли или станции мониторинга. В большинстве случаев клиентские узлы в Beowulf пассивны. Они конфигурируются и управляются серверными узлами и выполняют только то, что предписано серверным узлом.
Кластер NCSA NT Supercluster
В 2000 году в Национальном центре суперкомпьютерных технологий (NCSA – National Center for Supercomputing Applications) на основе рабочих станций Hewlett-Packard Kayak XU PC workstation (http://www.hp.com/desktops/kayak/) был собран еще один кластер, для которого в качестве операционной системы была выбрана ОС Microsoft Windows. Недолго думая, разработчики окрестили его NT Supercluster (http://archive.ncsa.uiuc.edu/SCD/Hardware/NTCluster/).
На момент ввода в строй кластер с показателем производительности на тесте LINPACK в 62 GFlops и пиковой производительностью в 140 GFlops занимал 207-ю строку списка Top 500.
Кластер построен из 38 двупроцессорных серверов на базе Intel Pentium III Xeon 550 MHz, 1 Gb RAM, 7.5 Gb HDD, 100 Mbit Ethernet card.
Связь между узлами основана на сети Myrinet (http://www.myri.com/myrinet/index.html).
Программное обеспечение кластера:
операционная система – Microsoft Windows NT 4.0;компиляторы – Fortran77, C/C++;уровень передачи сообщений основан на HPVM (ref src="http://www-csag. ucsd.edu/projects/clusters.html" type="url" /).
Кластер Thunder
В настоящий момент число систем, собранных на основе процессоров корпорации Intel и представленных в списке Top 500, составляет 318. Самый мощный суперкомпьютер, представляющий собой кластер на основе Intel Itanium2, установлен в Ливерморской национальной лаборатории (США).
Аппаратная конфигурация кластера Thunder (http://www.llnl.gov/linux/thunder/):
1024 сервера, по 4 процессора Intel Itanium 1.4 GHz в каждом;8 Gb оперативной памяти на узел;общая емкость дисковой системы 150 Tb.
Программное обеспечение:
J операционная система CHAOS 2.0;среда параллельного программирования MPICH2;отладчик параллельных программ TotalView;Intel и GNU Fortran, C/C++ компиляторы.
В данное время кластер Thunder занимает 5-ю позицию списка Top 500 (на момент установки – лето 2004 года – занимал 2-ю строку) с пиковой производительностью 22938 GFlops и максимально показанной на тесте LINPACK 19940 Gflops.
Кластеры
Кластер – группа компьютеров, объединенных в локальную вычислительную сеть (ЛВС) и способных работать в качестве единого вычислительного ресурса. Дополнительно предполагается, что для кластера обеспечивается более высокая надежность и эффективность, нежели для ЛВС, и существенно более низкая стоимость в сравнении с другими типами параллельных вычислительных систем (за счет использования типовых аппаратных и программных решений).
Исчисление истории кластеров можно начать от первого проекта, в котором одной из основных целей являлось установление связи между компьютерами, – проекта ARPANET1). Именно тогда были заложены первые, оказавшиеся фундаментальными, принципы, приведшие впоследствии к созданию локальных и глобальных вычислительных сетей и, конечно же, всемирной глобальной компьютерной сети Интернет. Правда, с момента ввода в действие сети ARPANET до появления первого кластера должно было пройти более двадцати лет.
Эти годы вместили в себя гигантский скачок в развитии аппаратной базы, появление и воцарение на рынке микропроцессоров и персональных компьютеров, накопление критической массы идей и методов параллельного программирования, что привело, в конечном счете, к решению извечной проблемы уникальности каждой параллельной вычислительной установки – разработке стандартов на создание параллельных программ для систем с общей и распределенной памятью. Добавим к этому дороговизну имевшихся на тот момент решений в области высокопроизводительных систем, предполагавших использование быстродействующих, а потому специфических компонентов. Также учтем непрерывное улучшение соотношения "цена/производительность" персональных компьютеров. В свете всех этих обстоятельств появление кластеров было неизбежным.
Преимущества нового подхода к созданию вычислительных систем большой мощности, получившие признание практически сразу после первого представления такой системы, со временем только возрастали, поддерживаемые непрерывным ростом производительности типовых компонентов.
В настоящее время в списке Top 500 самых высокопроизводительных систем кластеры составляют большую часть – 294 установки.
Контрольные вопросы
В чем заключаются основные способы достижения параллелизма?В чем могут состоять различия параллельных вычислительных систем?Что положено в основу классификации Флинна?В чем состоит принцип разделения многопроцессорных систем на мультипроцессоры и мультикомпьютеры?Какие классы систем известны для мультипроцессоров?В чем состоят положительные и отрицательные стороны симметричных мультипроцессоров?Какие классы систем известны для мультикомпьютеров? чем состоят положительные и отрицательные стороны кластерных систем?Какие топологии сетей передачи данных наиболее широко используются при построении многопроцессорных систем?В чем состоят особенности сетей передачи данных для кластеров?Каковы основные характеристики сетей передачи данных?Какие системные платформы могут быть использованы для построения кластеров?
Краткий обзор лекции
В лекции приводится общая характеристика способов организации параллельных вычислений и дается различие между многозадачным, параллельным и распределенным режимами выполнения программ. Для демонстрации возможных подходов рассматривается ряд примеров параллельных вычислительных систем и отмечается существенное разнообразие вариантов построения параллельных систем.
Многообразие компьютерных вычислительных систем приводит к необходимости их классификации. В лекции дается описание одного из наиболее известных способов – систематики Флинна, в основу которой положено понятие потоков команд и данных. Данная классификация является достаточно простой и понятной, однако в рамках такого подхода почти все многопроцессорные вычислительные системы попадают в одну группу – класс MIMD. С целью дальнейшего разделения возможных типов систем в лекции приводится также широко используемая структуризация класса многопроцессорных вычислительных систем, что позволяет выделить две важные группы систем с общей разделяемой и распределенной памятью – мультипроцессоры и мультикомпьютеры. Наиболее известные примеры систем первой группы — векторные параллельные процессоры (parallel vector processor или PVP) и симметричные мультипроцессоры (symmetric multiprocessor или SMP). К мультикомпьютерам относятся массивно-параллельные системы (massively parallel processor или MPP) и кластеры (clusters).
Далее в лекции обращается внимание на характеристику сетей передачи данных в многопроцессорных вычислительных системах. Приводятся примеры топологий сетей, отмечаются особенности организации сетей передачи данных в кластерах и обсуждаются параметры топологий, существенно влияющие на коммуникационную сложность методов параллельных вычислений.
В завершение лекции дается общая характеристика системных платформ для построения кластеров.
Мультикомпьютеры
Мультикомпьютеры (многопроцессорные системы с распределенной памятью) уже не обеспечивают общего доступа ко всей имеющейся в системах памяти (no-remote memory access или NORMA) (см. рис. 1.6). При всей схожести подобной архитектуры с системами с распределенной общей памятью (рис. 1.5б), мультикомпьютеры имеют принципиальное отличие: каждый процессор системы может использовать только свою локальную память, в то время как для доступа к данным, располагаемым на других процессорах, необходимо явно выполнить операции передачи сообщений (message passing operations). Данный подход применяется при построении двух важных типов многопроцессорных вычислительных систем (см. рис. 1.4) - массивно-параллельных систем (massively parallel processor или MPP) и кластеров (clusters). Среди представителей первого типа систем — IBM RS/6000 SP2, Intel PARAGON, ASCI Red, транспьютерные системы Parsytec и др.; примерами кластеров являются, например, системы AC3 Velocity и NCSA NT Supercluster.
Рис. 1.6. Архитектура многопроцессорных систем с распределенной памятью
Следует отметить чрезвычайно быстрое развитие многопроцессорных вычислительных систем кластерного типа – общая характеристика данного подхода приведена, например, в обзоре [19]. Под кластером обычно понимается (см. [60,76]) множество отдельных компьютеров, объединенных в сеть, для которых при помощи специальных аппаратно-программных средств обеспечивается возможность унифицированного управления (single system image), надежного функционирования (availability) и эффективного использования (performance). Кластеры могут быть образованы на базе уже существующих у потребителей отдельных компьютеров либо же сконструированы из типовых компьютерных элементов, что обычно не требует значительных финансовых затрат. Применение кластеров может также в некоторой степени устранить проблемы, связанные с разработкой параллельных алгоритмов и программ, поскольку повышение вычислительной мощности отдельных процессоров позволяет строить кластеры из сравнительно небольшого количества (несколько десятков) отдельных компьютеров (lowly parallel processing).
Тем самым, для параллельного выполнения в алгоритмах решения вычислительных задач достаточно выделять только крупные независимые части расчетов (coarse granularity), что, в свою очередь, снижает сложность построения параллельных методов вычислений и уменьшает потоки передаваемых данных между компьютерами кластера. Вместе с этим следует отметить, что организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, и это накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ.
Отдельные исследователи обращают особое внимание на отличие понятия кластера от сети компьютеров (network of workstations или NOW). Для построения локальной компьютерной сети, как правило, используют более простые сети передачи данных (порядка 100 Мбит/сек). Компьютеры сети обычно более рассредоточены, и пользователи могут применять их для выполнения каких-либо дополнительных работ.
В завершение обсуждаемой темы можно отметить, что существуют и другие способы классификации вычислительных систем (достаточно полный обзор подходов представлен в [2, 45,59], см. также материалы сайта http://www.parallel.ru/computers/taxonomy/). При рассмотрении темы параллельных вычислений рекомендуется обратить внимание на способ структурной нотации для описания архитектуры ЭВМ, позволяющий с высокой степенью точности описать многие характерные особенности компьютерных систем.
Мультипроцессоры
Для дальнейшей систематики мультипроцессоров учитывается способ построения общей памяти. Первый возможный вариант – использование единой (централизованной) общей памяти (shared memory) (см. рис. 1.5 а). Такой подход обеспечивает однородный доступ к памяти (uniform memory access или UMA) и служит основой для построения векторных параллельных процессоров (parallel vector processor или PVP) и симметричных мультипроцессоров (symmetric multiprocessor или SMP). Среди примеров первой группы - суперкомпьютер Cray T90, ко второй группе относятся IBM eServer, Sun StarFire, HP Superdome, SGI Origin и др.
Рис. 1.5. Архитектура многопроцессорных систем с общей (разделяемой) памятью: системы с однородным (а) и неоднородным (б) доступом к памяти
Одной из основных проблем, которые возникают при организации параллельных вычислений на такого типа системах, является доступ с разных процессоров к общим данным и обеспечение, в связи с этим, однозначности (когерентности) содержимого разных кэшей (cache coherence problem). Дело в том, что при наличии общих данных копии значений одних и тех же переменных могут оказаться в кэшах разных процессоров. Если в такой ситуации (при наличии копий общих данных) один из процессоров выполнит изменение значения разделяемой переменной, то значения копий в кэшах других процессоров окажутся не соответствующими действительности и их использование приведет к некорректности вычислений. Обеспечение однозначности кэшей обычно реализуется на аппаратном уровне – для этого после изменения значения общей переменной все копии этой переменной в кэшах отмечаются как недействительные и последующий доступ к переменной потребует обязательного обращения к основной памяти. Следует отметить, что необходимость обеспечения когерентности приводит к некоторому снижению скорости вычислений и затрудняет создание систем с достаточно большим количеством процессоров.
Наличие общих данных при параллельных вычислениях приводит к необходимости синхронизации взаимодействия одновременно выполняемых потоков команд.
Так, например, если изменение общих данных требует для своего выполнения некоторой последовательности действий, то необходимо обеспечить взаимоисключение (mutual exclusion), чтобы эти изменения в любой момент времени мог выполнять только один командный поток. Задачи взаимоисключения и синхронизации относятся к числу классических проблем, и их рассмотрение при разработке параллельных программ является одним из основных вопросов параллельного программирования.
Общий доступ к данным может быть обеспечен и при физически распределенной памяти (при этом, естественно, длительность доступа уже не будет одинаковой для всех элементов памяти) (см. рис. 1.5 б). Такой подход именуется неоднородным доступом к памяти (non-uniform memory access или NUMA). Среди систем с таким типом памяти выделяют:
системы, в которых для представления данных используется только локальная кэш-память имеющихся процессоров (cache-only memory architecture или COMA); примерами являются KSR-1 и DDM;системы, в которых обеспечивается когерентность локальных кэшей разных процессоров (cache-coherent NUMA или CC-NUMA); среди таких систем: SGI Origin 2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000;системы, в которых обеспечивается общий доступ к локальной памяти разных процессоров без поддержки на аппаратном уровне когерентности кэша (non-cache coherent NUMA или NCC-NUMA); например, система Cray T3E.
Использование распределенной общей памяти (distributed shared memory или DSM) упрощает проблемы создания мультипроцессоров (известны примеры систем с несколькими тысячами процессоров), однако возникающие при этом проблемы эффективного использования распределенной памяти (время доступа к локальной и удаленной памяти может различаться на несколько порядков) приводят к существенному повышению сложности параллельного программирования.
МВС-
Один из самых известных в России суперкомпьютеров – Многопроцессорная вычислительная система МВС-1000М – был установлен в Межведомственном суперкомпьютерном центре Российской академии наук.
Работы по созданию МВС-1000М проводились с апреля 2000 года по август 2001 года.
Согласно официальным данным (http://www.jscc.ru) состав системы:
384 двухпроцессорных модуля на базе Alpha 21264 с тактовой частотой 667 MHz (кэш L2 4 Mb), собранные в виде 6 базовых блоков, по 64 модуля в каждом;управляющий сервер и файл-сервер NetApp F840;сети Myrinet 2000 и Fast/Gigabit Ethernet;сетевой монитор;система бесперебойного электропитания.
Каждый вычислительный модуль имеет по 2 Gb оперативной памяти, HDD 20 Gb, сетевые карты Myrinet (2000 Mbit) и Fast Ethernet (100 Mbit).
При обмене данными между модулями с использованием протоколов MPI на сети Myrinet пропускная способность в МВС-1000М составляет 110 — 150 Mb в секунду.
Программное обеспечение системы составляют:
операционные системы управляющего и резервного управляющего сервера – ОС Linux RedHat 6.2 с поддержкой SMP;операционная система вычислительных модулей – ОС Linux RedHat 6.2 с поддержкой SMP;операционная среда параллельного программирования – пакет MPICH for GM;программные средства коммуникационных сетей (Myrinet, Fast Ethernet);оптимизированные компиляторы языков программирования С, C++, Fortran фирмы Compaq;отладчик параллельных программ TotalView;средства профилирования параллельных программ;средства параллельного администрирования.
Рис. 1.1. Структура суперкомпьютера МВС-1000М
Обслуживается МВС-1000М двумя основными компонентами:
подсистемой удаленного управления и непрерывного мониторинга;подсистемой коллективного доступа.
В летнем списке Top 500 2004 года система МВС-1000М заняла 391-ю позицию с пиковой производительностью 1024 GFlops и максимально показанной на тесте LINPACK 734 GFlops.
1000М заменена на самый мощный
В настоящий момент в МСЦ РАН система МВС- 1000М заменена на самый мощный суперкомпьютер России МВС-15000 (согласно последней редакции списка Top 50 стран СНГ – http://supercomputers.ru/index.php).
Аппаратная конфигурация вычислительных узлов МВС-15000 включает в себя:
2 процессора IBM PowerPC 970 с тактовой частотой 2,2 GHz, кэш L1 96 Kb и кэш L2 512 Kb;4 Gb оперативной памяти на узел;40 Gb жесткий диск IDE;2 встроенных адаптера Gigabit Ethernet;адаптер Myrinet типа M3S-PCIXD-2-I.
Рис. 1.2. Структурная схема системы МВС-15000
Состав программного обеспечения МВС-15000:
операционные системы SuSe Linux Enterprise Server версии 8 для платформ x86 и PowerPC;пакет GM 2.0.12 в качестве коммуникационной среды Myrinet;пакет MPICH-GM в качестве среды параллельного программирования;средства управления прохождением задач и их пакетной обработки.
На начало 2005 система МВС-15000 имела общее количество узлов 276 (552 процессора), пиковую производительность 4857,6 GFlops и максимальную (показанную на тесте LINPACK) производительность 3052 GFlops.
Обзор литературы
Дополнительная информация об архитектуре параллельных вычислительных систем может быть получена, например, из [2, 11, 14, 28, 45, 59]; полезная информация содержится также в [24, 76].
В качестве обзора возможных топологий сетей передачи данных в многопроцессорных системах и технологий для их реализации может быть рекомендована, например, работа [29].
Подробное рассмотрение вопросов, связанных с построением и использованием кластерных вычислительных систем, проводится в [24, 76]. Практические рекомендации по построению кластеров для разных системных платформ могут быть найдены в [70, 71].
Примеры параллельных вычислительных систем
Разнообразие параллельных вычислительных систем поистине огромно. В каком-то смысле каждая такая система уникальна. В них устанавливаются различные аппаратные составляющие: процессоры (Intel, Power, AMD, HP, Alpha, Nec, Cray, ѕ), сетевые карты (Ethernet, Myrinet, Infiniband, SCI, ѕ). Они функционируют под управлением различных операционных систем (версии Unix/Linux, версии Windows, ѕ) и используют различное прикладное программное обеспечение. Кажется, что найти между ними что-то общее практически невозможно. Конечно же, это не так, и ниже мы попытаемся с общих позиций сформулировать некоторые известные варианты классификаций параллельных вычислительных систем, но прежде рассмотрим несколько примеров.
Примеры топологий сети передачи данных
Структура линий коммутации между процессорами вычислительной системы (топология сети передачи данных) определяется, как правило, с учетом возможностей эффективной технической реализации. Немаловажную роль при выборе структуры сети играет и анализ интенсивности информационных потоков при параллельном решении наиболее распространенных вычислительных задач. К числу типовых топологий обычно относят следующие схемы коммуникации процессоров (см. рис. 1.7):
полный граф (completely-connected graph или clique) – система, в которой между любой парой процессоров существует прямая линия связи. Такая топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров;линейка (linear array или farm) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами. Такая схема является, с одной стороны, просто реализуемой, c другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки;звезда (star) – система, в которой все процессоры имеют линии связи с некоторым управляющим процессором. Данная топология является эффективной, например, при организации централизованных схем параллельных вычислений;решетка (mesh) – система, в которой граф линий связи образует прямоугольную сетку (обычно двух- или трехмерную). Подобная топология может быть достаточно просто реализована и, кроме того, эффективно использована при параллельном выполнении многих численных алгоритмов (например, при реализации методов анализа математических моделей, описываемых дифференциальными уравнениями в частных производных);гиперкуб (hypercube) – данная топология представляет собой частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора (т.е.
гиперкуб содержит 2N процессоров при размерности N). Такой вариант организации сети передачи данных достаточно широко распространен на практике и характеризуется следующим рядом отличительных признаков:
Рис. 1.7. Примеры топологий многопроцессорных вычислительных систем
- два процессора имеют соединение, если двоичные представления их номеров имеют только одну различающуюся позицию;
- в N-мерном гиперкубе каждый процессор связан ровно с N соседями;
- N-мерный гиперкуб может быть разделен на два (N–1)-мерных гиперкуба (всего возможно N различных таких разбиений);
- кратчайший путь между двумя любыми процессорами имеет длину, совпадающую с количеством различающихся битовых значений в номерах процессоров (данная величина известна как расстояние Хэмминга).
Дополнительная информация по топологиям многопроцессорных вычислительных систем может быть получена, например, в [2, 11, 24, 28, 45, 59, 76]. При рассмотрении вопроса следует учесть, что схема линий передачи данных может реализовываться на аппаратном уровне, а может быть обеспечена на основе имеющейся физической топологии при помощи соответствующего программного обеспечения. Введение виртуальных (программно-реализуемых) топологий способствует мобильности разрабатываемых параллельных программ и снижает затраты на программирование.
Программа ASCI
Программа ASCI (http://www.llnl.gov/asci/) – Accelerated Strategic Computing Initiative, поддерживаемая Министерством энергетики США, в качестве одной из основных целей имеет создание суперкомпьютера с производительностью в 100 TFlops.
Первая система серии ASCI – ASCI Red, построенная в 1996 г. компанией Intel, стала и первым в мире компьютером с производительностью в 1 TFlops (в дальнейшем производительность системы была доведена до 3 TFlops).
Тремя годами позже появились ASCI Blue Pacific от IBM и ASCI Blue Mountain от SGI, ставшие первыми на тот момент суперкомпьютерами с быстродействием 3 TFlops.
Наконец, в июне 2000 г. была введена в действие система ASCI White (http://www.llnl.gov/asci/platforms/white/) с пиковой производительностью свыше 12 TFlops (реально показанная производительность на тесте LINPACK составила на тот момент 4938 GFlops, позднее данный показатель был доведен до 7304 GFlops).
Аппаратно ASCI White представляет собой систему IBM RS/6000 SP с 512 симметричными мультипроцессорными (SMP) узлами. Каждый узел имеет 16 процессоров, система в целом – 8192 процессора. Оперативная память системы – 4 TB, емкость дискового пространства 180 TB.
Все узлы системы являются симметричными мультипроцессорами IBM RS/6000 POWER3 с 64-разрядной архитектурой. Каждый узел автономен, обладает собственной памятью, операционной системой, локальным диском и 16 процессорами.
Процессоры POWER3 являются суперскалярными 64-разрядными чипами конвейерной организации с двумя устройствами по обработке команд с плавающей запятой и тремя устройствами по обработке целочисленных команд. Они способны выполнять до восьми команд за тактовый цикл и до четырех операций с плавающей запятой за такт. Тактовая частота каждого процессора 375 MHz.
Программное обеспечение ASCI White поддерживает смешанную модель программирования – передача сообщений между узлами и многопотоковость внутри SMP-узла.
Операционная система представляет собой версию UNIX – IBM AIX. AIX поддерживает как 32-, так и 64-разрядные системы RS/6000.
Поддержка параллельного кода на ASCI White включает параллельные библиотеки, отладчики (в частности, TotalView), профилировщики, утилиты IBM и сервисные программы по анализу эффективности выполнения. Поддерживаются библиотеки MPI, OpenMP, потоки POSIX и транслятор директив IBM. Имеется параллельный отладчик IBM.
Пути достижения параллелизма
В общем плане под параллельными вычислениями понимаются процессы обработки данных, в которых одновременно могут выполняться несколько операций компьютерной системы. Достижение параллелизма возможно только при выполнении следующих требований к архитектурным принципам построения вычислительной среды:
независимость функционирования отдельных устройств ЭВМ – данное требование относится в равной степени ко всем основным компонентам вычислительной системы: к устройствам ввода-вывода, обрабатывающим процессорам и устройствам памяти;
избыточность элементов вычислительной системы – организация избыточности может осуществляться в следующих основных формах:
- использование специализированных устройств, таких, например, как отдельные процессоры для целочисленной и вещественной арифметики, устройства многоуровневой памяти (регистры, кэш);
- дублирование устройств ЭВМ путем использования, например, нескольких однотипных обрабатывающих процессоров или нескольких устройств оперативной памяти.
Дополнительной формой обеспечения параллелизма может служить конвейерная реализация обрабатывающих устройств, при которой выполнение операций в устройствах представляется в виде исполнения последовательности составляющих операцию подкоманд. Как результат, при вычислениях на таких устройствах на разных стадиях обработки могут находиться одновременно несколько различных элементов данных.
Возможные пути достижения параллелизма детально рассматриваются в [2, 11, 14, 28, 45, 59]; в этих же работах описывается история развития параллельных вычислений и приводятся примеры конкретных параллельных ЭВМ (см. также [24, 76]).
При рассмотрении проблемы организации параллельных вычислений следует различать следующие возможные режимы выполнения независимых частей программы:
многозадачный режим (режим разделения времени), при котором для выполнения нескольких процессов используется единственный процессор. Данный режим является псевдопараллельным, когда активным (исполняемым) может быть один, единственный процесс, а все остальные процессы находятся в состоянии ожидания своей очереди; применение режима разделения времени может повысить эффективность организации вычислений (например, если один из процессов не может выполняться из-за ожидания вводимых данных, процессор может быть задействован для выполнения другого, готового к исполнению процесса – см. [73]).
Кроме того, в данном режиме проявляются многие эффекты параллельных вычислений (необходимость взаимоисключения и синхронизации процессов и др.), и, как результат, этот режим может быть использован при начальной подготовке параллельных программ;
параллельное выполнение, когда в один и тот же момент может выполняться несколько команд обработки данных. Такой режим вычислений может быть обеспечен не только при наличии нескольких процессоров, но и при помощи конвейерных и векторных обрабатывающих устройств;
распределенные вычисления; данный термин обычно применяют для указания параллельной обработки данных, при которой используется несколько обрабатывающих устройств, достаточно удаленных друг от друга, в которых передача данных по линиям связи приводит к существенным временным задержкам. Как результат, эффективная обработка данных при таком способе организации вычислений возможна только для параллельных алгоритмов с низкой интенсивностью потоков межпроцессорных передач данных. Перечисленные условия являются характерными, например, при организации вычислений в многомашинных вычислительных комплексах, образуемых объединением нескольких отдельных ЭВМ с помощью каналов связи локальных или глобальных информационных сетей.
В рамках данного учебного материала основное внимание будет уделяться второму типу организации параллелизма, реализуемому на многопроцессорных вычислительных системах.
Система BlueGene
Самый мощный на данный момент суперкомпьютер в мире создан IBM. Точнее говоря, работы над ним еще не закончены. В настоящий момент система имеет полное название "BlueGene/L DD2 beta-System" и представляет собой "первую очередь" полной вычислительной системы. Согласно прогнозам, к моменту ввода в строй ее пиковая производительность достигнет 360 TFlops.
В качестве основных областей применения разработчики называют гидродинамику, квантовую химию, моделирование климата и др.
Текущий вариант системы имеет следующие характеристики:
32 стойки по 1024 двухъядерных 32-битных процессора PowerPC 440 с тактовой частотой 0,7 GHz;пиковая производительность – порядка 180 TFlops;максимальная показанная производительность (на тесте LINPACK) – 135 TFlops.
Суперкомпьютеры
Началом эры суперкомпьютеров с полным правом может считаться 1976 год – год появления первой векторной системы Cray 1. Результаты, показанные этой системой, пусть и на ограниченном в то время наборе приложений, были столь впечатляющи в сравнении с остальными, что система заслуженно получила название "суперкомпьютер" и в течение длительного времени определяла развитие всей индустрии высокопроизводительных вычислений. Однако в результате совместной эволюции архитектур и программного обеспечения на рынке стали появляться системы с весьма кардинально различающимися характеристиками, потому само понятие "суперкомпьютер" стало многозначным, и пересматривать его пришлось неоднократно.
Попытки дать определение термину суперкомпьютер, опираясь только на производительность, неизбежно приводят к необходимости постоянно поднимать планку, отделяющую его от рабочей станции или даже обычного настольного компьютера. Так, по определению Оксфордского словаря вычислительной техники 1986 года, для того чтобы получить это гордое название, нужно было иметь производительность в 10 MFlops 11). Сегодня, как известно, производительность настольных систем на два порядка выше.
Из альтернативных определений наиболее интересны два: экономическое и философское. Первое из них гласит, что суперкомпьютер – это система, цена которой выше 1–2 млн. долларов. Второе – что суперкомпьютер – это компьютер, мощность которого всего на порядок меньше необходимой для решения современных задач.
Топология сети вычислительных кластеров
Для построения кластерной системы во многих случаях используют коммутатор (switch), через который процессоры кластера соединяются между собой. В этом случае топология сети кластера представляет собой полный граф (рис. 1.7), в соответствии с которым передача данных может быть организована между любыми двумя процессорами сети. При этом, однако, одновременность выполнения нескольких коммуникационных операций является ограниченной – в любой момент времени каждый процессор может принимать участие только в одной операции приема-передачи данных. Как результат, параллельно могут выполняться только те коммуникационные операции, в которых взаимодействующие пары процессоров не пересекаются между собой.
Высокопроизводительный вычислительный кластер ННГУ
В качестве следующего примера рассмотрим вычислительный кластер Нижегородского университета, оборудование для которого было передано в рамках Академической программы Интел в 2001 г. В состав кластера входят (см. рис. 1.3):
2 вычислительных сервера, каждый из которых имеет 4 процессора Intel Pentium III 700 MHZ, 512 MB RAM, 10 GB HDD, 1 Gbit Ethernet card;12 вычислительных серверов, каждый из которых имеет 2 процессора Intel Pentium III 1000 MHZ, 256 MB RAM, 10 GB HDD, 1 Gbit Ethernet card;12 рабочих станций на базе процессора Intel Pentium 4 1300 MHZ, 256 MB RAM, 10 GB HDD, 10/100 Fast Ethernet card.
Следует отметить, что в результате передачи подобного оборудования Нижегородский госуниверситет оказался первым вузом в Восточной Европе, оснащенным ПК на базе новейшего процессора Intel®Pentium®4. Подобное достижение является дополнительным подтверждением складывающегося плодотворного сотрудничества ННГУ и корпорации Интел.
Важной отличительной особенностью кластера является его неоднородность (гетерогенность). В состав кластера входят рабочие места, оснащенные процессорами Intel Pentium 4 и соединенные относительно медленной сетью (100 Мбит), а также вычислительные 2- и 4-процессорные серверы, обмен данными между которыми выполняется при помощи быстрых каналов передачи данных (1000 Мбит). В результате кластер может использоваться не только для решения сложных вычислительно-трудоемких задач, но также и для проведения различных экспериментов по исследованию многопроцессорных кластерных систем и параллельных методов решения научно-технических задач.
В качестве системной платформы для построения кластера выбраны современные операционные системы семейства Microsoft Windows (для проведения отдельных экспериментов имеется возможность использования ОС Unix). Такой выбор определяется рядом причин:
операционные системы семейства Microsoft Windows (так же как и ОС Unix) широко используются для построения кластеров; причем если раньше применение ОС Unix для этих целей было преобладающим системным решением, то в настоящее время тенденцией является увеличение числа создаваемых кластеров под управлением ОС Microsoft Windows (см., например, www.tc.cornell.edu/ac3/, www.windowclusters.org и др.);разработка прикладного программного обеспечения выполняется преимущественно с использованием ОС Microsoft Windows;корпорация Microsoft проявила заинтересованность в создании подобного кластера и передала в ННГУ для поддержки работ все необходимое программное обеспечение (ОС MS Windows 2000 Professional, ОС MS Windows 2000 Advanced Server и др.).
В результате принятых решений программное обеспечение на момент установки кластера являлось следующим:
вычислительные серверы работают под управлением ОС Microsoft® Windows® 2000 Advanced Server; на рабочих местах разработчиков установлена ОС Microsoft® Windows® 2000 Professional;в качестве сред разработки применяются Microsoft® Visual Studio 6.0; для выполнения исследовательских экспериментов возможно использование компилятора Intel® C++ Compiler 5.0, встраиваемого в среду Microsoft® Visual Studio;на рабочих местах разработчиков установлены библиотеки:
- Plapack 3.0 (см. www.cs.utexas.edu/users/plapack);
- MKL (см. www.developer.intel.com/software/products/mkl/index.htm);
в качестве средств передачи данных между процессорами установлены две реализации стандарта MPI:
- Argonne MPICH (www.unix.mcs.anl.gov/mpi/MPICH/);
- MP-MPICH (www.lfbs.rwth-aachen.de/~joachim/MP-MPICH.html);
в опытной эксплуатации находится система разработки параллельных программ DVM (см. www.keldysh.ru/dvm/).
В 2006 году в рамках инновационной образовательной программы Нижегородского университета Приоритетного национального проекта "Образование" была выполнена модернизация вычислительного кластера ННГУ, в результате пиковая производительность кластера была доведена до 3000 Gflops.
увеличить изображение
Рис. 1.3. Структура вычислительного кластера Нижегородского университета
Задачи и упражнения
Приведите дополнительные примеры параллельных вычислительных систем.Рассмотрите дополнительные способы классификации компьютерных систем.Рассмотрите способы обеспечения когерентности кэшей в системах с общей разделяемой памятью.Подготовьте обзор программных библиотек, обеспечивающих выполнение операций передачи данных для систем с распределенной памятью.Рассмотрите топологию сети передачи данных в виде двоичного дерева.Выделите эффективно реализуемые классы задач для каждого типа топологий сети передачи данных.
Анализ масштабируемости параллельных вычислений
Целью применения параллельных вычислений во многих случаях является не только уменьшение времени выполнения расчетов, но и обеспечение возможности решения более сложных вариантов задач (таких постановок, решение которых не представляется возможным при использовании однопроцессорных вычислительных систем). Способность параллельного алгоритма эффективно использовать процессоры при повышении сложности вычислений является важной характеристикой выполняемых расчетов. Поэтому параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров. Возможный способ характеристики свойств масштабируемости состоит в следующем.
Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма
T0=pTp–T1.
Накладные расходы появляются за счет необходимости организации взаимодействия процессоров, выполнения некоторых дополнительных действий, синхронизации параллельных вычислений и т.п. Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:
Применяя полученные соотношения, эффективность использования процессоров можно выразить как
Последнее выражение показывает, что если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0. При фиксации числа процессоров эффективность их использования можно улучшить путем повышения сложности решаемой задачи T1 (предполагается, что при росте параметра сложности n накладные расходы T0 увеличиваются медленнее, чем объем вычислений T1). Как результат, при увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач. Поэтому важной характеристикой параллельных вычислений становится соотношение необходимых темпов роста сложности расчетов и числа используемых процессоров.
Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить
Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности (isoefficiency function) (см. [51]).
Покажем в качестве иллюстрации вывод функции изоэффективности для учебного примера суммирования числовых значений. В этом случае
и функция изоэффективности принимает вид
Как результат, например, при числе процессоров p=16 для обеспечения уровня эффективности E=0,5 (т.е. K=1) количество суммируемых значений должно быть не менее n=64. Или же, при увеличении числа процессоров с p до q (q>p) для обеспечения пропорционального роста ускорения (Sq/Sp)=(q/p) необходимо увеличить число суммируемых значений n в (qlog2q)/(plog2p) раз.
Каскадная схема суммирования
Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 2.3):
на первой итерации каскадной схемы все исходные данные разбиваются на пары, и для каждой пары вычисляется сумма их значений;далее все полученные суммы также разбиваются на пары, и снова выполняется суммирование значений пар и т.д.
Данная вычислительная схема может быть определена как граф (пусть n=2k)
G2(V2,R2),
Рис. 2.3. Каскадная схема алгоритма суммирования
где V2={(vi1,...,vli), 0ik, 1li2-1n} есть вершины графа ((v01,...v0n) - операции ввода, (v1l,...,v1n/2) - операции суммирования первой итерации и т.д.), а множество дуг графа определяется соотношениями:
R2={(vi-1,2j-1vij),(vi-1,2jvij), 1ik, 1j2-in}.
Как нетрудно оценить, количество итераций каскадной схемы оказывается равным величине
k=log2n,
а общее количество операций суммирования
Kпосл=n/2+n/4+...+1=n–1
совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным
Kпар=log2n.
Поскольку считается, что время выполнения любых вычислительных операций является одинаковым и единичным, то T1=Kпосл, Tp=Kпар, поэтому показатели ускорения и эффективности каскадной схемы алгоритма суммирования можно оценить как
Sp=T1/Tp=(n–1)/log2n, Ep=T1/pTp=(n–1)/(plog2n)=(n–1)/((n/2)log2n),
где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров.
Анализируя полученные характеристики, можно отметить, что время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера в теореме 2. Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений
Контрольные вопросы
Как определяется модель "операции — операнды"?Как определяется расписание для распределения вычислений между процессорами?Как определяется время выполнения параллельного алгоритма?Какое расписание является оптимальным?Как определить минимально возможное время решения задачи?Что понимается под паракомпьютером и для чего может оказаться полезным данное понятие?Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?Как определить минимально возможное время параллельного решения задачи по графу "операнды – операции"?Какие зависимости могут быть получены для времени параллельного решения задачи при увеличении или уменьшении числа используемых процессоров?При каком числе процессоров могут быть получены времена выполнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?Как определяются понятия ускорения и эффективности?Возможно ли достижение сверхлинейного ускорения?В чем состоит противоречивость показателей ускорения и эффективности?Как определяется понятие стоимости вычислений?В чем состоит понятие стоимостно-оптимального алгоритма?В чем заключается проблема распараллеливания последовательного алгоритма суммирования числовых значений?В чем состоит каскадная схема суммирования? С какой целью рассматривается модифицированный вариант данной схемы?В чем состоит различие показателей ускорения и эффективности для рассматриваемых вариантов каскадной схемы суммирования?В чем состоит параллельный алгоритм вычисления всех частных сумм последовательности числовых значений?Как формулируется закон Амдаля? Какой аспект параллельных вычислений позволяет учесть данный закон?Какие предположения используются для обоснования закона Густавсона – Барсиса?Как определяется функция изоэффективности?Какой алгоритм является масштабируемым? Приведите примеры методов с разным уровнем масштабируемости.
Краткий обзор лекции
В лекции рассматривается модель вычислений в виде графа "операции – операнды", которая может использоваться для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач.
В основу данной модели положен ациклический ориентированный граф, в котором вершины представляют операции, а дуги соответствуют зависимостям операций по данным. При наличии такого графа для определения параллельного алгоритма достаточно задать расписание, в соответствии с которым фиксируется распределение выполняемых операций по процессорам.
Представление вычислений при помощи моделей подобного вида позволяет получить аналитически ряд характеристик разрабатываемых параллельных алгоритмов, среди которых время выполнения, схема оптимального расписания, оценки максимально возможного быстродействия методов решения поставленных задач. Для более простого построения теоретических оценок в лекции рассматривается понятие паракомпьютера как параллельной системы с неограниченным количеством процессоров.
Для оценки оптимальности разрабатываемых методов параллельных вычислений в лекции приводятся широко используемые в теории и практике параллельного программирования основные показатели качества - ускорение (speedup), показывающее, во сколько раз быстрее осуществляется решение задач при использовании нескольких процессоров, и эффективность (efficiency), которая характеризует долю времени реального использования процессоров вычислительной системы. Важной характеристикой разрабатываемых алгоритмов является стоимость (cost) вычислений, определяемая как произведение времени параллельного решения задачи и числа используемых процессоров.
Для демонстрации применимости рассмотренных моделей и методов анализа параллельных алгоритмов в лекции рассматривается задача нахождения частных сумм последовательности числовых значений. На данном примере отмечается проблема сложности распараллеливания последовательных алгоритмов, которые изначально не были ориентированы на возможность организации параллельных вычислений.
Для выделения "скрытого" параллелизма показывается возможность преобразования исходной последовательной схемы вычислений и приводится получаемая в результате таких преобразований каскадная схема. На примере этой же задачи отмечается возможность введения избыточных вычислений для достижения большего параллелизма выполняемых расчетов.
В завершение лекции рассматривается вопрос построения оценок максимально достижимых значений показателей эффективности. Для получения таких оценок может быть использован закон Амдаля (Amdahl), позволяющий учесть существование последовательных (нераспараллеливаемых) вычислений в методах решения задач. Закон Густавсона – Барсиса (Gustafson – Barsis's law) обеспечивает построение оценок ускорения масштабирования (scaled speedup), применяемое для характеристики того, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач. Для определения зависимости между сложностью решаемой задачи и числом процессоров, при соблюдении которой обеспечивается необходимый уровень эффективности параллельных вычислений, вводится понятие функции изоэффективности (isoefficiency function).
Модель вычислений в виде графа "операции – операнды"
Для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач может быть использована модель в виде графа "операции – операнды" (см., например, [2, 22]). Для уменьшения сложности излагаемого материала при построении модели будет предполагаться, что время выполнения любых вычислительных операций является одинаковым и равняется 1 (в тех или иных единицах измерения). Кроме того, принимается, что передача данных между вычислительными устройствами выполняется мгновенно без каких-либо затрат времени (что может быть справедливо, например, при наличии общей разделяемой памяти в параллельной вычислительной системе). Анализ коммуникационной трудоемкости параллельных алгоритмов приводится в следующей лекции.
Представим множество операций, выполняемых в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости в виде ациклического ориентированного графа
G = (V, R),
Рис. 2.1. Пример вычислительной модели алгоритма в виде графа "операции – операнды"
где V = {1,...,|V|} есть множество вершин графа, представляющих выполняемые операции алгоритма, а R есть множество дуг графа (при этом дуга r = (i, j) принадлежит графу только в том случае, если операция j использует результат выполнения операции i). Для примера на рис. 2.1 показан граф алгоритма вычисления площади прямоугольника, заданного координатами двух противолежащих углов. Как можно заметить по приведенному примеру, для выполнения выбранного алгоритма решения задачи могут быть использованы разные схемы вычислений и построены соответственно разные вычислительные модели. Как будет показано далее, разные схемы вычислений обладают различными возможностями для распараллеливания и, тем самым, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма.
В рассматриваемой вычислительной модели алгоритма вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода. Обозначим через V множество вершин графа без вершин ввода, а через d(G) — диаметр (длину максимального пути) графа.
Моделирование и анализ параллельных вычислений
При разработке параллельных алгоритмов решения сложных научно-технических задач принципиальным моментом является анализ эффективности использования параллелизма, состоящий обычно в оценке получаемого ускорения процесса вычислений (сокращения времени решения задачи). Формирование подобных оценок ускорения может осуществляться применительно к выбранному вычислительному алгоритму (оценка эффективности распараллеливания конкретного алгоритма). Другой важный подход состоит в построении оценок максимально возможного ускорения процесса решения задачи конкретного типа (оценка эффективности параллельного способа решения задачи).
В данной лекции рассматривается модель вычислений в виде графа "операции – операнды", которая может использоваться для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач, и приводятся оценки эффективности максимально возможного параллелизма, которые могут быть получены в результате анализа имеющихся моделей вычислений. Примеры применения излагаемого теоретического материала приводятся в лекциях 6 – 11 настоящего учебного пособия при изучении параллельных методов решения ряда сложных вычислительно трудоемких задач.
Модифицированная каскадная схема
Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы (см. [22]). Для упрощения построения оценок можно предположить n=2k, k=2s. Тогда в новом варианте каскадной схемы все вычисления производятся в два последовательно выполняемых этапа суммирования (см. рис. 2.4):
на первом этапе вычислений все суммируемые значения подразделяются на (n/log2n) групп, в каждой из которых содержится log2n элементов; далее для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования; вычисления в каждой группе могут выполняться независимо друг от друга (т.е. параллельно – для этого необходимо наличие не менее (n/log2n) процессоров);на втором этапе для полученных (n/log2n) сумм отдельных групп применяется обычная каскадная схема.
Рис. 2.4. Модифицированная каскадная схема суммирования
Тогда для выполнения первого этапа требуется log2n параллельных операций при использовании p1=(n/log2n) процессоров. Для выполнения второго этапа необходимо
log2(n/log2n)log2n
параллельных операций для p2=(n/log2n)/2 процессоров. Как результат, данный способ суммирования характеризуется следующими показателями:
Tp=2log2n, p=(n/log2n).
С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:
Sp=T1/Tp=(n–1)/2log2n, Ep=T1/pTp=(n–1)/(2(n/log2n)log2n)=(n–1)/2n.
Сравнивая данные оценки с показателями обычной каскадной схемы, можно отметить, что ускорение для предложенного параллельного алгоритма уменьшилось в 2 раза, однако для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу
Можно отметить также, что данные значения показателей достигаются при количестве процессоров, определенном в теореме 5. Кроме того, необходимо подчеркнуть, что, в отличие от обычной каскадной схемы, модифицированный каскадный алгоритм является стоимостно-оптимальным, поскольку стоимость вычислений в этом случае
Cp=pTp=(n/log2n)(2log2n)
является пропорциональной времени выполнения последовательного алгоритма.
Обзор литературы
Дополнительная информация по моделированию и анализу параллельных вычислений может быть получена, например, в [2, 22]), полезная информация содержится также в [51, 63].
Рассмотрение учебной задачи суммирования последовательности числовых значений было выполнено в [22].
Впервые закон Амдаля был изложен в работе [18]. Закон Густавсона – Барсиса был опубликован в работе [43]. Понятие функции изоэффективности было предложено в работе [39].
Систематическое изложение (на момент издания работы) вопросов моделирования и анализа параллельных вычислений приводится в [77].
Оценка максимально достижимого параллелизма
Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности, однако получение идеальных величин Sp=p для ускорения и Ep=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач. Так, для рассматриваемого учебного примера в предыдущем пункте минимально достижимое время параллельного вычисления суммы числовых значений составляет log2n. Определенное содействие в решении этой проблемы могут оказать теоретические утверждения, приведенные в начале данной лекции. В дополнение к ним рассмотрим еще ряд закономерностей, которые могут быть чрезвычайно полезны при построении оценок максимально достижимого параллелизма1).
1. Закон Амдаля. Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены. Пусть f есть доля последовательных вычислений в применяемом алгоритме обработки данных, тогда в соответствии с законом Амдаля (Amdahl) ускорение процесса вычислений при использовании p процессоров ограничивается величиной
Так, например, при наличии всего 10% последовательных команд в выполняемых вычислениях эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных. В рассмотренном учебном примере вычисления суммы значений для каскадной схемы доля последовательных расчетов составляет f=log2n/n и, как результат, величина возможного ускорения ограничена оценкой S*=n/log2n.
Закон Амдаля характеризует одну из самых серьезных проблем в области параллельного программирования (алгоритмов без определенной доли последовательных команд практически не существует). Однако часто доля последовательных действий характеризует не возможность параллельного решения задач, а последовательные свойства применяемых алгоритмов. Поэтому доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания методов.
Следует отметить также, что рассмотрение закона Амдаля происходит в предположении, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи.
При рассмотрении закона Густавсона – Барсиса следует учитывать еще один важный момент. С увеличением числа используемых процессоров темп уменьшения времени параллельного решения задач может падать (после превышения определенного порога). Однако за счет уменьшения времени вычислений сложность решаемых задач может быть увеличена (так, например, для учебной задачи суммирования может быть увеличен размер складываемого набора значений). Оценку получаемого при этом ускорения можно определить при помощи сформулированных закономерностей. Такая аналитическая оценка тем более полезна, поскольку решение таких более сложных вариантов задач на одном процессоре может оказаться достаточно трудоемким и даже невозможным, например, в силу нехватки оперативной памяти. С учетом указанных обстоятельств оценку ускорения, получаемую в соответствии с законом Густавсона – Барсиса, еще называют ускорением масштабирования (scaled speedup), поскольку данная характеристика может показать, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.
Описание схемы параллельного выполнения алгоритма
Операции алгоритма, между которыми нет пути в рамках выбранной схемы вычислений, могут быть выполнены параллельно (для вычислительной схемы на рис. 2.1, например, параллельно могут быть реализованы сначала все операции умножения, а затем первые две операции вычитания). Возможный способ описания параллельного выполнения алгоритма может состоять в следующем (см., например, [2, 22]).
Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание)
Hp = {(i,Pi,ti):iV},
в котором для каждой операции iV указывается номер используемого для выполнения операции процессора Pi и время начала выполнения операции ti. Для того чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества Hp:
, т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент;, т.е. к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.
Определение времени выполнения параллельного алгоритма
Вычислительная схема алгоритма G совместно с расписанием Hp может рассматриваться как модель параллельного алгоритма Ap(G,Hp), исполняемого с использованием p процессоров. Время выполнения параллельного алгоритма определяется максимальным значением времени, применяемым в расписании
Для выбранной схемы вычислений желательно использование расписания, обеспечивающего минимальное время исполнения алгоритма
Уменьшение времени выполнения может быть обеспечено и путем подбора наилучшей вычислительной схемы
Оценки Tp(G,Hp), Tp(G) и Tp могут быть применены в качестве показателей времени выполнения параллельного алгоритма. Кроме того, для анализа максимально возможного параллелизма можно определить оценку наиболее быстрого исполнения алгоритма
Оценку T? можно рассматривать как минимально возможное время выполнения параллельного алгоритма при использовании неограниченного количества процессоров (концепция вычислительной системы с бесконечным количеством процессоров, обычно называемой паракомпьютером, широко применяется при теоретическом анализе параллельных вычислений).
Оценка T1 определяет время выполнения алгоритма при использовании одного процессора и представляет, тем самым, время выполнения последовательного варианта алгоритма решения задачи. Построение подобной оценки является важной задачей при анализе параллельных алгоритмов, поскольку она необходима для определения эффекта использования параллелизма (ускорения времени решения задачи). Очевидно, что
где , напомним, есть количество вершин вычислительной схемы без вершин ввода. Важно отметить, что если при определении оценки ограничиться рассмотрением только одного выбранного алгоритма решения задачи и использовать величину
то получаемые при такой оценке показатели ускорения будут характеризовать эффективность распараллеливания выбранного алгоритма. Для оценки эффективности параллельного решения исследуемой вычислительной задачи время последовательного решения следует определять с учетом различных последовательных алгоритмов, т.е.
использовать величину
где операция минимума берется по множеству всех возможных последовательных алгоритмов решения данной задачи.
Приведем без доказательства теоретические положения, характеризующие свойства оценок времени выполнения параллельного алгоритма (см. [22]).
Теорема 1. Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма, т.е.
T?(G)=d(G).
Теорема 2. Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением
T?(G)=log2n,
где n есть количество вершин ввода в схеме алгоритма.
Теорема 3. При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е.
q=cp, 0<c<1TpcTq.
Теорема 4. Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма
pTp<T?+T1/p.
Теорема 5. Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T?, можно достичь при количестве процессоров порядка p~T1/T?, а именно,
pT1/T?Tp2T?.
При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров, т.е.
Приведенные утверждения позволяют дать следующие рекомендации по правилам формирования параллельных алгоритмов:
при выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (см. теорему 1);для параллельного выполнения целесообразное количество процессоров определяется величиной p~T1/T? (см. теорему 5);время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.
Для вывода рекомендаций по формированию расписания по параллельному выполнению алгоритма приведем доказательство теоремы 4.
Доказательство теоремы 4. Пусть H? есть расписание для достижения минимально возможного времени выполнения T?. Для каждой итерации ?, 0<?<T?, выполнения расписания H? обозначим через n? количество операций, выполняемых в ходе итерации ?. Расписание выполнения алгоритма с использованием p процессоров может быть построено следующим образом. Выполнение алгоритма разделим на T? шагов; на каждом шаге ? следует выполнить все n? операций, которые выполнялись на итерации ? расписания H?. Эти операции могут быть выполнены не более чем за ?n?/p? итераций при использовании p процессоров. Как результат, время выполнения алгоритма Tp может быть оценено следующим образом
Доказательство теоремы дает практический способ построения расписания параллельного алгоритма. Первоначально может быть построено расписание без учета ограниченности числа используемых процессоров (расписание для паракомпьютера). Затем, согласно схеме вывода теоремы, может быть построено расписание для конкретного количества процессоров.
Показатели эффективности параллельного алгоритма
Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется величиной
Sp(n)=T1(n)/Tp(n),
т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величина n применяется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).
Эффективность (efficiency) использования параллельным алгоритмом процессоров при решении задачи определяется соотношением
Ep(n)=T1(n)/(pTp(n))=Sp(n)/p
(величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально задействованы для решения задачи).
Из приведенных соотношений можно показать, что в наилучшем случае Sp(n)=p и Ep(n)=1. При практическом применении данных показателей для оценки эффективности параллельных вычислений следует учитывать два важных момента:
При определенных обстоятельствах ускорение может оказаться больше числа используемых процессоров Sp(n)>p - в этом случае говорят о существовании сверхлинейного (superlinear) ускорения. Несмотря на парадоксальность таких ситуаций (ускорение превышает число процессоров), на практике сверхлинейное ускорение может иметь место. Одной из причин такого явления может быть неодинаковость условий выполнения последовательной и параллельной программ. Например, при решении задачи на одном процессоре оказывается недостаточно оперативной памяти для хранения всех обрабатываемых данных и тогда становится необходимым использование более медленной внешней памяти (в случае же использования нескольких процессоров оперативной памяти может оказаться достаточно за счет разделения данных между процессорами). Еще одной причиной сверхлинейного ускорения может быть нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных. Так, например, известный алгоритм пузырьковой сортировки характеризуется квадратичной зависимостью количества необходимых операций от числа упорядочиваемых данных.
Как результат, при распределении сортируемого массива между процессорами может быть получено ускорение, превышающее число процессоров (более подробно данный пример рассматривается в лекции 9). Источником сверхлинейного ускорения может быть и различие вычислительных схем последовательного и параллельного методов,При внимательном рассмотрении можно обратить внимание, что попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) могут привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются часто противоречивыми. Так, например, повышение ускорения обычно может быть обеспечено за счет увеличения числа процессоров, что приводит, как правило, к падению эффективности. И наоборот, повышение эффективности достигается во многих случаях при уменьшении числа процессоров (в предельном случае идеальная эффективность Ep(n)=1 легко обеспечивается при использовании одного процессора). Как результат, разработка методов параллельных вычислений часто предполагает выбор некоторого компромиссного варианта с учетом желаемых показателей ускорения и эффективности.
При выборе надлежащего параллельного способа решения задачи может оказаться полезной оценка стоимости (cost) вычислений, определяемой как произведение времени параллельного решения задачи и числа используемых процессоров
Cp=pTp.
В связи с этим можно определить понятие стоимостно-оптимального (cost-optimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.
Далее для иллюстрации введенных понятий в следующем пункте будет рассмотрен учебный пример решения задачи вычисления частных сумм для последовательности числовых значений. Кроме того, данные показатели будут использоваться для характеристики эффективности всех рассматриваемых в лекциях 6 – 11 параллельных алгоритмов при решении ряда типовых задач вычислительной математики.
Последовательный алгоритм суммирования
Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора
S=0, S=S+x1,...
Вычислительная схема данного алгоритма может быть представлена следующим образом (см. рис. 2.2):
G1=(V1,R1),
где V1={v01,...,v0n, v11,...,v1n} есть множество операций (вершины v01,...,v0n обозначают операции ввода, каждая вершина v1i, 1in, соответствует прибавлению значения xi к накапливаемой сумме S), а
R1={(v0i,v1i),(v1i,v1i+1), 1in–1}
есть множество дуг, определяющих информационные зависимости операций.
Рис. 2.2. Последовательная вычислительная схема алгоритма суммирования
Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен.
Учебный пример Вычисление частных сумм последовательности числовых значений
Рассмотрим для демонстрации ряда проблем, возникающих при разработке параллельных методов вычислений, сравнительно простую задачу нахождения частных сумм последовательности числовых значений
где n есть количество суммируемых значений (данная задача известна также под названием prefix sum problem).
Изучение возможных параллельных методов решения данной задачи начнем с еще более простого варианта ее постановки – с задачи вычисления общей суммы имеющегося набора значений (в таком виде задача суммирования является частным случаем общей задачи редукции)
Вычисление всех частных сумм
Вернемся к исходной задаче вычисления всех частных сумм последовательности значений и проведем анализ возможных способов последовательной и параллельной организации вычислений. Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи обычного последовательного алгоритма суммирования при том же количестве операций (!)
T1=n.
При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам; достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач. Так, для рассматриваемой задачи нахождения всех частных сумм алгоритм, обеспечивающий получение результатов за log2n параллельных операций (как и в случае вычисления общей суммы), может состоять в следующем (см. рис. 2.5, а также [22]):
перед началом вычислений создается копия S вектора суммируемых значений (S=x);далее на каждой итерации суммирования i, 1ilog2n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2i-1 позиций (освобождающиеся при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q.
Рис. 2.5. Схема параллельного алгоритма вычисления всех частных сумм
(величины Si-j означают суммы значений от i до j элементов числовой последовательности)
Всего параллельный алгоритм выполняется за log2n параллельных операций сложения. На каждой итерации алгоритма параллельно выполняются n скалярных операций сложения и, таким образом, общее количество скалярных операций определяется величиной
Kпар=nlog2n
(параллельный алгоритм содержит большее (!) количество операций по сравнению с последовательным способом суммирования). Необходимое количество процессоров определяется количеством суммируемых значений (p=n).
С учетом полученных соотношений показатели ускорения и эффективности параллельного алгоритма вычисления всех частных сумм оцениваются следующим образом:
Sp=T1/Tp=n/log2n, Ep=T1/pTp=n/(plog2n)=n/(nlog2n)=1/log2n.
Как следует из построенных оценок, эффективность алгоритма также уменьшается при увеличении числа суммируемых значений, и при необходимости повышения величины этого показателя может оказаться полезной модификация алгоритма, как и в случае с обычной каскадной схемой.
и выполните оценку показателей ускорения
1. Разработайте модель и выполните оценку показателей ускорения и эффективности параллельных вычислений:
для задачи скалярного произведения двух векторов
для задачи поиска максимального и минимального значений для заданного набора числовых данных
для задачи нахождения среднего значения для заданного набора числовых данных
2. Выполните в соответствии с законом Амдаля оценку максимально достижимого ускорения для задач п. 1.
3. Выполните оценку ускорения масштабирования для задач п.1.
4. Выполните построение функций изоэффективности для задач п.1.
5. Разработайте модель и выполните полный анализ эффективности параллельных вычислений (ускорение, эффективность, максимально достижимое ускорение, ускорение масштабирования, функция изоэффективности) для задачи умножения матрицы на вектор.
Алгоритмы маршрутизации
Алгоритмы маршрутизации определяют путь передачи данных от процессора – источника сообщения до процессора, к которому сообщение должно быть доставлено. Среди возможных способов решения данной задачи различают:
оптимальные, определяющие всегда наикратчайшие пути передачи данных, и неоптимальные алгоритмы маршрутизации;детерминированные и адаптивные методы выбора маршрутов (адаптивные алгоритмы определяют пути передачи данных в зависимости от существующей загрузки коммуникационных каналов).
К числу наиболее распространенных оптимальных алгоритмов относится класс методов покоординатной маршрутизации (dimension-ordered routing), в которых поиск путей передачи данных осуществляется поочередно для каждой размерности топологии сети коммуникации. Так, для двумерной решетки такой подход приводит к маршрутизации, при которой передача данных сначала выполняется по одному направлению (например, по горизонтали до достижения вертикали, на которой располагается процессор назначения), а затем данные передаются вдоль другого направления (данная схема известна под названием алгоритма XY-маршрутизации).
Для гиперкуба покоординатная схема маршрутизации может состоять, например, в циклической передаче данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров — того, на котором сообщение располагается в данный момент времени, и того, на который оно должно быть передано.
Анализ трудоемкости основных операций передачи данных
При всем разнообразии выполняемых операций передачи данных при параллельных способах решения сложных научно-технических задач, определенные процедуры взаимодействия процессоров сети могут быть отнесены к числу основных коммуникационных действий, либо наиболее широко распространенных в практике параллельных вычислений, либо тех, к которым могут быть сведены многие другие процессы приема-передачи сообщений. Важно отметить также, что в рамках подобного базового набора для большинства операций коммуникации существуют процедуры, обратные по действию исходным операциям (так, например, операции передачи данных от одного процессора всем имеющимся процессорам сети соответствует операция приема в одном процессоре сообщений от всех остальных процессоров). Как результат, рассмотрение коммуникационных процедур целесообразно выполнять попарно, поскольку во многих случаях алгоритмы выполнения прямой и обратной операций могут быть получены исходя из одинаковых предпосылок.
Рассмотрение основных операций передачи данных в этой лекции будет осуществляться на примере таких топологий сети, как кольцо, двумерная решетка и гиперкуб. Для двумерной решетки будет предполагаться также, что между граничными процессорами в строках и столбцах решетки имеются каналы передачи данных (т.е. топология сети представляет собой тор). Как и ранее, величина m будет означать размер сообщения в словах, значение p определяет количество процессоров в сети, а переменная N задает размерность топологии гиперкуба.
Циклический сдвиг
Частный случай обобщенной множественной рассылки есть процедура перестановки (permutation), представляющая собой операцию перераспределения информации между процессорами сети, в которой каждый процессор передает сообщение определенному неким способом другому процессору сети. Конкретный вариант перестановки – циклический q-сдвиг (cirlular q-shift), при котором каждый процессор i, 1iN, передает данные процессору с номером . Подобная операция сдвига используется, например, при организации матричных вычислений.
Поскольку выполнение циклического сдвига для кольцевой топологии может быть обеспечено при помощи простых алгоритмов передачи данных, рассмотрим возможные способы выполнения данной коммуникационной операции только для топологий решетка-тор и гиперкуб при разных методах передачи данных (см. п. 3.1.2).
Передача сообщений. Общая схема алгоритма циклического сдвига для топологии типа решетка-тор состоит в следующем. Пусть процессоры перенумерованы по строкам решетки от 0 до p-1. На первом этапе организуется циклический сдвиг с шагом по каждой строке в отдельности (если при реализации такого сдвига сообщения передаются через правые границы строк, то после выполнения каждой такой передачи необходимо осуществить компенсационный сдвиг вверх на 1 для процессоров первого столбца решетки). На втором этапе реализуется циклический сдвиг вверх с шагом для каждого столбца решетки. Общая длительность всех операций рассылок определяется соотношением:
|
(3.19) |
Для гиперкуба алгоритм циклического сдвига может быть получен путем логического представления топологии гиперкуба в виде кольцевой структуры. Для получения такого представления установим взаимно-однозначное соответствие между вершинами кольца и гиперкуба. Необходимое соответствие может быть получено, например, при помощи известного кода Грея. Более подробное изложение механизма установки такого соответствия осуществляется в подразделе 3.3; для наглядности на рис. 3.1 приводится вид гиперкуба для размерности N=3 с указанием для каждого процессора гиперкуба соответствующей вершины кольца.
Положительным свойством выбора такого соответствия является тот факт, что для любых двух вершин в кольце, расстояние между которыми равно l=2i для некоторого значения i, путь между соответствующими вершинами в гиперкубе содержит только две линии связи (за исключением случая i=0, когда путь в гиперкубе имеет единичную длину).
Рис. 3.1. Схема отображения гиперкуба на кольцо (в кружках приведены номера процессоров гиперкуба)
Представим величину сдвига q в виде двоичного кода. Количество ненулевых позиций кода определяет количество этапов в схеме реализации операции циклического сдвига. На каждом этапе выполняется операция сдвига с величиной шага, задаваемой наиболее старшей ненулевой позицией значения q (например, при исходной величине сдвига q=5=1012 на первом этапе выполняется сдвиг с шагом 4, на втором этапе шаг сдвига равен 1). Выполнение каждого этапа (кроме сдвига с шагом 1) состоит в передаче данных по пути, включающему две линии связи. Как результат, верхняя оценка для длительности выполнения операции циклического сдвига определяется соотношением:
(3.20) |
Передача пакетов. Использование пересылки пакетов может повысить эффективность выполнения операции циклического сдвига для топологии гиперкуб. Реализация всех необходимых коммуникационных действий в этом случае может быть обеспечена путем отправления каждым процессором всех пересылаемых данных непосредственно процессорам назначения. Применение метода покоординатной маршрутизации (см. п. 3.1.1) позволит избежать коллизий при использовании линий передачи данных (в каждый момент времени для каждого канала будет существовать не более одного готового для отправки сообщения). Длина наибольшего пути при такой рассылке данных определяется как log2p-?(q), где ?(q) есть наибольшее целое значение j такое, что 2j есть делитель величины сдвига q. Тогда длительность операции циклического сдвига может быть охарактеризована при помощи выражения
(3.21) |
(при достаточно больших размерах сообщений временем передачи служебных данных можно пренебречь и время выполнения операции может быть определено как ).
Контрольные вопросы
Какие основные характеристики используются для оценки топологии сети передачи данных? Приведите значения характеристик для конкретных типов коммуникационных структур (полный граф, линейка, решетка и др.).Какие основные методы применяются при маршрутизации передаваемых данных по сети?В чем состоят основные методы передачи данных? Приведите для этих методов аналитические оценки времени выполнения.Какие операции передачи данных могут быть выделены в качестве основных?В чем состоят алгоритмы выполнения передачи данных от одного процессора всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.В чем состоят алгоритмы выполнения передачи данных от всех процессоров всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.В чем состоят возможные алгоритмы выполнения операции редукции? Какой из алгоритмов является наилучшим по времени выполнения?В чем состоит алгоритм выполнения операции циклического сдвига? В чем состоит полезность использования логических топологий? Приведите примеры алгоритмов логического представления структуры коммуникационной сети.В чем состоит различие моделей для оценки времени выполнения операций передачи данных в кластерных вычислительных системах? Какая модель является более точной? Какая модель может быть использована для предварительного анализа временной трудоемкости коммуникационных операций?
Краткий обзор лекции
Данная лекция посвящена оценке коммуникационной сложности параллельных алгоритмов.
В подразделе 3.1 представлена общая характеристика алгоритмов маршрутизации и методов передачи данных. Для подробного рассмотрения выделены метод передачи сообщений и метод передачи пакетов, для которых определены оценки времени выполнения коммуникационных операций.
В подразделе 3.2 определены основные типы операций передачи данных, выполняемых в ходе параллельных вычислений. К основным коммуникационным операциям относятся:
передача данных между процессорами сети;передача данных от одного процессора всем остальным процессорам сети и двойственная ей операция приема на одном процессоре сообщений от всех остальных процессоров сети;передача данных от всех процессоров всем процессорам сети и двойственная ей операция приема сообщений на каждом процессоре от всех процессоров сети;обобщенная1) передача данных от одного процессора всем остальным процессорам сети и обратная операция обобщенного приема сообщений на одном процессоре от всех остальных процессоров сети;обобщенная передача данных от всех процессоров всем процессорам сети.
Для всех перечисленных операций передачи данных рассмотрены алгоритмы их выполнения на примере топологий кольца, решетки и гиперкуба. Для каждого из представленных алгоритмов приведены оценки их временной трудоемкости как для метода передачи сообщений, так и для метода передачи пакетов.
В подразделе 3.3 рассмотрены методы логического представления топологий на основе конкретных (физических) межпроцессорных структур. Использование логических топологий позволяет получить более простое изложение для ряда алгоритмов передачи данных, снизить затраты на реализацию коммуникационных операций и т.п.
В подразделе 3.4 более подробно обсуждаются модели, при помощи которых могут быть получены оценки времени выполнения операций передачи данных для кластерных вычислительных систем. Точность формирования временных оценок сравнивается при помощи проведения вычислительных экспериментов. По результатам экспериментов определена наиболее точная модель (модель B). Кроме того, отмечается, что для предварительного анализа временной трудоемкости коммуникационных операций целесообразно использовать более простую модель – модель C (модель Хокни).
Методы логического представления топологии коммуникационной среды
Как показало рассмотрение основных коммуникационных операций в подразделе 3.1, ряд алгоритмов передачи данных допускает более простое изложение при использовании вполне определенных топологий сети межпроцессорных соединений. Кроме того, многие методы коммуникации могут быть получены при помощи того или иного логического представления исследуемой топологии. Как результат, важным моментом при организации параллельных вычислений является возможность логического представления разнообразных топологий на основе конкретных (физических) межпроцессорных структур.
Способы логического представления (отображения) топологий характеризуются следующими тремя основными характеристиками:
уплотнение дуг (congestion), выражаемое как максимальное количество дуг логической топологии, которые отображаются в одну линию передачи физической топологии;удлинение дуг (dilation), определяемое как путь максимальной длины физической топологии, на который отображается дуга логической топологии;увеличение вершин (expansion), вычисляемое как отношение количества вершин в логической и физической топологиях.
Для рассматриваемых в рамках пособия топологий ограничимся изложением вопросов отображения топологий кольца и решетки на гиперкуб. Предлагаемые ниже подходы для логического представления топологий характеризуются единичными показателями уплотнения и удлинения дуг.
Методы передачи данных
Время передачи данных между процессорами определяет коммуникационную составляющую (communication latency) длительности выполнения параллельного алгоритма в многопроцессорной вычислительной системе. Основной набор параметров, описывающих время передачи данных, состоит из следующего ряда величин:
время начальной подготовки (tн) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т. п.;время передачи служебных данных (tс) между двумя соседними процессорами (т.е. для процессоров, между которыми имеется физический канал передачи данных). К служебным данным может относиться заголовок сообщения, блок данных для обнаружения ошибок передачи и т. п.;время передачи одного слова данных по одному каналу передачи данных (tк). Длительность подобной передачи определяется полосой пропускания коммуникационных каналов в сети.
К числу наиболее распространенных методов передачи данных относятся два основных способа коммуникации (см., например, [51]). Первый из них ориентирован на передачу сообщений (метод передачи сообщений или МПС) как неделимых (атомарных) блоков информации (store-and-forward routing или SFR). При таком подходе процессор, содержащий сообщение для передачи, готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию пересылки данных. Процессор, которому направлено сообщение, в первую очередь осуществляет прием полностью всех пересылаемых данных и только затем приступает к пересылке принятого сообщения далее по маршруту. Время пересылки данных tпд для метода передачи сообщения размером m байт по маршруту длиной l определяется выражением:
|
(3.1) |
При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение для времени передачи данных может быть записано в более простом виде:
|
(3.2) |
Второй способ коммуникации основывается на представлении пересылаемых сообщений в виде блоков информации меньшего размера – пакетов, в результате чего передача данных может быть сведена к передаче пакетов (метод передачи пакетов или МПП).
При таком методе коммуникации (cut- through routing или CTR) принимающий процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Время пересылки данных при использовании метода передачи пакетов определяется выражением:
(3.3) |
Сравнивая полученные выражения, можно заметить, что в большинстве случаев метод передачи пакетов приводит к более быстрой пересылке данных; кроме того, данный подход снижает потребность в памяти для хранения пересылаемых данных при организации приема-передачи сообщений, а для передачи пакетов могут использоваться одновременно разные коммуникационные каналы. С другой стороны, реализация пакетного метода требует разработки более сложного аппаратного и программного обеспечения сети, может увеличить накладные расходы (время подготовки и время передачи служебных данных). Кроме того, при передаче пакетов возможно возникновение конфликтных ситуаций (дедлоков).
Обобщенная передача данных от одного процессора всем остальным процессорам сети
Общий случай передачи данных от одного процессора всем остальным процессорам сети состоит в том, что все рассылаемые сообщения являются различными (one-to-all personalized communication или single-node scatter). Двойственная операция передачи для данного типа взаимодействия процессоров – обобщенный прием сообщений (single-node gather) на одном процессоре от всех остальных процессоров сети (отличие данной операции от ранее рассмотренной процедуры сборки данных на одном процессоре состоит в том, что обобщенная операция сборки не предполагает какого-либо взаимодействия сообщений (например, редукции) в процессе передачи данных).
Трудоемкость операции обобщенной рассылки сопоставима со сложностью выполнения процедуры множественной передачи данных. Процессор – инициатор рассылки посылает каждому процессору сети сообщение размера m, и, тем самым, нижняя оценка длительности выполнения операции характеризуется величиной mtk(p–1).
Проведем более подробный анализ трудоемкости обобщенной рассылки для случая топологии типа гиперкуб. Возможный способ выполнения операции состоит в следующем. Процессор – инициатор рассылки передает половину своих сообщений одному из своих соседей (например, по первой размерности) – в результате исходный гиперкуб становится разделенным на два гиперкуба половинного размера, в каждом из которых содержится ровно половина исходных данных. Далее, действия по рассылке сообщений могут быть повторены, и общее количество повторений определяется исходной размерностью гиперкуба. Длительность операции обобщенной рассылки может быть охарактеризована соотношением:
|
(3.14) |
(как и отмечалась выше, трудоемкость операции совпадает с длительностью выполнения процедуры множественной рассылки).
Обобщенная передача данных от всех процессоров всем процессорам сети
Обобщенная передача данных от всех процессоров всем процессорам сети (total exchange) представляет собой наиболее общий случай коммуникационных действий. Необходимость выполнения подобных операций возникает в параллельных алгоритмах быстрого преобразования Фурье, транспонирования матриц и др.
Выполним краткую характеристику возможных способов выполнения обобщенной множественной рассылки для разных методов передачи данных (см. п. 3.1.2).
Передача сообщений. Общая схема алгоритма для кольцевой топологии состоит в следующем. Каждый процессор производит передачу всех своих исходных сообщений своему соседу (в каком-либо выбранном направлении по кольцу). Далее процессоры осуществляют прием направленных к ним данных, затем среди принятой информации выбирают свои сообщения, после чего выполняют дальнейшую рассылку оставшейся части данных. Длительность выполнения подобного набора передач данных оценивается при помощи выражения:
|
(3.15) |
Способ получения алгоритма рассылки данных для топологии типа решетка-тор является тем же самым, что и в случае рассмотрения других коммуникационных операций. На первом этапе организуется передача сообщений раздельно по всем процессорам сети, располагающимся на одних и тех же горизонталях решетки (каждому процессору по горизонтали передаются только те исходные сообщения, что должны быть направлены процессорам соответствующей вертикали решетки). После завершения этапа на каждом процессоре собираются p сообщений, предназначенных для рассылки по одной из вертикалей решетки. На втором этапе рассылка данных выполняется по процессорам сети, образующим вертикали решетки. Общая длительность всех операций рассылок определяется соотношением:
|
(3.16) |
Для гиперкуба алгоритм обобщенной множественной рассылки сообщений может быть получен путем обобщения способа выполнения операции для топологии типа решетка на размерность гиперкуба N. В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1iN, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i-й размерности и формируют объединенные сообщения.
При организации взаимодействия двух соседей канал связи между ними рассматривается как связующий элемент двух равных по размеру подгиперкубов исходного гиперкуба, и каждый процессор пары посылает другому процессору только те сообщения, что предназначены для процессоров соседнего подгиперкуба. Время операции рассылки может быть получено при помощи выражения:
(3.17) |
(кроме затрат на пересылку, каждый процессор выполняет операций по сортировке своих сообщений перед обменом информацией со своими соседями).
Передача пакетов. Как и в случае множественной рассылки, применение метода передачи пакетов не приводит к улучшению временных характеристик для операции обобщенной множественной рассылки. Рассмотрим как пример более подробно выполнение данной коммуникационной операции для сети с топологией типа гиперкуб. В этом случае рассылка может быть выполнена за p-1 итерацию. На каждой итерации все процессоры разбиваются на взаимодействующие пары процессоров, причем это разбиение на пары может быть выполнено таким образом, чтобы передаваемые между разными парами сообщения не использовали одни и те же пути передачи данных. Как результат, общая длительность операции обобщенной рассылки может быть определена в соответствии с выражением:
(3.18) |
Обзор литературы
В качестве дополнительного учебного материала для данной лекции могут быть рекомендованы работы [51, 63].
Вопросы построения моделей для оценки времени выполнения коммуникационных операций широко обсуждаются в литературе. При изучении лекции могут быть полезны работы [[5], [28], [68]]. Модель Хокни впервые была опубликована в [[46]]. Модель B из подраздела 3.4 представлена в работе [[3]].
Оценка трудоемкости операций передачи данных для кластерных систем
Для кластерных вычислительных систем (см. п. 1.2.2) одним из широко применяемых способов построения коммуникационной среды является использование концентраторов (hub) или коммуникаторов (switch) для объединения процессорных узлов кластера в единую вычислительную сеть. В этих случаях топология сети кластера представляет собой полный граф, в котором, однако, имеются определенные ограничения на одновременность выполнения коммуникационных операций. Так, при использовании концентраторов передача данных в каждый текущий момент может выполняться только между двумя процессорными узлами; коммуникаторы могут обеспечивать взаимодействие нескольких непересекающихся пар процессоров.
Другое часто применяемое решение при создании кластеров состоит в использовании метода передачи пакетов (часто реализуемого на основе стека протоколов TCP/IP) в качестве основного способа выполнения коммуникационных операций.
Если выбрать для дальнейшего анализа кластеры данного распространенного типа (топология в виде полного графа, пакетный способ передачи сообщений), то трудоемкость операции коммуникации между двумя процессорными узлами может быть оценена в соответствии с выражением (модель А)
|
(3.23) |
оценка подобного вида следует из соотношений для метода передачи пакетов при единичной длине пути передачи данных, т.е. при l=1. Отмечая возможность подобного подхода, вместе с этим можно заметить, что в рамках рассматриваемой модели время подготовки данных tн предполагается постоянным (не зависящим от объема передаваемых данных), время передачи служебных данных tс не зависит от количества передаваемых пакетов и т.п. Эти предположения не в полной мере соответствуют действительности, и временные оценки, получаемые в результате использования модели, могут не обладать необходимой точностью.
С учетом приведенных замечаний, схема построения временных оценок может быть уточнена; в рамках новой расширенной модели трудоемкость передачи данных между двумя процессорами определяется в соответствии со следующими выражениями (модель В):
|
(3.24) |
/p> где есть количество пакетов, на которое разбивается передаваемое сообщение, величина Vmax определяет максимальный размер пакета, который может быть доставлен в сети (по умолчанию для операционной системы MS Windows в сети Fast Ethernet Vmax=1500 байт), а Vc есть объем служебных данных в каждом из пересылаемых пакетов (для протокола TCP/IP, ОС Windows 2000 и сети Fast Ethernet Vc=78 байт). Поясним также, что в приведенных соотношениях константа характеризует аппаратную составляющую латентности и зависит от параметров используемого сетевого оборудования, значение задает время подготовки одного байта данных для передачи по сети. Как результат, величина латентности
(3.25) |
увеличивается линейно в зависимости от объема передаваемых данных. При этом предполагается, что подготовка данных для передачи второго и всех последующих пакетов может быть совмещена с пересылкой по сети предшествующих пакетов и латентность, тем самым, не может превышать величины:
(3.26) |
Помимо латентности, в предлагаемых выражениях для оценки трудоемкости коммуникационной операции можно уточнить также правило вычисления времени передачи данных
(3.27) |
что позволяет теперь учитывать эффект увеличения объема передаваемых данных при росте числа пересылаемых пакетов за счет добавления служебной информации (заголовков пакетов).
Завершая анализ проблемы построения теоретических оценок трудоемкости коммуникационных операций, следует отметить, что для практического применения перечисленных моделей необходимо выполнить оценку значений параметров используемых соотношений. В этом отношении полезным может оказаться использование и более простых способов вычисления временных затрат на передачу данных – одной из известных схем подобного вида является подход, в котором трудоемкость операции коммуникации между двумя процессорными узлами кластера оценивается в соответствии с выражением:
(3.28) |
это модель C, предложенная Хокни (the Hockney model) – см., например, [46].
Для проверки адекватности рассмотренных моделей реальным процессам передачи данных приведем результаты выполненных экспериментов в сети многопроцессорного кластера Нижегородского университета (компьютеры IBM PC Pentium 4 1300 MГц и сеть Fast Etherrnet).
При проведении экспериментов для реализации коммуникационных операций использовалась библиотека MPI.
Часть экспериментов была выполнена для оценки параметров моделей:
значение латентности tн для моделей A и C определялось как время передачи сообщения нулевой длины;величина пропускной способности R оценивалась максимальным значением скорости передачи данных, наблюдавшимся в экспериментах, т.е. величиной
и полагалось tк=1/R;значения величин и оценивались при помощи линейной аппроксимации времен передачи сообщений размера от 0 до Vmax.
В ходе экспериментов осуществлялась передача данных между двумя узлами кластера, размер передаваемых сообщений варьировался от 0 до 8 Мб. Для получения более точных оценок выполнение каждой операции осуществлялось многократно (более 100 000 раз), после чего полученные результаты усреднялись. Для иллюстрации ниже приведен результат одного эксперимента, при проведении которого размер передаваемых сообщений изменялся от 2000 до 60 000 байт.
В табл. 3.2 приводится ряд числовых данных по погрешности рассмотренных моделей трудоемкости коммуникационных операций (величина погрешности дается в виде относительного отклонения от реального времени выполнения операции передачи данных).
| 2000 | 495 | 33,45 | 7,93 | 34,80 |
| 10000 | 1184 | 13,91 | 1,70 | 14,48 |
| 20000 | 2055 | 8,44 | 0,44 | 8,77 |
| 30000 | 2874 | 4,53 | -1,87 | 4,76 |
| 40000 | 3758 | 4,04 | -1,38 | 4,22 |
| 50000 | 4749 | 5,91 | 1,21 | 6,05 |
| 60000 | 5730 | 6,97 | 2,73 | 7,09 |
Как можно заметить по результатам проведенных экспериментов, оценки трудоемкости операций передачи данных по модели B имеют меньшую погрешность.
Вместе с этим важно отметить, что для предварительного анализа временных затрат на выполнение коммуникационных операций точности модели C C может оказаться достаточно. Кроме того, данная модель имеет наиболее простой вид среди всех рассмотренных.С учетом последнего обстоятельства, далее во всех последующих лекциях для оценки трудоемкости операций передачи данных будет применяться именно модель C (модель Хокни), при этом для модели будет использоваться форма записи, приведенная к обозначениям, которые приняты в работе Хокни [46]:
(3.29) |
где есть латентность сети передачи данных (т.е. =tн), а ? обозначает пропускную способность сети (т.е. ?=R=1/tк).
Отображение топологии решетки на гиперкуб
Отображение топологии решетки на гиперкуб может быть выполнено в рамках подхода, использованного для кольцевой структуры сети.
Тогда для отображения решетки на гиперкуб размерности N=r+s можно принять правило, что элементу решетки с координатами (i, j) соответствует процессор гиперкуба с номером:
G(i,r)||G(j,s),
где операция || означает конкатенацию кодов Грея.
Передача данных между двумя процессорами сети
Трудоемкость данной коммуникационной операции может быть получена путем подстановки длины максимального пути (диаметра сети) в выражения для времени передачи данных при разных методах коммуникации (см. п. 3.1.2) – см. табл. 3.1.
| Кольцо | ||
| Решетка-тор | ||
| Гиперкуб |
Передача данных от одного процессора всем остальным процессорам сети
Операция передачи данных (одного и того же сообщения) от одного процессора всем остальным процессорам сети (one-to-all broadcast или single-node broadcast) является одним из наиболее часто выполняемых коммуникационных действий. Двойственная ей операция – прием на одном процессоре сообщений от всех остальных процессоров сети (single-node accumulation). Подобные операции используются, в частности, при реализации матрично-векторного умножения, решении систем линейных уравнений методом Гаусса, решении задачи поиска кратчайших путей и др.
Простейший способ реализации операции рассылки состоит в ее выполнении как последовательности попарных взаимодействий процессоров сети. Однако при таком подходе большая часть пересылок является избыточной и возможно применение более эффективных алгоритмов коммуникации. Изложение материала будет проводиться сначала для метода передачи сообщений, затем – для пакетного способа передачи данных (см. п. 3.1.2).
Передача сообщений. Для кольцевой топологии процессор – источник рассылки может инициировать передачу данных сразу двум своим соседям, которые, в свою очередь, приняв сообщение, организуют пересылку далее по кольцу. Трудоемкость выполнения операции рассылки в этом случае будет определяться соотношением:
|
(3.4) |
Для топологии типа решетка-тор алгоритм рассылки может быть получен из способа передачи данных, примененного для кольцевой структуры сети. Так, рассылка может быть выполнена в виде двухэтапной процедуры. На первом этапе организуется передача сообщения всем процессорам сети, располагающимся на той же горизонтали решетки, что и процессор – инициатор передачи. На втором этапе процессоры, получившие копию данных на первом этапе, рассылают сообщения по своим соответствующим вертикалям. Оценка длительности операции рассылки в соответствии с описанным алгоритмом определяется соотношением:
|
(3.5) |
Для гиперкуба рассылка может быть выполнена в ходе N-этапной процедуры передачи данных. На первом этапе процессор-источник сообщения передает данные одному из своих соседей (например, по первой размерности) – в результате после первого этапа есть два процессора, имеющих копию пересылаемых данных (данный результат можно интерпретировать также как разбиение исходного гиперкуба на два таких одинаковых по размеру гиперкуба размерности N-1, что каждый из них имеет копию исходного сообщения).
На втором этапе два процессора, задействованные на первом этапе, пересылают сообщение своим соседям по второй размерности и т.д. В результате такой рассылки время операции оценивается при помощи выражения:
(3.6) |
Сравнивая полученные выражения для длительности выполнения операции рассылки, можно отметить, что наилучшие показатели имеет топология типа гиперкуб; более того, можно показать, что данный результат является наилучшим для выбранного способа коммуникации с помощью передачи сообщений.
Передача пакетов. Для топологии типа кольцо алгоритм рассылки может быть получен путем логического представления кольцевой структуры сети в виде гиперкуба. В результате на этапе рассылки процессор – источник сообщения передает данные процессору, находящемуся на расстоянии p/2 от исходного процессора. Далее, на втором этапе оба процессора, уже имеющие рассылаемые данные после первого этапа, передают сообщения процессорам, находящимся на расстоянии p/4, и т.д. Трудоемкость выполнения операции рассылки при таком методе передачи данных определяется соотношением:
(3.7) |
(как и ранее, при достаточно больших сообщениях временем передачи служебных данных можно пренебречь).
Для топологии типа решетка-тор алгоритм рассылки может быть получен из способа передачи данных, примененного для кольцевой структуры сети, в соответствии с тем же способом обобщения, что и в случае использования метода передачи сообщений. Получаемый в результате такого обобщения алгоритм рассылки характеризуется следующим соотношением для оценки времени выполнения:
(3.8) |
Для гиперкуба алгоритм рассылки (и, соответственно, временные оценки длительности выполнения) при передаче пакетов не отличается от варианта для метода передачи сообщений.
Передача данных от всех процессоров всем процессорам сети
Операция передачи данных от всех процессоров всем процессорам сети (all-to-all broadcast или multinode broadcast) является естественным обобщением одиночной операции рассылки, двойственная ей операция – прием сообщений на каждом процессоре от всех процессоров сети (multinode accumulation). Подобные операции широко используются, например, при реализации матричных вычислений.
Возможный способ реализации операции множественной рассылки состоит в выполнении соответствующего набора операций одиночной рассылки. Однако такой подход не является оптимальным для многих топологий сети, поскольку часть необходимых операций одиночной рассылки потенциально может быть выполнена параллельно. Как и ранее, материал будет рассматриваться раздельно для разных методов передачи данных (см. п. 3.1.2).
Передача сообщений. Для кольцевой топологии каждый процессор может инициировать рассылку своего сообщения одновременно (в каком-либо выбранном направлении по кольцу). В любой момент каждый процессор выполняет прием и передачу данных, завершение операции множественной рассылки произойдет через p-1 цикл передачи данных. Длительность выполнения операции рассылки оценивается соотношением:
|
(3.9) |
Для топологии типа решетка-тор множественная рассылка сообщений может быть выполнена при помощи алгоритма, получаемого обобщением способа передачи данных для кольцевой структуры сети. Схема обобщения состоит в следующем. На первом этапе организуется передача сообщений раздельно по всем процессорам сети, располагающимся на одних и тех же горизонталях решетки (в результате на каждом процессоре одной и той же горизонтали формируются укрупненные сообщения размера , объединяющие все сообщения горизонтали). Время выполнения этапа:
На втором этапе рассылка данных выполняется по процессорам сети, образующим вертикали решетки. Длительность этого этапа:
Общая длительность операции рассылки определяется соотношением:
|
(3.10) |
Для гиперкуба алгоритм множественной рассылки сообщений может быть получен путем обобщения ранее описанного способа передачи данных для топологии типа решетки на размерность гиперкуба N.
В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1iN, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i-ой размерности и формируют объединенные сообщения. Время операции рассылки может быть получено при помощи выражения:
(3.11) |
Передача пакетов. Применение более эффективного для кольцевой структуры и топологии типа решетка-тор метода передачи данных не приводит к какому-либо улучшению времени выполнения операции множественной рассылки, поскольку обобщение алгоритмов выполнения операции одиночной рассылки на случай множественной рассылки приводит к перегрузке каналов передачи данных (т.е. к существованию ситуаций, когда в один и тот же момент для передачи по одной и той же линии имеется несколько ожидающих пересылки пакетов данных). Перегрузка каналов приводит к задержкам при пересылках данных, что и не позволяет проявиться всем преимуществам метода передачи пакетов.
Широко распространенным примером операции множественной рассылки является задача редукции (reduction), которая определяется в общем виде как процедура выполнения той или иной обработки данных, получаемых на каждом процессоре в ходе множественной рассылки (в качестве примера такой задачи может быть рассмотрена проблема вычисления суммы значений, находящихся на разных процессорах, и рассылки полученной суммы по всем процессорам сети). Способы решения задачи редукции могут состоять в следующем:
непосредственный подход заключается в выполнении операции множественной рассылки и последующей затем обработке данных на каждом процессоре в отдельности;более эффективный алгоритм может быть получен в результате применения операции одиночного приема данных на отдельном процессоре, выполнения на этом процессоре действий по обработке данных и рассылки полученного результата обработки всем процессорам сети;наилучший же способ решения задачи редукции состоит в совмещении процедуры множественной рассылки и действий по обработке данных, когда каждый процессор сразу же после приема очередного сообщения реализует требуемую обработку полученных данных (например, выполняет сложение полученного значения с имеющейся на процессоре частичной суммой).
Время решения задачи редукции при таком алгоритме реализации в случае, например, когда размер пересылаемых данных имеет единичную длину (m=1) и топология сети имеет структуру гиперкуба, определяется выражением:
(3.12) |
Другим типовым примером использования операции множественной рассылки является задача нахождения частных сумм последовательности значений Si (в англоязычной литературе эта задача известна под названием prefix sum problem)
(3.13) |
(будем предполагать, что количество значений совпадает с количеством процессоров, значение xi располагается на i-м процессоре и результат Sk должен получаться на процессоре с номером k).
Алгоритм решения данной задачи также может быть получен при помощи конкретизации общего способа выполнения множественной операции рассылки, когда процессор выполняет суммирование полученного значения (но только в том случае, если процессор – отправитель значения имеет меньший номер, чем процессор-получатель).
Представление кольцевой топологии в виде гиперкуба
Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i, N) (binary reflected Gray code), определяемого в соответствии с выражениями:
|
(3.22) |
где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода в табл. 3.1 показывается отображение кольцевой топологии на гиперкуб для сети из p=8 процессоров.
Важное свойство кода Грея: соседние значения G(i,N) и G(i+1,N) имеют только одну различающуюся битовую позицию. Как результат, соседние вершины в кольцевой топологии отображаются на соседние процессоры в гиперкубе.
| 0 | 0 0 | 0 0 0 | 0 | 0 |
| 1 | 0 1 | 0 0 1 | 1 | 1 |
| 1 1 | 0 1 1 | 3 | 2 | |
| 1 0 | 0 1 0 | 2 | 3 | |
| 1 1 0 | 6 | 4 | ||
| 1 1 1 | 7 | 5 | ||
| 1 0 1 | 5 | 6 | ||
| 1 0 0 | 4 | 7 |
Разработайте алгоритмы выполнения основных операций
Разработайте алгоритмы выполнения основных операций передачи данных для топологии сети в виде 3-мерной решетки.Разработайте алгоритмы выполнения основных операций передачи данных для топологии сети в виде двоичного дерева.Примените модель B из подраздела 3.4 для оценки временной сложности операций передачи данных. Сравните получаемые показатели.Примените модель C из подраздела 3.4 для оценки временной сложности операций передачи данных. Сравните получаемые показатели.Разработайте алгоритмы логического представления двоичного дерева для различных физических топологий сети.
