Итеративті трафарет ілмектері - Iterative Stencil Loops

7 нүктелі 3D пішіні фон Нейман трафарет.

Итеративті трафарет ілмектері (ISL) - бұл сандық деректерді өңдеу шешімінің класы[1]қандай жаңарту жиым элементтері трафарет деп аталатын кейбір бекітілген үлгі бойынша.[2] Олар жиі кездеседі компьютерлік модельдеу, мысалы. үшін сұйықтықты есептеу динамикасы ғылыми және инженерлік қосымшалардың контекстінде. Басқа маңызды мысалдарға шешімдер жатады дербес дифференциалдық теңдеулер,[1] The Якоби ядро, Гаусс-Зайдель әдісі,[2] кескінді өңдеу[1] және ұялы автоматтар.[3] Массивтердің тұрақты құрылымы трафарет техникасын, сияқты басқа модельдеу әдістерінен бөлек қояды Соңғы элемент әдісі. Көпшілігі соңғы айырмашылық кодтары тұрақты торларда жұмыс жасайтын ISL ретінде тұжырымдалуы мүмкін.

Анықтама

ISL берілген массив арқылы сыпыру тізбегін жүзеге асырады (уақыт ағындары деп аталады).[2] Әдетте бұл 2 немесе 3 өлшемді тұрақты тор.[3] Жиым элементтері көбінесе ұяшықтар деп аталады. Әр уақыт кезеңінде барлық массив элементтері жаңартылады.[2] Массивтің көршілес элементтерін белгіленген үлгіде (трафарет) қолдана отырып, әр ұяшықтың жаңа мәні есептеледі. Көп жағдайда шекаралық мәндер өзгеріссіз қалады, бірақ кейбір жағдайларда (мысалы, LBM кодтары ) оларды есептеу кезінде де түзету қажет. Трафарет әр элемент үшін бірдей болғандықтан, мәліметтерге қол жеткізу үлгісі қайталанады.[4]

Ресми түрде біз ISL-ді a ретінде анықтай аламыз 5 кортеж мынадай мағынада:[3]

  • индекс жиынтығы. Ол массивтің топологиясын анықтайды.
  • бұл күйлердің (міндетті түрде ақырғы емес) жиынтығы, олардың әрқайсысы кез-келген уақыт кезеңінде қабылдауы мүмкін.
  • жүйенің 0 уақыттағы бастапқы күйін анықтайды.
  • трафареттің өзі болып табылады және маңайдың нақты формасын сипаттайды. Сонда трафареттегі элементтер.
  • - бұл көршісіне байланысты жасушаның жаңа күйін анықтау үшін қолданылатын өтпелі функция.

Бастап Мен Бұл к-өлшемді бүтін аралық, массив әрқашан ақырлы тұрақты тордың топологиясына ие болады. Массив модельдеу кеңістігі деп аталады және жеке ұяшықтар олардың индексі бойынша анықталады . Трафарет - бұл тапсырыс берілген жиынтығы салыстырмалы координаттар. Енді біз әр ұяшық үшін ала аламыз көршілерінің кортежі

Олардың күйлері кортежді картаға түсіру арқылы беріледі күйлердің сәйкес кортежіне , қайда келесідей анықталады:

Бізге жүйенің күйін келесі уақыт кезеңдері үшін анықтау қажет бірге :

Ескертіп қой бойынша анықталады және жай ғана емес өйткені шекара шарттарын да орнату керек. Кейде Тороидтық топологияны жүзеге асыру үшін модельдеу кеңістігінің өлшемін векторлық қосу модулімен анықтауға болады:

Бұл іске асыру үшін пайдалы болуы мүмкін мерзімді шекаралық шарттар, бұл белгілі бір физикалық модельдерді жеңілдетеді.

Мысалы: 2D Якобидің қайталануы

2D жиымындағы таңдалған ұяшықтың мәліметтерге тәуелділігі.

Ресми анықтаманы көрсету үшін біз екі өлшемділікті қарастырамыз Якоби қайталануын анықтауға болады. Жаңарту функциясы ұяшықтың төрт көршісінің арифметикалық ортасын есептейді. Бұл жағдайда біз 0-дің бастапқы шешімімен жолға шықтық. Сол және оң шекара 1-ге, ал жоғарғы және төменгі шекаралар 0-ге қойылды. Қайталаудың жеткілікті санынан кейін жүйе седла-пішінге жақындайды.

