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

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

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

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

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

نتایج نشان می‌دهد که کدهای تولیدشده توسط کامپایلر متقارن، سرعت‌های قابل‌توجهی نسبت به پیاده‌سازی ساده‌ی همان هسته‌ها دارند. این بهبود از حدود ۱٫۳۶ برابر برای ضرب ماتریس متقارن در بردار شروع می‌شود و تا ۷٫۹۵ برابر برای ضرب ماتریسی‌شده‌ی تنسور در حاصل‌ضرب کاتری-رائو چهاربعدی می‌رسد. در هسته‌هایی که ذاتاً محدود به پهنای باند حافظه هستند، مانند ضرب ماتریس متقارن در بردار، صرفه‌جویی در خواندن حافظه نقش اصلی را ایفا می‌کند. در هسته‌هایی که محدود به توان محاسباتی هستند، مانند ضرب ماتریس در ماتریس متقارن، کاهش محاسبات تکراری و نوشتن در خروجی نقش کلیدی دارد. به‌طور کلی، هرچه ابعاد تنسور و تعداد اندیس‌های متقارن بیشتر باشد، سود حاصل از بهره‌برداری از تقارن چشمگیرتر می‌شود، هرچند هزینه‌ی کنترل جریان نیز افزایش می‌یابد. در تنسورهای با ابعاد بالاتر، نسبت عناصر قطری به کل عناصر کاهش می‌یابد و همین امر مدیریت کارآمد قطرها را به چالشی مهم تبدیل می‌کند.

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

وقتی تقارن، محاسبات را شش تا بیست‌وچهار برابر سریع‌تر می‌کند!

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

تقارن فقط یک زیبایی ریاضی نیست؛ یک اهرم قدرتمند است

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

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

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

دو استراتژی ساده که همه‌چیز را تغییر می‌دهد

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

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

نکته‌ی جالب اینجاست که این دو استراتژی با هم جمع می‌شوند. شما هم حافظه‌ی کمتری می‌خوانید و هم محاسبات کمتری انجام می‌دهید. نتیجه؟ سرعت‌هایی که باورکردنی نیستند.

یک کامپایلر که خودش این کارها را انجام می‌دهد

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

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

این کامپایلر روی شش هسته‌ی تنسوری رایج آزمایش شده است: ضرب ماتریس متقارن در بردار، ضرب سه‌گانه‌ی متقارن، ضرب ماتریس در ماتریس متقارن، به‌روزرسانی رتبه‌کاهی متقارن، ضرب تنسور در ماتریس، و ضرب ماتریسی‌شده‌ی تنسور در حاصل‌ضرب کاتری-رائو. نتایج نشان می‌دهد که کدهای تولیدشده به‌طور میانگین از ۱٫۳۶ برابر تا ۷٫۹۵ برابر سریع‌تر از پیاده‌سازی ساده‌ی همان هسته‌ها عمل می‌کنند.

اعداد و ارقامی که داستان را کامل می‌کنند

بیایید به چند عدد واقعی نگاه کنیم. در هسته‌ی ضرب ماتریس متقارن در بردار، بهترین سرعت مشاهده‌شده ۱٫۸۵ برابر بوده است. این هسته ذاتاً محدود به پهنای باند حافظه است، بنابراین صرفه‌جویی در خواندن حافظه مستقیماً به سرعت تبدیل می‌شود.

در هسته‌ی ضرب تنسور در ماتریس، بهترین سرعت ۲٫۲۷ برابر بوده است. این هسته هم از تقارن ورودی و هم از تقارن خروجی بهره می‌برد. در تنسورهای با ابعاد بالاتر، این عدد چشمگیرتر می‌شود: برای ضرب ماتریسی‌شده‌ی تنسور در حاصل‌ضرب کاتری-رائو چهاربعدی، سرعت به ۷٫۹۵ برابر می‌رسد. و اگر فقط بخش غیرقطری را در نظر بگیریم، این عدد به ۱۰٫۱۷ برابر هم می‌رسد.

جالب‌تر از همه، برای یک تنسور پنج‌بعدی، پژوهشگران سرعت ۵۴٫۵۶ برابر را گزارش کرده‌اند. این عدد تقریباً با ۵! (صد و بیست) فاصله دارد، اما با در نظر گرفتن سرباز کنترل جریان، کاملاً منطقی به نظر می‌رسد. پیام واضح است: هرچه ابعاد بالاتر برود، بهره‌برداری از تقارن سود بیشتری دارد.

چرا این موضوع مهم است؟

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

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

«کامپایلرهای موجود یا اصلاً از تقارن بهره نمی‌برند یا آن را به‌طور کامل مورد استفاده قرار نمی‌دهند. این پژوهش یک رویکرد دانه‌دانه برای شناسایی تقارن در یک هسته‌ی تنسوری و تولید کدی که این تقارن را با موفقیت بهره‌برداری می‌کند، ارائه می‌دهد.»

موانع و چالش‌ها

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

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

آینده‌ای که در آن تقارن یک ویژگی پیش‌فرض است

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

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