Выборка элементов массива

Существует несколько разных подходов к программированию параллельных вычислительных систем:

использование специализированных языков параллельного программирования и параллельных расширений последовательных языков (параллельные реализации Fortran и C и пр.);
использование средств автоматического и полуавтоматического распараллеливания последовательных программ (PGI, BERT 77, FORGE, KAP и др.);
программирование на последовательных языках программирования с использованием коммуникационных библиотек и интерфейсов для организации межпроцессорного взаимодействия (MPI, PVM, OpenMP и др.);
программирование на последовательных языках с использованием параллельных библиотечных процедур (ScaLAPACK, HP Mathematical Library, PETSc и др.).

Существует также большое количество инструментальных средств, которые упрощают проектирование параллельных программ (CODE, TRAPPER и др.).

Данная глава открывает рассмотрение первого из указанных подходов к программированию параллельных вычислительных систем.

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

программирование параллельных ЭВМ на ассемблере является очень трудоемким;
быстрая смена элементной базы параллельных ЭВМ и самих этих ЭВМ означает переработку всего запаса ассемблерных программ.

Имеется три основных подхода к созданию параллельных языков высокого уровня (ЯВУ).

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

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

Третий

- создание новых параллельных ЯВУ, не зависящих от конкретной архитектуры или типа параллельных вычислительных систем (АДА, например). Достоинство подхода состоит в возможности использования в ЯВУ концепций, повышающих эффективность и надежность написанных на этом языке программ; недостатки подхода – в трудности освоения и сложности создания эффективных объектных кодов при трансляции.

Примеры в данном и ряде последующих параграфов приводятся с использованием ЯВУ Actus, который представляет собой расширение языка Pascal - см. R. H. Perrott, "A language for array and vector processors," ACM Transactions on Programming Languages and Systems, Vol. 1, October 1979, pp. 177-195.

Векторно-конвейерные вычислительные системы и векторно-параллельные вычислительные системы ориентированы и имеют высокую эффективность при выполнении векторных операций. Векторы представляются в ЯВУ в виде массивов данных. Рассмотрим поэтому конструкции параллельных ЯВУ, используемые для работы с массивами.

Напомним понятия ранг массива и размерность массива. Рангом массива называется количество его измерений. Т.е. слова «

-мерный массив» и «массив имеет ранг

» являются синонимами. Размерностью массива называется количество элементов данных по каждому из измерений. Например, массив

является трехмерным массивом (ранг равен трем) с размерностями

В параллельных ЯВУ можно выделить три подхода к представлению массивов:

1. Массивы - как последовательные объекты. В этом случае массивы описываются так же, как в последовательных ЯВУ. Параллелизм указывается только при обработке массивов (путем спецификации набора индексов элементов массивов, над которыми должна быть выполнена операция).

2. Массивы - как параллельные объекты. Здесь все массивы описываются как особые объекты заданной размерности. Любое обращение к массиву при этом подразумевает весь массив (хотя, естественно, не отменяется использование массива в качестве набора объектов меньшего ранга).

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

Пример 1

В языке Actus массивы могут содержать массивы всех указанных типов:

var

(*одномерный параллельный массив*)

parvar: array [1:100] of integer;

(*одномерный последовательный массив*)

scalvar: array [1..50] of integer;

(*двумерный массив параллельных строк*)

grid: array [1:50, 1..100] of real;

Выборка объектов пониженного ранга.

Пусть имеется 2-х мерный

-массив

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

или - весь этот массив;
или - -я строка массива ;
или - -й столбец массива ;
- элемент массива , находящийся в -й строке и в -ом столбце.

Выборка диапазона значений.

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

- выборка внутренних точек массива;

- выборка первых трех элементов из всех нечетных строк.

Выборка с помощью целочисленных массивов.

Пусть

одномерные массивы из

элементов, причем

Рассмотрим 2-х мерный (4*4) -массив

и положим, что

, т.е.

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

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

Если результирующий объект имеет вид

