Lygiagretaus skaičiavimo samprata yra bendra organizacinė schema. Lygiagrečios skaičiavimo sistemos

Lygiagretaus skaičiavimo procesai ir sistemos (13 paskaita)

Paralelizmo rūšys

Lygiagretus duomenų apdorojimas yra dviejų tipų: konvejerinis ir faktinis lygiagretumas.

Lygiagretus apdorojimas. Jei tam tikras įrenginys per laiko vienetą atlieka vieną operaciją, tai jis atliks tūkstantį operacijų per tūkstantį vienetų. Jei darysime prielaidą, kad yra penki identiški nepriklausomi įrenginiai, galintys veikti vienu metu, tai penkių įrenginių sistema tą patį tūkstantį operacijų gali atlikti ne per tūkstantį, o per du šimtus laiko vienetų.

Konvejerio apdirbimas. Ko reikia norint pridėti du realūs skaičiai, pavaizduotas slankiojo kablelio forma? Daug smulkių operacijų, tokių kaip užsakymų palyginimas, užsakymų derinimas, mantisų pridėjimas, normalizavimas ir kt. Pirmųjų kompiuterių procesoriai atliko visas šias „mikrooperacijas“ kiekvienai argumentų porai vieną po kitos, kol pasiekė galutinį rezultatą, ir tik tada pradėjo apdoroti kitą terminų porą. Dujotiekio apdorojimo idėja yra atskirti atskirus bendrosios operacijos atlikimo etapus, o kiekvienas etapas, baigęs savo darbą, perduotų rezultatą kitam, kartu gaudamas naują įvesties duomenų dalį. Dėl anksčiau atliktų operacijų derinio akivaizdžiai padidėja apdorojimo greitis. Tarkime, kad operacijoje yra penkios mikrooperacijos, kurių kiekviena atliekama per vieną laiko vienetą. Jei yra vienas nedalomas serijinis įrenginys, jis apdoros 100 argumentų porų 500 vienetų. Jei kiekviena mikrooperacija yra atskirta į atskirą konvejerio įrenginio etapą (arba kitaip vadinamą etapą), tai penktame laiko vienete, skirtinguose tokio įrenginio apdorojimo etapuose, bus išdėstytos pirmosios penkios argumentų poros. , o visas šimto porų rinkinys bus apdorotas per 5 + 99 = 104 laiko vienetus – pagreitis, palyginti su serijiniu įrenginiu, yra beveik penkis kartus (remiantis konvejerio etapų skaičiumi).

Atrodytų, kad dujotiekio apdorojimą galima sėkmingai pakeisti įprastu lygiagretumu, kuriam pagrindinį įrenginį dubliuojame tiek kartų, kiek numatoma dujotiekio etapų skaičius. Bet padidinę įrenginių skaičių penkis kartus, gerokai padidiname ir įrangos apimtį, ir jos kainą.

Lygiagrečių sistemų diegimas

Nuo 1945 m. iki šių dienų kompiuterių našumas išaugo eksponentiškai (remiantis vidutiniškai kas 10 metų). Kompiuterių architektūra patyrė didelių pokyčių – nuo serijinės iki lygiagrečios.

Kompiuterio našumas yra tiesiogiai susijęs su laiku, kurio reikia pagrindinėms funkcijoms atlikti, ir šių pagrindinių operacijų, kurias galima atlikti vienu metu, skaičiumi. Vienos paprastos instrukcijos vykdymo laikas galiausiai yra ribotas.

Lengva daryti išvadą, kad negalite apsiriboti greičio didinimu tik procesoriaus laikrodžio dažnio sąskaita. Priklausomybė nuo procesorių galiausiai veda į aklavietę. Kita šios srities strategija – procesoriaus mikroschemoje naudoti vidinį lygiagretumą. Tačiau tokia technologija yra labai brangi. Šiuolaikiniai superkompiuteriai daugiausia grindžiami idėja naudoti daugybę jau turimų palyginti nebrangių procesorių.

Tai taip pat apima tokias sistemas kaip: superkompiuteriai su tūkstančiais procesorių; darbo vietų tinklai; kelių procesorių darbo stotys ir kt.

Multikompiuteris – tai tam tikra suma von Neumann mašinos(mazgai), sujungti tinklu. Kiekvienas kompiuteris vykdo savo programą. Šios programos gali pasiekti vietinę atmintį ir siųsti bei gauti pranešimus tinkle. Pranešimai, naudojami ryšiui tarp kompiuterių, prilygsta skaitymo ar rašymo operacijoms iš nuotolinės atminties. Idealizuotame tinkle pranešimo pristatymo laikas tarp įrenginių nepriklauso nuo atstumo tarp mazgų ar tinklo srauto, bet priklauso nuo siunčiamo laiško ilgio.

Kelių kompiuterių modelio parametras yra tas, kad prieiga prie vietinės (to paties mazgo) atminties yra pigesnė nei nuotolinės (esančios kitame mazge) atmintis. Tie. Skaitymo ir rašymo operacijos yra pigesnės nei pranešimų siuntimas ar gavimas. Todėl pageidautina, kad vietiniai duomenys būtų pasiekiami daug dažniau nei nuotoliniai. Ši pagrindinė programinės įrangos savybė vadinama lokalumu. Vietovės vertė priklauso nuo nuotolinės prieigos ir vietinės prieigos kainos santykio.

Kiti automobilių modeliai. Pažvelkime į svarbiausias kompiuterių architektūras. Keli kompiuteriai yra labai panašūs į tai, kas dažnai vadinama MIMD (Multiple Instruction Multiple Data) paskirstytos atminties kompiuteriu. MIMD reiškia, kad kiekvienas procesorius gali apdoroti atskirą komandų srautą per savo vietinius duomenis. Paskirstyta atmintis reiškia, kad atmintis yra paskirstyta tarp procesorių. Esminis skirtumas tarp MIMD kompiuterio ir kelių kompiuterių yra tas, kad pranešimo tarp dviejų mazgų pristatymo kaina nepriklauso nuo mazgo vietos ir tinklo srauto. Pagrindiniai šios klasės atstovai: IBM SP, Intel Paragon, Thinking Machines CM 5, Cray T 3D, Meiko CS-2, CUBE.

Kita superkompiuterių klasė yra kelių procesorių arba MIMD bendros atminties kompiuteris. Daugiaprocesoriuje visi procesoriai dalijasi prieiga prie bendros atminties, dažniausiai per magistralę arba per magistralės hierarchiją. Idealizuotame lygiagrečios laisvosios prieigos mašinos (PRAM) modelyje, dažnai naudojant teoriškai ištirtus lygiagrečius algoritmus, bet kuris procesorius gali pasiekti bet kurį atminties elementą tuo pačiu metu. Ši architektūra paprastai apima specialią atminties įrenginio formą. Prieigų prie bendros atminties skaičius sumažinamas išsaugant dažnai pasiekiamų duomenų kopijas talpykloje, susietoje su kiekvienu procesoriumi.

Prieiga prie šios talpyklos yra daug greičiau nei prieiga prie bendrosios atminties, todėl vietovė yra labai svarbi. Programos, sukurtos keliems kompiuteriams, gali taip pat efektyviai veikti keliuose procesoriuose, nes bendra atmintis leidžia efektyviai perduoti pranešimus. Šios klasės atstovai yra „Silicon Graphics Challenge“, „Sequent Symmetry“ ir daugelis kelių procesorių darbo stočių.

Labiau specializuota lygiagrečių kompiuterių klasė yra SIMD (Single Instruction Miltiple Data) kompiuteriai. SIMD įrenginiuose visi procesoriai veikia su tuo pačiu skirtingų duomenų instrukcijų srautu. Šis metodas gali sumažinti programinės įrangos sudėtingumą ir aparatūra, tačiau tai prasminga tik esant specializuotoms problemoms, kurioms būdingas didelis reguliarumas, pvz., vaizdo apdorojimas ir tam tikro tipo skaitmeninis modeliavimas. Daugeliui kompiuterių taikomi algoritmai paprastai negali būti efektyviai vykdomi SIMD kompiuteriuose.

Neurokompiuterinės sistemos.

Neurokompiuterinis įrenginys – tai sistema, kurios veikimas yra maksimaliai orientuotas į neuroninių tinklų algoritmų įgyvendinimą. Pagrindinis skirtumas tarp neurokompiuterių ir kitų skaičiavimo sistemų yra didelio skaičiavimų lygiagretumo užtikrinimas naudojant specializuotą neuroninio tinklo loginį pagrindą arba specifinius architektūrinius sprendimus. Galimybė pateikti neuroninio tinklo algoritmus įgyvendinant neuroninio tinklo loginį pagrindą yra pagrindinė būtina sąlyga norint smarkiai padidinti neurokompiuterių našumą.

Šiuo metu skaitmeninių neurokompiuterių kūrimas aktyviausiai vykdomas šiose srityse:

· programinė neuroninių tinklų algoritmų emuliacija, pagrįsta įprastiniu naudojimu skaičiavimo įrenginiai Ir programinė įranga neuroniniams tinklams modeliuoti;

· Neuroninių tinklų programinė ir techninė emuliacija standartiniais skaičiavimo įrankiais su įskiepiu virtualaus neuroninio tinklo bloku, atliekančiu pagrindines neurooperacijas ir programine įranga, atliekančia bendrąsias valdymo funkcijas;

· aparatinė neuroninių tinklų realizacija.

Nepaisant to, kad didžiausią efektą diegiant neuroninių tinklų algoritmus galima pasiekti tik naudojant trečiosios krypties neurokompiuterius, jų platų panaudojimą riboja aukštosios technologijos. Pavyzdžiui, neurokompiuteris Synaps1 yra vienas iš trečiosios krypties neurokompiuterių atstovų, turi daugiaprocesorių architektūrą, originalų atminties posistemio dizainą, skaičiavimo operacijoms atlikti naudoja signalų procesorius ir specialius signalų matricų procesorius MA16. Dėl šios priežasties neurokompiuterio našumas siekė kelis milijardus daugybos ir pridėjimo per sekundę. Programinė įrangaĮ šią sistemą įeina Synaps1 OS su neuroalgoritmų biblioteka, taip pat programinė įranga: pagrindinė NS biblioteka, neuroalgoritmų programavimo kalbos (nAPL) kompiliatorius (C++ bibliotekos funkcijų rinkinys) ir kt. Taikomieji tyrimai parodė, kad trečios krypties neurokompiuterių panaudojimas leidžia bent trimis dydžiais padidinti įprastų skaičiavimo sistemų našumą ir imituoti neuroninius tinklus su milijonais jungčių. Pavyzdžiui, Synaps1 leidžia imituoti neuroninį tinklą su 64 milijonais sinapsių naudojant įvairias aktyvinimo funkcijas.

Yra dvi kompiuterių sistemų klasės, kurios kartais naudojamos kaip lygiagrečiai kompiuteriai vietinis tinklas(LAN), kuriame fiziškai arti (pavyzdžiui, tame pačiame pastate) esantys kompiuteriai yra sujungti sparčiuoju tinklu ir pasaulinis tinklas(WAN), kuriame yra prijungti geografiškai nutolę kompiuteriai. Nors tokio tipo sistemos kelia papildomų problemų, tokių kaip saugumas, patikimumas, jos gali būti laikomos įvairiais kompiuteriais, nors ir brangiai. Nuotolinis prisijungimas.

