Transpozitsiyaga asoslangan rejalashtirish - Transposition-driven scheduling

Transpozitsiyani boshqaradigan rejalashtirish (TDS) a yuklarni muvozanatlash uchun algoritm parallel hisoblash. Da ishlab chiqilgan Vrije Universiteit yilda Amsterdam, Nederlandiya hal qilish algoritmi sifatida jumboq. Algoritm ba'zi bir muammolar va o'lchovlar bilan chiziqli tezlikni ta'minlaydi. U nashr etildi^[1] haqida John Romein, Aske Plaat, Anri Bal va Jonathan Seffer.

Transpozitsiyaga asoslangan jumboq echimi

Jumboqda barcha mumkin bo'lgan o'yinlar tugunlarga mos keladigan taxta joylari, qirralarga to'g'ri keladigan harakatlar, daraxtning ildizi sifatida boshlang'ich pozitsiyasi va barglari kabi echimlar bilan daraxtda aks ettirilishi mumkin. Yo'lda velosipedlar, ya'ni daraxtning yuqorisida allaqachon uchragan pozitsiyani beradigan harakatlar, daraxt tashqarisida qoladi, chunki ular hech qachon optimal echimga olib kelishi mumkin emas.

Ko'pgina jumboqlarda harakatlarning turlicha tartiblanishi jumboqning bir xil pozitsiyasiga olib kelishi mumkin. Oldingi harakatlar echimga ta'sir qilmaydigan jumboqlarda, ikkala yo'l uchun ham echim topish uchun ushbu pozitsiyani faqat bir marta baholashingiz kerak. Bir xil pozitsiyani bir necha bor baholamaslik uchun (va shuning uchun hisoblash davrlarini behuda sarflashi uchun), ushbu turdagi jumboqlarni hal qilish uchun yozilgan dasturlardan foydalaniladi transpozitsiya jadvallari. Transpozitsiya - bu turli xil yo'llar bilan erishish mumkin bo'lgan, ammo bir xil echimga ega bo'lgan jumboq holati. Har safar bunday dastur pozitsiyani baholashni boshlaganida, avval pozitsiya allaqachon baholangan bo'lsa, jadvalga qaraydi. Agar shunday bo'lsa, yechim hisoblangan o'rniga jadvaldan olinadi va ko'p vaqtni tejaydi.

Biroq, parallel hisoblashda ushbu yondashuv jiddiy kamchiliklarga ega. Transpozitsiyani qidirishning afzalliklaridan to'liq foydalanish uchun tarmoqdagi barcha kompyuterlar o'z echimlarini boshqa kompyuterlarga u yoki bu tarzda etkazishlari kerak, yoki siz ba'zi pozitsiyalarni ortiqcha hal qilish xavfiga duch kelasiz. Bu og'irni keltirib chiqaradi aloqa xarajatlari, demak, barcha kompyuterlarning ko'p vaqtlari muammoni hal qilish o'rniga, boshqalar bilan muloqot qilish uchun sarflanadi.

Transpozitsiyani boshqaradigan rejalashtirish

An'anaviy o'rnatish

Ushbu kamchilikni hal qilish uchun muammoni hal qilishni birlashtiradigan yondashuv qabul qilindi va yuklarni muvozanatlash. Boshlash uchun har bir taxta pozitsiyasiga noyob qiymat beradigan funktsiya aniqlanadi. Tarmoqdagi har bir kompyuterga uning vakolatiga ega bo'lgan bir qator lavozimlar tayinlangan. Har qanday kompyuterning o'ziga xos transpozitsiya jadvali va ish uchun navbat bor. Har doim kompyuter o'z ishini tugatganda, navbatdan yangi ish olib keladi. Keyinchalik, bitta amalda mavjud holatdan erishish mumkin bo'lgan barcha aniq pozitsiyalarni hisoblab chiqadi. Bu an'anaviy transpozitsiyaga asoslangan muammolarni hal qilish. Biroq, an'anaviy usulda, kompyuter hozirgina hisoblab chiqilgan har bir pozitsiya uchun ushbu pozitsiyani boshqarish vakolatiga ega bo'lgan kompyuterdan uning echimi borligini so'raydi. Agar yo'q bo'lsa, kompyuter echimni rekursiv ravishda hisoblab chiqadi va vakolatiga kiradigan kompyuterga echimni yo'naltiradi. Bu juda ko'p aloqa yukini keltirib chiqaradi.

