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

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

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

یکی از نوآوری‌های کلیدی این پژوهش، نحوهٔ تقسیم داده‌ها میان واحدهای پردازشی است. در سامانه‌ای با حافظهٔ توزیع‌شده، شیوهٔ توزیع داده‌ها به‌طور مستقیم بر حجم ارتباطات شبکه‌ای و توازن بار میان واحدها اثر می‌گذارد. اگر داده‌های مرتبط در واحدهای دور از هم قرار گیرند، حجم زیادی پیام میان آن‌ها رد و بدل می‌شود و شبکه به گلوگاه تبدیل می‌شود. از سوی دیگر، اگر بار محاسباتی به‌طور نامتوازن توزیع شود، برخی واحدها بیکار می‌مانند در حالی که برخی دیگر بیش از حد مشغول‌اند و زمان کل اجرا توسط کندترین واحد تعیین می‌شود. روش‌های پیشین معمولاً تنها یکی از این دو هدف را دنبال می‌کنند یا هر دو را فقط برای کاربردهایی با الگوی تُنُکی ثابت و بدون تغییر در طول اجرا در نظر می‌گیرند. اما بسیاری از کاربردهای هدف، الگوی تُنُکی پویا دارند؛ یعنی توزیع عناصر غیرصفر در طول تکرارها تغییر می‌کند. برای نمونه، در جست‌وجوی سطح‌به‌سطح، مجموعهٔ گره‌هایی که در هر تکرار بررسی می‌شوند تغییر می‌کند و در نتیجه، بخش فعال ماتریس نیز از تکرار به تکرار متفاوت است. این پژوهش نخستین روشی را ارائه می‌دهد که هم‌زمان توازن بار و کمینه‌سازی ارتباطات را برای کاربردهایی با تُنُکی پویا نیز ممکن می‌سازد.

روش تقسیم‌بندی پیشنهادی از ترکیب پارتیشن‌بندی گراف و ابرگراف بهره می‌گیرد و در دو مرحله انجام می‌شود. در مرحلهٔ نخست، عناصری که احتمال می‌رود در یک تکرار با هم استفاده شوند، در خوشه‌هایی گروه‌بندی می‌شوند. در مرحلهٔ دوم، هر خوشه به‌طور مستقل میان همهٔ واحدهای پردازشی توزیع می‌شود تا ارتباطات درون‌خوشه‌ای کمینه شود. این راهبرد، برخلاف روش‌های پیشین، هم بار محاسباتی را متوازن می‌کند و هم مسیر ارتباطات را کوتاه نگه می‌دارد. افزون بر این، برای کاهش مسافت فیزیکی پیام‌ها، پارتیشن‌بندی به‌صورت بازگشتی و ابتدا در سطح تراشه‌ها و سپس در سطح واحدهای درون هر تراشه انجام می‌شود. برای کاربردهایی که همهٔ عملوندهایشان الگوی تُنُکی ثابت دارند، همانند روش‌های پیشین، ابرگراف وابستگی‌های داده را مدل می‌کند و گره‌هایی که در یک محاسبه شریک‌اند با یال‌هایی به هم متصل می‌شوند؛ سپس الگوریتم پارتیشن‌بندی ابرگراف گره‌ها را به گروه‌هایی با اندازهٔ تقریباً برابر تقسیم می‌کند و شمار یال‌های بریده‌شده را کمینه می‌سازد. نتایج نشان می‌دهد که این ترکیب، به‌ویژه در کاربردهایی با رفتار پویا، بهبود چشمگیری در کارایی به همراه دارد و به‌طور میانگین چند برابر سریع‌تر از روش‌های تک‌هدفی عمل می‌کند.

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

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

در مجموع، این پایان‌نامه گامی نخست به‌سوی معماری‌ای عمومی، برنامه‌پذیر و بسیار کارآمد برای محاسبات تُنُک تکرارشونده برمی‌دارد. معماری ارائه‌شده نشان می‌دهد که می‌توان هم‌زمان به کارایی بالا و انعطاف‌پذیری دست یافت، به شرط آنکه محاسبات به وظایف کوچک و متناسب با سخت‌افزار شکسته شوند و داده‌ها با دقت و هوشمندی میان واحدهای پردازشی توزیع گردند. این رویکرد می‌تواند زمینه‌ساز پژوهش‌های آینده در حوزه‌هایی مانند یادگیری ماشین، روش‌های صوری و کاربردهایی با تُنُکی پویا در دو سو باشد و مسیر تازه‌ای برای طراحی شتاب‌دهنده‌های نسل آینده بگشاید. با توجه به گسترش روزافزون داده‌های تُنُک در حوزه‌های گوناگون، چنین معماری‌هایی می‌توانند نقش مهمی در تأمین توان محاسباتی لازم برای نسل‌های آیندهٔ الگوریتم‌های علمی و تحلیلی ایفا کنند و راه را برای سامانه‌هایی هموار سازند که هم سریع‌اند و هم قابل برنامه‌نویسی.

راز یک شتاب‌دهنده: وقتی حافظه‌های کوچک، محاسبات غول‌آسا را ممکن می‌کنند

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

وقتی داده‌ها تُنُک می‌شوند، سخت‌افزار به زانو درمی‌آید