Lygiagrečių sistemų naudojimo sunkumai

Didžiulį lygiagrečių kompiuterių ir superkompiuterių našumą daugiau nei kompensuoja jų naudojimo sunkumai.

Jūs turite programą ir prieigą prie, tarkime, 256 procesorių kompiuterio. ko tikitės? Taip, aišku: jūs visiškai teisėtai tikitės, kad programa veiks 256 kartus greičiau nei viename procesoriuje. Tačiau greičiausiai taip neatsitiks.

Amdahlio dėsnis. Tarkime, kad programoje operacijų, kurias reikia atlikti nuosekliai, dalis yra lygi f, kur 0<=f <=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из "p" процессоров при данном значении f, можно воспользоваться законом Амдала: если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (10 получается только в том случае, когда время исполнения параллельной части равно 0).

Amdahlio dėsnio pasekmė. Norint paspartinti programos vykdymą q kartų, reikia paspartinti bent q kartų ne mažiau nei (1-1/q) programos dalis. Todėl, jei norite pagreitinti programą 100 kartų, palyginti su jos nuoseklia versija, tuomet turite ne mažiau pagreitinti bent 99,99% kodo!

Taigi, pasiekti, kad lygiagrečiai skaičiavimo sistema veiktų maksimaliai efektyviai konkrečioje programoje, nėra lengva užduotis, nes būtina atidžiai derinti programų struktūrą ir algoritmus su lygiagrečių skaičiavimo sistemų architektūrinėmis ypatybėmis.

Lygiagrečių sistemų programavimas

Von Neumann mašinos modelis daro prielaidą, kad procesorius vykdo instrukcijų seką. Instrukcijose, be įvairių aritmetinių operacijų, gali būti nurodyti duomenų, kuriuos reikia nuskaityti/įrašyti į atmintį, adresus ir/arba kitos vykdytinos komandos adresą. Nors kompiuterį galima programuoti tik pagal šį pagrindinį modelį, šis metodas yra pernelyg sudėtingas daugeliu atvejų dėl to, kad turime sekti milijonus atminties pozicijų ir organizuoti tūkstančių mašinos komandų vykdymą. Vadinasi, taikoma modulinio projektavimo technika, kai iš paprastų komponentų kuriamos sudėtingos programos, o komponentai struktūrizuojami pagal aukštesnio lygio abstrakcijas (pvz., duomenų struktūras, iteracines kilpas ir procedūras). Abstrakcijos (pvz., procedūros) palengvina moduliškumo išnaudojimą, nes leidžia manipuliuoti objektais nepažeidžiant jų vidinės struktūros. Taip sukuriamos aukšto lygio kalbos, tokios kaip Fortran, C, Ada ir Java, kurios leidžia plėtoti šias abstrakcijas, kurios automatiškai verčiamos į vykdomąjį kodą. Lygiagretusis programavimas suteikia papildomų sudėtingumo šaltinių: jei turime programuoti žemiausiu lygiu, turime ne tik padidinti vykdomų instrukcijų skaičių, bet ir valdyti tūkstančių procesorių vykdymą bei koordinuoti milijonus tarpprocesorių komunikacijų. Todėl abstrakcija ir moduliškumas yra ne mažiau svarbūs kaip nuosekliame programavime. Tiesą sakant, moduliškumą pabrėžiame kaip ketvirtą pagrindinį lygiagrečios programinės įrangos reikalavimą, be lygiagretumo, mastelio ir lokalumo.

Pagrindinės paralelinio programavimo abstrakcijos yra susijusios su užduotimis ir kanalais:

1. Lygiagretusis skaičiavimas susideda iš vienos ar kelių užduočių. Užduotys vykdomos lygiagrečiai. Programos vykdymo metu užduočių skaičius gali keistis.

2.Užduotis išskiria nuosekliąją programą ir vietinę atmintį. Be to, įėjimų ir išėjimų rinkinys apibrėžia jo sąsają aplinkoje.

3. Užduotis gali atlikti keturis pagrindinius veiksmus, be skaitymo ir rašymo vietinėje atmintyje: išsiųsti pranešimą į savo išvesties prievadus, gauti pranešimą iš įvesties prievadų, sukurti naujas užduotis ir sunaikinti (užbaigti) užduotį.

4. Pranešimo siuntimo operacija yra asinchroninė ir baigiama nedelsiant. Gavimo operacija yra sinchroninė ir sukelia užduotį, kuri blokuoja procesą, kol bus gautas pranešimas.

5.I/O poros gali būti susietos eilėje esančiais pranešimais, vadinamais kanalais. Galima kurti ir ištrinti kanalus, o nuorodas į kanalus (prievadus) galima įtraukti į pranešimus, kad ryšys dinamiškai keistųsi.

6. Darbai gali būti susieti su fiziniais procesoriais įvairiais būdais; ekrano programa neturi įtakos programos semantikai. Konkrečiai, keli darbai gali būti susieti su vienu procesoriumi (taip pat galima įsivaizduoti, kad viena užduotis gali būti susieta su keliais procesoriais, tačiau į šią galimybę čia neatsižvelgiama).

Užduočių abstrakcijai reikalinga lokalumo savybė: užduoties lokalioje atmintyje esantys duomenys yra „uždaryti“; kiti duomenys „ištrinami“. Kanalo abstrakcija suteikia mechanizmą, nurodantį, kokie vienos užduoties duomenys turi būti apskaičiuoti, kad būtų galima pradėti vykdyti kitą užduotį. (Tai būdinga priklausomybei nuo duomenų). Užduotis ir kanalo modelis taip pat turi keletą kitų savybių:

Spektaklis . Nuoseklios programavimo abstrakcijos, tokios kaip procedūros ir duomenų struktūros, yra veiksmingos, nes jas galima paprastai ir efektyviai susieti su von Neumann kompiuteriu. Užduotys ir kanalai turi panašiai tiesioginį pasiskirstymą keliuose kompiuteriuose. Užduotis yra kodo dalis, kuri gali būti vykdoma nuosekliai viename procesoriuje. Jei dvi užduotys, kurios dalijasi kanalu, yra susietos su kitais procesoriais, kanalo ryšys įgyvendinamas kaip tarpprocesorių ryšys; jei jie susieti su tuo pačiu procesoriumi, gali būti naudojami keli efektyvesni mechanizmai.

Platinimo nepriklausomumas . Kadangi užduotys bendrauja naudojant tą patį mechanizmą (kanalus), nepriklausomai nuo užduoties vietos, programos apskaičiuojamas rezultatas nepriklauso nuo to, kur užduotis vykdoma. Todėl algoritmus galima kurti ir įgyvendinti nesijaudinant dėl procesorių, kuriuose jie veiks, skaičiaus; Tiesą sakant, algoritmai dažnai skirti sukurti daug daugiau užduočių nei procesoriai. Tai paprastas būdas pasiekti mastelį: didėjant procesorių skaičiui, vienam procesoriui tenkančių užduočių skaičius mažėja, tačiau paties algoritmo keisti nereikia. Kai yra daugiau užduočių, nei procesoriai galėtų atlikti, kad užmaskuotų ryšio vėlavimus, pateikiami kiti skaičiavimai, kuriuos galima atlikti, kol vyksta ryšys, kad būtų galima pasiekti nuotolinius duomenis.

Moduliškumas. Moduliniame programavime skirtingi programos komponentai yra kuriami atskirai kaip nepriklausomi moduliai ir tada sujungiami, kad būtų sudaryta visa programa. Sąveika tarp modulių apsiriboja aiškiai apibrėžtomis sąsajomis. Vadinasi, modulinius diegimus galima keisti nekeičiant kitų komponentų, o programos savybes galima nustatyti pagal jos modulių specifikaciją ir tuos modulius jungiančio kodo. Sėkmingai pritaikius modulinę plėtrą, sumažėja programinės įrangos sudėtingumas ir palengvinamas pakartotinis kodo naudojimas.

Determinizmas. Algoritmas arba programa yra deterministiniai, jei, kai vykdomi naudojant tam tikrą įvestį, jis visada sukuria tą pačią išvestį. Tai nėra deterministinis, jei keli tos pačios įvesties vykdymai gali sukurti skirtingą išvestį. Nors nedeterminizmas kartais yra naudingas ir turėtų būti palaikomas, paralelinio programavimo modelis, palengvinantis deterministinių programų rašymą, yra labai pageidautinas. Deterministinės programos yra labiau suprantamos. Taip pat, tikrinant teisingumą, reikia skaičiuoti tik vieną lygiagrečios programos vykdymo seką, o ne visas galimas vykdymo sekas.

Dabartinė puslapio versija dar nepatvirtinta

Dabartinės puslapio versijos dar nepatikrino patyrę dalyviai ir ji gali labai skirtis nuo 2014 m. spalio 5 d. patikrintos versijos; būtini patikrinimai.

Lygiagretusis skaičiavimas- kompiuterinio skaičiavimo organizavimo būdas, kai programos kuriamos kaip sąveikaujančių skaičiavimo procesų, vykstančių lygiagrečiai (vienu metu), visuma. Šis terminas apima programavimo lygiagretumo problemas, taip pat efektyvių aparatinės įrangos diegimų kūrimą. Lygiagrečio skaičiavimo teorija sudaro taikomosios algoritmų teorijos atšaką.

Yra įvairių būdų, kaip įgyvendinti lygiagretųjį skaičiavimą. Pavyzdžiui, kiekvienas skaičiavimo procesas gali būti įgyvendintas kaip operacinės sistemos procesas arba skaičiavimo procesai gali būti vykdymo gijų rinkinys viename OS procese. Lygiagrečios programos gali būti fiziškai vykdomos arba nuosekliai viename procesoriuje – paeiliui keičiant kiekvieno skaičiavimo proceso žingsnius, arba lygiagrečiai – kiekvienam skaičiavimo procesui priskiriant vieną ar daugiau procesorių (esančių šalia arba paskirstytų kompiuterių tinkle).

Pagrindinis sunkumas kuriant lygiagrečias programas yra užtikrinti teisingą skirtingų skaičiavimo procesų sąveikų seką, taip pat procesų dalijamų išteklių koordinavimą.

Kai kuriose paralelinio programavimo sistemose duomenų perdavimas tarp komponentų yra paslėptas nuo programuotojo (pavyzdžiui, naudojant pažado mechanizmą), o kitose jis turi būti aiškiai nurodytas. Aiškios sąveikos gali būti suskirstytos į du tipus:

Pranešimus perduodančios lygiagrečios sistemos dažnai yra lengviau suprantamos nei bendros atminties sistemos ir paprastai laikomos geresniu lygiagretaus programavimo metodu. Yra daugybė matematinių teorijų, skirtų pranešimų perdavimo sistemoms tirti ir analizuoti, įskaitant veikėjo modelį ir įvairius proceso skaičiavimo tipus. Pranešimų siuntimas gali būti efektyviai įgyvendintas simetriniuose daugiaprocesoriuose su bendra nuoseklia atmintimi arba be jos.

