Лекция 2 Моделирование и анализ параллельных вычислений
Download 85.69 Kb.
|
3mar
- Bu sahifa navigatsiya:
- Guruch. 2.4.
- Barcha qisman summalarni hisoblash
- S ning nusxasi yaratiladi
£
V -V x VA. da G XX XX 5 6 7 8 X , X 2 X , X 4 xxxxx xxx, 9 10 11 12 13 14 15 16 Guruch. 2.4. O'zgartirilgan kaskad yig'ish sxemasi birinchi bosqichni bajarish uchun tizimga kirish talab qilinadi p\={n/ logindan foydalanganda parallel operatsiyalar ) protsessorlar. Ikkinchi bosqichni bajarish uchun sizga kerak logi(n/log 2 n) pi=(n/log 2 n)/2 uchun parallel amallar protsessorlar. Natijada, yig'ishning ushbu usuli quyidagi ko'rsatkichlar bilan tavsiflanadi : T p =2log 2 n, p=(n/log 2 n). Olingan hisob-kitoblarni hisobga olgan holda , o'zgartirilgan kaskad sxemasining tezlashuvi va samaradorligi ko'rsatkichlari quyidagi munosabatlar bilan belgilanadi: Sp=T\/T p ={n-\)/2log 2 n, Ep=T\/pTp=(n-l)/{2{n/log 2 n)log 2 n) ={n-\)/2n. Ushbu hisob-kitoblarni an'anaviy kaskad sxemasi ko'rsatkichlari bilan taqqoslab shuni ta'kidlash mumkinki, taklif qilingan parallel algoritm uchun tezlik 2 baravar kamaydi, ammo yangi yig'ish usulining samaradorligi uchun asimptotik nolga teng bo'lmagan bahoni olish mumkin. quyida E p \u003d (n - 1) / 2uW), 25, limEp -\u003e 0,5 da Shuni ham ta'kidlash mumkinki, ko'rsatkichlarning ushbu qiymatlariga 5-teoremada belgilangan protsessorlar soni bilan erishiladi. Bundan tashqari, shuni ta'kidlash kerakki, an'anaviy kaskad sxemasidan farqli o'laroq, o'zgartirilgan kaskad algoritmi iqtisodiy jihatdan maqbuldir . chunki bu holatda hisob-kitoblarning narxi C p \u003d p T p ={n/log 2 ri){2log 2 ri) algoritmning bajarilish vaqtiga proportsionaldir . Barcha qisman summalarni hisoblash Keling , qiymatlar ketma-ketligining barcha qisman summalarini hisoblashning asl muammosiga qaytaylik va hisob-kitoblarni ketma-ket va parallel tashkil etishning mumkin bo'lgan usullarini tahlil qilaylik. Skayar kompyuterda barcha qisman yig'indilarni hisoblashni bir xil miqdordagi operatsiyalar (!) bilan odatiy ketma-ket yig'ish algoritmi yordamida olish mumkin . T\=p. Parallel bajarishda kaskad sxemasidan aniq foydalanish istalgan natijalarga olib kelmaydi; Samarali parallellashtirishga erishish muammolarni hal qilish uchun yangi parallel yo'naltirilgan algoritmlarni ishlab chiqish uchun yangi yondashuvlarni (hatto ketma-ket dasturlashda tengi yo'q) talab qiladi. Shunday qilib, barcha qisman yig'indilarni topishning ko'rib chiqilayotgan muammosi uchun log 2 n natijalarini beruvchi algoritm. parallel operatsiyalar (umumiy summani hisoblashda bo'lgani kabi) quyidagicha bo'lishi mumkin (2.5-rasmga qarang, shuningdek [22]): hisob-kitoblar boshlanishidan oldin S ning nusxasi yaratiladi yig'ilgan qiymatlar vektorlari (<5=x); keyin yig'indining har bir iteratsiyasida /, \4Klog2fi, yordamchi vektor Q hosil bo'ladi S vektorini siljitish orqali 2 m pozitsiyalar bilan (chapdagi siljish paytida chiqarilgan pozitsiyalar nol qiymatlarga o'rnatiladi); algoritmning takrorlanishi S vektorlarni yig'ishning parallel operatsiyasi bilan tugaydi va Q. Guruch. 2.5. Barcha qisman summalarni hisoblash uchun parallel algoritm sxemasi (qiymatlari *S/_/ i dan o'rtacha qiymatlar yig'indisi jga _ raqamli ketma-ketlik elementlari) Hammasi bo'lib, parallel algoritm log 2 n da ishlaydi parallel qo'shish operatsiyalari. Algoritmning har bir iteratsiyasida n ta skalyar qo‘shish amallari parallel ravishda bajariladi va shu bilan skalyar amallarning umumiy soni qiymat bilan aniqlanadi. Download 85.69 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling