Lim,fan va innovatsiyalar vazirligi muhammad al-xorazimiy nomidagi toshkent axborot texnologiyalari universiteti

T₁ = min T₁(G) ,
G
keyin berilgan smeta bo'yicha olingan tezlik koeffitsientlari tanlangan algoritmni parallellashtirish samaradorligini tavsiflaydi. Ko'rib chiqilayotgan hisoblash masalalarini parallel yechish samaradorligini baholash uchun ketma-ket hal qilish vaqtini turli xil ketma-ket algoritmlar bo'yicha baholash kerak, ya'ni qiymatdan foydalanish kerak.

bu erda minimal operatsiya berilgan masala uchun barcha mumkin bo'lgan ketma-ket algoritmlar to'plami ustidan olinadi.
Biz parallel algoritmni bajarish vaqtini baholash xususiyatlarini tavsiflovchi nazariy bayonotlarni ko'rib chiqamiz (qarang: Bertsekas va Tsitsiklis (1989)).
Teorema 1. Algoritmni hisoblash sxemasining maksimal yo'l uzunligi parallel algoritm bajarilishining minimal mumkin bo'lgan vaqtini belgilaydi, ya'ni.

Teorema 2. Algoritmni hisoblash sxemasida ma'lum bir chiqish cho'qqisi uchun har bir kirish cho'qqisidan yo'l bo'lsin. Bundan tashqari, sxema cho'qqilarining kirish quvvati (kiruvchi yoylar soni) 2 dan oshmasligiga ruxsat bering. Keyin parallel algoritmni bajarishning minimal mumkin bo'lgan vaqti pastdan qiymat bilan cheklanadi.

Bu erda n - algoritm sxemasidagi kirish uchlari soni.
Teorema 3. Ishlatilgan protsessorlar soni kamaysa, algoritmni bajarish vaqti protsessorlar sonining kamayishiga mutanosib ravishda ortadi, ya'ni.

Teorema 4. Qo'llaniladigan protsessorlarning istalgan soni uchun parallel algoritmni bajarish vaqti uchun quyidagi yuqori baho to'g'ri bo'ladi:

Teorema 5. Algoritmning bajarilish vaqti T mumkin bo'lgan minimal vaqt bilan solishtiriladi
Agar protsessorlar soni p ~ T1 / T∞ tartibida bo'lsa, aniqrog'i,

bolishi mumkin
Agar protsessorlar kamroq bo'lsa, algoritmni bajarish vaqti berilgan protsessorlar soni bilan eng yaxshi hisoblash vaqtidan ikki martadan ortiq bo'lishi mumkin emas, ya'ni.