Paskirstytos atminties lygiagretumas ir pranešimų perdavimo lygiagretumas turi skirtingas veikimo charakteristikas. Paprastai (bet ne visada) procesų atminties ir užduočių perjungimo laikas yra mažesnis pranešimų perdavimo sistemoms, tačiau pranešimų siuntimas yra brangesnis nei procedūrų iškvietimas. Šiuos skirtumus dažnai užgožia kiti veiksniai, turintys įtakos našumui.

Plaksin M.A.

Nacionalinis tyrimų universitetas Aukštoji ekonomikos mokykla (Permės filialas), Permė, Ph.D., Informacinių technologijų versle katedros docentas, mapl @ list. ru

„SUPERKOMPIUTERIAI“ VS „LYGIALELIS PROGRAMAVIMAS“. „LYGIALELIS PROGRAMAVIMAS“ VS „BENDRADARBIAVIMAS“. KAIP STUDIJUSI TEMĄ „LYGIALELIS SKAIČIAVIMAS“ VIDURINĖJE MOKYKLOJE?

RAKTINIAI ŽODŽIAI

Informatika, lygiagretusis programavimas, lygiagretusis skaičiavimas, lygiagrečiai algoritmai, superkompiuteriai, pradinė mokykla, vidurinė mokykla, TRIZformashka.

ANOTACIJA

Straipsnis skirtas temos „lygiagretusis skaičiavimas“ įtraukimui į mokyklos informatikos kursą. Paminėta nemažai šiuo atveju iškylančių problemų, aptariamas temos nagrinėjimo tikslas, medžiagos parinkimas, kai kurie pasiūlymai dėl mokymo metodų, siūlomos metodikos testavimo mechanizmai bei sukaupta patirtis. Klausimas dėl šios medžiagos vietos mokymo programoje nėra sprendžiamas.

Dabartinis informatikos vystymosi etapas yra susijęs su masiniu skaičiavimų lygiagretumo plitimu visuose lygmenyse (kelių mašinų klasteriai, daugiaprocesoriai kompiuteriai, kelių branduolių procesoriai).

Masinis paralelizmo plitimas turi rimtų pasekmių, kurias dar reikia nustatyti ir išanalizuoti. Pradėkime nuo kai kurių teorinių problemų sąrašo.

Šiuolaikinė algoritmų teorija buvo sukurta atsižvelgiant į nuoseklaus algoritmo koncepciją. Kaip atsisakymas reikalauti veiksmų sekos paveiks algoritmo sampratą?

Bent pastaruosius 20 metų „algoritmo“ sąvoka buvo diegiama mokyklose, neatsiejamai susijusi su „atlikėjo“ sąvoka. Tai natūralu nuosekliam algoritmui. Ką daryti su lygiagrečiu algoritmu? Ar jį atlieka vienas atlikėjas ar atlikėjų grupė? Norėdami būti konkretesni, kaip pavyzdį paimkime kompiuterinę mokymo programą „Tank Crew“. Šioje programoje studentas turi suprogramuoti tanko įgulos, susidedančios iš trijų žmonių: ginklininko, vairuotojo ir krautuvo, veiksmus. Kiekvienas iš jų turi savo komandų sistemą. Norėdami įvykdyti kovinę misiją (pataikyti į visus taikinius), visi įgulos nariai turi veikti kartu. Tank Crew programos žaidimo lauko pavyzdį žr. 1 pav.

Klausimas: ar šie trys veikėjai turėtų būti laikomi nepriklausomais atlikėjais, ar kaip trys vieno sudėtingo atlikėjo komponentai (įrenginiai)? Tanko įgulai antrasis variantas atrodo natūralesnis, nes nė vienas veikėjas negali atlikti užduoties pats. Bet ką daryti, jei žaidimas tampa sudėtingesnis, o kovinė misija bus priskirta dviem tankams vienu metu? Už tris tankus? Trys vienos komandos nariai gali būti laikomi trimis vieno atlikėjo dalimis. Tačiau kiekviena įgula akivaizdžiai yra nepriklausoma atlikėja. Tai reiškia, kad lygiagretus kelių tankų algoritmas vienu metu bus vykdomas vykdytojų grupės. Pasirodo, kad lygiagrečiam algoritmui reikia apsvarstyti abi galimybes: lygiagrečių veiksmų atlikimą vieno vykdytojo ir vykdytojų grupės. Tanko įgulos atveju liniją nubrėžti lengva. Atlikėjas yra tas, kuris sugeba išspręsti užduotį. Šis vykdytojas gali susidėti iš kelių komponentų, kurių kiekvienas atlieka tam tikrą užduoties dalį, tačiau negali savarankiškai atlikti visos užduoties be kitų komponentų pagalbos. Tačiau ar „visų atlikėjų“ ir kompleksinio atlikėjo dalių atskyrimas visada bus toks paprastas, dabar pasakyti neįmanoma.

Failas 1*ra Langas Apie programą

Vpolyet viskas

Bbno.n«fTb į paryškintą eilutę

Grįžti į pradinį puslapį**"

būtų popnlt žingsnis po žingsnio (įvykdžius „.order komandą nesykoa^“ bus paspaustas mygtukas gV ygolg „n-b next uwr“)

Ё ГГВД iTHWTt. specialus žingsnis

Informacija žingsnis po žingsnio

1 pav. „Tank Crew“ programos žaidimo lauko fragmentas

Atlikėjo dalių, galinčių savarankiškai veikti, identifikavimas reikalauja, kad šios dalys būtų kažkaip pavadintos. Be to, pavadinimas turi leisti rekursiją, nes pačios vaidinančios atlikėjo dalys gali turėti sudėtingą struktūrą.

Būtina susitarti dėl termino kooperatyvo atlikėjų grupei paskirti. Terminas „komanda“ netinka, jis siejamas su „vykdytojų komandų sistema“ ir su „centrinio procesoriaus komandomis“. „Atlikėjų kolektyvas“? „Atlikėjų brigada“?

Š. Algoritmas

n Pataikyti1"; Vairuotojo įkroviklis

1 Išmatuokite orun* ant „master sgkll V Stop V Charge 1

g Pci V Stop V Charge 2

3 Didmeninė prekyba! V Pasukite pagal laikrodžio rodyklę 90 laipsnių V Įkraukite 1 V

L V V pirmasis V įkrovimas? V

5 Ugnis! V Stop V Charge 1

Í P^chm V St*p V Zaryasya? V

7 Ugnis! V Stop V Charge 1 V

3 Pa^ V Pasukite pagal laikrodžio rodyklę 45 laipsnių V Įkraukite 2 V

S Pauzė V Pradėti V Pauzė V

10 Pvdea V Pirmyn V Pauzė ¿d

11 Plrl V Pirmyn V Pauzė V

12 Paum V Pasukite pagal laikrodžio rodyklę 45 laipsnių V Pauzė V

13 Padm V Pirmyn V Pauzė V

14 V

2 pav. „Tank Crew“ programos fragmentas (komandų eilučių pavyzdys) Tradicinė „vykdytojo komandų sistemos“ (SCS) koncepcija ir pačios komandos samprata reikalauja tobulinimo. Jei manome, kad trys tanko įgulos nariai sudaro vieną atlikėją, ką tuomet reikėtų laikyti šio atlikėjo SKI? O kas laikoma komanda? O gal palikti SKI sąvoką kiekvienam veikėjui? Tai yra, tai jau ne VYKDYTOJO komandų sistema, o vieno iš atlikėjo komponentų (kuriam dar nėra pavadinimo) komandų sistema?

Komandos sąvoką patogu išplėsti iki „komandų eilutės“. Tanko įgulos komandų eilučių pavyzdį žr. 2 pav. Tačiau „komandų eilutės“ sąvoka gerai tinka tik linijiniams algoritmams. Kitais atvejais liniuotės formuojamos dinamiškai. Vaizdinės lentelės pavidalu jų pavaizduoti neįmanoma.

Tarp algoritmų savybių išsiskiria nauja praktiškai reikšminga charakteristika – galimybė lygiagrečiai. Aiškinamasis klausimas yra apie galimą lygiagretumo laipsnį (kiek prasminga didinti procesorių skaičių vykdant tam tikrą algoritmą).

Atskira problema yra esamų nuoseklių algoritmų lygiagretinimo metodai.

Dar visai neseniai lygiagretus programavimas buvo kelių aukštos kvalifikacijos sistemų programuotojų sritis. Šiandien tai tampa profesinės kompetencijos dalimi. Tačiau lygiagretaus programavimo technologija labai skiriasi nuo tradicinio nuoseklaus programavimo. Grįsdamas šį teiginį, vadovaudamasis L.L. Bosova, cituosime didžiausią Rusijos specialistą lygiagrečiojo skaičiavimo srityje V.V. Vojvodina:

„... Jaunų specialistų paralelinės architektūros skaičiavimo technologijos įvaldymas iškyla su dideliais sunkumais. Mūsų nuomone, taip yra dėl to, kad pažintis su lygiagrečiuoju skaičiavimu, kaip ir apskritai šios srities išsilavinimas, prasideda ne nuo to, nuo ko reikėtų pradėti. Be to, tai, nuo ko reikia pradėti, nėra apžvelgiama jokiuose kursuose. Galimybė greitai išspręsti problemas naudojant lygiagrečios architektūros skaičiavimo technologiją verčia vartotojus pakeisti visą įprastą bendravimo su kompiuteriais stilių. Lyginant, pavyzdžiui, su asmeniniais kompiuteriais ir darbo stotimis, keičiasi beveik viskas: naudojamos kitos programavimo kalbos, modifikuojama dauguma algoritmų, naudotojai turi pateikti daugybę nestandartinių ir sunkiai pasiekiamų sprendžiamų užduočių charakteristikų, sąsaja nustoja būti draugiška ir pan. Svarbus faktas yra tai, kad visiškai neatsižvelgus į naujas eksploatavimo sąlygas, gali gerokai sumažėti naujos ir, be to, gana brangios įrangos naudojimo efektyvumas.

„Tik svarbu, kad studentas kuo anksčiau sužinotų, kad yra ir kitų skaičiavimo procesų organizavimo būdų, o ne tik nuoseklaus „operacijos pagal operaciją“ vykdymo, kad ant šių kitų metodų būtų sukurta galingiausia šiuolaikinė kompiuterinė technologija. kad tik tokia technologija galima išspręsti dideles problemas.pramonės ir mokslo uždaviniai ir kt. Visų pirma svarbu kuo anksčiau atkreipti studentų dėmesį į kritiško požiūrio į nuoseklaus skaičiavimo filosofiją poreikį. Juk būtent su šia filosofija jiems tenka susidurti per visą savo išsilavinimą – tiek mokykloje, tiek universitete. Ir kaip tik ši filosofija trukdo suprasti darbo su lygiagrečios architektūros kompiuteriais ypatybes.

Šiandien mums reikia masinio mokymo lygiagrečiojo programavimo technologijos metodų. Šio straipsnio autorius mano, kad mokymosi procese atėjo laikas revoliucijai nuoseklaus ir lygiagretaus programavimo santykiuose. Iki šiol pirmiausia mokėme nuoseklaus programavimo, o vėliau – nuoseklių algoritmų paralelinimo. Dabar turime iš karto iškelti lygiagretaus programavimo mokymo klausimą. Nuoseklus algoritmas turėtų būti laikomas tam tikra paralelinio algoritmo dalimi, kuriai nereikia ryšio su kitomis jo dalimis. Kaip tai padaryti – atviras klausimas. Vis dar yra keletas idėjų, kurias reikia praktiškai įgyvendinti ir išbandyti. Tikimasi, kad po metų kitoje konferencijoje bus galima aptarti gautus rezultatus.

