موازی سازی الگوریتم های مرتب سازی با استفاده از OpenMP

این وبلاگ در اصل در https://blog.sahrohit.com.np/posts/parallel-sorting-algorithm پست شده و برای دسترسی بیشتر در سراسر پلتفرم ها توزیع شده است.

این وبلاگ بر بررسی برنامه نویسی موازی با استفاده از OpenMP، به ویژه در زمینه الگوریتم های مرتب سازی تمرکز دارد. هدف مقایسه عملکرد اجرای سریال و موازی سه الگوریتم مرتب‌سازی معروف – Bubble، مرتب‌سازی سریع و مرتب‌سازی ادغام – بر روی اعداد تولید شده به‌طور تصادفی است و بینش‌هایی در مورد اینکه چگونه برنامه‌نویسی موازی بر کارایی محاسباتی تأثیر می‌گذارد، ارائه می‌کند.

این وبلاگ شامل ایجاد هر دو اجرای سریال (S) و موازی (P) برای هر یک از سه الگوریتم مرتب‌سازی، در کنار پیاده‌سازی مرجع با استفاده از STL's std::sort برای محک زدن نتایج است. عملکرد این الگوریتم‌ها با اندازه‌گیری زمان‌های اجرا در اندازه‌های ورودی مختلف ارزیابی می‌شود و اثرات ابر نخ‌سازی نیز مورد مطالعه قرار می‌گیرد.

بررسی اجمالی سخت افزار

راه اندازی سخت افزار برای سیستم های مورد استفاده در این وبلاگ شامل دو سرور است. اولین، تربچه، دارای 4 هسته با 2 رشته در هر هسته است که در نتیجه 8 CPU مجازی (vCPU) ایجاد می شود. دومی، jalapeno، دارای 4 هسته با 2 رشته در هر هسته است که 16 vCPU را ارائه می دهد، که نشان می دهد hyper-threading نیز فعال است. این سیستم ها طیف وسیعی از تنظیمات سخت افزاری را برای آزمایش کارایی موازی الگوریتم های مرتب سازی با OpenMP ارائه می دهند.

مرور کلی الگوریتم مرتب سازی

مرتب‌سازی حبابی (O(n^2))

مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی مبتنی بر مقایسه ساده با پیچیدگی زمانی درجه دوم است که با مقایسه هر آیتم با آیتم مجاورش و جابجایی برای مرتب‌سازی کار می‌کند. موازی سازی مرتب سازی حباب به دلیل ماهیت متوالی ذاتی آن چالش برانگیز است.

نسخه موازی این الگوریتم بین دو فاز متناوب است تا اطمینان حاصل شود که همه عناصر به درستی قرار گرفته اند. هر رشته در طول این مراحل بر روی بخش‌های مشخصی از داده‌ها عمل می‌کند و با کاهش تعداد مقایسه‌های اضافی، کارایی را بهبود می‌بخشد. وضعیت مشترک آرایه با استفاده از تکنیک‌های همگام‌سازی، مانند کاهش، برای اطمینان از مرتب‌سازی مناسب بدون درگیری یا شرایط مسابقه، به طور مداوم در سراسر رشته‌ها حفظ می‌شود. این رویکرد سیستم را قادر می سازد تا از منابع محاسباتی موجود به طور کامل استفاده کند و روند مرتب سازی را به ویژه برای مجموعه داده های بزرگ سرعت بخشد.

void bubbleSortParallel(int arr[], int n) {
    bool sorted = false;
    int tmp;

    while (!sorted) {
        sorted = true;

        #pragma omp parallel private(tmp)
        {
            // Even phase
            #pragma omp for reduction(&&:sorted)
            for (int i = 0; i < n-1; i += 2) {
                if (arr[i] > arr[i+1]) {
                    tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                    sorted = false;
                }
            }

            // Odd phase
            #pragma omp for reduction(&&:sorted)
            for (int i = 1; i < n-1; i += 2) {
                if (arr[i] > arr[i+1]) {
                    tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                    sorted = false;
                }
            }
        }
    }
}

مرتب سازی سریع (O(n log n))

مرتب سازی سریع یک الگوریتم پرکاربرد، کارآمد و تقسیم و غلبه است. با پارتیشن بندی بازگشتی آرایه، عملکرد O(n log n) را در حالت متوسط ​​خود به دست می آورد. موازی کردن مرتب سازی سریع با اختصاص پارتیشن های مختلف به رشته های مختلف امکان پذیر است.

