В данном разделе, будут кратко рассмотрены архитектура современных высокопроизводительных процессоров и кластерных систем. На примере сети Infiniband будут продемонстрированы принципы построения быстрых сетей передачи данных, используемых в кластерных установках. Более детально будет представлена архитектура наиболее производительных кластерных вычислительных систем: Blue Gene/L и семейства SGI Altix.

В качестве базового программного обеспечения для организации вычислений на кластерных системах рассматривается Windows Compute Cluster Server (CCS) 2003. Дается его общая характеристика и состав сервисов, работающих на узлах кластеров.

В заключение данного раздела, приводятся правила работы с консолью запуска и управления заданиями CCS. Описываются подробности работы планировщика CCS при исполнении последовательностей заданий на кластере.

В истории развития архитектуры компьютерных процессоров можно выделить два крупных этапа:

• 1-й этап - увеличение тактовой частоты работы процессоров (до 2000 г.),
• 2-й этап - появление многоядерных процессоров ( после 2000) г.

Таким образом, подход на основе SMP (Symmetrical MultiProcessing), который развивался при построении высокопроизводительных серверов, в которых несколько процессоров разделяют ресурс системы, и, в первую очередь, оперативную память (см. Рис 1.1), сместился "вниз" на уровень ядер внутри процессора.

На пути к многоядерным процессорам, первой появилась технология Hyper-Threading, впервые примененная в 2002 г. в процессорах Intel Pentium 4:

В этой технологии два виртуальных процессора разделяют между собой все ресурсы одного физического процессора, а именно, кэши, конвейер исполнения и отдельные исполнительные устройства. При этом, если один виртуальный процессор занял общий ресурс, то второй будет ожидать его освобождения. Тем самым, процессор с Hyper-Threading можно сравнить с многозадачной операционной системой, обеспечивающей каждому работающему в ней процессу свой виртуальный компьютер с полным набором средств и занимающейся планированием порядка и времени работы этих процессов на физическом оборудовании. Только в случае с Hyper-Threading, все это происходит на значительно более низком аппаратном уровне. Тем не менее, два потока команд позволяют более эффективно загрузить исполнительные устройства процессора. Реальный прирост производительности процессора от применения технологии Hyper-Threading оценивается от 10 до 20 процентов.

Полноценный двухъядерный процессор (см. Рис 1.3), на отдельных задачах демонстрирует прирост производительности от 80 до 100 процентов.

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

Более того, каждое ядро может (как, например, в процессоре Intel Pentium Extreme Edition 840) поддерживать технологию Hyper-Threading, а потому такого рода двухъядерный процессор может выполнять четыре программных потока одновременно.

В начале 2007 г., корпорация Intel представила 80-ядерный однокристальный процессор, получивший название Teraflops Research Chip (http://www.intel.com/research/platform/terascale/teraflops.htm). Этот процессор может достигать производительности 1,01 терафлопс при минимальной тактовой частоте ядра 3,16 ГГц и напряжении 0,95 В. При этом общее энергопотребление чипа составляет всего 62 Вт.

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

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

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

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

Программное обеспечение кластеров состоит из двух компонент:

• средств разработки/программирования и
• средств управления ресурсами.

К средствам разработки относятся компиляторы для языков, библиотеки различного назначения, средства измерения производительности, а также отладчики, что, всё вместе, позволяет строить параллельные приложения.

К программному обеспечению управления ресурсами относятся средства инсталляции, администрирования и планирования потоков работ.

Хотя для параллельной обработки существует очень много моделей программирования, но, на настоящий момент, доминирующим подходом является модель на основе "передачи сообщений" (message passing), реализованная в виде стандарта MPI (Message Passing Interface). MPI - это библиотека функций, с помощью которых в программах на языках C или Фортран можно передавать сообщения между параллельными процессами, а также управлять этими процессами.

Альтернативами такому подходу являются языки на основе так называемого "глобального распределенного адресного пространства" (GPAS - global partitioned address space), типичными представителями которых являются языки HPF (High Performance Fortran) и UPC (Unified Parallel C).

Выбор сетевой технологии зависит от ряда факторов, среди которых

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

Технические характеристики сети, непосредственно связанные с передачей данных, выражаются в терминах задержки (latency) и широты полосы пропускания (bandwidth).

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

Широта полосы пропускания есть количество бит за секунду, которое может быть передано по участку сети.

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

Коммуникационный протокол определяет правила и соглашения, которые используются двумя или более компьютерами для обмена данными по сети.

В кластерах используются как традиционные сетевые протоколы, предназначенные для Internet, так и протоколы, специально ориентированные на использование в кластерах.

Типичными IP (Internet Protocol)-протоколами являются TCP (Transmission Control Protocol) и UDP (User Datagram Protocol). Эти протоколы совместно с прикладным интерфейсом программиста (Application Programming Interface) на основе BSD-сокетов, были первой библиотекой для передачи сообщений для использования в кластерах.

Исследования по протоколам с малой задержкой привели к созданию стандарта VIA (Virtual Interface Architecture). В частности, существует реализация версии MPICH стандарта MPI, которая называется MVICH, работающая с использованием VIA.

Большой консорциум промышленных партнеров, включая Compaq, Dell, Hewlett-Packard, IBM и др., разработали и поддерживают стандарт Infiniband для передачи данных с малой задержкой. В Infiniband -архитектуре (см. Рис 1.4) компьютеры связываются между собой на основе высокоскоростной, последовательной, расширяемой, переключаемой фабрики, работающей на основе передачи сообщений.

Все системы и устройства подсоединяются к фабрике либо через HCA-адаптеры (host channel adapters), либо через TCA-адаптеры (target channel adapters). Скорость передачи данных по отдельной Infiniband-линии - свыше 2,5 Гб/сек.

Кроме того, в Infiniband поддерживается режим RDMA (Remote Direct Memory Access), который позволяет одному процессору обращаться к содержимому памяти другого процессора непосредственно, а также протокол IPv6 передачи сообщений для Internet.

Кластерная вычислительная система Blue Gene/L - это первый шаг на пути реализации программы по созданию компьютера с производительностью 1 петафлопс, осуществляемой фирмой IBM.

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

Принципиальный подход, принятый при построении семейства машин Blue Gene состоит в том, что система, по-прежнему, собирается из огромного числа узлов, однако, каждый из них работает на сравнительно небольшой тактовой частоте. Тем самым, достигается как снижение стоимости системы, так и значительное уменьшение энергопотребления. Другая главная особенность Blue Gene/L заключается в применении так называемой технологии "система на чипе" - применении интегральных микросхем со сверхвысокой степенью интеграции, когда в рамках одной интегральной схемы объединяются:

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

Система Blue Gene/L является масштабируемым (расширяемым) суперкомпьютером, который может состоять из более, чем 65536 вычислительных процессоров.

Архитектура суперкомпьютера Blue Gene/L показана на Рис 1.5.

Базовым компонентом суперкомпьютера Blue Gene/L является так называемая "вычислительная карта" (compute card), которая состоит из двух вычислительных узлов, где каждый узел содержит 2 процессора PowerPC 440. 16 вычислительных карт группируются в модульную (или узловую) карту, которая, таким образом, содержит уже 64 процессора. В свою очередь, 16 модульных карт устанавливаются на объединительной панели (midplane), и две таких панели монтируются в серверную стойку (cabinet), которая содержит в итоге 1024 узла с общим количеством процессоров 2048.

Процессор PowerPC 440 способен выполнять за такт 4 операции с плавающей запятой, что для заданной частоты соответствует пиковой производительности в 1,4 терафлопса на одну объединительную панель (midplane), если считать, что на каждом узле установлено по одному процессору. Второй процессор на узле, идентичный первому, призван выполнять телекоммуникационные функции, то есть, он предназначен, преимущественно, для осуществления связи с другими процессорами суперкомпьютера. Кроме того, конструкцией суперкомпьютера, предусмотрена установка некоторого количества двухпроцессорных узлов, которые занимаются исключительно операциями ввода/вывода.

Узлы суперкомпьютера связаны между собой пятью сетями:

1. трехмерной тороидальной сетью для обмена данными непосредственно между блоками-узлами,
2. сетью с топологией "дерева" для выполнения общих (глобальных) для всех блоков операций,
3. сетью барьеров и прерываний,
4. сетью Gigabit Ethernet-JTAG (Ethernet со специальным интерфейсом JTAG),
5. еще одной сетью Gigabit Ethernet для подключения к главному (хост-) компьютеру, файловым серверам и другим системам.

Энергопотребление суперкомпьютера Blue Gene/L относительно невелико: оно составляет порядка 1,6 мегаватт. Для сравнения, суперкомпьютер ASC Purple - предыдущая машина, разработанная IBM для Ливерморской лаборатории, потребляет 4,8 мегаватт при производительности 100 терафлопс. Разница объясняется тем, что Blue Gene/L состоит из специально разработанных компактных блоков, размещенных в 64 серверных стойках (см. Рис 1.6), тогдакак ASC Purple построена на основе обычных серверов - аналогов серверов IBM eServe p655.

С точки зрения программного обеспечения, суперкомпьютер Blue Gene/L работает под управлением специальной версии операционной системы Linux, разработанной в IBM.

Этот суперкомпьютер использовался для моделирования взаимодействия 16 миллионов атомов в образце тантала, застывающего под давлением. Кроме того, Blue Gene/L применялся в Национальной лаборатории Лос-Аламоса для изучения появления раковин в металле, при этом моделировалось в динамике взаимодействие более 2,1 миллиарда атомов.

Компания Silicon Graphics Incorporated (SGI) является традиционным производителем многопроцессорных систем с архитектурой SMP и ccNUMA. Спецификой архитектуры ccNUMA является объединение памяти отдельных процессоров в единую глобальную память, где каждый процессор имеет доступ в каждую ячейку этой памяти. SGI выпустила два поколения многопроцессорных серверов с ccNUMA-архитектурой, а именно Origin 2000 и Origin 3000. Однако, данные серверы обладали сравнительно малой производительностью из-за использованных в них собственных процессоров R1x000 компании SGI.

Поэтому в новом семействе серверов с ccNUMA-архитектурой SGI Altix 3000 были применены процессоры Itanium 2/ Madison с тактовой частотой 1,5 ГГц и КЭШем третьего уровня емкостью 6 Гбайт. Следует отметить, что ccNUMA-системы на базе Itanium 2 выпускают также компания Hewlett-Packard, а именно системы HP Superdome.

Системы SGI Altix строятся из так называемых "кирпичей" (bricks) - модулей разных габаритов, однако, помещаемых в стандартную стойку и соединяемых кабелями. В таблице 1.1 приведены основные типы "кирпичей" семейства SGI Altix 3000.

Основу системы составляют "вычислительные" кирпичи - С-блоки (см. Рис 1.7).

Каждый С-кирпич содержит 4 процессора Itanium-2 и состоит из двух узлов по 2 процессора в каждом. Узлы соединены между собой дуплексными каналами типа NUMAlink 4 с общей пропускной способностью 6,4 Гбайт/с на канал. Два коммутатора SHUB, имеющиеся в каждом С-кирпиче, связывают основные компоненты узлов и могут подсоединяться к 8-портовым коммутаторам типа NUMAlink3 с пропускной способностью 3,2 Гбайт/с в дуплексном режиме. Такая архитектура позволяет иметь в системах семейства SGI Altix до 512 процессоров.

Допустимая емкость оперативной памяти в С-кирпиче - от 4 до 16 Гбайт. Для расширения емкости памяти возможно применение также специальных М-кирпичей, которые аналогичны С-кирпичам, но не содержат микропроцессоров.

R-кирпичи содержат коммутаторы, которые в семействах машин SGI называются маршрутизаторами. Эти маршрутизаторы могут соединять между собой С-кирпичи, а в более крупных конфигурациях, и другие коммутаторы.

Возможные способы организации межсоединений для различных конфигураций систем показаны на Рис 1.8, 1.9.

На Рис 1.8 представлены возможные конфигурации без использования маршрутизаторов. На Рис 1.9 показаны одностоечные конфигурации с двусторонней (dual-plane) топологией, которая предусматривает дублирование соединений между С-кирпичами за счет использования пар машрутизаторов. Также возможны многостоечные конфигурации с двусторонним соединением.

Кроме С-кирпичей, каждая система SGI Altix имеет хотя бы один IX-кирпич, реализующий базовые средства ввода-вывода. Кроме IX-кирпичей, имеются так называемые PX-кирпичи, которые предназначены для подключения дополнительных шин типа PCI.

D-кирпичи представляют собой корпус для монтирования отдельных жестких дисков (общим числом до 16, но минимум - два диска). Для D-кирпичей обеспечивается горячая замена дисков.

Машины семейства SGI Altix снабжаются специальной версией ОС Linux, разработанной в SGI. В частности, в ядро данной операционной системы внесена поддержка архитектуры ccNUMA. Все доработки, внесенные в ядро операционной системы разработчиками из SGI, являются общедоступными.

Microsoft Windows Compute Cluster Server (CCS) 2003 является интегрированной платформой для проведения высокопроизводительных вычислений. С использованием этой платформы, производить вычисления на кластерах, имеющих от нескольких до сотен, и даже, тысяч узлов.

Конфигурирование, мониторинг, управление и обеспечение безопасного доступа для кластеров является очень трудной задачей, на решение которой требуется обычно большое количество времени и ресурсов. Одна из целей Windows CCS 2003 - максимально упростить управление вычислительными кластерами и сократить общую стоимость владения ими (TCO - total cost of ownership), одновременно сделав их доступными для более широкого круга пользователей. В частности, для Windows CCS 2003 процессы установки и администрирования максимально автоматизированы. Это достигается через интеграцию Windows CCS 2003 с технологиями Active Directory и Microsoft Operations Manger (MOM). Для удобства использования, в состав Windows CCS 2003 входит планировщик заданий (job scheduler), работа с которым обеспечивается через графический интерфейс пользователя и через командную строку.

Windows CCS 2003 поддерживает исполнение параллельных приложений, базирующихся на стандарте Message Passing Interface (MPI). Кроме того, для того, чтобы можно было использовать среду разработки Visual Studio 2005 для создания параллельных приложений, в нее включены поддержка стандарта OpenMP, а также возможность отладки параллельных программ, использующих MPI.

Версия MPI, используемая в Windows CCS 20033 - MS MPI, является вариантом одной из реализаций MPI, разработанной в Аргонской национальной лаборатории, и названной MPICH2.

MS MPI построен на основе WinSock API (Windows Sockets networking API), и передача данных через сеть может осуществляться либо через обычный протокол TCP/IP, либо через драйвер WinSock Direct Provider, обеспечивающий непосредственную (игнорируя слой TCP/IP) передачу данных через сетевую аппаратуру. Тем самым, MS MPI обеспечивает поддержку сетей Ethernet либо Gigabit Ethernet через TCP/IP, и сетей с малым временем задержки и широкой полосой пропускания, таких как Infiniband или Myrinet через драйверы WinSock Direct.

MS MPI обеспечивает поддержку языков программирования C, Fortran 77 и Fortran 90. Среда разработки Microsoft Visual Studio 2005 включает в себя отладчик параллельных программ, написанных с применением MS MPI. Разработчики могут запускать свои MPI-приложения на множестве вычислительных узлов непосредственно из Visual Studio, причем Visual Studio автоматически связывается с процессами на узлах, что позволяет разработчикам, по индивидуальному выбору, останавливать программу на любом из узлов и просматривать значения программных переменных.

Windows CCS 2003 поддерживает пять различных сетевых топологий головного и вычислительных узлов кластера, где эти топологии отличаются друг от друга своей производительностью (скоростью передачи данных) и возможностями доступа в данную сеть. Каждая из топологий включает в себя, по меньшей мере, один из следующих типов сетей:

• общая (public) сеть,
• частная (private) сеть и
• MPI-сеть,

или, возможно, некоторую их комбинацию.

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

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

MPI-сеть - это выделенная, высокоскоростная сеть, предназначенная для передачи сообщений параллельных приложений, работающих на вычислительных узлах кластера. Если в кластере такой сети не существует, то MPI-трафик передается через частную сеть. Если и частной сети не существует, то MPI-трафик будет проходить через общую сеть.

Использование отдельных сетей для передачи внутрикластерного (служебного) и MPI-трафика между вычислительными узлами и головным узлом значительно повышает общую производительность кластера и разгружает от этого трафика общую сеть. Тем не менее, доступ в общую сеть с вычислительных узлов, по-прежнему, возможен с помощью сервиса NAT (Network Address Translation), запущенного на головном узле.

Windows CCS 2003 поддерживает кластеры, состоящие из одного головного узла и одного или нескольких вычислительных узлов, как показано на Рис 1.10.

Головной узел управляет и является посредником для доступа ко всем ресурсам кластера и представляет собой единую точку для управления, развертывания ресурсов и исполнения заданий на вычислительном кластере. Windows CCS 2003 может использовать существующую инфраструктуру Active Directory для обеспечения безопасности, управления учетными записями и общим управлением всеми операциями, а также может быть интегрирован с такими средствами управления, как MOM ( Microsoft Operations Manager) 2005 и SMS (Systems Management Server) 2003.

Развертывание Microsoft CCS 2003 включает в себя:

1. установку базовой операционной системы на головном узле,
2. присоединение головного узла к существующему Active Directory-домену,
3. установку пакета Compute Cluster Pack.

Если планируется использовать сервис удаленной установки (RIS - Remote Installation Service), то RIS будет установлен и сконфигурирован на последнем шаге процедуры развертывания.

После окончания установки пакета Compute Cluster Pack на головном узле, на его экране отображается ToDo-список, который показывает какие шаги необходимо выполнить для завершения конфигурирования вычислительного кластера. Эти шаги включают в себя:

1. определение топологии сети,
2. конфигурирование RIS с помощью соответствующего мастера,
3. добавление вычислительных узлов в кластер,
4. конфигурирование информации о пользователях и администраторах кластера

На головном узле кластера устанавливаются следующие сервисы:

1. Management Service - управление кластером, обнаружение узлов, управление конфигурациями
2. Scheduler Service - постановка заданий в очередь, планирование их запуска, распределение ресурсов, исполнение заданий
3. SDM Store Service - операции чтения/записи в хранилище данных System Definition Model (SDM), управление целостностью
4. MPI Service - реализация MPI на основе MPICH2
5. Node Manager Service - устанавливается на головном узле, когда он сконфигурирован также и в качестве вычислительного узла; взаимодействует с Scheduler Service и отвечает за исполнение заданий
6. SQL Service - Microsoft SQL Server 2000 Desktop Engine (MSDE)

На вычислительных узлах кластера устанавливаются следующие сервисы:

1. Management Service - взаимодействует с одноименным сервисом на головном узле; отвечает за управление кластером, обнаружение узлов и управление конфигурациями со стороны вычислительного узла
2. MPI Service - реализация MPI на основе MPICH2
3. Node Manger Service - взаимодействует с Scheduler Service на головном узле; отвечает за исполнении заданий

Менеджер заданий в составе Windows CCS 2003 (Compute Cluster Job Manager) является приложением с графическим интерфейсом, которое обеспечивает доступ к планировщику заданий (Job Scheduler) для их создания, отправки на кластер и мониторинга исполнения. Менеджер заданий может быть установлен и исполняться на машине, не принадлежащей вычислительному кластеру, что дает возможность использовать кластер удаленно.

Графический интерфейс менеджера заданий состоит из

1. заголовка,
2. меню,
3. верхней панели отображения и
4. нижней панели отображения

(см. Рис 1.11).

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

Меню состоит из пунктов File, View, Show и Help. С помощью File и View, можно подсоединиться к кластеру, создать задание, отослать его на исполнение и др. С помощью пункта Show можно просматривать очередь заданий на исполнение с возможностью фильтрации этой очереди в соответствии с различными критериями.

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

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

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

Вид панели Tasks шаблона заданий показан на Рис 1.12.

Любая функция менеджера заданий имеет эквивалент в виде соответствующей командной строки. Все множество командных строк делится на 2 группы:

• операции пользователя: создание заданий, отправка их на кластер и управление ими;
• операции администратора: управление кластером как таковым.

Наличие интерфейса командной строки позволяет разрабатывать сложные сценарии (скрипты) для выполнения специальных работ на кластере и управления им.

К операциям пользователя относятся команды job и task с соответствующими параметрами.

1. • job new [job_terms] - создать задание
   • job add jobID [ task_terms] - добавить задачи к заданию
   • job submit /id:jobid - отправить задание, созданное с помощью job new
   • job submit [job_terms] [task_terms] - отправить задание
   • job cancel jobID - снять задание
   • job modify [ options ] - модифицировать задание
   • job requeue [ jobID ] - заново поставить задание в очередь
   • job list - выдать список заданий, исполняющихся на кластере
   • job listtasks - выдать список задач задания
   • job view jobID - выдать сведения о задании
2. • task view taskID - выдать сведения о задаче
   • task cancel taskID - снять задачу
   • task requeue taskID - заново поставить задачу в очередь

К операциям администратора относится команда cluscfg:

• cluscfg view - выдать сведения о кластере
• cluscfg listparams/setparams - просмотреть/установить конфигурационные параметры
• cluscfg listenvs/setenv - просмотреть/установить параметры окружения
• cluscfg delcreds/setcreds - удалить / установить полномочия пользователя

Интерфейс на основе передачи сообщений (MPI - Message Passing Interface) является стандартной моделью программирования для разработки приложений с явным параллелизмом (т.е., параллельные части программы определяет программист), в которых параллельные процессы взаимодействуют между собой путем передачи сообщений.

Для различных операционных систем и разнообразных сетей передачи данных, используемых в кластерах, разработаны и продолжают разрабатываться специальные реализации MPI. MS MPI (Microsoft MPI) есть стандартная реализация интерфейса передачи сообщений для операционной системы Windows. MS MPI, в свою очередь, базируется на MPICH2 - открытой (open source) реализации стандарта MPI 2.0, разработка которой первоначально была начата в Аргонской национальной лаборатории (Argonne National Laboratory), США.

MS MPI может использоваться в программах, написанных на языках Fortan-77, Fortran-90, C и C++. Пакет Compute Cluster Pack не предоставляет библиотеки классов для MPI в рамках .NET Framework. Тем не менее, программы, реализуемые как последовательные задачи для исполнения под управлением CCS, могут разрабатываться на языках, поддерживаемых платформой .NET. С другой стороны, программы, использующие MPI и написанные на языках, поддерживаемых .NET, могут обращаться к MPI-функциям посредством механизма P/Invoke. В будущих версиях CCS ожидается поддержка MPI в виде стандартных классов .NET Framework.

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

Стандарт MPI-1 включает в себя следующие базовые функции:

1. управление вычислительным окружением,
2. передача сообщений типа "точка-точка",
3. коллективные операции взаимодействия,
4. использование производных типов данных,
5. управление группами и коммуникаторами,
6. виртуальные топологии.

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

Стандарт MPI-2, помимо функциональности стандарта MPI-1, включает в себя функции:

1. динамического порождения процессов,
2. однонаправленной передачи сообщений,
3. расширенных коллективных операций,
4. параллельного ввода/вывода.

Кроме реализаций MPICH и MPICH-2 Аргонской национальной лаборатории, на которых базируется MS MPI, имеется еще множество других реализаций стандарта MPI, как коммерческих, так и свободно доступных. Примером коммерческой версии является система ScaMPI фирмы Scali, ориентированная, в частности, на поддержку быстрого интерконнекта SCI. Примером широко используемой свободно доступной реализации является система LAM MPI, разработанная в Суперкомпьютерном центре штата Огайо, США.

В последующих разделах будут изложены основные функции стандарта MPI-1 и способы их применения, а также будут даны сведения об отладке MPI-программ c использованием Visual Studio 2005.

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

Наиболее часто используемые функции (в формате языка С) перечисляются ниже.

1. MPI_Init

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

   Формат вызова:

   MPI_Init ( &argc, &argv)

2. MPI_Initialized

   Эта функция определяет вызывалась ли функция инициализации MPI_Init, и возвращает флаг в виде логической истины (1) или логической лжи(0). Необходимость этой функции обусловлена тем, что в сложных программах разные модули могут требовать использования MPI и, так как функция MPI_Init может быть вызвана один раз и только раз каждым процессом, то указанная функция помогает модулю решить нужно ли вызывать MPI_Init или же окружение MPI уже было проинициализировано другим модулем.

   Формат вызова:

   MPI_Initialized ( &flag )

3. MPI_Finalize

   Эта функция завершает работу вычислительного окружения MPI. Вызов этой функции должен быть последним обращением к какой-либо MPI-функции в программе: после нее никакая другая MPI-функция вызвана быть не может.

   Формат вызова:

   MPI_Finalize()

4. MPI_Comm_size

   Все параллельные процессы, из которых состоит MPI-программа, объединяются в группы, которые управляются так называемыми коммуникаторами (communicators). Именно коммуникаторы обеспечивают взаимодействие параллельных процессов внутри группы.

   Функция MPI_Comm_size определяет количество процессов в группе, связанной с данным коммуникатором. Специальный встроенный коммуникатор с именем MPI_COMM_WORLD управляет всеми MPI-процессами в приложении, и потому чаще всего используется в качестве аргумента в данной функции:

   
   
   
   

   Формат вызова:

   MPI_Comm_size ( comm., &size )

5. MPI_Comm-rank

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

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

   Формат вызова:

   MPI_Comm-rank ( comm., &rank )

   
   
   
   

Операции передачи данных в MPI типа "точка-точка" представляют собой передачу сообщений между, в точности, двумя MPI-процессами. Один процесс, при этом, выполняет команду Send (послать), тогда как другой процесс выполняет команду Receive (принять).

Выполнение команд Send и Receive осуществляется посредством вызова соответствующих MPI-функций, которые имеют различные типы, или, другими словами, различное назначение:

• Блокирующий Send / блокирующий Receive
• Неблокирующий Send / неблокирующий Receive
• Синхронный Send
• Буферированный Send
• Комбинированный Send / Receive
• Send по готовности ( "ready" Send ).

С любым типом операции Send может состоять в паре любой тип операции Receive.

Функции передачи данных типа "точка-точка" имеют список аргументов одного из следующих форматов:

• Блокирующий Send:

  MPI_Send ( buffer, count, type, dest, tag, comm )

• Неблокирующий Send:

  MPI_Isend ( buffer, count, type, dest, tag, comm, request )

• Блокирующий Receive:

  MPI_Recv ( buffer, count, type, source, tag, comm., status )

• Неблокирующий Receive:

  MPI_Irecv ( buffer, count, type, source, tag, comm., request )

Аргументы в этих функциях имеют следующее назначение:

1. buffer - место хранения данных, которые посылаются или принимаются;
2. count - количество элементов данных конкретного типа, которые посылаются или принимаются;
3. type - тип элементарных данных, задаваемый через встроенные MPI-типы, такие как (для языка С): MPI_CHAR, MPI_SHORT, MPI_INT, MPI_LONG, MPI_FLOAT, MPI_DOUBLE, MPI_BYTE, MPI_PACKED и др.
4. dest - указывает процесс, которому должно быть доставлено сообщение - задается через ранг принимающего процесса;
5. source - аргумент функций приема сообщений, указывающий номер посылающего процесса; указание значения MPI_ANY_SOURCE означает прием сообщения от любого процесса;
6. tag - произвольное неотрицательное целое число, присваиваемое программистом для однозначной идентификации сообщения; у парных операций Send и Reсeive эти числа должны совпадать; указание у операции Receive значения MPI_ANY_TAG может быть использовано для приема любого сообщения, независимо от значения tag ;
7. comm - указывает на коммуникатор, в рамках которого трактуются значения аргументов dest и source ; чаще всего используется встроенный коммуникатор MPI_COMM_WORLD ;
8. status - для операции Receive, указывает источник (source) сообщения и его тег ( tag ); в языке С, этот аргумент есть указатель на встроенную структуру MPI_Status ; из этой же структуры может быть получено количество принятых байт посредством функции MPI_Get_count ;
9. request - используется в неблокирующих операциях Send и Receive, и задает уникальный "номер запроса"; в языке С, этот аргумент является указателем на встроенную структуру MPI_Request.

К наиболее часто используемым блокирующим функциям передачи сообщений относятся следующие функции:

MPI_Send

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

Формат вызова:

MPI_Send ( &buf, count, datatype, dest, tag, comm. )

MPI_Recv

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

Формат вызова:

MPI_Recv ( &buf, count, datatype, source, tag, comm, &status )

MPI_Ssend

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

Формат вызова:

MPI_Ssend ( &buf, count, datatype, dest, tag, comm )

MPI_Bsend, MPI_Buffer_attach

Перед вызовом MPI_BSend, программист должен вызвать функцию MPI_Buffer_attach для размещения буфера, используемого в MPI_Bsend. Буферированная блокирующая операция посылки сообщения заканчивает свою работу, когда данные из программного буфера скопированы в буфер посылки.

Форматы вызовов:

MPI_Buffer_attach ( &buffer, size )
MPI_Bsend ( &buf, count, datatype, dest, tag, comm )

В нижеследующем примере, процесс 0 посылает однобайтовое сообщение процессу 1, и ждет от него аналогичного сообщения.

Основные особенности и отличия радиовещательных (коллективных) обменов данными от обменов типа "точка-точка" состоят в следующем:

1. принимают и/или передают данные одновременно все процессы группы для указываемого коммуникатора;
2. радиовещательная (коллективная) функция выполняет одновременно и прием, и передачу данных, а потому она имеет параметры, часть из которых относится к приему, а часть - к передаче данных;
3. как правило, значения всех параметров (за исключением адресов буферов) должны быть идентичны во всех процессах;
4. коллективные операции являются блокирующими;
5. коллективные операции могут использоваться только для встроенных (predefined) MPI-типов данных, но не могут использоваться для производных (derived) MPI-типов данных.

MPI_Bcast

Посылает сообщение от процесса с рангом "root" (обычно, это процесс с рангом 0) всем другим процессам в группе.

Формат вызова:

MPI_Bcast ( &buffer, count, datatype, root, comm )

MPI_Gather

Собирает сообщения от каждого из процессов в группе в приемный буфер процесса с рангом 'root".

Формат вызова:

MPI_Gather ( &sendbuf, sendcount, sendtype, &recvbuf, recvcount,
             recvtype, root, comm )

Cледует заметить, что

• sendtype и recvtype, в общем случае, могут различаться, а потому будут задавать разную интерпретацию данных на приемной и передающей стороне;
• процесс root также отправляет данные, но в свой же приемный буфер.

MPI_Scatter

Эта функция является обратной к функции MPI_Gather: отдельные части передающего буфера процесса с рангом 'root& распределяются по приемным буферам всех других процессов в группе.

Формат вызова:

MPI_Scatter ( &sendbuf, sendcount, sendtype, &recvbuf, recvcount,
              recvtype, root, comm )

MPI_Allgather

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

Формат вызова:

MPI_Allgather ( &sendbuf, sendcount, sendtype, &recvbuf, recvcount,
                recvtype, comm )

MPI_Alltoall

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

Формат вызова:

MPI_Alltoall ( &sendbuf, sendcount, sendtype, &recvbuf, recvcount, 
               recvtype, comm )

В нижеследующем примере, с помощью функции MPI_Scatter строки массива рассылаются отдельным процессам:

Вывод на консоль данной программы будет таким:

rank= 0  Results: 1.000000 2.000000 3.000000 4.000000
rank= 1  Results: 5.000000 6.000000 7.000000 8.000000
rank= 2  Results: 9.000000 10.000000 11.000000 12.000000
rank= 3  Results: 13.000000 14.000000 15.000000 16.000000

Коллективные операции в MPI выполняют следующие функции:

• MPI_Reduce,
• MPI_Allreduce,
• MPI_Reduce_scatter и
• MPI_Scan.

Помимо встроенных, пользователь может определять использовать свои собственные коллективные операции. Для этого служат функции MPI_Op_create и MPI_Op_free, а также специальный тип данных MPI_Usr_function.

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

MPI_Reduce

Данная функция выполняет коллективную операцию во всех процессах группы и помещает результат в процесс с рангом root.

Формат вызова:

MPI_Reduce ( &sendbuf, &recvbuf, count, datatype, op, root, comm )

Пример поэлементного суммирования массивов:

Встроенных коллективных операций в MPI насчитывается 12:

• MPI_MAX и MPI_MIN - поэлементные максимум и минимум
• MPI_SUM - сумма векторов
• MPI_PROD - произведение векторов
• MPI_LAND, MPI_BAND, MPI_LOR, MPI_BOR, MPI_LXOR, MPI_BXOR - логические и двоичные (бинарные) операции И, ИЛИ, исключающее ИЛИ
• MPI_MAXLOC, MPI_MINLOC - поиск индекса процесса с максимумом/минимумом значения и самого этого значения

Эти функции могут работать только со следующими типами данных (и только ними):

• MPI_MAX, MPI_MIN - целые и вещественные
• MPI_SUM, MPI_PROD - целые, вещественные (комплексные - для Фортрана)
• MPI_LAND, MPI_LOR, MPI_LXOR - целые
• MPI_BAND, MPI_BOR, MPI_BXOR - целые и типа MPI_BYTE
• MPI_MAXLOC, MPI_MINLOC - вещественные

MPI_Allreduce

Применяет коллективную операцию и рассылает результат всем процессам в группе.

Формат вызова:

MPI_Allreduce (&sendbuf, &recvbuf, count, datatype, op, comm)

MPI_Reduce_scatter

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

Формат вызова:

MPI_Reduce_scatter (&sendbuf, &recvbuf, recvcount, datatype, op, comm)

MPI_Scan

Данная операция аналогична функции MPI_Allreduce в том отношении, что после ее выполнения каждый процесс получает результирующий массив. Главное отличие данной функции состоит в том, что содержимое результирующего массива в процессе i является результатом выполнения коллективной операции над массивами из процессов с номерами от 0 до i включительно.

Формат вызова:

MPI_Scan ( &sendbuf, &recvbuf, count, datatype, op, comm )

Управление процессами в MPI происходит посредством организации их в группы, управляемые коммуникаторами

Группа есть упорядоченное множество процессов. Каждому процессу в группе присваивается уникальный целочисленный номер - ранг. Значения ранга изменяются от 0 до N - 1, где N есть количество процессов в группе. В MPI, группа представляется в памяти компьютера в виде объекта, доступ к которому программист осуществляет с помощью "обработчика" (handle) MPI_Group. С группой всегда связывается коммуникатор, также представляемый в виде объекта.

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

Основные цели средств организации процессов в группы:

1. позволяют организовывать задачи, объединяя в группы процессы, основываясь на их функциональном назначении;
2. позволяют осуществлять коллективные операции (см. Раздел 4) только на заданном множестве процессов;
3. предоставляют базис для организации пользователем виртуальных топологий;
4. обеспечивают безопасную передачу сообщений в рамках одной группы.

Группы/коммуникаторы являются динамическими - они могут создаваться и уничтожаться во время исполнения программы.

Процессы могут относиться к более, чем одной группе/коммуникатору. В каждой группе/коммуникаторе, каждый процесс имеет уникальный номер (ранг).

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

1. Получить обработчик глобальной группы, связанной с коммуникатором MPI_COMM_WORLD, используя функцию MPI_Comm_group.
2. Создать новую группу как подмножество глобальной группы, используя функцию MPI_Group_incl.
3. Создать новый коммуникатор для вновь созданной группы, используя функцию MPI_Comm_create.
4. Получить новый ранг процесса во вновь созданном коммуникаторе, используя функцию MPI_Comm_rank.
5. Выполнить обмен сообщениями между процессами в рамках вновь созданной группы.
6. По окончании работы, освободить (уничтожить) группу и коммуникатор, используя функции MPI_Group_free и MPPI_Comm_free.

Пример, показанный ниже, демонстрирует создание двух отдельных групп процессов для выполнения коллективных операций внутри каждой из них.

Вывод программы на консоль будет таким:

rank= 7 newrank= 3 recvbuf= 22
rank= 0 newrank= 0 recvbuf= 6
rank= 1 newrank= 1 recvbuf= 6
rank= 2 newrank= 2 recvbuf= 6
rank= 6 newrank= 2 recvbuf= 22
rank= 3 newrank= 3 recvbuf= 6
rank= 4 newrank= 0 recvbuf= 22
rank= 5 newrank= 1 recvbuf= 22

В терминах MPI, виртуальная топология описывает отображение MPI процессов на некоторую геометрическую конфигурацию процессоров.

В MPI поддерживается два основных типа топологий - декартовые (решеточные) топологии и топологии в виде графа.

MPI-топологии являются виртуальными - связь между физической структурой параллельной машины и топологией MPI-процессов может и отсутствовать.

Виртуальные топологии строятся на основе групп и коммуникаторов, и "программируется" разработчиком параллельного приложения.

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

В примере, показанном ниже, создается декартова топология 4 х 4 из 16 процессов, и каждый процесс сообщает свой ранг своим соседям, получая от них их собственные ранги.

Вывод данной программы на консоль будет следующим:

rank= 0 coords= 0 0  neighbors(u,d,l,r)= -3 4 -3 1
rank= 0                inbuf(u,d,l,r)= -3 4 -3 1
rank= 1 coords= 0 1  neighbors(u,d,l,r)= -3 5 0 2
rank= 1                inbuf(u,d,l,r)= -3 5 0 2
rank= 2 coords= 0 2  neighbors(u,d,l,r)= -3 6 1 3
rank= 2                inbuf(u,d,l,r)= -3 6 1 3
        . . . . .
rank= 14 coords= 3 2  neighbors(u,d,l,r)= 10 -3 13 15
rank= 14                inbuf(u,d,l,r)= 10 -3 13 15
rank= 15 coords= 3 3  neighbors(u,d,l,r)= 11 -3 14 -3
rank= 15                inbuf(u,d,l,r)= 11 -3 14 -3

Visual Studio 2005 включает в себя важные функции, которые позволяют отлаживать параллельные приложения в удаленном режиме.

MPI-отладчик из Visual Studio использует файл Mpishim.exe для автоматического присоединения отладочных средств к MPI-процессам, исполняющимся на узлах кластера. Совокупность стандартных средств отладки, уже имевшееся в составе Visual Studio 2005, расширено на параллельные приложения, и обеспечивает точки останова и пошаговое выполнение на уровне процессов и на уровне потоков. С помощью этих средств, возможно отладить приложения, в которых имеются несоответствия в передаче и приеме сообщений, дедлоки и условия для возникновения гонок.

Visual Studio 2005 Professional Edition и Visual Studio 2005 Team System позволяют отлаживать приложения, включая и параллельные приложения, в удаленном режиме. При отладке MPI-приложений в рамках Visual Studio используются следующие средства:

1. Msvsmon - монитор удаленной отладки
2. Smpd - процесс-демон, который запускает приложение Mpishim.exe
3. Mpishim - приложение, которое связывается с Msvsmon и запускает процедуру Mpiexeс.
4. Mpiexec - процедура запуска приложения пользователя в виде MPI-задания.

Общие шаги по установке и конфигурированию средств отладки MPI приложений в рамках Visual Studio состоят в следующем:

1. Установить и сконфигурировать MS MPI на каждом узле кластера. MS MPI включен в пакет Windows Compute Cluster Server 2003, но поддерживаются и другие версии MPI.
2. Установить Mpishim.exe на каждом узле кластера в одной и той же директории на каждом из узлов. Например, можно поместить Mpishim.exe в директорию C:\Windows\system32 на каждом узле кластера.
3. Установить монитор удаленной отладки (Msvsmon.exe) на каждом узле кластера.
4. Установить на компьютере, с которого будет производиться удаленная отладка, достаточные привилегии для запуска заданий на кластере. Этот компьютер должен находиться в таком сегменте сети и в такой подсети, чтобы с него был возможен доступ к вычислительным узлам кластера.

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

1. Вставить в дисковод последний из установочных дисков Visual Studio 2005.
2. Отыскать на нем директорию Remote Debugger\x64.
3. Запустить из нее файл rdbgsetup.exe для установки компонент для удаленной отладки.

Дополнительные замечания:

1. При большом количестве узлов на вычислительном кластере, рекомендуется скопировать содержимое папки Remote Debugger\x64 на диск, доступный всем узлам, и запускать процедуру установки оттуда.
2. Пользователь, задействованный в сессии отладки MPI-приложений в Visual Studio 2005, должен также быть пользователем, запустившим Msvsmon.exe на удаленных машинах, поскольку Visual Studio проверяет, чтобы пользователь, выполняющий отладку, и пользователь, запустивший процессы на удаленных компьютерах, совпадали.

Visual Studio 2005 имеет средства, которые делают ее эффективным инструментом отладки MPI-приложений. Пользователь может выполнять MPI-приложения непосредственно в рамках сессии из Visual Studio в двух режимах:

• (1) в режиме симуляции на одной машине (задавая количество виртуальных процессоров, которые будет использовать MPI-приложение),
• (2) в режиме непосредственного запуска приложения на вычислительном кластере.

При задании точек остановки (breakpoints) в приложении, пользователь может указать применение этих точек

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

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

1. Открыть в Visual Studio решение, которое содержит требуемое MPI приложение.
2. На странице Properties проекта, раскрыть подраздел Configuration Properties, выбрать Debugging, и затем в списке Debugger to launch, выбрать MPI Cluster Debugger, как показано на Рис 2.1.
   
   
   
   увеличить изображение
   
   Рис. 2.1.  Отладка MPI-приложения с использованием Visual Studio

3. Заполнить соответствующими аргументами поля, как показано на Рис 2.1. Те же самые аргументы используются и в обычном MPI-задании, за исключением файла Mpishim.exe, который необходим для взаимодействия отладчика с MPI-сервисом.
4. Проверить, что значение поля Application Command содержит значение, которое верно для каждого из узлов кластера. Легче всего это обеспечить, если указанный путь относится к общей директории для всех узлов.
5. В главном меню Visual Studio 2005, выберите пункт Tools, а в нем - подпункт Options для раскрытия диалогового окна, показанного на Рис 2.2.
   
   
   
   Рис. 2.2.  Диалоговое окно Options

6. Установить необходимые точки остановки, и заново запустить процесс Build повторного построения изображения.

Замечание.

Важное свойство отладки параллельных приложений в Visual Studio 2005 состоит в том, что в ней возможно устанавливать точки остановки отдельно для каждого процесса. Например, можно установить точку остановки только для процесса с конкретным Windows Process ID (PID) или же для множества процессов с выбранными PID.

После того, как для приложения установлены конфигурационные параметры в Visual Studio, запустить приложение в режиме отладки можно, нажав клавишу F5. В результате этого, приложение запустится с использованием mpiexec, а отладчик из Visual Studio будет запущен на узлах, где исполняются процессы приложения. Когда процесс приложения на некотором узле достигнет точки остановки, то его выполнение прервется.

Чтобы просмотреть процессы приложения, необходимо нажать Ctrl-Alt-Z, чтобы открыть окно Processes, пример которого показан на Рис 2.3.

Отметим, что в поле ID этого окна отображается Windows Process ID (PID), а не ранг процесса в смысле MPI.

Как уже говорилось выше, установка фильтров для точек остановки позволяет иметь активные точки остановки только для некоторых процессов.

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

Замечание.

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

Язык параллельного программирования MC# предназначен для написания программ, работающих на всём спектре параллельных архитектур - от многоядерных процессоров до Grid-сетей. Единственное требование к таким системам со стороны MC# - на них должна быть установлена среда исполнения CLR (Common Language Runtime) с соответствующим набором библиотек. На машинах с операционной системой Windows реализацией такой среды является Microsoft .NET Framework, а на машинах с операционной системой Linux - система Mono (http://www.mono-project.com), которая является свободной реализацией платформы .NET для Unix-подобных систем.

Язык MC# является адаптацией и развитием базовых идей языка Polyphonic C# на случай параллельных и распределенных вычислений. Язык Polyphonic C# был разработан в 2002г. в Microsoft Research Laboratory (г. Кембридж, Великобритания) Н. Бентоном (N. Benton), Л. Карделли (L. Cardelli) и Ц. Фурнье (C. Fournet). Целью его создания было добавление высокоуровневых средств асинхронного параллельного программирования в язык C# для использования в серверных и клиент-серверных приложениях на базе Microsoft .NET Framework.

Ключевая особенность языка Polyphonic C# заключается в добавлении к обычным, синхронным методам, так называемых "асинхронных" методов, которые предназначены играть в (многопоточных) программах две основные роли:

1. автономных методов, предназначенных для выполнения базовой вычислительной работы, и исполняемых в отдельных потоках, и
2. методов, предназначенных для доставки данных (сигналов) обычным, синхронным методам.

Для синхронизации нескольких асинхронных методов, а также асинхронных и синхронных методов, в язык C#, кроме того, были введены новые конструкции, получившие название связок (chords).

При этом исполнение Polyphonic C#-программ, по замыслу авторов этого языка, по-прежнему, предполагалось либо на одной машине, либо на нескольких машинах, с зафиксированными на них асинхронными методами, взаимодействующими между собой с использованием средств удаленного вызова методов (RMI - Remote Method Invocation), предоставляемых библиотекой System.Runtime.Remoting платформы .NET.

В случае языка MC#, программист может предусмотреть исполнение автономных асинхронных методов либо локально, либо удаленно. В последнем случае, метод может быть спланирован для исполнения на другой машине, выбираемой двумя способами: либо согласно явному указанию программиста (что не является типичным случаем), либо автоматически (обычно, на наименее загруженном узле кластера или машине Grid-сети). Взаимодействие асинхронных методов, в рамках языка MC#, реализуется посредством передачи сообщений с использованием каналов и обработчиков канальных сообщений. Эти каналы и обработчики определяются в MC#-программах с помощью связок в стиле языка Polyphonic C#.

Таким образом, написание параллельной, распределенной программы на языке MC# сводится к выделению с помощью специального ключевого слова async методов, которые должны быть исполнены асинхронно локально (в виде отдельных потоков), а также с помощью ключевого слова movable тех методов, которые могут быть перенесены для исполнения на другие машины.

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

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

Разделение всех методов в программе на обычные (синхронные) и асинхронные (в том числе, на те, которые могут быть перенесены для исполнения на другие машины) производится программистом с использованием специальных ключевых слов async и movable. (В языке MC#, семантика и использование ключевого слова async полностью совпадает с использованием этого слова в языке Polyphonic C# за тем исключением, что в MC# async-методы не могут встречаться в связках - см. об этом ниже).

Async- и movable-методы являются единственным средством создания параллельных процессов (потоков) в языке MC#.

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

• для обеспечения взаимодействия параллельных процессов между собой,
• для их синхронизации.

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

Для синхронизации параллельных процессов в MC# используются связки (chords), определяемые в стиле языка Polyphonic C#.

Общий синтаксис определения async- и movable-методов в языке MC# следующий:

модификаторы { async | movable } имя_метода ( аргументы )
{
   < тело метода >
}

Ключевые слова async и movable располагаются на месте типа возвращаемого значения, поэтому синтаксическое правило его задания при объявлении метода в языке MC# имеет вид:

return-type ::= type | void | async | movable

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

Отличия async- и movable-методов от обычных методов состоят в следующем:

• вызов async- и movable-методов заканчивается, по существу, мгновенно (для последних из названных методов, время затрачивается только на передачу необходимых для вызова этого метода данных на удаленную машину),
• эти методы никогда не возвращают результаты (о взаимодействии movable-методов между собой и с другими частями программы, см. Раздел 2.2 "Каналы и обработчики").

Соответственно, согласно правилам корректного определения async- и movable-методов:

• они не могут объявляться статическими,
• в их теле не может использоваться оператор return.

Вызов movable-метода имеет две синтаксические формы:

1. имя_объекта.имя_метода ( аргументы )

   (место исполнения метода выбирается Runtime-системой автоматически),

2. имя_машины@имя_объекта.имя_метода ( аргументы )

   ( имя_машины задает явным образом место исполнения данного метода).

При разработке распределенной программы на языке MC# (т.е., при использовании в ней movable-методов и исполнении её на кластере или в Grid-сети), необходимо учитывать следующие особенности системы исполнения (Runtime-системы) MC#-программ.

Во-первых, объекты, создаваемые во время исполнения MC#-программы, являются, по своей природе статическими: после своего создания, они не перемещаются и остаются привязанными к тому месту (машине), где они были созданы. В частности, именно в этом месте (на этой машине) они регистрируются Runtime-системой, что необходимо для доставки канальных сообщений этим объектам и чтения сообщений с помощью обработчиков, связанных с ними (этими объектами).

Поэтому, первой ключевой особенностью языка MC# (а точнее, его семантики) является то, что, в общем случае, во время вызова movable-метода, все необходимые данные, а именно:

1. сам объект, которому принадлежит данный movable-метод, и
2. его аргументы (как ссылочные, так и скалярные значения) только копируются (но не перемещаются) на удаленную машину. Следствием этого является то, что все изменения, которые осуществляет (прямо или косвенно) movable-метод с внутренними полями объекта, проводятся с полями объекта-копии на удаленной машине, и никак не влияют на значение полей исходного объекта.

Если копируемый (при вызове его movable-метода) объект обладает каналами или обработчиками (или же просто, они являются аргументами этого movable-метода), то они также копируются на удаленную машину. Однако, в этом случае, они становятся "прокси"-объектами для исходных каналов и обработчиков.

Каналы и обработчики канальных сообщений являются средствами для организации взаимодействия параллельных распределенных процессов между собой. Синтаксически, каналы и обработчики обычно объявляются в программе с помощью специальных конструкций - связок (chords).

В общем случае, синтаксические правила определения связок в языке MC# имеют вид:

chord-declaration ::= [handler-header] [ & channel-header ]* body
handler-header ::= attributes modifiers handler handler-name
                   return-type ( formal-parameters )
channel-header ::= attributes modifiers channel channel-name
                  ( formal-parameters )

Связки определяются в виде членов класса. По правилам корректного определения, каналы и обработчики не могут иметь модификатора static, а потому они всегда привязаны к некоторому объекту класса, в рамках которого они объявлены.

Обработчик используется для приема значений (возможно, предобработанного с помощью кода, являющегося телом связки) из канала (или группы каналов), совместно определенных с этим обработчиком. Если, к моменту вызова обработчика, связанный с ним канал пуст (т.е., по этому каналу значений не поступало или они все были выбраны посредством предыдущих обращений к обработчику), то этот вызов блокируется. Когда по каналу приходит очередное значение, то происходит исполнение тела связки (которое может состоять из произвольных вычислений) и по оператору return происходит возврат результирующего значения обработчику.

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

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

Вторая ключевая особенность языка MC# состоит в том, что каналы и обработчики могут передаваться в качестве аргументов методам (в том числе, async- и movable-методам) отдельно от объектов, которым они принадлежат (в этом смысле, они похожи на указатели на функции в языке С, или, в терминах языка C#, на делегатов ( delegates ) ).

Третья ключевая особенность языка MC# состоит в том, что, в распределенном режиме, при копировании каналов и обработчиков на удаленную машину (под которой понимается узел кластера или некоторая машина в Grid-сети) автономно или в составе некоторого объекта, они становятся прокси-объектами, или посредниками для оригинальных каналов и обработчиков. Такая подмена скрыта от программиста - он может использовать переданные каналы и обработчики (а, в действительности, их прокси-объекты) на удаленной машине (т.е., внутри movable-методов) также, как и оригинальные: как обычно, все действия с прокси-объектами перенаправляются Runtime-системой на исходные каналы и обработчики. В этом отношении, каналы и обработчики отличаются от обычных объектов: манипуляции над последними на удаленной машине не переносятся на исходные объекты (см. первую ключевую особенность языка MC#).

Аналогично языку Polyphonic C#, в одной связке можно определить несколько каналов. Такого вида связки являются главным средством синхронизации параллельных (в том числе, распределенных) потоков в языке MC#:

Таким образом, общее правило срабатывания связки состоит в следующем: тело связки исполняется только после того, как вызваны все методы из заголовка этой связки.

При использовании связок в языке MC# нужно руководствоваться следующими правилами их корректного определения:

1. Формальные параметры каналов и обработчиков не могут содержать модификаторов ref или out.
2. Если в связке объявлен обработчик с типом возвращаемого значения return-type, то в теле связки должны использоваться операторы return только с выражениями, имеющими тип return-type.
3. Все формальные параметры каналов и обработчика в связке должны иметь различные идентификаторы.
4. Каналы и обработчики в связке не могут быть объявлены как static.

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

Если структура данных задачи организована в виде дерева, то его обработку легко распараллелить путем обработки каждого поддерева отдельном async- ( movable- ) методом.

Предположим, что мы имеем следующее определение (в действительности, сбалансированного) бинарного дерева в виде класса BinTree:

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

Следует также отметить, что в случае распределенного варианта этой программы, при вызове movable -метода Sum, к объекту класса BinTree, являющемуся аргументом этого метода, будут применяться процедуры сериализации/десериализации при переносе вычислений на другой компьютер. (В действительности, с точки зрения Runtime-языка MC#, поддерживающей распрердЄZQVрдЄZQVЂvZQV0‹ўZQVXеЄZQVеЄZQV@еЄZQVуры сериализации/десериализации).

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

Рассмотрим задачу вычисления частичных сумм массива f длины n.

А именно, по заданному массиву чисел f [ 0 : n-1 ] необходимо построить массив h [ 0 : n-1 ], такой что

Идея параллельного решения этой задачи состоит в разбиении массива f на p сегментов, где n кратно p, с дальнейшей одновременной обработкой этих сегментов данных длины m = n div p. Таким образом, обработка каждого сегмента будет производиться movable -методом.

(Отметим, что приведенное ниже решение пригодно и для случая, когда n не кратно p. Соответствующее обобщение может рассматриваться в качестве упражнения).

Разбиение исходного массива f на p сегментов производится таким образом, что в сегмент q, где ( 0 <= q < p ) попадают элементы f [ i ], такие что i mod p = q.

Так, например, если n = 16 и p = 4, то

0 -ой сегмент составят числа f [ 0 ], f [ 4 ], f [ 8 ], f [ 12 ] ;

1 -ый сегмент составят числа f [ 1 ], f [ 5 ], f [ 9 ], f [ 13 ]

и т.д.

Параллельный алгоритм вычисления частичных сумм будет устроен так, что q -му процессу ( movable -методу), обрабатывающему q -ый сегмент данных, достаточно будет общаться лишь с его соседями слева и справа (соответственно, 0 -му процессу - лишь с соседом справа, а последнему, (p-1) -му процессу - лишь с соседом слева) и главной программой для возврата результатов. Процесс с номером q будет вычислять все элементы h [j] результирующего массива, такие что j mod p = q, где 0 <= j < n.

Фрагмент главной программы, разбивающей исходный массив на сегменты и вызывающий movable -метод handleSegment, показан ниже. Здесь первым аргументом этого метода является номер сегмента, а последним - имя канала для возврата результатов.

Объекты класса BDChannel объявляются следующим образом :

Схема взаимодействия процессов (movable-методов) между собой и главной программой показана ниже:

После разбиения, исходный массив f приобретает вид двумерной матрицы, распределенной по p процессам:

Другими словами, эта матрица получена из массива f разрезанием его на p сегментов и транспонированием каждого сегмента.

Ключевая идея алгоритма отдельного процесса q состоит в заполнении локальных для него массивов h0 и h1 (оба, имеющие размерность m ) в соответствии с формулами:

Неформально, это означает, что для процесса с номером q i -ый элемент массива h0 есть сумма всех элементов приведенной выше матрицы, которые расположены выше и слева элемента a_q,i (включая и элементы столбца i ).

Аналогично, i -ый элемент массива h1 есть сумма всех элементов матрицы, которые расположены ниже и слева элемента a_q,i (но, не включая элементов из столбца i ).

Ниже показана иллюстрация этого принципа для n = 16, p = 4 и q = 1, i = 2.

После того, как вычислены массивы h0 и h1 (посредством взаимодействия с соседними процессами), процесс с номером q может вычислить элемент h[i * p + q] результирующего массива как

Получаемые результирующие m значений процесс q сохраняет в локальном массиве h для передачи их главной программе. Тогда общая схема movable -метода handleSegment выглядит следующим образом:

Фрагмент программы, вычисляющий массив h0, приведен ниже.

Как обычно, для любого параллельного языка программирования, реализация MC# состоит из компилятора и рантайм-системы. Главными функциональными частями рантайм-системы являются:

1. ResourceManager - процесс, исполняющийся на центральном узле и распределяющий по узлам movable-методы.
2. WorkNode - процесс, исполняющийся на каждом из рабочих узлов и контролирующий выполнение movable-методов.
3. Communicator - процесс, исполняющийся на каждом из узлов и ответственный за принятие сообщений для объектов, расположенных на данном узле.

Компилятор переводит программу из MC# в C#, его главной целью является создание кода, реализующего:

1. выполнение movable-методов на других процессорах,
2. пересылку канальных сообщений и
3. синхронизацию методов, объединённых связкой.

Эти функции предоставляются соответствующими методами классов рантайм-системы. Среди них:

1. класс Session - реализует вычислительную сессию.
2. класс TCP - предоставляет возможность доставки запросов на исполнение movable-методов и канальных сообщений.
3. класс Serialization - предоставляет сериализацию/десериализацию объектов, перемещаемых на другие рабочие узлы.
4. класс Channel - содержит информацию о канале.
5. класс Handler - содержит информацию об обработчике.

Главные функции компилятора MC#:

1. Добавление вызовов функций Init() и Finalize() класса Session в главном методе программы. Функция Init() доставляет исполняемый модуль программы на другие узлы, запускает процесс Manager, создаёт объекты LocalNode и другие. Функция Finalize() останавливает запущенные потоки и завершает вычислительную сессию.
2. Добавление выражений, создающих объекты типа сhannel и handler для каждого из каналов и обработчиков, описанных в программе.
3. Замена вызовов async-методов на порождение соответствующих локальных потоков.
4. Замена вызовов movable-методов на запросы менеджеру распределения ресурсов.
5. Замена канальных вызовов на пересылку соответствующих сообщений по TCP-соединению. Трансляция связок, содержащих определения каналов, производится так же, как и в языке Polyphonic C#.

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

Доступные на настоящий момент программные интерфейсы и библиотеки для организации параллельных вычислений, такие как OpenMP (http://www.openmp.org) (для систем с общей (shared) памятью) и MPI (Message Passing Interface, http://www.mcs.anl.gov/mpi) (для систем на основе передачи сообщений), ориентировны, в основном, на языки C и Fortran, а потому являются очень низкоуровневыми и неадекватными современным языкам объектно-ориентированного программирования, таким как C++, C# и Java. В частности, одной из причин низкоуровневости этих средств является то, что они опираются либо на вызовы библиотечных функций, либо на аналоги таких функций - препроцессорные директивы, а не на соответствующие, "родные" конструкции языков программирования.

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

1. базовых конструкций языка как таковых, и
2. совокупности специализированных библиотек, доступных через соответствующие API (Application Programming Interfaces).

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

Одним из последних достижений в этом направлении является введение модели асинхронного параллельного программирования в рамках языка Polyphonic C# на основе платформы .NET фирмы Microsoft [1]. В свою очередь, эта модель базируется на так называемом join-исчислении [2] - математическом исчислении процессов с высокоуровневым механизмом обработки сообщений, адекватно абстрагирующим соответствующий низкоуровневый механизм (на основе IP-адресов, портов и сокетов), который используется в современных компьютерных системах.

Введение новых конструкций для параллельного программирования - асинхронных методов и связок (chords) в язык Polyphonic C#, который является расширением языка C#, позволяет обойтись без библиотеки System.Threading, которая обычно требуется для реализации мультипоточных приложений в рамках .NET. С другой стороны, введение новых конструкторов типов данных (потоков (streams), анонимных структур, разделенных объединений (discriminated unions) и др.) вместе с соответствующими средствами определения запросов в язык C? [3] (которые, вначале, вошли в проект Linq, http://msdn2.microsoft.com/en-us/netframework/aa904594.aspx, а затем стали частью спецификации языка C# 3.0, http://msdn2.microsoft.com/en-us/vcsharp/aa336745.aspx ) делает ненужной подсистему для работы с данными ADO.NET (а именно, традиционные библиотеки System.Data и System.XML, предназначенные для работы с реляционными и слабоструктурированными данными).

Мы предлагаем сделать следующий шаг в этом направлении - ввести в объектно-ориентированный язык высокоуровневые конструкции для создания параллельных и распределенных программ, и, тем самым, освободить программиста от необходимости использования библиотек System.Threading и System.Remoting, которые требуются для разработки параллельных и распределенных приложений на базе .NET. С практической точки зрения, цель, которая преследовалась разработчиками языка MC#, заключалась в разработке языка для промышленного параллельного и распределенного программирования, которое, в настоящее время, вовлекает в себя все больше и больше человеческих ресурсов в связи с наступлением эры многоядерных процессоров. Этот язык призван заменить языки C и Фортран в разработке приложений указанного типа. В этом отношении, подход, принятый в рамках проекта MC#, совпадает с подходом, принятым при разработке языка Х10 [4], который ориентирован как на многоядерные, так и на "неоднородные кластерные вычисления". Разработка языка X10 является частью совместного проекта PERCS (Productive Easy-to-use Reliable Computer Systems) фирмы IBM с несколькими академическими партнерами. Этот проект нацелен на создание к 2010г. новых масштабируемых систем, которые должны обеспечить десятикратное увеличение продуктивности работы программистов при разработке параллельных приложений [5].

В данном учебном введении рассматриваются основы программирования на языке MC#, предназначенном для написания программ, работающих на всём спектре параллельных архитектур - от многоядерных процессоров до Grid-сетей. Единственное требование к таким системам со стороны MC# - на них должна быть установлена среда исполнения CLR (Common Language Runtime) с соответствующим набором библиотек. На машинах с операционной системой Windows реализацией такой среды является Microsoft .NET Framework, а на машинах с операционной системой Linux - система Mono (http://www.mono-project.com), которая является свободной реализацией платформы .NET для Unix-подобных систем.

Язык MC# является адаптацией и развитием базовых идей языка Polyphonic C# на случай параллельных и распределенных вычислений. Язык Polyphonic C# был разработан в 2002г. в Microsoft Research Laboratory (г. Кембридж, Великобритания) Н. Бентоном (N. Benton), Л. Карделли (L. Cardelli) и Ц. Фурнье (C. Fournet). Целью его создания было добавление высокоуровневых средств асинхронного параллельного программирования в язык C# для использования в серверных и клиент-серверных приложениях на базе Microsoft .NET Framework.

Ключевая особенность языка Polyphonic C# заключается в добавлении к обычным, синхронным методам, так называемых "асинхронных" методов, которые предназначены играть в (многопоточных) программах две основные роли:

1. автономных методов, предназначенных для выполнения базовой вычислительной работы, и исполняемых в отдельных потоках, и
2. методов, предназначенных для доставки данных (сигналов) обычным, синхронным методам.

Для синхронизации нескольких асинхронных методов, а также асинхронных и синхронных методов, в язык C#, кроме того, были введены новые конструкции, получившие название связок (chords).

При этом исполнение Polyphonic C#-программ, по замыслу авторов этого языка, по-прежнему, предполагалось либо на одной машине, либо на нескольких машинах, с зафиксированными на них асинхронными методами, взаимодействующими между собой с использованием средств удаленного вызова методов (RMI - Remote Method Invocation), предоставляемых библиотекой System.Runtime.Remoting платформы .NET.

В случае языка MC#, программист может предусмотреть исполнение автономных асинхронных методов либо локально, либо удаленно. В последнем случае, метод может быть спланирован для исполнения на другой машине, выбираемой двумя способами: либо согласно явному указанию программиста (что не является типичным случаем), либо автоматически (обычно, на наименее загруженном узле кластера или машине Grid-сети). Взаимодействие асинхронных методов, в рамках языка MC#, реализуется посредством передачи сообщений с использованием каналов и обработчиков канальных сообщений. Эти каналы и обработчики определяются в MC#-программах с помощью связок в стиле языка Polyphonic C#.

Таким образом, написание параллельной, распределенной программы на языке MC# сводится к выделению с помощью специального ключевого слова async методов, которые должны быть исполнены асинхронно локально (в виде отдельных потоков), а также с помощью ключевого слова movable тех методов, которые могут быть перенесены для исполнения на другие машины.

Выбор языка C# в качестве базового, дает возможность использовать современный язык объектно-ориентированного программирования, обладающий богатым множеством библиотек (для создания Web-приложений и работы с Web-сервисами, разработки графических приложений, обработки реляционных и слабоструктурированных (XML-) документов, реализации систем с повышенными средствами безопасности, и т.д.), быстро развивающийся (см. спецификации языков С# 2.0 и C# 3.0), и, одновременно, исключающий низкоуровневые и небезопасные средства, такие, как указатели и команды резервирования и освобождения областей памяти, которые значительно снижают производительность труда программистов и надежность создаваемых ими систем.

По сравнению с применением интерфейса MPI, в программах на языке MC# нет необходимости явно управлять распределением вычислительных процессов по процессорам (ядрам, узламкластера, машинам Grid-сети), хотя необходимые для этого средства в языке также предоставляются. Чтобы написать параллельную программу на языке MC#, достаточно только указать с помощью специальных ключевых слов ( async или movable ) какие функции (методы классов) могут быть выполнены параллельно (распределенно). Кроме того, новые вычислительные процессы могут создаваться и распределяться по доступным узлам (в распределенном режиме) динамически во время исполнения MC#-программ, что невозможно для MPI-программ. Средства динамического создания так называемых "активностей" также предусмотрены в языке X10, но с явным указанием места исполнения новой активности. Таким образом, в системе исполнения X10-программ не предусмотрены средства автоматического распределения активностей по доступным физическим процессорам. Более точно, асинхронная активность в языке X10 создается с помощью оператора async ( P ) S, где P есть выражение, задающее место исполнения активности, а S есть оператор, представляющий вычислительное тело активности. В языке X10, внутри одного метода класса возможно создание нескольких активностей, тогда как в языке MC# параллельность возможна только на уровне методов класса.

В сравнении с MPI, в программах на MC# (в распределенном режиме) нет необходимости в ручном программировании сериализации объектов (данных) для их пересылке на другой узел - Runtime-система языка MC# производит сериализацию/десериализацию пересылаемых объектов автоматически.

Структура данного учебного пособия построена следующим образом. В данной лекции дано описание новых средств языка MC# - async- и movable- методов, а также каналов и обработчиков канальных сообщений. Приведены примеры определения связок каналов и обработчиков, а также отмечены особенности программирования для локального (многоядерного) и распределенного (кластерного) режимов.

Лекция 5 посвящена некоторым типичным задачам, имеющим параллельные алгоритмы решения, на которых демонстрируется использование специфических конструкций языка MC# и общие методы построения параллельных программ на этом языке.

В Приложении даны полные тексты программ из лекции 5.

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

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

Разделение всех методов в программе на обычные (синхронные) и асинхронные (в том числе, на те, которые могут быть перенесены для исполнения на другие машины) производится программистом с использованием специальных ключевых слов async и movable. (В языке MC#, семантика и использование ключевого слова async полностью совпадает с использованием этого слова в языке Polyphonic C# за тем исключением, что в MC# async-методы не могут встречаться в связках - см. об этом ниже).

Async- и movable-методы являются единственным средством создания параллельных процессов (потоков) в языке MC#.

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

• для обеспечения взаимодействия параллельных процессов между собой,
• для их синхронизации.

Основой взаимодействия параллельных процессов в языке MC# является передача сообщений (в отличие от другой альтернативы - использования общей (разделяемой) памяти). Продолжая сравнение языка MC# с языком X10, следует отметить, что в языке X10 реализованы обе парадигмы взаимодействия - как на основе передачи сообщений, так и на основе общей (разделяемой) памяти. В языке MC#, средства взаимодействия между процессами оформлены в виде специальных синтаксических категорий - каналов и обработчиков канальных сообщений. При этом, синтаксически посылка сообщения по каналу или прием из него с помощью обработчика выглядят в языке как вызовы обычных методов. В языке X10, пересылка значений с одного "места" (place - в терминологии X10) в другое, требует явного порождения (асинхронной) активности, осуществляющей транспортировку этого сообщения.

Для синхронизации параллельных процессов в MC# используются связки (chords), определяемые в стиле языка Polyphonic C#. В языке X10, для синхронизации используются более сложные конструкции под названием clocks.

Общий синтаксис определения async- и movable-методов в языке MC# следующий:

модификаторы { async | movable } имя_метода ( аргументы )
{
   < тело метода >
}

Ключевые слова async и movable располагаются на месте типа возвращаемого значения, поэтому синтаксическое правило его задания при объявлении метода в языке MC# имеет вид:

return-type ::= type | void | async | movable

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

Отличия async- и movable-методов от обычных методов состоят в следующем:

• вызов async- и movable-методов заканчивается, по существу, мгновенно (для последних из названных методов, время затрачивается только на передачу необходимых для вызова этого метода данных на удаленную машину),
• эти методы никогда не возвращают результаты (о взаимодействии movable-методов между собой и с другими частями программы, см. Раздел 4.2 "Каналы и обработчики").

Соответственно, согласно правилам корректного определения async- и movable-методов:

• они не могут объявляться статическими,
• в их теле не может использоваться оператор return.

Вызов movable-метода имеет две синтаксические формы:

1. имя_объекта.имя_метода ( аргументы )

   (место исполнения метода выбирается Runtime-системой автоматически),

2. имя_машины@имя_объекта.имя_метода ( аргументы )

   ( имя_машины задает явным образом место исполнения данного метода).

При разработке распределенной программы на языке MC# (т.е., при использовании в ней movable-методов и исполнении её на кластере или в Grid-сети), необходимо учитывать следующие особенности системы исполнения (Runtime-системы) MC#-программ.

Во-первых, объекты, создаваемые во время исполнения MC#-программы, являются, по своей природе статическими: после своего создания, они не перемещаются и остаются привязанными к тому месту (машине), где они были созданы. В частности, именно в этом месте (на этой машине) они регистрируются Runtime-системой, что необходимо для доставки канальных сообщений этим объектам и чтения сообщений с помощью обработчиков, связанных с ними (этими объектами).

Поэтому, первой ключевой особенностью языка MC# (а точнее, его семантики) является то, что, в общем случае, во время вызова movable-метода, все необходимые данные, а именно:

1. сам объект, которому принадлежит данный movable-метод, и
2. его аргументы (как ссылочные, так и скалярные значения) только копируются (но не перемещаются) на удаленную машину. Следствием этого является то, что все изменения, которые осуществляет (прямо или косвенно) movable-метод с внутренними полями объекта, проводятся с полями объекта-копии на удаленной машине, и никак не влияют на значение полей исходного объекта.

Эта ситуация проиллюстрирована на Рис 4.2.

Поэтому выполнение программы

даст

Before: x = 1
After: x = 1

Если копируемый (при вызове его movable-метода) объект обладает каналами или обработчиками (или же просто, они являются аргументами этого movable-метода), то они также копируются на удаленную машину. Однако, в этом случае, они становятся "прокси"-объектами для исходных каналов и обработчиков (см. об этом подробнее в Разделе 4.2).

В распределенном режиме, имеется два режима параллелизации MC#-программ: "функциональный" и "нефункциональный" (или объектный), и от выбора того или другого будет, в конечном счете, зависеть эффективность исполнения программы. Эти режимы задаются модификаторами functional и nonfunctional при объявлении movable-метода (для async-методов эти модификаторы игнорируются). Значением по умолчанию является режим functional.

В функциональном режиме, объект, для которого вызывается movable-метод, не передается на удаленную машину. То есть, все данные, необходимые movable-методу, должны передаваться через его аргументы. Наоборот, путем задания модификатора nonfunctional, обеспечивается передача объекта на удаленную машину.

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

имя_машины:имя_узла@имя_объекта.имя_метода ( аргументы )

Каналы и обработчики канальных сообщений являются средствами для организации взаимодействия параллельных распределенных процессов между собой. Синтаксически, каналы и обработчики обычно объявляются в программе с помощью специальных конструкций - связок ( chords ). Впервые, в императивных языках, конструкция связок появилась в языке Polyphonic C#. Помимо объявления каналов и обработчиков, связки также играют в языке роль средств синхронизации процессов: как распределенных (использующих movable-методы), так и нераспределенных (использующих async-методы).

Например, объявление канала sendInt для передачи одиночных целочисленных значений вместе с соответствующим обработчиком getInt для получения значений из этого канала, выглядит следующим образом:

В общем случае, синтаксические правила определения связок в языке MC# имеют вид:

chord-declaration ::= [handler-header] [ & channel-header ]* body
handler-header ::= attributes modifiers handler handler-name
                   return-type ( formal-parameters )
channel-header ::= attributes modifiers channel channel-name
                  ( formal-parameters )

Связки определяются в виде членов класса. По правилам корректного определения, каналы и обработчики не могут иметь модификатора static, а потому они всегда привязаны к некоторому объекту класса, в рамках которого они объявлены:

Таким образом, мы можем послать целое число n по каналу sendInt, записав выражение

a.sendInt( n );

где a есть объект для которого определен канал sendInt.

Если имя канала использовано без уточняющих префиксов, например, как

c( n );

то подразумевается, как обычно, использование текущего объекта:

this.c ( n );

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

int m = a.getInt();

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

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

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

Аналогично языку Polyphonic C#, в одной связке можно определить несколько каналов. Такого вида связки являются главным средством синхронизации параллельных (в том числе, распределенных) потоков в языке MC#:

Таким образом, общее правило срабатывания связки состоит в следующем: тело связки исполняется только после того, как вызваны все методы из заголовка этой связки.

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

Также, возможно объявление канала, разделяемого между несколькими обработчиками:

Синтаксически, такое объявление возможно путем применения двух связок, как показано в примере ниже:

Таким образом, в данном примере, если имеются значения в каналах c1 и c2, то возможно срабатывание обработчика h1. Аналогичная ситуация имеет место для каналов c2, c3 и обработчика h2. В общем случае, это может привести к нетерминизму в поведении программы.

Наконец, возможен случай, когда один и тот же обработчик объявлен в разных связках и с различными каналами:

Схематически, совокупность таких определений может быть представлена как на Рис 4.6:

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

При использовании связок в языке MC# нужно руководствоваться следующими правилами их корректного определения:

1. Формальные параметры каналов и обработчиков не могут содержать модификаторов ref или out.
2. Если в связке объявлен обработчик с типом возвращаемого значения return-type, то в теле связки должны использоваться операторы return только с выражениями, имеющими тип return-type.
3. Все формальные параметры каналов и обработчика в связке должны иметь различные идентификаторы.
4. Каналы и обработчики в связке не могут быть объявлены как static.

Вторая ключевая особенность языка MC# состоит в том, что каналы и обработчики могут передаваться в качестве аргументов методам (в том числе, async- и movable -методам) отдельно от объектов, которым они принадлежат (в этом смысле, они похожи на указатели на функции в языке С, или, в терминах языка C#, на делегатов ( delegates ) ).

Третья ключевая особенность языка MC# состоит в том, что, в распределенном режиме, при копировании каналов и обработчиков на удаленную машину (под которой понимается узел кластера или некоторая машина в Grid-сети) автономно или в составе некоторого объекта, они становятся прокси-объектами, или посредниками для оригинальных каналов и обработчиков. Такая подмена скрыта от программиста - он может использовать переданные каналы и обработчики (а, в действительности, их прокси-объекты) на удаленной машине (т.е., внутри movable-методов) также, как и оригинальные: как обычно, все действия с прокси-объектами перенаправляются Runtime-системой на исходные каналы и обработчики. В этом отношении, каналы и обработчики отличаются от обычных объектов: манипуляции над последними на удаленной машине не переносятся на исходные объекты (см. первую ключевую особенность языка MC#).

На Рис 4.7 и 4.8 схематически демонстрируются передача и использование каналов и обработчиков на удаленной машине. Верхние индексы y у имен каналов и обработчиков обозначают исходную машину, где они были созданы.

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

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

Последовательность чисел Фибоначчи есть бесконечный ряд из натуральных чисел

a0, a1, a2, a3, . . .

таких, что

a0 = 1,
a1 = 1, и
ai = ai-1 + ai-2,  для  i >=  2.

Построим параллельную программу, находящую n -ое ( n >= 0 ) число в ряду Фибоначчи, т.е., элемент a_n последовательности.

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

Класс Fib, содержащий основной вычислительный метод Compute, может иметь следующий вид:

Главный класс для этой программы может выглядеть следующим образом:

Упражнение 1. Показать, почему при рекурсивных вызовах функции Compute необходимо создание новых объектов класcа Fib.

( Подсказка: рассмотреть как будут использоваться каналы ic1 и ic2 в программе, в которой опущено создание таких объектов, например, при вызове функции Compute с n = 3).

Легко видеть, что приведенный вариант параллельной программы является очень неэффективным, поскольку в нем порождается 2ⁿ асинхронных вызовов метода Compute, каждый из которых выполняет очень мало вычислительных операций: фактически, порождает два дополнительных вызова и передает результат по каналу. Очевидно, что в этом случае эффект от параллельного исполнения методов будет перекрыт накладными расходами на их порождение.

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

Приведенный выше вариант является более эффективным, чем первый, но и он обладает существенным недостатком: теперь async-методы для больших n выполняют очень мало вычислительных операций.

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

Приведенные выше рассуждения и варианты программы Fib переносятся и на варианты этой же программы, но для распределенного исполнения (т.е., с заменой async на movable ). При этом, для получения максимального ускорения программист должен подобрать оптимальное значение константы threshold.

Ниже приведены графики времени выполнения последовательной программы и распределенного, "линейного" варианта программы Fib с threshold = 36. Причем количество используемых процессоров в распределенном варианте определялось как n - 34 (для n >= 35 ). Тестовые замеры проводились на кластере с процессорами AMD Athlon(TM) MP 1800+.

Полные тексты вариантов программы Fib приведёны в приложении [A1].

Если структура данных задачи организована в виде дерева, то его обработку легко распараллелить путем обработки каждого поддерева отдельном async- ( movable- ) методом.

Предположим, что мы имеем следующее определение (в действительности, сбалансированного) бинарного дерева в виде класса BinTree:

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

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

Следует также отметить, что в случае распределенного варианта этой программы, при вызове movable -метода Sum, к объекту класса BinTree, являющемуся аргументом этого метода, будут применяться процедуры сериализации/десериализации при переносе вычислений на другой компьютер. (В действительности, с точки зрения Runtime-языка MC#, поддерживающей распределенное исполнение программ, канал также является обычным объектом, к которому будут применяться процедуры сериализации/десериализации).

Полный текст данной программы приведён в приложении [A2].

Упражнение 2. Предположим, что имеется класс Tree, внутренними полями которого являются поле value, хранящее значение, связанное с корнем данного дерева, и поле subtrees, являющееся массивом объектов класса Tree.

Написать параллельную программу на MC#, суммирующую значения из всех вершин заданного дерева.

( Подсказка: для получения значений от рекурсивно порождаемых методов, воспользуйтесь одним каналом).

Напомним коротко некоторые понятия и определения, относящиеся к дискретному преобразованию Фурье и быстрым алгоритмам его вычисления. Более подробно об этом см., например, в главе 32.2 "Дискретное преобразование Фурье. Быстрый алгоритм" книги [6].

Комплексное число

называется главным значением корня степени n из единицы.

Вектор y=(y₀, y₁, … , y_n-1) называется дискретным преобразованием Фурье вектора a=(a₀, a₁, … , a_n-1), где a_i и y_j ( 0 <= i, j <= n ) есть комплексные числа, если

Быстрое преобразование Фурье (БПФ) представляет собой метод быстрого вычисления дискретного преобразования Фурье, использующий свойства комплексных корней из единицы и требующий времени O(n log n), в отличие от времени O(n²) при прямом вычислении по формуле.

В случае, когда n есть степень двойки, имеется следующий алгоритм быстрого преобразования Фурье вектора a=(a₀, a₁, … , a_n-1):

Легко видеть, что используемый в данном алгоритме двоичный принцип "разделяй и властвуй" аналогичен принципам, реализованным в предыдущих программах вычисления чисел Фибоначчи и обхода двоичного дерева.

Ниже приведен текст на языке MC# асинхронного метода, реализующего приведенный выше рекурсивный алгоритм. Полный текст этой программы можно найти в приложении [A3].

Однако, данная программа, даже с оптимизациями, аналогичными рассмотренным для программ Fib и SumBinTree, не дает ускорения при исполнении на параллельной архитектуре из-за больших объемов требуемой памяти ( в 2 раза бoльших, чем для последовательного варианта), необходимой для размещения массивов a^[0], a^[1], y^[0], y^[1] при рекурсивных вызовах.

Существуют более эффективные алгоритмы БПФ, например, итеративный алгоритм из главы 32.3 "Эффективные реализации быстрого преобразования Фурье" из книги [6]. Однако, данный алгоритм естественным образом параллелится только на 2 процессора. Реализацию такого алгоритма на языке MC# см. в приложении [A3].

Ниже представлены графики времени исполнения последовательного и итеративного параллельного (на 2 процессора) алгоритмов БПФ, реализованных на языке MC#.

Тестовые замеры проводились на машине с двухядерным процессором Intel Core 2 Duo 2.4 GHz и оперативной памятью 1 Гб.

В данном разделе будет представлена параллельная программа построения списка простых чисел методом просеивания (другое название этого метода - "решето Эратосфена").

По условию задачи, по заданному натуральному числу N >= 2, необходимо найти все простые числа в интервале от 2 до N.

Метод просеивания состоит из следующих шагов:

1. из исходного списка l₀ всех натуральных чисел от 2 до N

   l₀ = [2, … , N]

   выбирается первое число этого списка, а именно 2, и выдается в качестве первого выходного значения;
2. затем строится новый список l₁, который получается из списка l₀ вычеркиванием из него всех чисел, кратных очередному выбранному простому числу - на первом шаге, числу 2:

   l₁ = [3, 5, 7, … , N] (в предположении, что N нечетно)

3. затем данная процедура повторяется рекурсивно для вновь построенного списка.

Алгоритм заканчивает свою работу, когда очередной список оказывается пустым.

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

1. переслать первый элемент из входного потока натуральных чисел (если он не пуст) в выходной поток;
2. отфильтровать все оставшиеся числа их входного потока по модулю первого элемента и направить этот отфильтрованный поток на вход новой рекурсивно вызванной процедуре Sieve; выходным потоком для рекурсивно вызванной процедуры становится исходный выходной поток.

Выходным же каналом для этой новой процедуры будет исходный выходной канал.

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

Рекурсивные вызовы метода Sieve сопровождаются созданием соответствующих объектов (класса CSieve ), имеющих каналы и обработчики. Эти каналы и обработчики используются для создания цепочки обрабатывающих элементов, с помощью которых производится просеивание потока натуральных чисел.

Программа состоит из следующих методов:

• async Sieve( handler int() getList, channel ( int ) sendPrime) - async-метод класса CSieve, который реализует собственно алгоритм просеивания: из обработчика getList предыдущего объекта цепочки читается поток чисел, фильтруется по модулю первого элемента из потока, и выбранные простые числа посылаются в канал sendPrime (через дальнейшие рекурсивные вызовы метода Sieve );
• void filter ( int p, handler int()getList, channel ( int ) cfiltered) - функция класса CSieve, реализующая фильтрацию потока натуральных чисел: из потока чисел, получаемых путем вызова обработчика getList, удаляются все элементы, которые делятся на число p, и посылаются по каналу cfiltered;
• public static void Main( String [] args )- главная функция из класса Eratosthenes, которая создает поток натуральных чисел Nats, и, по мере получения простых чисел из обработчика getPrime, выводит их на консоль.

Полный текст программы приведен ниже, а также в приложении [A4].

Как обычно, распределенный вариант программы, который может исполняться на сети машин, получается заменой ключевого слова async на movable.

В принципе, при исполнении программы на одной машине, элементы цепочки, с помощью которой производится просеивание, могут быть построены из стандартных объектов .NET, например, из очередей (объектов класса Queue ). Однако, в этом случае, программист должен позаботиться об их блокировке, что необходимо в случае одновременной работы множества синхронных методов (потоков). Использование каналов и обработчиков языка MC# освобождает программиста от этой обязанности.

Аналогично ранее рассмотренным примерам, метод Sieve выполняет слишком мало вычислительных операций, чтобы обеспечить эффективность всей параллельной (распределенной ) программы в целом.

В данном разделе описывается модификация наивного алгоритма "решето Эратосфена", существенно улучшающая эффективность параллельной (распределенной) программы, и которая дает существенное ускорение при поиске простых чисел в длинных интервалах (например, для N >= 10⁶ ).

Основная идея предлагаемого алгоритма заключается в переходе от использования потоков одиночных данных (потоков отдельных натуральных чисел) к потокам пакетов натуральных чисел.

Пакет - это массив натуральных чисел фиксированного размера (задаваемого в программе значением PACKAGE_SIZE ), пустые хвостовые элементы которого заполняются нулями.

При этом, функции наивного алгоритма обобщаются в данном варианте естественным образом:

• async Sieve( handler int []() getNatPack, channel (int []) sendPrimesPack) - с помощью обработчика getNatPack получает первый пакет из потока, обрабатывает его функцией SynchronousSieve, получая пакет простых чисел head, и отправляя его по каналу sendPrimesPack; остальные пакеты из входного потока фильтруются с помощью функции filter по модулю пакета head и направляются на вход следующей в цепочке рекурсивной функции Sieve ;
• void filter( int [] head, handler int [] () getNatPack, channel ( int []) cfiltered) - функция, которая фильтрует пакеты из входного потока, получаемые с помощью обработчика getNatPack, по модулю пакета простых чисел head, отправляя результирующие пакеты в канал cfiltered; при этом, все результирующие пакеты (кроме, может быть, последнего) имеют длину PACKAGE_SIZE (строго говоря, и последний пакет имеет длину PACKAGE_SIZE, но его хвостовая часть может быть заполнена нулями).

Полный текст программы Eratosthenes2 приведен ниже, а также в приложении [A4].

5.5. Программа all2all

Ниже будет представлен вариант программы all2all с распределенными ( movable- ) процессами.

В этой программе, каждый распределенный процесс представляется методом Start объекта класса DistribProcess. Для взаимодействия между собой, каждый распределенный процесс создает объект класса BDChannel (Bidirectional channel), содержащий канал Send и обработчик Receive:

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

Каждый распределенный процесс (объект класса DistribProcess ) выполняет в данной программе следующую последовательность действий:

1. Создает свой собственный объект класса BDChannel и отсылает его главному процессу.
2. Принимает от главного процесса массив объектов класса BDChannel всех остальных процессов (включая свой собственный).
3. Пользуясь этим массивом, посылает сообщение всем остальным процессам в группе.
4. Принимает сообщения от всех процессов в группе.
5. Посылает сигнал об окончании своей работы главному процессу.

Полный текст программы All2all приведен в приложении [A5].

Дополнения

Дополнение. Приложение

[A1]	ComputeFib	Программы вычисления чисел Фибоначчи:
		а) базовый алгоритм,
		б) алгоритм с локальной функцией cfib,
		в) "линейный" алгоритм.
[A2]	SumBinTree	Программа обхода (суммирования значений в узлах) бинарного дерева
[A3]	FFT	Программа быстрого преобразования Фурье:
		а) рекурсивный алгоритм,
		б) итеративный алгоритм.
[A4]	Eratosthenes	Вычисление простых чисел методом просеивания (решето Эратосфена):
		а) наивный алгоритм,
		б) пакетный алгоритм.
