|
Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali “kompyuter injiniringi” fakulteti
|
| bet | 10/13 | | Sana | 25.05.2024 | | Hajmi | 143,49 Kb. | | #253828 |
Bog'liq 1-amaliy ish Parallel tartiblash
PPL uchta tartiblash algoritmini taqdim etadi: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort va concurrency::p arallel_radixsort . Ular parallel ravishda saralash foydaliroq bo'lgan ma'lumotlar to'plamiga ega bo'lganda samarali bo'ladi. Xususan, parallel saralash katta ma'lumotlar to'plamiga ega bo'lganda va hisoblash intensiv taqqoslash operatsiyalaridan foydalanganda samarali bo'ladi. Ushbu algoritmlarning har biri elementlarni joyida tartiblaydi.
Algoritmlar taqqoslashga asoslanadi parallel_sort. parallel_buffered_sortYa'ni elementlarni qiymat bo'yicha solishtirishadi. Algoritm parallel_sortqo'shimcha xotirani talab qilmaydi va umumiy holatda saralash uchun mos keladi. Algoritm talab qilinadigan O(N) maydonidan parallel_buffered_sortyaxshiroq ishlashi mumkin .parallel_sort
Algoritm parallel_radixsortxeshga asoslangan. Ya'ni elementlarni saralash uchun butun sonli kalitlardan foydalanadi. Tugmachalar yordamida ushbu algoritm taqqoslash operatsiyalarini emas, balki to'g'ridan-to'g'ri elementning joylashishini aniqlay oladi. Masalan parallel_buffered_sort, bu algoritm O(N) maydonini talab qiladi.
Quyidagi jadvalda uchta parallel tartiblash algoritmlarining muhim xususiyatlari keltirilgan.
Algoritm
|
Tavsif
|
Saralash mexanizmi
|
Saralash barqarorligi
|
Xotiraga qo'yiladigan talablar
|
Vaqtning murakkabligi
|
Iteratorga kirish
|
parallel_sort
|
Umumiy maqsadli taqqoslashga asoslangan saralash.
|
Taqqoslash asosida (o'sish)
|
Beqaror
|
Yo'q
|
O(N/P)log(N/P) + 2N(P-1)/P))
|
Tasodifiy
|
parallel_buffered_sort
|
O(N) xotirasini talab qiluvchi tezroq umumiy maqsadli taqqoslashga asoslangan tartib.
|
Taqqoslash asosida (o'sish)
|
Beqaror
|
Qoʻshimcha O(N) maydoni talab qilinadi
|
O(N/P)log(N)log(N))
|
Tasodifiy
|
parallel_radixsort
|
O(N) xotirani talab qiladigan butun sonli tugmalar asosida saralash.
|
Xeshga asoslangan
|
Barqaror
|
Qoʻshimcha O(N) maydoni talab qilinadi
|
O(n/p)
|
Tasodifiy
|
Quyidagi rasmda uchta parallel tartiblash algoritmining muhim xossalari grafik ko'rsatilgan.
Ushbu parallel tartiblash algoritmlari bekor qilish va istisnolarni qayta ishlash qoidalariga bo'ysunadi. Parallel ish vaqtidagi istisnolarni bekor qilish va qayta ishlash haqida ko'proq ma'lumot olish uchun Parallel algoritmlarni bekor qilish va istisnolardan foydalanish bo'limiga qarang .
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali “kompyuter injiniringi” fakulteti
|
