Mavzu: Dinamik parallel hisoblashlar uchun parallel jarayonlarni tashkillash Mundarija

2.4. Kommutativ va komutativ bo'lmagan parallellik

Parallellikning ushbu shakllarini taqsimlash tabiiy savol bilan bog'liq: bir vaqtning o'zida bajarilishi mumkin bo'lgan dastur komponentalari har doim ketma-ket istalgan tartibda bajarilishi mumkinmi. Ushbu savolga javob berish muhim ahamiyatga ega, chunki samolyot resurslari doimo cheklangan va vaziyat bajarilishi tabiiy holat bo'lib, dastur bajarilishida ishlab chiqarilgan va bir vaqtning o'zida ishlashga qodir bo'lgan komponentlar soni samolyotdagi protsessorlar yoki kompyuterlar sonidan ko'pdir. Bunday holda, ushbu komponentlarning bajarilishini buyurtma qilish kerak va tanlangan tartib har doim ham o'zboshimchalik bilan bo'lmasligi mumkin.

Ta'ri: Agar bir vaqtning o'zida bajarilishi mumkin bo'lgan dastur tarkibiy qismlarining o'zboshimchalik tartibini tan olsak, parallellik komutativ deb ataladi. Aks holda, parallellik komutativ emas deb nomlanadi. Agar shartli operator uchun p (x) bo'lsa, u holda f1 (x) else f2 (x), garchi p (x), f1 (x) va f2 (x) bir vaqtning o'zida bajarilishi mumkin bo'lsa-da, agar siz hisoblashni f1 (x) dan boshlasangiz abadiy davom etadi (f1 funktsiyasi x ga taalluqli emas) va p (x) ning qiymati yolg'on va f2 (x) aniqlangan bo'lsa, u holda shartli operatorni to'g'ri bajarish mumkin emas. P (x) ni f1 (x) yoki f2 (x) bilan bir vaqtning o'zida baholash, shuningdek p (x) va keyin f1 (x) yoki f2 (x) ni ketma-ket bajarish to'g'ri.

Vaziyatni to'g'ri hisoblashni ketma-ket shaklga keltirish mumkin bo'lmagan parallel funktsiyalar deb ataladigan vaziyat yanada murakkablashadi. Telefoniyada ma'lum bo'lgan f (g1 (x), g2 (x), g3 (x)) [2] parallel ovoz berish funktsiyasi misolini ko'rib chiqing, agar u g1 (x), g2 (x) va g3 qiymatlarini hisoblashda aniqlansa. (x) ulardan istalgan ikkitasi aniqlangan va teng va bu holda f (g1 (x), g2 (x), g3 (x)) funktsiyasining qiymati ulardan biridir; aks holda, funktsiya qiymati aniqlanmagan. F (g1 (x), g2 (x), g3 (x)) qiymatini hisoblashda g1 (x), g2 (x) va g3 (x) funktsiyalar qiymatlarini parallel hisoblash tabiiy va oddiy ketma-ket hisoblashgacha kamayishi aniq. har qanday tartibdagi qiymatlar natijani kafolatlamaydi. Ushbu qiymatlardan birini hisoblash aniqlanmagan va cheksiz davom etadigan, qolgan ikkitasi aniqlangan va teng bo'lgan holatni ko'rib chiqish kifoya. Masalan, bir vaqtning o'zida yoki kvazalallel hisoblash g1 (x), g2 (x) va g3 (x) qiymatlarni hisoblash vaqtini taqsimlash orqali f (g1 (x), g2 (x), g3 (x)) funktsiyalar qiymatlarini to'g'ri hisoblanishini ta'minlashi mumkin. Bunday funktsiyalarni ketma-ket yoki parallel tillarda dasturlash alohida yondashuvni talab qiladi. FPTL funktsional tilida bu kabi parallel funktsiyalarni ko'rsatish va to'g'ri hisoblash muammo tug'dirmaydi. FPTL-da qisqartirilgan ovoz berish funktsiyasi (g1 * g2) .eq®g1ÅÅ Å (g2 * g3) .eq®g2Å (g1 * g3) .eq®g3 sifatida ifodalanishi mumkin, bu erda eq argumentlarning tengligini tekshirish uchun ikkilik funktsiya.

FPTLning operatsion semantikasi f1 va f2 ortogonal funktsiyalarining b-tarkibi bilan olingan f1Åf2 funktsiyasining qiymatini hisoblashda (f1 ff2 parallel funktsiya ekanligiga e'tibor bering), f1 (x) yoki f2 (x) qiymatlarni hisoblashni noma'lum muddatga qoldirmaslik kerakligini talab qiladi. ularga protsessor vaqtini navbat bilan ajratish orqali erishiladi. Bundan tashqari, parallel funktsiyalar komutativ bo'lmagan parallellikka ega funktsiyalar deb tasniflanadi. Kutilayotgan parallellikdan farqli o'laroq, vaqt o'tishi bilan bajarilishi kerak bo'lgan dastur tarkibiy qismlarining qiymatlarini keyinga qoldirish mumkin bo'lsa, parallel funktsiyalar uchun, yuqorida aytib o'tilganidek, bu dastur bajarilishining natijasi umuman olinmasligiga olib kelishi mumkin.