[A5]	All2all	Программа, демонстрирующая взаимодействие группы параллельных, распределенных процессов в соответствии с принципом "каждый с каждым"

[A1] ComputeFib

• Базовый алгоритм
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

• Алгоритм с локальной функцией cfib
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

• "Линейный алгоритм"
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

[A2] SumBinTree

увеличить изображение

увеличить изображение

[A3] FFT

• Рекурсивный алгоритм
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

• Итеративный алгоритм
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

[A4] Eratosthenes

• Наивный алгоритм
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

• Пакетный алгоритм
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  
  
  
  
  увеличить изображение
  
  

[A5] All2all

увеличить изображение

увеличить изображение

увеличить изображение

Дополнение. Windows Compute Cluster Server - платформа для высокопроизводительных вычислений на базе технологий фирмы Microsoft

Цель - научиться устанавливать Compute Cluster Pack на машины двух типов:

• рабочие узлы кластера (включая головной узел),
• клиентские машины, используемые для посылки заданий на кластер.

Содержание

Перед развертыванием Windows Compute Cluster Server (CCS) 2003 для организации вычислительного кластера из машин под управлением ОС Windows, в первую очередь выбирается машина, которая будет служить головным узлом кластера, и проверяется ее соответствие техническим требованиям:

1. CPU - процессор с 64-битной архитектурой: Intel Pentium, или семейство процессоров Intel Xeon с технологией Intel Extended Memory 64 Technology (EMT64), или семейство процессоров AMD Opteron, AMD Athlon или совместимые с ними
2. минимальный объем оперативной памяти - 512 Мб
3. необходимый размер дискового пространства - 4 Gb
4. сетевые карты - если предусматривается организация, кроме общей (public) сети еще и частной (private), то необходимы две сетевые карты; организация специальной MPI-сети может потребовать еще одной дополнительной сетевой карты.

Развертывание Windows CCS 2003 состоит из трех основных шагов:

1. установка базовой операционной системы Windows Server 2003 (Standard x64 Edition/Enterprise x64 Edition/Compute Cluster Edition);
2. установка Compute Cluster Pack;
3. конфигурирование сети кластера и службы RIS (Remote Installation Services), а также добавление узлов и пользователей кластера.

В данном занятии рассматривается практическое выполнение шагов 2 и 3.

Предварительно, относительно шага 1 следует отметить, что

1. если предполагается использование RIS для развертывания вычислительных узлов кластера, то для этой службы должен быть создан отдельный том (например, D:\) на диске;
2. компьютер с установленной базовой ОС должен быть включен в существующий Active Directory-домен, или же должен быть создан новый домен для кластера с использованием программы DCpromo.exe, и между вновь созданным доменом и уже существующими доменами должны быть установлены доверительные (trust) отношения соответствующими средствами.

Шаг 2 (установка Compute Cluster Pack) включает в себя следующую последовательность действий:

1. Вставить CD-ROM с Compute Cluster Pack в дисковод - процедура установки Setup.exe запустится автоматически.
2. В мастере установки Microsoft CCS, выбрать одну из трех возможностей, как показано на Рис 1.1, и нажать Next.
   
   
   
   Рис. 1.1.  Выбор режима установки для Compute Cluster Pack.

