Расширение объектно-ориентированных языков программирования параллельными конструкциями для многопроцессорных и распределенных систем Гузев Вадим Борисович

2 Мультипроцессорность повсюду…

3 Типичная картина при выполнении программ…

4 2 подхода к созданию параллельных языков Создание специализированных параллельных языков Расширение существующих языков программирования параллельными конструкциями

5 Цель работы Поддержка параллельного программирования для многопроцессорных и распределенных систем на базе существующих широко распространенных объектно- ориентированных языков программирования.

6 Нужны языки, в которых… обеспечивалось абстрагирование от физической среды исполнения; распределение нагрузки обеспечивалось системой времени исполнения; обеспечивалась автоматическая передача по сети сложноустроенных в памяти объектов; поддерживались синтаксические конструкции для синхронизации параллельных потоков. Ну и самое главное - язык должен быть лёгким для понимания и обучения!

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

8 Язык MC# - адаптация основной идеи языка Polyphonic C# на случай распределенных вычислений

9 Связки из Polyphonic C# Связка срабатывает только тогда, когда все методы объявленные в связке были вызваны! В данном примере для срабатывания связки должны быть вызваны Get(), c1() и c2() Связки – средство синхронизации потоков вычисления

10 Каналы и обработчики канальных сообщений MC#

11 3 типа функций в MC#

12 Недостатки языка MC# Затруднена возможность использования legacy-кода базового языка

13 Parallel C#

14 Объекты функциональных типов Предположим, что имеется некоторая функция: long square( int x ) { return x * x; } Либо инициализировать ссылкой на функцию: (int) => long fun2 = square; Console.WriteLine( fun2( 2 ) ); Объекты функциональных типов можно передавать другим функциям: void fun1( (int) => long s ) { Console.WriteLine( s( 2 ) ); } … fun1( square ); Сигнатура данной функции: (int) => long

15 Автоматическая генерация прокси-функций

16 Технология расширения языков программирования , 4

17 Реализация

18 Реализация На данный момент на сайте проекта доступны два вида систем исполнения, оформленные как проект с открытым исходным кодом: Parallel C# Many Core Edition – система программирования, позволяющая компилировать и исполнять программы в локальном режиме на Windows-машинах. Parallel C# Cluster Edition – система программирования, позволяющая компилировать и исполнять программы на Linux-кластерах.