در نسخه موازی مرتب‌سازی سریع، رویکرد تقسیم و حکومت با اختصاص پارتیشن‌های آرایه‌های مختلف به رشته‌های جداگانه بهینه‌سازی می‌شود. پس از پارتیشن بندی آرایه حول یک عنصر محوری، زیرآرایه های چپ و راست به طور مستقل مدیریت می شوند. این استقلال امکان اجرای موازی را فراهم می کند، جایی که چندین رشته می توانند به طور همزمان قسمت های مختلف آرایه را مرتب کنند و زمان کلی مرتب سازی را تا حد زیادی کاهش می دهد. با کنترل عمق بازگشت، وظایف به صورت مشروط ایجاد می شوند تا از موازی سازی بیش از حد سربار جلوگیری شود و اطمینان حاصل شود که منابع محاسباتی به طور موثر مورد استفاده قرار می گیرند. در نتیجه، مرتب‌سازی سریع موازی می‌تواند مجموعه داده‌های بزرگ را به طور مؤثرتری نسبت به همتای متوالی خود مدیریت کند.

void quickSortParallel(int arr[], int low, int high, int depth = 0) {
    if (low < high) {
        int pi = partition(arr, low, high);

        #pragma omp task shared(arr) if(depth < 3)
        quickSortParallel(arr, low, pi - 1, depth + 1);

        #pragma omp task shared(arr) if(depth < 3)
        quickSortParallel(arr, pi + 1, high, depth + 1);

        #pragma omp taskwait
    }
}

در کد منبع، موازی سازی از طریق دستورات وظیفه omp #pragma حاصل می شود، که وظایف موازی را برای مرتب سازی زیرآرایه های چپ و راست پس از پارتیشن بندی ایجاد می کند. به طور خاص، پس از محاسبه شاخص محوری (pi)، دو کار جداگانه ایجاد می‌شود: یکی برای مرتب‌سازی زیرآرایه در سمت چپ محور (quickSortParallel(arr، low، pi – 1، عمق + 1)) و دیگری برای زیرآرایه به سمت راست محور (quickSortParallel(arr, pi + 1, high, depth + 1)). این وظایف به طور همزمان توسط رشته های مختلف اجرا می شوند.

شرط if(عمق < 3) تضمین می کند که ایجاد کار به چند سطح بازگشتی اول محدود می شود، که از ایجاد وظایف بیش از حد زیاد در بازگشت عمیق جلوگیری می کند. دستورالعمل #pragma omp taskwait تضمین می‌کند که برنامه قبل از حرکت به جلو منتظر می‌ماند تا هر دو کار مرتب‌سازی تکمیل شوند و صحت در فرآیند مرتب‌سازی کلی حفظ شود. این رویکرد ساختاریافته به طور موثر الگوریتم مرتب سازی سریع را موازی می کند در حالی که ایجاد کار و استفاده از منابع را متعادل می کند.

مرتب سازی ادغام (O(n log n))

Merge Sort یکی دیگر از الگوریتم های تقسیم و غلبه با عملکرد تضمین شده O(n log n) در بدترین حالت است. این به ویژه برای موازی سازی مناسب است زیرا زیرآرایه های مختلف را می توان همزمان با هم ادغام کرد و آن را به یک نامزد ایده آل برای OpenMP تبدیل می کند.

void mergeSortParallel(int arr[], int l, int r, int depth = 0) {
    if (l < r) {
        int m = l + (r - l) / 2;

        #pragma omp task shared(arr) if(depth < 3)
        mergeSortParallel(arr, l, m, depth + 1);

        #pragma omp task shared(arr) if(depth < 3)
        mergeSortParallel(arr, m + 1, r, depth + 1);

        #pragma omp taskwait
        merge(arr, l, m, r);
    }
}

در نسخه موازی Merge Sort، آرایه به صورت بازگشتی به زیرآرایه های کوچکتری تقسیم می شود که می توانند به طور مستقل مرتب شوند. مزیت کلیدی برای موازی سازی در فرآیند ادغام نهفته است، جایی که دو زیرآرایه مرتب شده می توانند به طور همزمان در رشته های جداگانه ادغام شوند. این اجرای موازی انواع زیرآرایه مستقل به طور قابل توجهی زمان اجرا کلی را کاهش می دهد، به خصوص برای مجموعه داده های بزرگ. عمق بازگشت کنترل می شود تا از سربار بیش از حد جلوگیری شود و اطمینان حاصل شود که فقط سطوح بالای بازگشت موازی می شوند، جایی که مزایای موازی سازی بیشتر است.

