بهینه‌سازی افراطی یا Superoptimization یک شبیه‌ساز FPU با جستجوی جامع

مقدمه ای بر Superoptimization

توسعه‌دهندگان معمولاً برای بهینه‌سازی کدها به کامپایلرها اتکا می‌کنند، اما کامپایلرها در استدلال‌های غیربدیهی و ابداع رویکردهای کاملاً جدید چندان توانا نیستند. مفهوم Superoptimization فرآیندی است که در آن ابزارها به طور خودکار به دنبال بهینه‌ترین توالی از دستورات بدون حلقه می‌گردند. در جریان توسعه یک کتابخانه برای محاسبات ممیز شناور (Floating-point)، نویسنده با چالشی مواجه شد که در ادامه به جزئیات و راه‌حل آن پرداخته می‌شود.

چالش اصلی در محاسبات ممیز شناور

هدف، نوشتن تابعی بود که یک عدد ممیز شناور از نوع f32 را دریافت کرده و عددی معادل با پایین‌ترین بیت فعال (Lowest set bit) آن را تولید کند. پیاده‌سازی این منطق با ترفندهای بیتی (Bit twiddling) امکان‌پذیر است، اما الگوریتم ساده آن برای توان‌های دو دچار مشکل می‌شود و نیازمند استفاده از دستور شرطی if است:

if f32::from_bits(x.to_bits() & !f32::MANTISSA_MASK) == x {
    return x;
} else {
    return x - f32::from_bits(x.to_bits() & (x.to_bits() - 1));
}

این دستور شرطی باعث کند شدن اجرای کد در حالت رایج و خطای پیش‌بینی شاخه (Branch misprediction) می‌شود. هدف این بود که فرمولی بدون نیاز به if پیدا شود که به طور خودکار توان‌های دو را نیز مدیریت کند.

رویکرد جستجوی جامع (Brute-force) به جای هوش مصنوعی

به جای استفاده از مدل‌های زبانی بزرگ (LLM) که ممکن است الگوهای محبوب را بیش از حد بازتولید کنند، نویسنده تصمیم گرفت تمام فرمول‌های ممکن را با روش Brute-force جستجو کند. با محدود کردن تعداد عملگرها و ثابت‌ها، تعداد ترکیب‌های احتمالی به حد قابل قبولی کاهش یافت.

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

• فرمول‌ها با ۰ عملیات شامل متغیر x و ثابت‌ها هستند.
• فرمول‌های با n عملیات از ترکیب جفت فرمول‌های کوچکتر ساخته می‌شوند.
• حذف موارد تکراری (Deduplication) نقش کلیدی در کاهش زمان اجرا داشت؛ به طوری که کل فرآیند جستجو تنها در حدود ۴ دقیقه تکمیل شد.

نتایج شگفت‌انگیز

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

دیدگاه کاربران هکرنیوز

در بحث‌های هکرنیوز، نکات فنی جالبی مطرح شد:

• برخی کاربران اشاره کردند که بنچمارک گرفتن برای تک‌تک این ترکیب‌ها غیرممکن است.
• بحث‌هایی پیرامون استفاده از دستورات شمارش بیت (مانند ctz) شکل گرفت و اینکه عبور از دامنه اعداد صحیح به ممیز شناور در انتهای الگوریتم چه تأثیری بر عملکرد می‌گذارد.
• مقایسه‌ای میان کدهای دست‌ساز و کدهای تولیدشده توسط ابزارهای خودکار انجام شد و کارایی روش‌های کلاسیک به چالش کشیده شد.