در C++17، کتابخانه استاندارد قابلیتهای جدیدی برای پردازش موازی دادهها ارائه میکند که بخشی از آنها در قالب Parallel Algorithms و Execution Policies در دسترس هستند. یکی از قابلیتهای مهم این مجموعه، الگوریتمهای Scan است که برای محاسبه تدریجی مقادیر روی مجموعهای از دادهها استفاده میشوند. الگوریتمهایی مانند inclusive_scan و exclusive_scan از C++17 وارد کتابخانه استاندارد شدند و میتوانند همراه با سیاست اجرای موازی مورد استفاده قرار بگیرند.
مفهوم Scan در بسیاری از مسائل پردازش داده اهمیت دارد؛ زیرا به جای محاسبه یک نتیجه نهایی، نتیجه تجمعی را در تمام موقعیتهای یک مجموعه تولید میکند. این ویژگی باعث میشود الگوریتمهای اسکن در پردازشهای عددی، تحلیل داده، محاسبات تجمعی و الگوریتمهای موازی کاربرد زیادی داشته باشند.
الگوریتمهای Scan در C++17
در C++17 چند الگوریتم مهم برای انجام عملیات Scan در STL معرفی شدهاند که مهمترین آنها inclusive_scan، exclusive_scan، transform_inclusive_scan و transform_exclusive_scan هستند. این الگوریتمها علاوه بر حالت اجرای عادی، امکان استفاده از Execution Policy را نیز دارند و بنابراین میتوانند برای پردازش موازی دادهها به کار گرفته شوند.
ایده اصلی Scan این است که به ازای هر عنصر، نتیجه ترکیب آن عنصر با نتایج قبلی محاسبه شود. برای مثال در یک جمع تجمعی، خروجی هر موقعیت نشاندهنده مجموع مقادیر تا همان نقطه خواهد بود.
تفاوت مهم میان دو نوع اصلی Scan در این است که Inclusive Scan عنصر فعلی را در نتیجه همان موقعیت وارد میکند، در حالی که Exclusive Scan عنصر فعلی را کنار میگذارد و نتیجه را بر اساس عناصر قبل از آن محاسبه میکند.
اجرای موازی Inclusive Scan
الگوریتم inclusive_scan برای تولید نتایج تجمعی استفاده میشود و در C++17 نسخهای دارد که میتواند یک Execution Policy دریافت کند. به این ترتیب، برنامه میتواند نحوه اجرای الگوریتم را به صورت صریح مشخص کند و در صورت استفاده از سیاست موازی، اجرای عملیات برای بخشهای مختلف داده امکان موازیسازی پیدا میکند.
نکته مهم در استفاده از اسکن موازی این است که عملیات تجمعی باید برای اجرای موازی مناسب باشد. در چنین الگوریتمهایی، نحوه ترکیب نتایج اهمیت زیادی دارد و اگر عملگر مورد استفاده ویژگیهای ریاضی لازم برای ترکیب مستقل بخشهای مختلف داده را نداشته باشد، ممکن است نتیجه اجرای موازی با انتظار برنامهنویس متفاوت باشد. استاندارد نیز درباره رفتارهای احتمالی در صورت غیرهمبسته یا غیرجابجایی بودن عملیات تجمعی هشدار میدهد.
اجرای موازی Exclusive Scan
exclusive_scan شباهت زیادی به inclusive_scan دارد، اما نتیجه هر موقعیت، عنصر همان موقعیت را در محاسبه خودش در نظر نمیگیرد. یک مقدار اولیه نیز میتواند برای شروع عملیات در نظر گرفته شود.
این الگوریتم برای مسائلی مناسب است که نتیجه تجمعی قبلی باید در موقعیت فعلی قرار بگیرد. به همین دلیل در الگوریتمهای تخصیص موقعیت، محاسبه Offsetها، پردازش موازی دادهها و برخی ساختارهای پردازش دستهای کاربرد دارد.
نسخه C++17 این الگوریتم نیز Execution Policy را پشتیبانی میکند و میتواند در قالب اجرای موازی مورد استفاده قرار گیرد.
ترکیب Transform و Scan
یکی از قابلیتهای پیشرفتهتر STL، ترکیب عملیات تبدیل داده با Scan است. الگوریتمهای transform_inclusive_scan و transform_exclusive_scan این امکان را فراهم میکنند که ابتدا یک تبدیل منطقی روی دادهها انجام شود و سپس نتیجه تبدیلشده وارد فرآیند Scan شود. این رویکرد باعث میشود چند مرحله پردازش را بتوان در قالب یک الگوریتم استاندارد بیان کرد.
برای مثال در یک مسئله ممکن است لازم باشد ابتدا مقدار هر داده تغییر کند و سپس مجموع تجمعی مقادیر تغییریافته محاسبه شود. الگوریتمهای Transform Scan دقیقاً برای چنین الگوهایی طراحی شدهاند و در C++17 به مجموعه الگوریتمهای جدید Parallelism اضافه شدند.
نقش Execution Policy در اسکن موازی
یکی از مفاهیم کلیدی برای استفاده از الگوریتمهای موازی در C++17، Execution Policy است. سیاستهایی مانند seq و par مشخص میکنند که الگوریتم چگونه مجاز است اجرا شود. سیاست seq اجرای ترتیبی را مشخص میکند، در حالی که par اجازه میدهد اجرای الگوریتم میان چند مسیر اجرایی یا Thread تقسیم شود.
نکته مهم این است که استفاده از سیاست موازی الزاماً به این معنا نیست که اجرای موازی همیشه سریعتر خواهد بود. برای دادههای کوچک، هزینه ایجاد و هماهنگسازی عملیات موازی ممکن است بیشتر از مزیت آن باشد. بنابراین استفاده مؤثر از الگوریتمهای Scan موازی زمانی اهمیت بیشتری پیدا میکند که حجم داده و هزینه محاسبات به اندازهای باشد که موازیسازی بتواند مزیت واقعی ایجاد کند.
اهمیت الگوریتمهای اسکن موازی در C++17
الگوریتمهای Scan یکی از نمونههای مهم تغییر رویکرد STL در C++17 به سمت پردازش موازی هستند. این الگوریتمها به برنامهنویس اجازه میدهند بدون پیادهسازی دستی سازوکارهای پیچیده Thread و تقسیم داده، از قابلیتهای موازیسازی کتابخانه استاندارد استفاده کند.
شناخت تفاوت inclusive_scan و exclusive_scan، نحوه ترکیب آنها با Transform و همچنین مفهوم Execution Policy، پایه مهمی برای استفاده صحیح از Parallel STL محسوب میشود. این مفاهیم در پروژههایی که با حجم زیادی از داده سروکار دارند میتوانند نقش مهمی در طراحی الگوریتمهای کارآمد و قابل توسعه داشته باشند.
کلیدواژه ها : برنامهنویسی-موازی-C++17- الگوریتمهای-اسکن-موازی-در-STL- الگوریتمهای-موازی-STL- C++17-Parallel-Algorithms- Parallel-STL- Parallel-Scan- C++-Scan-Algorithms- Inclusive-Scan- Exclusive-Scan- Transform-Inclusive-Scan- Transform-Exclusive-Scan- Execution-Policy- C++17-Execution-Policy- اجرای-موازی-در-C++- پردازش-موازی-داده-ها- الگوریتمهای-STL- C++17-STL-Parallel-Algorithms-