در کد منبع، موازی‌سازی با استفاده از دستورالعمل #pragma omp اجرا می‌شود، که وظایف موازی را برای مرتب‌سازی نیمه‌های چپ و راست آرایه ایجاد می‌کند (mergeSortParallel(arr, l, m) و mergeSortParallel (arr, m + 1, r) ). شرط if(عمق <3) ایجاد کار را به سطوح بالاتر بازگشت محدود می کند، و تعادل بین موازی بودن و سربار را متعادل می کند. دستورالعمل #pragma omp taskwait تضمین می‌کند که هر دو کار مرتب‌سازی قبل از ادامه مرحله ادغام تکمیل می‌شوند، که برای حفظ صحت الگوریتم مرتب‌سازی ادغام بسیار مهم است.

روش شناسی

راه اندازی آزمایشی

برای ارزیابی عملکرد، برنامه آرایه‌های تصادفی از اعداد صحیح را تولید می‌کند، جایی که اندازه آرایه‌ها از کوچک به بزرگ (مثلاً 2500 تا 500000 عدد صحیح) تغییر می‌کند. آرایه های تصادفی با استفاده از آرگومان های خط فرمان برای اندازه آرایه و مقدار دانه تولید شدند. هر الگوریتم مرتب‌سازی، هر دو نسخه سریال و موازی (16 رشته)، در فایل‌های اجرایی جداگانه جمع‌آوری شد و زمان اجرا اندازه‌گیری شد.

هر فایل اجرایی دو آرگومان خط فرمان داشت:

cpp [executable name] [number of random integers to generate] [seed value for random number generation]

سپس یک اسکریپت bash برای ساخت و اجرای تمامی فایل های اجرایی و نوشتن زمان اجرا هر کدام در یک فایل CSV نوشته شد.

موازی سازی با استفاده از OpenMP به دست آمد و هر الگوریتم مرتب سازی بر اساس ساختار آن موازی شد. زمان اجرا با استفاده از کتابخانه C++ chrono اندازه گیری شد و از دقت اطمینان حاصل شد. عملکرد برای هر الگوریتم به صورت سریال، موازی و با استفاده از STL's std:: sort به عنوان مرجع مقایسه شد.

معیارهای مقایسه

معیار اولیه مورد استفاده برای مقایسه، زمان اجرا بر حسب ثانیه بود. آزمایش‌ها در طیف وسیعی از اندازه‌های ورودی برای مشاهده چگونگی مقیاس عملکرد با افزایش داده‌ها انجام شد. نتایج در نمودارها برای تجسم تفاوت بین اجرای سریال، موازی و مرجع ترسیم شد.

تجزیه و تحلیل مرتب سازی حباب

نمودار 1: مرتب‌سازی حبابی (bbs، bbp، مرجع)

این نمودار زمان‌های اجرای سه پیاده‌سازی مرتب‌سازی را مقایسه می‌کند: مرتب‌سازی STL C++، مرتب‌سازی حباب‌های موازی و مرتب‌سازی حباب سریال، برای اندازه‌های ورودی مختلف. به طور خاص، نسخه موازی می تواند به طور قابل توجهی برای آرایه های با اندازه کوچکتر به دلیل سربار معرفی شده توسط مدیریت رشته، همگام سازی و انسجام حافظه پنهان کندتر باشد. با این حال، برای ورودی های بزرگتر، زمان اجرای آن به طور قابل توجهی کاهش می یابد. این به دلیل این واقعیت است که هسته‌های CPU به طور مؤثرتری مورد استفاده قرار می‌گیرند، الگوهای دسترسی به حافظه کارآمدتر هستند، و از پیش واکشی سخت‌افزاری بهتر بهره‌برداری می‌شود، حتی اگر هر دو پیاده‌سازی مرتب‌سازی حبابی دارای پیچیدگی O(n²) باشند.

توضیح گراف

برای مجموعه داده‌های کوچک‌تر، سربار مرتبط با مدیریت رشته‌ها در نسخه موازی (bbp) منجر به عملکرد کندتر در مقایسه با نسخه سریال (bbs) می‌شود. با این حال، با افزایش اندازه مجموعه داده، اجرای موازی با توزیع حجم کار در چندین هسته شروع به عملکرد بهتر از سریال می‌کند. الگوریتم مرتب سازی STL مرجع به دلیل طراحی پیچیده و بهینه آن، که شامل ملاحظاتی برای الگوهای دسترسی به حافظه، خط لوله CPU و الگوریتم های مرتب سازی پیشرفته تر با پیچیدگی زمانی بهتر است، همواره از هر دو bbs و bbp پیشی می گیرد.

