Оқулық Қазақстан Республикасы Білім және ғылым министрлігі бекіткен Алматы, 2011
жүктеу/скачать 2,81 Mb. Pdf көрінісі
|
duisembiev-parallel-esep
| Бекітілім 1.2.3
Берілген функция n айнымалыға тәуелді болсын және аргументтер саны р-дан аспайтын операциялардың шектеулі санының суперпозициясы ретінде берілсін. Оның мәндері осы операцияларды пайдаланатын қандай да бір алгоритмнің көмегімен есептелінеді делік. Егер деректердің енгізілуі ескерілмесе және алгоритмнің биіктігі s – ке тең болса, онда s ≥ log p n. Енді алгоритм графының канондық параллельдік формасын қарастырайық. Нӛлдік яруста, кіріс айнымалыларының енгізу мәндеріне сәйкес келетін шыңдар (тӛбелер) орналассын. Соңғы s-ші яруста бір ғана шың орналасады. Сонымен әрбір шыңдағы кіретін доғалар саны р-дан аспайтындықтан, (s – 1)-ші ярустағы шыңдар саны р-дан аспайды, (s – 2)-ші ярустағы шыңдар саны р 2 -ден аспайды және тағы с.с. Нӛлінші ярустағы шыңдар саны р s –тен аспайды. р s ≥ n болатыны түсінікті, сондықтан s ≥ log p n. Сонымен, егер қандай да бір есеп n кіріс деректерімен анықталса, онда жалпы жағдайда біз биіктігі log n аспайтын оның шешімінің алгоритмі бар болатынына сенім артпауымыз керек. Егер алынған алгоритм биіктігінің реті log α n , α > 0 болса, онда бұндай алгоритмді біз параллельдік есептеу жүйесінде іске асырылу уақытысы жағынан тиімді деп санауымызға болады. Егер, әрине оның іске асырылуының барлық басқа да аспектілерін есепке алмасақ. Вектор у, квадраттық матрица А және реті n болатын х векторының кӛбейтіндісі ретінде есептеледі делік. Егер у i , a ij , x j сәйкес векторлар және матрицаның элеметтері болса, онда кез-келген i үшін n j j ij i x a y 1 Айталық, берілген есептеу жүйесінде n 2 процессор бар болсын. Онда бірінші қадамда a ij x j – дің барлық n 2 кӛбейтіндісін параллель есептеуге, ал 121 одан соң, қосуға арналған екіеселену схемасын пайдаланып, [log 2 n] қадамда у векторының координаталарын анықтайтын барлық n қосындыны параллель есептеуге болады. Олай болса, квадраттық матрица және реті n болатын вектордың кӛбейтіндісін есептейтін алгоритм (биіктігінің реті log 2 n) тұрғыза аламыз. Сонымен қатар, алгоритмнің ені n 2 тең. Процессорлар біркелкі қолданылмайды. Тек бірінші қадамда ғана барлық процессорлар іске араласады. Одан кейін, жұмыс істейтін процессорлардың саны әрбір қадам сайын екі есе азаяды. 1.2.3 бекітіліміне сәйкес, биіктігі кіші болатын алгоритмді тұрғызуға болмайды. Бірақ, логарифмдік биіктікте ені кішірек болатын алгоритмдер кездеседі. Реті n болатын екі матрицаны кӛбейту есебін, бір матрицаның және реті n болатын n тәуелсіз векторлардың n кӛбейтіндісін есептеу есебі деп қарастыруға болады. Мұндағы векторлар ретінде екінші матрицаның бағандары алынады. Егер барлық осы кӛбейтулерді мазмұндалған алгоритм бойынша параллель есептейтін болса, онда алынған алгоритмнің биіктігі log 2 n және ені n 3 тең болады. Тағы да процессорлар біркелкі пайдаланылмайды және тағы да биіктіктігі кіші болатын алгоритмді құрастыруға болмайды, бірақ мұнда да логарифмдік биіктікте ені кішірек болатын алгоритмдер кездеседі. Ал енді келесі жағдайларға назар аударайық. Егер келтірілген алгоритмдерді канондық параллель форма ярустары арқылы іске асыруға талпынып кӛрсек, онда бірдей мәліметтерді кӛптеген процессорларға бір уақытта жіберу қажеттілігі туындайды. Бұндай операцияны ӛте жылдам орындауға болмайды. Сондықтан да нақты жағдайларда мәліметтерді жіберуге кеткен уақыт есептеу процесін айтарлықтай тежейді. Биіктігі ең кіші болатын параллель алгоритмдерді құрастыру, матрица- векторлық қосу және кӛбейтуде ешқандай қиындық тудырған жоқ десе болады. Демек, бұндай алгоритмдерді басқа да матрица-векторлық есептер үшін оңай құрастыруға болады деген ой тууы мүмкін. Бұндай ой әрине дұрыс емес. Қарастырылған алгоритмдер дербес идеалды жағдайларда ғана іске асуы мүмкін. Берілген x жүктеу/скачать 2,81 Mb. Достарыңызбен бөлісу:
|