3. На странице Welcome, для продолжения работы, нажмите Next.
4. На странице лицензионного соглашения End-User License Agreement, выбрать альтернативу "Accept", как показано на Рис 1.2, и нажать далее Next.
   
   
   
   Рис. 1.2.  Страница лицензионного соглашения.

5. На странице Installation Folder (см. Рис 1.3), либо нажать Change для изменения директории, где будет установлен Compute Cluster Pack, либо нажать Next.
   
   
   
   Рис. 1.3.  Страница выбора директории для установки Compute Cluster Pack.

6. Нажать Install для выполнения непосредственно процедуры установки.

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

Также, при установке головного узла, будет проверено наличие и доустановлены (если необходимо) следующие программные компоненты:

• MMC (Microsoft Management Console) 3.0,
• .NET Framework 2.0,
• обновления для RIS и ICS (Internet Connection Sharing).

Сразу после окончания установки, на экране появляется страница To Do List, которая используется для конфигурирования кластера на следующем шаге.

Также, конфигурирование кластера можно произвести и с помощью панели Compute Cluster Administrator, которая появляется в списке программ после окончания установки Compute Cluster Pack.

Конфигурирование кластера

После установки Compute Cluster Pack на головной узел, необходимо соответствующим образом сконфигурировать кластер с помощью страницы ToDo List или с помощью меню Compute Cluster Administrator.

