2. 1-§. Taqsimlangan tizimlar arxitekturasi 1

3.2-§. Maximin tipidagi optimallashtirish masalalarini hal qilishda taqsimlangan tizimlar uchun dasturiy ta'minoti

Maksimin turdagi optimallashtirish masalalarini hal qilishda taqsimlangan tizimlar uchun dasturiy ta'minotni ishlab chiqish optimallashtirish masalalarini hal qilish uchun taqsimlangan hisoblash texnikasidan foydalanishni o'z ichiga oladi, bunda maqsad funktsiyasi ma'lum cheklovlar ostida maqsadlar to'plamining minimal qiymatini maksimallashtirishdir.
Taqsimlangan tizimlar muammoni hal qilish uchun birgalikda ishlaydigan kompyuterlar tarmog'iga ishora qiladi va ular bitta mashina bilan solishtirganda hisoblash quvvati, tezligi va miqyosi bo'yicha sezilarli afzalliklarni berishi mumkin. Optimallashtirish muammolari kontekstida taqsimlangan tizimlar bitta mashinada hal qilish uchun juda katta yoki murakkab muammolarni hal qilish uchun ishlatilishi mumkin.
Maksimal turdagi optimallashtirish muammolari optimallashtirish muammolari sinfi bo'lib, uning maqsadi ma'lum cheklovlar ostida maqsadlar to'plamining minimal qiymatini maksimal darajada oshiradigan echimni topishdir. Bu muammolar iqtisodiyot, o'yin nazariyasi va muhandislik kabi turli sohalarda paydo bo'ladi va ularni hal qilish juda qiyin bo'lishi mumkin.
Maksimal turdagi optimallashtirish muammolarini hal qilishda taqsimlangan tizimlar uchun dasturiy ta'minotni ishlab chiqish uchun bir nechta yondashuvlardan foydalanish mumkin. Bir yondashuv optimallashtirish muammosini bir nechta mashinalar bo'ylab tarqatish uchun MapReduce, Spark yoki Hadoop kabi parallel hisoblash tizimidan foydalanishdir. Har bir mashina optimallashtirish muammosining kichik muammosini hal qilishi mumkin va yakuniy yechimni olish uchun echimlar birlashtirilishi mumkin.
Yana bir yondashuv - bo'lish va bo'ysundirish algoritmidan foydalanish, bunda optimallashtirish masalasi kichikroq kichik muammolarga bo'linadi va har bir kichik muammo turli mashinalarda mustaqil ravishda hal qilinadi. Keyin eritmalar birlashtirilib, yakuniy eritma olinadi.
Ikkala yondashuvda ham turli xil mashinalar o'rtasidagi aloqa va sinxronizatsiya olingan echimlarning to'g'ri va izchil bo'lishini ta'minlash uchun juda muhimdir. Bundan tashqari, dasturiy ta'minot mashinalarning ishdan chiqishi, tarmoq uzilishlari va taqsimlangan tizimda yuzaga kelishi mumkin bo'lgan boshqa muammolarni hal qilish uchun mo'ljallangan bo'lishi kerak.
Umuman olganda, maksimal turdagi optimallashtirish muammolarini hal qilishda taqsimlangan tizimlar uchun dasturiy ta'minotni ishlab chiqish taqsimlangan hisoblash, optimallashtirish va dasturiy ta'minot muhandisligi bo'yicha tajribani talab qiladi. Biroq, optimallashtirish muammolarini hal qilishda taqsimlangan tizimlardan foydalanishning afzalliklari sezilarli bo'lishi mumkin va dasturiy ta'minot ilgari hal qilib bo'lmaydigan katta va murakkab optimallashtirish muammolarini hal qilishga imkon beradi.
Taqsimlangan tizimda bo'lish va bo'lish algoritmidan foydalangan holda maksimal turdagi optimallashtirish muammosini hal qilish uchun C++ tilidagi misol kodi:
#include
#include
#include
#include

using namespace std;

const int ROOT = 0;

// Objective function to be optimized

double objective_function(double x) {
return x * x - 2 * x + 1;
}

// Sub-problem solver

double solve_subproblem(double left, double right) {
double best_solution = 0.0;
double best_value = -numeric_limits::infinity();
for (double x = left; x <= right; x += 0.001) {
double value = objective_function(x);
if (value > best_value) {
best_solution = x;
best_value = value;
}
}
return best_solution;
}

// Divide-and-conquer solver

double solve_problem(double left, double right, int rank, int size) {
if (rank == ROOT) {
double subproblems[size][2];
double solutions[size];
double best_solution = 0.0;
double best_value = -numeric_limits::infinity();
for (int i = 0; i < size; i++) {
subproblems[i][0] = left + i * (right - left) / size;
subproblems[i][1] = left + (i + 1) * (right - left) / size;
}
for (int i = 1; i < size; i++) {
MPI_Send(&subproblems[i], 2, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);
}
for (int i = 1; i < size; i++) {
MPI_Recv(&solutions[i], 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
double value = objective_function(solutions[i]);
if (value > best_value) {
best_solution = solutions[i];
best_value = value;
}
}
return best_solution;
} else {
double subproblem[2];
MPI_Recv(&subproblem, 2, MPI_DOUBLE, ROOT, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
double solution = solve_subproblem(subproblem[0], subproblem[1]);
MPI_Send(&solution, 1, MPI_DOUBLE, ROOT, 0, MPI_COMM_WORLD);
return 0.0;
}
}

int main(int argc, char** argv) {

MPI_Init(&argc, &argv);
int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
double left = 0.0;
double right = 2.0;
double solution = solve_problem(left, right, rank, size);
if (rank == ROOT) {
cout << "Solution: " << solution << endl;
}
MPI_Finalize();
return 0;
}

Ushbu kodda “objective_function” kvadrat funktsiya sifatida aniqlanadi. Funktsiya “solve_subproblem” optimallashtirish masalasining kichik muammosini ma'lum oraliqda eng yaxshi echimni izlash orqali hal qiladi. Funktsiya “solve_subproblem” muammoni kichik muammolarga bo'lish va ularni turli mashinalarga tarqatish orqali "bo'l va egalla" algoritmini amalga oshiradi. va funktsiyalari turli mashinalar o'rtasida aloqa “MPI_Send” o'rnatish “MPI_Recv” uchun ishlatiladi. Va nihoyat, funktsiyada “main” optimallashtirish muammosi funksiya yordamida hal qilinadi “solve_problem” va agar daraja bo'lsa, yechim konsolda chop etiladi.