Параллелизм. Программалау модельдері

Деректер параллелизмі мен есептер параллелизмі

Қазіргі заманғы бірпроцессорлы машина бірнеше компоненттен тұратын белгілі.

Бірпроцессорлы машина.

  • орталық процессор (CPU);
  • алғашқы жады;
  • бір және бірнеше деңгейдегі кэш-жады;
  • екінші жады (дискідегі жады);
  • әртүрлі сыртқы құрылғылар.

Программаның орындауына қатысты түйінді компоненттер: орталық процессор, кэш және жады.

Бірпроцессордың архитектурасын жақсартудың әртүрлі әдістері бар:

  1. орталық процессордың бір ішкі бөлігінің орнына қосындаушы (көбейткіштердің) төрт модулін қолдану;
  2. өткізу жолағын үлкейту үшін орталық процессорға екі немесе бірнеше жады блогын қосу;
  3. уақыт өлшемінде орындалатынкомандалар санын үлкейту үшін бір жадының бір немесе бірнеше процессорды қосу;
  4. барлық компьютерлердің жұмысы бірге бір ғана программаны шешуге бағытталатыңдай толық компьютерді (процессор, жады және енгізу-шығару құрылғысын қосу) машина желісіне қосу;

 Параллелизм

Параллелизм әр түрлі деңгейде топталуы мүмкін:

  • тапсырма деңгейіндегі параллелизм;
  • программа деңгейіндегі параллелизм;
  • команда деңгейіндегі параллелизм;
  • арифметикалық және биттік туралайтын параллелизм.

Тапсырма деңгейіндегі параллелизм – параллелизмнің жоғарғы деңгейі.

Мысалы, лаборатория немесе компьютер орталығы берілген уақыт аралығында көптеген есептердіорындайды. Оған үлкен компьютерлік желілерді сатып алу арқылы жетуге болады, кез – келген уақытта көп тапсырма орындалады, және қолданушының кез-келген тапсырмасы басқаларға қарағанда тез орындалмайды.

Тапсырма деңгейіндегі параллелизм бір компьютер шегінде бір тапсырманы немесе бірнеше тапсырманың тәуелсіз есептер жиынтығы ретінде өңдей отырып қолданылады. Орталық процессор және енгізу – шығару жүйелері параллель жұмыс і стейді.

Берілген параллелизм түрінің мысалы: біруақытта жадыда бірнеше тапсырма болады, сонымен қатар кез – келген берілген уақытта олардың тек біреуі орындалады. Егер бұл тапсырма енгізу – шығару немесе дискіден оқу типті қызметті қажет етсе, онда амал инициалданады, жоғарыдағы қызметтің бірін қажет еткен тапсырма тоқтатылып, басқа тапсырма орындау күйіне орналастырылады. Ары қарай, енгізу – шығару амалы аяқталғаннан кейін, басқару кері алғашқы тапсырмаға оралып, орындалу жалғасады.

Программаның деңгейіндегі параллелизм

Программа деңгейіндегі параллелизмде пбір программа бөліктерге, оның құраушыларына бөлінеді.

Мысалы, матрицалардың көбейтіндісі: С=AxB матрицаларды квадраттарға бөлужолымен есептеледі:

В11 В12
В21 В22
А11 А12
А21 А22

С11
X
=

С12

 С21 С22

Жалпы, программа деңгейіндегі параллелизм екі әдіспен көрінеді:

  • берілген программаның тәуелсіз бөліктердеге бөлу;
  • итерациялар арасында ешқандай байланыс жоқ циклің жеке итерацияларын қолдану.

Параллелизмнің бұл түрін процессорлар жиынтығы немесе функциональды модулдер жиынтығын қолдануы мүмкін.

Программа деңегейіндегі параллелизмнің көруінуінің қарапайым мысалы: қосындыларын есептеу. Төменде екі массив элементтерінің қосындысын есептеу коды көрсетілген:

for(i=0; i<N; i++)

A[i]=B[i]+C[i]

Қосындылар тәуелсіз, яғни B[i]+C[i] есептеуі B[i]+C[i]-ге тәуелсіз, кез – келген j<i үшін.

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

Команда деңгейіндегі параллелизм

Программаның деңгейіндегі параллелизм – архетектураның төменгі деңгейі және компьютер ұйымдастыру саласына жатады. Параллелизмнің бұл түрінжүзеге асырудың жалпы әдісі – конвейерлер.

Бұл жағдайда, жеке командалар қабысуы мүмкін, немесе берілген команда ішкіамалдарға бөлінуі мүмкін, ал ол ішкі амалдар тағы да ішкі амалдарға бөлініп, олар да қабысуы мүмкін.

Бірінші жағдайда, мысалы, арифметикалық командамен қабыса отырып әдетте жүктеу командасын табады, ол жады мәнін орталық процессордың ішкі регистріне көшіреді. Екінші жағдайда, бәріне үлгеретін конвейердің мысалы бола алады. Ол арифметикалық өңдеутірегі болады.

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

Мысалы, Cray фирмасының супен ЭЕМ-і вектордың ұзынығы – 64 бит немесе одан аз болғана неғұрлым тиімді және ұзын векторлардың кішкене бөліктерінеамалдар қолданатын қайта құру программалары жұмысты жақсарады.

Арифметикалық және иттік туралау параллелизм. Арифметикалық және биттік туралау параллелизмі – параллелизмнің ең төменгі деңгейі.

Параллелизмнің бұл деңгейі орталық процессордағы арифметикалық логикалық құрылғыға қатысты.

