Транспозицияға негізделген жоспарлау

Транспозицияға негізделген жоспарлау (TDS) - а жүктемені теңдестіру үшін алгоритм параллель есептеу. Ол әзірленді Vrije Universiteit жылы Амстердам, Нидерланды шешу алгоритмі ретінде басқатырғыштар. Алгоритм сызықтық жылдамдықты кейбір мәселелер мен масштабтармен өте жақсы қамтамасыз етеді. Ол жарияланды^[1] туралы Джон Ромейн, Aske Plaat, Анри Бал және Джонатан Шеффер.

Транспозицияға негізделген жұмбақ шешу

Сөзжұмбақта барлық мүмкін пьесалар ағашта түйіндерге сәйкес келетін тақтай позициялары, шеттеріне сәйкес келетін қимылдар, бастапқы позиция ағаштың тамыры, ал шешімдер жапырақтар түрінде ұсынылуы мүмкін. Жолдағы циклдар, яғни ағаштың басында кездесетін позицияны беретін қозғалыстар ағаштан тыс қалады, өйткені олар ешқашан оңтайлы шешімге әкелмейді.

Жұмбақтардың көпшілігінде іс-әрекеттің әр түрлі орналасуы басқатырғыштың бірдей орналасуына әкелуі мүмкін. Алдыңғы әрекеттер шешімге әсер етпейтін жұмбақтарда екі жолға да шешім табу үшін осы позицияны бір рет бағалауыңыз керек. Бір позицияны бірнеше рет бағалауды болдырмау үшін (және, осылайша, есептеу циклдарын ысыраптау), осы басқатырғыштарды шешуге арналған бағдарламалар қолданылады транспозициялық кестелер. Транспозиция дегеніміз - әртүрлі жолдармен жетуге болатын, бірақ шешімі бірдей жұмбақ күйі. Мұндай бағдарлама позицияны бағалауды бастаған сайын алдымен позиция бағаланған болса, алдымен кестеден іздейді. Егер ол бар болса, шешім көп уақытты үнемдеуге емес, есептелудің орнына кестеден алынады.

Алайда, параллельді есептеу кезінде бұл тәсілдің елеулі кемшілігі бар. Транспозициялық іздеудің артықшылықтарын толық пайдалану үшін желідегі барлық компьютерлер өз шешімдерін басқа компьютерлерге сол немесе басқа жолмен жеткізуі керек, немесе сіз кейбір позицияларды артық шешуге тәуекел етесіз. Бұл өте ауыр байланыс үстеме ақысы Бұл дегеніміз, компьютерлердің барлық уақытының көп бөлігі проблеманы шешудің орнына басқалармен байланысуға кетеді.

Дәстүрлі қондырғы

Бұл кемшілікті шешу үшін мәселені шешуді біріктіретін тәсіл қолданылды жүктемені теңдестіру. Бастау үшін тақтаның әр позициясына ерекше мән беретін функция анықталды. Желідегі кез-келген компьютерге ол өкілеттігі бар бірқатар тақта позициялары тағайындалады. Кез-келген компьютерде өзінің транспозиция кестесі және жұмыс кезегі бар. Компьютер ағымдағы жұмысымен аяқталған сайын, кезектен жаңа жұмыс алады. Содан кейін ол бір әрекетте ағымдағы позициядан қол жеткізуге болатын барлық мүмкін позицияларды есептейді. Бұл дәстүрлі транспозицияға негізделген мәселелерді шешу. Алайда, дәстүрлі әдіс бойынша, компьютер қазір есептелген әрбір позиция үшін сол позицияға билік ететін компьютерден оның шешімі бар-жоғын сұрайды. Егер олай болмаса, компьютер шешімді рекурсивті түрде есептеп шығарады және шешімді оның құзыретіне кіретін компьютерге жібереді. Байланыстың көп шығындарын тудыратыны да осы.

TDS қадамы

