Использование асинхронных списков в потоковой модели вычислений

А.И. Легалов
© 2006

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

Введение

Асинхронное управление широко используется в параллельном программировании. На его основе разработаны различные модели вычислений и языки программирования. Одной из основополагающих работ является книга Хоара [1], в которой описаны базовые методы асинхронного взаимодействия и подведен соответствующий теоретический фундамент. Теоретические аспекты асинхронного автоматного программирования представлены в работе [2].

Схемы потока данных (СПД) тоже используют асинхронное управление, которое связывается с моментами готовности операндов той или иной выполняемой операции [3]. Это позволяет декларировать, что данный подход к вычислениям в потенциале обеспечивает достижение максимального параллелизма, зависящего только от информационных связей решаемой задачи. Для того чтобы предоставить в распоряжение программиста возможность описания максимального параллелизма, в СПД используются различные концепции. В частности, следует отметить принцип единственного присваивания [3], раскраску данных, принадлежащих раздельно обрабатываемым наборам [3], принцип единственного использования операционных ресурсов [4]. Последний реализован в модели вычислений, лежащей в основе функционально-потокового языка параллельного программирования «Пифагор» [5, 6].

Вместе с тем, следует отметить, что существующим СПД присущ недостаток, который не позволяет эффективно описывать более сложные методы обработки асинхронных потоков данных. Использование неявного подтверждения [7] и бесконечных очередей [3] не обеспечивает представление максимального параллелизма из-за наличия ресурсных ограничений, связанных с конкуренцией между независимыми наборами данных за одни и те же операционные ресурсы. Помимо этого в СПД отсутствуют механизмы совместной обработки асинхронно поступающих данных, принадлежащих одному набору. Операции выполняются только после приема и синхронизации всех элементов, составляющих общий структурированный набор.

Рассмотрим особенности этого ограничения на примере нахождения суммы элементов вектора. Большинство потоковых языков используют в вычислениях заранее подготовленный исходный массив. При наличии в этом массиве всех элементов параллельные вычисления можно организовать на основе древовидной свертки, когда в начале суммируются пары из исходного массива, затем результаты, полученные после суммирования этих пар и т.д. до получения окончательного результата. В языке «Пифагор» исходный массив задается списком данных [5, 6]. Функция древовидной рекурсивной свертки, написанная на нем, имеет следующий вид:

// Функция, возвращающая сумму элементов вектора
VecSum << funcdef A {
  // Формат аргумента: A=(x1, x2, … , xn), 
  // где x1, x2, … , xn - числа
  Len<< A:|; // Определяется длина вектора A
  return<< .^[((Len,2):[<,=,>]):?]^    
  ( {A:[]},   // Возвращается значение его единственного элемента
    {A:+},    // Аргумент имеет длину 2 - возврат суммы элементов
      // Третий элемент реализован в виде блока, 
    {block {
      OddVec << A:[(1,Len,2):..];
         // где OddVec - список из нечётных элементов
  EvenVec << A:[(2,Len,2):..];
    // где EvenVec - список из чётных элементов
       // Оба списка объединяются в параллельный
       // над которым выполняется функция суммирования,
       // что приводит к параллельному рекурсивному
       // вызову:
      ([OddVec,EvenVec]: VecSum
     // Результаты параллельного выполнения двух 
     // экземпляров функции VecSum суммируются:            
     ):+ >>break // Выдача результата из блока
    } // конец блока
  } // конец задержанного списка
  )
}

Схема такого суммирования для массива, состоящего из восьми элементов, представлена на рис. 1.

Рис. 1. Суммирование с использованием древовидной свертки

Следует отметить, что существуют задачи, в которых обрабатываемый массив заранее неизвестен, и формируется в ходе выполнения вычислений. Например, к моменту вызова функции суммирования возможно наличие только 1-го и 5-го элементов массива (рис. 2).

Рис. 2. Возможность суммирования при наличии двух любых элементов

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

Рис. 3. Суммирование появившегося элемента с вычисленным промежуточным значением

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

Ниже предлагаются методы организации данных и механизмы управления вычислениями, расширяющие возможности асинхронного управления в СПД. Показывается, каким образом предлагаемые понятия расширяют функционально-потоковую модель параллельных вычислений и могут быть реализованы в языке программирования «Пифагор».

