1

2 Язык параллельного программирования MC# Сердюк Ю.П. декабрь 2010г.

3 История π-исчисление (R.Milner) join-исчисление (C.Fournet,G.Gonthier) Polyphonic C# (N.Benton, L.Cardelli,C.Fournet) JoCaml MC#

4 Асинхронная модель программирования Join-модель параллельного программирования, - N.Benton, L.Cardelli, C.Fournet Modern concurrency abstractions for C#, - ACM Transactions on Programming Languages and Systems, 26(5):769–804, 2004.

5 Средства параллельного программирования 1)Порождение параллельных процессов (потоков) 2)Взаимодействие параллельных процессов 3)Синхронизация

6 Порождение параллельных процессов в MC# Методы: синхронные асинхронные public async f ( int x, float y ) { } Вызов метода: f ( i + j, 10.0f );

7 Порождение параллельных процессов в MC# public movable f ( Complex c, Bitmap b ) { } Автоматическая сериализация/десериализация Равномерное распределение async- и movable- методов по узлам

8 Взаимодействие параллельных процессов 2 типа взаимодействия: на основе разделяемых (shared) переменных ( OpenMP, Intel TBB, Microsoft TPL ) на основе передачи сообщений ( MPI, Go, MC# )

9 Взаимодействие параллельных процессов c h Объект

10 Взаимодействие параллельных процессов public handler h int () & channel c ( int x ) { return ( x * x ); } c ! ( 10 ); int x = (int) h ? ();

11 Средства синхронизации c1 c2 h

12 Средства синхронизации public handler plus int() & channel c1 ( int x ) & channel c2 ( int y ) { return ( x + y ); }

13 Средства синхронизации public handler h1 int() & channel c1 ( int x ) & channel c2 ( int y ) { return ( x + y ); } public handler h2 int() & channel c2 ( int y ) & channel c3 ( int z ) { return ( y + z ); }

14 Программа Fibonacci... new Fib().compute ( n – 1, c1 ); new Fib().compute ( n – 2, c2 ); int n = (int) get ? ();... public handler get int() & channel c1 ( int x ) & channel c2 ( int y ) { return ( x + y ); }

15 Свойства MC# 1.Единая модель для параллельного и распределенного программирования 2.Автоматическая сериализация / десериализация объектов 3.Реализация под Windows и Linux 4.Использование быстрого интерконнекта (Infiniband) без повторной сборки программ 5.Использование любых программ и языков на C/C++ из программ на С#

16 Теоретические основы Robin Milner

17 Теоретические основы Машины Тьюринга Частично-рекурсивные функции λ-исчисление

18 λ-исчисление V = { x, y, z, … } λ-термы: x, x – переменная (MN) M,N- λ-термы (λx.M) x-переменная,M- λ-терм

19 λ-исчисление Редукция (вычисление): ( λx.M) N β M [ x := N ] Примеры: ( λx.x) N β N Ω (λx.xx) (λx.xx) Ω β Ω

20 λ-исчисление Отношение равенства между λ-термами : Аксиома : M = N, если M β N или N β M Правила вывода :... M = N λx.M = λx.N...

21 λ-исчисление Теорема о неподвижной точке: 1) для всех F, Ǝ X F X = X 2) существует λ-терм Y, для всех F, F ( Y F ) = Y F Доказательство: W λx.F ( x x ) X ( W W ) F X F ( W W ) = ( λx.F ( x x ) ) W W W X

22 λ-исчисление λ-определимость : 1) натуральные числа : c n λ f x. f n ( x ) 2) арифметические операции: A + λ xypq. xp (ypq) (применение ассоциативно влево) A * λ xyz. x ( yz ) A exp λ xy. y x Теорема Россера : A + c n c m = c n+m A * c n c m = c n*m...

23 λ-исчисление Теорема Черча-Россера: M N1N1 N2N2 N3N3 β

24 λ-исчисление c типами λx.x – тождественная функция α – переменная, обозначающая тип λx.x : α α Типы λ-исчисления: 1) α, где α переменная 2) ( σ τ ), где σ,τ типы

25 λ-исчисление c типами Присваивание типов λ-термам : Γ – множество объявлений переменных с типами ( x : σ, y : τ, … ) 1)Γ x : σ, если ( x : σ ) принадлежит Γ 2)Γ ( M N ) : τ, если Γ M : (στ), N : σ 3)Γ (λx.M) : ( σ τ ), еслиΓ, x:σ M : τ

