Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 4
Текст из файла (страница 4)
Пусть элементы массива al используются в качестве аргументов только оператором Sβ, условия отсутствия коммуникаций между процессорами не выполняются для двух фиксированныхнаборов индексов l, β, q1, ξ и l, β, q2, ξ (q1 ≠ q2), функция Fl ,β,q1 стоит влевой части оператора Sβ, функция Fl ,β,q2 – в правой части, и существует истинная зависимость, порожденная входами q1 и q2 массива al(Ti )в оператор Sβ. Пусть множества Vβявляются невырожденными, гдеTi – различные значения t (β) ( I ), I ∈ Vl (,βF,q)1 , и выполняется условие(β)(β)Π U≠ 0.17Тогда можно организовать трансляцию данного al(F) на каждойитерации Ti между процессорами P (c (β) ( J )), J ∈ Vβ(Ti ).Замечание. При выполнении условий утверждения 2 до трансляции данного al(F) необходимо осуществить передачу al(F) от процессора P ( d (β) ( F )) к процессору P (c (β) ( J 0 )) такому, что t (β) ( J 0 )) = T0лексикографически наименьший вектор из векторов Ti .
Трансляциюследует осуществлять согласно лексикографической упорядоченностивекторов Ti . При выполнении условий утверждения 3 до начала трансляции данного al(F) необходимо осуществить передачу al(F) от процессора P ( d (β) ( F )) к процессору P (c (β ) ( J 1 )) такому, что c (β) ( J1 )лексикографически наименьший вектор из векторов c (β) ( J ); послетрансляции необходимо осуществить передачу al(F) от процессораP (c (β) ( J 2 )) такого, что c (β ) ( J 2 ) лексикографически наибольший вектор из векторов c (β) ( J ), к процессору P (d (β) ( F )).
Трансляцию следует осуществлять согласно лексикографической упорядоченности векторов c (β) ( J ), J ∈ Vβ(Ti ).3. Установление схемы обмена даннымиРассмотрим задачу установления схемы обмена данными. Пустьдля аффинного гнезда циклов найдены функции cξ(β ) , d ξ( l ) и t ξ(β) , т.е.найдено распределение операций и данных по процессорам и установлен порядок выполнения операций процессорами (см.
например [1, 4,5]). Пусть для некоторого фиксированного набора l, β, q, ξ условияотсутствия коммуникаций между процессорами не выполняются.Утверждения 1–3 позволяют определить группы процессоров, между которыми можно организовать бродкаст или трансляцию данных.В случаях, неоговоренных утверждениями 1–3, на итерации T можноорганизовать коммуникацию точка-точка между процессорамиP ( d (l ) ( Fl ,β,q ( J ))) и P (c (β ) ( J )) для передачи данного al ( Fl ,β,q ( J )),где вектор J такой, что t (β) ( J ) = T .Между процессорами каждой группы, для которой установлен видкоммуникации, обмен данными следует организовать, пользуясь сле18дующими правилами очередности передачи и приема данных.Пусть данное передается от процессора, в локальной памяти которого оно хранится. Передачу данного следует осуществлять после того,как будут выполнены все операции, которые его переопределяют ивыполняются в исходной программе до операции Sβ(J), и после того,как процессор осуществит прием результатов этих операций от другихпроцессоров.
Пусть данное передается от процессора, в котором онопереопределяется. Передачу данного следует осуществлять после выполнения операции Sβ(J). Пусть данное передается от процессора, который использует его в качестве аргумента. Передачу данного следуетосуществлять в начале итерации.Пусть данное передается процессору, в локальной памяти которогооно хранится. Прием данного следует осуществлять до того, как будутвыполняться все операции, которые используют это данное в качествеаргумента и выполняются в исходной программе после операции Sβ(J),и до того, как процессор осуществит передачу аргументов этих операций другим процессорам. Пусть данное передается процессору, который использует его в качестве аргумента. Прием данного следует осуществлять до выполнения операции Sβ(J).Литература1.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СанктПетербург. БХВ-Петербург. 2002. 608 с.2. Лиходед Н.А. Отображение аффинных гнезд циклов на независимыепроцессоры. Кибернетика и системный анализ. 2003. 3. С. 169–179.3. Lim A.W., Liao S.-W., Lam M.S. Blocking and array contraction acrossarbitrary nested loops using affine partitioning. Proceedings of the ACMSIGPLAN Simposium on Principles and Practice of Programming Languages,2001.4.
Фролов А.В. Оптимизация размещения массивов в Фортранпрограммах на многопроцессорных вычислительных системах. Программирование. 1998. 3. С. 70–80.5. Adutskevich E.V., Likhoded N.A. Mapping affine loop nests: solving ofthe alignment and scheduling problems. Proc. 7th Int. Conf. on Parallel Computing Technologies (PaCT-2003).
Nizhni Novgorod, Russia. Sept. 15–19, 2003.Berlin: Springer, 2003. P. 1–9.6. Dion M., Randriamaro C., Robert Y. Compiling affine nested loops: howto optimize the residual communications after the alignment phase? J. of Paralleland Distrib. Computing. 1996. Vol.
30, 2. P. 176–187.19МОДЕЛИРОВАНИЕ ГРАВИТАЦИОННОГО ТЕРРИГЕННОГООСАДКАО.Е. Амосова, Ю.А. ТкачевИнститут геологии Коми НЦ УрО РАН, СыктывкарНами предпринята попытка исследования структуры обломочныхгорных пород и осадков компьютерным моделированием осаждениячастиц и получающейся при этом их упаковки. Задача имеет большоезначение в нефтяной геологии, в фациальной диагностике природныхосадков и в технологии получения композиционных материалов.Для моделирования мы использовали современные ПК (PentiumMMX 233, AMD Athlon XP 1600+ 785 904Кб ОЗУ), тем не менее, программа оказалась критической как по размеру используемой памяти,так и по времени выполнения.
Максимальное число частиц в осадкедостигало только 7700, тогда как для статистики необходимо, чтобыосадок состоял из нескольких десятков тысяч частиц. Один эксперимент на Pentium MMX 233 непрерывно обсчитывался около недели. НаAMD Athlon XP 1600+, гораздо более мощном по производительности,моделирование заняло несколько минут, так моноразмерный осадок,состоящий из 7000 частиц был получен за 3 минуты 10 секунд, двухразмерный насыщенный, с отношением диаметров крупных и мелкихчастиц равным 5, состоящий из 7360 частиц, – за 6 минут.
Нам удалосьполучить характеристики структуры лишь самых простых «осадков»:шарообразных частиц одного и двух размеров. Реальные осадки состоят из частиц различной формы (в аппроксимации – эллипсоидов с различным соотношением осей от вытянутых иглообразных до почти плоских лепешкообразных). Смоделировать такой осадок не представлялось возможным ввиду резкого увеличения времени счета (около недели на один вид осадка).Предложенное нами компьютерное моделирование осадка заключаетсяв следующем. Пусть задана функция распределения частиц осадка (илиосадочной породы) по размерам f (d) – гранулометрическая кривая.
Впервом приближении будем считать частицы шарообразными и осаждающимися в некой абстрактной среде (газе, жидкости, пустоте), никакне взаимодействующей с осаждающимися частицами. В этой среде нетвихрей, нет упругих аэро- или гидродинамических, электрических,магнитных сил, сил трения, действующих на частицы, а есть толькосила тяжести и силы реакции опоры, возникающие при соприкосновении частиц. За этими исключениями процесс моделирования гравита20ционного осадка соответствует физическому процессу осаждения.
Моделирование осаждения производится в емкость или седиментационный «контейнер» параллелепипедальной формы. При визуализации наэкране компьютера емкость простирается на всю ширину и высоту экрана и на заданную величину вглубь экрана. Над емкостью моделируется шарообразная частица диаметра d, получаемого с вероятностями,снятыми с гранулометрической кривой. Центр частицы находится назаданной высоте. Две другие координаты (горизонтальные) имеют случайное равномерное распределение над емкостью. Частица движетсявертикально вниз, пока не опустится надно, либо не коснется уже покоящихсячастиц.
Коснувшись одной из них, частица будет скатываться по ней, пока некоснется следующей частицы и так да3лее, пока по сложной траектории, скатываясь в ямки или проникая глубоко восадок по поровым каналам, не опус1тится на дно, либо не займет устойчивоеположение (получит три точки опорывнутри осадка). Траектория движения2осаждающейся частицы представляет собой кривую в пространстве, состоящуюиз отдельных элементов – дуг окружностей и отрезков прямых (рис. 1). ТраРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