S_0
S_200
S_400
S_600
S_800
S_1000
2D Якобидің қайталануы а Массив

Трафареттер

Жаңартулар кезінде қолданылатын көршілес пішін қосымшаның өзіне байланысты. Ең көп таралған трафареттер - 2D немесе 3D нұсқалары фон Нейман маңы және Мур маңы. Жоғарыдағы мысалда 2D фон Нейман трафареті қолданылады, ал LBM кодтары оның 3D нұсқасын қолданады. Конвейдің өмір ойыны 2D Мур маңын пайдаланады. Айтуынша, басқа трафареттер, мысалы, сейсмикалық толқындардың таралуына арналған 25 баллдық трафарет[5] табуға болады.

9-нүктелік трафарет
9-нүктелік 2D трафареті
5-нүктелік трафарет
5 нүктелік 2D трафареті
6-нүктелік трафарет
7-нүктелік трафарет
25 нүктелік трафарет
25-нүктелік трафарет
Әр түрлі ғылыми қосымшаларда қолданылатын трафареттерді таңдау.

Іске асыру мәселелері

Көптеген модельдеу кодтары ISL ретінде табиғи түрде тұжырымдалуы мүмкін. Есептеу уақыты мен жадыны тұтыну жиым элементтерінің санына байланысты біртіндеп өсетіндіктен, зерттеу үшін ISL параллельді енгізу маңызды болып табылады.[6] Бұл өте қиын, өйткені есептеулер тығыз байланысты (ұяшықтардың көршілес ұяшықтарға байланысты жаңартуларына байланысты) және ISL-дің көпшілігі жадпен байланысты (яғни, жадқа қол жетімділіктің есептеулерге қатынасы жоғары).[7] Іс жүзінде барлық параллель архитектуралар ISL-ді тиімді орындау үшін зерттелген;[8] Қазір GPGPU ең тиімді екендігі дәлелденді.[9]

Кітапханалар

ISL-дің маңыздылығына байланысты компьютерлік модельдеу және олардың жоғары есептеу талаптары, ғалымдарға трафарет негізінде есептеулер жүргізуге қолдау көрсету үшін бірнеше рет пайдаланылатын кітапханалар құруға бағытталған бірқатар күштер бар. Кітапханалар көбінесе параллелизациямен айналысады, сонымен қатар IO сияқты басқа да мәселелерді шешуі мүмкін. басқару және бақылау пункті. Олар API бойынша жіктелуі мүмкін.

Патч негізіндегі кітапханалар

Бұл дәстүрлі дизайн. Кітапхана жиынтықты басқарады n- қолданушы бағдарламасы жаңартуды жүзеге асыруға рұқсаты бар өлшемді скалярлық массивтер. Кітапхана шекараларды синхрондауды басқарады (елес аймақ немесе гало деп аталады). Бұл интерфейстің артықшылығы - қолданушы бағдарламасы массивтердің үстінен цикл жасай алады, бұл бұрынғы кодты біріктіруді жеңілдетеді [10]. Кемшілігі - кітапхана кэшті бұғаттаумен жұмыс істей алмайды (өйткені оны циклдар ішінде жасау керек)[11]) немесе үдеткіштерге арналған API-қоңырауларды орау (мысалы, CUDA немесе OpenCL арқылы). Іске асыруға кіреді Кактус, физика проблемаларын шешу ортасы және waLBerla.

Ұяшыққа негізделген кітапханалар

