Қолданбалы есептерге параллельді алгоритмдерді қолдану

КІРІСПЕ 3

1 НЕГІЗГІ БӨЛІМ 4
1.1 ҚОЛДАНБАЛЫ ЕСПТЕР ҮШІН ПАРАЛЛЕЛЬДІ ЕСЕПТЕУЛЕР 4
1.1.1 Қатарлы және параллельді алгоритмдер 4
1.1.2 Параллельді алгоритмдерді ұйымдастыру 7
1.1.3 Параллельді есептеудің технологиялары 11
1.1.4 Параллель есептеулерді қолданатын салалар 14
1.1.5 Тиімділікті талдау алгоритмі 15
2 ПРАКТИКАЛЫҚ БӨЛІМ 17
2.1 СҰРЫПТАУДЫҢ ПАРАЛЛЕЛЬДІ АЛГОРИТМДЕРІ 17
2.1.1 Көпіршік сұрыптау: тізбекті және параллельді әдістері 17

2.1.2 Жылдам сұрыптау: тізбекті және параллельді әдістері 25
2.1.2 Шелл әдісімен сұрыптау: тізбекті және параллельді әдістері 28
ҚОРЫТЫНДЫ
31
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ 32
Жұмыстың негізгі мақсаты: Сұрыптау есебінің параллельді алгоритмін құру.
Жұмыстың міндеті:
1. Көпіршік, жылдам, Шелл сұрыптау әдістерінің тура программасын құру.
2. Көпіршік, жылдам, Шелл сұрыптау әдістерінің параллельді есептеу программасын құру.
3. Құрылған программалардың нәтижесін MPI арқылы көру және анализ жасау.
Тақырыптың өзектілігі:
1. Параллельді есептеуді қолданудың өзектілігі. Параллельді есептеу дегеніміз – бір уақыт кезінде бірнеше есептеу операцияларын орындайтын есепті шешуге арналған процестер. Суперкомпьютерлер технологиясы мен жоғарғы өнімді есептеулер параллельді есептеудің негізін құрайды.Бір уақытта орындалатын операциялар бір есепті шешуге арналуы керек. Параллельді есептеуді қолданатын аймақтар:
• Ғылымда. Ауа райын болжауда, жаңа технологияларда, жаңалықтарда, ағымдағы космостық ұшу туралы жедел ақпарат алу кезінде, генетика саласында, химиялық есептеулер кезінде.
• Бизнестегі коммерциялық қосымшаларда. Видео конференциялары бар қосымшаларда, жұмыс ортасының бірлесуінде, деректер қорын параллельді өңдеуде, банктық транзакциялар орындау кезінде.
• Білім саласында. Графика мен виртуальды өмірді кеңейту үшін.
2. Параллельді программалауды MPI арқылы іске асыру. MPI (Mes¬sage Passing Interface) хабарламаны жіберу интерфейсі деп аударылады. Компьютер бірнеше процестерден тұрады, ал әрбір процесс өзінің меншікті жадысымен қамтылған. Процессоры мен оның меншікті оперативті жадысы бар, коммуникациялық желіге қосылған компьютерды хост-машина деп айтады.
Параллельді алгоритм құруда бастапқы мәселе бірнеше бөлік есептерге бөлінеді және оның әр біреуі бір әдіспен шешіледі.Сондықтан бұл жағдайда параллелді программа бірнеше ұқсас фрагменттерден тұрады және барлық процестерде бірдей есептер орындалады. Бұл схема SPMD-моделі (Single Program Multiple Data) деп аталады және хабарламаны жіберу моделінің дербес жағдайы болып табылады.
MPI — "Хабарламаны жіберу интерфейсі"
MPICH (MPI CНameleon) MPI спецификациясын іске асырулардың бірі болып табылады.
Жұмыстың нәтижелері:
1. Көпіршік, жылдам, Шелл сұрыптау әдістерінің тізбекті программасы құрылды.
2. Көпіршік, жылдам, Шелл сұрыптау әдістерінің параллельді есептеу программасы құрылды.
3. Құрылған программалардың нәтижесі МРІ арқылы көріп, талдау жасалды.
1. Акжалова А.Ж. Параллельные вычисления (учебное пособие). Алматы, 2004ж. 114 бет.
2. Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем. Санкт-Петербург, 2002ж. 400бет.
3. Ақжалова Ә.Ж. Параллельдік есептеу (оқулық): Parallel Computing , Алматы, 2004 ж. 48бет.
4. Воеводин Вл. Параллельные вычисления . С-П, 2002 ж. 36 бет.
5. Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределительного программирования., Изд.Дом., 2003 ж. 132 бет.
6. Немнюгин С.А.,Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем. С-П., 2002 ж. 147б.
7. Павловская Т.А. C/C++. Программирование на языке высокого уровня. СПб.: Питер 2006ж. 83 б.
Интернет-сілтемелер:

8. http://www.ccas.ru/mmes/educat/lab04k/01/basics.html
9. http://www-unix.mcs.anl.gov/mpi
10. http://www.parallel.ru/vvv/mpi.html
        
        ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖƏНЕ ҒЫЛЫМ МИНИСТРЛІГІ
