Uchenye iz neskol’kikh institutov, v tom chisle Instituta teoreticheskoi fiziki imeni L.D. Landau, razrabotali parallel’nyi vychislitel’nyi algoritm, kotoryi pozvolyaet s khoroshei tochnost’yu modelirovat’ povedenie veshchestva v ekstremal’nykh usloviyakh: pri vzryvakh, moshchnom lazernom vozdeistvii, padenii meteoritov i dazhe pri stolknovenii zvezd. Novyi algoritm pozvolyaet optimal’no raspredelyat’ nagruzku mezhdu vychislitel’nymi uzlami superkomp’yutera, chto mnogokratno sokrashchaet vremya vychislenii. Stat’ya opublikovana v zhurnale Computer Physics Communications.
Protsessy, dlya modelirovaniya kotorykh byl razrabotan etot algoritm, otlichayutsya vysokoi slozhnost’yu i postoyannym vzaimozavisimym izmeneniem struktury vnutrennikh elementov. Pomimo vzryvov i razrusheniya khrupkikh materialov pri padenii ili udare, k takim protsessam otnosyatsya, naprimer, protekanie zhidkosti cherez granuly dioksida urana v aktivnoi zone yadernogo reaktora ili prokhozhdenie tsunami skvoz’ pribrezhnyi gorod. Chtoby ponyat’, kak budut razvivat’sya sobytiya v etikh situatsiyakh, neobkhodimo ispol’zovat’ superkomp’yutery. No esli zagruzit’ takoi zadachei superkomp’yuter, ne raspredelyaya osobym obrazom vychisleniya po ego vychislitel’nym uzlam, dazhe samoi vysokoi moshchnosti budet nedostatochno, chtoby zakonchit’ vychisleniya za razumnoe vremya. «Esli nagruzka raspredelyaetsya neravnomerno, i na kakie-to uzly prikhoditsya malo vychislitel’noi raboty, oni zakanchivayut schet bystree i nachinayut zhdat’, poka poschitayut bolee zagruzhennye uzly. V itoge obshchee vremya rascheta uvelichivaetsya iz-za etogo ozhidaniya», – ob’yasnyaet problemy neoptimal’noi parallelizatsii pervyi avtor raboty, nauchnyi sotrudnik FGUP «Vserossiiskii nauchno-issledovatel’skii institut avtomatiki imeni N.L. Dukhova» Mariya Egorova.
Chtoby provodit’ raschety maksimal’no effektivno, uchenye i inzhenery ispol’zuyut tak nazyvaemye parallel’nye algoritmy, kotorye raspredelyayut neobkhodimye vychisleniya mezhdu protsessorami, ustanovlennymi v vychislitel’nykh uzlakh. No odin i tot zhe protsess mozhno raspredelit’ po vychislitel’nym uzlam po-raznomu v zavisimosti ot togo, kakim sposobom uchenye predstavlyayut sredu, v kotoroi proiskhodyat opisyvaemye protsessy. Samyi populyarnyi sposob – tak nazyvaemyi setochnyi metod, kogda sreda predstavlyaetsya kak nabor zhestko svyazannykh mezhdu soboi elementov-yacheek s yavno provedennymi granitsami mezhdu nimi. No kak raz etot metod plokho podkhodit dlya protsessov, razvivayushchikhsya pod deistviem ekstremal’nykh sil. «V takikh protsessakh sreda vse vremya deformiruetsya po vsemu ob’emu, granitsy ob’ektov sil’no iskazhayutsya, i togda elementy setki, esli oni zhestko privyazany k veshchestvu, iskazhayutsya tozhe. Eto narushaet tochnost’ rascheta, i setki prikhoditsya perestraivat’. Esli v nashikh zadachakh privyazat’ elementy setki ne k veshchestvu, a k prostranstvu, soderzhimoe yacheek okazyvaetsya smeshannym – naprimer, sostoyashchim iz vakuuma i materii – i prikhoditsya otslezhivat’, kak menyayutsya granitsy mezhdu komponentami soderzhimogo. Na eto ukhodit mnogo vychislitel’noi moshchnosti. My khoteli oboitis’ bez etikh zatrat», – rasskazyvaet Egorova.
Perekhlest volny cherez palubu korablya i zatoplenie goroda vodoi, smodelirovannye s ispol’zovaniem algoritma sglazhennykh chastits. Illyustratsii Ihmsen M. et al., 2013.
Dlya modelirovaniya podvizhnykh sred ispol’zuyutsya bessetochnye metody, v kotorykh net fiksirovannykh svyazei mezhdu elementami sredy. Eto, naprimer, metod molekulyarnoi dinamiki ili metod sglazhennykh chastits, kotorye khorosho prisposobleny dlya bystrykh peremeshchenii otdel’nykh elementov sredy. No dlya togo chtoby smodelirovat’ vzryv ili soudarenie dvukh ob’ektov – skazhem, pri padenii meteorita – prikhoditsya sovmeshchat’ setochnye i bessetochnye metody. Do udara ispol’zuetsya setochnyi metod, posle – bessetochnyi. «My razrabotali algoritm, kotoryi pozvolyaet proschityvat’ vse protsessy, ispol’zuya tol’ko metod sglazhennykh chastits. S chastitsami rabota bolee prozrachna i edinoobrazna, chem s setkami, tak kak ne nuzhno nichego perestraivat’, privlekat’ slozhnye mnogokomponentnye modeli v yacheike setki. No problema metoda sglazhennykh chastits zaklyuchaetsya v tom, chto on menee tochnyi, chem setochnye metody. Chtoby povysit’ tochnost’, nuzhno vvodit’ v raschet bol’she chastits. Nash algoritm pozvolyaet effektivno ispol’zovat’ stol’ko chastits, skol’ko neobkhodimo» – govorit Mariya Egorova.
Dlya togo chtoby razdelit’ sredu na otdel’nye uchastki, kazhdyi iz kotorykh budet obschityvat’sya na raznykh protsessorakh, algoritm ispol’zuet razbienie po diagramme Voronogo. Etim terminom nazyvayut osobyi sposob razdeleniya tela na neskol’ko oblastei. «Dopustim, my reshili razbit’ nekuyu chast’ prostranstva na 10 oblastei. Dlya sozdaniya razbieniya na nei nam snachala nuzhno vybrat’ 10 nesovpadayushchikh tochek. Togda odna yacheika razbieniya budet predstavlyat’ soboi oblast’ prostranstva, lyubaya tochka kotoroi blizhe k odnoi iz vybrannykh tochek, chem k lyuboi iz drugikh devyati vybrannykh», – ob’yasnyaet Mariya Egorova printsip postroeniya diagrammy Voronogo. Naglyadno uvidet’, kak rabotaet diagramma, mozhno tut. V sozdannom uchenymi algoritme kolichestvo tochek, po kotorym budet stroit’sya diagramma Voronogo, vybiraetsya ravnym kolichestvu protsessorov. Kazhdaya tochka privyazyvaetsya k konkretnomu protsessoru i okruzhayushchaya ee oblast’, to est’ sootvetstvuyushchaya yacheika razbieniya, rasschityvaetsya etim protsessorom. Peredvigaya tochki, uchenye mogut vybirat’, kakaya chast’ sredy budet obrabatyvat’sya na kazhdom protsessore, vovlechennom v raschet, i tem samym regulirovat’ vychislitel’nuyu nagruzku kazhdogo protsessora.
«Takoe dinamicheskoe razdelenie sredy mezhdu protsessorami pozvolyaet optimizirovat’ vychisleniya za schet togo, chto granichashchie drug s drugom oblasti diagrammy Voronogo mogut obmenivat’sya mezhdu soboi chastitsami, – govorit Egorova. – Blagodarya etomu nash algoritm pozvolyaet optimal’no nagruzhat’ vse protsessory: esli okazyvaetsya, chto kakoi-to iz nikh prostaivaet, on poluchaet ot svoego bolee zagruzhennogo soseda po diagramme chast’ ego veshchestva na raschet. Prichem my izmenyaem nagruzku na protsessory, orientiruyas’ imenno na vremya, kogda oni zanyaty vychisleniyami, a ne na obshchee vremya raboty protsessora. Eto bolee slozhnyi put’, no zato on obespechivaet luchshuyu balansirovku mezhdu uzlami superkomp’yutera. Do sikh por v nashei oblasti nikto ne predlagal ispol’zovat’ imenno takoi podkhod».
V svoei rabote issledovateli testirovali zadachu o vzryvayushcheisya provolochke – eto yavlenie nablyudaetsya, naprimer, pri razryadke kondensatora cherez provodnik («provolochku»). V moment razryadki provodnik ochen’ bystro nagrevaetsya do desyatkov tysyach gradusov i perekhodit v sostoyanie plazmy. Pri etom proiskhodit mnozhestvo ves’ma slozhnykh protsessov, v tom chisle vozniknovenie udarnoi volny, chto sushchestvenno oslozhnyaet tochnoe opisanie etogo prostogo s vidu yavleniya. Po sravneniyu s traditsionnym razbieniem, kogda protsessoram otdayutsya na raschet nepodvizhnye oblasti prostranstva, razbienie, predlozhennoe avtorami novoi raboty, pozvolyaet uvelichit’ skorost’ rascheta v zadache o vzryvayushcheisya provolochke v 3-6 raz pri odinakovom kolichestve protsessorov.
Levaya chast’. Algoritm izmenyaet raspredelenie yacheek diagrammy Voronogo po mere rasshireniya provolochki pri nagreve (sleva napravo). Iznachal’no plotnost’ provolochki odinakova po vsemu ob’emu, i yacheiki takzhe raspredelyayutsya ravnomerno. Pri vzryvnom rasshirenii plotnost’ v tsentre i po krayam stanovitsya rezko neodnorodnoi, poetomu yacheiki sosredotachivayutsya s krayu, uvelichivaya tem samym effektivnost’ vychislenii: esli by raspredelenie ne menyalos’, protsessory, zanyatye raschetami dlya tsentral’noi oblasti provolochki, prostaivali by.
Pravaya chast’: pri ispol’zovanii novogo algoritma razbieniya effektivnost’ raschetov pochti lineino vozrastaet s uvelicheniem kolichestva protsessorov. Takoe maksimal’no effektivnoe ispol’zovanie vychislitel’noi moshchnosti nazyvayut ideal’nym uskoreniem raschetov.
Izobrazhenie avtorov raboty.
«Novyi parallel’nyi algoritm pozvolit effektivno ispol’zovat’ vychislitel’nye klastery, sostoyashchie iz mnogikh tysyach protsessorov, i tem samym sushchestvenno rasshirit’ vozmozhnosti modelirovaniya slozhnykh protsessov, proiskhodyashchikh pod vozdeistviem moshchnykh sil, ot vozdeistviya lazerov i vzryvov do formirovaniya zvezd – poyasnyaet eshche odin soavtor raboty, vedushchii nauchnyi sotrudnik VNII avtomatiki imeni N.L. Dukhova i sotrudnik ITF imeni L.D. Landau Vasilii Zhakhovskii. – Nikakimi imeyushchimisya kommercheskimi programmnymi paketami takoe modelirovanie osushchestvit’ nevozmozhno».
Rabota podderzhana grantom RNF №14-19-01599.
Dogovorit’sya ob interv’yu s uchenymi, kommentariyakh ili zaprosit’ dopolnitel’nuyu informatsiyu, v tom chisle polnyi tekst stat’i, mozhno po adresu: [email protected].