Оценка эффективности параллельных вычислений

Amdal qonuni

• Panjara bo'yash (300 dona)
• Tayyorgarlik - 30 daqiqa. Parallellashtirib bo'lmaydi
• Rasm (bitta doska) - 1 min. PARALLELLAR
• Tozalash - 30 daqiqa. Parallellashtirib bo'lmaydi

Miqdori rassomlar	Bo'yash vaqti
1	30 + 300/1 + 30 = 360
2	30 + 300/2 + 30 = 210
o'n	30 + 300/10 + 30 = 90
100	30 + 300/100 + 30 = 63
1000	30 + 300/1000 + 30  60
1 000 000	o'ttiz + 300/1000000 + 30  60



Amdal qonuni

• Panjara bo'yash (300 dona)
• Tayyorgarlik - 30 daqiqa. Parallellashtirib bo'lmaydi
• Rasm (bitta doska) - 1 min. PARALLELLAR
• Tozalash - 30 daqiqa. Parallellashtirib bo'lmaydi

Miqdori rassomlar	Bo'yash vaqti
1	30 + 300/1 + 30 = 360
2	30 + 300/2 + 30 = 210
o'n	30 + 300/10 + 30 = 90
100	30 + 300/100 + 30 = 63
1000	30 + 300/1000 + 30  60
1 000 000	o'ttiz + 300/1000000 + 30  60



Amdal qonuni

• Parallel dasturning tezlashishi protsessorlar soniga emas, balki dasturning ketma-ket qismi hajmiga bog'liq.

Protsessorlar soni

Tezlashtirish

Parallel qism

Amdal qonuni

Gustafson qonuni

• Amdahl qonuni protsessorlar soni va dasturning parallel qismining nisbati mustaqil deb hisoblaydi, bu mutlaqo to'g'ri emas.
• Odatda, ma'lumotlarning belgilangan miqdori bo'lgan vazifa boshqa protsessorlar sonida (akademik tadqiqotlardan tashqari) bajarilmaydi, lekin ma'lumotlar miqdori protsessorlar soniga qarab o'zgaradi.
• tomonidan tezlashtirish haqida so'rash o'rniga p protsessorlarga o'tishda hisob-kitoblarni sekinlashtirish masalasini ko'rib chiqing bitta protsessor.

J. Gustafson

(1955 yilda tug'ilgan)

Parallel protsessorda ishlaydi

f

1-f

f

(1-f) /p

1

p

Seriyali protsessorda ishlaydi

f '

1-f '

f '

(1-f ') *p

1

p

Seriyali protsessorda gipotetik ishga tushirish

Parallel protsessorda ishlaydi

Gustafson qonuni

• Amdahl qonuni protsessorlar soni va dasturning parallel qismining nisbati mustaqil deb hisoblaydi, bu mutlaqo to'g'ri emas.
• Odatda, ma'lumotlarning belgilangan miqdori bo'lgan vazifa boshqa protsessorlar sonida (akademik tadqiqotlardan tashqari) bajarilmaydi, lekin ma'lumotlar miqdori protsessorlar soniga qarab o'zgaradi.
• tomonidan tezlashtirish haqida so'rash o'rniga p protsessorlarga o'tishda hisob-kitoblarni sekinlashtirish masalasini ko'rib chiqing bitta protsessor.

J. Gustafson

(1955 yilda tug'ilgan)

Gustafson qonuni

Amdal va Gustafson qonunlari

• Amalga oshirish vaqtini qisqartirish va boshqalar hal qilinayotgan muammo hajmining oshishi
• Yechilayotgan masala hajmining oshishi parallel qismning nisbati oshishiga olib keladi, chunki ketma-ketlik qismi o'zgarmaydi.

Algoritmlarning masshtabliligi

• Parallel algoritm deyiladi kengaytiriladigan (kengaytiriladigan)agar protsessorlar soni ortib borayotgan bo'lsa, u protsessor samaradorligining doimiy darajasini saqlab turganda tezlashuvning oshishini ta'minlaydi.
• Masshtablilikni tahlil qilganda, ko'rib chiqing yuqori (umumiy qo'shimcha xarajatlar), protsessorlar o'rtasidagi o'zaro ta'sirni tashkil etish, parallel hisoblashlarni sinxronlashtirish va boshqalar.

Masshtablilik tahlili

• Qo'shimcha xarajatlar
• Muammoni hal qilish vaqti keldi
• Tezlashtirish
• Samaradorlik

Masshtablilik tahlili

• Agar hal qilinayotgan muammoning murakkabligi aniqlansa (T1= const), keyin protsessorlar sonining ko'payishi bilan samaradorlik, qoida tariqasida, qo'shimcha xarajatlarning oshishi tufayli pasayadi. T0...
• Protsessorlar sonini belgilash orqali hal qilinayotgan muammoning murakkabligini oshirish orqali protsessorlardan foydalanish samaradorligini oshirish mumkin. T1...
• Protsessorlar sonining ko'payishi bilan ko'p hollarda hal qilinayotgan muammolarning murakkabligini mos ravishda oshirish yordamida ma'lum darajadagi samaradorlikni ta'minlash mumkin.

Masshtablilik tahlili

• Bo'lsin E=const - bu bajariladigan hisoblash uchun kerakli samaradorlik darajasidir. Keyin
• Bu qaramlik n = F (p) hal qilinayotgan muammoning murakkabligi va protsessorlar soni o'rtasida chaqiriladi izo-samaradorlik funktsiyasi (iz samaradorlik funktsiyasi).

Xulosa

• Parallel algoritm ishlash ko'rsatkichlari
• Tezlashtirish
• Samaradorlik
• Narxi
• Maksimal erishish mumkin bo'lgan parallellikni baholash
• Amdal qonuni
• Gustafson qonuni
• Parallel algoritmning masshtablilik tahlili