Для этого необходимо выполнить следующие шаги:

1. На панели Networking (см. Рис 1.4), выбрать Define cluster network topology и задать топологию сети кластера, задав интерфейсы общей частной и MPI-сетей головного узла.
   
   
   
   Рис. 1.4.  Панель управления кластером

2. Сконфигурировать RIS. Для этого, на панели Remote Installation Services (RIS) выбрать мастера Configure RIS и установить RIS. Если будет использоваться автоматический метод добавления узлов и повторной установки на них образов операционной системы, то должны быть установлены RIS и обновления для этой службы.
3. Если будет использоваться RIS, то необходимо создать установочный образ. Для этого, на панели Remote Installation Services (RIS) необходимо выбрать мастера Manage Images. Система Windows Compute Cluster Server 2003 позволяет хранить несколько образов на головном узле.
4. Модифицировать установочный образ с помощью соответствующего установочного ключа.
5. Добавить вычислительные узлы. Для этого, на панели Node Management выбрать мастера Add Nodes, и затем выбрать режим Automated. При добавлении узлов в кластер, от администратора кластера будет требоваться подтверждение этого добавления.
6. Сконфигурировать (завести) новых пользователей и администраторов кластера. Для этого, на панели Cluster Security выбрать мастера Configure Users.

На шаге 5, администратор кластера должен ввести имя пользователя и пароль для входа в домен, куда будут добавляться узлы. Эти имя и пароль будут использованы для создания учетных записей в Active Directory для каждого из узлов. Также, администратор на этом шаге должен ввести так называемый Node Series Name - префикс имен компьютеров, которые будут добавляться в качестве узлов кластера.

Дополнение. Подготовка заданий для выполнения на кластере под управлением Compute Cluster Server

Цель - научиться подготавливать и запускать задания с использованием графического интерфейса менеджера заданий; изучить структуру XML-файлов заданий и их параметры.

Для проведения данного практического занятия понадобится самораспаковывающийся архив ClusterComputing.exe, который либо можно скачать с http://download.microsoft.com/download/f/2/7/f279e71e-efb0-4155-873d-5554a0608523/ClusterComputing.exe, либо он уже может быть доступен на машинах учебного класса, где проводятся занятия. Данный архив необходимо распаковать и открыть соответствующее решение в рамках Visual Studio 2005. В данном решении реализуется несколько алгоритмов перемножения больших матриц.

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

MatrixUtil matrix1.mtx 1 5000
MatrixUtil matrix2.mtx 1 5000

после исполнения которых будут созданы матрицы matrix1.mtx и matrix2.mtx размерности 5000 х 5000.

В рамках Windows Compute Cluster Server имеется скрипт job, который можно использовать из командной строки для запуска заданий на кластере.

Для запуска последовательного алгоритма перемножения матриц, необходимо выполнить команду

job submit /f:MatrixMultiplierSerial.x

где XML-файл MatrixMultiplierSerial.xml, описывающий данное задание для вычислительного кластера, имеет вид:

<?xml version="1.0" encoding="utf-8" ?> 
<Job xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
    xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
    SoftwareLicense="" 
    MaximumNumberOfProcessors="1" 
    MinimumNumberOfProcessors="1" 
    Runtime="00:00:50" 
    IsExclusive="false" 
    Priority="Normal" 
    Name="MatrixMultiplierSerial" 
    Project="Matrix Multiplication" 
    RunUntilCanceled="false">
    <Tasks xmlns="http://www.microsoft.com/ComputeCluster/">
        <Task MaximumNumberOfProcessors="1" 
            MinimumNumberOfProcessors="1" 
            WorkDirectory="\\DataServer\Public" 
            Stdout="MatrixMultiplier.out" 
            Name="MatrixMultliplier"     
            CommandLine=
                "MatrixMultiplier matrix1.mtx matrix2.mtx matrix3.mtx" 
            IsCheckpointable="false"             
            IsExclusive="false" 
            IsRerunnable="false"
            Runtime="00:00:50">
            <EnvironmentVariables /> 
        </Task>
    </Tasks>
</Job>

Если команда отсылки задания на кластер закончилась успешно, то этому заданию будет присвоен уникальный ID

Job created ,   ID: 55

Этот ID в дальнейшем может быть использован для получения информации о состоянии задания, изменения его параметров и снятия его с выполнения.

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

job view 55

По этой команде, будет выдано информационное сообщение примерно такого вида:

JOB_ID: 55
SubmittedBy:    TestComputeCluster\Administrator
NAME:   MatrixMultiplierSerial
STATUS: Running
CPUS:   1,1
ALLOCATED_NODES:        TestNode1
SUBMIT_TIME  :  11/22/2005 9:49:00 AM
NUM_TASKS:      1
  Queued:       0
  Running:      1
  Finished:     0
  Failed:       0
  Cancelled:    0

Задание MatrixMultiplierMultiSerial является параллельной реализацией алгоритма перемножения матриц, но без использования MPI.