در بسیاری از محاسبات علمی و تحلیل‌های شبکه‌ای، ماتریس‌هایی با میلیون‌ها درایه داریم که تقریباً همهٔ آن‌ها صفر هستند. به این ویژگی «تُنُکی» می‌گویند. مثلاً در یک شبکهٔ اجتماعی، هر کاربر با چند ده نفر ارتباط دارد، نه با میلیون‌ها نفر دیگر. پس ماتریس ارتباطات آن‌ها پر از صفر است. همین تُنُکی باعث می‌شود دسترسی به داده‌ها نامنظم و پراکنده شود و پردازنده‌های معمولی نتوانند از پهنای باند حافظه به‌درستی استفاده کنند. از طرفی، این محاسبات به ازای هر بایت داده‌ای که جابه‌جا می‌شود، عملیات ریاضی اندکی انجام می‌دهند؛ یعنی «شدت محاسباتی» پایینی دارند. نتیجه؟ گلوگاه همیشه حافظه است، نه پردازنده.

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

مشکل بزرگ: تقسیم داده‌ها میان صدها حافظهٔ کوچک

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

اما بسیاری از کاربردهای واقعی، الگوی تُنُکی پویا دارند. مثلاً در جست‌وجوی سطح‌به‌سطح، مجموعهٔ گره‌هایی که در هر تکرار بررسی می‌شوند تغییر می‌کند و بخش فعال ماتریس از تکرار به تکرار متفاوت است. این پویایی کار تقسیم‌بندی را بسیار دشوار می‌کند.

راه‌حل: ترکیب هوشمندانهٔ پارتیشن‌بندی گراف و ابرگراف

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

این روش دو مرحله‌ای، برخلاف روش‌های پیشین، هم بار محاسباتی را متوازن می‌کند و هم مسیر ارتباطات را کوتاه نگه می‌دارد. نتایج نشان می‌دهد که این ترکیب، به‌ویژه در کاربردهایی با رفتار پویا، بهبود چشمگیری در کارایی به همراه دارد.

«این نخستین روشی است که هم‌زمان توازن بار و کمینه‌سازی ارتباطات را برای کاربردهایی با تُنُکی پویا ممکن می‌سازد.»

معماری‌ای که مثل یک ارکستر، هر لحظه خودش را کوک می‌کند

معماری پیشنهادی به‌جای اجرای دستورهای متوالی، از «وظایف کوتاه جریان‌داده» استفاده می‌کند. هر وظیفه با رسیدن یک پیام از شبکه یا اتمام یک وظیفهٔ محلی فعال می‌شود و به‌طور میانگین تنها چند ده عملیات انجام می‌دهد. هر واحد پردازشی می‌تواند بر اساس پیام‌های دریافتی، پیکربندی خود را به‌سرعت تغییر دهد و وظیفهٔ متناسب با دادهٔ محلی خود را اجرا کند. این پیکربندی مجدد با استفاده از سلول‌های دو-بافری انجام می‌شود تا پیکربندی وظیفهٔ بعدی هم‌زمان با اجرای وظیفهٔ جاری بارگذاری شود.

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

برنامه‌نویسی بدون دردسر: از اینزوم تا وظیفه

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

این چارچوب، طیف گسترده‌ای از کاربردها را با تعداد محدودی نوع وظیفه پوشش می‌دهد و برنامه‌پذیری را بدون از دست دادن کارایی فراهم می‌کند. به بیان دیگر، برنامه‌نویس لازم نیست نگران جزئیات سخت‌افزاری باشد؛ کافی است محاسبه را به زبان ریاضی بنویسد و بقیهٔ کارها به‌طور خودکار انجام می‌شود.

نتیجه: بیست‌وشش برابر سریع‌تر از بهترین سامانهٔ پیشین

کارایی این معماری در شبیه‌سازی با پیکربندی چندتراشه‌ای شامل بیش از شانزده هزار واحد پردازشی و چند گیگابایت حافظهٔ روی‌تراشه ارزیابی شده است. شش کاربرد نمونه از حوزه‌های محاسبات علمی و تحلیل گراف بررسی شده‌اند: جست‌وجوی سطح‌به‌سطح، کوتاه‌ترین مسیر تک‌منبعی، مؤلفه‌های همبند ضعیف، گرادیان‌های مزدوج، تکرار چبیشف و روش گرادیان مزدوج اولیه-دوگان.

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

این پژوهش گامی نخست به‌سوی معماری‌ای عمومی، برنامه‌پذیر و بسیار کارآمد برای محاسبات تُنُک تکرارشونده برمی‌دارد. معماری ارائه‌شده نشان می‌دهد که می‌توان هم‌زمان به کارایی بالا و انعطاف‌پذیری دست یافت، به شرط آنکه محاسبات به وظایف کوچک و متناسب با سخت‌افزار شکسته شوند و داده‌ها با دقت و هوشمندی میان واحدهای پردازشی توزیع گردند. با توجه به گسترش روزافزون داده‌های تُنُک در حوزه‌های گوناگون، چنین معماری‌هایی می‌توانند نقش مهمی در تأمین توان محاسباتی لازم برای نسل‌های آیندهٔ الگوریتم‌های علمی و تحلیلی ایفا کنند.