N kompyuter tomonidan echilishi kerak bo'lgan ixtiyoriy hisoblash muammosi bo'lsin

1.1 teorema. CRCW-PRAM ( p ) da n hisoblash masalasini yechishning har bir algoritmi EREW-PRAM ( p ) da n ni yechishning eng tezkor algoritmidan ko'pi bilan O ( log p ) - marta tezroq.
Tasdiqlovchi fikr. Biz birinchi navbatda CONSISTENT-CRCW-PRAM( p ) ning bir vaqtning o'zida bir xil joyga yozishlari EREW-PRAM( p ) tomonidan O ( log p ) bosqichlarida bajarilishi mumkinligini ko'rsatamiz. Shunday qilib, EREW-PRAM CRCW-PRAMni taqlid qilishi mumkin, sekinlashuv omili O ( log p ) . Keyin biz ushbu sekinlashtiruvchi omil qattiq ekanligini ko'rsatamiz, ya'ni n hisoblash muammosi mavjud bo'lib, uning uchun sekinlashtiruvchi omil aslida 0 ( logp ) . Bunday n , masalan, maksimal tez-tez sonlarni topish masalasidir. □
PRAM modelining dolzarbligi
Biz PRAM modeli nima uchun darhol manzilli, cheklanmagan umumiy xotirani taxmin qilishda haqiqiy emasligini tushuntirdik. Bu, albatta, PRAM modeli parallel hisoblashni amaliy amalga oshirish maqsadlari uchun ahamiyatsiz ekanligini anglatadimi? Javob PRAM modelidan nimani kutayotganimizga yoki umuman olganda, nazariyaning rolini qanday tushunishimizga bog'liq.
n muammosini hal qilish algoritmini ishlab chiqishga harakat qilsak , bizning harakatlarimiz n ni echishga tayyor bo'lgan amaliy algoritm bilan yakunlanmasligi mumkin . Biroq, dizayn n ga xos bo'lgan narsani ochib berishi mumkin , ya'ni n ning parallellashtirilishi mumkin. Boshqacha qilib aytganda, dizayn n ta kichik muammolarni aniqlashi mumkin, ulardan ba'zilari, hech bo'lmaganda, printsipial ravishda, parallel ravishda hal qilinishi mumkin. Bunday holda, odatda bunday kichik muammolar eng liberal (va real bo'lmagan) PRAM CRCW-PRAMda parallel ravishda hal qilinishi mumkinligini isbotlaydi.
Shu nuqtada 1.1 teoremasining ahamiyati yaqqol namoyon bo'ladi: biz CRCW- PRAMni haqiqiy EREW-PRAM bilan almashtira olamiz va ikkinchisida n ni hal qilamiz . (Bularning barchasi n ni hal qilish tezligining cheklangan degradatsiyasi hisobiga .)
Xulosa qilib aytganda, PRAMning dolzarbligi quyidagi usulda aks ettirilgan:

1. 
   ( p ) modelida n ni yechish uchun P dasturini loyihalashtiring , bunda p n masalaga bog liq bo lishi mumkin . E'tibor bering, CRCW-PRAM uchun P dizayni EREW-PRAM dizaynidan osonroq bo'lishi kutilmoqda, chunki CRCW-PRAMda bir vaqtning o'zida kirish cheklovlari hisobga olinmaydi.
   
2. 
   EREW-PRAM ( p ) da P ni ishga tushiring, u bir vaqtning o'zida bir xil joyga kirishni taqlid qila oladi.­
   
3. 
   P ning EREW- PRAM ( p ) da parallel bajarilish vaqti kamroq real bo'lgan CRCW-PRAM ( p ) da bo'ladiganidan ko'pi bilan O ( log p ) - marta yuqori ekanligini kafolatlash uchun foydalaning .
   

2.