26 λ-исчисление c типами Теорема о редукции субъекта : Если M β N, то Γ M : σ Γ N : σ

27 π -исчисление P, Q :: = 0 пустой процесс y ( z ).P оператор ввода ӯ z. P оператор вывода P | Q параллельная композиция ( ν x ) P ограничение ! P репликация

28 π -исчисление Редукция : ӯ z.P | y(x).Q P | Q [ x := z ]... Структурная конгруэнтность : ( P | Q ) | R P | ( Q | R )... ! P P | ! P

29 C -исчисление (a concurrent object calculus) J :: = c канал | J 1 & J 2 связка из каналов D :: = J P связка | D 1, D 2 композиция определений O :: = a = D объект | O 1 ;O 2 композиция объектов P :: = 0 | a.J | P 1 || P 2 | obj O in P

30 C -исчисление (a concurrent object calculus) Редукция : Вычислительная конфигурация : множество определений объектов (мульти)множество процессов a = { J P } a.Jσ a = { J P } Pσ

31 C -исчисление с типами Типы : τ :: = b базовый тип | тип канала | { c 1 : τ 1, …, c n : τ n } тип объекта Теорема о редукции субъекта : Одношаговые редукции сохраняют типы.

32 D -исчисление (a distributed object calculus) D :: =... определения связок | С P |H & C return E... P :: =... | a.m ( E 1, …, E n ) async-метод | a.m ( E 1, …, E n ) s movable-метод...

33 Программирование GPU Суперкомпьютер Tianhe-1A – 1 место в Top500 (ноябрь 2010 г.) Intel Xeon ( x 6 ядер ) Nvidia Tesla M2050 ( x 448 гр. ядер)

34 Технология программирования CUDA Процессоры (виртуальные)... N 512 f

35 Технология программирования CUDA Grid Block

36 Программирование GPU на MC# GpuConfig gpuconf = new GpuConfig(); gpuconf.SetBlockSize ( N ); gpuconf.vecadd ( A, B, C );... public static gpu vecadd (int[] A, int[] B, int[] C ) { int i = ThreadIndex.X; C [ i ] = A [ i ] + B [ i ]; }

37 Перемножение матриц на GPU i j

38 Перемножение матриц на GPU GpuConfig gpuconf = new GpuConfig(); gpuconf.SetBlockSize ( BLOCK_SIZE, BLOCK_SIZE ); gpuconf.SetGridSize ( N / BLOCK_SIZE, N / BLOCK_SIZE ); gpuconf.MatMul ( A, B, C, N );... public static gpu MatMul (float[] A, float[] B, float[], int N ) { int row = BlockIndex.Y * BLOCK_SIZE +ThreadIndex.Y; int col = BlockIndex.X * BLOCK_SIZE + ThreadIndex.X; float c = 0.0f; for ( int k = 0; k < N; k++ ) c += A [ row * N + k ] * B [ k * N + col ]; C [ row * N + col ] = c; }

39 Перемножение матриц на GPU

40 Перемножение матриц на GPU

41 Структура памяти узла с GPU Основная память CPU Основная память GPU 16K/48К... Разделяемая память GPU ( shared memory )

42 Перемножение матриц с использованием shared memory I J

43 Перемножение матриц с использованием shared memory [ StaticArray ( BLOCK_SIZE * BLOCK_SIZE ) ] private static Shared1D As; public static gpu MatrixMultSharMem (float[] A, float[] B, float[] C, int N) {... float c = 0.0f; for ( int b = 0; b < N / BLOCK_SIZE; b++ ) { Загрузка элемента из очередного блока в As Загрузка элемента из очередного блока в Bs CudaRuntime.SyncThreads(); for ( int k = 0; k < BLOCK_SIZE; k++ ) c += As [ i * BLOCK_SIZE + k ] * Bs [ k * BLOCK_SIZE + j ]; CudaRuntime.SyncThreads(); } C [ … ] = c; }

44 Перемножение матриц с использованием shared memory

45 Перемножение матриц с использованием shared memory

46 Дополнительные средства GPU и CUDA 1)Несколько устройств у одного GPU Tesla C1060 : 2 x 240 ядер, Tesla M2050 : 4 x 112 ядер 2) Библиотеки математических функций cuBLAS, cuFFT.

47 Задача N-Queens N = 25 : N = 26 : N = 27 : ?

48 Задача Гамильтоновы циклы N = 22 : N = 24 : ?

49