Taqsimlangan algoritmlar vatizimlar

Kompyuter injiniringi fakulteti


Axborot texnologiyalari kafedrasi

“TAQSIMLANGAN ALGORITMLAR VATIZIMLAR”

fanidan


11-15- laboratoriya ishlari
11 – Laboratoriya mashg’uloti. TAQSIMLANGAN ALGORITMLARGA OID MASALALARNI LOYIHALASH.

Zamonaviy multiprocessor mashinalari o'nlab va yuzlab protsessorlar, minglab protsessorlarga ega. Lekin bunday noyob mashinalar juda qimmat, maxsus superkompyuter markazlarida yoki harbiy tashkilotlarda o'rnatiladi va odatdagi foydalanuvchilar uchun doimo mavjud emas. Shu bilan bir qatorda, global aloqa tarmoqlari bilan bog'langan va shaxslar va turli tashkilotlarga tegishli alohida kompyuterlardan foydalanish. Kompyuterlar nisbatan kam ishlashga ega bo'lishi mumkin, biroq tarmoqdagi bir necha o'nlab yoki yuz minglab kompyuterlarning bitta masalani hal qilish uchun bir xil superkompyuterning ta'sirini yaratadi, lekin ehtimol yanada kuchli.

Yuqorida keltirilgan parolni hal qilish uchun ishlatiladigan bu tarqalgan kompyuter tizimi. Bu "qattiq" tizim emas edi - kompyuterlar ixtiyoriy ravishda ishlatilgan, istalgan vaqtda har qanday kompyuter tizimdan chiqishi mumkin. Biroq, yangi kompyuterlar kabi mavjud bo'lganlarga qo'shilish mumkin. Kompleks masalalarni hal qilish uchun global kompyuterlar tarmog'idan foydalanish g'oyasi va mos keluvchi texnologiyaga "Grid" nomi berildi.
Agar veb-global axborot resurslariga kirish imkoni bo'lsa, Grid global hisoblash (qayta ishlash) manbalariga kirishni ta'minlashi kerak. Griddan foydalanishning asosiy loyihalari hozirgi vaqtda elementar zarracha fizikasida eksperimental ma'lumotlarning katta soni (terrabaytlar, pentabaytlar), astronomiyada kuzatuvlar, biologiyada inson genomining dekodlanishi bilan bog'liq.
Distributed problem, turli xil nuqtalardan manba ma'lumotlarini to'playdigan va hisoblash natijalarini turli nuqtalarga yuboradigan taqsimlangan algoritm bilan hal etiladi. Algoritmni taqsimlashda qo'shimcha omil kosmosdagi turli nuqtalarda joylashgan bir necha ijrochilarning mavjudligi (tarqalgan ijrochi) bo'lishi mumkin.
Ma'lumki, algoritm asl ma'lumotlarga, shuningdek, qidiruv ma'lumotlarga va ma'lumotlar bazalari bilan ishlaydigan katta tizimlarda ishlaydi. Taqsimlangan algoritm uchun tabiiy ravishda savol tug'iladi: bu ma'lumotlarni qanday qilib tashkil etish kerak - jamlangan yoki tarqalgan ma'lumotlar bazasi shaklida?
Tarqatilgan algoritmlarning bir turi protokollardir. Protokol, kamida ikkita aloqa kanali bilan ajratilganligi bilan tavsiflanadi. Har tomondan, Ak (mahalliy) (joyga jamlanganda) algoritmi bajariladi. Mahalliy algoritm A1 ishni davom ettirish uchun boshqa A2 mahalliy algoritmidan ma'lumotlarni talab qiladigan vaqtga qadar bajariladi. Mahalliy A2 algoritmiga havola orqali ma'lumot so'rovini yuboradi. Algoritm A2 xabarni aloqaga yo'naltirish orqali javob beradi. Shundan so'ng mahalliy A1 algoritmi o'z ishini davom ettirmoqda.
Protokollar odatda texnik rol o'ynaydi va uzoq ob'ektlar orasida ma'lumotlarni qabul qilish / uzatish usullarini o'rnatish uchun ishlatiladi. Hisob-kitoblarga ko'ra, mahalliy algoritmlar - protokol qismlari murakkab emas.
Maxsus tarqatiladigan algoritmlar kriptografik protokollardir. Ular bir yoki har ikkala tomon tomonidan maxfiy ma'lumot almashish va boshqa shunga o'xshash maqsadlar uchun da'vo qilayotgan shaxslar ekanligini isbotlash uchun mo'ljallangan.
Eng oddiy kriptografik protokollardan biri - taqsimlangan algoritmlarni ko'rib chiqing.
Kosmosdagi turli nuqtalarda O1 va O2 ikkita ob'ekt bor, ularning har biri umumiy vazifaning P qismini (P1 yoki P2) echib oladi. Biroq, umumiy muammolarni hal qilish istagidan tashqari, ob'ektlar ham o'zlarining maxsus vazifalari, Q1 va Q2ga ega. Shunday qilib, ob'ekt O1 bir vaqtning o'zida P1 va Q1 muammosini echadi va O2 ob'ekti P2 va Q2 muammolarini echintirib. Agar P1 va P2 vazifalari mos va o'zaro bir-birini to'ldirsa, Q1 va Q2 vazifalari bir-biriga zid keladi.
Shuning uchun O1 va O2 ob'ektlari hamkorlik qiladilar, biroq ayni paytda ular raqobatlashadi. Aytish mumkinki, ob'ektlar raqobatlashadi, lekin hamkorlik qilishga majbur. Bu Vining ob'ekti uchun muhim bo'lgan Pi yoki Qi vazifalaridan qaysi aksinani qanday joylashtirishingizga bog'liq.
Ta'kidlangan holat juda keng tarqalgan. Universitetlar mutaxassislarni tayyorlashni takomillashtirish muammosini hal qilishdan manfaatdordirlar va bu vazifada ular hamkorlik qilmoqdalar. Shu bilan birga, universitetlar har yili qobiliyatli talabalar uchun raqobatlashadi. Ilmiy tashkilotlar tez-tez o'z manfaatlarini o'zaro aloqada (fanlarning kesishishida) birgalikda tadqiqotlar olib boradilar. Lekin ular moliya taqsimotida raqobatlashadilar. Firmaning ikkita bo'linmasi firma umumiy maqsadlariga erishish uchun ishlaydi, lekin ularning har biri firma ichida boshqa bo'linishdan ko'ra ko'proq rivojlanishni istaydi. Umumiy holda, do'stlar, raqiblar. Qisman raqobat.
Bizning muammo, ob'ektlar O1 va O2 muammoni P. hal manfaatlari bir umumiy murosaga kelgan teng ikki yechimlari (vazifa R jihatidan) bor deylik. rozi O2 ob'ektini - biri ham ob'ekt O1 va boshqa mezbonlik. So'ngra ob'ektlar O1 va O2 qur'a tashladilar qaror qildi. Bu amalga oshirilishi mumkin: a kolba ichiga qog'oz yo'l, qog'oz o'z parcha har qaror yozish bingo va amalga olish uchun qog'oz parcha biriga o'ting. Bu murosaga hal bo'ladi.
Murakkablik darajasi ob'ektlar O1 va O2 bir-biridan juda katta masofada ekanligi, va bingo bilan amaliyotlaridan amalga oshirish uchun mumkin emas.
Lotereya bilan ishlash jarayoni bir joyda amalga oshiriladi, bu yo'naltirilgan tizim uchun mumkin. Bizning tizimimiz taqsimlangan. Lotereya protsedurasi O1 ob'ektini bajarishi va natijani O2 obyektiga etkazishi mumkin, ammo O2 obyekti O1 ob'ektiga to'liq ishonmaydi. Hatto teledasturni efirga uzatish ham aniq dalil emas - bu mohirona tahrirlangan yozuv bo'lishi mumkin.
Chiqish quyidagicha. Qarorlarning biri 0 raqamiga, ikkinchisini esa 1 raqamiga qo'ying. Ob'ektlarning har biri bir-biridan mustaqil ravishda 0 dan 99 gacha bo'lgan oraliqdagi raqam sonini bildirishi kerak. So'ngra ob'ektlar soni ni o'zgartiradi va n1 + n2 (mod 2 ). Bu yechim bo'ladi, ya'ni. 0 yoki 1 raqami.
Birgalikda bir vaqtda raqamlarni bir-biriga moslamalarni yuborish. Biri birinchi navbatda o'z raqamlarini yuboradi va foydasiz holatda bo'ladi.
Misol uchun, O1 n1 raqamini "1" yechimida g'amxo'rlik qiluvchi O2 ob'ektiga jo'natdi. Keyin O2, n1 ni bilib, o'zgaruvchan n2 ga nisbatan n1 + n2 (mod 2) = 1 tenglamasini echadi va O1 ni n2 qiymatini topadi. Tenglamani echish deyarli vaqt topa olmaydi: O1 dan teng sonli raqamni olish, O2 ning g'alati va aksincha javob berish kerak.
Bu adolatsizlikni yo'q qilish kerak. Shu bilan birga, har holda, xabar almashish taraflaridan biri birinchi navbatda o'z raqamini yuboradi. Ikkinchisining "javobni tanlash" uchun etarli vaqti yo'qligi uchun kerak.
O1 va O2 ob'ektlari masofani masofadan turib "lotereya" larning butun amaliyoti bir necha daqiqada yakunlanishi kerakligiga rozi bo'lishi mumkin. Bir vaqtning o'zida ikkala ob'ekt ham javobni tanlab olish superkompyuterning bir necha soat ishlashini talab qilsa, u holda bu echim boshqa tomondan "tweaked" emasligiga ishonch hosil qilishi mumkin. Kalkulyatorda bunday vaqt parametrlarini ta'minlash uchun f (x) funktsiyasini ishlatish kerak, uning qiymati y = f (x) ma'lum argüman x bilan nisbati bilan hisoblash mumkin.
Ammo f (x) = y tenglamasini yechish uchun, ya'ni, noma'lum x ni ma'lum bir qiymatda tezda topib bo'lmaydi. Bundan tashqari, bu tenglamani echish uchun matematik usullar ma'lum emasligi, buning uchun to'liq ro'yxatga olish yoki murakkablikda unga o'xshashlik mavjud emas. Albatta, f (x) funksiyasining ta'rifi domen juda katta bo'lishi kerak, buning uchun qidiruvni bajarish deyarli mumkin emas. 0 va 1 elementlarining maydoni kichik bo'lib, 0dan 99gacha bo'lgan maydon ham kam. Siz operatsiya qilishingiz kerak bo'lgan integerlar kasrda 150-200 raqamdan kam bo'lmasligi yoki ikkilik notada kamida 512 bit bo'lishi kerak. Bunday raqamlar "uzoq" deb nomlanadi.
F (x) va h (z, v, w) ikkita murakkab tersinir vazifa bo'lsin. H (z, v, w) funktsiyasida dastlabki ikkita argument uzoq raqamlar, uchinchisi esa bitwise. F va h funktsiyalari O1 va O2 ob'ektlarida ma'lum va ular ushbu funktsiyalarning qiymatlarini argumentlarning berilgan qiymatlari uchun tez hisoblash uchun o'z algoritmlariga ega, lekin ular bu funktsiyalarni tezda qanday qaytarish kerakligini bilmaydi. tenglamalarni echish

1.