ПАРАЛЛЕ́ЛЬНОЕ ПРОГРАММИ́РОВАНИЕ

ПАРАЛЛЕ́ЛЬНОЕ ПРОГРАММИ́РОВАНИЕ, раз­ра­бот­ка про­грамм­но­го обес­пе­че­ния, ко­то­рое вы­пол­ня­ет зна­чит. часть вы­чис­ле­ний од­но­вре­мен­но (па­рал­лель­но). Це­ли П. п.: ре­ше­ние боль­ших за­дач с объ­ё­мом дан­ных, пре­вос­хо­дя­щим воз­мож­но­сти од­но­про­цес­сор­ной вы­чис­лит. сис­те­мы; уве­ли­че­ние эф­фек­тив­но­сти про­грамм за счёт па­рал­лель­но­го вы­пол­не­ния как мож­но боль­ше­го чис­ла опе­ра­ций. Воз­мож­ность П. п. обу­слов­ле­на тем, что боль­шие за­да­чи час­то воз­мож­но раз­де­лить на неск. мень­ших под­за­дач, ко­то­рые мо­гут вы­пол­нять­ся од­но­вре­мен­но. В за­ви­си­мо­сти от то­го, как час­то под­за­да­чи долж­ны син­хро­ни­зи­ро­вать­ся или взаи­мо­дей­ст­во­вать ме­ж­ду со­бой, раз­ли­ча­ют мел­ко­зер­ни­стый (fine-grained) и круп­но­зер­ни­стый (coarse-grained) па­рал­ле­лизм про­грамм­ных при­ло­же­ний. В пер­вом слу­чае под­за­да­чи взаи­мо­дей­ст­ву­ют очень час­то (мно­го раз в се­кун­ду), во вто­ром – зна­чи­тель­но ре­же (в иде­аль­ном слу­чае под­за­да­чи не взаи­мо­дей­ст­вуют во­все ли­бо взаи­мо­дей­ст­вие про­исхо­дит край­не ред­ко, напр. в на­ча­ле и в кон­це ра­бо­ты).

Де­ле­ние на под­за­да­чи оп­ре­де­ля­ет ви­ды па­рал­ле­лиз­ма, ис­поль­зуе­мые в ком­пь­ю­тер­ной про­грам­ме. Па­рал­ле­лизм уров­ня ин­ст­рук­ций ос­но­ван на том фак­те, что совр. про­цес­со­ры име­ют неск. функ­цио­наль­ных уст­ройств кон­вей­ер­ной струк­ту­ры. По­ток ин­ст­рук­ций в про­грам­ме пе­ре­упо­ря­до­чи­ва­ет­ся та­ким об­ра­зом, что­бы как мож­но боль­шее их чис­ло вы­пол­ня­лось па­рал­лель­но; ко­ли­че­ст­во од­но­вре­мен­но вы­пол­няе­мых ин­ст­рук­ций за­ви­сит от на­бо­ра функ­цио­наль­ных уст­ройств, дли­ны кон­вей­е­ра и за­ви­си­мо­стей по дан­ным ме­ж­ду ин­ст­рук­ция­ми (за­ви­си­мость воз­ни­ка­ет, ко­гда ре­зуль­тат од­ной ин­струк­ции яв­ля­ет­ся опе­ран­дом дру­гой; в этом слу­чае вто­рую ин­ст­рук­цию нель­зя вы­пол­нять до за­вер­ше­ния пер­вой). Па­рал­ле­лизм дан­ных свя­зан с цик­ла­ми про­грам­мы, в ко­то­рых об­ра­ба­ты­ва­ют­ся мас­си­вы; рас­пре­де­ле­ние дан­ных по уз­лам па­рал­лель­ной сис­те­мы воз­мож­но при от­сут­ст­вии за­ви­си­мо­стей ме­ж­ду ите­ра­ция­ми цик­ла. Па­рал­ле­лизм уров­ня за­дач воз­ни­ка­ет, ко­гда про­грам­ма вы­пол­ня­ет су­ще­ст­вен­но раз­ли­чаю­щие­ся вы­чис­ле­ния над од­ни­ми и те­ми же ли­бо над разл. на­бо­ра­ми дан­ных.

Па­рал­ле­лизм од­но­го по­то­ка ин­ст­рук­ций реа­ли­зу­ет­ся в су­пер­ска­ляр­ных (см. в ст. Мик­ро­про­цес­сор) и кон­вей­ер­ных про­цес­со­рах, а так­же в ма­ши­нах с длин­ным ко­манд­ным сло­вом (very long in­stru­c­tion word – VLIW). Мно­го­ядер­ные про­цес­со­ры вы­пол­ня­ют па­рал­лель­но ин­ст­рук­ции из не­сколь­ких по­то­ков, име­нуе­мых ни­тя­ми (thread). Сим­мет­рич­ные муль­ти­про­цес­со­ры (symmetric multi­pro­cessor – SMP) с об­щей па­мя­тью реа­ли­зу­ют мно­го­по­точ­ные вы­чис­ле­ния и па­рал­ле­лизм дан­ных; для этих сис­тем воз­мож­но так­же П. п. уров­ня за­дач. Муль­ти­про­цес­сор­ные сис­те­мы с рас­пре­де­лён­ной па­мя­тью – мас­сив­но-па­рал­лель­ные сис­те­мы (massive pa­rallel processor – MPP) и кла­сте­ры спо­соб­ны вы­пол­нять про­грам­мы как с па­рал­ле­лиз­мом дан­ных, так и за­дач. Взаи­мо­дей­ст­вие про­цес­сов па­рал­лель­ной про­грам­мы в слу­чае рас­пре­де­лён­ной па­мя­ти осу­ще­ст­в­ля­ет­ся по­сред­ст­вом об­ме­на со­об­ще­ния­ми. Ме­ха­низм рас­пре­де­лён­ной об­щей па­мя­ти (di­stri­buted shared memory) и вир­туа­ли­за­ция об­щей па­мя­ти по­зво­ля­ют скрыть ме­ха­низм пе­ре­да­чи со­об­ще­ний от про­грам­ми­ста и де­ла­ют в ря­де слу­ча­ев П. п. для сис­тем с рас­пре­делён­ной па­мя­тью бо­лее про­стым. Ряд за­дач П. п. ре­ша­ет­ся с ис­поль­зо­ва­ни­ем спе­циа­ли­зир. па­рал­лель­ных сис­тем, напр. век­тор­ных про­цес­со­ров, сис­тем, по­стро­ен­ных на ос­но­ве гра­фич. про­цес­со­ров (graphics processing units – GPU) или про­грам­ми­руе­мых поль­зо­ва­те­лем вен­тиль­ных мат­риц (field-programmable gate array – FPGA).

