محدودیت اِمدال: چرا سرعت پردازش موازی همیشه در گرو بخش‌های متوالی کد است؟

یک کار محاسباتی را تصور کنید که انجام آن روی یک پردازنده دقیقاً ۱۰۰ ساعت زمان می‌برد. اگر بتوان ۹۵ ساعت از این زمان را به‌طور بی‌نقص میان بی‌نهایت کارگر تقسیم کرد، اما ۵ ساعت باقی‌مانده شامل مراحلی متوالی باشد که باید یکی پس از دیگری اجرا شوند، مطلقاً کمترین زمان ممکن برای پایان این کار همان ۵ ساعت خواهد بود. حداکثر افزایش سرعت نظری، فارغ از اینکه ده هسته به کار بگیرید یا ده میلیون هسته، روی ۲۰ برابر سرعت اولیه قفل شده است.

این سقف سخت ریاضی یک نقص در سخت‌افزارهای مدرن نیست، بلکه یکی از قوانین بنیادین علوم کامپیوتر است. این اصل که نخستین بار در سال ۱۹۶۷ توسط جین اِمدال، معمار کامپیوتر، در کنفرانس مشترک بهاری فدراسیون انجمن‌های پردازش اطلاعات آمریکا (AFIPS) مطرح شد، دیکته می‌کند که کسر متوالی یک برنامه، شتاب کلی آن را به‌طور نامتناسبی محدود می‌سازد.[1]

استدلال پشت این قانون، شفاف و بی‌رحمانه است. همان‌طور که در کتاب «سنجش عملکرد کامپیوتر» تعریف شده، تز اصلی «اساساً این است که بهبود عملکرد کلی مشاهده‌شده در یک برنامه کاربردی، توسط آن بخش از برنامه که از تغییرات اعمال‌شده بر سیستم تأثیر نمی‌پذیرد، محدود می‌شود.»[5]

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

برای مشاهده این محدودیت در عمل، نرم‌افزاری را در نظر بگیرید که ۹۰ درصد کد آن می‌تواند به‌صورت موازی اجرا شود و ۱۰ درصد آن متوالی است. اگر یک تیم مهندسی سرور خود را از یک ماشین تک‌هسته‌ای به یک ماشین ۱۰ هسته‌ای ارتقا دهد، این فرمول افزایش سرعتی معادل ۵.۲۶ برابر را به ما نشان می‌دهد.[2][4]

حال اگر همین تیم تصمیم بگیرد هزینه هنگفتی برای یک کلاستر ابررایانه ۱۰۰۰ هسته‌ای بپردازد تا دقیقاً همان بار کاری را اجرا کند، ریاضیات یک سیلی محکم از واقعیت به آن‌ها می‌زند. افزایش سرعت تنها به ۹.۹۱ برابر می‌رسد. آن ۹۹۰ پردازنده اضافی تقریباً هیچ بازده نهایی به همراه نداشتند، زیرا اکنون همان گلوگاه ۱۰ درصدی متوالی است که بر زمان اجرا مسلط شده است.[3][8]

این حد مجانبی به‌خوبی توضیح می‌دهد که چرا فشار بی‌امان صنعت فناوری به سمت پردازنده‌های چندهسته‌ای — و عرضه تراشه‌های مصرفی با ۱۶، ۲۴ یا حتی ۶۴ هسته — اغلب نمی‌تواند به افزایش عملکرد متناسب در نرم‌افزارهای روزمره دسکتاپ ترجمه شود.[7]

یک تحلیل در سال ۲۰۲۳ تأکید می‌کند که اگرچه معماری‌های پردازش موازی برای پردازش داده‌های مدرن ضروری هستند، اما سربار ناشی از هماهنگ‌سازی پردازنده‌های متعدد — مانند همگام‌سازی رشته‌ها و انتقال داده‌ها — در صورتی که کسر موازی به‌اندازه کافی بزرگ نباشد، می‌تواند در عمل باعث افت عملکرد شود.[6]

