СКИПОДы 2007 полная версия (1127795), страница 47
Текст из файла (страница 47)
Начальная конфигурация выбираетсяпроизвольным образом. Игровое поле может иметь края или может быть свернуто в тор.Вот пример конфигурации: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 .
Для многомерных циклов для всех пар (f,q)определяются направляющие вектора, элементы которых состоят из символов (=, >, <) впозиции соответствующего индекса, которая определяется порядком индексов в гнездецикла. В примере Лемпорта (исходном) для А вектор имеет вид: (<,=).Для тела цикла, состоящего из одного оператора, отношения, и соответственно,семантика выполнения, могут быть: < > = и их сочетание.
Например, тело цикла: A(I) =(А(I)+A(I+1))/2 допускает векторное выполнение; оно невозможно при наличии воператоре хотя бы одного соотношения: f>q. Для тела цикла: A(I) = A(I+C))/2 при С>0возможно синхронное выполнение, при С=0 кроме синхронного, возможно параллельноеасинхронное; а при С<0 параллельное выполнение невозможно.Для многомерных (тесногнездовых) циклов такое исследование может проводиться длякаждого параметра, а для распараллеливания выбираться наиболее оптимальный вариант.Для самого внутреннего цикла определение следования можно проводить, считая егоодномерным. Для любого другого цикла, исследование можно проводить по такой жесхеме, если семантика цикла допускает перестановку его на позицию самого внутреннего.Перестановка допустима, если для всех новых направляющих векторов крайне левый,отличный от = , элемент сохранил направление.
Например, для двумерного цикла,наличие вектора (<,>) делает перестановку некорректной. Так для цикла:156DO 99 J=2,MDO 99 K=2,M99 U(J,K) = (U(J+1,K)+U(J,K+1)+U(J-1,K)+U(J,K-1)) .25направляющие вектора:1 <U(J,K),U(J+1,K)> = (<,=)2 <U(J,K),U(J,K+1)> = (=,<)3 <U(J,K),U(J-1,K)> = (>,=)2 <U(J,K),U(J,K-1)> = (=,>)Отсюда:- операторы циклов по I и J можно менять местами,- часть оператора, включающая вхождения из векторов 1 и 2, можно вынести в отдельныйоператор, который векторизуется как по I так и по J.Для двух операторов тела цикла отношения следования переменных с индексами можносистематизировать и кодировать так (qi в общем случае, список - информационные поля qи f) : А - независимые отношения В - (qi>qj) , C - (qi<qj) , K - (qi=qj) G - B+K,B+C,B+K+C ,Н - неоднозначные отношения.
Тогда по координатам приводимой ниже таблице можноопределить типы связей и метод выполнения цикла для этих операторов. Если объединитьинформационные поля двух операторов , то таблицу можно использовать для анализатретьего оператора и т.д.* Таблица решений для метода координат* Оператор 1 O1 = I1 Oi,Ii - список переменных с индексами* Оператор 2 O2 = I2 -> - порядок анализа отношений*--------------------------------------------------------------------*.O2 -> I1.*. A . B .
K . C . G . H .*. HEЗАВ. . O > I . O = I . O < I . O <=>I * .* I2 -> O1 ...... .*---------------------------------------------------------------------*.......* A HEЗАВ. . P . R . S . M . R(K,C). T .*______________________________________________________________________*.......* B I > O .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