TDS - бұл басқа біреудің шешімінің бар-жоғын сұраудың орнына, мәселені басқа біреудің жұмыс кезегіне қосу. Басқаша айтқанда, компьютерде шешімін қалайтын тақта позициясы болған сайын, оны желі арқылы жауапты компьютерге жібереді. және енді бұл туралы алаңдамайды. Егер проблема өзінің құзыреті шегінде болса ғана, компьютер өзінің кестесінде шешімі бар болса іздеуге тырысады. Егер олай болмаса, ол оны өз кезегіне қосады. Егер оның шешімі болса, енді ештеңе есептеудің қажеті жоқ және кезектен жаңа жұмыс алады.

Айырмашылығы

Дәстүрлі транспозицияға негізделген есептер мен TDS арасындағы үлкен айырмашылық - кейбір компьютерлерден мәселе шешілген болса, сұрау-жауап тәсіліне сәйкес келеді, басқа компьютерден сұрайтын компьютер жауап күтуі керек. TDS-де жұмысты басқа компьютерге жіберу күтуді қажет етпейді, өйткені сіз басқа дизайнның жұмысты қабылдайтынын және оны шешуге тырысатынын білесіз (дизайн бойынша). Бұл дегеніміз кешігу (сұранысқа жауап беру модельдерінің кешігуінің негізгі себебі) мәселе емес, өйткені компьютер ешқашан жауаптың келуін күтпейді. Аппараттық құрал немесе амалдық жүйе хабарлама тағайындалған жерге жететініне кепілдік бере алады, сондықтан ол жұмысты жөнелткеннен кейін бағдарлама енді ештеңеге алаңдамайды.

Нәтижелер

Жылдамдық

TDS дәстүрлі алгоритмдермен салыстырғанда керемет нәтижелер береді, тіпті супер сызықтық жылдамдыққа жетеді (сөздің бір мағынасында болса да). Бұл қасиетке компьютерлердің есте сақтау қабілеті шектеулі болғандықтан қол жеткізіледі, және үлкен проблемалар үшін барлық транспозициялар сақтала бермейді. Сондықтан кейбір транспозициялар бірнеше рет есептелетін болады. 16 компьютердің жады 1-ден 16 есе көп болғандықтан (барлық компьютерлер бірдей болса), TDS-ті 16 компьютер транспозицияны 1-ге қарағанда көбірек сақтай алады, сондықтан аз есептеу керек. Бір компьютер 16 топтың әрқайсысынан 16 есе көп жадты алғанда жылдамдық сызықтықтан сәл төмен болады.

Масштабтылық

TDS-тегі байланыс схемасы тек нүктелік-нүктелік байланысты қолданатындықтан, хабар тарату немесе басқа топтық байланыс жоқ болғандықтан, жалпы байланыстың мөлшері есептеуге қатысатын компьютерлер санына пропорционалды. Осыған байланысты TDS масштабы көптеген компьютерлері бар параллель жүйелерге жақсы әсер етеді. Сондай-ақ, кешіктіру мәселесі болмағандықтан, TDS географиялық тұрғыдан да ауқымды

Әдебиеттер тізімі

^ Джон В.Ромейн; Аске Плат; Анри Э.Бал; Джонатан Шеффер. «Таратылған іздеу кезінде транспозициялық кестеге негізделген жұмысты жоспарлау» (PDF). Архивтелген түпнұсқа (PS) 2015 жылғы 23 қазанда. Алынған 1999-07-18. Күннің мәндерін тексеру: | рұқсат күні = (Көмектесіңдер)

[TDS_paper-1] Джон В.Ромейн; Аске Плат; Анри Э.Бал; Джонатан Шеффер. «Таратылған іздеу кезінде транспозициялық кестеге негізделген жұмысты жоспарлау» (PDF). Архивтелген түпнұсқа (PS) 2015 жылғы 23 қазанда. Алынған 1999-07-18. Күннің мәндерін тексеру: | рұқсат күні = (Көмектесіңдер)

[1]