|
2.3. Monte-Karlo uslubining g'oyasi
Monte-Karlo usuli - bu ehtimollik qonunlarini sun'iy ravishda amalga oshirishni qo'llaydigan usul. Statistik testlar usulidan foydalanganda har safar operatsiyani bitta bajarilishi (kompyuterda modelni bitta hisoblash) tasodifiy dastlabki ma'lumotlar bilan amalga oshiriladi. Amaliyotni uning modeli bo'yicha bir necha bor noto'g'ri hisoblash, o'rganilayotgan operatsiyani baholash mumkin bo'lgan ma'lumotlar asosida ma'lumotlarni to'plash imkonini beradi.
Monte-Karlo uslubining mohiyati quyidagicha: ba'zi bir o'rganilgan miqdorning a qiymatini topish talab qilinadi. Buning uchun matematik kutilmasi a ga teng bo'lgan tasodifiy X ni tanlang: M (X) = a.
Amalda ular quyidagilarni bajaradilar: n ta test o'tkazadilar, natijada X ning n mumkin bo'lgan qiymatlari olinadi; ularning o'rtacha arifmetikasini hisoblang
va kerakli a sonining taxminiy qiymati (taxminiy qiymati) a * ni oling.
Ushbu usul nazariyasi X tasodifiy o'zgaruvchini qanday tanlashni eng maqbul ekanligini, uning mumkin bo'lgan qiymatlarini qanday topish kerakligini ko'rsatadi. Xususan, ishlatilgan tasodifiy o'zgaruvchilarning farqlanishini kamaytirish usullari ishlab chiqilmoqda, natijada kerakli matematik kutilishni a qiymatini a * ga almashtirish bilan yo'l qo'yilgan xato kamayadi.
III.BOB
3.1. Integrallarni hisoblash algoritmlari Monte-Karlo usuli bilan. Aniq integral
F (x) funktsiyasi [a, b] cheklangan intervalda aniqlansin. Biz [a, b] segmentini qandaydir tarzda bo'linish nuqtalari bo'yicha N qismlarga bo'ldik (shart emas).
a = x0
(3.1.1)
Raqam [a, b] qismning nozikligi deb nomlanadi.
[Xi, xi + 1] oralig'idan ixtiyoriy ξi nuqtalarni tanlang va integral summani tuzing.
(3.1.1) qismga mos keladigan f (x) funktsiyasi va ξi nuqtalarini tanlash. Agar IN ning integral yig'indilarining ketma-ketligi δN → 0 sifatida cheklangan I chegaraga ega bo'lsa, bu [a, b] segmentni ajratish uslubiga yoki ξi nuqtalarni tanlashga bog'liq emas bo'lsa, u holda bu chegara a (dan) gacha bo'lgan oraliqdagi f (x) funktsiyasining aniq integrali deb ataladi. Integralni taxminan hisoblash talab qilinadi. Faraz qilaylik, qandaydir tarzda F (ξ) taqsimlash funktsiyasi bilan L = [a, b] oralig'ida teng taqsimlangan tasodifiy, juftlik bilan D0,…, DN-1 nuqtalarni olish mumkin.
Si tasodifiy o'zgaruvchilari juftlik bo'yicha mustaqil va teng taqsimlanadi:
bu erda M - si qiymatining matematik kutish operatori.
Si tasodifiy o'zgaruvchining D dispersiyasi:
(3.1.2)
Shunday qilib, N tasodifiy ξi sonlarni qo'lga kiritib va ulardagi f funktsiyasining qiymatlarini hisoblab, katta N sonlar uchun taxminan integral I beradigan IN qiymatini aniqlay olamiz.
Formulalar integrallarni statistik testlar usuli yoki Monte-Karlo usuli bilan hisoblashning birinchi usulini belgilaydi. Keling, buni o'rtacha ko'rsatkichlar usuli deb ataymiz. Integralning taxminiy qiymatini olish maqsadga muvofiq bo'lgan reliability ishonchlilik darajasini ko'rsatib, takroriy jarayonni to'xtatish shartini aniqlash uchun Chebyshev tengsizligini qo'llashimiz mumkin va bu tengsizlik 1 - ability ehtimollik bilan qondiriladi.Chebyshev tengsizligi qo'llanilishining haqiqiyligi uchun har qanday pointsi nuqtalarni taqsimlash mustaqilligi to'g'risidagi taxmin bajarilishi kerak.
F taqsimlash funktsiyasini bilmasligimiz sababli, amalda takrorlanish jarayonini tugatish uchun quyidagi shartdan foydalanamiz (bundan keyin - chiqish sharti): agar oldingi va joriy bosqichlarda integral baholari orasidagi farq moduli belgilangan xato qiymatidan kam yoki unga teng bo'lsa ε, protsedurani bekor qiling.Oldingi xatboshida tasvirlangan Monte-Karlo uslubining o'zgarishiga qo'shimcha ravishda bitta integralni hisoblash uchun yana bitta usul - maydon usulini aniqlash mumkin. Keling, misol yordamida maydon usulini tushuntiraylik. F (x) funktsiyasi berilgan bo'lsin, umuman olganda belgi o'zgaruvchan, a va b integratsiya chegaralari .Integral bu holda 3.1.1-rasmdagi soyali qismlarning umumiy maydonini aks ettiradi. F (x) egri chizilgan to'rtburchakning maydonini belgilaymiz - S, kerakli maydon - σ. Biz qandaydir tarzda to'rtburchak ichida yotgan N tasodifiy x va N tasodifiy nuqtalarni olamiz.
Rasm: 3.1.1
3.2. Parallel hisoblash algoritmlari
Monte-Karlo usulidan foydalanish uchun ketma-ket kompyuter bo'lsa, tasodifiy sonlar generatori, kalkulyator va analizatorga ega bo'lish zarur. Ushbu elementlarning barchasi zanjir bo'ylab chiziqli ravishda ishlaydi: generator → kalkulyator → analizator:
GENERATOR
|
|
KALKULYATOR
|
|
ANALIZATOR
|
|
|
Agar bizda parallel tizim, masalan, klaster bo'lsa, u holda Monte Karlo uslubidagi oraliq hisob-kitoblar ushbu klasterning turli tugunlarida amalga oshirilishi mumkin va yakuniy natijani ba'zi bir xost mashinalarida, ya'ni ildiz deb nomlash mumkin. Bunday sxema shakl. 3.2.1 Shaklga ko'ra. 1, tizim uchun bitta tasodifiy raqamlar generatori mavjud va kalkulyatorlar orqali yuqoridan pastgacha o'tib, ularning har biriga hosil bo'lgan tasodifiy sonni beradi. Biroq, kompyuterlar o'rtasida ma'lumot uzatilishi kerakligi sababli, parallel tizimning ishlashi pasayadi. Ma'lumot hozirda mavjud bo'lgan vositalar orqali uzatiladi. Etkazish tezligi 12 Mb / s gacha bo'lgan Fast Ethernet texnologiyasi, 80 Mb / s dan zamonaviy SCI yoki Myrinet texnologiyalari uchun aniqlanadi [9]. Ishlab chiqarishdagi sezilarli farqdan tashqari, eng yuqori tezlikdagi texnologiyalar kechikish vaqtini sezilarli darajada pastroq (5-10 miks va 150-300 miks tezkor Ethernet). Ushbu texnologiyalarning asosiy kamchiliklari bu ba'zan hisoblash elementlari narxidan oshib ketadigan xarajatdir.
Rasm.3.2.1
Monte-Karlo uslubining parallel algoritmining soddalashtirilgan diagrammasi. Xabar almashishni minimal darajada ushlab turish uchun har bir kalkulyatorga o'z tasodifiy (psevdo-tasodifiy) raqamlar generatorini taqdim etishingiz mumkin. Bundan tashqari, generator va kalkulyator bir xil jarayon bo'lishi mumkin. Bundan tashqari, generator, kalkulyator va analizator bitta asosiy jarayonda birlashtirilishi mumkin. Bu ishda ushbu sxema amalga oshirildi. Shaklda grafik tarzda ko'rsatilgan. Ushbu ishda MPI klasterida Monte Karlo usuli bo'yicha yakka integrallarni hisoblashning uchta parallel algoritmi ishlab chiqilgan va amalga oshirilgan bo’ladi.
Uchala algoritm ham uchta MPI funktsiyasidan foydalanishga asoslangan.
MPI_BARRIER (comm): kirish parametri comm (type - descriptor) - bu kollektiv operatsiya bajariladigan guruhning kommunikatori. Ushbu funktsiya to'siqni sinxronlash funktsiyasi bo'lib, guruhdagi barcha jarayonlar funktsiyani chaqirguncha qo'ng'iroq qilish jarayonini bloklaydi. Har bir jarayonda boshqarish faqat guruhdagi barcha jarayonlar MPI_BARRIERga qo'ng'iroq qilganda qaytadi.
Do'stlaringiz bilan baham: |
