Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину

Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину

У статті розглядається задача моделювання процесу фільтраційної консолідації ґрунтів під дією двокомпонентного розчину. Математична модель таких процесів в одновимірному випадку поширюється на тривимірний та пропонується ряд паралельних алгоритмів розв’язання задач щодо неї, зокрема багатопоточний а...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
Datum:2011
1. Verfasser: Богаєнко, В.О.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/48792
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину / В.О. Богаєнко // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2011. — Вип. 5. — С. 20-35. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-48792
record_format dspace
spelling Богаєнко, В.О.
2013-09-03T18:14:24Z
2013-09-03T18:14:24Z
2011
Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину / В.О. Богаєнко // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2011. — Вип. 5. — С. 20-35. — Бібліогр.: 11 назв. — укр.
XXXX-0059
https://nasplib.isofts.kiev.ua/handle/123456789/48792
519.6
У статті розглядається задача моделювання процесу фільтраційної консолідації ґрунтів під дією двокомпонентного розчину. Математична модель таких процесів в одновимірному випадку поширюється на тривимірний та пропонується ряд паралельних алгоритмів розв’язання задач щодо неї, зокрема багатопоточний алгоритм, алгоритми для кластерних систем та графічних процесорів (GPU).
Problem of modeling filtration consolidation processes in soils under the influence of bi-component solution has been considered in the paper. One-dimensional mathematical model of such processes has been extended to three-dimensional case and a set of parallel algorithms for solving problems about it have been proposed, in particular, multithreaded algorithms, algorithms for cluster systems and graphical processors (GPU).
uk
Інститут кібернетики ім. В.М. Глушкова НАН України
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
Parallel algorithms for modeling of filtration consolidation under the influence of two-component solution
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
spellingShingle Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
Богаєнко, В.О.
title_short Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
title_full Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
title_fullStr Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
title_full_unstemmed Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
title_sort паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину
author Богаєнко, В.О.
author_facet Богаєнко, В.О.
publishDate 2011
language Ukrainian
container_title Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Parallel algorithms for modeling of filtration consolidation under the influence of two-component solution
description У статті розглядається задача моделювання процесу фільтраційної консолідації ґрунтів під дією двокомпонентного розчину. Математична модель таких процесів в одновимірному випадку поширюється на тривимірний та пропонується ряд паралельних алгоритмів розв’язання задач щодо неї, зокрема багатопоточний алгоритм, алгоритми для кластерних систем та графічних процесорів (GPU). Problem of modeling filtration consolidation processes in soils under the influence of bi-component solution has been considered in the paper. One-dimensional mathematical model of such processes has been extended to three-dimensional case and a set of parallel algorithms for solving problems about it have been proposed, in particular, multithreaded algorithms, algorithms for cluster systems and graphical processors (GPU).
issn XXXX-0059
url https://nasplib.isofts.kiev.ua/handle/123456789/48792
citation_txt Паралельні алгоритми моделювання процесу фільтраційної консолідації під дією двокомпонентного розчину / В.О. Богаєнко // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2011. — Вип. 5. — С. 20-35. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv AT bogaênkovo paralelʹníalgoritmimodelûvannâprocesufílʹtracíinoíkonsolídacíípíddíêûdvokomponentnogorozčinu
AT bogaênkovo parallelalgorithmsformodelingoffiltrationconsolidationundertheinfluenceoftwocomponentsolution
first_indexed 2025-11-25T23:31:40Z
last_indexed 2025-11-25T23:31:40Z
_version_ 1850582637305921536
fulltext Математичне та комп’ютерне моделювання 20 УДК 519.6 В. О. Богаєнко, канд. техн. наук Інститут кібернетики імені В. М. Глушкова НАН України, м. Київ ПАРАЛЕЛЬНІ АЛГОРИТМИ МОДЕЛЮВАННЯ ПРОЦЕСУ ФІЛЬТРАЦІЙНОЇ КОНСОЛІДАЦІЇ ПІД ДІЄЮ ДВОКОМПОНЕНТНОГО РОЗЧИНУ У статті розглядається задача моделювання процесу фільт- раційної консолідації ґрунтів під дією двокомпонентного роз- чину. Математична модель таких процесів в одновимірному випадку поширюється на тривимірний та пропонується ряд паралельних алгоритмів розв’язання задач щодо неї, зокрема багатопоточний алгоритм, алгоритми для кластерних систем та графічних процесорів (GPU). Ключеві слова: фільтраційна консолідація, двокомпонентні розчини, математичне моделювання, паралельні алгоритми. Вступ. Комплексне математичне моделювання консолідації ґрунтів є актуальною проблемою при прогнозуванні гідродинамічних процесів. При цьому важливим є врахування таких факторів, як солоність порово- го розчину, неізонермічність та релаксаційність процесів. На цей час розроблена низка математичних моделей [1—6], що описують такі про- цеси, деякі з яких досліджені лише для одновимірного випадку [4—6]. Процедури розв’язання задач щодо таких моделей мають високу обчис- лювальну складність, що зумовлює необхідність їх адаптації для високо- продуктивних обчислювальних систем, зокрема, кластерів. У цій статті розглядаються паралельні алгоритми для розв’язання задач моделювання процесів фільтраційної консолідації ґрунтів під дією двокомпонентного розчину в неізотермічних умовах у тривимірному випадку. На основі одновимірної, будується тривимірна модель, скін- ченно-елементний алгоритм розв’язання i схеми його розпаралелення для систем з розподіленою та спільної пам’яттю. Математична модель. Розглядається математична модель філь- траційної консолідації ґрунтів у припущені їх ізотропності під дією двокомпонентного розчину з урахування впливу температурного ре- жиму у векторній формі, побудована на основі одновимірної моделі, описаної у [5; 6]:         , , , 1, 2, T v v T T i i i i T CH T div C gradH div gradG t t k C D div gradC u gradC D div gradT i t                     © В. О. Богаєнко, 2011 Серія: Фізико-математичні науки. Випуск 5 21   ,T P T C div gradT C u gradT t        (1)   1 1 2 2 1 1 2 2 , , , , i v v i v C C G C C T k k u grad kH v C v C T                  де H — надлишковий напір, iC — концентрації солей у поровому роз- чині, T — температура, k — коефіцієнт фільтрації, vC — коефіцієнт консолідації, T — коефіцієнт термічного розширення,  — середнє значення пористості ґрунту, iD — коефіцієнти молекулярної дифузії компонентів розчину, iv ,  — коефіцієнти хімічного та термоосмосу, TD — коефіцієнт термодифузії, TC , PC — об’ємна та питома теплоєм- ності порового розчину,  — коефіцієнт теплопровідності. Систему рівнянь (1) доповнимо наступними початковими й кра- йовими умовами:                       1 3 2 1 3 2 1 3 2 1 0 0 1 ( ,0) 0, , , , 0, , 0, ,0 0, , , , 0, , 0, ,0 , , , , 0, , 0, Г Г Г i i i i iГ Г Г Г Г Г H x H x t H H x t H x t n C x C x t C C x t C x t n T x T T x t T T x t T x t n                                  (2) де 1Г — частина границі області моделювання, де відбувається кон- такт з рідиною, 2Г — непроникна частина границі, 3Г — границя проникної основи. У безрозмірних змінних система (1)-(2) прийме наступний вигляд:           ' ' ' ' ' , ' ' ' ' ' ' ' ' , 1, 2, ' ' ' ' ' ', ' T i i i i i H T div gradH div gradG t t C D div gradC u gradC r div gradT i t T div gradT v gradT t                         1 1 2 2' ' ' ' ' ' ',G C C T     (3)  1 1 2 2' ' ' ' ' ' ' ' ' ,u grad u H v C v C T      1 1 1 2 2 1' ' ' ' ' ' ' ' ' ,v grad u H C C T       де Математичне та комп’ютерне моделювання 22 0 1 ' ,T T T H    ' ,vt C t 1' / ,H H H ' ,i i v D D C  0 0 ,T i v i D T r C C  ' , T vC C   0' / ,i i iC C C 0' / ,T T T 0 1 ' ,i i i v C C H    0 1 ' , v T C H    0 01' , ' , ' ,i i i v v v v C TkH u v C C C     1' ', p T C u u C   ' ' , p i i T C v C    1' ' p T C C    .                 31 2 1 3 2 1 3 2 1 1 0 1 1 0 '( ,0) 0, ' , ' 1, ' , ' 0, '( , ') 0, ' ( ,0) 1, ' , ' ' , ' , ' 0, ' , ' 0, '( ,0) 1, ' , ' ' , ' , ' 0, ' , ' 0. ГГ Г i i i i i iГ Г i Г Г Г Г H x H x t H x t H x t n C C x C x t C C x t C x t C n T T x T x t T T x t T x t T n                                    (4) У подальшому знак штрих над безрозмірними величинами опустимо. Скінченно-елементна дискретизація. Систему (3)—(4) дискре- тизуємо за методом скінченних елементів. Будемо шукати її розв’язок у вигляді (1) (2) 1 1 2 1 1 (3) (4) 2 3 4 1 1 ( ) ( ) ( ), ( ) ( ) ( ), ( ) ( ) ( ), ( ) ( ) ( ), v v v v N N i i i i i i N N i i i i i i H a t N x W x C b t N x W x C q t N x W x T p t N x W x                           (5) де ( ) ( )j iN x  — базисні функції vN -вимірного підпростору простору Соболева функцій, що задовольняють крайовим умовам для відпові- дних величин ( H для 1j  і т.д.), а 1( )W x  — відомі функції, які за- довольняють цим умовам. Перейшовши до варіаційної постановки задачі (3)—(4) та врахо- вуючи (5) отримуємо систему звичайних диференціальних рівнянь щодо коефіцієнтів   1 ( ) ,vN i i A a t      1 ( ) ,vN i i B b t      1 ( ) ,vN i i P p t      1 ( ) vN i i Q q t    : 1 2 1 0,T dA dP M LA M F dt dt        Серія: Фізико-математичні науки. Випуск 5 23 3 1 2 4 2 3 0, 0, dB M L B F dt dQ M L Q F dt               (6) 5 3 4 0, dP M L P F dt       де    (1) (1) (1) (4) 1 2, , , ,ij j i ij j iM N N M N N   (2) (2) 3 , ,ij j iM N N  (3) (3) 4 , ,ij j iM N N  (4) (4) 5 , ,ij j iM N N (1) (1)3 1 , ,j i ij k k k dN dN L dx dx            (2) (2) (2)3 3 (2) 1 1 2 2 1 1 (1)(2) (2) (2) (2) (2) (2)1 1 , , , , , , , v j i i ij j k kk k k k N i l i i j l j j lk k k k k k dN dN dN L D uH v C T N dx dx x dx dNdN dN dNdW H N a N N x dx dx dx dx dx                                                (3) (3) (3)3 3 (3) 2 2 1 1 1 1 (4) (4) (4)3 3 (4) 3 1 1 1 2 2 1 1 , , , , , , j i i ij j k kk k k k j i i ij j k kk k k k dN dN dN L D uH v C T N dx dx x dx dN dN dN L u H C C N dx dx x dx                                               (1)3 1 1 1 1 2 2 1 (1) (4) (1) (1) 4 1 , , , , , , v j j k k k N j l i i l lk k k k k k dN F W C C T x dx dN dN dN dNdW T p x dx dx dx dx dx                                            (2)3 2 1 2 1 1 2 3 (2)1 2 1 2 2 1 , , , j j k k k j k k k k dN F D W rT x dx C dW v uH v C T N x x dx                               Математичне та комп’ютерне моделювання 24 (4) (2) (2) (2)2 2 4 2 1 , , , , vN l j l j j lk k k k k k dNdW dW dW dW T N p N N x dx dx dx dx dx                   1 2 1 2 1 2 2 (2) (2) (2) (2)1 1 1 2 (2) (2)2 2 1 , ) , 2 , , , v vN N l l j l l j l lk k k j j k k k dN dNC N b b N x dx dx dW dW C N N x dx dx                                           (3)3 3 2 3 2 1 2 3 (3)32 2 1 1 1 2(4)3 3 (4)4 4 4 1 1 1 2 2 1 1 , , , , ( , , j j k k k j k k k k j j j k kk k k k k dN F D W r T x dx dWC v uH v C T N x x dx dNW dWT F uH C C N x dx x x dx                                                                       (1) (2) 1 1 3 2 (3) (4) 4 3 5 0 4 (0) (1 ), , (0) , , (0) , , (0) , . i i i i i i i i M A W N M B W N M Q W N M P T W N              (7) Задачу (6), (7) будемо розв’язувати за допомогою наступної лі- неаризованої неявної різницевої схеми [5—7]:               1 2 1 3 1 2 4 2 3 5 3 4 , , 0, , , , , , 0, , , , , , 0, , , , , , 0, t T t t t t M A LA M P F B Q P M B L A Q P B F A B Q P M Q L A B P Q F A B Q P M P L A B Q P F A B Q P                           (8) де  , , ,A B Q P — вектори коефіцієнтів на поточному кроці,  , , ,A B Q P    — вектори коефіцієнтів на попередньому кроці,  , , , t A B Q P      1 , , , , , ,A B Q P A B Q P      — різницеві похідні по часу. Введемо наступні позначення: Серія: Фізико-математичні науки. Випуск 5 25  , , ,A B Q P  ,   ( ) ( ) , ,I J IJ j i i j M N N ( ) ( )3 1 , , , I J j i IJ k k k i j dN dN М dx dx             ( ) ( )3 ( ) 1 1 , ( ) , v I JN Kl i IJK I I l j k l k k i j dN dN S N dx dx                , ( )3 ( ) 1 , , J KiI IJK j k k k i j dNdW W N dx dx             , (9) ( )3 1 , J iI IJ k k k i dNdW w dx dx             , 3 (2) ( ) 1 , KJI iIJK k k k i dWdW w N dx dx             , 2 3 (2) (2)1 1 1 ( ) ( , j k k j C a C N x               . Слід зазначити, що ( ) ( )IJK I J JIK J IS K K S K K . Враховуючи (6) у позначеннях (9) система (8) прийме наступний вигляд:         1 2 0 1 2 11 11 1 21 21 2 31 31 41 41 1 1 1 1 , T T M A M P M A M P М A w М B w М Q w М P w                                            3 212 212 1 (2) (2) 3 1 22 22 122 1 1212 (2) 2 322 322 232 232 M B u S B W A M B D М B w u W B w v a C v S Q B W B W Q w                                    (2) 422 422 242 1 42 42242 ,S P B W B W P w r M P w            (10)             4 313 313 1 323 323 2 (2) (2) 4 2 33 33 133 1 233313 323 M Q u S Q W A v S Q W B M Q D М Q w u W Q w v W Q w                                 (2) (2) 433 433 343 2 43 43 2 2343 ,S P Q W Q W P w r M P w v a C              Математичне та комп’ютерне моделювання 26                    5 1 414 414 1 424 424 (2) 2 434 434 3 5 44 44 (2) (2) (2) 1 144 1 244 2 344414 424 434 1 1 . M P u S P W A S P W B S P W Q M P М P w a T u W P w W P w W P w                                         У матричному вигляді систему лінійних алгебраїчних рівнянь (10) можна представити як ,A               00 03 10 11 20 21 22 30 31 32 33 1 2 212 212 3 313 313 1 323 323 4 1 414 414 1 424 424 2 434 434 5 0 0 0 0 0 1 1 0 0 ( ) 0 0 , ( ) ( ) 0 1 ( ) ( ) ( ) T A A A A A A A A A A A A M M u S B W M u S Q W v S Q W M u S P W S P W S P W M                                                          (11) де  0 1 2 3, , ,      — вектор правих частин рівнянь (10). Алгоритм розв’язання системи лінійних алгебраїчних рів- нянь. Спеціальний вид матриці A системи лінійних рівнянь (11), яка виникає після дискретизації розглядуваної задачі, дозволяє розв’язува- ти її використовуючи декомпозиційний підхід за наступним ітерацій- ним процесом:         ( 1) ( )1 00 0 03 ( 1) ( 1)1 11 1 10 ( 1) ( 1) ( 1)1 22 2 20 21 ( 1) ( 1) ( 1) ( 1)1 33 3 30 31 32 , , , . k k k k k k k k k k k A A A A B A A A Q A A A A B P A A A A B A Q                           (12) Оцінимо обчислювальну складність цього алгоритму. Серія: Фізико-математичні науки. Випуск 5 27 Будемо розв’язувати розріджені СЛАР за допомогою ітерацій- них методів, зокрема BiCGStab [8], складність яких пропорційна кі- лькості ненульових елементів ( )V A матриці A : ( )sT k V A . Тоді складність обчислень по формулі (12), у припущенні, що коефіцієнти складності розв’язання СЛАР рівні, можна оцінити як                        1 00 11 22 33 03 10 20 21 30 31 32 . sT k V A V A V A V A V A V A V A V A V A V A V A             (13) У припущені, що кількість ненульових елементів у підматрицях матриці A рівна, оцінка (13) прийме вигляд    1 1 7 4 16sT k V A V A  , а складність розв’язання системи A   декомпозиційною проце- дурою (12)    1 2 1 4 7 16f sT k k V A  , (14) де 2k — кількість ітерацій процесу (12). З іншої сторони, складність розв’язання безпосередньо системи (11) складає  2 sT k V A . (15) Порівнюючи оцінки (14) та (15) доходимо до висновку, що за умови, коли як система A   , так і її підсистеми ii i iA    розв’язуються за однакову кількість ітерацій, схема (12) матиме мен- шу складність при 2 3k  . Кількість ітерацій 2k для розглядуваної задачі залежить від зна- чення коефіцієнту термічного розширення T . Обчислювальні екс- перименти показали, що умова 2 3k  виконується при 110T  , в той час, коли значення T речовин мають порядок 4 610 10  . Паралельні алгоритми для кластерних систем. При викорис- танні для розрахунків розподіленої обчислювальної системи, будемо розподіляти матрицю A по ній за рядками, що є оптимальною схе- мою для паралельного обчислення множення матриці на вектор, опе- рації, на виконання якої витрачається більшість часу при розв’язанні СЛАР ітераційними методами. Позначимо як ( )iA блок рядків матриці A , який зберігається у пам’яті процесу i , а як ( , )i jA — підматрицю матриці A , яка зберіга- Математичне та комп’ютерне моделювання 28 ється у пам’яті процесу i , а діапазон її стовпців відповідає діапазону рядків, що зберігаються у пам’яті процесу j . Тоді при виконанні операції множення розподіленої розрідженої матриці A на вектор y , обміни фрагментами вектора y відбувають- ся лише між процесами i та j для яких ( , ) ( , )0 0i j j iA A   . Обчислення значень елементів матриці A та вектора правої час- тини  розпаралелюється за даними й не потребує обмінів. Обсяг же обмінів між процесами при розв’язанні СЛАР зале- жить від структури матриці. Подібна схема розпаралелення породжує задачу оптимального завантаження процесорів, яка виникає через різну кількість ненульо- вих елементів у рядках розрідженої матриці A . Час роботи паралельного алгоритму можна оцінити як    ( ) ( ) ( ) 43 max maxi i i P ex i i T k k V A N   , (16) де ( ) 3 ik — коефіцієнт складності обчислення значень елементів СЛАР, 4k — коефіцієнт складності розв’язання СЛАР, ( )i exN — об’єм обмінів даними, що їх здійснює процес i , P — кількість процесів. Виникає оптимізаційна задача знаходження такого розподілу рядків  1,..., PR R R , який мінімізував би оцінку (16). У реалізованому паралельному алгоритмі ця задача наближено розв’язується наступним чином:  задля мінімізації обмінів даними використовується перенумеру- вання рядків й стовпців матриці за алгоритмом Катхіла-МакКі [9];  окремо розв’язується задача рівномірого завантаження процесів обчислювальними задачами. Починаючи з однакових розмірів блоків ( )iA , блоки послідовно збільшуються чи зменшуються та- ким чином, щоб    ( ) ( ) ( ) 43 1 ( ) maxi i i P ex i k k V A T N P    . При цьому значення коефіцієнтів ( ) 3 ik та 4k оцінюються, а ( )i exN — вимірю- ється в процесі роботи алгоритму. Окрім цього, в межах одного вузла кластерної системи, який міс- тить багатоядерні процесори, обчислення можна організувати викорис- товуючи багатопоточне розпаралелення. При цьому один процес займає весь вузол системи й на кожному з ядер виконується один з його потоків. Різниця між такою схемою й схемою, коли кожен процес розподіленої програми виконується на одному ядрі, полягає в тому, що не знижуючи швидкодії розрахункової частини алгоритму, обміни даними виконують- Серія: Фізико-математичні науки. Випуск 5 29 ся між меншим числом процесів, що є ефективним у випадку, коли обсяг обмінів збільшується при збільшені числа процесів. У випадку розглядуваної задачі, залежність обсягу обмінів від числа процесів визначається структурою матриці A , яка у свої чергу залежить від форми області моделювання та її дискретизації на скін- чені елементи. Паралельний алгоритм для графічних процесорів (GPU). Графічні процесори є високопродуктивними обчислювальними сис- темами, які проте мають певні архітектурні особливості, що усклад- нює розробку ефективних алгоритмів та програм для них. Обчислення на GPU є масово-паралельними, при чому потоки обчислень об’єднуються у блоки й засоби синхронізації існують ли- ше в межах блоків. С точки зору доступу до пам’яті, у сучасних GPU виділяють повільну глобальну пам’ять, до якої мають доступ всі по- токи, й більш швидку локальну, яка розділяється між потоками в ме- жах блоку. В додачу до цього, декілька операцій доступу до пам’яті при виконанні певних умов можуть бути об’єднані в одну, що суттєво пришвидшує виконання програми. Враховуючи ці особливості, побудову алгоритмів для GPU мож- на розбити на такі етапи:  виділення незалежних блоків обчислень;  оптимізація доступу до пам’яті;  оптимізація відношення кількості арифметичних операцій та опе- рацій доступу до пам’яті (чим більше це відношення, тим ефекти- вніше буде виконуватись програма);  вибір оптимальної кількості потоків та групування потоків у блоки. Виділяють [10] декілька варіантів алгоритмів формування СЛАР у методі скінчених елементів відштовхуючись від того, обчислення стосовно яких елементів проводиться кожним потоком:  формування по ненульовим елементам матриці;  формування по рядках матриці;  формування по окремим скінченим елементам. У перших двох випадках обчислення є апріорі незалежними, у третьому — скінчені елементи мають бути розбиті на підмножини, в межах яких елементи не мають спільних вершин. Стандартним під- ходом до проведення такого розбиття є фарбування скінченоелемен- тної сітки, як графу залежностей між елементами. В кожному з цих підходів існує можливість блокування потоків й використання лока- льної пам’яті для доступу до даних, які необхідні всім потокам з бло- ку. В усіх випадках, для доступу до елементів розрідженої матриці ефективно використовувати наперед прораховані індекси елементів Математичне та комп’ютерне моделювання 30 замість дуже неефективної при реалізації на GPU операції їх пошуку в процесі розрахунків. Питання оптимізації доступу до пам’яті GPU є важливим при реалізації алгоритмів розв’язання СЛАР й, в першу чергу, операції множення розрідженої матриці на вектор. Оскільки алгоритм мно- ження безпосередньо залежить від формату зберігання матриці, зада- ча оптимізації доступу до пам’яті зводиться до задачі знаходження такого формату зберігання, якій дав би можливість якнаймога в бі- льшому об’ємі використовувати спільну між потоками пам’ять й об’єднувати операції доступу до неї. З найчастіше використовуваних форматів можна виділити [11] покоординатний, стиснутий рядковий (compressed row storage, CSR), діагональний, блочний стиснутий ряд- ковий (block compressed row storage, BCSR) та гібридні схеми. Слід зауважити, що наразі існують спеціальні бібліотеки розроблені, зок- рема, такими компаніями як NVIDIA та IBM, у яких реалізовані алго- ритми для GPU множення матриці на вектор. У випадку розглядуваної задачі на вибір підходів при розробці GPU-алгоритмів суттєво впливають два фактори:  нелінійність задачі, яка ускладнює обчислення та збільшує мож- ливість повторного використання даних;  великий коефіцієнт наповненості матриць СЛАР. Перший фактор, за умови того, що всі скінчені елементи мають однакову кількість вершин, зумовив використання схеми формування СЛАР у якій кожен блок потоків оброблює один скінчений елемент, при чому кожен потік змінює елементи СЛАР, пов’язані лише з однією вершиною. При цьому виконується умова незалежності обчислень й з’являється можливість сумісної роботи потоків блоку через локальну пам’ять з даними, пов’язаними з конкретним скінченим елементом. Другий фактор зумовив вибір BCSR формату збереження розрі- дженої матриці, ефективність використання якого зростає при збільшен- ні заповненості матриці. Оптимальний розмір блоку на основі даних обчислювальних експериментів був вибраний таким, що дорівнює 16. У випадку розглядуваної задачі, використання GPU у якості со- процесора без суттєвих модифікацій комбінується з алгоритмами для кластерних систем, що дозволяє використовувати для розв’язання цих задач GPU-кластери. Алгоритми були реалізовані з використанням технології OpenCL й тестувались на кластері СКІТ-3GPU Інституту кібернетики ім. В.М. Глушкова на задачі з 29791-елементною сіткою, матрицею СЛАР розмірністю 119164х 119164 з 8016008 ненульових елементів. Отри- мані дані щодо швидкодії алгоритмів подані у табл. 1. Серія: Фізико-математичні науки. Випуск 5 31 Таблиця 1 Час роботи алгоритмів, мс Загальний час Час формування СЛАР Час розв’язання СЛАР 1 CPU 4220 3560 660 3 CPU 2260 1480 780 1 GPU 1260 1020 240 3 GPU 1090 870 220 Як видно з отриманих даних, використання GPU дозволяє у 2—3 рази пришвидшити розрахунки в додачу до пришвидшення, що дося- гається використанням кластерних систем. Чисельні експерименти. Стосовно алгоритмів для кластерних систем була проведена серія чисельних експериментів у яких вимі- рювався час роботи алгоритмів в цілому та їх частин в залежності від розмірності задачі, кількості та конфігурації задіяних ресурсів. У якості тестової розглядалась тривимірна задача моделювання процесу консолідації ґрунтового масиву, розміщеного на проникній основі. Значення параметрів задачі (1), (2) брались наступними:  граничні та початкові умови: 10 11 0 1 1350 / , 240 / , 10 , 25 , 5 ;C г л C г л T C T C H м      характеристики ґрунтового масиву: 21 , 0.655, 0.001 / , 0.03232 / ;vl м k м доба c м добу     коефіцієнти дифузії та осмосу: 2 2 5 5 1 2 1 5 5 5 2 2 0.02 / , 0.04 / , 2*10 / * , 3*10 / * , 10 / * ; D м добу D м добу v м кг добу v м кг добу м град добу         (17)  термічні коефіцієнти: 6 32*10 / * * ,TC дж кг м град 30.8*10 / * ,C дж кг град  31100 / ,кг м  69120 / * * ,дж м град добу  5 1 20.5*10 , 0.078 /T T p K D м добу pC      . Дані щодо швидкодії для задачі з сіткою розмірністю 77310 вуз- лів (розмірність матриці — 309240х309240) наведені у табл.2, а для задачі з сіткою розмірністю 220210 вузлів (розмірність матриці — 880488х880488) — у табл. 3. Розв’язок задачі на прямій x=z=0 зобра- жений на рис.1а, аналогічний розв’язок задачі, що не враховує осмо- тичні явища та терморозширення, зображений на рис. 1 б. Математичне та комп’ютерне моделювання 32 Таблиця 2 Час обчислення одного кроку для задачі з сіткою розмірністю 77310 вузлів, мс Кіль- кість потоків Кіль- кість процесів Кіль- кість задіяних вузлів Безпосереднє розв’язання СЛАР Декомпозиційний алгоритм Загаль- ний час Час обчи- слення значень елементів СЛАР Час розв’язан ня СЛАР Загаль- ний час Час обчи- слення значень елементів СЛАР Час розв’язан ня СЛАР 1 1 1 30420 18020 12400 24610 18300 6310 8 2 2 8770 5110 3660 9040 5810 3230 28 7 7 4380 2220 2160 3400 1630 1770 40 10 10 3960 1640 2320 3460 1530 1930 8 8 2 13150 6070 7080 6510 3520 2990 32 32 8 4270 1980 2290 3280 1240 2040 40 40 10 3940 1780 2160 3370 1060 2310 Таблиця 3. Час обчислення одного кроку для задачі з сіткою розмірністю 220210 вузлів, мс Кіль- кість потоків Кіль- кість процесів Кіль- кість задіяних вузлів Безпосереднє розв’язання СЛАР Декомпозиційний алгоритм Загаль- ний час Час обчи- слення значень елементів СЛАР Час розв’язан ня СЛАР Загаль- ний час Час обчи- слення значень елементів СЛАР Час розв’язан ня СЛАР 1 1 1 74500 39050 35450 79480 54590 24890 8 2 2 24010 10980 13030 21380 11630 9750 28 7 7 13750 5880 7870 8470 3940 4530 40 10 10 12610 5070 7540 8370 3210 5160 8 8 2 27460 8440 19020 18250 9170 9080 12 12 3 19250 6890 12360 17140 7620 9520 Розв’язувалась також задача моделювання процесу фільтрацій- ної консолідації ґрунтового масиву розміром 40x40 м, за наявності двох ставків, заповнених розчинами різних солей, й часткового не- проникного бар’єру між ними (рис. 2). Моделювання процесу прово- дилось на період у 12 місяців зі значеннями параметрів (17). Ізопове- рхні отриманої функції розподілу температури зображені на рис. 3. Серія: Фізико-математичні науки. Випуск 5 33 Ізолінії функції надлишкових напорів на розрізі z=12 м зображені на рис. 4 а., а сумарної функції засоленості на рис. 4 б. а) б) Рис. 1. Розв’язок задачі на прямій x=z=0 Рис. 2. Область моделювання Рис. 3. Ізоповерхні функції розподілу температури а) надлишкових напорів б) сумарної засоленості Рис. 4. Ізолінії функцій В цілому, експерименти підтвердили ефективність застосування декомпозиційного алгоритму розв’язання СЛАР. Так, для задачі ме- ншої розмірності пришвидшення при цьому склало ~16%, а для зада- чі більшої розмірності — ~45%. Математичне та комп’ютерне моделювання 34 Пришвидшення ж від використання багатопоточності спостері- галось лише на невеликій кількості задіяних вузлів, зокрема на двох чотирипроцесорних вузлах пришвидшення склало ~12% для задачі високої розмірності й ~33% для задачі низької розмірності. При заді- яні трьох й більше вузлів пришвидшення від використання багатопо- точності не спостерігалось. Падіння прискорення при зростанні розмірності тут може бути пояснено зменшенням при цьому відношення часу, що витрачається на обміни, до часу, що витрачається на обчислення. Це призводить до ефекту, що спостерігався, так як використання багатопоточності ра- зом з розпаралеленням для систем з розподіленою пам’яттю для розв’язання розглядуваної задачі потенційно зменшує саме обсяг об- мінів при незмінному обсязі обчислень. По тій самій причині приш- видшення при використанні декомпозиційного алгоритму зростає при збільшенні розмірності, оскільки в цій ситуації зменшується як час, що витрачається на обміни, так і обсяг обчислень. Висновки. Для задачі моделювання процесу фільтраційної кон- солідації ґрунту під дією бікомпонентного розчину були розглянуті обчислювальні аспекти розв’язання у випадку тривимірної постанов- ки, зокрема пов’язані з розпаралеленням. На предмет досягнення найвищої швидкодії досліджувались чотири паралельні алгоритми для систем з розподіленою пам’яттю:  з безпосереднім розв’язанням СЛАР;  з використанням декомпозиційного алгоритму розв’язання СЛАР;  з безпосереднім розв’язанням СЛАР та використанням багатопо- точності;  з використанням декомпозиційного алгоритму розв’язання СЛАР та багатопоточності. При цьому в усіх варіантах для розв’язання розріджених СЛАР використовувався алгоритм BiCGStab, та застосовувалась схема оп- тимізації завантаження процесорів. Як теоретичні оцінки, так і дані обчислювальних експериментів показали, що  декомпозиційний алгоритм розв’язання СЛАР є швидшим за без- посереднє розв’язання СЛАР при невеликих значеннях коефіцієн- ту термічного розширення;  використання багатопоточності дозволяє суттєво (на ~33%) приш- видшити розрахунки лише для задач невеликої розмірності на не- великій (до двох чотирипроцесорних) кількості задіяних вузлів. Окрім цього було досліджена можливість використання GPU у яко- сті сопроцесора при розв’язанні розглядуваних задач. Були розроблені відповідні алгоритми та проведені обчислювальні експерименти, які по- казали 2—3-кратне прискорення в порівнянні з CPU-алгоритмами. Серія: Фізико-математичні науки. Випуск 5 35 Список використаних джерел: 1. Бомба А. Я. Нелінійні математичні моделі процесів геогідродинаміки / А. Я. Бомба, В. М. Булавацький, В. В. Скопецький. — К. : Наук. думка, 2007. — 292 с. 2. Власюк А. П. Математичне моделювання консолідації ґрунтів в процесі фільтрації сольових розчинів / А. П. Власюк, П. М. Мартинюк. — Рівне : Вид-во УДУВГП, 2004. — 211 с. 3. Власюк А. П. Математичне моделювання консолідації ґрунтів при фільт- рації сольових розчинів в неізотермічних умовах / А. П. Власюк, П. М. Мартинюк. — Рівне : Вид-во НУВГП, 2008. — 416 с. 4. Булавацький В. М. Математическое моделирование динамики консоли- дационного процесса насыщенной бинарным солевым раствором порис- той среды / В. М. Булавацький // Компьютерная математика. — 2008. — № 2. — С. 3—12. 5. Булавацький В. М. Математическое моделирование динамики одного неизотермического консолидационного процесса / В. М. Булавацький, В. В. Скопецький // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки : зб. наук. пр. — Кам’янець-Подільський : Ка- м'янець-Поділ. нац. ун-т, 2010. — Вип. 3. — С. 28—36. 6. Булавацький В. М. Об одной неизотермической консолидационной мате- матической модели геоинформатики / В. М. Булавацький, В. В. Скопець- кий // Пробл. упр. и информатики. — 2010. — № 6. — С. 35—45. 7. Самарский А. А. Вычислительная теплопередача / А. А. Самарский, П. Н. Вабищевич. — М. : Едиториал УРСС, 2003. — 784 с. 8. Saad Y. Iterative methods for sparse linear systems, 2 edition / Y. Saad. — Society for Industrial and Applied Mathematics, 2003. — 528 p. 9. Cuthill E. Reducing the bandwidth of sparse symmetric matrices / E. Cuthill, J. McKee // In Proc. 24th Nat. Conf. ACM. — 1969. — P. 157—172. 10. Cecka C. Assembly of finite element methods on graphics processors / C. Cecka, A. J. Lew, E. Darve // International Journal for Numerical Methods in Engineering. — 2011. — Р. 640—669. 11. Abhijeet Gaikwad, Ioane Muni Toke GPU based Sparse Grid Technique for Solving Multidimensional Options Pricing PDEs // Supercomputing'09, Proceed- ings of the 2nd Workshop on High-Performance Computational Finance — SC09-WHPCF09, ACM Press (2009) Problem of modeling filtration consolidation processes in soils under the influence of bi-component solution has been considered in the paper. One-dimensional mathematical model of such processes has been extended to three-dimensional case and a set of parallel algorithms for solving prob- lems about it have been proposed, in particular, multithreaded algorithms, algorithms for cluster systems and graphical processors (GPU). Key words: filtration consolidation, bi-component solutions, mathe- matical modeling, parallel algorithms. Отримано: 17.05.2011 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /All /Binding /Left /CalGrayProfile (Gray Gamma 2.2) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (Coated FOGRA27 \050ISO 12647-2:2004\051) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.3 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.1000 /ColorConversionStrategy /sRGB /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo false /PreserveFlatness false /PreserveHalftoneInfo false /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Remove /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true /Arial-Black /Arial-BlackItalic /Arial-BoldItalicMT /Arial-BoldMT /Arial-ItalicMT /ArialMT /ArialNarrow /ArialNarrow-Bold /ArialNarrow-BoldItalic /ArialNarrow-Italic /ArialUnicodeMS /CenturyGothic /CenturyGothic-Bold /CenturyGothic-BoldItalic /CenturyGothic-Italic /CourierNewPS-BoldItalicMT /CourierNewPS-BoldMT /CourierNewPS-ItalicMT /CourierNewPSMT /Georgia /Georgia-Bold /Georgia-BoldItalic /Georgia-Italic /Impact /LucidaConsole /Tahoma /Tahoma-Bold /TimesNewRomanMT-ExtraBold /TimesNewRomanPS-BoldItalicMT /TimesNewRomanPS-BoldMT /TimesNewRomanPS-ItalicMT /TimesNewRomanPSMT /Trebuchet-BoldItalic /TrebuchetMS /TrebuchetMS-Bold /TrebuchetMS-Italic /Verdana /Verdana-Bold /Verdana-BoldItalic /Verdana-Italic ] /AntiAliasColorImages false /CropColorImages false /ColorImageMinResolution 150 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 150 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /ColorImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /AntiAliasGrayImages false /CropGrayImages false /GrayImageMinResolution 150 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 150 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /GrayImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >> /AntiAliasMonoImages false /CropMonoImages false /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects true /CheckCompliance [ /PDFX1a:2001 ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064506390020064506420627064A064A0633002006390631063600200648063706280627063906290020062706440648062B0627062606420020062706440645062A062F062706480644062900200641064A00200645062C062706440627062A002006270644062306390645062706440020062706440645062E062A064406410629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043f043e04340445043e0434044f044904380020043704300020043d043004340435043604340435043d0020043f044004350433043b04350434002004380020043f04350447043004420020043d04300020043104380437043d0435044100200434043e043a0443043c0435043d04420438002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e55464e1a65876863768467e5770b548c62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc666e901a554652d965874ef6768467e5770b548c52175370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002000760068006f0064006e00fd00630068002000700072006f002000730070006f006c00650068006c0069007600e90020007a006f006200720061007a006f007600e1006e00ed002000610020007400690073006b0020006f006200630068006f0064006e00ed0063006800200064006f006b0075006d0065006e0074016f002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000650067006e006500720020007300690067002000740069006c00200064006500740061006c006a006500720065007400200073006b00e60072006d007600690073006e0069006e00670020006f00670020007500640073006b007200690076006e0069006e006700200061006600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200075006d002000650069006e00650020007a0075007600650072006c00e40073007300690067006500200041006e007a006500690067006500200075006e00640020004100750073006700610062006500200076006f006e00200047006500730063006800e40066007400730064006f006b0075006d0065006e00740065006e0020007a0075002000650072007a00690065006c0065006e002e00200044006900650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000520065006100640065007200200035002e003000200075006e00640020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ENU (Use these settings to create Adobe PDF documents suitable for reliable viewing and printing of business documents. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f00620065002000500044004600200061006400650063007500610064006f007300200070006100720061002000760069007300750061006c0069007a00610063006900f3006e0020006500200069006d0070007200650073006900f3006e00200064006500200063006f006e006600690061006e007a006100200064006500200064006f00630075006d0065006e0074006f007300200063006f006d00650072006300690061006c00650073002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e400740074006500690064002000e4007200690064006f006b0075006d0065006e00740069006400650020007500730061006c006400750073007600e400e4007200730065006b0073002000760061006100740061006d006900730065006b00730020006a00610020007000720069006e00740069006d006900730065006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f006200650020005000440046002000700072006f00660065007300730069006f006e006e0065006c007300200066006900610062006c0065007300200070006f007500720020006c0061002000760069007300750061006c00690073006100740069006f006e0020006500740020006c00270069006d007000720065007300730069006f006e002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003b103be03b903cc03c003b903c303c403b7002003c003c103bf03b203bf03bb03ae002003ba03b103b9002003b503ba03c403cd03c003c903c303b7002003b503c003b903c703b503b903c103b703bc03b103c403b903ba03ce03bd002003b503b303b303c103ac03c603c903bd002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05d405e905ea05de05e905d5002005d105d405d205d305e805d505ea002005d005dc05d4002005db05d305d9002005dc05d905e605d505e8002005de05e105de05db05d9002000410064006f006200650020005000440046002005e205d105d505e8002005d405e605d205d4002005d505d405d305e405e105d4002005d005de05d905e005d4002005e905dc002005de05e105de05db05d905dd002005e205e105e705d905d905dd002e002005de05e105de05db05d90020005000440046002005e905e005d505e605e805d5002005e005d905ea05e005d905dd002005dc05e405ea05d905d705d4002005d105d005de05e605e205d505ea0020004100630072006f006200610074002005d5002d00410064006f00620065002000520065006100640065007200200035002e0030002005d505d205e805e105d005d505ea002005de05ea05e705d305de05d505ea002005d905d505ea05e8002e> /HRV (Za stvaranje Adobe PDF dokumenata pogodnih za pouzdani prikaz i ispis poslovnih dokumenata koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF00410020006800690076006100740061006c006f007300200064006f006b0075006d0065006e00740075006d006f006b0020006d00650067006200ed007a00680061007400f30020006d0065006700740065006b0069006e007400e9007300e900720065002000e900730020006e0079006f006d00740061007400e1007300e10072006100200073007a00e1006e0074002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c00200068006f007a006800610074006a00610020006c00e9007400720065002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA (Utilizzare queste impostazioni per creare documenti Adobe PDF adatti per visualizzare e stampare documenti aziendali in modo affidabile. I documenti PDF creati possono essere aperti con Acrobat e Adobe Reader 5.0 e versioni successive.) /JPN <FEFF30d330b830cd30b9658766f8306e8868793a304a3088307353705237306b90693057305f002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a3067306f30d530a930f330c8306e57cb30818fbc307f3092884c3044307e30593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020be44c988b2c8c2a40020bb38c11cb97c0020c548c815c801c73cb85c0020bcf4ace00020c778c1c4d558b2940020b3700020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b0075007200690065002000740069006e006b006100200070006100740069006b0069006d006100690020007000650072017e0069016b007201170074006900200069007200200073007000610075007300640069006e0074006900200076006500720073006c006f00200064006f006b0075006d0065006e007400750073002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020007000690065006d01130072006f00740069002000640072006f016100610069002000620069007a006e00650073006100200064006f006b0075006d0065006e007400750020006100700073006b006100740065006900200075006e0020006400720075006b010101610061006e00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken waarmee zakelijke documenten betrouwbaar kunnen worden weergegeven en afgedrukt. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d002000650072002000650067006e0065007400200066006f00720020007000e5006c006900740065006c006900670020007600690073006e0069006e00670020006f00670020007500740073006b007200690066007400200061007600200066006f0072007200650074006e0069006e006700730064006f006b0075006d0065006e007400650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f0020006e00690065007a00610077006f0064006e00650067006f002000770079015b0077006900650074006c0061006e00690061002000690020006400720075006b006f00770061006e0069006100200064006f006b0075006d0065006e007400f300770020006600690072006d006f0077007900630068002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f00620065002000500044004600200061006400650071007500610064006f00730020007000610072006100200061002000760069007300750061006c0069007a006100e700e3006f002000650020006100200069006d0070007200650073007300e3006f00200063006f006e0066006900e1007600650069007300200064006500200064006f00630075006d0065006e0074006f007300200063006f006d0065007200630069006100690073002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e007400720075002000760069007a00750061006c0069007a00610072006500610020015f006900200074006900700103007200690072006500610020006c0061002000630061006c006900740061007400650020007300750070006500720069006f0061007201030020006100200064006f00630075006d0065006e00740065006c006f007200200064006500200061006600610063006500720069002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002000760068006f0064006e00fd006300680020006e0061002000730070006f013e00610068006c0069007600e90020007a006f006200720061007a006f00760061006e006900650020006100200074006c0061010d0020006f006200630068006f0064006e00fd0063006800200064006f006b0075006d0065006e0074006f0076002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020007000720069006d00650072006e006900680020007a00610020007a0061006e00650073006c006a00690076006f0020006f0067006c00650064006f00760061006e006a006500200069006e0020007400690073006b0061006e006a006500200070006f0073006c006f0076006e0069006800200064006f006b0075006d0065006e0074006f0076002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002c0020006a006f0074006b006100200073006f0070006900760061007400200079007200690074007900730061007300690061006b00690072006a006f006a0065006e0020006c0075006f00740065007400740061007600610061006e0020006e00e400790074007400e4006d0069007300650065006e0020006a0061002000740075006c006f007300740061006d0069007300650065006e002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d00200070006100730073006100720020006600f60072002000740069006c006c006600f60072006c00690074006c006900670020007600690073006e0069006e00670020006f006300680020007500740073006b007200690066007400650072002000610076002000610066006600e4007200730064006f006b0075006d0065006e0074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005400690063006100720069002000620065006c00670065006c006500720069006e0020006700fc00760065006e0069006c0069007200200062006900720020015f0065006b0069006c006400650020006700f6007200fc006e007400fc006c0065006e006d006500730069002000760065002000790061007a0064013100720131006c006d006100730131006e006100200075007900670075006e002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043d0430043404560439043d043e0433043e0020043f0435044004350433043b044f043404430020044204300020043404400443043a0443002004340456043b043e04320438044500200434043e043a0443043c0435043d044204560432002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043f043e04340445043e0434044f04490438044500200434043b044f0020043d0430043404350436043d043e0433043e0020043f0440043e0441043c043e044204400430002004380020043f04350447043004420438002004340435043b043e0432044b044500200434043e043a0443043c0435043d0442043e0432002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AllowImageBreaks true /AllowTableBreaks true /ExpandPage false /HonorBaseURL true /HonorRolloverEffect false /IgnoreHTMLPageBreaks false /IncludeHeaderFooter false /MarginOffset [ 0 0 0 0 ] /MetadataAuthor () /MetadataKeywords () /MetadataSubject () /MetadataTitle () /MetricPageSize [ 0 0 ] /MetricUnit /inch /MobileCompatible 0 /Namespace [ (Adobe) (GoLive) (8.0) ] /OpenZoomToHTMLFontSize false /PageOrientation /Portrait /RemoveBackground false /ShrinkContent true /TreatColorsAs /MainMonitorColors /UseEmbeddedProfiles false /UseHTMLTitleAsMetadata true >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /BleedOffset [ 0 0 0 0 ] /ConvertColors /ConvertToRGB /DestinationProfileName (sRGB IEC61966-2.1) /DestinationProfileSelector /UseName /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements true /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles true /MarksOffset 6 /MarksWeight 0.250000 /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PageMarksFile /RomanDefault /PreserveEditing true /UntaggedCMYKHandling /UseDocumentProfile /UntaggedRGBHandling /LeaveUntagged /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [600 600] /PageSize [419.528 595.276] >> setpagedevice

Ähnliche Einträge