70.0.1. ПАРАЛЕЛЬНЫЕ КОНСТРУКЦИИ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 


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


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

  


  



Основу паралельных конструкций составляет барьер:

                | одна нить
                |
	        V	
	==================  точка распаралеливания
	  |   |   |   |
	  |   |   |   |
      паралельное выполнение
    	  |   |   |   |
    	  V   V   V   V
	=================== барьер
		|
		V

  


Паралельное выполнение кончается у барьера.
Варианты поведения барьера:

		Барьер
		/   \
	    Ждущий  Неждущий

Неждущий 	барьер не ждет окончания выполнения всех нитей
		а пропускает первые дошедшие N нитей дальше (как правило N=1)
Ждущий		барьер ждет пока все нити дойдут до барьера
		затем пропускает первые N нитей дальше

Смешанный	барьер ждет пока первые M нитей не достигнуть барьера
		затем пропускает первые N нитей дальше

  

  


  

  


  

  





  
  Простая паралелизация 
 

  ---------------------------
	PAR
	{
		A;
		B;
		C;
		D;
		E;
		F;
	}
  ---------------------------

Все подоператоры выполняются паралельно - кто первый взял тот и выполнил.
Пример выполнения на 3 нитях:
	
	-------------------------
	# нити	  0   1   2
	- - - - - - - - - - - - - 
	задачи    A   B   D
	          C       F
	          E
	-------------------------



  
  Паралелизация с секциями 
 

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

  ---------------------------
	PAR
	{
		SEQ
		{
			A1
			A2
		}
		SEQ
		{
			B1
			B2
			B3
		}
		SEQ	
		{
			C1
		}
		SEQ
		{
			D1
			D2
		}
	}
  ---------------------------

Пример выполнения на 3 нитях:
	-------------------------
	# нити	  0    1    2
	- - - - - - - - - - - - - 
	задачи    A1   B1   C1
	          A2   B2   
	               B3
	               D1
		       D2	
	-------------------------


  
  Паралелизация циклов 
 

Итерации для цикла выполняются паралельно
  ---------------------------
	PARFOR	i = 1 TO 5
	{
		A(i)
	}
  ---------------------------
как правило подразумевается
  ---------------------------
	PARFOR i = 1 TO 5
	{
		SEQ
		{
			A(i)
		}
	}
  ---------------------------

	
Пример выполнения на 3 нитях:
	-------------------------
	# нити	  0    1    2
	- - - - - - - - - - - - - 
	задачи    A(1)  A(3)  A(5)
		  A(2)  A(4)
	-------------------------



Паралелизация внутри цикла:
  
  ---------------------------
	PARFOR  i = 1 TO 2
	{
		PAR
		{
			A(i)
			B(i)
		}
	}
  ---------------------------
это то же самое что
  ---------------------------
	PAR
	{
		A(1)
		B(1)
		A(2)
		B(2)
	}
  ---------------------------
то есть запросто 
 


Паралелизация вложенных циклов
  ----------------------------
	PARFOR i = 1 TO 2
	{
		PARFOR j = 1 TO 2
		{
			A(i,j)
		}
	}
  ----------------------------
тоже самое что
  ----------------------------
	PAR
	{
		A(1,1)
		A(1,2)
		A(2,1)
		A(2,2)
	}
  ----------------------------



  
  Паралелизация с атомарными операциями 
 
  -----------------------------
	PARFOR i = 1 TO 8
	{
		SEQ
		{
			A
			ATOMIC
			{
				B
			}
			C
		}
	}
  -----------------------------

  


Секция ATOMIC означает что в ней может работать только одна нить одновременно
Пример выполнения операций на 3х нитях:
	-------------------------------------------------------
	# нити	  0     1     2     3
	- - - - - - - - - - - - - - - - -    выбран  очередь
	задачи    A(1)  A(3)  A(5)  A(7)	--	--
		  B(1)  wait  wait  wait	0	2 1 3
		  C(1)  wait  B(5)  wait	2	1 3
		  A(2)  B(3)  C(5)  wait	1	3
		  wait  C(3)  A(6)  B(7)	3	0
		  B(2)  A(4)  wait  C(7)	0	2
		  C(2)  wait  B(6)  A(8)	2	1
			B(4)  C(6)  wait	1	3
			C(4)	    B(8)	3	--
				    C(8)	--	--
	-------------------------------------------------------



Другой вариант разрешает работать в секции только master thread
  

	
  


OCCAM-II

	SEQ
	   ....


паралельный IF:
	IF 
	   cond1
	      process1
	   cond2
	      process2
	   cond3
              proces3



	PAR
	   WHILE TRUE
	     SEQ
	       ....
           WHILE TRUE
	     SEQ
               ....



Циклы:
	SEQ I = 0 TO 2
          SEQ
	    ....


	PAR I = 1 TO 2       тоже самое что	PAR
	  PAR                                      P(1)
	      P(I)                                 Q(1)
	      Q(I)			           P(2)
	                                           Q(2)



Переменные могут быть shared могут быть local



Каналы связи между паралельными процессами:

	CHAN OF BYTE keyboard
	CHAN OF BYTE screen
	CHAN OF INT  term_in, term_out
	PAR
		editor(term_in,term_out)
		keyboard_handler(keyboard,term_in)
		screen_handler(term_out, screen)

Очень все напоминает HDLs.



Критическая секция

	--------------
	P(mutex)
		Тело критической секции
	V(mutex)
	---------------
	



Барьерная синхронизация

Возможные варианты синхронизации
	Разделяемый счетчик
	Древовидная структура
	Барьер-бабочка

Идейная часть

		1 2
		+-+

	process1		process2
	{			{
		...             	....
		V(arrive1)		V(arrive2)
		P(arrive2)		P(arrive1)
	}			}


Древовидная структура
		1 2 3 4 5 6 7 8
		+-+ +-+ +-+ +-+
		 +---+   +---+
		   +-------+

Барьер-Бабочка
		1 2 3 4 5 6 7 8
           L1   +-+ +-+ +-+ +-+

	   L2   +---+   +---+
		  +---+   +---+

	   L3   +-------+
                  +-------+
                    +-------+
                       +------+



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