Prieš trisdešimt metų prasidėjus masiniam gamybos kompiuterizavimui, reikėjo pakelti gyventojų kompiuterinio raštingumo lygį. Dėl to 1985 m. į mokyklos programą buvo įtrauktas informatikos mokslas. Tačiau kompiuterių mokslo kursas sovietinėje (tuometinėje rusiškoje) versijoje neapsiribojo „informatika su mygtuku“ - darbo su taikomosios programinės įrangos paketais ir kompiuteriniais žaidimais technologijos įsisavinimu. Jis pradėjo keisti jaunosios kartos mąstymo stilių. Visų pirma, tai buvo susiję su algoritmiškumu, tikslumu ir griežtumu. Tada informatikos kursas apėmė logikos ir sistemų analizės elementus. Vėliau visa tai labai supaprastino XXI amžiuje taip reikalingų technologijų platinimą. projekto požiūris. Dabar kalbama, kad per ateinantį dešimtmetį turėtų tapti lygiagrečiai naudojami algoritmai

bendros mąstymo kultūros elementas. Klausimas: kaip paralelinio algoritmo sampratos įsisavinimas paveiks ateinančios kartos mąstymą, prie ko prives sąmonės persitvarkymas „lygiagrečiai“?

Masiškai plintant lygiagrečiam informacijos apdorojimui būtina skubiai perkelti atitinkamas sąvokas į viešai prieinamų ir bendrųjų kultūrinių kategoriją. Susipažinimas su lygiagrečiais algoritmais turėtų tapti raštingumo dalimi, kaip per pastarąjį ketvirtį amžiaus tapo pagrindinės algoritmų teorijos sąvokos. Tai galima padaryti tik vienu būdu – įtraukiant aktualias temas į mokyklos informatikos kursą. Tai reiškia, kad mums reikia metodikos pirminiam susipažinimui su lygiagrečiu programavimu vidurinės mokyklos lygmeniu.

Istoriškai pirmasis bandymas lygiagrečiojo skaičiavimo temą įtraukti į mokyklos informatikos kursą buvo atliktas prieš dvidešimt metų. Prieš 20 metų kursuose „Algoritmika“ buvo aprašytas „Statybos direktorius“, kuris vadovavo kelių komandų, kuriančių konstrukciją iš stačiakampių ir trikampių blokų, lygiagrečiams veiksmams. Be to, šiam atlikėjui buvo sukurta programinė įranga. Deja! Dešimtojo dešimtmečio viduryje ši nuostabi metodinė plėtra nebuvo paklausa. Ji buvo beveik dvidešimt metų pranašesnė už savo laiką!

Šiandien situacija tokia, kad lygiagretaus skaičiavimo tema vidurinėje mokykloje visų pirma susijusi su superkompiuterių tema. Įvairių metodinių patobulinimų autoriai sutelkia studentų dėmesį į superkompiuterius, net kai tai nėra būtina. Pakanka pasakyti, kad atitinkama žurnalo „Informatika mokykloje“ skiltis vadinasi „Superkompiuterinis mokymas mokykloje“. Ši situacija turi ir teigiamų, ir neigiamų pusių. Tarp teigiamų aspektų yra šie:

Superkompiuterių tema domina visuomenę, taip pat ir studentus. Šis susidomėjimas šiuolaikiniu lygiu pakartoja susidomėjimą, kurį prieš pusę amžiaus sukėlė didelės mašinos – jų laikų superkompiuteriai;

Superkompiuterių bendruomenės organizacinis palaikymas. Kiekvieną vasarą Maskvos valstybinio universiteto Kompiuterinės matematikos ir kibernetikos fakultete vyksta vasaros superkompiuterių akademija. Ir kiekvieną vasarą šios Akademijos rėmuose organizuojamas mokyklinis trekas informatikos mokytojams. Mokymai teikiami nemokamai. Nerezidentams studentams būstas suteikiamas labai palankiomis sąlygomis. 2015 metų rugsėjį vykusioje konferencijoje „Rusijos superkompiuterių dienos“ buvo surengta mokyklinė sekcija ir meistriškumo klasė informatikos mokytojams. Nuoseklus organizacinis darbas leido nustatyti ir suformuoti mokytojų grupę, suinteresuotą propaguoti šią temą;

Ryškus, charizmatiškas lyderis, pavyzdžiui, Vladimiras Valentinovičius Voevodinas - fizinių ir matematikos mokslų daktaras, profesorius, Rusijos mokslų akademijos narys korespondentas, Maskvos valstybinio universiteto Tyrimų skaičiavimo centro direktoriaus pavaduotojas;

Susidomėjimas ir parama (įskaitant medžiagą) iš „Intel“ atstovybės Rusijoje ir „Intel“ strateginės plėtros vadovo Igorio Olegovičiaus Odincovo.

„Superkompiuterio“ metodo trūkumas yra tas, kad jis susiaurina lygiagrečiojo skaičiavimo sritį. Patys superkompiuteriai, kaip taisyklė, yra neprieinami moksleiviams (nebent dideliuose miestuose juos galima pamatyti ekskursijose). Užduotys, kurias jie turi išspręsti, yra pernelyg sudėtingos moksleiviams ir daugeliu atvejų neturi tiesioginės praktinės reikšmės ir nėra praktiškos.

Natūralus superkompiuterių lauko išplėtimas yra lygiagrečiojo programavimo studijos. Šiuo metu, norint vykdyti lygiagrečias programas, visai nebūtina turėti superkompiuterį. Pakanka kelių branduolių procesoriaus arba vaizdo plokštės su grafikos greitintuvų rinkiniu. Ir tai jau prieinama beveik kiekvienam. Tarp šios krypties darbų pažymime kandidato M.A. Sokolovskaya apie būsimų informatikos mokytojų paralelinio programavimo pagrindų mokymo metodiką ir E.Yu patirtį. Kiseleva apie CUDA technologijos įsisavinimą moksleiviams.

Šio straipsnio autoriaus teigimu, dėmesys superkompiuteriams ir lygiagrečiam programavimui gerokai nuskurdina ir apsunkina lygiagrečiojo skaičiavimo temą bei atitraukia mokinių dėmesį nuo daugelio svarbių ir prieinamų klausimų. Temos tikslas „lygiagretus

kompiuterija“ vidurinėje mokykloje – tai ne „tikro“ lygiagretaus programavimo mokymas (studijantis atitinkamas kalbos konstrukcijas, programavimo kalbas ir technologijas), o supažindinimas su atitinkamomis sąvokų rinkiniais ir paralelinio darbo ypatybių supratimas. Pasaulis aplink mus ir mūsų viduje yra sudėtinga lygiagreti sistema. Ir pati ši sistema suteikia daug medžiagos paralelizmo sąvokoms ir mechanizmams įsisavinti. Tam nereikia jokių sudėtingų dirbtinių struktūrų, tokių kaip MPI ir OpenMP technologijos. Mokyklos informatika turėtų skatinti mąstymą „lygiagrečiu būdu“. Ir tegul universitetas į šį mąstymą įtraukia profesines žinias, įgūdžius ir gebėjimus. Mokykloje prasminga orientuotis ne į superkompiuterių pažinimą ir paralelinio programavimo studijas, o į nuolat ir plačiai gyvenime naudojamų „bendros veiklos“ mechanizmų įsisavinimą. Kursas siūlo atsakyti į šiuos klausimus:

1) Kelių vykdytojų bendradarbiavimas (kasant griovį keliais duobkasiais) ir lygiagretinimas vieno vykdytojo „viduje“, esant keliems apdorojimo įrenginiams (obuolio skaitymas ir valgymas). Informatikos srityje tai bus kelių mašinų kompleksas ir kelių branduolių procesorius.

2) Lygiagretumo rūšys: tikrasis paralelizmas ir pseudoparalelizmas (vienas procesorius dalimis vykdo kelias programas).

3) To paties tipo (digeriai) ir skirtingų tipų (tanko įgula) atlikėjai.

4) To paties tipo ir skirtingų tipų kūriniai.

5) „Vykdytojų – darbų“ santykis: 1 atlikėjas – 1 darbas, 1 atlikėjas – N darbų (pseudolygiagretus vykdymas arba tikras lygiagretumas, esant keliems skirtingų darbų apdorojimo įrenginiams), N atlikėjų – 1 darbas, N atlikėjų - N darbo vietų.

6) Atlikėjų veiklos koordinavimas. Tvirtinimo tipai: pagal darbo dalis, pagal laiką, pagal veiklos rezultatus, pagal išteklius.

7) Ištekliai. Ištekliai yra bendrinami ir nebendrinami, vartojami ir pakartotinai naudojami. Sunaudotų išteklių perdirbimas („šiukšlių surinkimas“ plačiąja prasme).

8) Vieno atlikėjo ir atlikėjų grupės to paties kūrinio atlikimas. Darbo greičio priklausomybė nuo atlikėjų skaičiaus. Darbo kainos priklausomybė nuo atlikėjų skaičiaus. Netiesinis darbo greičio padidėjimas didėjant atlikėjų skaičiui. Kritinis kelias. Optimalus atlikėjų skaičius. Optimalus atlikėjų apkrovimas. Optimali procedūra. Apkrovos balansavimas.

9) Atlikėjų konkurencija dėl išteklių. Blokavimas. Clinch (aklavietė).

10) Atlikėjų veiksmų koordinavimo mechanizmai.

11) Pseudolygiagretus procesų vykdymas kompiuteryje (vieno resurso - procesoriaus padalijimas) tarp vykdytojų-procesų.

12) Algoritmų tinkamumas lygiagrečiavimui. Galimas lygiagretumo laipsnis. Algoritmų, kurių negalima lygiagretinti, buvimas.

Atkreipkite dėmesį, kad aukščiau pateiktas sąrašas atspindi privačią straipsnio autoriaus nuomonę ir yra atviras aptarimui, papildymui ir taisymui. Be to, autoriaus nuomone, „superkompiuterių bendruomenei“ būtų labai naudinga suformuluoti mokyklos „socialinę tvarką“: kokias žinias ir įgūdžius ji nori matyti abiturientuose. Kuo „superkompiuterių pasaulio“ mokyklos absolventas turėtų skirtis nuo šių dienų absolvento? Jei bus užsakymas, bus ir rezultatas. Šviežias pavyzdys. Pirmąją „Russian Supercomputing Days-2015“ dieną dviejuose pranešimuose buvo išsakyta mintis, kad šiuolaikinių superkompiuterių greitį lemia ne procesorių galia (kuri yra visuomenės dėmesio centre), o RAM greitis. Būtent tai tampa kliūtimi, kurios pralaidumas lemia visos sistemos produktyvumą. Dėl to antrąją konferencijos dieną mokytojų meistriškumo klasės dalyviai išbandė šio straipsnio autoriaus sugalvotą žaidimą, demonstruojantį centrinio procesoriaus, RAM ir talpyklos sąveiką. Medžiagos pateikimo tvarka ir forma – atviras klausimas.

