Обзор программной нотации
В пяти предыдущих разделах были представлены примеры циклических схем в параллельном программировании: итеративный параллелизм, рекурсивный параллелизм, производители и потребители, клиенты и серверы, а также взаимодействующие равные. Многочисленные примеры этих схем еще будут приведены. В примерах также была введена программная нотация. В данном разделе дается ее обзор, хотя она очевидна из примеров.
Напомним, что параллельная программа содержит один или несколько процессов, а каждый процесс — это последовательная программа. Таким образом, наш язык программирования содержит механизмы и параллельного, и последовательного программирования. Нотация последовательных программ основана на базовых понятиях языков С, C++ и Java. В нотации параллельного программирования используются операторы со и декларации process. Они были представлены ранее и определяются ниже. В следующих главах будут определены механизмы синхронизации и межпроцессного взаимодействия.
1.9.1. Декларации
Декларация (объявление, или определение) переменной задает тип данных и перечисляет имена одной или нескольких переменных этого типа. При объявлении переменную можно инициализировать, например: int i, j = 3; double sum = 0.0;
Массив объявляется добавлением размера каждого измерения к имени массива. Диапазон индексов массива по умолчанию находится в пределах от 0 до значения, меньшего на 1, чем размер измерения. В качестве альтернативы можно непосредственно указать нижнюю и верхнюю границы диапазона. Массивы также можно инициализировать при их объявлении. Вот примеры:
int a[n]; # то же, что и "int a[0:n-l];"
int b[l:n]; # массив из п целых, Ь[1] ... Ь[п]
int c[l:n]=([п]0); # вектор нулей
double c[n,n] = ([n] ([n] 1.0)); # матрица единиц
Каждая декларация сопровождается комментарием, который начинается знаком # (см. раздел 1.9.4). Последняя декларация говорит, что с — это матрица чисел двойной точности.
Ин дексы каждого ее измерения находятся в пределах от 0 до п-1, а начальное значение каждого ее элемента — 1.0.
Если условие имеет значение "истина", то выполняются вложенные операторы (тело цик ла), а затем оператор while повторяется. Цикл while завершается, если условие имеет зна чение "ложь". Если в теле цикла только один оператор, фигурные скобки опускаются.
Операторы if и while идентичны соответствующим операторам в языках С, C++ и Java, но оператор for записывается более компактно. Его общий вид таков.
for [квантификатор!, ..., квантификаторМ] { оператор!;
операторы,-}
Каждый квантификатор вводит новую индексную переменную (параметр цикла), инициализирует ее и указывает диапазон ее значений. Квадратные скобки вокруг квантификаторов используются для определения диапазона значений, как и в декларациях массивов.
В действительности его общий вид— while (условие) оператор;. Это же относится и к следующему оператору for. — Прим, перев
1.9. Обзор программной нотации 39
Предположим, что а [п] — это массив целых чисел. Тогда следующий оператор инициализирует каждый элемент массива а [ i ] значением 1. for [i = 0 to n-1] a[i] = i;
Здесь i — новая переменная; ее не обязательно определять выше в программе. Область видимости переменной i — тело данного цикла for. Ее начальное значение 0, и она принимает по порядку значения от 0 до п-1.
Предположим, что m[n,n] — массив целых чисел. Рассмотрим оператор for с двумя квантификаторами.
for [i = 0 to n-1, j = 0 to n-1] m[i,j] = 0;
Этому оператору эквивалентны вложенные операторы for.
for [i = 0 to n-1] for [j = 0 to n-1] m[i,j] = 0;
В обоих случаях п2 значений матрицы m инициализируются нулями. Рассмотрим еще два примера квантификаторов.
[i = 1 to n by 2] #нечетные значения от 1 до п
[i = 0 to n-1 st i!=x] каждое значение, кроме i==x
Обозначение st во втором квантификаторе — это сокращение слов "such that" ("такой, для которого").
Операторы for записываются с использованием синтаксиса, приведенного выше, по нескольким причинам. Во-первых, этим подчеркивается отличие наших операторов for от тех же операторов в языках С, C++ и Java. Во-вторых, такая нотация предполагает их использование с массивами, у которых индексы заключаются в квадратные, а не круглые скобки. В-третьих, наша запись упрощает программы, поскольку избавляет от необходимости объявлять индексную переменную. (Сколько раз вы забывали это сделать?) В-четвертых, зачастую удобнее использовать несколько индексных переменных, т.е. записывать несколько квантификаторов. И, наконец, те же формы квантификаторов используются в операторах со и декларациях process.
1.9.3. Параллельные операторы, процессы и процедуры
.По умолчанию операторы выполняются последовательно, т.е. один за другим. Оператор со (concurrent — параллельный, происходящий одновременно) указывает, что несколько операторов могут выполняться параллельно. В одной форме оператор со имеет несколько ветвей (arms).
со оператор!;
// .. .
// onepaтopN;
ос
Каждая ветвь содержит оператор (или список операторов). Ветви отделяются символом параллелизма //. Оператор, приведенный выше, означает следующее: начать параллельное выполнение всех операторов, затем ожидать их завершения. Оператор со, таким образом, завершается после выполнения всех его операторов.
В другой форме оператор со использует один или несколько квантификаторов, которые указывают, что набор операторов должен выполняться параллельно для каждой комбинации
40 Глава 1. Обзор области параллельных вычислений
значений параметров цикла. Например, следующий тривиальный оператор инициализирует массивы а [п] иЬ[п] нулями.
co[i = 0 to n-1] {
a[i] = 0; b[i] = 0; }
Этот оператор создает п процессов, по одному для каждого значения переменной i.
Область видимости счетчика — описание процесса, и у каждого процесса свое, отличное от других, значение переменной i. Две формы оператора со можно смешивать. Например, одна ветвь может иметь квантификатор в квадратных скобках, а другая — нет.
Декларация процесса является, по существу, сокращенной формой оператора со с одной ветвью и/или одним квантификатором. Она начинается ключевым словом process и именем процесса, а заканчивается ключевым словом end. Тело процесса содержит определения локальных переменных, если такие есть, и список операторов.
В следующем простом примере определяется процесс f оо, который суммирует числа от 1 до 10, записывая результат в глобальную переменную х.
process foo {
int sum = 0;
for [i = 1 to 10] sum += i;
x = sum; }
Декларация process записывается на синтаксическом уровне декларации procedure; это не оператор, в отличие от со. Кроме того, объявляемые процессы выполняются в фоновом режиме, тогда как выполнение оператора, следующего за оператором со, начинается после завершения процессов, созданных этим со.
Еще один простой пример: следующий процесс записывает значения от 1 до п в стандартный файл вывода.
process barl { for [i = 1 to n]
write(i); # то же, что "printf("%d\n",i);" }
Массив процессов объявляется добавлением квантификатора (в квадратных скобках) к имени процесса.
process bar2[i = 1 to n] {
write(i); }
И barl, и bar2 записывают в стандартный вывод значения от 1 до п. Однако порядок в котором их записывает массив процессов Ьаг2, недетерминирован, поскольку массив Ьаг2 состоит из п отдельных процессов, выполняемых в произвольном порядке. Существует п! различных порядков, в которых этот массив процессов мог бы записать числа (п! — число перестановок п значений).
Процедуры и функции объявляются и вызываются так же, как это делается в языке С, например, так.
int addOne(int v) { # функция возвращает целое число
return (v + 1); }
main() { # "void"-процедура int n, sum;
read(n); # прочитать целое число из stdin for [i = 1 to n]
sum = sum + addOne(i);
Историческая справка 41
write("Окончательным значением является ", sum); }
Если входное значение п равно 5, эта программа выведет такую строку.
Окончательным значением является 20
1.9.4. Комментарии
Комментарии записываются двумя способами. Однострочные комментарии начинаются символом # и завершаются в конце строки. Многострочные комментарии начинаются символами /* и оканчиваются символами */. Для однострочных комментариев используется символ #, поскольку символ однострочных комментариев // языков C++ и Java уже давно использовался в параллельном программировании как разделитель ветвей в параллельных операторах.
Утверждение — это предикат, определяющий условие, которое должно выполняться в некоторой точке программы. (Утверждения подробно описаны в главе 2.) Утверждения можно рассматривать как предельно точные комментарии, поэтому они записываются в отдельных строках, начинающихся двумя символами #:
## х > О Данный комментарий утверждает, что значение х положительно.