Раз­ли­ча­ют яв­ный и не­яв­ный под­хо­ды к П. п. В пер­вом слу­чае дан­ные и вы­чис­ле­ния рас­пре­де­ля­ют­ся про­грам­ми­стом по уз­лам па­рал­лель­ной сис­те­мы яв­но при соз­да­нии ко­да при­ло­же­ния. При не­яв­ном под­хо­де ав­то­ма­тич. рас­пре­де­ле­ние дан­ных и вы­чис­ле­ний яв­ля­ет­ся за­да­чей сис­те­мы про­грам­ми­ро­ва­ния. П. п. уров­ня ин­ст­рук­ций ос­но­ва­но на не­яв­ном под­хо­де с ис­поль­зо­ва­ни­ем рас­па­рал­ле­ли­ваю­щих ком­пи­ля­то­ров. Мно­го­по­точ­ное П. п. для SMP-сис­тем ис­поль­зу­ет оба под­хо­да – ав­то­ма­тич. рас­па­рал­ле­ли­ва­ние при­ло­же­ний и яв­ное П. п. Для ком­пь­ю­те­ров с рас­пре­де­лён­ной па­мя­тью ис­поль­зу­ет­ся яв­ный под­ход; ав­то­ма­тич. рас­па­рал­ле­ли­ва­ние про­грамм для MPP ог­ра­ни­че­но экс­пе­рим. про­ек­та­ми.

Ин­ст­ру­мен­таль­ные сред­ст­ва П. п. вклю­ча­ют в се­бя биб­лио­те­ки про­грамм (POSIX Threads, OpenMP, MPI), про­грам­мы от­лад­чи­ки и про­фи­ли­ров­щи­ки (ис­поль­зуе­мые для оцен­ки вре­ме­ни вы­пол­не­ния разл. час­тей про­грам­мы). По­след­ние при­ме­ня­ют­ся не толь­ко для уст­ра­не­ния де­фек­тов, но и для дос­ти­же­ния долж­ной эф­фек­тив­но­сти ра­бо­ты па­рал­лель­ной про­грам­мы. Вы­со­ко­уров­не­вые язы­ки П. п. (High Performance Fortran, Occam и др.) ны­не прак­ти­че­ски не ис­поль­зу­ют­ся, по­сколь­ку не мо­гут обес­пе­чить долж­но­го уров­ня эф­фек­тив­но­сти (ре­аль­ное вре­мя счё­та про­грам­мы в ра­зы боль­ше воз­мож­но­го для дан­но­го ал­го­рит­ма на дан­ной па­рал­лель­ной сис­теме). Для П. п. спе­циа­ли­зир. сис­тем, по­стро­ен­ных на ос­но­ве GPU, ис­поль­зу­ют спе­циа­ли­зир. про­грамм­ные сред­ст­ва (CUDA, OpenCL). Ряд хо­ро­шо рас­пре­де­ляе­мых за­дач с очень боль­ши­ми объ­ё­ма­ми дан­ных ре­ша­ет­ся на кла­сте­рах с по­мо­щью реа­ли­за­ций фрейм­вор­ка MapReduce (тех­но­ло­гии ком­па­нии «Google» для бы­ст­рой об­ра­бот­ки боль­ших объ­ё­мов дан­ных, под­дер­жи­ваю­щей обыч­ные для па­рал­лель­ных ал­го­рит­мов эта­пы – рас­пре­де­ле­ние ис­ход­ных дан­ных по про­цес­со­рам и сбор ре­зуль­та­тов по­сле счё­та).

П. п. ис­поль­зу­ет­ся в та­ких об­лас­тях, как га­зо­вая ди­на­ми­ка, ядер­ная фи­зи­ка, мо­ле­ку­ляр­ная био­ло­гия, гид­ро­ме­тео­ро­ло­гия, гео­ло­го­раз­вед­ка, ав­то­ма­ти­зир. про­ек­ти­ро­ва­ние, крип­то­гра­фия, про­гно­зи­ро­ва­ние биз­нес-про­цес­сов и др. По­сред­ст­вом П. п. ре­ша­ют­ся за­да­чи ли­ней­ной ал­геб­ры, ком­би­на­тор­ной ло­ги­ки, спек­траль­ные ме­то­ды (бы­строе пре­об­ра­зо­ва­ние Фу­рье), ме­тод се­ток (ме­тод ко­неч­ных эле­мен­тов), ме­тод Мон­те-Кар­ло, об­ход гра­фов и сор­ти­ров­ка, ди­на­мич. про­грам­ми­ро­ва­ние, ме­тод вет­вей и гра­ниц и др.