تجزیه و تحلیل

عملکرد ضعیف‌تر مرتب‌سازی حباب‌دار موازی در آرایه‌های کوچک‌تر ناشی از سربار قابل‌توجهی است که در ایجاد و همگام‌سازی نخ وجود دارد. علاوه بر این، الگوهای دسترسی ذاتی به حافظه مرتب‌سازی حبابی به دلیل وابستگی به داده‌ها، موانع همگام‌سازی مکرر را ایجاد می‌کنند. با این حال، در مجموعه داده‌های بزرگ‌تر، افزایش حجم کار، موازی‌سازی را قادر می‌سازد تا موثرتر باشد، و در نتیجه عملکرد بهتری برای bbp در مقایسه با همتای سریالی آن دارد. با این وجود، هر دو نوع مرتب‌سازی حبابی کندتر از مرتب‌سازی STL هستند که از الگوریتم‌های پیشرفته و بهینه‌سازی‌های متناسب با معماری‌های CPU مدرن استفاده می‌کنند.

تجزیه و تحلیل مرتب سازی سریع

نمودار 2: مرتب سازی سریع (qss، qsp، مرجع)

نمودارها زمان اجرای سه اجرای مرتب‌سازی سریع مختلف را مقایسه می‌کنند: سریال (qss)، موازی (qsp با 16 رشته)، و مرجع (مرتب‌سازی STL). با کمال تعجب، هر دو اجرای سریال و موازی از std::sort بهتر عمل می کنند، که می تواند به تفاوت های کلیدی در رویکرد الگوریتمی و بهینه سازی نسبت داده شود.

توضیح گراف

برای مجموعه داده‌های کوچک‌تر، مرتب‌سازی سریع سریال (qss) عملکردی مشابه با مرتب‌سازی سریع موازی (qsp) دارد. با افزایش اندازه ورودی، نسخه موازی از پردازش چند هسته ای بهره می برد و زمان اجرا را در مقایسه با نسخه سریال به شدت کاهش می دهد. جالب اینجاست که علیرغم اینکه std::sort بسیار بهینه شده است، هم qss و هم qsp زمان اجرا سریع تری را نشان می دهند. این نتیجه نشان می‌دهد که سربار معرفی‌شده توسط بهینه‌سازی‌های اضافی std::sort، به‌ویژه برای توزیع‌های داده‌ای که در اینجا آزمایش شده‌اند، مضر است.

تجزیه و تحلیل

عملکرد کندتر std::sort در این مقایسه احتمالاً به دلیل سربار بهینه‌سازی‌های پیچیده‌تر آن است، مانند مرتب‌سازی سریع 3 پارتیشن و سوئیچ به مرتب‌سازی درج برای پارتیشن‌های کوچک. در حالی که این بهینه‌سازی‌ها برای مدیریت بدترین سناریوها و مجموعه داده‌های سنگین تکراری طراحی شده‌اند، در صورت عدم وجود چنین شرایطی می‌توانند سربار غیرضروری اضافه کنند. در مقابل، طرح پارتیشن Lomuto ساده‌تر مورد استفاده در qss و qsp برای اندازه‌های ورودی و توزیع داده‌های آزمایش‌شده در اینجا کارآمدتر است و منجر به عملکرد بهتر می‌شود.

تجزیه و تحلیل مرتب سازی ادغام

نمودار 3: مرتب سازی ادغام (mss، msp، مرجع)

نمودار سوم عملکرد Merge Sort را با مقایسه نسخه سریال (mss)، نسخه موازی (msp) و مرجع (مرتب سازی STL) نشان می دهد. مرتب‌سازی ادغام برای موازی‌سازی مناسب است، بنابراین انتظار می‌رود که نسخه موازی (msp) در هنگام آزمایش در اندازه‌های مجموعه داده بهتر از همتای سریال (mss) عمل کند. نمودار نشان می دهد که چگونه نسخه موازی از چند رشته ای استفاده می کند، به ویژه برای ورودی های بزرگتر، در حالی که مرتب سازی STL مرجع فقط کمی بهتر از مرتب سازی ادغام سریال عمل می کند.

توضیح گراف