Medžiaga turėtų būti demonstruojama naudojant pavyzdžius, nesusijusius su kompiuterio veikimu. Atlikėjai turi manipuliuoti materialiais objektais.

Kiek įmanoma daugiau mokymų turėtų būti verslo (organizacinių ir veiklos) žaidimų pobūdžio.

Įvykdžius šiuos reikalavimus bus lengviau suprasti tiriamą medžiagą. Tai pravers tiek naudojant šią techniką informatikos pamokose mokykloje (įskaitant pradines!), tiek mokant suaugusiuosius: informatikos mokytojus ir mokinius. Mokinys, mokyklos mokytojas, nepagrindinės specialybės studentas galės sustoti susipažinimo ir supratimo lygyje. Profesionalus studentas turės žengti kitą žingsnį ir pereiti nuo pažinties prie šių mechanizmų studijavimo profesionaliu lygiu. Bet tai jau yra žingsnis už pradinio susipažinimo su tema metodais.

Šio straipsnio autorius parengdamas lygiagrečiojo skaičiavimo studijų metodiką pradėjo 2013 m., rengdamasis TRIZformashka-2013 konkursui, ir tęsė vėlesniais metais.

(„TRIZformashka“ – tai tarpregioninis informatikos, sistemų analizės ir TRIZ interneto konkursas. Vyksta kasmet kovo antroje pusėje. Dalyvių amžius nuo pirmos klasės iki ketvirto kurso. Geografija – nuo Vladivostoko iki Rygos. Vid. dalyvių skaičius – 100 komandų (300 žmonių .), maksimalus – 202 komandos (daugiau nei 600 žmonių) Varžybų svetainė www.trizformashka.ru.) Tada, 2013 m., darbo tikslas buvo suformuluotas taip:

1. Per dvejus trejus metus parengti atlikėjų aprašymą, žaidimų ir užduočių, susijusių su lygiagrečiuoju skaičiavimu, rinkinį;

2. Pasiūlyti juos (dalimis, kasmet) konkurso dalyviams;

3. Išanalizuoti jų reakciją (įvertinti sprendėjų skaičių, amžių, sprendimo sėkmę, tipines klaidas, aptiktus uždavinių formulavimo netikslumus ir kt.). TRIZformashka konkursas pasirodė esąs patogus įrankis problemoms derinti, nes

leido gauti įvairaus amžiaus (nuo pirmos klasės iki ketvirto kurso), įvairių regionų, skirtingų ugdymo įstaigų reakcijų.

Per pastaruosius metus buvo parengtas toks metodinių priemonių ir platformų rinkinys jų testavimui.

1. Lygiagretumo užduotys nuo 2013 m. buvo įtrauktos į konkursą „TRIZformashka“ (nuo 2013 m. konkursas turi paantraštę „Paralelinis skaičiavimas“). Toliau pateikiamas užduočių tipų sąrašas;

2. Informatikos vadovėlio naujai versijai 4 klasei parengtas paralelizmo skyrius. Medžiaga išbandyta Permės 10 licėjaus 3 ir 4 klasėse;

3. Kompiuterinis žaidimas „Tank Crew“ buvo kuriamas ir naudojamas nuo 2014 metų TRIZformashka konkurse;

4. Buvo sukurta ir išbandyta daugybė žaidimų, kurie atspindi šias problemas:

Atlikėjų veiklos koordinavimas. Įvairių tipų patvirtinimai;

Atliekant tą patį kūrinį vienas atlikėjas ir atlikėjų grupė. Darbo greičio priklausomybė nuo atlikėjų skaičiaus. Netiesinis darbo greičio padidėjimas didėjant atlikėjų skaičiui. Kritinis kelias. Optimalus atlikėjų skaičius. Optimalus atlikėjų apkrovimas. Optimali procedūra;

Ištekliai. Bendri ir nebendrieji ištekliai;

Atlikėjų konkurencija dėl išteklių. Blokavimas. Clinch (aklavietė). Buvo pasiūlytos ir išbandytos šių tipų problemos:

1. Užduotys dėl patvirtinimo tipų. (Kokie koordinavimo būdai egzistuoja mokyklos valgykloje?);

2. Žaidimas „Tanko įgula“. Užduotis sukurti lygiagretųjį algoritmą;

3. Atlikėjas „Statyba“. Tuo pačiu metu darbo komandos stato konstrukciją iš horizontalių ir vertikalių sijų. Užduotys apima nurodyto algoritmo vykdymo, naujo algoritmo kūrimo, klaidų paieškos duotame algoritme, algoritmų tyrimo (konstravimo laiko palyginimas naudojant skirtingus algoritmus, statybos sąnaudų palyginimas, galimybės sutaupyti perskirstant įvertinimą). darbas ir kt.);

4. Konkurencija dėl išteklių. Trys mažos kiaulės kiekviena gamina savo pietus. Kiekvienam paršeliui nurodoma, kokius patiekalus jis gamina, kokių išteklių (įrangos, indų ir kt.) jam reikia tam ir kiek laiko šiuos išteklius naudoti. Būtina sudaryti darbo grafiką kiekvienam paršeliui, jei jis virtuvėje gamina vienas, jei gamina dviese, jei gamina visi trys iš karto. Virimo laikas turėtų būti kuo mažesnis;

5. Tinklo schema. Pateikiama tinklo schema. Reikalaujama (schemiškai) pavaizduoti statomą statinį, nustatyti, kiek dienų užtruks statybos su tam tikru brigadų skaičiumi, kokia darbų dalis bus atlikta iki tam tikro laiko;

6. Pakopinės-lygiagrečios formos. Darbų planavimas pagal įvairius kriterijus. Pateikiama darbo užduotis, darbuotojo produktyvumas ir apmokėjimo taisyklės. Būtina nustatyti darbuotojų skaičių, reikalingą darbui atlikti per tam tikrą laiką, nustatyti darbo laikotarpį tam tikram darbuotojų skaičiui, nustatyti darbuotojų skaičių, reikalingą darbo sąnaudoms sumažinti;

7. Ganto diagramos. Tekste aprašomas cecho rekonstrukcijos darbų planas: trukmė ir abipusė veiksmų seka, reikalingi darbuotojai. Būtina nustatyti objekto užbaigimo terminą, termino pasikeitimą dėl tam tikrų darbo jėgos pasikeitimų, konkrečia data dalyvaujančių darbuotojų sąrašą.

8. Pasikartojančio darbo koordinavimas. Tegul užduotis yra pagaminti prietaisų partiją per minimalų laiką, su sąlyga, kad kiekvienas įrenginys turi būti apdorojamas skirtinguose įrenginiuose, yra skirtingi kiekiai įrenginių su skirtingu našumu. Būtina planuoti kiekvienos įrangos paleidimo ir veikimo laiką bei kuo labiau sumažinti prastovos laiką.

Šiandien turime šiuos rezultatus:

1. Suformuluotas požiūris nagrinėjant „lygiagrečiojo skaičiavimo“ temą: eiti ne nuo informatikos problemų, o „iš gyvenimo“, orientuotis į „bendrą veiklą“;

2. Suformuluotas sąrašas klausimų, kuriuos siūloma atspindėti pradinėje lygiagrečiojo skaičiavimo eigoje;

3. Suformuluotos kai kurios problemų klasės. Remdamiesi sukaupta patirtimi, galite įvertinti, kokias problemas reikėtų sugalvoti;

4. Parengtas įvardintų klasių uždavinių rinkinys. Problemos buvo išbandytos TRIZformashka varžybose 2013, 2014, 2015 m. ir (arba) pradinėje mokykloje (klasėse su Permės licėjaus Nr. 10 trečių ir ketvirtų klasių mokiniais);

5. Parengtas dalykinių žaidimų rinkinys. Žaidimai buvo išbandyti pradinėse mokyklose ir daugelyje mokytojams skirtų renginių. Visų pirma, jie buvo pristatyti 2014 m. Maskvos valstybinio universiteto Vasaros superkompiuterių akademijos mokyklinėje trasoje, „Russian Supercomputing Days-2015“ mokytojų meistriškumo klasėje, keliose kitose konferencijose (įskaitant konferenciją „IT-edukation-2015“). asociacija APKIT) ir kiti renginiai informatikos mokytojams;

6. Ketvirtos klasės vadovėliui parengtas tekstų rinkinys apie lygiagretumą. Tekstai buvo išbandyti Permės licėjuje Nr. 10;

7. Parengtas kompiuterinis žaidimas „Tank Crew“. Žaidimas buvo išbandytas TRIZformashka varžybose 2014 ir 2015 m.;

8. TRIZformashka konkursas pasitvirtino kaip testavimo platforma;

9. Suformuluota „castling“ užduotis dėstant algoritmizavimą: iš karto išmokyti paralelinio programavimo, pateikiant nuoseklųjį algoritmą kaip paralelinio dalį. Kyla minčių, kaip šią idėją būtų galima įgyvendinti. Šias idėjas yra galimybė išbandyti einamaisiais mokslo metais (4-5 klasių mokiniams);

10. Yra poreikis, noras ir galimybė dirbti toliau.

Literatūra

1. Algoritmai: 5-7 klasės: Vadovėlis ir užduočių knygelė bendrajam ugdymui. ugdymo įstaigos /A.K. Zvonkinas, A.G. Kulakovas, S.K. Lando, A.L. Semenovas, A.Kh. Shen. - M.: Bustardas, 1996 m.

2. Bosova L.L. Lygiagretieji algoritmai pradinėse ir vidurinėse mokyklose. //Informatika mokykloje. 2015, Nr.2. P.24-27.

3. Voevodinas V.V. Skaičiavimo matematika ir algoritmų struktūra: 10 paskaita apie tai, kodėl sunku spręsti lygiagrečios architektūros skaičiavimo sistemų uždavinius ir kokią papildomą informaciją reikia žinoti. sėkmingai įveikti šiuos sunkumus: vadovėlis. M.: MSU leidykla 2010 m.

4. Gavrilova I.V. Pirmoji kelionė į „lygiagretųjį pasaulį“. //Informatika mokykloje. 2015, Nr.6. P.16-19.

5. Dieteris M.L., Plaksinas M.A. Lygiagretusis skaičiavimas mokyklinėje informatikoje. Žaidimas „Statyba“. //Informatika mokykloje: praeitis, dabartis ir ateitis.: Visos Rusijos medžiaga. mokslinis metodas. konf. dėl IKT naudojimo švietime, 2014 m. vasario 6-7 d. /Perm. valstybė nacionalinis tyrimai univ. - Permė, 2014. - P.258-261.

6. Ivanova N.G., Plaksin M.A., Rusakova O.L. TRIZformaška. //Kompiuterija. N05 Gauta 2015-10-10.

14. Plaksin M.A. Informatika: vadovėlis 4 klasei: 2 val. / M.A.Plaksin, N.G.Ivanova, O.L.Rusakova. - M.: BINOM. Žinių laboratorija, 2012 m.

15. Plaksin M.A. Apie pradinės pažinties su lygiagrečiuoju skaičiavimu metodą vidurinėje mokykloje. //Informatika mokykloje: praeitis, dabartis ir ateitis.: Visos Rusijos medžiaga. mokslinis metodas. konf. dėl IKT naudojimo švietime, 2014 m. vasario 6-7 d. /Perm. valstybė nacionalinis tyrimai univ. - Permė, 2014. - P.256-258.

16. Plaksin M.A. Verslo žaidimų rinkinys, skirtas supažindinti su lygiagrečiuoju skaičiavimu pradinėje mokykloje. //Informacinių technologijų mokymas Rusijos Federacijoje: tryliktosios atviros visos Rusijos konferencijos „IT-0education-2015“ (Permė, 2015 m. gegužės 14-15 d.) medžiaga. Permės valstybinis nacionalinis tyrimų universitetas, - Permė, 2015. P.60-62.

17. Plaksin M.A., Ivanova N.G., Rusakova O.L. Užduočių rinkinys, skirtas susipažinti su lygiagrečiuoju skaičiavimu konkurse TRIZformashka. //Informacinių technologijų mokymas Rusijos Federacijoje: tryliktosios atviros visos Rusijos konferencijos „IT švietimas-2015“ (Permė, 2015 m. gegužės 14-15 d.) medžiaga. Permės valstybinis nacionalinis tyrimų universitetas, - Permė, 2015. 232-234 p.

18. Sokolovskaya M.A. Būsimiems informatikos mokytojams paralelinio programavimo pagrindų mokymo metodinė sistema.: santrauka. dis. ...kand. ped. Mokslai, Krasnojarskas, 2012 m.

Lygiagretaus skaičiavimo samprata

LYGIALINIO SKAIČIAVIMO PAGRINDAI

Paskaita Nr.6

Pagal lygiagrečiai arba lygiagrečiai skaičiavimai galite suprasti problemų sprendimo procesus, kuriuose vienu metu galima atlikti kelias skaičiavimo operacijas

Lygiagretusis skaičiavimas sudaro superkompiuterių technologijų ir didelio našumo skaičiavimo pagrindą

Lygiagretus apdorojimas

Jei tam tikras įrenginys per laiko vienetą atlieka vieną operaciją, tai jis atliks tūkstantį operacijų per tūkstantį vienetų. Jei darysime prielaidą, kad yra penki identiški nepriklausomi įrenginiai, galintys veikti vienu metu, tai penkių įrenginių sistema tą patį tūkstantį operacijų gali atlikti ne per tūkstantį, o per du šimtus laiko vienetų.

Panašiai N įrenginių sistema tą patį darbą atliks per 1000/N laiko vienetų. Panašių analogijų galima rasti ir gyvenime: jei vienas kareivis iškasa sodą per 10 valandų, tai penkiasdešimties karių, turinčių tuos pačius sugebėjimus, kuopa, dirbanti vienu metu, su tuo pačiu darbu susidoros per 12 minučių – paralelizmo principas veikiant!

Lygiagretaus duomenų srautų apdorojimo pradininkas buvo akademikas A. A. Samarsky, atlikęs skaičiavimus, reikalingus branduoliniams sprogimams imituoti šeštojo dešimtmečio pradžioje. Samarskis išsprendė šią problemą, prie stalų susodindamas kelias dešimtis jaunų damų su mašinomis. Jaunos ponios duomenis viena kitai perdavė tiesiog žodžiais ir surašydamos reikiamus skaičius surašydamos sudėjimo mašinas. Taigi, visų pirma, buvo apskaičiuota sprogimo bangos raida.

Buvo daug darbo, jaunos ponios buvo pavargusios, o Aleksandras Andrejevičius vaikščiojo tarp jų ir skatino. Tai, galima sakyti, buvo pirmoji paralelinė sistema. Nors vandenilinės bombos skaičiavimai buvo atlikti meistriškai, jų tikslumas buvo labai mažas, nes naudojamame tinklelyje mazgų, o skaičiavimo laikas buvo per ilgas.

Konvejerio apdirbimas

Dujotiekio apdorojimo idėja yra atskirti atskirus bendrosios operacijos atlikimo etapus, o kiekvienas etapas, baigęs savo darbą, perduotų rezultatą kitam, kartu gaudamas naują įvesties duomenų dalį. Sujungdami anksčiau atliktas operacijas, gauname akivaizdų apdorojimo greičio padidėjimą.

Tarkime, kad operacijoje yra penkios mikrooperacijos, kurių kiekviena atliekama per vieną laiko vienetą. Jei yra vienas nedalomas serijinis įrenginys, jis apdoros 100 argumentų porų 500 vienetų. Jei kiekviena mikrooperacija yra atskirta į atskirą konvejerio įrenginio etapą (arba kitaip vadinamą etapą), tai penktame laiko vienete, skirtinguose tokio įrenginio apdorojimo etapuose, bus išdėstytos pirmosios penkios argumentų poros. , o visas šimto porų rinkinys bus apdorotas per 5 + 99 = 104 laiko vienetus – pagreitis lyginant su serijiniu įrenginiu yra beveik penkis kartus (pagal konvejerio etapų skaičių).

Lygiagrečių kompiuterių modeliai (Flynn klasifikacija)

· „Vienas komandų srautas – vienas duomenų srautas“ (SISD – „Single Instruction Single Data“)

Nurodo von Neumann architektūrą. SISD kompiuteriai yra įprasti, „tradiciniai“ nuoseklūs kompiuteriai, kuriuose vienu duomenų elementu (skaitine ar kita reikšme) vienu metu atliekama tik viena operacija. Dauguma šiuolaikinių asmeninių kompiuterių patenka į šią kategoriją.

· „Vienas komandų srautas – daug duomenų srautų“ (SIMD – „Viena instrukcija – keli duomenys“)

SIMD (viena instrukcija, keli duomenys)- kompiuterinio skaičiavimo principas, leidžiantis duomenų lygiu lygiagretumą. SIMD kompiuteriai susideda iš vieno komandų procesoriaus (valdymo modulio), vadinamo valdikliu, ir kelių duomenų apdorojimo modulių, vadinamų apdorojimo elementais. Valdymo modulis priima, analizuoja ir vykdo komandas.

Jei komandoje aptinkami duomenys, valdiklis siunčia komandą visiems procesoriaus elementams ir ši komanda vykdoma keliuose arba visuose procesoriaus elementuose. Kiekvienas apdorojimo elementas turi savo atmintį duomenims saugoti. Vienas iš šios architektūros privalumų yra tas, kad tokiu atveju skaičiavimo logika įgyvendinama efektyviau. SIMD procesoriai taip pat vadinami vektoriniais procesoriais.

· „Daugelis komandų srautų – vienas duomenų srautas“ (MISD – „Keli nurodymai – vieni duomenys“)

Šios klasės kompiuterių praktiškai nėra ir sunku pateikti sėkmingo jų įgyvendinimo pavyzdį. Vienas iš nedaugelio – sistolinis procesorių masyvas, kuriame procesoriai išsidėstę taisyklingos gardelės mazguose, kurių kraštinių vaidmenį atlieka tarpprocesorinės jungtys. Visus procesoriaus elementus valdo bendras laikrodžio generatorius. Kiekviename darbo cikle kiekvienas apdorojimo elementas gauna duomenis iš savo kaimynų, įvykdo vieną komandą ir perduoda rezultatą savo kaimynams.

Vadinami PE masyvai su tiesioginiais ryšiais tarp netoliese esančių PE sistolinis. Tokie masyvai yra itin efektyvūs, tačiau kiekvienas iš jų yra orientuotas į labai siauros klasės problemų sprendimą. Panagrinėkime, kaip sukurti sistolinį masyvą, kad išspręstumėte tam tikrą problemą. Pavyzdžiui, leiskite sukurti įrenginį, skirtą matricai apskaičiuoti D=C+AB, Kur

Čia visos matricos yra eilės juostos matricos n. Matrica A turi vieną įstrižainę aukščiau ir dvi įstrižaines žemiau pagrindinės; matrica B- viena įstrižainė žemiau ir dvi įstrižainės virš pagrindinės; matrica C trys įstrižainės virš ir žemiau pagrindinės. Tegul kiekvienas PE gali atlikti skaliarinę operaciją c+ab ir tuo pačiu metu perduoti duomenis. Todėl kiekvienas PE turi turėti tris įvestis: a, b, c ir trys išėjimai: a, b, c. Įvestis ( in) ir savaitgaliais ( išeiti) duomenys yra susieti ryšiais

a out = a in , b out = b in , c out = c in + a in *b in ;

Jei operacijos metu kai kurie duomenys nebuvo gauti, tada manysime, kad jie yra apibrėžti kaip nuliai. Darykime prielaidą, kad visi PE yra plokštumoje ir kiekvienas iš jų yra prijungtas prie šešių gretimų. Jei sudėliosite duomenis taip, kaip parodyta paveikslėlyje, grandinė apskaičiuos matricą D.

Masyvas veikia laikrodžio ciklais. Per kiekvieną laikrodžio ciklą visi duomenys perkeliami į gretimus mazgus rodyklėmis nurodytomis kryptimis.

Paveikslėlyje parodyta sistolinio masyvo būsena tam tikru momentu. Kito laikrodžio ciklo metu visi duomenys bus perkelti į vieną mazgą ir elementus a11, b11, c11 atsidurs vienoje PE, esančioje punktyrinių linijų sankirtoje. Todėl išraiška bus įvertinta c11+a11b11.Tuo pačiu laikrodžiu, duomenys a12 Ir b21 bus labai arti PE, esančio sistolinio masyvo viršuje.

Kito laikrodžio ciklo metu visi duomenys vėl perkels vieną mazgą rodyklių kryptimi ir bus rodomi viršutiniame PE. a12 Ir b21 ir žemiau esančios PE ankstesnės operacijos rezultatas, t.y. c11+a11b11. Todėl išraiška bus įvertinta c11+a11b11+a12b21. Tai yra elementas d11 matricos D.

Tęsdami nuoseklų proceso tyrimą, galime įsitikinti, kad PE išėjimuose, atitinkančiuose viršutinę sistolinio masyvo ribą, matricos elementai periodiškai išvedami po trijų žingsnių. D, o tos pačios įstrižainės elementai rodomi kiekviename išvestyje. Maždaug 3n ciklų, bus baigtas visos matricos skaičiavimas D. Šiuo atveju kiekvienos sistolinės ląstelės apkrova yra asimptotiškai vienoda 1/3 .

„Daugelis komandų srautų – daug duomenų srautų“ (MIMD – „Keli nurodymai – keli duomenys“)

Ši kompiuterių architektūros kategorija yra turtingiausia, jei turėkite omenyje sėkmingo jos įgyvendinimo pavyzdžius. Tai apima simetrišką lygiagrečios skaičiavimo sistemos, darbo vietos su daugybe procesoriai, darbo stočių klasteriai ir kt.

Didžiulį lygiagrečių kompiuterių ir superkompiuterių našumą daugiau nei kompensuoja jų naudojimo sunkumai. Pradėkime nuo paprasčiausių dalykų. Jūs turite programą ir prieigą prie, tarkime, 256 procesorių kompiuterio. ko tikitės? Taip, aišku: jūs visiškai teisėtai tikitės, kad programa veiks 256 kartus greičiau nei viename procesoriuje. Tačiau greičiausiai taip neatsitiks.