Специфика асинхронного управления данными

Опираясь на результаты работы Хоара [1], можно считать, что события, возникающие при выполнении параллельных процессов, порождаются последовательно. Подобное допущение часто используется и в другой, широко известной асинхронной модели параллельных вычислений – сетях Петри [8]. Учитывая то, что в СПД события связаны с моментами получения значений, будем считать последовательными моменты порождения этих значений во время вычислений.

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

Опираясь на представленные рассуждения, можно предложить следующую схему вычисления суммы элементов одномерного массива на основе готовности данных. Элементы массива, асинхронно формируемые в ходе вычислений, образуют очередь, в которую заносятся в порядке появления. При наличии в этой очереди двух или более элементов проводится суммирование образуемых пар с последующей засылкой результата в эту же очередь. Единственный элемент, оставшийся в ходе суммирования, является окончательным результатом. Схема подобной организации вычислений представлена на рис. 4.

Рис. 4. Суммирование данных, асинхронно поступающих в общий информационный поток

Для реализации управления на основе асинхронно поступающих данных в функциональную модель потоковых вычислений предлагается добавить асинхронный список. Его особенностью является упорядочение элементов в соответствии с последовательностью их порождения. По сравнению с обычным списком данных, выдающим сигнал готовности после поступления всех его элементов, асинхронный список сигнализирует только о появлении первого значения. Это накладывает определенную специфику на его интерпретацию. Можно считать, что об асинхронном списке достоверно известно следующее: или он не готов, или содержит как минимум один готовый элемент (а об остальных данных ничего не известно), или является пустым.

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

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

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

Обозначим асинхронный список через AN, где N – количество порождаемых в нем элементов. Тогда его структуру можно описать следующим образом:

A⁰ = (.), если N = 0
A^N = (d, D^N-1), если N > 0,

где d – головной элемент порождаемого списка, D^N-1 – N-1 элементов списка, оставшиеся еще не обработанными, A⁰ – пустой асинхронный список, эквивалентный обычному пустому списку данных, который обозначается в языке «Пифагор» как «(.)» [4-6].

Чтобы отличить асинхронный список от обычного списка данных, используемого в языке «Пифагор», введем для него следующее обозначение:

asynch(d₁, d₂, ... d_N) = A^N ,

где d₁, d₂, ... d_N – список элементов, порождаемых в ходе вычислений, проистекающих внутри него, упорядоченный по времени формирования значений. Для выделения и дальнейшей обработки этих значений допускается использовать операции выборки первого элемента и создания списка без первого элемента, эквивалентные по синтаксису и семантике аналогичным операциям списка данных. Таким образом, выделения из списка первого элемента задается следующим образом:

asynch(d₁, d₂, ... d_N):1 => d₁ .

Для выделения прочих элементов в отдельный асинхронный список необходимо воспользоваться следующей операцией:

asynch(d₁, d₂, ... d_N):-1 => asynch(d₂, ... d_N) .

Одновременное использование этих двух операций позволяет выделить и обработать все элементы асинхронного списка. Выполнение этих операций может продолжиться до получения вместо асинхронного списка пустого списка данных:

asynch(d₁, d₂, ... d_N):[1,-1] => d₁, asynch(d₂, ... d_N) [1,-1] =>
=> d₁, d₂, asynch(d₃, ... d_N):[1,-1] => d₁, d₂, d₃, asynch(d₄, ... d_N):[1,-1] => ...
...=> d₁, d₂, d₃,... d_N-1, asynch(d_N):[1,-1] => d₁, d₂, d₃,... d_N, (.).

Таким образом, прямой доступ к произвольному элементу асинхронного списка невозможен. Если же данные были сформированы заранее, то порядок их следования в асинхронном списке определяется размещением в исходном списке данных. Для заранее заданного одномерного массива:

X = (44,55,12,42)

асинхронный список, порождаемый из исходного списка данных, будет трансформироваться обрабатываться по этим же правилам:

asynch(44,55,12,42):[1, -1] => 44, asynch(55,12,42) :[1, -1] => 44, 55, asynch(12,42) :[1, -1] =>
=> 44, 55, 12, asynch (42) :[1, -1] => 44, 55, 12, 42, (.) .

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

