ر C++17، دو الگوریتم موازی جدید به نام‌های std::reduce و std::transform_reduce به کتابخانه‌ی استاندارد اضافه شده‌اند که در هدر <numeric> تعریف شده‌اند . این الگوریتم‌ها، نسخه‌های موازی و کارآمدی از عملیات‌های تجمیع (Aggregation) هستند که امکان پردازش موازی مجموعه‌داده‌های بزرگ را با عملکردی بسیار بهتر از نسخه‌های ترتیبی خود فراهم می‌کنند. هر دو الگوریتم از سیاست‌های اجرایی seq، par و par_unseq پشتیبانی می‌کنند و می‌توانند در سناریوهای مختلف بهینه‌سازی شوند.

std::reduce: نسخه‌ی موازی std::accumulate

std::reduce در واقع نسخه‌ی موازی و بهبودیافته‌ی std::accumulate محسوب می‌شود . در حالی که accumulate عناصر را به‌صورت ترتیبی و از چپ به راست ترکیب می‌کند، reduce اجازه می‌دهد تا عملیات ترکیب به‌صورت نامرتب و با گروه‌بندی دلخواه روی عناصر اعمال شود . این تفاوت به کامپایلر و کتابخانه اجازه می‌دهد تا عملیات را به بخش‌های کوچک‌تری تقسیم کرده و آنها را روی ریسه‌های مختلف موازی‌سازی کند.

این تابع در چندین نسخه ارائه شده است: یک نسخه که عملگر جمع پیش‌فرض (std::plus<>()) را به‌کار می‌گیرد، و نسخه‌ی دیگر که یک عملگر دودویی سفارشی (BinaryOp) دریافت می‌کند. همچنین می‌توان یک مقدار اولیه (init) برای شروع عملیات کاهش مشخص کرد .

مهم‌ترین نکته در مورد std::reduce این است که عملگر دودویی ارائه‌شده باید انجمنی (Associative) و جابه‌جایی‌پذیر (Commutative) باشد؛ در غیر این صورت، نتیجه‌ی اجرا غیرقطعی (Non-deterministic) خواهد بود . این محدودیت به‌دلیل آزادی عمل کتابخانه در گروه‌بندی و ترتیب‌دهی مجدد عناصر در حین موازی‌سازی است.

std::transform_reduce: ترکیب تبدیل و کاهش

std::transform_reduce یک الگوریتم قدرتمندتر است که عملیات تبدیل (Transform) و کاهش (Reduce) را در یک مرحله ترکیب می‌کند . این تابع می‌تواند به دو شکل اصلی عمل کند: روی یک محدوده (یک عملگر تبدیل یکانی + یک عملگر کاهش دودویی) یا روی دو محدوده (یک عملگر تبدیل دودویی + یک عملگر کاهش دودویی). حالت خاص آن که معادل نسخه‌ی موازی std::inner_product محسوب می‌شود، برای محاسبه‌ی ضرب داخلی دو بردار در مجموعه‌داده‌های بزرگ، بسیار کارآمد است .

این الگوریتم ابتدا تابع transform را روی هر عنصر (یا هر جفت عنصر از دو محدوده) اعمال می‌کند و سپس نتایج را به‌همراه مقدار اولیه با استفاده از تابع reduce ترکیب می‌کند . مشابه reduce، عملگرهای transform و reduce نباید عناصر محدوده را تغییر دهند یا تکرارگرها را باطل کنند .

مزایا و کاربردهای عملی

مهم‌ترین مزیت این الگوریتم‌ها نسبت به نسخه‌های قدیمی (accumulate و inner_product)، افزایش چشمگیر سرعت در پردازش مجموعه‌داده‌های بزرگ است. برای مثال، محاسبه‌ی مجموع یک آرایه‌ی میلیون‌عنصری یا ضرب داخلی دو بردار بزرگ، می‌تواند با استفاده از std::reduce(std::execution::par, ...) چندین برابر سریع‌تر از نسخه‌ی ترتیبی اجرا شود. البته باید توجه داشت که موازی‌سازی برای مجموعه‌داده‌های کوچک، سربار ایجاد ریسه‌ها را توجیه نمی‌کند و در آن موارد اجرای ترتیبی ممکن است بهتر باشد .

نکات مهم در پیاده‌سازی و پشتیبانی

پیاده‌سازی کامل این الگوریتم‌ها در کتابخانه‌های استاندارد مختلف با سرعت متفاوتی صورت گرفته است. برای مثال، در کتابخانه‌ی libstdc++ (مربوط به GCC)، پیاده‌سازی سریال این الگوریتم‌ها مدتی پس از نسخه‌ی موازی آنها اضافه شده است . همچنین پیاده‌سازی‌های مختلف ممکن است همه‌ی الگوریتم‌ها را به‌صورت کامل موازی نکنند، اما reduce و transform_reduce جزو الگوریتم‌هایی هستند که در پیاده‌سازی‌های اصلی (مانند MSVC) موازی‌سازی شده‌اند .

کلیدواژه ها : std::reduce-std::transform_reduce-الگوریتم‌های موازی C++17-کاهش موازی در C++-ترکیب تبدیل و کاهش-std::accumulate موازی-std::inner_product موازی-هدر numeric در C++17-سیاست اجرایی par-الگوریتم‌های کاهش STL-عملگر انجمنی در reduce-پرفورمنس transform_reduce-مدیریت مجموعه‌داده بزرگ-آموزش std::reduce-آموزش std::transform_reduce