<?xml version="1.0" encoding="utf-8" ?> 
<Job xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
    xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
    SoftwareLicense="" 
    MaximumNumberOfProcessors="4" 
    MinimumNumberOfProcessors="4" 
    Runtime="00:00:12" 
    IsExclusive="false" 
    Priority="Normal" 
    Name="MatrixMultiplierMultiSerial" 
    Project="Matrix Multiplication" 
    RunUntilCanceled="false">
    <Tasks xmlns="http://www.microsoft.com/ComputeCluster/">
        <Task MaximumNumberOfProcessors="1" 
            MinimumNumberOfProcessors="1" 
            WorkDirectory="\\DataServer\Public"             
            Stdout="MatrixMultiplierMultiSerial.out" 
            Name="Task1" 
            CommandLine="MatrixMultiplier.exe matrix1.mtx matrix2.mtx 
                         matrix_out1.mtx 0 0 2500" 
            IsCheckpointable="false" 
            IsExclusive="false" 
            IsRerunnable="false" 
            Runtime="00:00:10">
            <EnvironmentVariables /> 
        </Task>
        
        <!-- Task2, Task3 and Task4 are defined similarly -->
        <Task MaximumNumberOfProcessors="1" 
            MinimumNumberOfProcessors="1" 
            Depend="Task1,Task2,Task3,Task4" 
            WorkDirectory="\\DataServer\Public" 
            Stdout="MatrixMutltiplierMultiSerial.out" 
            Name="Task5" 
            CommandLine="MatrixUtil.exe MatrixMerged.mtx 2 matrix_out1.mtx 
                         matrix_out2.mtx matrix_out3.mtx matrix_out4.mtx" 
            IsCheckpointable="false" 
            IsExclusive="false" 
            IsRerunnable="false" Runtime="00:00:01">
            <EnvironmentVariables /> 
        </Task>
        <Task MaximumNumberOfProcessors="1" 
            MinimumNumberOfProcessors="1" 
            Depend="Task5" 
            WorkDirectory="\\DataServer\Public"     
            Stdout="MatrixMutltiplierMultiSerial.out"
            Name="Cleanup" 
            CommandLine="del \\DataServer\Public\matrix_out*.mtx" 
            IsCheckpointable="false" 
            IsExclusive="false" 
            IsRerunnable="false" 
            Runtime="00:00:01">
            <EnvironmentVariables /> 
        </Task>
    </Tasks>
</Job>

Листинг 1. (html, txt)

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

Запуск данного задания осуществляется командой:

job submit /f:MatrixMultiplierMultiSerial.xml

Описание задания для исполнения MPI-варианта алгоритма перемножения матриц представлено файлом MatrixMultiplierMPI.xml:

<?xml version="1.0" encoding="utf-8" ?> 
<Job xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
    xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
    SoftwareLicense="" 
    MaximumNumberOfProcessors="4" 
    MinimumNumberOfProcessors="4" 
    Runtime="00:00:12" 
    IsExclusive="false" 
    Priority="Normal" 
    Name="MatrixMultiplierMPI" 
    Project="Matrix Multiplication" 
    RunUntilCanceled="false">
    <Tasks xmlns="http://www.microsoft.com/ComputeCluster/">
        <Task MaximumNumberOfProcessors="4" 
            MinimumNumberOfProcessors="4" 
            WorkDirectory="\\DataServer\MatrixMultiplier" 
            Stdout="MatrixMultiplierMPI.out" Name="Task1" 
            CommandLine="mpiexec.exe -hosts %CCP_NODES% 
                         MatrixMultiplierMPI.exe matrix1.mtx 
                         matrix2.mtx matrix_mpi.mtx" 
            IsCheckpointable="false" 
            IsExclusive="false" 
            IsRerunnable="false" 
            Runtime="00:00:12">
            <EnvironmentVariables /> 
        </Task>
    </Tasks>
</Job>

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

mpiexec -hosts %CCP_NODES% MatrixMultiplierMPI.exe

Переменная окружения CCP_NODES задает узлы и процессоры на каждом узле, которые выделены заданию планировщиком. Запуск этого задания на исполнение производится командой

job submit /f:MatrixMultiplierMPI.xml

Задание на исполнение с применением mpiexec можно также послать без использования XML-файла, задавая необходимые параметры в командной строке:

job submit /numprocessors:8 /runtime:5:0 myApplication.exe

Кроме того, Windows Compute Cluster Server предоставляет API (Application Programming Interface) для использования в программах на языке C# с помощью которого можно программно подсоединиться к кластеру, создавать задачи и задания, посылать задания на кластер, управлять заданиями, ресурсами, задачами, узлами и выполнять другие работы. Базовым интерфейсом в этом API является интерфейс ICluster, который предоставляет следующие основные методы:

• Connect
• CreatJob
• CreateTask
• AddTask
• SubmitJob

Дополнение. Введение в MPI

Цель - изучить базовую структуру MPI-программ и способ их запуска на кластере.

Базовая структура MPI-программ предполагает обязательное применение функций

• MPI_Init,
• MPI_Comm_size,
• MPI_Comm_rank и
• MPI_Finalize.

Их использование представлено в примере ниже.

Компиляция MPI-программ осуществляется утилитами

• mpicc ( для программ, написанных на языке С), или
• mpiCC ( для программ, написанных на языке С++).

Эти утилиты являются надстройками над соответствующими компиляторами, установленными в рамках ОС.

Пример запуска MPI-программы на компиляцию:

mpiCC myprog.cpp -o myprog

Запуск оттранслированной программы на счет производится с помощью команды вида:

mpirun   [параметры mpirun] <имя программы>
         [ входные параметры программы ]

Основными параметрами mpirun являются:

• -h | -help - показывает возможные аргументы и параметры команды mpirun
• - maxtime - задает максимальное время счета программы (в минутах)
• - np <число процессоров> - задает число процессоров, на которых запускается программа

Пример запуска

mpirun -np 4 -maxtime 5 myprog

Задача 1. Откомпилировать и выполнить программу, приведенную выше, задающую базовую структуру MPI-программ. Запустить программу на количестве процессоров от 1 до 4.

Задача 2. Написать и отладить MPI-программу, в которой корневой процесс (процесс с рангом 0) выдает на консоль количество запущенных процессов, а также сообщение

"Root process: Hello, world",

а все остальные процессы выдают сообщение

"Slave process: my rank is xxxx",

где xxx есть ранг соответствующего процесса.

Выполнить запуски программы на разном количестве процессоров.

Дополнение. Методы передачи данных типа "точка-точка" в MPI

Цель - изучить назначение и применение функций MPI_Send и MPI_Recv и их разновидностей для обмена данными между MPI-процессами

Наиболее часто используемыми блокирующими функциями передачи данных типа "точка-точка" являются функции MPI_Send и MPI_Recv.

Задача 1. Оттранслировать и запустить на выполнение с параметром -np 2 программу, показанную ниже, в которой процесс с номером 0 "пингует" (посылает тестовое сообщение, в данном случае, длины 1) процесс с номером 1, и ждет от него ответного сообщения.

Задача 2. Запустить данную программу с параметром -np N, где N > 2 и объяснить поведение MPI-процессов с рангом > 2.

Задача 3. Изменить программу из Задачи 1 так, чтобы процесс с номером 0 "пинговал" все процессы в группе (кроме, естественно, самого себя), посылая им однобайтовые сообщения и принимая от них такие же ответные сообщения.

Задача 4. Оттранслировать и запустить на выполнение программу, показанную ниже, в которой между соседними процессами, объединенными в кольцо, происходит обмен сообщениями, содержащими ранг посылающего процесса. Изучить по документации назначение и способы применения команд MPI_Isend, MPI_Irecv, MPI_Waitall.

Задача 5. Объяснить поведение программы при ее запуске с параметром -np 1.

Дополнение. Коллективные (радиовещательные) обмены данными между MPI-процессами

Цель - изучить назначение и применение функций обмена данными MPI_Bcast, MPI_Gather, MPI_Scatter и др. между MPI-процессами.

Отличия операций коллективного обмена данными от коммуникаций типа "точка-точка" состоят в следующем:

1. принимают/передают данные одновременно все процессы группы для указываемого коммуникатора;
2. операция коллективного обмена выполняет одновременно и прием, и передачу данных, а потому она имеет параметры, часть из которых относится к приему данных, а часть - к их передаче;
3. как правило, значения всех параметров (за исключением адресов буферов с данными) должны быть тождественны во всех процессах;
4. для сообщений передаваемых посредством коллективного обмена, идентификаторы (tags) назначаются автоматически; кроме того, сообщения передаются, в действительности, не по указываемому коммуникатору, а с помощью временного коммуникатора-дубликата, чем обеспечивается изоляция операций коллективной передачи данных друг от друга и от операций типа "точка-точка".

Задача 1. Реализовать рассылку сообщения от процесса с заданным рангом (этот ранг является входным параметром задачи) всем другим процессам в группе с помощью функции MPI_Bcast. Реализовать эквивалентный вариант программы, в котором вместо функции MPI_Bcast используются функции синхронной передачи данных MPI_Send и MPI_Recv.

Задача 2. Реализовать посылку сообщений (например, значений ранга) от всех процессов в группе, процессу с заданным рангом (этот ранг является входным параметром программы) с помощью функции MPI_Gather. Реализовать эквивалентный вариант программы, в котором вместо функции MPI_Gather используются функции синхронной передачи данных MPI_Send и MPI_Recv.

Задача 3. Оттранслировать и выполнить с параметром -np 4 программу, представленную ниже, в которой функция MPI_Scatter используется для рассылки строк матрицы чисел с плавающей точкой по отдельным процессам. Дополнить эту программу фрагментом, в котором отдельные процессы суммируют все элементы полученной строки и возвращают полученные результаты корневому процессу с помощью функции MPI_Gather.

Дополнение. Коллективные операции и их исполнение

Цель - изучить назначение и применение функций для выполнения коллективных операций MPI_Reduce, MPI_Allreduce, MPI_Reduce_scatter и MPI_Scan.

Схема выполнения коллективных операций MPI-процессами состоит в следующем.

Каждый MPI-процесс имеет вектор данных (чаще всего, числовой) с элементами определенного типа, например, MPI_INT. Функция коллективной операции (например, MPI_Reduce ) выполняет некоторую операцию, которая задается одним из аргументов этой функции, над нулевыми ячейками всех векторов, над первыми ячейками, и т.д.

Функции MPI_Reduce, MPI_Allreduce, MPI_Reduce_scatter и MPI_Scan, выполняющие такого рода коллективные операции, отличаются друг от друга только способом размещения результата операции в MPI-процессах.

Задача 1. Реализовать программу следующего содержания:

Объяснить поведение программы (в частности, содержимое вектора result ) при запуске программы с np - N при различных N.

Задача 2. Модифицировать предыдущую программу, заменив операцию MPI_Reduce на MPI_Allreduce, и предусмотрев печать содержимого вектора result в каждом из процессов.

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

Задача 3. Реализовать программу, которая

1. рассылает строки исходной прямоугольной матрицы по процессам;
2. находит максимальный элемент в каждом столбце этой матрицы,
3. умножает все элементы i-ой строки матрицы на максимальный элемент i -го столбца,
4. собирает полученную матрицу в процессе с номером 0, который ее распечатывает.

Дополнение. Управление процессами в MPI

Цель - изучить понятия "группа" и "коммуникатор" и средства их создания и управления ими в MPI-программах.

Типичный сценарий формирования новых групп MPI-процессов на основе исходной глобальной группы MPI_COMM_WORLD и организации взаимодействия внутри новых групп состоит из следующих шагов:

1. Получить обработчик глобальной группы, связанной с коммуникатором MPI_COMM_WORLD, используя функцию MPI_Comm_group.
2. Создать новую группу как подмножество глобальной группы, используя функцию MPI_Group_incl.
3. Создать новый коммуникатор для вновь созданной группы, используя функцию MPI_Comm_create.
4. Получить новый ранг процесса во вновь созданном коммуникаторе, используя функцию MPI_Comm_rank.
5. Выполнить обмен сообщениями между процессами в рамках вновь созданной группы.
6. По окончании работы, освободить (уничтожить) группу и коммуникатор, используя функции MPI_Group_free и MPPI_Comm_free.

Схематически, такой сценарий можно представить следующим рисунком:

Задача 1. Реализовать следующую программу, в которой организуется две группы процессов для выполнения коллективной операции внутри каждой из групп.

Запустить на выполнение данную программу с ключом -np 8. Объяснить результаты работы программы, выводимые на консоль.

Задача 2. Модифицировать текст предыдущей программы таким образом, чтобы

• в рамках первой группы выполнялась коллективная операция MPI_MIN, и результат помещался в процесс с наименьшим рангом в глобальной (исходной) группе и распечатывался им, и
• в рамках второй группы выполнялась коллективная операция MPI_MAX, и результат помещался в процесс с наибольшим рангом в глобальной (исходной) группе и распечатывался им.

Дополнение. Организация логических топологий процессов

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

В MPI поддерживается два основных типа виртуальных топологий:

• декартова (решеточная) и
• графовая.

Обе эти топологии строятся на основе групп и коммуникаторов и "программируются" разработчиком параллельного приложения.

Задача 1. В программе, представленной ниже, 16 процессов объединяются в декартову топологию 4 х 4:

В программе, каждый процесс обменивается своим рангом с четырьмя соседними процессами, где для процесса с координатами (i, j) его соседями считаются процессы с координатами

( i - 1, j ),
( i,  j - 1 ),
( i, j + 1 ),
( i + 1, j + 1 ),

если их координаты не выходят за пределы заданной декартовой решетки.

Оттранслировать, выполнить и объяснить выданный результат для программы, представленной ниже.

увеличить изображение

Задача 2. Пусть для процесса с координатами (i, j) его соседями считаются процессы с координатами

( i - 1, j - 1 ),
( i - 1, j + 1 ),
( i + 1, j - 1 ),
( i + 1, j + 1 ).

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

Дополнение. Разработка сложных параллельных программ с использованием MPI

Цель - изучить параллельный алгоритм Фокса перемножения матриц и реализовать его с применением MPI; получить экспериментальные данные о масштабируемости данного алгоритма.

В данном занятии изучаются 2 параллельных алгоритма перемножения матриц:

• с декомпозицией по строкам,
• с блочной декомпозицией.

Ниже в тексте предполагается, что матрицы являются квадратными порядка N (т.е., они являются N х N матрицами). Тип элементов матриц может быть выбран произвольным - целочисленный, с плавающей точкой, с плавающей точкой двойной точности, и т.п.

Задача 1. Требуется реализовать параллельный алгоритм перемножения матриц с использованием декомпозиции по строкам. Пусть даны исходные матрицы A, B, а C является результирующей матрицей, т.е., C = A x B.

Предполагается, что для матриц порядка N алгоритм выполняется на N процессорах. Соответственно, i -ая строка матриц A,B назначается процессору i, и процессор i ответственен за вычисление i -ой строки результирующей матрицы C.

Суть алгоритма заключается в нахождении элемента с координатами (i, j) результирующей матрицы С процессом с номером i путем вычисления "поточечного" (скалярного) произведения строки i матрицы А и столбца j матрицы B. Для вычисления этого произведения, процессу i понадобится весь столбец j матрицы B, что может быть реализовано путем применения операции MPI_Allgather во всех процессах:

Альтернативное применению MPI_Allgather может быть решение с предварительной рассылкой всей матрицы B всем процессам.

Оттранслировать и выполнить полученную программу для матриц размером 10x10 с использованием 10 процессоров ( -np 10 ).

Дополнительную информацию об этом алгоритме можно получить со страницы http://www.abo.fi/~Mats.Aspnas/PP2006/handouts/Chapter4.pdf

Задача 2. Требуется реализовать параллельный алгоритм перемножения матриц с блочной декомпозицией (алгоритм Фокса).

В данном алгоритме предполагается, что матрицы размерности N x N распределяются между P процессами, которые организованы в виде декартовой решетки (квадрата) со стороной vP.

Предполагается, что N делится без остатка на vP, а потому каждый процесс хранит подматрицы размерности N' x N', где

N' = N / vP.

Например, при N = 16, т.е., матрицах размерности 16 x 16, и P = 4, т.е., для решетки процессоров 2 х 2, каждый процесс хранит подматрицы размером 8 х 8 исходных матриц A, B, и ответственен за вычисление соответствующей подматрицы результирующей матрицы С.

Пусть A_ij является подматрицей размерности N' x N' матрицы A, первым элементом которой является элемент A [ i * N', j * N' ] (аналогично для подматриц B_ij и C_ij ). Подматрицы A_ij, B_ij и C_ij назначаются процессу с номером (i, j). Тогда алгоритм работы процесса с номером (i, j) состоит в следующем:

Реализация данного алгоритма в виде MPI-программы показана ниже:

увеличить изображение

Оттранслировать и выполнить данную программу для матриц размерности 100х100 с использованием 16 процессоров ( -np 16 ).

Дополнение. Отладка MPI-программ с использованием Visual Studio 2005

Цель - изучить настройку конфигурационных параметров для отладки MPI-приложений в рамках Visual Studio 2005; изучить способы задания точек остановки (breakpoints) для отдельных и множеств MPI-процессов.

Отладка MPI-программ с использованием Visual Studio 2005 состоит, в общем случае, из трех шагов:

1. запуска удаленного отладчика (a remote debugger) на узлах, зарезервированных для сеанса отладки;
2. конфигурирования отладочных свойств проекта MPI-приложения в рамках Visual Studio;
3. запуска приложения в режиме отладки и просмотра процессов в точках их остановки (breakpoints).

Задача 1. Запустить удаленный отладчик msvsmon.exe на нескольких узлах (допустим, имеющих имена Node1, Node2, Node3, Node4 ) сформировав и запустив следующее задание с использованием интерфейса командной строки:

job new /jobname:ReserveTimeForDebug /askednodes:Node1,Node2,Node3,Node4 /runtime:00:05:00 /rununtilcancelled:true /scheduler:myCluster 
job add <JobID> /requirednodes:Node1 C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64\msvsmon.exe
job add <JobID> /requirednodes:Node2 C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64\msvsmon.exe
job add <JobID> /requirednodes:Node3 C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64\msvsmon.exe
job add <JobID> /requirednodes:Node4 C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64\msvsmon.exe 
job submit /id:<JobID>

Листинг 2. (html, txt)

Задача 2. В качестве примера отлаживаемой программы, здесь предполагается программа из Занятия 9 перемножения матриц с декомпозицией по строкам.

Необходимо открыть данную программу в рамках Visual Studio, и на странице Properties проекта выбрать последовательно

Configuration Properties -> Debugging,

и в списке Debugger to launch выбрать MPI Cluster Debugger.

На этой же странице, необходимо заполнить соответствующие поля (MPIRun Command, MPIRun Arguments, MPIShim location и др.) нужными значениями для старта приложения.

Из основного меню Visual Studio 2005, выбрать последовательно

Tools -> Options

чтобы открыть диалоговое окно для задания точек остановки (breakpoints).

Необходимо установить точку остановки в программе после выполнения команды MPI_Allgather, и заново построить приложение.

Задача 3. Запустить вновь построенное приложение в режиме отладки, нажав F5. После остановки программы, нажать Ctrl+Alt+Z для открытия окна Processes. Выбрать один из параллельных процессов и просмотреть значения его переменных.

Проверить пошаговое выполнение программы, начиная с точки остановки, используя соответствующие клавиши на панели окна Processes (см. рисунок):

увеличить изображение

Дополнение. Введение в высокоуровневый язык параллельного, распределенного программирования MC#

Цель - изучить модель программирования языка MC# и его специфические конструкции: async- и movable-методы, каналы, обработчики и связки

Высокоуровневый язык параллельного, распределенного программирования MC# предназначен для написания программ, работающих на всем спектре параллельных архитектур - от многоядерных процессоров до Grid-сетей. В случае, когда параллельная программа разрабатывается для исполнения на кластерах или Grid-сети, то она называется параллельной, распределенной программой.

Для исполнения MC#-программ, на машинах должна быть установлена среда исполнения CLR (Common Language Runtime) с соответствующим набором библиотек. На машине с операционной системой Windows, реализацией такой системы является Microsoft .NET Framework, а на машинах с операционной системой Linux - система Mono (http://www.mono-project.com).

Ключевая особенность языка MC# заключается в добавлении к обычным, синхронным методам, так называемых "асинхронных" методов, которые отмечаются в MC#-программах ключевым словом async (а в случае распределенных программ - ключевым словом movable ). При их вызове, происходит порождение нового потока (thread), в котором выполняется вызванный асинхронный метод.

Взаимодействие асинхронных методов в MC#-программе осуществляется с помощью передачи сообщений с использованием специальных средств - каналов и обработчиков канальных сообщений, выделенных в специальные синтаксические категории языка MC#: channels и handlers, соответственно.

Задача 1. Оттранслировать и выполнить, задавая различные значения входного параметра, программу вычисления n-го числа Фибоначчи:

Трансляция MC#-программ осуществляется командой:

mcsc <имя программы>.mcs

Запуск на выполнение осуществляется

• в Windows, командой

  <имя программы> <входные параметры>

• в Linux, командой

  mono <имя программы>.exe  <входные параметры>

Объяснить, почему при рекурсивных вызовах программы, необходимо создание новых объектов класса Fib.

Задача 2. Оттранслировать и выполнить модифицированный вариант программы вычисления чисел Фибоначчи с порогом для локального вычисления (см. текст программы ниже):

увеличить изображение

Если задание выполняется на машине, имеющей два или более ядра (процессора), то для входного параметра n = 40, подобрать оптимальное значение порога, при котором время исполнения программы будет наименьшим.

Задача 3. Оттранслировать и выполнить программу вычисления чисел Фибоначчи с линейным порождением рекурсивных вызовов:

увеличить изображение

Если задание выполняется на многоядерной (многопроцессорной) машине, то сравнить время выполнения данного варианта программы с вариантом из Задачи 2 при запуске с N = 40 и одинаковым порогом для обеих программ.

Объяснить полученное время выполнения для этих вариантов по сравнению друг с другом.

Дополнение. Многопоточное программирование на языке MC#

Цель - изучить назначение и применение async-методов языка MC# и сравнить их с традиционными средствами многопоточного программирования .NET

Для создания многопоточных приложений, предназначенных для исполнения на многоядерных (многопроцессорных) машинах, в языке MC# используются асинхронные методы. Они являются единственным средством создания параллельных процессов (потоков) в этом языке (если не считать movable-методов, которые являются "распределенными" аналогами локальных асинхронных методов).

Общий синтаксис определения асинхронных методов в языке MC# следующий:

Задание ключевого слова async при определении некоторого метода означает, что при вызове данного метода он будет запущен в идее отдельного потока локально, т.е., на машине, где произошел его вызов (возможно, на отдельном ядре/процессоре). В систему исполнения (Runtime-систему) языка MC# встроена подсистема автоматической балансировки нагрузки, которая на основе оценки загруженности процессоров машины, привязывает порождаемый поток (асинхронный метод) к наименее загруженному процессору.

Отличия асинхронных методов от обычных состоят в том, что

• вызов async-методов заканчивается, по существу, мгновенно (время тратится только на запуск нового потока),
• async-методы никогда не возвращают результатов (для взаимодействия async-методов между собой и другими частями программы в языке MC# предусмотрены специальные средства - каналы и обработчики канальных сообщений).

Задача 1. Написать на языке MC# параллельную программу перемножения двух матриц с использованием async-методов.

Каждый async-метод должен вычислять свою часть - стрoки - результирующей матрицы, где количество этих строк определяется числом N / P, где N - количество строк в результирующей матрице, P - количество асинхронных методов.

Для обнаружения момента окончания async-методов необходимо завести специальный объект с внутренним счетчиком (некоторой целочисленной переменной). Этот счетчик (при предварительном блокировании объекта, которому он принадлежит) наращивается каждым async-методом при завершении его работы, а главная программа с заданным интервалом проверяет значение этого счетчика.

Если задание выполняется на многоядерной (многопроцессорной) машине, сравнить время исполнения последовательного варианта программы с параллельным, где в последнем число асинхронных методов равно числу доступных ядер/процессоров.

Задача 2. Разработать параллельную программу перемножения двух матриц с использованием стандартных средств многопоточного программирования в .NET, а именно с использованием класса Thread. Для обнаружения момента завершения работы потоков, воспользоваться либо методом из Задачи 1 данного задания, либо командой Join класса Thread.

Сравнить время выполнения данной программы с эквивалентным вариантом из Задачи 1, написанным на языке MC#.

Дополнение. Использование каналов и обработчиков языка MC# для организации взаимодействия параллельных потоков (процессов)

Цель - изучить синтаксические конструкции каналов и обработчиков языка MC# и правила их определения; рассмотреть правила работы Runtime-системы языка с ними.

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

В рамках многопоточного программирования, эти средства являются более высокоуровневыми и удобными в использовании, чем стандартные средства языка C# и платформы .NET, которрдЄZQVрдЄZQVЂvZQV0‹ўZQVXеЄZQVеЄZQV@еЄZQVявляются в MC#-программах с помощью специальных конструкций - связок (chords). Синтаксические правила определения связок в языке MC# имеют вид:

Связки определяются в виде членов класса. По правилам корректного определения, каналы и обработчики не могут иметь модификатор static, а потому они всегда привязаны к некоторому объекту класса, в рамках которого они объявлены.

Одна из ключевых особенностей языка MC# состоит в том, что каналы и обработчики могут передаваться в качестве аргументов методам отдельно от объектов, которым они принадлежат.

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

Задача 2. Написать параллельную программу, в которой два асинхронных метода поочередно печатают сообщения на выходной консоли.

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

Дополнение. Средства синхронизации параллельных процессов в языке MC#

Цель - изучить правила определения и использования связок (chords) в языке MC#; рассмотреть возможные типы связок и их влияние на поведение программы.

Главным и единственным средством синхронизации параллельных потоков (процессов) в языке MC# являются связки (chords). Они, в общем случае, состоят из обработчика и нескольких каналов (хотя возможно объявление связок, состоящих только из каналов, в частности, одного канала).

Типичный пример связки представлен ниже:

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

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

Задача 1. Написать программу на языке MC#, в которой порождаются три async-метода, и которым для посылки сигнала об окончании их работы передается специально определенный для этого канал.

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

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

Задача 2. Написать программу на языке MC#, в которой имеется канал, разделяемый между двумя обработчиками, вида:

Реализовать в программе циклическую (многократную) посылку сообщений в каналы в последовательности

C1 ; C3; C2,

а также соответствующий циклический вызов обработчиков h1 и h2 из различных async-методов.

Объяснить полученные результаты.

Дополнение. Разработка сложных параллельных программ на языке MC#

Цель - изучить параллельный алгоритм вычисления частичных сумм массива чисел и реализовать его на языке MC#.

На данном занятии, требуется реализовать программу на языке MC#, решающую задачу вычисления частичных сумм массива f длины n.

А именно, по заданному массиву чисел f [ 0 : n-1 ] необходимо построить массив h [ 0 : n-1 ], такой что

Идея параллельного решения этой задачи состоит в разбиении массива f на p сегментов, где n кратно p, с дальнейшей одновременной обработкой этих сегментов данных длины m = n div p. Таким образом, обработка каждого сегмента будет производиться movable -методом.

(Отметим, что приведенное ниже решение пригодно и для случая, когда n не кратно p. Соответствующее обобщение может рассматриваться в качестве упражнения).

Разбиение исходного массива f на p сегментов производится таким образом, что в сегмент q, где ( 0 <= q < p ) попадают элементы f [ i ], такие что i mod p = q.

Так, например, если n = 16 и p = 4, то

0 -ой сегмент составят числа f [ 0 ], f [ 4 ], f [ 8 ], f [ 12 ] ;

1 -ый сегмент составят числа f [ 1 ], f [ 5 ], f [ 9 ], f [ 13 ]

и т.д.

Параллельный алгоритм вычисления частичных сумм будет устроен так, что q -му процессу ( movable -методу), обрабатывающему q -ый сегмент данных, достаточно будет общаться лишь с его соседями слева и справа (соответственно, 0 -му процессу - лишь с соседом справа, а последнему, (p-1) -му процессу - лишь с соседом слева) и главной программой для возврата результатов. Процесс с номером q будет вычислять все элементы h [j] результирующего массива, такие что j mod p = q, где 0 <= j < n.

Фрагмент главной программы, разбивающей исходный массив на сегменты и вызывающий movable -метод handleSegment, показан ниже. Здесь первым аргументом этого метода является номер сегмента, а последним - имя канала для возврата результатов.

Объекты класса BDChannel объявляются следующим образом :

Схема взаимодействия процессов ( movable -методов) между собой и главной программой показана ниже:

После разбиения, исходный массив f приобретает вид двумерной матрицы, распределенной по p процессам:

процесс 0:	a0,0	a0,1	…	a0,m-1
процесс 1:	a1,0	a1,1	…	a1,m-1
...	…	…	…	…
процесс q:	aq,0	aq,1	…	aq,m-1
…	…	…	…	…
процесс p-1:	ap-1,0	ap-1,1	…	ap-1,m-1

Другими словами, эта матрица получена из массива f разрезанием его на p сегментов и транспонированием каждого сегмента.

Ключевая идея алгоритма отдельного процесса q состоит в заполнении локальных для него массивов h0 и h1 (оба, имеющие размерность m ) в соответствии с формулами:

Неформально, это означает, что для процесса с номером q i -ый элемент массива h0 есть сумма всех элементов приведенной выше матрицы, которые расположены выше и слева элемента a_q,i (включая и элементы столбца i ).

Аналогично, i -ый элемент массива h1 есть сумма всех элементов матрицы, которые расположены ниже и слева элемента a_q,i (но, не включая элементов из столбца i ).

Ниже показана иллюстрация этого принципа для n = 16, p = 4 и q = 1, i = 2.

После того, как вычислены массивы h0 и h1 (посредством взаимодействия с соседними процессами), процесс с номером q может вычислить элемент h[i * p + q] результирующего массива как

Получаемые результирующие m значений процесс q сохраняет в локальном массиве h для передачи их главной программе. Тогда общая схема movable -метода handleSegment выглядит следующим образом:

Фрагмент программы, вычисляющий массив h0, приведен ниже.

Дополнение. Распределенное программирование на языке MC#

Цель - изучить структуру Runtime-системы языка MC# для поддержки распределенных вычислений, процедуры загрузки и остановки Runtime-системы и особенностей распределенного программирования на примере программы All2all.

Под распределенным программированием на языке MC# понимается разработка программ, которые будут исполняться на кластере или (Grid-) сети машин.

Ключевым средством языка MC# для порождения параллельных процессов, которые могут исполняться распределено (т.е., на удаленных машинах), являются movable-методы. Movable-методы - это методы классов языка MC#, которые помечены ключевым словом movable и при вызове которых, система исполнения программ на языке MC# (Runtime-система) планирует и переносит этот метод для исполнения на удаленную машину (обычно, выбираемую исходя из принципа наименьшей ее загруженности среди всех доступных машин).

Прежде чем распределенные программы могут быть запущены, необходимо загрузить Runtime-систему языка MC# командой

mcsboot <имя конфигурационного файла>

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

Остановка Runtime-системы производится командой

mcshalt

Одной из ключевых особенностей языка MC# является то, что, в общем случае, во время вызова movable-метода, все необходимые данные, а именно

1. сам объект, которому принадлежит данный movable-метод, и
2. его аргументы (как ссылочные, так и скалярные значения)

только копируются (но не перемещаются) на удаленную машину. Следствием этого является то, что все изменения, которые осуществляет movable-метод с внутренними полями объекта, проводятся с полями объекта-копии на удаленной машине, и не переносятся на исходные объекты.

Задача 1. Оттранслировать и выполнить программу

и объяснить ее результаты, выдаваемые на печать, а именно, значения переменной x до и после вызова movable-метода Compute.

Другая ключевая особенность языка MC# состоит в том, что в распределенном режиме, при копировании каналов и обработчиков на удаленную машину автономно (т.е., в качестве аргументов movable-методов) или в составе некоторого объекта, они становятся прокси-объектами, или посредниками для оригинальных каналов и обработчиков. Как обычно, все действия с прокси-объектами перенаправляются Runtime-системой на исходные каналы и обработчики.

Задача 2. Оттранслировать и выполнить в распределенном режиме программу All2all, представленную ниже.

В этой программе демонстрируется взаимодействие множества распределенных процессов между собой по принципу "каждый с каждым". Перед началом такого взаимодействия, каждый распределенный процесс из этого множества создает собственный объект класса BDChannel, который служит для взаимодействия с другими процессами множества. Взаимообмен такими объектами происходит через главную программу. Имея объекты BDChannel других процессов, процесс может воспользоваться каналом Send и обработчиком Receive этих объектов (точнее, их прокси-объектов) для посылки сообщений другим процессам и приема сообщений от них.

---