WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
Введение в параллельное программирование на языке MC# Сердюк Ю. П. ( Yury@serdyuk.botik.ru ) Институт программных систем РАН, г. Переславль-Залесский Переславль-Залесский 2007 2 Содержание Содержание.......................................................................................................................................2 1. Введение.........................................................................................................................................3 2. Новые средства языка MC#: async- и movable-методы, каналы и обработчики............7 1.1. ASYNC- И MOVABLE-МЕТОДЫ......................................................................................................................... 8 1.2. КАНАЛЫ И ОБРАБОТЧИКИ.............................................................................................................................. 10 3. Программирование на языке MC#.........................................................................................16 3.1 ВЫЧИСЛЕНИЕ ЧИСЕЛ ФИБОНАЧЧИ................................................................................................................ 16 3.2 ОБХОД БИНАРНОГО ДЕРЕВА........................................................................................................................... 19 3.3 БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ.............................................................................................................. 21 3.4 ПОСТРОЕНИЯ СПИСКА ПРОСТЫХ ЧИСЕЛ МЕТОДОМ “РЕШЕТА ЭРАТОСФЕНА”.............................................. 24 3.4.1 Наивный алгоритм................................................................................................................................. 24 3.4.2 Пакетный алгоритм............................................................................................................................... 27 3.5 ПРОГРАММА ALL2ALL..................................................................................................................................... Литература......................................................................................................................................Приложение..................................................................................................................................... 1. Введение Широкое распространение вычислительных систем с массовым параллелизмом, таких как многоядерные процессоры, кластеры и GRID-архитектуры, с особой остротой поставило вопрос о разработке высокоуровневых, мощных и удобных в использовании языков программирования, позволивших бы создавать сложное, но, одновременно и надежное программное обеспечение, эффективно использующее возможности параллельных, распределенных вычислений и легко масштабируемое на заданное число процессоров (ядер), узлов или машин.

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

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

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

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

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

Введение новых конструкций для параллельного программирования – асинхронных методов и связок (chords) в язык Polyphonic C#, который является расширением языка C#, позволяет обойтись без библиотеки System.Threading, которая обычно требуется для реализации мультипоточных приложений в рамках.NET. С другой стороны, введение новых конструкторов типов данных (потоков (streams), анонимных структур, разделенных объединений (discriminated unions) и др.) вместе с соответствующими средствами определения запросов в язык C [L3] (которые, вначале, вошли в проект 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 [L4], который ориентирован как на многоядерные, так и на “неоднородные кластерные вычисления”. Разработка языка X10 является частью совместного проекта PERCS (Productive Easy-to-use Reliable Computer Systems) фирмы IBM с несколькими академическими партнерами. Этот проект нацелен на создание к 2010г. новых масштабируемых систем, которые должны обеспечить десятикратное увеличение продуктивности работы программистов при разработке параллельных приложений [L5].

В данном учебном введении рассматриваются основы программирования на языке MC#, предназначенном для написания программ, работающих на всём спектре параллельных архитектур – от многоядерных процессоров до Grid-сетей. Единственное требование к таким системам со стороны MC# - на них должна быть установлена среда исполнения CLR (Common Language Runtime) с соответствующим набором библиотек. На машинах с операционной системой Windows реализацией такой среды является Microsoft.NET Framework, а на машинах с операционной системой Linux – система Mono (www.monoproject.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# производит сериализацию/десериализацию пересылаемых объектов автоматически.

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

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

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

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

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

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

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

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

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

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

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

модификаторы { async | movable } имя_метода ( аргументы ) { < тело метода > } Ключевые слова async и movable располагаются на месте типа возвращаемого значения, поэтому синтаксическое правило его задания при объявлении метода в языке MC# имеет вид:

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.