, то ранг его равен единице и элементы определяются по правилу:

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

Таким образом,

Если результирующий объект имеет вид

, ранг его также равен единице и элементы определяются по правилу:

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

Таким образом,

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

Если результирующий объект имеет вид , то ранг его равен двум и элементы определяются по правилу:

в первую строку массива записывается строка исходного массива;
во вторую строку массива записывается строка исходного массива;
и т.д.

Таким образом,

Если результирующий объект имеет вид

, то ранг его также равен двум и элементы определяются по правилу:

в первый столбец массива записывается столбец исходного массива;
во вторую столбец массива записывается столбца исходного массива;
и т.д.

Таким образом,

Если результирующий объект имеет вид

, то ранг его также равен двум и элементы определяются по правилу:

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

Таким образом,

Пример 2

В ЯВУ Actus используется линейное отображение с помощью параллельных целочисленных массивов. Пусть имеют место спецификации

const

(*параллельная константа*)

diagonal = 1:100 of integer;

var

(*параллельный массив*)

diag: array [1:100] of integer;

(*массив параллельных строк*)

para: array [1:100, 1..100] of real;

и присваивание (параллельное) diag [1:100] := diagonal. Тогда конструкция para[1:100,diag] означает все диагональные элементы массива para, доступ к которым может выполняться параллельно.

Выборка с помощью булевых массивов.

Пусть

одномерный булевый массив из

элементов. Так же, как в предыдущем разделе рассмотрим 2-х мерный (4*4) -массив

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

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

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

Если результирующий объект имеет вид

, то ранг его равен единице и элементы определяются по правилу:

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

Таким образом,

Если результирующий объект имеет вид

, то ранг его также равен единице и элементы определяются по правилу

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

Таким образом,

Линейное отображение с помощью булевых массивов. В этом случае результирующий объект имеет тот же ранг, что и ранг исходного объекта. Массив

, с помощью которого осуществляется выборка, может иметь более одного отличного от нуля элемента. Положим, что

Если результирующий объект имеет вид

, то ранг его равен двум и элементы определяются по правилу:

в первую строку массива записывается та строка исходного массива, которая соответствует первому единичному элементу массива ;
во вторую строку массива записывается та строка исходного массива, которая соответствует второму единичному элементу массива ;
и т.д.

Таким образом,

Если результирующий объект имеет вид

, то ранг его также равен двум и элементы определяются по правилу:

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

Таким образом,

Выборка с помощью индексных множеств.

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

Пример 3

Рассмотрим следующие спецификации и присваивания на языке Actus:

var

(*массив параллельных строк*)

para: array [1:100,1..100] of real;

index

(*множество целых чисел от 1 до 100, исключая числа 11 - 90*)

i=1:10,91:100;

(*множество нечетных чисел от 1 до 100*)

odd=1:(2)99;

(*множество четных чисел от 1 до 100*)

even=2:(2)100;

Тогда конструкция para [i,1..100] означает строки массива para, из которого исключены строки 11 – 90. Доступ к оставшимся строкам может выполняться параллельно. Аналогично, конструкция para [odd,1..100] означает нечетные строки массива para, а para [even,1..100] - четные строки массива para. Доступ к указанным строкам может выполняться параллельно.

Над индексными множествами в языке Actus определены теоретико-множественные операции объединения, пересечения и разности.

Индексация сдвигом.

Суть индексации сдвигом покажем на примере.

Пример 4

Рассмотрим фрагмент Actus-программы

var

(*параллельные одномерные массивы*)

para, parb: array [1:100] of integer;

index

(*множество целых чисел от 1 до 50*)

first50=1:50;

Тогда конструкция para [first50] := parb [first50] + parb [first50 shift 1] определяет параллельное сложение элементов 1 – 50 массива parb с элементами 2 – 51 этого же массива. Если значение целого выражения после операторов shift, rotate положительно, то сдвиг осуществляется «справа налево». В противном случае – «слева направо».