Дополнительные аксиомы и операции интерпретации функционально-потоковой модели вычислений

Для реализации асинхронного управления в функционально-потоковой модели вычислений введем ряд дополнительных понятий. Пусть, имеется асинхронный список:

asynch(g₁, g₂, ... g_n)

где g₁, g₂, ... g_n – генераторы данных, порождающие величины в произвольной последовательности. Как и список данных, асинхронный список фильтрует (отбрасывает, игнорирует) пустые элементы, не выставляя их очередь данных:

asynch(g₁, .) = asynch(g₁)

Помимо этого, асинхронному списку присуща ассоциативность, определяющая, что порядок размещения генераторов данных не влияет на порядок выдачи элементов, который определяется только моментом порождения данных каждым из генераторов:

asynch(g₁, g₂) = asynch(g₂, g₁)

Асинхронные списки можно преобразовывать в другие списки. Преобразование в параллельный список осуществляется по следующему правилу:

asynch(d₁, d₂, ... d_N):[] => [d₁, d₂, ... d_N] .

В результате на выходе формируется параллельный список, состоящий из множества независимых данных. Порядок следования данных в параллельном списке совпадает с последовательностью их порождения в асинхронном.

Операция преобразования асинхронного списка в список данных определяется аналогичным образом:

asynch(d₁, d₂, ... d_N):() => (d₁, d₂, ... d_N) .

Допустимы также обратные преобразования существующих списков в асинхронные, которые осуществляются с использованием существующих аксиом и правил преобразования модели вычислений. Непосредственным является только преобразование списка данных в асинхронный список:

(d₁, d₂, ... d_N):asynch => asynch(d₁, d₂, ... d_N) .

При преобразовании параллельного и задержанного списков применяются аксиомы, определяющие групповые операции [5, 6].

Использование асинхронных списков в языке программирования «Пифагор»

Приведенные выше расширения функционально потоковой модели вычислений можно реализовать в языке программирования «Пифагор». Это позволит писать параллельные программы в несколько ином стиле, при котором учитывается асинхронное поступление данных. В частности, сложение элементов одномерного массива, соответствующее схеме, представленной на рис. 4, может быть реализовано следующим образом:

 
// Функция, возвращающая сумму элементов асинхронного списка
A_VecSum<< funcdef A
    // Формат аргумента: A=asynch(x1, x2, ... , xn)
    // где x1, x2, ... , xn - числа
{
  x1<< A:1;      // Поступивший элемент данных
  tail_1<< A:-1;  // Хвост асинхронного списка
  // Проверка на пустоту остатка списка
  [((tail_1:|, 0):[=, !=]):?]^
  (
     x1, // В списке, только один элемент, определяющий сумму
     {   // Выделение второго аргумента с последующим суммированием
        block {
           x2<< tail_1:1;      // второй аргумент
           s<< (x1,x2):+;      // сумма двух поступивших элементов
           tail_2<< tail_1:-1;  // “хвост” от “хвоста”
           // Рекурсивная обработка оставшихся элементов
           [((tail_2:|, 0):[=, !=]):?]^
           (
              s,
              { asynch( tail_2:[], s):A_VecSum }
           ):. >>break
        }
     }
  ):. >>return;
}

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

Интерпретация временных соотношений асинхронной потоковой программы

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

Рис. 5. Последовательное суммирование при delta_t_dat >= delta_t_add

В том случае, если интервал времени поступления данных станет меньше времени их сложения, начнет появляться параллелизм в выполнении этих операций. Количество параллельных потоков будет кратно отношению времени delta_t_add к delta_t_dat. Например, при delta_t_add/delta_t_dat = 2 будет динамически сформировано два потока операций сложения (рис. 6).

Рис. 6. Формирование двух параллельных потоков при delta_t_add = 2*delta_t_dat

Если темп поступление данных много выше времени выполнения операции сложения, то можно считать, что они успевают поступить до начала суммирования, которое начнется практически одновременно для всех пар чисел. По завершению суммирования результаты также «мгновенно» поступают в асинхронный список, обеспечивая тем самым одновременное суммирование на втором слое. При этом общая схема вычислений будет соответствовать древовидной свертке, представленной на рис. 1.

