6 -MAVZU: RAQAMLI ISHLOV BERISH UNUMDORLIGINI
BAHOLASH USULLARI.
Reja
1.
Parallel algoritmlar analizining prinsiplari.
2.
PRAM modeli.
3.
Unumdorlikni baholash.
4.
Amdal qonuni
a.
Ma’lumotlarni parallelashtirish
b.
Buyruqlarni parallelashtirish
Kalit so'zlar.
Multidastur, dastur, buyruq, oqim, ma’lumot,
operatsion
tizim, mashina buyruqlari, registr xotirasi, razryad,
protsessor bloki, shoxcha,
konveyer, xotira modullari, ajratilgan xotira, konver, multikompyuter,
taqsimlgan xotira, protsessor, massiv parallel, kesh, supkonver, kontroller, ovoz
kontrolleri,
tarmoq interfeysi, sovutish tizimi, graf, utilitalar,
operatsiya,
matritsa, yacheyka.
1.Parallel algoritmlar analizining prinsiplari
Parallel algoritmlarning bajarilishida ikki vazifa – algoritmlarning dastur
effektivligiga qanday ta’sir etishi va turli xil
algoritmlarning analizini
o‘rganishdir. Ba’zi bir zamonaviy dasturiy ta’minotlarga e’tibor qilsak ularning
ayrim tuzuvchilari na dasturning ishlash effektivligiga va na xotiraning aql bilan
ishlatilishiga e’tibor qilishadi. Ularning fikricha, dastur ko‘p
joy olsa,
foydalanuvchi qo‘shimcha xotira sotib olishga majbur bo‘ladi yoki yangi tezroq
ishlaydigan kompyuter sotib oladi.
Parallel algoritmlar bilan ishlashda bizni ikki tushuncha qiziqtiradi:
1.
Tezlanish koeffitsienti
2.
Qiymati
Parallel algoritmlarning tezlanish koeffitsienti optimal ketma-ket
algoritmning qanchalik tez ishlashini ko‘rsatadi. Ma’lumki optimal tartiblash
algoritmi
O
(
N
log
N
) ta operatsiyani talab qiladi.
O
(
N
) murakkablikdagi parallel
tartiblash algoritmining tezlanish koeffitsienti
O
(log
N
) ni tashkil qiladi.
Bizni qiziqtiradigan ikkinchi tushuncha – parallel
algoritmning qiymati
bo‘lib, uni biz ishlatilayotgan protsessorlar sonining algoritm murakkabligiga
ko‘paytmasi orqali aniqlaymiz. Agar bizning holatda parallel tartiblash algoritmi
O(N)
ta operatsiya uchun kiruvchi yozuvlar soniga teng protsessorlarni talab
qilsa, uning qiymati
O(N^)
ga teng. Bu parallel tartiblash algoritmi qimmatliroq
ekanligini bildiradi, ya’ni bitta protsessordagi ketma-ket tartiblash algoritmining
qiymati uning murakkabligi bilan mos keladi va
O
(
N
log
N
) ga teng.
2. PRAM modeli
Ketma-ket tartiblash algoritmida hech qanday o‘xshash cheklovlar yo‘q.
Bizni ko‘proq protsessorlar soni kiruvchi ma’lumotlar
potensial hajmidan
yetarlicha kam bo‘lgan va bu son kirish uzunligining ortishi bilan kattalashishni
talab qilmaydigan parallel tartiblash algoritmlari qiziqtiradi.