ӘЛ-ФАРАБИ АТЫНДАҒЫ ҚАЗАҚ ҰЛТТЫҚ ... ... ... жұмысы
Қолданбалы есептерге параллельді алгоритмдерді қолдану
|Орындаған 4 курс ... ... ... У.С. |
| | | |
| | | ... ... | | ... ғ.к., ... ... ... М.Е. |
| | | |
| | | ... ... ... ... М.Ж. |
| | | |
| | | ... меңгерушісінің | | ... ... ... | |
| ... ... Д.Ж. ... ғ.к., доцент | | ... ... ... | |
| ... |3 |
| | | |
|1 ... ... |4 |
| | 1.1 ... ... ҮШІН ... ... |4 |
| | 1.1.1 ... және параллельді алгоритмдер |4 |
| | 1.1.2 ... ... ... |7 |
| | 1.1.3 ... ... ... |11 |
| | 1.1.4 ... ... ... ... |14 |
| | 1.1.5 ... ... алгоритмі |15 |
|2 ... ... |17 |
| | 2.1 ... ... ... |17 |
| |2.1.1 ... ... ... және параллельді |17 |
| ... | |
| | 2.1.2 ... ... ... және ... әдістері |25 |
| | 2.1.2 Шелл ... ... ... және ... |28 |
| ... | |
| ... |31 |
| ... ... ... |32 |
| | | |
| | | ... ... ... Сұрыптау есебінің параллельді алгоритмін
құру.
Жұмыстың міндеті:
1. Көпіршік, жылдам, Шелл сұрыптау әдістерінің тура программасын құру.
2. Көпіршік, ... Шелл ... ... ... ... құру.
3. Құрылған программалардың нәтижесін MPI арқылы көру және анализ жасау.
Тақырыптың өзектілігі:
1. Параллельді есептеуді қолданудың ... ... ... – бір ... ... бірнеше есептеу операцияларын орындайтын
есепті шешуге арналған процестер. Суперкомпьютерлер технологиясы мен
жоғарғы өнімді ... ... ... негізін құрайды.Бір
уақытта орындалатын операциялар бір ... ... ... ... ... ... ... Ғылымда. Ауа райын болжауда, жаңа технологияларда, ... ... ұшу ... ... ... алу кезінде, генетика
саласында, химиялық есептеулер кезінде.
• Бизнестегі коммерциялық ... ... ... бар
қосымшаларда, жұмыс ортасының бірлесуінде, деректер қорын параллельді
өңдеуде, банктық транзакциялар орындау кезінде.
• Білім саласында. Графика мен ... ... ... ... Параллельді программалауды MPI арқылы іске асыру. MPI (Message ... ... ... ... деп ... ... бірнеше
процестерден тұрады, ал әрбір процесс өзінің меншікті жадысымен қамтылған.
Процессоры мен оның меншікті оперативті жадысы бар, ... ... ... ... деп айтады.
Параллельді алгоритм құруда бастапқы мәселе бірнеше бөлік ... және оның әр ... бір ... ... бұл ... ... ... ұқсас фрагменттерден тұрады және барлық
процестерде ... ... ... Бұл ... ... ... Multiple Data) деп ... және хабарламаны жіберу моделінің дербес
жағдайы болып табылады.
MPI — "Хабарламаны жіберу интерфейсі"
MPICH (MPI CНameleon) MPI ... іске ... бірі ... ... ... жылдам, Шелл сұрыптау әдістерінің тізбекті программасы
құрылды.
2. ... ... Шелл ... ... ... есептеу
программасы құрылды.
3. Құрылған программалардың нәтижесі МРІ арқылы көріп, талдау жасалды.
1 НЕГІЗГІ БӨЛІМ
1.1 ... ... ... ... ... ... алгоритмдер
Информатикадағы дәстүрлі жүйелі алгоритмдерге қарсы қойылатын
параллель ... ...... ... ... және нақты
ортақ қорытынды алуға негізделген көптеген есептеу құрылғыларында ... ... ... ... ... ... ... түрде
тәуелсіз орындалатын көріністерге бөлуге болады. ... 1-ден ... ... сандарды олардың қайсысы жай сандар ... ... ... ... ... жай ... ... арқылы
қолда бар әрбір процессорға қандай да бір ішкі жиынды беру арқылы жіктеу
(осындай ... ... GIMPS ... ... ... ... жағынан
бізге белгілі алгоритмдердің көпшілігі пи ... ... ... ... бөле ... ... олар ... алдыңғы
итерациясының мәнін талап етеді. Ньютон әдісі немесе үш дене есебі сияқты
итеративті ... ... ... ... ... ... ... алгоритмдердің мысалдарды параллельдіктен ажыратуға бағындыру
қиынға соғады. Осындай мысалдардың бірі – графалардағы тереңдікке ... ... көп ... ... ... ... ... заманғы процессорлардағы ядролардың санын көбейтуге байланысты
маңызды орын алады. Әдетте бірнеше баяу ... ... ... бар
компьютерге қарағанда бір ғана жылдам процессоры бар компьютерді құрастыру
оңайға соғады (бір ғана ... жету ... ... ... ... негізінен техникалық процесті жетілдірудің
(өндіру нормаларын азайту) есебінен арта түседі, ... ... ... мен жылу ... ... ... ... Аталмыш шектеулерді көп процессорлы өңдеуге көшу арқылы ... Бұл әдіс кіші ... ... үшін де ... ... ... алгоритмдердің күрделілігі алгоритмді орындау үшін ... жад пен ... ... такті саны) көлемінде байқалады.
Параллель алгоритмдер тағы бір мынадай қорды қолдануды ... ... ... түрлі процессорлар арасындағы байланыстардың ішкі ... ... ... екі ... бар: жалпы жадты және
хабарламаларды беру жүйесі. Жалпы жады бар ... ... ... ... ... ... ... етеді, осылайша олар қосымша
процессорларды қолдану барысында нақты шектеулер қояды.
Хабарламаларды жеткізу жүйелері хабарламалардың желісі мен ... ... ... Бұл ... ... трафикті тудырып, хабарламалардың
жүйесін ұйымдастыру үшін жадтың қосымша шығындалуын талап етеді. Қазіргі
заманға сай ... ... ... ... ... қойылған мәселені орындауға тигізетін зиянын азайту мақсатында арнайы
коммутаторлар (кроссбарлар) қарастырылуы мүмкін.
Параллель алгоритмдерді қолдануға қатысты ... бірі ... ... Мысалы, 1-ден 100000-ға дейінгі аралықтағы жай сандарды
тауып, қолда бар процессорларға оңай ... ... ... ... ... жұмыс көлемін алса, екінші біреулері өңдеуді ... бос ... ... ... ... теңгеруге қатысты кедергілер
гетерогенді есептеу ... ... ... ... түседі. Мұндай
орталарда есептеу элементтері өнімділігі мен қол ... ... ... ... ... алгоритмдердің үлестірілген алгоритмдер деп ... ... ... ... ерекшеліктерін ескере отырып, кластерлер мен
үлестірілген есептеу жүйелерінде қолдану мақсатында ... ... ... ... пайдалану параллель есептеулердің ... ... және ... ... ... ... ... өзара
ортақ қасиеттері бар аппаратты тұғырнамалардың кең класы үшін параллель
бағдарламалаудың ерекшеліктері ... ... ... ... ... кластерлері) кеңінен
қолданылып жүр – бұл көп ... ... мен ... ... ... тәжірибелерін ұйымдастыру үшін қолданылатын суперкомпьютерлер,
ақпараттық және есептеу қорларын ... ... ... ... ... Есептеу кластерлерінде түрлі сәулет
ғимараттары мен операциялық қоршаған ортасы ... ... ... ... жиі ... ... ... туындайды. Осының барлығы
үлестірілген есептеу құралдарын жалпы ұжымдық қор ретінде қолдануға ... ... ... Біз осы ... кем ... аз ... тырысып көреміз.
Процессорлардың жұмысының тактілік жиілігі шамамен ... ... ... деп есептесек, онда қазіргі таңда жасалатын
секундына 103 млн. операция (МОПС) – бұл бір ғана ... ... ... ... болатын өнімділік. Жыл сайын шығарылатын процессорлардың
тактілік жиілігі артып отыратындықтан максимал өнімділікті шамамен 106-108
МОПС арттыруға болады ... үміт жоқ ... ... ... процессорлардың
молекулалық шектеулердің салдарынан уақыт бойынша сызықты экстраполяциясы
жоқ. Өнімділігі 108 МОПС артық процессорлар ... ... ... ... ... ... мүмкін, не болмаса оларды ... ... ... шығатындай, есептеу техникасын дамытудың жалғыз
жоспары – бұл көп процессорлы есептеулерді жасау. ... ...... ... шешуде өнімділікті жоғарылатудың ұтымды
тәсілі.
Параллель алгоритмді орындау барысында әрбір ... ... емес ... бар ... қарастырылған жүйелі алгоритм жүзеге
асырылады. Процессорлық элементтердің арасында ... ... бар ... Есеп ... мәліметтер диск жадынан нөлдік процессордың
көмегімен оқылады және қалғандарына беріледі. Әрі қарай нөлдік ... ... ... ... бастапқы есеп шешіледі, ал қалған
процессорлар осы ... күту ... ... ... ... ... параллель есептеулерді ұйымдастыруға арналған қажетті анықтамалық
ақпарат жинақталады.
Кез келген процессорды іске қосу үшін (әрі қарай оның ішінде нөлдікті
де) оның ... ... ... ... жіберіледі: ISB, ISN және
бағалау есептерін бейнелеу үшін қолданылатын h массивінің бір ... ... ... ... ... ISB ... ... айнымалылардың
нөмірлерінен құралады, n өлшемді базисті емес айнымалыларға ... ... ISN ... ... ... немес төменгі шекараларда айнымалылардың
орналасқандығын анықтайды, ал ... ... үшін ISN ... ... ... ... ... h массивінің қай бөлігі
берілетіндігі бағалау есептерін шешу басталатын деңгеймен анықталады.
Нөлдік процессордан қандай да бір процессорлық элементті жүктеу ... ... k ... ... ... ... үшін ... таңдалып алынсын және P-j < P+j. Нөлдік процессорда P-j штрафына
сәйкес келетін бағалау есебі шешілетін болады. Егер fi – P+j > ri ... ... ... процессорлық элементке жіберіледі.
Нөлдік процессорлық элементте P+j мәніне сәйкес келетін тармақ белгіленеді
(h (3,k) ... 1 мәні ... ... ... k-ға қарағанда
анағұрлым жоғары деңгейге ие белгіленбеген барлық тармақтар белгіленеді.
ISB тізімінің негізінде базисті матрицаларға ... ... ... құру
процедурасының (бұл процедураны тағы қайталау деп те атайды) көмегімен В-1
матрицасы тұрғызылады. ISB, ISN және h ... ... ... ... ... ... ... үшін жеткілікті.
Параллель алгоритмде әрбір процессорлық элементте есептеу процесін
бастаған жөн, мүмкіндігінше, ... ... ... ... ... болады.
Ол үшін әрбір процессорлық элементте ISB және ISN массивтері ... олар ... ... соң ... ... ... беріледі.
Егер қандай да бір процессор жаңа ri рекордын алса, онда бұл ... ... ri алып ... ... ... £ ... орындалуы тексеріледі, мұндағы k аталмыш ... ... ... ... ... сәйкес келеді. Осы теңсіздік
орындалған жағдайларда жаңа тапсырмаға ... ... ... ri мәні һ
массивіндегі белгіленген және белгіленбеген тармақтарды тексеру ... ISB, ISN ... ... ... болмай қалуы мүмкін
(ri жаңа мәнінде осы массивтерге сәйкес ... ... ... ... ISB мен ISN жаңа ... дайындалады және нөлдік
процессорлық элементке осы массивтерге ... ... ... ... ... Есеп ... егер ri = f0 рекорды қабылданған болса
немесе барлық процессорлық элементтерде ... ... қол ... Есеп ... ... мәліметтерді беру MPI BCAST блоктау
функциясының көмегімен жүзеге ... Әрі ... ... ... режимде орындалады және мәліметтермен алмасу блокталмаған
функциялар арқылы жүзеге асырылады. ... ... ... ... ... ... іске ... Хабарламалар ISEND және WAIT
арқылы орындалады, ал қабылдау ... RECV ... ... Аталмыш
процессорға хабарлама бар – жоғын ... ... IPROBE ... Қысқа хабарламалар үшін үш мақсатты және бір ғана заттық саны бар
екі еселік дәлдіктегі құрылым ... ... ... ... (ISB, ISN және h ... ... ... хаттама арқылы
орындалады. Блоктаушы функциялардың көмегімен шешімді алғаннан ... ... ... есепті шешу бойынша өзге процессорлардан келген
статистикалық мәліметтер саналады.
2. Параллельді ... ... жады бар ... ... көп ... ... ... тағы бір жалпы ... ... ... ... ... жоғары өнімді кластерлік есептеу жүйелерінің кеңінен
дамуына сай соңғы уақыттарда өсуде.
Параллель бағдарламалаудың көптеген ... ... ... ... ... ... және ... жадқа ие
жүйелер үшін ортақ болып табылады. Параллель есептеулерді үлестірілген
жадтан ажырататын ... әр ... ... ... ... өзара әсерлесуі хабарламаларды тасымалдау арқылы қамтамасыз
етілетіндігіне негізделген (message passing). Үлестірілген жады ... ... жады бар көп ... ... ... ... анағұрлым күрделі есептеу құрылғысы екендігі анық. ... ... үшін әрі ... ... жады бар ... сервері деп атайтын боламыз (сервер ретінде ішінара жалпы жады бар
көп процессорлы жүйе де ... ... ... ... барлық
тәжірибелерді жүргізу үшін процессорлары Pentium IV, 1300 Mhz, 256 RAM, 100
Mbit Fast Ethernet ... 4 ... ... Үлестірілген жады бар
жүйелерде параллель есептеулерді ұйымдастыру ... ... ... ... ... ... ... есептеу серверлерінің арасында
бөлу тәсілдерін таңдауға ... ... ... ... есептеулерді жергіліктендірудің қол жеткізілген дәрежесімен
анықталады (хабарламаларды жеткізудегі ... ... ... қатысты
серверлердің өзара әсерлесу қарқыны минимал болуы тиіс).
1 сурет. Есептеу облысын процессорлар арасында ... бөлу ... ... ... ... отырған Дирихле есебін шешуге ... оқу ... ... екі ... ... бар – есептеу торының бірөлшемді
немесе таспалы сызбасы (1 ... не ... ... ... ... (2 ... Оқу материалы әрі қарай бірінші тәсіл мысалында
баяндалатын болады; ... ... ... ... ... ... жіктеудің осындай тәсіліне ие ... ... ... да бір ... ... жүзеге асыратын процессорға есептеу
торының алдыңғы және кейінгі жолақтарының шекаралық жолдары ... ... баса ... аударған жөн. Көшірілген жолақтың шекаралық жолдары
есептеу барысында ғана қолданылуы тиіс. Осы жолдарды қайта есептеу бастапқы
орнындағы жолақтарда ... ... ... ... ... тор
әдісінің әрбір кезекті итерациясы алдында жүзеге асырылуы тиіс. Жолақтың
жолдарын ... үшін 0 және M+1 ... ... ... ... ... ... ал процессордың өзіндік жолағының жолдары 1-ден М-
ге дейінгі нөмірлерге ие болатын нөмірлеуді қолданатын боламыз.
2 сурет. ... ... ... ... ... беру ... процессорлар арасындағы шекаралық жолдармен алмасу процедурасы екі
кезекті операцияларға жіктелуі ... оның ... ... ... ... ... ... келесі процессорға беріп, дәл осындай жолды
алдыңғы процессордан қабылдап алады. ... ... ... ... ... ... асырылады: процессорлар өздерінің жоғарғы шекаралық жолдарын
өздерінің алдыңғы ... ... және ... ... ... ... Осындай мәліметтерді беру операцияларын жалпы күйде
төмендегіше ... ... ... болу үшін ... ... бөлігін ғана қарастырамыз):
// төменгі шекаралық жолды келесі
// процессорға беру және берілетін жолды
// алдыңғы процессордан ... ( ProcNum != NP-1 ... ( ProcNum != 0 ... ... жазбалау үшін стандартқа жақын MPI форматы
қолданылады, мұндағы бірінші және екінші параметрлер жіберілетін ... ... ... сипаттайды, ал үшінші параметр мәліметтерді ... (Send ... ... ... алу ... (Receive ... үшін)
анықтайды).
Мәліметтерді беру үші екі түрлі механизм іске қосылады. Жіберу
операциясына ... күш ... ... бірінде мәліметтерді жіберуге
қатысты ... ... ... ... ... ... ... (яғни процессор – адресат ... оған ... алып ... ... ... ... ... асырылатын
қабылдау-беру операциялары әдетте синхронды немесе блоктаушы деп ... бір әдіс – ... ... ... тасымал – ол қабылдау-беру
операциялары тасымал процесіне ғана түрткі болып, осы ... ... ... ... ... ұзақ ... созылатын
коммуникациялық операциялардың аяқталуын күтпей-ақ, ... ... сай ... ... дайындығын тексере
отырып, өздерінің есептеулерін ... ... ... осы қос
нұсқасы да параллель есептеулерді ұйымдастыруда кеңінен қолданылады және
олардың да ... ... мен ... бар. ... ... ... ... қолдануға оңай және анағұрлым сенімді;
блоктамайтын операциялар мәліметерді тасымалдау және ... ... ... ... әдетте олардың салдарынан бағдарламалау ... ... ... ... осындай мысалдарды ескере ... ... ... үшін блоктау типіндегі қабылдау-беру
операциялары қолданылатын болады.
Жоғарыда ... ... ... ... ... қасиеті (алдымен Send, содан соң Recieve) жолдарды
тасымалдаудың қатаң жүйелі сызбасына келіп ... ... ... ... Send ... ... және күту ... Тасымалданатын мәліметтерді қабылдауға дайын болатын бірінші
процессор – бұл NP-1 нөмірлі ... ... NP-2 ... ... жолын беру операциясын орындап, NP-3 процессорынан жолды
қабылдауға көшеді және ... ... ... ... саны NP-1 ... ... ... өңдеу алдында шекаралық жолдарды тасымалдаудың екінші
бөлігі де іске ... (2 ... ... ... тасымалдау
операцияларының жүйелі сипаты амалдарды кезегімен орындау тәсілін таңдаумен
анықталады. Осы амалдарды орындау кезегін жұп және тақ ... ... ... және беру ... ... ... өзгертіп көрейік:
// төменгі шекаралық жолды келесі
// процессорға беру және берілетін жолды
// алдыңғы процессордан ... ( ProcNum % 2 == 1 ) { // тақ ... ( ProcNum != NP-1 ... ( ProcNum != 0 ... else { // жұп ... процессор
if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);
if ( ProcNum != NP-1 ... ... ... қажетті беру операцияларын екі кезекті қадамның ішінде-
ақ орындауға ... ... ... ... ... тақ ... ... жібереді, ал жұп нөмірлі процессорлар ... ... ... қадамда процессорлардың рөлдері ауысады –
жұп процессорлар Send амалын орындаса, тақ ... Reciеve ... ... ... ... ... ... мақсатындағы қабылдау-беру
операцияларынң жүйелі сипаты параллель есептеулер тәжірибесінде ... ... ... ... ... ... ... қолдауға арналған процедуралар бар. ... ... Sendrecv ... ... оны қолдану арқылы
бағарлама кодының алдыңғы көрінісін қысқаша түрде ... ... ... ... ... келесі
// процессорға беру және жіберілген жолды
// келесі процессордың қабылдауы
Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);
Мұндай Sendrecv біріккен ... ... ... ... ... сай ... беру ... қабылдау операциясының бірін орындау қажет болмайтын
шеткі ... ... ... ... ету үшін және ... шығу үшін және ... мәліметтерді тасымалдауды параллель
жүзеге асыру мүмкіндігіне ие болу үшін ... ... ... ... ... Параллельді есептеулердің технологиялары (MPI,Open/MP)
Параллельді программалауды MPI арқылы іске асыру. MPI (Message Passing
Interface) хабарламаны жіберу интерфейсі деп аударылады. Компьютер ... ... ал ... ... ... ... ... қамтылған.
Процессоры мен оның меншікті оперативті жадысы бар, ... ... ... ... деп айтады.Хабарламаны жіберу моделіндегі
параллельді программа бір ... ... ... ... ... Осы тізбектелген программалардың әрбіреуі ... ... және ... ... жадысына жүгіне алады.
Хабарлама жіберу моделінде мәлімет сілтемесі және ... ... ... іске ... ... құруда бастапқы мәселе бірнеше бөлік есептерге
бөлінеді және оның әр ... бір ... ... ... ... ... мәлімет терудегі түрлі фрагменттерде ... ... ... ... ... ... ... фрагменттерден тұрады және
барлық процестерде бірдей есептер орындалады. Бұл схема SPMD-моделі (Single
Program Multiple Data) деп аталады және ... ... ... ... болып табылады.
MPI — "Хабарламаны жіберу интерфейсі"
Бұл спецификация 1993—1994 жылдары MPI Forum тобымен ... ... ... ... программа, хабарламаны жіберетін және
қабылдайтын ішкі программаларға жүгінетін ... ... ... ... ... ... белгіленген
процестер жиынтығы құрылады және ... ... ... ... ... ... ... MPI спецификацияларын
қанағаттандыратын бірнеше программалық пакеттер құрылған: MPICH, LAM, ... тағы ... ... ең аз ... ... программалау кітапханасы (Си,
Си++ және Фортран тілдері үшін ... ... мен ... ... ... (MPI CНameleon) MPI спецификациясын іске ... бірі ... Ол ... үлкен санында және түрлі коммуникациялық
интерфейстерде, ... ... да ... ... алады.
Мысалдардың жиыны MPICH түрлі версияларында әртүрлі болуы мүмкін.
MPI-дың ең қысқа қолданбаларында да қолданылатын ... ... ... ... ... main ... алғашқы нұсқаулардың
бірі:
MPI_Init(&argc, &argv );
Операциялық жүйелерден және ... ... ... ... main функциясы ... ... ... ... ... ... ... кезінде MPI-ға қатысты қателерге
байланысты қолданбалы программаның ... ... ... ... ... ... MPI қатесінің коды);
MPI_Abort функциясы шақырылғанда кез келген есептен берілген байланыс
аймағына қосылған барлық есептерді мәжбүрлі түрде ... ... ... ... ... ... ... оның барлық есептері түгел дерлік аяқталады.
3. Кітапхананы дұрыс жабу:
MPI_Finalize();
4. Екі ақпараттық функциялар: топ ... ... ... ... ... ... ... саны) және шақырылатын есептің реттік
номері:
int size, rank;
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI-да мәлімет алмасу:
Алмасудың негізгі типтері - екі нүктелі және коллективті.
Хабарламамен екі ... ... ... ... ... ... ... хабарламаға сілтеу үшін
жіберуші процестің ішкі программасын шақырады, оған ... ... ... ... ... ... ... рангісі көрсетіледі. Алушы
процесс өзіне бағытталған хабарламаны алу үшін, жіберуші процестің ... ... ішкі ... шақыруы керек.Мысалы, 0 рангті
процесс 1 рангті процеске екі А және В хабарламаларын ... 1 ... А ... ... В хабарламасын алады. Маңызды қасиеттерінің бірі −
алмасудың міндетті орындалуы болып табылады.
Екі нүктелі алмасудың төрт түрі бар: ... ... - ... ... ... ... ... деп саналады.
Синхронды жіберу - стандарттыдан хабарламаны қабылдау ... ... ... ... ... - бірден аяқталады, және
хабарлама жүйелік буферге көшіріледі де ол ... ... ... ... ... ... жіберу - адресат хабарламаны қабылдауға
инициаланған ... ... ... ... ... ... ... алмасуды ұйымдастыратын функциялар:
MPI_SEND(buf, count, ... dest, tag, comm) – ... ... кіретін параметрлер: buf – жіберу буферінің адресі, count ... ... ... саны ... ... ... сан), datatype –
жіберілетін мәліметтердің типі, tag – хабарлама тегі (бүтін сан), comm ... count, ... source, tag, comm, status) – ... buf – шығу ... status та шығу ...... ... source – хабарлама алатын процестің идентификаторы. Қалған
параметрлер MPI_SEND-те бар.
Коллективті мәлімет алмасу:
Екі нүктелі алмасуда екі процесс қатысады – ... көзі және ... ... ... ... саны ... Хабарлама бір
процестен бірнешеуіне жіберіледі немесе бір процесс бірнешеуінен мәлімет
жинайды.
Коллективті алмасуды ұйымдастыратын ... ... ... int ... ... sendtype, void
*rcvbuf, int rcvcount, MPI_Datatype rcvtype, int root, MPI_Comm ... ... ... int sendcount, MPI_Datatype sendtype, void
*rcvbuf, int rcvcount, MPI_Datatype rcvtype, int root, MPI_Comm ... ... ... int ... int *displs, ... void *rcvbuf, int rcvcount, MPI_Datatype rcvtype, int root,
MPI_Comm comm)
int MPI_Bcast(void *buffer, int count, ... ... int ... ... MPI_Gatherv(void *sendbuf, int sendcount, MPI_Datatype sendtype, void
*recvbuf, int *recvcounts, int *displs, ... ... int ... ... ... ... int ... MPI_Datatype sendtype, void
*rcvbuf, int rcvcount, MPI_Datatype rcvtype, MPI_Comm coram)
int ... ... int ... int ... sendtype, void *rcvbuf, int *rcvcounts, int *rdispls,
MPI_Datatype rcvtype, MPI_Comm ... ... *buf, void *result, int count, ... ... op, int root, MPI_Coimi coirm)
OpenMP – негізінен ... ... ... ... ... ... ... қосымшаларды құрастыру үшін ... ... OpenMP ... мен ... ... ... ... жиынтығынан тұрады. OpenMP стандарттары соңғы 15 жылдың
ішінде жалпы жадты ... ... ... ... ... ... жады бар ... есептеу жүйелері үшін OpenMP
стандарттарын ... ... ... ... 2005 ... ... Intel
компаниясы Cluster OpenMP өнімін жарнамалады, аталмыш өнім OpenMP
кеңейтілуін ... жады бар ... ... үшін ... асырады. Осы
өнім кластерлердің барлық түйіндері қол жеткізе алатын мәліметтер облысын
жариялауға және мәліметтерді Lazy Release ... ... ... емес ... ... ... ... мәліметтерді
тасымалдауға мүмкіндік береді. OpenMP жеңіл, әрі жылдам ... Fortran ... ... ... көп ағымды қосымшаларды жасауды қамтамасыз
етеді. Осы ... OpenMP ... C/C++ ... ... директиваларына ұқсас және Fortran алгоритм тіліндегі
түсініктемелердің ... ... ... Бұл ... ... жүзеге асырылуын жобалаудың кез келген мезетінде қажет болған
жағдайда бағдарламаның жүйелі ... ... ... ... ... ... ... параллель есептеулерді жобалаушылардың ... ... ... ... атап ... Intel, Hewlett-Packard, Silicon
Graphics, Sun, IBM, Fujitsu, Hitachi, Siemens, Bull ... және ... бар. ... ... ... ... ... көптеген
белгілі компаниялар OpenMP көмегімен жүйелік бағдарламалық қамтудың жобасын
жасауға аса көп көңіл бөледі. Осындай компаниялардың ... Intel, ... PSR, APR, Absoft және ... атап ... жөн. ... ... ... асыратын компаниялар мен ғылыми – зерттеу
ұйымдарының ... саны ... ... ... бағдарламалық өнімдерін
жобалауда OpenMP қолданады. ... ... мен ... ... Fluent, Oxford ... NAG, DOE ASCI, Dash, ... Software,
сонымен қатар ТЕСИС сияқты ресейлік компанияларды, Орталық ... РҒА ... ... ... РҒА ... ... ... Институты, ММУ Ғылыми-зерттеу есептеу орталығы, РҒА
химиялық физика Институты және т.б. сияқты ғылыми-зерттеулік ұйымдарды атап
кеткен жөн.
1.1.4 ... ... ... ... ... ... шартты түрде үш ірі облысын ... ... ... және ... ... - іздеу, өңдеу,
сақтау және ақпараттарды ... ... ... және білім базасын құру;
2. Адамның ... ... ... және ... ... автоматтандырылған жүйесі (АСНИ), жобалаулардың автомат
тандырылған жүйесі (САПР), басқарудың автоматтандырылған жүйесі (АСУ).
3. Табиғаты ... ... және ... ... модельдеу –
күрделі көппараметрлі сызықтық емес құбылыстардың сандық және сапалық
сипаттамаларын алу, оларды ... және ... ... дамуын болжау-
сандық эксперимент.
Есептеу техникасы алғаш және ... ... ... ... ... модельдеу және есептеу эксперименттері : ... құру және ... ... аса ... ... ... ... мынандай тізбекті іске асырады: нысан- модель (мат
физика теңдеулері) – алгоритм ... ... және ... ... - ... талдау - нысанды басқару. Осылай есептеу экспе римент
көмегімен алынған ... ... ... ... болады. Тек қана
математикалық модельдеу және ... ... ... ... ... маңызды проблемаларды атауға болады:
1) Энергетикалық проблемалар - атомдық және ... ... ... ... физикалық процесстердің математикалық модельдерін
зерттеу негізінде оларды есептеу және ұзақмерзімді болжамдар жасау;
2) ... және ... ...... ... ... сүйір ағын (обтекания) есебі;
3) Тәжірибеден немесе сынақтан алынған деректерді өңдеу;
4) Экологиялық проблемалар - ... ... және ... тек ММ негізінде
шешіледі;
5) Гео-астофизикалық құбылыстар - ұзақ ... ауа ... ... болжау, жұлдыздар және күннің белсенділік көрсетуі және
дамуын , Әлемнің ... ... және ... ... ... ... күрделі жуйелерді сандық модельдеу, ауа-райын ... ... үшу ... ... ... ... болжау типті
модель бойынша ертеңгі күннің ... ... ... ... ... Химия – химиялық реакцияларды есептеу, реакция тұрақтыларын анықтау,
макро-және микродеңгейде жылу және масса тасымалдауларын ... ... - ... проблемалар (генетика, морфогенез ... ... және ... жаңа ... ... ... Физика – ММ пайдаланудың ең дамыған облысы;
9) ...... және ... өзімізге қажет қасиеті бар материал
дар жасау;
10) Экономика және басқару есептерін шешу.
11) ... ... ... кұрамына бейнеконференция,
үйлескен жүмыс орталары, параллель деректер коры. банктык транзакциялар
кіретін қосымшалар.
12) Техникадағы косымшалар: ... ... ... ... ... коммерциялык қосымшалар: кеңейтіген графика ... ... ... ... ойындар, ойын-сауык, салалары;
Бұл мәселелердің көпшілігін дербес компьютерлерде шығару тек қана есеп тің
ең қарапайым модельдерінде, есептің ... ... ... ... ... ... Ал, күрделі және толық математикалық модельдер үшін
ЭЕМ-ның өнімділігін күрт ... ... ... да ... және ... эксперименттерімен байланысты зерттеу жұмыстарын
жүргізгенде суперкомпьютерлер қолданылады.
1.1.5 Тиімділікті талдау алгоритмі
Идеал ... Р ... ... бір процессорға қарағанда Р ретке
жылдам орындалуы тиіс немесе/және көлемі Р ретке үлкен есептерді ... ... ... ... ... жеделдетуге ешқашанда қол жеткізе
алмаймыз. Мұның себебін Амдал заңы жақсы бейнеленеді:
| | |(3.1) ... S – Р ... ... ... жеделдетілуі, ал f ... ... емес ... үлесі. Бұл өрнек жалпы жадты үлгіде
де, хабарламаларды беру үлгісінде де бағдарламалауда орынды. Қандай да ... ұдай ... ... емес код ұғымында жатыр. SMP жүйелер үшін (жалпы
жад ... осы ... ... ... ... ... операторлар
құрайды. MPP жүйелер (хабарламаларды беру мезанизмі) үшін кодтың параллель
емес бөлігі орындалуы ... ... ... ... ... ... мәтінін талдаудан бұл шаманы анықтау
мүмкін ... ... ... ... ... санынан тұратын
нақты есептеулер ғана береді. (1) өрнектен Р-ретті жеделдетуге параллель
емес ... ... ... тең ... ... ғана қол ... ... Мұндай жағдайды болдыру мүмкін емес. Кестеден көрініп тұрғанындай,
егер, мысалы, жүйелі ... ... 2%-ды ... онда ... ... алу ... ... Екінші жағынан 49-ретті жеделдетуді алу
мақсатында ... ... 2048 ... жіберу ойға қонымсыз.
Дегенмен де мұндай есеп 16 процессорда тиімді түрде жүзеге асырылады, ... ... 32 ... ... шешу үшін өнімділіктің 37%-ын
жоғалту мүмкін болады. Белгілі бір ... ... заңы ... ... параллель емес кодтың үлесіне қатысты бағдарлама ... ... ... ... Бұл ... процессорлар арасындағы
алмасуларға қойылатын шығындарды ескермейді, сондықтан нақты өмірде ... да ... ... ... ... параллельдіктен ажырату – оның
жұмысын жеделдетудің ... бірі ... ... бір ... ... көп ұтысқа ие болуға әбден мүмкін. Айтарлықтай
өзектілікке осы мәселе ... ... ... пен ... жадтың
жылдамдықтары арасындағы үлкен айырмашылықтың салдарынан ие болды. Өкінішке
орай, өте жиі жағдайларда осы ... ... ... ... ... ... ... емес бағдарламаларды параллельдіктен ажыратуға
бекер күш жұмсалуда. Осы жағдайды жеткілікті түрде төмендегі тарау баяндап
береді.
2 ПРАКТИКАЛЫҚ ... ... ... ... ... ... ... жай және параллельді программасы
Сұрыптау дегеніміз – мәліметтерді өңдеу барысында туатын ... бірі және ... оны ... мәндер жиынтығының
элементтерін
монотонды арту немесе кему тәртібімен орналастыруға арналған іс-әрекет
ретінде ... әрі ... ... ... ... болу үшін мәліметтерді арту
бойынша орналастыру мысалында ғана ... ... ... ... ... ... ... жеткілікті түрде
жоғары деп айтуға болады. Мысалы, бірқатар қарапайым ... ... ... қосу ... ... және т.б.) ... қажетті
операциялардың саны реттеуге тиісті мәліметтерге квадратты тәуелділікпен
анықталады:
.
Ал мұдан да тиімдірек алгоритмдер үшін ... ... ... ... жылдам сұрыптау) жұмсалатын еңбек мөлшері мына ... T\sim n \log_2 ... ... сонымен қатар n мәннен құралатын жинақты ... ... ... ... төменгі бағамын береді; аз күш жұмсауды
қажет ететін алгоритмдер есептің дербес нұсқалары үшін ғана ... ... ... үшін ... ... бірнеше процессорларды (p>1)
қолдануға ... Осы ... ... реттеуге кететін ... ... ... ... барысында мәліметтер
процессорларға таратылып, өзара салыстырылады. ... ... ... ... ... ... бұл кезде мұндай жіктеуді ... ... үшін ... үшін ... нөмірлеу жүйесі енгізіледі
және әдетте сұрыптауды ... соң ... кіші ... ... ... процессорлардың мәндерінен асып кетпеуін қадағалаған
жөн. Сұрыптауды жіті талдау проблемасын тереңірек қарастыру мақсатында ... ішкі ... ... ... үшін ... ... асыру
тәсілдеріне баса назар аударатын боламыз. Яғни, нақты ... ... ... ... ЭЕМ ... жадында орналасады.
Көпіршік әдісімен сұрыптаудың қарапайым программасы:
#include
#include
# define k 1000
void main()
{
int N,i,j,pp,arr[k];
coutN;
for(i=0; ...

Пән: Информатика
Жұмыс түрі: Курстық жұмыс
Көлемі: 27 бет
Бұл жұмыстың бағасы: 700 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Орта мектепте программалау негіздерін оқыту68 бет
Мультиспектралды бейнелерді өңдеуде кластеризация алгоритмін зерттеу және өңдеу, параллелизация технологиясын қолдану арқылы бағдарламаның тиімділігін арттыру54 бет
Сызықты Навье – Стокс жүйесі үшін кері есептің шешімінің алгоритмін параллельдеу47 бет
Delphi (дерек қормен жұмыс)11 бет
Delphi дің мультимедиялық мүмкіндіктері12 бет
RDF моделінің синтаксисі33 бет
Аруна баспасы жұмысының ақпараттық жүйесін тұрғызуды негіздеу39 бет
Есепті шығару алгоритмі23 бет
Жерді қашықтан зондтау және гиперспектральді бейнелерді өңдеу алгоритмдері733 бет
Параллельді программалау89 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь