بازآرایی گراف در GPU: کلیدی پنهان برای تسریع جستجوی برداری در هوش مصنوعی 🚀

جستجوی تقریبی نزدیک‌ترین همسایه (ANNS) یکی از پایه‌ای‌ترین چالش‌ها در کاربردهای مدرن هوش مصنوعی است. از سیستم‌های بازیابی اطلاعات گرفته تا پایگاه‌های داده برداری و مدل‌های زبانی بزرگ که از بازیابی اطلاعات تقویتی (RAG) استفاده می‌کنند، همگی به توانایی بازیابی سریع و کارآمد مشابه ترین بردارها از یک مجموعه داده عظیم متکی هستند. در این میان، رویکردهای مبتنی بر گراف به دلیل توازن فوق‌العاده بین دقت و سرعت، به ویژه بر روی پردازنده‌های گرافیکی (GPU)، به پارادایم غالب تبدیل شده‌اند.

با این حال، با وجود تحقیقات گسترده برای بهینه‌سازی ساختار توپولوژیکی این گراف‌ها، یک جنبه حیاتی و تأثیرگذار بر عملکرد، یعنی چیدمان حافظه (Memory Layout)، تا حد زیادی نادیده گرفته شده است. عملکرد GPU به شدت به الگوهای دسترسی به حافظه وابسته است و این مقاله به این سوال اساسی می‌پردازد: چگونه می‌توانیم رئوس یک گراف را در حافظه مرتب کنیم تا تنگناهای دسترسی به حافظه را کاهش داده و کارایی جستجوی ANNS بر روی GPU را به حداکثر برسانیم؟

مشکل اصلی: دسترسی پراکنده به حافظه در GPU ⛓️

برای درک اهمیت چیدمان حافظه، ابتدا باید با معماری حافظه GPU آشنا شویم. برخلاف CPU که برای پردازش متوالی با تأخیر کم بهینه شده است، GPU برای محاسبات موازی با توان عملیاتی بالا طراحی شده و هزاران رشته (thread) را به طور همزمان اجرا می‌کند. معماری حافظه GPU دارای سلسله مراتبی است: حافظه سراسری (Global Memory) با ظرفیت بالا اما تأخیر زیاد، و حافظه‌های کش L1/L2 و حافظه اشتراکی (Shared Memory) با ظرفیت کمتر اما سرعت دسترسی بسیار بالاتر.

کلید دستیابی به عملکرد بالا در GPU، “دسترسی یکپارچه به حافظه” (Coalesced Memory Access) است. پردازنده‌های گرافیکی رشته‌ها را در گروه‌های ۳۲ تایی به نام “warp” اجرا می‌کنند. وقتی تمام رشته‌های یک warp به آدرس‌های متوالی و پشت سر هم در حافظه دسترسی پیدا می‌کنند، GPU می‌تواند تمام این درخواست‌ها را در یک تراکنش واحد و بزرگ ادغام کند که این کار باعث استفاده حداکثری از پهنای باند حافظه می‌شود. در مقابل، اگر رشته‌ها به آدرس‌های پراکنده و نامرتبط دسترسی پیدا کنند، GPU مجبور به انجام تراکنش‌های متعدد و کوچک می‌شود که بسیار کند و ناکارآمد است.

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

راه‌حل: بازآرایی گراف (Graph Reordering) اینجاست که “بازآرایی گراف” وارد می‌شود. این تکنیک با تغییر ترتیب شناسه‌های رأس (vertex IDs)، گره‌هایی که به طور مکرر با هم یا به صورت متوالی در طول جستجو مورد دسترسی قرار می‌گیرند را در مکان‌های حافظه پشت سر هم قرار می‌دهد. این کار الگوهای دسترسی پراکنده را به دسترسی‌های متوالی تبدیل کرده و به طور مستقیم باعث بهبود استفاده از کش و افزایش دسترسی یکپارچه می‌شود و در نتیجه، سرعت جستجو را افزایش می‌دهد.

یک چارچوب یکپارچه برای ارزیابی منصفانه 📊

یکی از چالش‌های اصلی در بررسی اثربخشی بازآرایی گراف، این است که شاخص‌های گراف مختلف (مانند NSG، Vamana، CAGRA) هر کدام با پیاده‌سازی‌ها، ساختارهای داده و الگوریتم‌های جستجوی منحصربه‌فرد خود ارائه می‌شوند. این تفاوت‌ها، مقایسه منصفانه و سیستماتیک را غیرممکن می‌سازد. آیا یک شاخص سریع‌تر است چون توپولوژی بهتری دارد یا چون کد آن بهینه‌تر نوشته شده است؟

برای حل این مشکل، این تحقیق یک “چارچوب ارزیابی یکپارچه” (Unified Evaluation Framework) نوآورانه را معرفی می‌کند. این چارچوب دارای دو جزء کلیدی است:

1. آداپتور گراف (Graph Adapter): این جزء هر نوع شاخص گراف از پیش ساخته شده‌ای را دریافت کرده و توپولوژی آن را بدون تغییر، به یک نمایش استاندارد و سازگار با GPU تبدیل می‌کند.
2. موتور جستجوی یکپارچه (Unified Search Engine): تمام گراف‌های استاندارد شده با استفاده از یک الگوریتم جستجوی واحد و بسیار بهینه‌شده برای GPU (پیاده‌سازی traversal از CAGRA) ارزیابی می‌شوند.

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

آزمایش‌ها و نتایج کلیدی: چهار یافته شگفت‌انگیز 📈

با استفاده از این چارچوب، محققان مجموعه‌ای جامع از آزمایش‌ها را بر روی شاخص‌های مختلف (CAGRA، NSG، Vamana، NN-Descent)، الگوریتم‌های بازآرایی متنوع و طیف وسیعی از مجموعه داده‌های سنتی و مدرن (با ابعاد بالا) انجام دادند. نتایج، چهار یافته کلیدی و بعضاً شگفت‌انگیز را آشکار کرد:

• یافته ۱: برتری غیرمنتظره الگوریتم‌های طراحی‌شده برای CPU. وقتی شاخص‌های مختلف تحت موتور جستجوی یکپارچه GPU اجرا شدند، NSG و Vamana که در اصل برای CPU طراحی شده بودند، در بسیاری از مجموعه داده‌ها عملکردی مشابه یا حتی بهتر از شاخص CAGRA که مخصوص GPU بهینه‌سازی شده بود، از خود نشان دادند. این یافته نشان می‌دهد که وقتی الگوریتم جستجو و چیدمان حافظه یکسان باشد، تفاوت‌های توپولوژیکی تأثیر کمتری بر توان عملیاتی GPU دارند و تنگنای اصلی، الگوهای دسترسی به حافظه است.
• یافته ۲: بازآرایی گراف مؤثر است، اما اثربخشی آن به داده بستگی دارد. آزمایش‌ها تأیید کردند که بازآرایی گراف می‌تواند سرعت جستجو را به طور قابل توجهی بهبود بخشد و در برخی موارد تا ۱۵٪ افزایش در تعداد کوئری بر ثانیه (QPS) بدون هیچ‌گونه کاهش در دقت به همراه داشت. با این حال، این بهبود جهانی نبود. اثربخشی بازآرایی به شدت به مجموعه داده وابسته بود؛ برای مثال، در مجموعه داده‌های Deep10M و Yandex T2I بهبود قابل توجهی مشاهده شد، در حالی که در SIFT یا Wikipedia تأثیر آن ناچیز یا حتی منفی بود.
• یافته ۳: عدم وجود ارتباط قوی با ساختار جامعه گراف. در حالی که در سایر کاربردهای گراف، وجود ساختارهای اجتماعی قوی (community structures) – که با معیاری به نام ضریب خوشه‌بندی محلی (LCC) اندازه‌گیری می‌شود – معمولاً اثربخشی بازآرایی را افزایش می‌دهد، در این تحقیق هیچ ارتباط واضحی بین LCC و بهبود QPS مشاهده نشد. این نشان می‌دهد که پیش‌بینی اثربخشی بازآرایی در ANNS مبتنی بر GPU، به دلیل ماهیت متفاوت بار کاری و وجود بردارهای با ابعاد بالا، پیچیده‌تر از معیارهای ساختاری سنتی است.
• یافته ۴: تأثیر ابعاد برداری بر اثربخشی بازآرایی. آزمایش‌ها نشان داد که ابعاد بردارها تأثیر زیادی بر کارایی بازآرایی دارد. برای شاخص‌های طراحی‌شده برای CPU (NSG، Vamana، NN-Descent)، یک همبستگی منفی قوی مشاهده شد: هرچه ابعاد بردارها بالاتر می‌رفت، مزیت بازآرایی کمتر می‌شد. در مقابل، شاخص بومی GPU یعنی CAGRA چنین روندی را نشان نداد و عملکرد پایداری را در ابعاد مختلف حفظ کرد.

نتیجه‌گیری و چشم‌انداز آینده 🔮

این تحقیق برای اولین بار یک ارزیابی جامع از اثربخشی بازآرایی گراف برای تسریع جستجوی ANNS مبتنی بر گراف بر روی GPU ارائه می‌دهد. یافته‌های کلیدی نشان می‌دهند که بهینه‌سازی چیدمان حافظه یک تکنیک قدرتمند و “متعامد” (orthogonal) با نوآوری‌های الگوریتمی است که می‌تواند تا ۱۵٪ بهبود عملکرد را بدون تغییر در دقت به ارمغان آورد.

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

🔗مقاله اصلی