2. 1-§. Taqsimlangan tizimlar arxitekturasi 1

3.1-§. Taqsimlangan tizimlar uchun "bo'l va egalla" algoritmi

G. Coulouris, J. Dollimore va T. Kindberglarning "Taqsimlangan tizimlarga kirish" nomli nashrida tarqatilgan tizimlar haqida keng qamrovli kirishni taqdim etadi va aloqasinxronizatsiya, xatolarga chidamlilik va xavfsizlik kabi mavzularni qamrab olgan.
N.Santoroning "Taqsimlangan algoritmlar" tadqiqot ishi taqsimlangan algoritmlarni loyihalash va tahlil qilishga qaratilgan bo'lib, xabarlarni uzatish, sinxronlashtirish, konsensus va yetakchilarni tanlash kabi mavzularni qamrab oladi.
M.G. Arnold, M. Allen va J.E. Gustedt tomonidan yozilgan "Parallel hisoblash: printsiplar va amaliyot" kitobda parallel hisoblash uchun amaliy qo'llanma beradi va parallel arxitekturalar, parallel algoritmlar va parallel dasturlash modellari kabi mavzulari yoritilgan.
T.H.Cormen, C.E.Leiserson, R.L.Rivest va C.Steinlarning "Algoritmlarga kirish" nomli klassik darsligi algoritmlarning keng doirasini, jumladan, bo'lish va zabt etish algoritmlarini o'z ichiga oladi va algoritmni loyihalash va tahlil qilish uchun ajoyib kirishni taqdim etadi.
D.E.Keyes va A.B.Kahnglarning "Parallel va taqsimlangan hisoblash: raqamli usullar" kitobida chiziqli algebra va optimallashtirish kabi raqamli usullar uchun parallel va taqsimlangan algoritmlarni loyihalash va amalga oshirishga qaratilgan.
“Bo'l va egalla” algoritmi – muammolarni kichikroq kichik muammolarga bo‘lish, har bir kichik muammoni mustaqil yechish, so‘ngra yakuniy yechimni olish uchun yechimlarni birlashtirish yo‘li bilan yechish usuli. Algoritm, ayniqsa, parallellashtirish uchun mos keladi va katta va murakkab muammolarni hal qilish uchun taqsimlangan tizimlarda ishlatilishi mumkin.
“Bo'l va egalla” algoritmining asosiy bosqichlari quyidagilardan iborat:
Bo'lish: Muammoni kichikroq kichik muammolarga ajrating. Har bir kichik muammo o'lchami bo'yicha dastlabki masaladan kichikroq bo'lishi va dastlabki masala bilan bir xil turdagi bo'lishi kerak.
Egallash: Har bir kichik muammoni mustaqil hal qiling. Bu taqsimlangan tizimdagi turli mashinalarda parallel ravishda amalga oshirilishi mumkin.
Birlashtirish: Asl muammoning yakuniy yechimini olish uchun kichik muammolarning echimlarini birlashtiring.
Oddiy optimallashtirish masalasini hal qilish uchun taqsimlangan tizimda bo'lish va zabt etish algoritmidan qanday foydalanish mumkinligiga misol:
Bo'lish: [0, 2] oralig'ini to'rtta pastki intervalga bo'ling: [0, 0,5], [0,5, 1], [1, 1,5] va [1,5, 2].
Conquer: Har bir sub-intervalni taqsimlangan tizimdagi boshqa mashinaga tayinlang. Har bir mashinada mahalliy optimallashtirish algoritmi yordamida sub-interval ichida maqsad funksiyasining maksimal qiymatini qidiring.
Birlashtirish: Har bir mashinadan yechimlarni to'plang va yakuniy yechim sifatida maqsad funktsiyasi qiymati eng yuqori bo'lganini tanlang.
Yuqoridagi algoritm C++ da xabarlarni uzatish interfeysi (MPI) yordamida amalga oshirilishi mumkin, bunda har bir mashina sub-intervallar va echimlar haqida ma'lumot almashish uchun boshqalar bilan bog'lanadi. Mashinalar bo'ylab ish yukini muvozanatlash va aloqa yukini kamaytirish uchun kichik intervallar sonini va kichik muammolar hajmini sozlash orqali algoritm yanada optimallashtirilishi mumkin.
Umuman olganda, “Bo'l va egalla” algoritmi taqsimlangan tizimlardagi muammolarni, ayniqsa kichikroq kichik muammolarga bo'linishi mumkin bo'lgan muammolarni hal qilish uchun kuchli texnikadir. Yechish jarayonini parallellashtirish orqali algoritm muammolarni bitta mashinadan ko'ra samaraliroq va tez hal qilish uchun taqsimlangan tizim resurslaridan foydalanishi mumkin.