قوی‌ترین استدلال متقابل در برابر این مرز بدبینانه از سوی جان گوستافسون مطرح می‌شود که در سال ۱۹۸۸ قانون گوستافسون را معرفی کرد. گوستافسون استدلال کرد که فرض ثابت بودن اندازه بار کاری، که با عنوان مقیاس‌پذیری قوی شناخته می‌شود، بازتاب‌دهنده نحوه استفاده واقعی انسان‌ها از قدرت محاسباتی عظیم نیست.[3][4]

وقتی محققان به یک ابررایانه بزرگ‌تر دسترسی پیدا می‌کنند، به‌ندرت از آن برای حل سریع‌ترِ دقیقاً همان مسئله قبلی استفاده می‌کنند. در عوض، آن‌ها اندازه مسئله را بزرگ‌تر می‌کنند؛ مثلاً یک سیستم آب‌وهوایی وسیع‌تر را شبیه‌سازی می‌کنند، تصویری با وضوح بالاتر رندر می‌گیرند، یا یک شبکه عصبی پیچیده‌تر را آموزش می‌دهند.[8]

در مدل گوستافسون که به مقیاس‌پذیری ضعیف معروف است، کسر متوالی ثابت نمی‌ماند. با بزرگ‌تر شدن اندازه کلی مسئله، بخش قابل موازی‌سازی معمولاً بسیار سریع‌تر از فازهای متوالی راه‌اندازی و خاتمه رشد می‌کند و به سیستم اجازه می‌دهد تا در مجموعه داده‌های عظیم به افزایش سرعت تقریباً خطی دست یابد.[3][7]

با این حال، محدودیت اولیه سال ۱۹۶۷ برای برنامه‌های حساس به تأخیر که در آن‌ها نمی‌توان اندازه مسئله را به‌طور دلخواه افزایش داد، همچنان پابرجاست. یک پرس‌وجوی پایگاه داده که باید در ۵۰ میلی‌ثانیه پاسخ دهد را نمی‌توان مقیاس‌پذیر کرد؛ این پرس‌وجو صرفاً باید سریع‌تر اجرا شود.[1][6]

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

در همین حال، بارهای کاری که واقعاً دارای کسر موازی نزدیک به ۹۹.۹ درصد هستند — مانند رندر گرافیکی و ضرب ماتریس برای هوش مصنوعی — به‌طور کامل از پردازنده‌های مرکزی همه‌منظوره فاصله گرفته‌اند.[8]

این وظایف به‌شدت موازی، در عوض روی واحدهای پردازش گرافیکی و واحدهای پردازش تنسور اجرا می‌شوند؛ تراشه‌هایی که بهینه‌سازی‌های پیچیده متوالی را کنار گذاشته‌اند تا هزاران هسته ساده‌تر و کندتر را روی یک تراشه واحد جای دهند.[7][8]

مرزی که شش دهه پیش تعیین شد، همچنان اقتصاد رایانش ابری را دیکته می‌کند. اجاره یک ماشین مجازی عظیم ۱۲۸ هسته‌ای در آمازون وب سرویسز یا مایکروسافت آژور، اگر برنامه مستقرشده به‌شدت متوالی باشد، چیزی جز هدر دادن سرمایه نیست.[6]

بنابراین، مهندسان نرم‌افزار باید پیش از تأمین سخت‌افزار، کدهای خود را با دقت پروفایل کرده و کسر دقیق متوالی را شناسایی کنند. اگر رقابت بر سر قفل‌ها یا وابستگی متوالی داده‌ها وجود داشته باشد، ریختن سیلیکون بیشتر به پای مسئله تنها هزینه‌ها را افزایش می‌دهد، نه توان عملیاتی را.[4][6]

مرز بعدی در شتاب‌بخشی محاسباتی، نه از طریق افزایش ساده تعداد هسته‌ها، بلکه از دل پیشرفت‌های الگوریتمی بیرون خواهد آمد که وابستگی‌های متوالی را به ساختارهای قابل موازی‌سازی بازنویسی کرده و کسر موازی را بیش از پیش به عدد یک نزدیک می‌کنند.[8]