Бұл кітапханалар интерфейсті жалғыз имитациялық ұяшықтарды жаңартуға ауыстырады: тек ағымдағы ұяшық және оның көршілері көрінеді, мысалы. getter / setter әдістері арқылы. Бұл тәсілдің артықшылығы - кітапхана қай ұяшықтардың қандай ретпен жаңартылатындығын қатаң басқара алады, бұл тек кэшті бұғаттауды жүзеге асыруға ғана емес пайдалы[9] сонымен қатар көп ядролы және графикалық процессорларда бірдей кодты іске қосу керек.[12] Бұл тәсіл пайдаланушыдан бастапқы кодты кітапханамен бірге компиляциялауды талап етеді. Әйтпесе, кез-келген ұяшықтың жаңартуы үшін функционалды қоңырау қажет болуы мүмкін, бұл өнімділікті айтарлықтай нашарлатады. Сияқты техникамен ғана мүмкін болады сынып шаблондары немесе метапрограммалау, бұл сонымен қатар бұл дизайнның жаңа кітапханаларда болуының себебі. Мысалдар Физ және LibGeoDecomp.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б c Рот, Джералд және басқалар. (1997) SC'97 еңбектері: жоғары өнімді желі және есептеу. Үлкен өнімді фортрандағы трафареттерді құрастыру.
  2. ^ а б c г. Слоот, Питер М.А. және т.б. (28 мамыр 2002) Есептеу ғылымы - ICCS 2002: Халықаралық конференция, Амстердам, Нидерланды, 2002 ж. 21-24 сәуір. Іс жүргізу, I бөлім. 843-бет. Шығарушы: Springer. ISBN  3-540-43591-3.
  3. ^ а б c Фей, Диетмар және басқалар. (2010) Торды есептеу: Eine Basistechnologie für Computational Science. Бет 439. Шығарушы: Springer. ISBN  3-540-79746-7
  4. ^ Янг, Лоренс Т .; Гуо, Мини. (2005 жылғы 12 тамыз) Жоғары тиімділікті есептеу: парадигма және инфрақұрылым. 221-бет. Баспагері: Уилли-Интерсисианс. ISBN  0-471-65471-X
  5. ^ Микикевич, Паулюс және басқалар. (2009) CUDA көмегімен графикалық процессорлардағы 3D ақырлы айырмашылықты есептеу Графикалық өңдеу қондырғыларындағы жалпы мақсаттағы өңдеу бойынша 2-ші семинардың материалдары ISBN  978-1-60558-517-8
  6. ^ Датта, Каушик (2009) Кэшке негізделген көп ядролы платформаларға арналған трафарет кодтарын автоматты түрде баптау Мұрағатталды 2012-10-08 Wayback Machine, Ph.D. Диссертация
  7. ^ Wellein, G және басқалар. (2009) Көпфункционалды толқындық параллельдеу арқылы трафаретті есептеу үшін тиімді уақытша блоктау, Компьютерлік бағдарламалық қамтамасыздандыру мен бағдарламалық қамтамасыздандырудың 33-ші Халықаралық IEEE конференциясы, COMPSAC 2009 ж
  8. ^ Датта, Каушик және басқалар. (2008) Трафаретті есептеуді оңтайландыру және заманауи мультикорлық архитектурада автоматты түрде баптау, SC '08 Суперкомпьютер бойынша 2008 ACM / IEEE конференциясының материалдары
  9. ^ а б Шафер, Андреас және Фей, Диетмар (2011) GPGPU үшін жоғары өнімділікті трафарет кодының алгоритмдері, Халықаралық есептеуіш конференция конференциясының материалдары, ICCS 2011 ж
  10. ^ С.Донат, Дж. Гётц, C. Фейхтингер, К. Иглбергер және У. Рюде (2010) waLBerla: Мыңдаған процессорлары бар итанға негізделген жүйелерді оңтайландыру, Ғылым мен техникадағы жоғары өнімді есептеу, Гарчинг / Мюнхен 2009 ж
  11. ^ Нгуен, Энтони және басқалар. (2010) Қазіргі заманғы процессорлар мен графикалық процессорлардағы трафаретті есептеу үшін блоктауды оңтайландыру, SC '10 Жоғары өнімділікті есептеу, желілік байланыс, сақтау және талдау бойынша халықаралық ACM / IEEE 2010 конференциясының материалдары.
  12. ^ Наоя Маруяма, Тацуо Номура, Кенто Сато және Сатоси Мацуока (2011) Физис: Үлкен масштабты GPU-жеделдетілген суперкомпьютерлерде трафаретті есептеу үшін айқын параллельді бағдарламалау моделі, SC '11 Жоғары өнімді есептеу, желілік байланыс, сақтау және талдау бойынша 2011 ACM / IEEE Халықаралық конференциясының материалдары.

Сыртқы сілтемелер