19 Пример: вычисление чисел Фибоначчи fib(1) = 1; fib(2) = 1; fib(n) = fib(n - 1) + fib(n - 2) public class Fib { public long Get2() & async Result1(long x) & async Result2(long y) { return x + y; } long Get() & async Result(long x) { return x; } async Compute(long n, (long) => async result) { if (n < 2) result(n); else { Fib f = new Fib(); f.Compute(n - 1, f.Result1); f.Compute(n - 2, f.Result2); result(f.Get2()); } public static void Main(string[] args) { int n = int.Parse(args [0]); Fib fib = new Fib(); fib.Compute(n, fib.Result); Console.WriteLine("Fibonacci " + n + " is " + fib.Get()); }

20 Пример: вычисление чисел Фибоначчи fib(1) = 1; fib(2) = 1; fib(n) = fib(n - 1) + fib(n - 2)

21 Пример: вычисление чисел Фибоначчи (распределенный вариант) public class Fib { public long Get2() & async Result1(long x) & async Result2(long y) { return x + y; } long Get() & async Result(long x) { return x; } movable Compute(long n, (long) => async result) { if (n < 2) result(n); else { Fib f = new Fib(); f.Compute(n - 1, f.Result1); f.Compute(n - 2, f.Result2); result(f.Get2()); } public static void Main(string[] args) { int n = int.Parse(args [0]); Fib fib = new Fib(); fib.Compute(n, fib.Result); Console.WriteLine("Fibonacci " + n + " is " + fib.Get()); }

22 Пример: вычисление чисел Фибоначчи (распределенный вариант)

23 Пример: перемножение матриц public async Multiply( int N, double[,] A, double[,] B, double[,] C, int from, int to, () => async stop ) { for ( int i = from; i < to; i++ ) for ( int j = 0; j < N; j++ ) for ( int k = 0; k < N; k++ ) C [i, j] += A [i, k] * B [k, j]; stop(); } … public class Program { public static void Main( string[] args ) { int N = System.Convert.ToInt32( args [0] ); double[,] A = new double [N, N], B = new double [N, N], C = new double [N, N]; ReadMatrix( A, B ); Program p = new Program(); int N2 = N / 2; p.Multiply( N, A, B, C, 0, N2, p.stop ); p.Multiply( N, A, B, C, N2, N, p.stop ); p.getStop(); p.getStop(); WriteMatrix(C); } public void getStop() & async stop() { return; } }

24 Пример: перемножение матриц Перемножение матриц на языке Parallel C#, по сравнению с версией на языке C#. Замеры делались на компьютере с процессором Intel Core 2 CPU система Parallel C# Many Core Edition, ОС: Windows XP

25 Пример: поиск вхождений слов в текст public class Program { static void Main( string[] args ) { Program p = new Program(); // число используемых процессоров в кластере int np = CommWorld.Size; string[] words = ReadTheWords( args [0] ); int n = Math.Min( words.Length, np ); int portion = words.Length / n; // отправка порции слов на обработку for( int i = 0; i < n; i++ ) { string[] chunkOfWords = new string [portion]; Array.Copy( words, i * portion, chunkOfWords, 0, portion); p.Map( args [1], chunkOfWords, p.Reduce ); } for ( int i = 0; i < n; i++ ) p.Pulse(); PrintTheResult( p.dic ); } Hashtable dic = new Hashtable(); … movable Map(string fileName, string[] words, (string[], int[]) => async Reduce) { int[] counts = new int [words.Length]; using ( FileStream file = new FileStream( fileName, FileMode.Open, FileAccess.Read ) ) { TextReader tr = (TextReader) new StreamReader( file ); string line = tr.ReadLine(); while ( line != null ) { for ( int j = 0; j < words.Length; j++ ) counts[j] += Regex.Matches( line, words[j] ).Count; line = tr.ReadLine(); } Reduce( words, counts ); } void Pulse() & async Reduce( string[] words, int[] counts ) { for ( int i = 0; i < words.Length; i++ ) dic.Add( words [i], counts [i] ); }

26 Примеры: поиск вхождений слов в текст Поиск 32 слов в тексте размером 64 Mb на разных количествах процессоров (кластер СКИФ «Первенец-М»)

27 ||-исчисление ||-исчисление – модификация формального исчисления для языка MC# 2.0 [Y.Serdyuk,A formal basis for the MC# programming language]. Основные отличия следуют из: Отправка сообщений => вызовы методов Каналы => асинхронные методы Хендлеры => синхронные методы

28 Семантика ||-исчисления (1/2)

29 Семантика ||-исчисления (2/2)

30 Основные выводы (1/3) Предложена технология расширения существующих объектно-ориентированных языков программирования с помощью следующего набора элементов: асинхронных и перемещаемых методов, функциональных типов объектов, связок асинхронных и синхронных методов, автоматической генерации прокси-функций и автоматической стерилизации и дестерилизации объектов при пересылке между виртуальными узлами. Описан формальный базис для получаемого семейства языков (||-исчисление). Разработаны правила трансляции новых синтаксических конструкций в базовые языки и представлена в качестве демонстрации практическая реализация данных правил на примере языка Parallel C# (расширение существующего языка C#). Стоит отметить, что с помощью данных конструкций можно расширить многие другие языки программирования, например, Java, Nemerle и др.

31 Основные выводы (2/3) Разработаны транслятор и две системы исполнения для языка Parallel C# - для многопроцессорных и кластерных архитектур. Реализованы тестовые программы и произведены замеры производительности этих программ на кластере, показавших приемлемый уровень ускорения на разном числе процессоров.

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

33 Апробация работы Журнал Информационные технологии (входит в список ВАК), 4, 2008 г. PDPTA'08 - The 2008 International Conference on Parallel and Distributed Processing Techniques and Applications, Monte Carlo Resort, Las Vegas, Nevada, USA, July 14-17, 2008 XLIV Всероссийской Конференции по Проблемам Математики, Информатики, Физики и Химии, секция Программные Системы, г. Москва, Российский Университет Дружбы Народов, апреля 2008 г. C# and.NET Technologies'2003, 1st International Workshop on C# and.NET Technologies on Algorithms, Computer Grafics, Visualilization, Distributed and WEB Computing, University of West Bohemia, Plzen, Czech Republic, 5-7 February, 2003 Технологии Microsoft в научных исследованиях и высшем образовании, Научно- техническая конференция по программированию, Москва, июня, 2003 г. Международная конференция PACT'2003, Нижний Новгород, Россия, сентября 2003 XII-ой международной конференции по вычислительной механике и современным прикладным программным системам, г. Владимир, Россия, 30 июня - 5 июля 2003 г. II-й Белорусский космический конгресс, октября 2005 г., Минск Всероссийская научная конференция "Научный сервис в сети Интернет: технологии распределенных вычислений, г. Новороссийск, сентября 2005 г. Материалы исследования базируются на тезисах докладов и опубликованных статьях, получивших положительную оценку в различных научных форумах/журналах:

34 Основные публикации Guzev V. Parallel C#: The usage of chords and higher-order functions in the design of parallel programming languages. In proc. of "The 2008 International Conference on Parallel and Distributed Processing Techniques and Applications", Las Vegas, USA, CSREA Press, 2008, p Гузев В.Б. Использование связок и функций высшего порядка для разработки языков параллельного программирования. Труды XLIV Всероссийской Конференции по Проблемам Математики, Информатики, Физики и Химии, секция "Программные Системы", М.:Изд-во РУДН, 2008, c

35 Спасибо за внимание! Адрес проекта Parallel C#:

36 Сравнение MC# и Parallel C# (1/4) 1. Вместо каналов и обработчиков сообщений используется единообразный формат описания асинхронных и синхронных методов: MC#: handler GetResult long() & channel SendResult( long result ) { return result; } Parallel C#: long GetResult() & async SendResult( long result ) { return result; }

37 Сравнение MC# и Parallel C# (2/4) 2. Т.к. в качестве базовой операции используется вызов метода, то отсутствует необходимость в дополнительных операторах для отправки и получения сообщений (! и ?): MC#: movable Fun( int x, handler long (int) square, channel(long) sendResult ) { sendResult ! ( (long) square ? ( x ) ); } Parallel C#: movable Fun( int x, (int) => long square, (long) => async sendResult ) { sendResult( square( x ) ); }

38 Сравнение MC# и Parallel C# (3/4) 3. Parallel C# - строго типизированный язык (нет необходимости приводить типы при обмене данными между узлами): MC#: movable Fun( int x, handler long (int) square, channel(long) sendResult ) { sendResult ! ( (long) square ? ( x ) ); } Parallel C#: movable Fun( int x, (int) => long square, (long) => async sendResult ) { sendResult( square( x ) ); } (long)

39 Сравнение MC# и Parallel C# (4/4) 4. В Parallel C# реализована возможность запуска статических перемещаемых функций (соответственно отпала необходимость в ключевом слове functional и в создании инстанса объекта): MC#: functional movable Fun( … ) { … } MyProgram prog = new MyProgram(); prog.Fun(…); Parallel C#: static movable Fun( … ) { … } MyProgram.Fun( … );

40 Грамматика (обозначения) o – имена объектов sm – синхронные методы, am – асинхронные методы, mm – перемещаемые методы s, r – имена сайтов конечный список выражений обозначается как:

41 Грамматика (1/2)

42 Грамматика (2/2)