Заключение

Таким образом, использование асинхронных списков позволяет реализовать новый класс алгоритмов, параллелизм которых зависит от временных соотношений между выполняемыми основными и подготовительными операциями. Это позволяет говорить о специфическом подходе к построению параллельных функционально-потоковых алгоритмов, позволяющем разрабатывать и исследовать новые методы создания переносимых параллельных программ. В отличие от эквивалентных преобразований обобщенных функций, предлагаемых в [9, 10] для адаптации параллельного алгоритма к конкретной вычислительной системе, использование асинхронных списков позволяет применять один и тот же алгоритм, на который накладываются разные временные отношения между выполняемыми операциями.

Предложенный в работе механизм описания асинхронных вычислений предоставляет в распоряжения программиста дополнительные возможности. Его инструментальная поддержка на уровне языков обеспечивает использование новых методов разработки функционально-потоковых параллельных программ, характеризующихся динамическим изменением параллелизма в зависимости от временных соотношений между выполняемыми операциями. Это повышает гибкость разрабатываемых алгоритмов, и позволяет использовать один и тот же алгоритм для динамического задания различных уровней параллелизма. Формируемые при этом программы позволяют описывать максимальный параллелизм решаемой задачи и не зависят от архитектур используемых вычислительных систем. Вместе с тем следует отметить, что использование асинхронных списков не влияет на организацию виртуального вычислителя, используемого для параллельной интерпретации функциональных программ [11].

Первоначальная версия статьи опубликованна в [12].

Литература

1. Хоар Ч. Взаимодействующие последовательные процессы. Пер. с англ. - М.: Мир, 1989. -264 с.

2. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / Под ред. В.И. Варшавского. – М.: Наука. Гл. ред. физ.-мат. лит., 1986 – 400 с.

3. Алгоритмы, математическое обеспечение и проектирование архитектур, многопроцессорных вычислительных систем. Под ред. А.П. Ершова. - М: Наука, 1982.

4. Легалов А.И., Казаков Ф.А., Кузьмин Д.А. Водяхо А.И. Модель параллельных вычислений функционального языка. Известия ГЭТУ, Сборник научных трудов. Выпуск 500. Структуры и математическое обеспечение специализированных средств. С.-Петербург, 1996. с. 56-63.

5. Легалов А.И. Функциональный язык для создания архитектурно-независимых параллельных программ. – Вычислительные технологии, № 1 (10), 2005. С. 71-89.

6. Легалов А.И. Кузьмин Д.А., Казаков Ф.А., Привалихин Д.В. На пути к переносимым параллельным программам. – Открытые системы, № 5 (май), 2003, с. 36-42.

7. Денис Дж.Б., Фоссин Дж.Б., Линдерман Дж.П. Схемы потоков данных // В кн. Теория программирования. Ч 2. Новосибирск: ВЦ СО АН CCCР, 1972 г. с 7-43.

8. Котов В. Е. Сети Петри. – М.: Наука. Главная редакция физико-математической литературы, 1984. – 160 с.

9. Легалов А.И., Казаков Ф.А. Эквивалентные преобразования функционально-параллельных программ. – Распределенные и кластерные вычисления. Избранные материалы Третьей школы-семинара. / Институт вычислительного моделирования СО РАН. Красноярск, 2004, с. 134-141.

10. Воеводин В.В. Математические проблемы параллельных вычислений. // Сб. тр. Всероссийской конф. «Научный сервис в сети Интенет: технологии распределенных вычислений». Новороссийск, 19-24 сентября 2005 г. – Изд-во Московского ун-та, 2005. – С. 3-8.

11. Кузьмин Д.А., Легалов А.И. Интерпретация функционально-параллельных программ с использованием кластерных систем. – Высокопроизводительные вычисления на кластерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. / Под ред. В.А. Сойфера. Самара, 2004. С. 136-144.

12. Легалов А.И. Использование асинхронных вычислений в функциональных языках параллельного программирования. – Распределенные и кластерные вычисления. Избранные материалы четвертой школы-семинара. / Институт вычислительного моделирования СО РАН. Красноярск, 2005. С. 172-183.