Ushbu teoremalar parallel algoritm yaratish qoidalariga oid quyidagi tavsiyalar uchun asos yaratishga imkon beradi:
1) Algoritmni hisoblash sxemasini tanlashda mumkin bo'lgan minimal diametrli grafikdan foydalanish kerak (1-teoremaga qarang);
2) Parallel bajarish uchun protsessorlarning samarali soni p ~ T1 / T∞ qiymati bilan aniqlanadi.
3) Parallel algoritmni bajarish vaqti yuqoridan 4 va 5 teoremalarda berilgan qiymatlar bilan chegaralanadi.
Demak, hisoblash modeli "operandlar-operandlar" grafigi sifatida tavsiflanadi, bu esa tanlangan muammolarni hal qilish algoritmlarida mavjud bo'lgan ma'lumotlarga bog'liqliklarni tavsiflash uchun ishlatilishi mumkin. Model asiklik yo'naltirilgan grafikga asoslangan bo'lib, uning uchlari operatsiyalarni ifodalaydi va yoylar operatsiyalarning ma'lumotlarga bog'liqligiga mos keladi. Agar bunday grafik mavjud bo'lsa, parallel algoritmni aniqlash uchun bajarilgan operatsiyalarning protsessorlar o'rtasida taqsimlanishi belgilangan jadvalni o'rnatish kifoya.
Bunday modellar yordamida hisob-kitoblarni ifodalash ishlab chiqilayotgan parallel algoritmlarning bir qator xarakteristikalarini analitik tarzda olish imkonini beradi. Ushbu xususiyatlar qatorida bajarish vaqti, optimal jadval sxemasi, muammolarni hal qilish usullarini qayta ishlashning maksimal tezligini baholash mavjud. Nazariy hisob-kitoblarni soddalashtirish uchun cheksiz miqdordagi protsessorlarga ega parallel tizim sifatida parakompyuter tushunchasi ko'rib chiqiladi.
Parallel hisoblash usullarining samaradorligini baholash uchun biz parallel dasturlash nazariyasi va amaliyotida keng qo'llaniladigan tezlik va samaradorlik kabi asosiy sifat ko'rsatkichlarini ko'rib chiqdik. Tezlashtirish, agar bir nechta protsessor ishlatilsa, muammoni necha marta tezroq hal qilishini ko'rsatadi. Samaradorlik hisoblash tizimining protsessorlari amalda qo'llaniladigan vaqt qismini tavsiflaydi. Hisoblashlarning narxi ham ishlab chiqilgan algoritmning muhim xarakteristikasi hisoblanadi. U parallel muammolarni hal qilish vaqti va foydalanilgan protsessorlar sonining mahsuloti sifatida aniqlanadi.
Modellarning qo'llanilishi va parallel algoritmli tahlil usullarini ko'rsatish uchun biz raqamli qiymatlar ketma-ketligining qisman yig'indilarini topish masalasini ko'rib chiqdik. Misol murakkablikni parallellashtirishning ketma-ket algoritmi muammosini ko'rsatishga yordam beradi. Murakkablik paydo bo'ladi, chunki bu algoritmlar dastlab parallel hisoblash tartiblari imkoniyatiga yo'naltirilmagan. "Yashirin" parallelizmni ko'rsatish uchun biz dastlabki ketma-ket hisoblash sxemasini konvertatsiya qilish imkoniyatini ko'rsatdik va konvertatsiya natijasida olingan kaskad sxemasini tasvirlab berdik. Xuddi shu muammoni ko'rib chiqib, biz bajarilgan hisob-kitoblarda katta parallellikka erishish uchun ortiqcha hisob-kitoblarni kiritish imkoniyatini ko'rsatdik.
Xulosa qilib biz samaradorlik mezonlarining maksimal erishish mumkin bo'lgan qiymatlarini baholashni yaratish muammosini ko'rib chiqdik. Bunday baholarni yaratish uchun Amdal qonunidan foydalanish mumkin, bu bizga muammolarni hal qilish usullarida mavjud ketma-ket (parallellashtirilmagan) hisoblarni hisobga olish imkonini beradi. Gustafson-Barsis qonuni muammoning murakkabligi oshishi bilan parallel hisoblashlar qanchalik samarali tashkil etilishini tavsiflash uchun foydalaniladigan masshtabli tezlikni baholashni qurishni nazarda tutadi. o'rtasidagi bog'liqlikni aniqlash uchun muammoning murakkabligi va protsessorlar soni, ularning kuzatilishi parallel hisoblashning zaruriy samaradorlik darajasini ta'minlaydi, biz iz samaradorlik funktsiyasi tushunchasini kiritdik.


Xulosa
"Operatsiyalar-operandlar" grafli hisoblash modeli, matematikda hisoblash amallarini tushunish uchun qulay usul hisoblanadi. Bu modelda, hisoblash amalining operandlari va ularni birlashtiruvchi operatsiyalar, grafda yoritiladi. Bu usul hisoblash amalini bir qatorda bajarishga imkon beradi, shuningdek, paralel hisoblash uchun qulaydir.Bu modelning asosiy elementlari quyidagilardan iborat:
Operandlar: Bu, hisoblash jarayonida ishlatiladigan raqam, xarif yoki boshqa qiymatlar. Grafda, operandlar node (to'p) deb ataladi.
Operatsiyalar: Bu, operandlarni birlashtiradigan amallar. Grafda, operatsiyalar alohida to'plar (node) sifatida ko'rsatiladi va ularni bog'liq operandlarga bog'lash uchun to'plar orqali alohida bo'g'lamalar (edge) tuziladi.
Hisoblash tartibi: Operatsiyalar operandlarga qanday tartibda amal qilishi kerakligini belgilaydi. Bu tartibni o'zgartirish uchun qo'shimcha to'plar yoki boshqa elementlar ishlatilishi mumkin.
Quyidagi misol, "operatsiyalar-operandlar" grafli hisoblash modelining ko'rsatilishidir.Operatsiyalar-operandlar grafli hisoblash modeli.
Ushbu misolda "a", "b", "c" va "d" raqamlari operandlarga mos keladi, "+" va "*" amallari esa operatsiyalarga. Grafda ko'rsatilgan hisoblash tartibi quyidagicha:
"b" va "c" operandlari "+' operatsiyasi bilan qo'shiladi.
"a" operandiga "d" qiymati ko'rsatiladi.
"a" va ("d" + "c") qiymatlari "*' operatsiyasi bilan ko'paytiriladi.
"b" va "c" qiymatlari "+" operatsiyasi bilan qo'shiladi.
("a" * ("d" + "c")) va ("b" + "c") qiymatlari "*' operatsiyasi bilan ko'paytiriladi.
Shu tartibda hisoblash bajariladi va natija 78 bo'ladi. Bu model, matematik, kiber-xavfsizlik, matematik hisoblashlari va boshqa sohalarda qo'llaniladi.