TDS-qadam

TDS nima qiladi, boshqa birovdan uning echimi borligini so'rash o'rniga, bu muammoni birovning ish navbatiga qo'shishdir. Boshqacha qilib aytganda, har safar kompyuterda echimini istagan taxta holati bo'lganida, uni shunchaki uni mas'ul kompyuterga tarmoq orqali yuboradi. va bundan endi tashvishlanmaydi. Muammo o'z vakolatlari doirasiga kirgandagina, kompyuter o'z jadvalida saqlangan echim bo'lsa qidirishga harakat qiladi. Agar yo'q bo'lsa, uni shunchaki o'z navbatiga qo'shib qo'yadi. Agar uning echimi bo'lsa, endi hech narsa hisoblashi shart emas va navbatdan yangi ish olib keladi.

Farqi

An'anaviy transpozitsiyaga asoslangan muammolarni hal qilish va TDS o'rtasidagi katta farq shundaki, ba'zi bir kompyuterlardan muammo hal qilinganligini so'rash so'rov-javob uslubiga amal qiladi, bunda boshqa kompyuterdan so'ragan kompyuter javobni kutishi kerak. TDS-da ishni boshqa kompyuterga yo'naltirish kutishni o'z ichiga olmaydi, chunki siz bilasiz (dizayn bo'yicha) boshqa kompyuter ishni qabul qiladi va uni hal qilishga harakat qiladi. Bu shuni anglatadiki kechikish (so'rovga javob modellari kechikishining asosiy sababi) bu muammo emas, chunki kompyuter hech qachon javob qaytishini kutmaydi. Uskuna yoki operatsion tizim xabarning manziliga etib borishini kafolatlashi mumkin, shuning uchun dastur ishni yuborganidan keyin endi hech narsa haqida qayg'urmaydi.

Natijalar

Tezlikni oshirmoq

TDS an'anaviy algoritmlarga nisbatan ajoyib natijalar beradi, hatto superlinear tezlashishga erishadi (garchi so'zning bir ma'nosida bo'lsa ham). Ushbu xususiyatga kompyuterlarning xotirasi cheklanganligi sababli erishiladi va katta muammolar uchun barcha transpozitsiyalarni saqlash mumkin emas. Shuning uchun ba'zi transpozitsiyalar bir necha marta hisoblab chiqiladi. 16 ta kompyuterning xotirasi 1dan 16 baravar ko'p bo'lganligi sababli (barcha kompyuterlar bir xil deb hisoblasak), TDS ga ega 16 ta kompyuter 1 ga qaraganda ko'proq transpozitsiyalarni saqlashi mumkin va shuning uchun kamroq hisoblashlari kerak. Bitta kompyuter 16 guruhning har biriga nisbatan 16 baravar ko'p xotiraga ega bo'lganda, tezlashtirish chiziqli darajadan pastroq bo'ladi.

Miqyosi

TDS-da aloqa sxemasi faqat nuqta-nuqta aloqasidan foydalanganligi sababli, translyatsiya va boshqa guruh aloqalari mavjud emas, umumiy aloqa miqdori hisoblashda qatnashadigan kompyuterlar soniga mutanosibdir. Shu sababli TDS ko'lami juda ko'p kompyuterlarga ega bo'lgan parallel tizimlarga juda yaxshi mos keladi. Bundan tashqari, kechikish muammo emasligi sababli, TDS geografik ma'noda ham ölçeklenebilir

Adabiyotlar