مرتب سازی ادغام موازی (msp) به طور مداوم برای اندازه های ورودی بزرگتر از نسخه سریال (mss) بهتر عمل می کند. با استفاده از 16 رشته، msp به طور موثر آرایه را تقسیم می کند و بخش ها را به طور همزمان ادغام می کند، که به طور قابل توجهی زمان اجرا را در مقایسه با نسخه سریال (mss) بهبود می بخشد. با این حال، برای مجموعه داده‌های کوچک‌تر، سربار مدیریت رشته‌های متعدد، مزیت msp را کاهش می‌دهد. از سوی دیگر، مرتب‌سازی STL، در حالی که موازی نیست، از الگوریتم‌های بسیار کارآمد، از جمله مرتب‌سازی سریع 3 پارتیشن، مرتب‌سازی درج، و مرتب‌سازی پشته‌ای استفاده می‌کند که به آن اجازه می‌دهد تا کمی بهتر از مرتب‌سازی سریال ادغام (mss) عمل کند، به ویژه در موارد کوچک. مجموعه داده ها

تجزیه و تحلیل

مرتب سازی ادغام برای موازی سازی بسیار مناسب است، زیرا رویکرد تقسیم و غلبه آن به طور طبیعی اجازه می دهد تا بخش های مستقل یک آرایه به طور همزمان ادغام شوند. مرتب سازی ادغام موازی (msp) به طور قابل توجهی زمان اجرا را برای مجموعه داده های بزرگتر با توزیع حجم کار در 16 رشته کاهش می دهد. در حالی که مرتب‌سازی STL از مدیریت بهینه حافظه و استفاده از حافظه نهان پردازنده سود می‌برد، نمی‌تواند از موازی‌سازی استفاده کند، و این باعث می‌شود در مجموعه داده‌های بزرگ از msp کندتر باشد. با این حال، به دلیل الگوریتم‌های ترکیبی کارآمد خود که از بدترین پیچیدگی‌های زمانی معمولی مرتب‌سازی سریع اجتناب می‌کند، همچنان در سناریوهای داده‌های کوچک از مرتب‌سازی سریال (mss) بهتر عمل می‌کند.

تجزیه و تحلیل Hyper-threading

نتایج Hyper-threading

آزمایش ابر نخ بر روی تمام الگوریتم های فوق به عنوان مورد آزمایشی انجام شد. Hyper-threading فعال شد و زمان اجرا برای اندازه‌های ورودی مختلف اندازه‌گیری شد. نمودار زمان اجرای کاهش زمان اجرا بیش از حد نخ را در همه موارد نشان می دهد و با hyper-threading بهتر عمل می کند.

توضیح نتایج

hyper-threading بهبود اندکی را در عملکرد برای همه اندازه‌های ورودی نشان می‌دهد، به‌ویژه زمانی که حجم کار به اندازه کافی بزرگ است که هسته‌های منطقی را اشباع کند. برای مجموعه داده‌های کوچک‌تر، ابر رشته‌ای کمترین مزیت را به همراه دارد، زیرا رشته‌ها به طور کامل از منابع موجود استفاده نمی‌کنند.

تجزیه و تحلیل

hyper-threading می‌تواند با اجازه دادن به رشته‌های بیشتر به صورت همزمان، بهبود عملکرد را ارائه دهد، اما این تنها زمانی مفید است که حجم کار به اندازه‌ای باشد که تمام هسته‌های منطقی را مشغول نگه دارد. در مواردی که حجم کار خیلی کم است، سربار hyper-threading در واقع می تواند عملکرد را کاهش دهد.

نتیجه گیری

نتایج نشان می‌دهد که در حالی که پیاده‌سازی موازی الگوریتم‌های مرتب‌سازی می‌تواند بهبود عملکرد را ارائه دهد، مزایا به شدت به اندازه مجموعه داده و الگوریتم خاص بستگی دارد. برای مجموعه داده‌های کوچک‌تر، سربار مدیریت رشته‌ها اغلب مزایای موازی‌سازی را نفی می‌کند. با این حال، برای مجموعه داده های بزرگتر، نسخه های موازی بهتر از همتایان سریال خود عمل می کنند. تجزیه و تحلیل همچنین نشان می‌دهد که hyper-threading می‌تواند عملکرد را افزایش دهد، اما فقط تحت شرایط خاص.

کد منبع

https://github.com/sahrohit/parallel-sorting.git

https://github.com/sahrohit/parallel-sorting/blob/main/combined.csv