ПОД (пособие) (1184372), страница 47
Текст из файла (страница 47)
Если значения элементов массиваопределяются довольно сложным выражением, а вычислять их надо многократно, товекторизация или распараллеливание цикла для вычисления элементов массива можетоказаться очень эффективным. В отдельный параграф мы вынесли решение системдифференциальных уравнений, что по своей сути также является обработкой массивовфункций, производных и т.д. Но на самом деле эффективными могут также бытьвычисления сверток, сумм, функций от каждого элемента массива и т.п.Конечно, не имеет смысл векторизовать или распараллеливать действия надкороткими массивами кроме тех случаев, когда собственно вычисления каждого элементазанимают большое время.Двумерные массивыПри исполнении вложенных циклов эффективно распараллеливаются самыевнешние циклы, а векторизуются только внутренние.
Однако практически все действия сматрицами (сложение, умножение, умножение на вектор, прямое произведение) могут бытьвыполнены быстро на супер-ЭВМ. Многие алгоритмы линейной алгебры (но не все) могутбыть эффективно векторизованы и распараллелены.
Некоторые библиотеки подпрограмм(например, LAPACK(?)) существуют для параллельных и векторных машин.Совершенно неэффективно использовать векторные ЭВМ для работы с матрицамиразмерности 3x3. Но можно переписать алгоритм для одновременной обработки нескольких(к примеру 1000) матриц - обращение, поиск собственных чисел и т.д.При увеличении размера матриц растет эффективность работы программы, но растети размер требуемой памяти для хранения матриц. При работе на векторной машине снебольшим (128-512 Мбайт) объемом ОЗУ это может стать причиной общего снижения еебыстродействия из-за частого обращения к дискам при записи/чтении данных.Вычисления в узлах сеток и решетокИнженерные и научные задачиВо многих областях знания встречаются задачи, которые сводятся к вычислениюэволюции объектов, расположенных в дискретных точках и взаимодействующих сближайшими соседями.
Простейшей и, наверно, наиболее широко известной такой задачейявляется игра "жизнь".Все игровое поле представляет двумерную сетку с квадратными ячейками. Каждаяячейка может быть в одном из двух состояний - пустая или живая. Если на каком-то шагеигры вокруг пустого поля существуют ровно три живых поля, то на следующем шаге игры вэтом поле рождается жизнь. Если число живых полей вокруг пустого поля не равно трем, тов это поле остается пустым. Если вокруг живого поля существуют два или три другихживых поля, то жизнь в в этом поле продолжается.
Если число живых соседей отлично отдвух или трех, то поле погибает (становится пустым). Начальная конфигурация выбираетсяпроизвольным образом. Игровое поле может иметь края или может быть свернуто в тор.Вот пример конфигурации:oooОбозначения:oxoOo - пустыеOXOXx - живыеoxoO - родится, o - останетсяoooX - останется, x - погибнетПример игры реализован в качестве заставки на дисплее в системе OpenWindows на ЭВМфирмы SUN.154В игре "жизнь" реализуется простейшая модель "взаимодействия" пустых и живыхячеек с соседями, определяющая эволюцию всей системы. Но вот пример из физики,который по способу построения модели идентичен этой игре. Модель магнетиков Изингапредставляет собой набор спинов (элементарных магнитов), расположенных в узлахрешетки и взаимодействующих только с ближайшими соседями.
Вычислительный интереспредставляют трех- и четырехмерные модели. Двумерные Изинговские магнетики санизотропными (зависящими от направления) дальними взаимодействиями (т.е. не только сближайшими, но и через один узел) также нельзя исследовать аналитически, а только спомощью компьютерных экспериментов. Очевидно, что алгоритм построения эволюцииИзинговских магнетиков будет во многом идентичен алгоритму игры.Многие молекулярные модели сплошных сред в статистической физике такжестроятся по принципу узлов (или ячеек) в кубической решетке. Молекулы могутрасполагаться только в ячейках.
Взаимодействия молекул в соседних ячейках определяютих ориентацию (для несферических молекул) и предпочтительность (вероятность)переходов в соседние пустые ячейки.В задачах по динамике сплошных сред (аэро- и гидродинамика) также применяетсяметод разбиения всего пространства на маленькие объемы и моделирование перемещенияэтих объемов при движении твердых тел или при обтекании средой неподвижныхпредметов.Инженерные расчеты по распределению нагрузок в сложных конструкциях такжемогут проводиться в рамках сеточных моделей. Всю конструкцию можно рассматриватькак сетку, в которой каждое соединение узлов имеет определенные силовые коэффициентыи предельные нагрузки на сжатие и растяжение.
Таким образом можно моделироватьдеформацию конструкции и предельную нагрузочную способность при приложении силы влюбой точке конструкции.Видно, что класс задач, использующих сеточные методы довольно широк и крайневажен. В следующем параграфе мы рассмотрим алгоритмы решения таких задач.Алгоритмы преобразования программ методом координат.Одним изметодов распараллеливания программ является метод координат,обеспечивающий векторизацию циклов для синхронных ЭВМ (ОКМД - SIMDархитектуры). Семантика синхронных циклов следующая: для каждой итерации цикланазначается процессор;вычисления должны производиться всеми процессорами(процессорными элементами) параллельно и синхронно. Операторы тела циклавыполняются по очереди, но каждый оператор выполняется всеми процессорамиодновременно.
При выполнении оператора присваивания сначала вычисляется правая часть,затем одновременно выполняется операция присваивания для всех элементов массива левойчасти.Теоретическое обоснование классического метода координат предложено Лэмпортом.Метод применим для канонических ("чистых") циклов, тела которых состоят только изоператоров присваивания, причем управляющая переменная заголовка цикла (параметрцикла) должна входить в индексные выражения операторов тела цикла линейно. Методпредназначен для синхронной векторизации одномерных циклов (многомерные циклыможно рассматривать по каждому параметру отдельно). Идея данного метода состоит в том,что для индексов, содержащих параметры цикла, рассматривается порядок следования,который и определяет очередность выборки/записи соответствующего элемента массива.Так как рассматриваются только линейные индексные выражения, порядок следованияопределяется значениями соответствующих алгебраических выражений.
Строится графхарактеристических множеств всех индексов, и при отсутствии в графе петель делаетсязаключение о возможности векторизации всего цикла.155В некоторых случаях (устранимая векторная зависимость) векторизация возможна лишьв случае переупорядочивания - перестановки операторов цикла или путем введениявременной переменной (массива), куда будут копироваться элементы вектора для защитыперед их изменением для последующего использования в исходном виде. Итак, методкоординат:- позволяет определить возможность выполнения цикла в синхронном режиме;- содержит алгоритмы преобразования тела цикла к синхронному виду.Например, по Лэмпорту, цикл:DO 24 I=2,MDO 24 J=2,N21 A(I,J) = B(I,J)+C(I)22 C(I) = B(I-1,J)23 B(I,J) = A(I+1,J) ** 224 CONTINUEпреобразуется в цикл:DO 24 J=2,NDO 24 SIM FOR ALL I {i:2<=i<=M}C SIM - SI Multeneusly (одновременно)TEMP(I) = A(I+1,J)21 A(I,J) = B(I,J)+C(I)23 B(I,J) = TEMP(I) ** 222 C(I) = B(I-1,J)24 CONTINUEКонструктивный алгоритм реализации метода координат.Пусть, цикл одномерный, все операторы тела - операторы присваивания, в левых частяхкоторых - переменные с индексом - параметром цикла.
Индексы линейные, т.е. имеют видi+/-b,где b - константа. Определяются отношения следования для всех пар одноименныхпеременных с индексами:генерируемых переменных (переменные в левой частиоператоров присваивания - f) и используемых переменных (входящих в формулы правыхчастей - q). Отношение следования для одной пары зависит от порядка обращения кодному и тому же элементу массива при выполнении цикла. Так, для A(I) = A(I+1)отношение можно кодировать: f<q .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
