Курс лекций "Параллельная обработка данных"

Содержание

Лекция 7. Система параллельного программирования Linda

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

 ( "Hello", 42, 3.14 ),
 ( "P", 5, FALSE, 97, 1024, 2),  
 ( "worker", 5 ) .

Первый элемент кортежа всегда является символьной строкой и выступает в роли имени кортежа. Так первый кортеж предыдущего примера состоит из имени ("Hello"), элемента целого типа (42) и вещественного числа (3.14). Во втором кортеже кроме имени "P" есть элемент целого типа (5), элемент логического типа (FALSE) и три целых числа. Последний кортеж состоит из двух элементов: имени ("worker") и целого числа (5). Количество элементов в кортеже может быть любым.

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

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

Функция OUT помещает кортеж в пространство кортежей. Например,

 out ( "GoProcess", 5);

Функция IN ищет подходящий кортеж в пространстве кортежей, присваивает значения его элементов элементам своего параметра-кортежа и удаляет найденный кортеж из пространства кортежей. Например,

 in( "P", int i, FALSE );

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

 int i = 5;
 in( "P", i, FALSE );

Если переменная описана до вызова функции и ее надо использовать как формальный элемент кортежа, можно использовать ключевое слово formal или знак '?'. Например, во фрагменте программы

 j = 15; 
 in( "P", formal i, j ); 

 in ( "Add_If", int i, bool b);

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

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

 eval ("hello", funct( z ), TRUE, 3.1415);

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

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

 out( "Next", 1);

 in( "Next", formal My_Id);
 out( "Next", My_Id+1);

 read( "Next", formal Num_Processes);

Теперь рассмотрим возможную схему организации программы для перемножения С=A*B двух квадратных матриц размера N*N. Инициализирующий процесс использует функцию out и помещает в пространство кортежей исходные строки матрицы A и столбцы матрицы B:

 out( "A",1, <1-я строка A>);
 out( "A",2, <2-я строка A>); 
   ... 
 out( "B",1, <1-й столбец B>); 
 out( "B",2, <2-й столбец B>); 
   ...

Для порождения Nproc идентичных параллельных процессов можно воспользоваться следующим фрагментом:

 for( i = 0; i < Nproc; ++i )
  eval( "ParProc", get_elem_result() );

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

 out( "NextElementCij", 1);

 in( "NextElementCij", formal NextElement); 
 if( NextElement < N*N ) 
  out("NextElementCij ", NextElement + 1); 
 Nrow = (NextElement - 1) / N + 1; 
 Ncol = (NextElement - 1) % N + 1; 

В результате выполнения данного фрагмента для элемента с номером NextElement процесс определит его местоположение в результирующей матрице: номер строки Nrow и столбца Ncol. Заметим, что если вычисляется последний элемент, то кортеж с именем "NextElementCij" в пространство не возвращается. Когда в конце работы программы процессы обратятся к этому кортежу, они будут заблокированы, что не помешает нормальному завершению программы. И, наконец, для вычисления элемента C_ij каждый процесс get_elem_result выполнит следующий фрагмент:

 read( "A", Nrow, formal row); 
 read( "B", Ncol, formal col); 
 out( "result", Nrow, Ncol, DotProduct(row,col) ); 

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

 
 for ( irow = 0; irow < N; irow++) 
  for ( icol = 0; icol < N; icol++) 
   in( "result", irow + 1, icol + 1, formal C[irow][icol]); 

Не имея в системе Linda никаких явных средств для синхронизации процессов, совсем не сложно их смоделировать самому. Предположим, что в некоторой точке нужно выполнить барьерную синхронизацию N процессов. Какой-то один процесс, например, стартовый, заранее помещает в пространство кортеж ("ForBarrier", N). Подходя к точке синхронизации, каждый процесс выполняет следующий фрагмент, который и будет выполнять функции барьера:

 in( "ForBarrier", formal Bar);
 Bar = Bar - 1;
 if( Bar != 0 ) {
  out( "ForBarrier", Bar);
  read( "Barrier" );
 } else 
  out( "Barrier" );

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

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

Оглавление       Назад