Мысалы, 64 битке қосынды екі түрлі әдісен есептелуі мүмкін:

  1. барлық 64 битті бірден қосу (неғұрлым маңызды биттерге тасымал кез-келген екі биттің қосындысының жылдамдығындай есептеуі және болжауы мүмкін);
  2. амалы 4 биттік бөлікке және 16 циклдағы толық қосындысын есептеуге болады.

Параллель программалық жасау үшін фундаментальды талаптарға бар:

  • параллелизм;
  • масштабтылық (әр жақтылық);
  • жергіліктілік;
  • модульдік.

Параллелизм – көптеген амалдарды біруақытта орындауға қабілеттілік.

Әр жақылық – процессорларды санын өсіруе «икемілік» қасиеті.

Жергіліктілік қашықтағы жадыға қатынаудың жергілікті жадыға қатынауына қатынастарының коэффициенттерінің жоғарылылығын білдіреді.

Модульдік – күрділ объектілердің қараайым компоненттерге декомпозициясы.

  • Программалау модельдері: параллель және тізбекті

Тізбекті модеь.

Фон Нейман модеіне:

  • Командалар тізбегін орындауға қабілетті процессор;
  • Команда берілген шаманың адресін анықтайды, орындалатын команданың немесе келесі команданың адресін жадыдан оқиды немесе жазады.

Бүгінгі күні, компьютерді осы негізгі модель терминінде маиналық тілде программалауға болады.

Бұл әдістің кемшілігі мынада: біз жадының милиондаған ұяшығын бақылауымыз керек және мыңдаған машиналық командалардың орындалуын ұйымдастыруымыз керек.

Программаларды қарапайым құрал етудің бір әдісі – процедуралар, циклдар және т.с.с. модульдік программалаудың артықшылығын қолдану.

Параллель модель.

3-суретте қарапайым модель «есептер/каналдар» моделі көрсетілген.

3-сурет. Қарапайым параллель модель: «есептер/каналдар» моделі.

Есептеу процесі каналдармен байланысқан (стрелкалар) есептер жиынын (дөңгелекпен белгіленген) шешуден тұрады.

Есептер программа және жергілікті жадыны инкапсуяциялайды және ортамен өзара әрекеттесетін порттар жиынын анықтайды.

Канал – хабарлар кезегі, оған жіберуші хабар орналастыа алады және алушы хабарды жоя алады, егер хабар қатынауы болмаса, онда канал қатынауды «бұғатайды».

Параллель модельдерді қарастырғанда кейбір келісімдер мен абстракцияларды қабылдау қажет. Параллель программалық жасау үшін фундаментальдық шарттарды қолдану келесі абстракцияларды қабылдауға мәжбүр етеді:

  • Параллель есептеу бір немесе бірнеше есептерді шешуден тұратын. Есептер бір уақытта орындалады. Есептер саны программаның орындалуы кезеңінде өзгеруі мүмкін.
  • Есеп тізбекті программа және жергілікті жадыны инкапсуяциялайды. (шындығында, ұл Фон Нейманның виртуальды машинасы). Одан басқа, ішкі порттар (inports) және қашықтағы порттар (outports) жиынтығы оның оаға өзара әрекетін анықтайды.
  • Есептерді жергілікті жадыдан оқу мен жазудан басқа қосымша төрт негізгі амалды орындай алады: алыс порттарға хабар беру, ішкі порттарын хабар алу, сондай-ақ жаңа есептер құру және оларды аяқтау.
  • Outports/imports жұптары канадар деп аталатын хабарлар кезегімен байланысқан. Каналдар құрылуы және жойылуы мүмкін және каналдарға (порттарға) нұсқағыштар хабарға кіруі мүмкін, садған байланысты қамтамасыз ету динамикалық өзгеруі мүмкін.
  • Есепер физикалық процессорларға әртүрлі әдіспен бейнеленуі мүмкін; қолданылатын бейнелеу программаның семантикасын қозғамайды. Дербес жағдайларда есептердің көптігі бірпроцессорлы компьютерлерге де жарамды.

Ары қарай, программалаудың негізгі параллель модельдерін қарастырамыз.

  • Программалаудың негізгі параллель модельдері

Параллель программалаудың әр түрлі модельдері бар. Олар есептердің өзара әрекеттесу механизмдерімен есептерді талдап тексерідәрежесімен, орналасуын қолдаумен, әржақтылық пен модельділігімен ерекшеленеді:

  • Хабар беру.
  • Деректер параллелизмі.
  • Жалпықатынау жадысы.

Келесі лекцяларда оларға толығырақ тоқталамыз. Мұнда тек олардың әрбіреуінің негізгі принциптеріне тоқталамыз.

Хабар беру

Хабар беру программаларды есептер жиынын құрады, олардың әрбіреуінің жергілікті деректен тұады. әрбір есеп басқа есептермен өзара әрекеттестікте болады, берілген есепке хабар береді немесе ерілген есептен хабар алады.

Деректер параллелизмі

Деректер параллелизмі үлестірілген есептеулерді қолданады. Олар деректер құрылымының элементтер жиынына қолданылатын бір ғана амалдан және бір қосымшадан шыққан. Деректердің әрбір элементіне қолданыатын әрбір амалды тәуелсіз есеп деп қарастыруға болады.

Жалпықатынау жадысы

Жалпыанықтау жадысында модельді программалағанда есептер жалпы адрестіккеңістікті бірге қолданады, олар оны асинхронды оқиды және жазады. Сонымен қатар, жалпықатынау жадысына қатынауды басқару үшін әртүрлі механизмдер қолданылуы мүмкін.