Lygiagretusis skaičiavimas – tai kompiuterinio skaičiavimo organizavimo būdas, kai programos kuriamos kaip sąveikaujančių skaičiavimo procesų, veikiančių vienu metu, rinkinys.

Lygiagrečiam skaičiavimui įgyvendinti yra įvairių būdų: kiekvienas skaičiavimo procesas gali būti įgyvendintas kaip operacinės sistemos procesas arba skaičiavimo procesai gali būti viename procese vykdomų gijų rinkinys. Gija (arba tiksliau vykdymo gija) yra mažiausias apdorojimo vienetas, kurio vykdymą gali priskirti operacinės sistemos branduolys. Tame pačiame procese gali egzistuoti kelios vykdymo gijos ir dalytis ištekliais, pvz., atmintimi, o procesai šių išteklių nesidalija. Lygiagrečios programos gali būti fiziškai vykdomos arba nuosekliai viename procesoriuje – paeiliui keičiant kiekvieno skaičiavimo proceso žingsnius, arba lygiagrečiai – kiekvienam skaičiavimo procesui priskiriant vieną ar daugiau procesorių (esančių šalia arba paskirstytų kompiuterių tinkle).

Pagrindinis iššūkis kuriant lygiagrečias programas yra užtikrinti teisingą skirtingų skaičiavimo procesų sąveikų seką, taip pat dalintis ištekliais, tokiais kaip RAM ar išoriniai įrenginiai.

Kai kuriose lygiagrečiojo programavimo sistemose duomenų perdavimas tarp komponentų yra paslėptas nuo programuotojo, o kitose jis turi būti aiškiai nurodytas. Aiškios sąveikos gali būti suskirstytos į du tipus:

1. Sąveika per bendrą atmintį (pavyzdžiui, Java arba C#). Šio tipo lygiagrečiam programavimui paprastai reikia tam tikros formos valdymo fiksavimo, kad būtų suderintos gijos tarpusavyje.

2. Sąveika perduodant pranešimą. Pranešimais galima keistis asinchroniškai arba naudojant pasimatymo metodą, kai siuntėjas blokuojamas, kol jo žinutė bus pristatyta. Asinchroninis pranešimų perdavimas gali būti patikimas (su pristatymo garantija) arba nepatikimas. Pranešimus perduodančios lygiagrečios sistemos dažnai yra lengviau suprantamos nei bendros atminties sistemos ir paprastai laikomos geresniu lygiagretaus programavimo metodu. Pranešimų siuntimas gali būti efektyviai įgyvendintas simetriniuose daugiaprocesoriuose su bendra nuoseklia atmintimi arba be jos.

Yra nemažai skirtingų lygiagretaus programavimo technologijų. Be to, šios technologijos skiriasi ne tiek programavimo kalbomis, kiek architektūriniais metodais kuriant lygiagrečias sistemas. Pavyzdžiui, kai kurios technologijos apima lygiagrečių sprendimų konstravimą, pagrįstą keliais kompiuteriais (tiek to paties, tiek skirtingų tipų), o kitose – dirbama vienoje mašinoje su keliais procesoriaus branduoliais. Šiuo metu pagrindiniai programinės įrangos įrankiai lygiagrečioms programoms kurti yra šie:

1. OpenMP naudojamas lygiagrečiose sistemose su bendra atmintimi (pavyzdžiui, šiuolaikiniuose kompiuteriuose su kelių branduolių procesoriais);

2. MPI (pranešimo perdavimo sąsaja) yra pranešimų perdavimo sistemų tarp lygiagrečiai vykdančių procesų standartas, naudojamas kuriant programas superkompiuteriams;

3. POSIX siūlai yra vykdymo gijų diegimo standartas;

4. „Windows“ operacinė sistema turi integruotą daugiasriegių programų palaikymą C++ API lygiu;

5. PVM (lygiagreti virtuali mašina) leidžia sujungti nevienalyčius kompiuterius, sujungtus tinklu, į bendrą skaičiavimo šaltinį.

Sistemos, pagrįstos keliais kompiuteriais, priskiriamos paskirstytojo skaičiavimo sistemoms. Tokie sprendimai naudojami gana ilgą laiką. Ryškiausias paskirstytos skaičiavimo technologijos pavyzdys yra MPI (Message Passing Interface). MPI yra labiausiai paplitęs lygiagretaus programavimo duomenų mainų sąsajos standartas; yra įdiegimų daugybei kompiuterių platformų. MPI suteikia programuotojui vieningą šakų sąveikos mechanizmą lygiagrečioje programoje, neatsižvelgiant į mašinos architektūrą (vieno procesoriaus / kelių procesorių su bendra / atskira atmintimi), santykinę šakų vietą (tame pačiame procesoriuje arba skirtinguose).

Kadangi MPI visų pirma skirtas sistemoms su bendra atmintimi, jį naudoti norint organizuoti lygiagretų procesą sistemoje su bendra atmintimi yra labai sunku ir nepraktiška. Tačiau niekas netrukdo jums sukurti MPI sprendimų vienai mašinai.

Tačiau lygiagrečios programavimo sistemos, skirtos darbui vienoje mašinoje, pradėtos kurti palyginti neseniai. Žinoma, tai nėra iš esmės naujos idėjos, tačiau būtent asmeninių kompiuterių ir mobiliųjų įrenginių rinkoje atsiradus kelių branduolių sistemoms, tokios technologijos kaip OpenMP buvo smarkiai išplėtotos.

Labai svarbu, kad lygiagretaus programavimo technologija palaikytų galimybę palaipsniui paversti lygiagrečią programą. Žinoma, idealią paralelinę programą iš karto reikėtų parašyti lygiagrečiai, galbūt kokia nors funkcine kalba, kur lygiagretinimo klausimas visai nekyla. Tačiau praktiškai, norint padidinti našumą, būtina palaipsniui lygiagretinti rašytinį nuoseklųjį. Tokiu atveju OpenMP technologija bus labai geras pasirinkimas. Tai leidžia pasirinkti programos vietas, kurioms labiausiai reikia lygiagretinimo, ir pirmiausia padaryti jas lygiagrečias. Lygiagretus versijų kūrimo procesas gali būti nutrauktas, tarpinės programos versijos išleistos ir prireikus grąžintos. Štai kodėl ypač išpopuliarėjo OpenMP technologija.

OpenMP (Open Multi-Processing) yra kompiliatoriaus direktyvų, bibliotekos procedūrų ir aplinkos kintamųjų rinkinys, skirtas programuoti daugiagijas programas bendros atminties kelių procesorių sistemose.

OpenMP specifikaciją kuria keli pagrindiniai techninės ir programinės įrangos gamintojai, kurių darbą reguliuoja ne pelno organizacija, vadinama OpenMP Architecture Review Board (ARB).

Pirmoji versija pasirodė 1997 m., skirta Fortran kalbai. C/C++ versija buvo sukurta 1998 m. 2008 m. buvo išleista OpenMP 3.0. OpenMP sąsaja tapo viena populiariausių lygiagretaus programavimo technologijų. OpenMP sėkmingai naudojamas tiek programuojant superkompiuterines sistemas su daugybe procesorių, tiek stalinių kompiuterių vartotojų sistemose arba, pavyzdžiui, Xbox 360.

„OpenMP“ įgyvendina lygiagretųjį skaičiavimą, naudodamas daugiagiją, kai „pagrindinė“ gija sukuria pagalbinių gijų rinkinį ir užduotis paskirstoma tarp jų. Manoma, kad gijos vykdomos lygiagrečiai mašinoje su keliais procesoriais (procesorių skaičius neturi būti didesnis arba lygus gijų skaičiui).

Lygiagrečiai gijų atliekamos užduotys, taip pat šioms užduotims atlikti reikalingi duomenys aprašomi naudojant specialias atitinkamos kalbos išankstinio procesoriaus direktyvas – pragmas. Pavyzdžiui, prieš Fortran kodo sekciją, kurią turi vykdyti kelios gijos, kurių kiekviena turi savo kintamojo N kopiją, yra prieš šią direktyvą: !$OMP PARALLEL PRIVATE(N)

Sukurtų gijų skaičių galima reguliuoti tiek pačia programa, iškviečiant bibliotekos procedūras, tiek išoriškai, naudojant aplinkos kintamuosius.

Pagrindiniai OpenMP elementai yra

1. konstruktai gijų kūrimui (lygiagreti direktyva);

2. konstrukcijos, skirtos paskirstyti darbą tarp sriegių (DO/už ir skyriaus direktyvos);

3. konstruktai, skirti valdyti darbą su duomenimis (bendrosios ir privačios išraiškos kintamųjų atminties klasei apibrėžti);

4. gijų sinchronizavimo konstrukcijos (kritinės, atominės ir barjerinės direktyvos);

5. vykdymo palaikymo bibliotekos procedūros (pavyzdžiui, omp_get_thread_num);

6. aplinkos kintamieji (pvz., OMP_NUM_THREADS).

OpenMP naudoja atšakų sujungimo lygiagrečiojo vykdymo modelį. OpenMP programa prasideda kaip viena vykdymo gija, vadinama pradine gija. Kai gija susiduria su lygiagrečia konstrukcija, ji sukuria naują gijų grupę, susidedančią iš jos pačios ir kelių papildomų gijų, ir tampa naujos grupės šeimininku. Visi naujos grupės nariai (įskaitant pagrindinę grupę) vykdo kodą lygiagrečios konstrukcijos viduje. Lygiagrečios struktūros gale yra numanomas barjeras. Po lygiagrečios konstrukcijos tik pagrindinė gija toliau vykdo vartotojo kodą. Lygiagreti sritis gali būti įdėta į kitas lygiagrečias sritis, kuriose kiekviena pradinės srities gija tampa pagrindine savo gijų grupės gija. Įdėti regionai savo ruožtu gali apimti regionus, esančius gilesniame lizdų lygyje.

Lygiagrečiai veikiančios grupės gijų skaičių galima valdyti keliais būdais. Vienas iš jų naudoja OMP_NUM_THREADS aplinkos kintamąjį. Kitas būdas yra iškviesti omp_set_num_threads() procedūrą. Kitas būdas yra naudoti num_threads išraišką kartu su lygiagrečia direktyva.

Šioje programoje du masyvai (a ir b) pridedami lygiagrečiai dešimčia gijų.

#įtraukti

int main(int argc, char *argv)

plūduriuoti a[N], b[N], c[N];

omp_set_dynamic(0); // neleisti openmp bibliotekai keisti gijų skaičiaus vykdymo metu

omp_set_num_threads(10); // nustatykite gijų skaičių į 10

// inicijuokite masyvus

už (I = 0; I< N; i++)

// apskaičiuokite masyvų sumą

#pragma omp lygiagrečiai bendrinamas(a, b, c) privatus(i)

už (I = 0; I< N; i++)

c[i] = a[i] + b[i];

printf("%f\n", c);

Šią programą galima sudaryti naudojant gcc-4.4 ir naujesnę versiją su –fopenmp vėliava. Akivaizdu, kad jei pašalinsite omp.h antraštės failo įtraukimą, taip pat OpenMP konfigūracijos funkcijos iškvietimus, programa gali būti sukompiliuota bet kuriame C kompiliatoriuje kaip įprasta nuosekli programa.

OpenMP palaiko daugelis šiuolaikinių kompiliatorių:

1. Sun Studio kompiliatoriai palaiko oficialią specifikaciją – OpenMP 2.5 – su pagerintu našumu naudojant Solaris OS; Kitame leidime planuojamas Linux palaikymas.

2. Visual C++ 2005 ir naujesnės versijos palaiko OpenMP Professional ir Team System leidimuose.

3. GCC 4.2 palaiko OpenMP, o kai kurie platinimai (pvz., Fedora Core 5 gcc) įtraukė palaikymą į savo GCC 4.1 versijas.

4. Intel C++ Compiler, įskaitant Intel Cluster OpenMP versiją, skirtą programavimui paskirstytose atminties sistemose.

Pranešimų perdavimo sąsaja (MPI pranešimų perdavimo sąsaja) yra informacijos perdavimo programavimo sąsaja (API), kuri leidžia keistis pranešimais tarp procesų, atliekančių tą pačią užduotį. Sukūrė William Group, Evin Lusk ir kiti.

MPI yra labiausiai paplitęs duomenų mainų sąsajos standartas lygiagrečiam programavimui, ir yra įdiegimų daugybei kompiuterių platformų. Naudojamas kuriant programas, skirtas klasteriams ir superkompiuteriams. Pagrindinė MPI procesų komunikacijos priemonė yra pranešimų perdavimas vienas kitam. MPI standartizavimą vykdo MPI forumas. MPI standartas apibūdina pranešimų perdavimo sąsają, kuri turi būti palaikoma tiek platformoje, tiek vartotojo programose. Šiuo metu yra daug nemokamų ir komercinių MPI diegimų. Yra įdiegimų Fortran 77/90, C ir C++ kalboms.

MPI pirmiausia orientuotas į sistemas su paskirstyta atmintimi, tai yra, kai duomenų perdavimo išlaidos yra didelės, o OpenMP - į sistemas su bendra atmintimi (keli branduoliai su bendru ESH). Abi technologijos gali būti naudojamos kartu, siekiant optimaliai panaudoti kelių branduolių sistemas klasteryje.

Pirmoji MPI versija buvo sukurta 1993–1994 m., o MPI 1 buvo išleista 1994 m.

Dauguma šiuolaikinių MPI diegimų palaiko 1.1 versiją. MPI standartinę 2.0 versiją palaiko dauguma šiuolaikinių diegimų, tačiau kai kurios funkcijos gali būti neįgyvendintos iki galo.

pranešimų siuntimas ir gavimas tarp atskirų procesų;

kolektyvinės procesų sąveikos;

sąveikos proceso grupėse;

procesų topologijų diegimas;

dinamiškas procesų generavimas ir procesų valdymas;

vienpusis ryšys (Get/Put);

lygiagretus įėjimas ir išėjimas;

išplėstinės kolektyvinės operacijos (procesai gali atlikti kolektyvines operacijas ne tik viename komunikatoriuje, bet ir keliuose komunikatoriuose).

MPI 2.1 versija buvo išleista 2008 m. rugsėjo pradžioje.

Pagrindinis ryšio tarp MPI procesų mechanizmas yra pranešimų perdavimas ir priėmimas. Pranešime yra perduoti duomenys ir informacija, leidžianti gaunančiajai šaliai pasirinktinai juos gauti:

1. siuntėjas - žinutės siuntėjo rangas (skaičius grupėje);

2. recipientas – gavėjo rangas;

3. ženklas – gali būti naudojamas atskirti įvairių tipų pranešimus;

4. komunikatorius – procesų grupės kodas.

Priėmimo ir perdavimo operacijos gali būti blokuojamos arba neblokuojamos. Neblokuojančioms operacijoms apibrėžiamos funkcijos, skirtos patikrinti pasirengimą ir laukti, kol operacija bus baigta.

Kitas ryšio būdas yra nuotolinė prieiga prie atminties (RMA), leidžianti nuskaityti ir modifikuoti nuotolinio proceso atminties sritį. Vietinis procesas gali perkelti nuotolinio proceso atminties sritį (procesų nurodytame lange) į savo atmintį ir atgal, taip pat sujungti į nuotolinį procesą perkeltus duomenis su jo atmintyje turimais duomenimis (pavyzdžiui, sumuojant). ). Visos nuotolinės atminties prieigos operacijos yra neblokuojančios, tačiau blokuojančios sinchronizavimo funkcijos turi būti iškviestos prieš ir po jų vykdymo.

Žemiau pateikiamas pavyzdys, skirtas π skaičiavimui C naudojant MPI:

// Reikiamų antraščių prijungimas

#įtraukti

// Įtraukti MPI antraštės failą

#include "mpi.h"

// Tarpinių skaičiavimų funkcija

dvigubas f (dvigubas a)

grąžinti (4,0 / (1,0+ a*a));

// Pagrindinė programos funkcija

int main (int argc, char **argv)

// Kintamųjų deklaravimas

int padaryta = 0, n, myid, numprokas, I;

dvigubas PI25DT = 3,141592653589793238462643;

dvigubas mypi, pi, h, suma, x;

dvigubas pradžios laikas = 0,0, pabaigos laikas;

char procesoriaus_pavadinimas;

// Inicijuoti MPI posistemį

MPI_Init(&argc, &argv);

// Gaukite komunikatoriaus MPI_COMM_WORLD dydį

// (bendras procesų skaičius užduotyje)

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

// Gaukite dabartinio proceso numerį

// komunikatorius MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(procesoriaus_pavadinimas,&namelen);

// Rodyti gijos numerį bendrame telkinyje

fprintf(stdout, "Procesas %d iš %d yra %s\n", myid,numprocs,procesoriaus_pavadinimas);

// intervalų skaičius

fprintf(stdout, "Įveskite intervalų skaičių: (0 quits)");

if(scanf("%d",&n) != 1)

fprintf(stdout, „Neįvestas numeris; išjungiamas\n“);

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1,0 / (dvigubas) n;

// Apskaičiuokite procesui priskirtą tašką

for(I = myid + 1 ; (I<= n) ; I += numprocs)

x = h * ((dvigubas)I – 0,5);

// Iš naujo nustatykite visų procesų rezultatus ir pridėkite

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

// Jei tai yra pagrindinis procesas, išveskite rezultatą

printf ("PI yra maždaug %.16f, klaida yra %.16f\n", pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf ("sieninio laikrodžio laikas = %f\n", pabaigos laikas-pradžios laikas);

// Atleiskite MPI posistemį

Šiandien dažniausiai naudojami MPI diegimai:

MPICH yra labiausiai paplitęs nemokamas diegimas, veikia UNIX sistemose ir Windows NT

LAM/MPI yra dar vienas nemokamas MPI diegimas. Palaiko nevienalytes konfigūracijas, LAM (http://www.lam-mpi.org) palaiko nevienalytes konfigūracijas, Globus paketą ir tenkina IMPI (interoperable MPI).

Palaikomos įvairios ryšio sistemos (įskaitant Myrinet).

WMPI – MPI diegimas, skirtas „Windows“.

MPI/PRO, skirtas Windows NT – komercinis diegimas, skirtas Windows NT

Intel MPI – komercinis diegimas, skirtas Windows/Linux

Microsoft MPI yra įtrauktas į Compute Cluster Pack SDK. Remiantis MPICH2, bet apima papildomas darbo valdymo galimybes. MPI-2 specifikacija palaikoma.

HP-MPI – komercinis HP diegimas

SGI MPT – mokama SGI MPI biblioteka

Mvapich – nemokamas MPI diegimas, skirtas Infiniband

Open MPI – nemokamas MPI diegimas, LAM/MPI įpėdinis

Oracle HPC ClusterTools – nemokamas Solaris SPARC/x86 ir Linux diegimas, pagrįstas Open MPI

MPJ – MPI, skirta Java

POSIX siūlai- POSIX standartas, skirtas diegti vykdymo gijas, apibrėžti API joms kurti ir valdyti.

Bibliotekos, kurios įgyvendina šį standartą (ir šio standarto funkcijas), paprastai vadinamos Pthreads (prie funkcijos yra „pthread_“). Nors geriausiai žinomos parinktys skirtos „Unix“ tipo operacinėms sistemoms, tokioms kaip „Linux“ ar „Solaris“, yra įdiegta ir „Microsoft Windows“ (Pthreads-w32).

Pthreads apibrėžia tipų ir funkcijų rinkinį C programavimo kalba. Antraštės failas yra pthread.h.

Duomenų tipai:

1. pthread_t – gijos aprašas;

2. pthread_attr_t – gijos atributų sąrašas.

Siūlų valdymo funkcijos:

1. pthread_create() – gijos kūrimas;

2. pthread_exit() – gijos pabaiga (nutraukus turi būti iškviesta gijos funkcijos);

3. pthread_cancel() – atšaukti giją;

4. pthread_join() – blokuoja gijos vykdymą, kol nutrūks kita funkcijos iškvietime nurodyta gija;

5. pthread_detach() – atlaisvinkite gijos užimtus resursus (jei gija veikia, resursai bus atlaisvinti jai pasibaigus);

6. pthread_attr_init() – inicijuoja gijos atributo struktūrą;

7. pthread_attr_setdetachstate() – nurodykite sistemai, kad pasibaigus gijai, ji gali automatiškai išleisti gijos užimtus resursus;

8. pthread_attr_destroy() – atlaisvinkite atmintį iš gijos atributo struktūros (sunaikinkite deskriptorių).

Gijų sinchronizavimo funkcijos:

2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();

3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().

Gijų naudojimo C programoje pavyzdys:

#įtraukti

statinis void laukti_sriegis(tuščia)

laikas_t pradžios_laikas = laikas (NULL);

while (laikas (NULL) == pradžios_laikas)

/* nedarykite nieko, išskyrus procesoriaus gabalėlių kramtymą iki vienos sekundės. */

static void *thread_func(void *vptr_args)

už (I = 0; I< 20; i++)

fputs ("b\n", stderr);

pthread_t gija;

if (pthread_create(&gija, NULL, gijos_funkcija, NULL) != 0)

grąžinti EXIT_FAILURE;

už (I = 0; I< 20; i++)

if (pthread_join(gija, NULL) != 0)

grąžinti EXIT_FAILURE;

grąžinti EXIT_SUCCESS;

Pateiktoje programoje naudojamos dvi gijos, kurios spausdina pranešimus į konsolę, viena spausdina "a", antra - "b". Pranešimų išvestis sumaišoma dėl vykdymo perjungimo tarp gijų arba vienu metu vykdomo kelių procesorių sistemose.

C programa sukuria vieną naują giją, kad išspausdintų "b", o pagrindinė gija atspausdina "a". Pagrindinė gija (atspausdinus „aaaaa...“) laukia, kol baigsis antrinė gija.

Kontroliniai klausimai

Kas yra lygiagreti programa?
Kuo procesas skiriasi nuo vykdymo gijos?
Ar programa gali sukurti 5 gijas, kai ji veikia keturių branduolių procesoriuje?
Kokios yra bendros atminties lygiagrečių programų funkcijos?
Kokios programinės įrangos priemonės egzistuoja lygiagrečioms programoms kurti?
Kodėl kuriant programas kompiuteriams plačiai paplito OpenMP, o ne, pavyzdžiui, MPI?