يبتكر نظام الذكاء الاصطناعي التحسينات الأولى لفرز الكود منذ أكثر من عقد – Ars Technica

لا شك في أن أي شخص درس علوم الكمبيوتر الأساسية قد أمضى وقتًا في ابتكار خوارزمية الفرز – رمز يأخذ قائمة غير مرتبة من العناصر ويضعها في ترتيب تصاعدي أو تنازلي. إنه تحد مثير للاهتمام نظرًا لوجود العديد من الطرق للقيام بذلك ولأن الأشخاص قد أمضوا الكثير من الوقت في معرفة كيفية القيام بهذا الفرز بأكبر قدر ممكن من الكفاءة.

يعتبر الفرز أساسيًا لدرجة أن الخوارزميات مدمجة في معظم المكتبات القياسية للغات البرمجة. وفي حالة مكتبة C ++ المستخدمة مع مترجم LLVM ، لم يتم التطرق إلى الكود منذ أكثر من عقد.

لكن مجموعة DeepMind AI التابعة لشركة Google قد طورت الآن أداة تعلم معزز يمكنها تطوير خوارزميات محسّنة للغاية دون أن يتم تدريبها أولاً على أمثلة التعليمات البرمجية البشرية. كانت الحيلة هي إعداده للتعامل مع البرمجة كلعبة.

إنها كلها لعبة

DeepMind ، من بين أشياء أخرى ، معروف بتطويره لبرامج تعلم نفسها كيفية ممارسة الألعاب. لقد أثبت هذا النهج فعاليته العالية ، حيث قهر ألعاب متنوعة مثل الشطرنج ، يذهب، و ستار كرافت. بينما تختلف التفاصيل اعتمادًا على اللعبة التي يتعامل معها ، يتعلم البرنامج من خلال اللعب بنفسه ويكتشف الخيارات التي تسمح له بزيادة النتيجة إلى الحد الأقصى.

نظرًا لأنه لم يتم تدريبه على الألعاب التي يلعبها البشر ، يمكن لنظام DeepMind اكتشاف طرق للألعاب التي لم يفكر بها البشر. بالطبع ، نظرًا لأنها تلعب دائمًا ضد نفسها ، فهناك حالات طورت فيها نقاطًا عمياء يمكن للبشر استغلالها.

هذا النهج وثيق الصلة بالبرمجة. تكتب النماذج اللغوية الكبيرة رمزًا فعالًا لأنها شاهدت الكثير من الأمثلة البشرية. ولكن بسبب ذلك ، من غير المرجح أن يطوروا شيئًا لم يفعله البشر من قبل. إذا كنا نتطلع إلى تحسين الخوارزميات المفهومة جيدًا ، مثل وظائف الفرز ، فإن تأسيس شيء ما على رمز بشري موجود ، في أحسن الأحوال ، سيوفر لك أداءً مكافئًا. ولكن كيف تحصل على ذكاء اصطناعي لتحديد نهج جديد حقًا؟

اتخذ الأشخاص في DeepMind نفس النهج الذي اتبعوه مع لعبة الشطرنج و يذهب: لقد حولوا تحسين الكود إلى لعبة. طور نظام AlphaDev خوارزميات تجميع x86 التي تعاملت مع زمن انتقال الشفرة على أنها نتيجة وحاولت تقليل هذه النتيجة مع ضمان تشغيل الكود حتى الاكتمال دون أخطاء. من خلال التعلم المعزز ، يطور AlphaDev تدريجيًا القدرة على كتابة تعليمات برمجية محكمة وعالية الكفاءة.

داخل AlphaDev

إن القول بأن النظام يحسن زمن الانتقال يختلف تمامًا عن شرح كيفية عمله. مثل معظم أنظمة الذكاء الاصطناعي المعقدة الأخرى ، يتكون AlphaDev من عدة مكونات متميزة. إحداها هي وظيفة التمثيل ، والتي تتعقب الأداء العام للشفرة أثناء تطويرها. يتضمن هذا الهيكل العام للخوارزمية ، بالإضافة إلى استخدام سجلات x86 والذاكرة.

يضيف النظام تعليمات التجميع بشكل فردي ، يختارها أ البحث عن شجرة مونت كارلو– مرة أخرى ، نهج مستعار من أنظمة اللعب. يسمح الجانب “الشجري” لهذا النهج للنظام بالتضييق بسرعة على منطقة محدودة من نطاق كبير من التعليمات المحتملة ، بينما يضيف مونت كارلو درجة من العشوائية إلى التعليمات الدقيقة التي يتم اختيارها من هذا الفرع. (لاحظ أن “التعليمات” في هذا السياق تتضمن أشياء مثل السجلات المحددة المختارة لإنشاء تجميع صالح وكامل.)

يقوم النظام بعد ذلك بتقييم حالة رمز التجميع للكمون والصلاحية ويخصص له درجة ، ويقارن ذلك بدرجة النتيجة السابقة. ومن خلال التعلم المعزز ، فإنه يتعلق بالمعلومات حول كيفية عمل الفروع المختلفة للشجرة ، بالنظر إلى حالة البرنامج. بمرور الوقت ، “تتعلم” كيفية تحقيق حالة لعبة فائزة – فرز مكتمل – بأقصى درجة ، مما يعني حدًا أدنى من زمن الانتقال.

الفائدة الرئيسية من هذا النظام هي أن تدريبه لا يجب أن يتضمن أي أمثلة على الكود. بدلاً من ذلك ، يقوم النظام بإنشاء أمثلة التعليمات البرمجية الخاصة به ثم يقوم بتقييمها. في هذه العملية ، يتم تعليقها على معلومات حول مجموعات التعليمات الفعالة في الفرز.

كود مفيد

يمكن أن يتعامل الفرز في البرامج المعقدة مع مجموعات كبيرة وتعسفية من العناصر. ولكن على مستوى المكتبات القياسية ، فقد تم إنشاؤها من مجموعة كبيرة من الوظائف المحددة للغاية التي تتعامل مع موقف واحد فقط أو حالات قليلة. على سبيل المثال ، هناك خوارزميات منفصلة لفرز ثلاثة عناصر وأربعة عناصر وخمسة عناصر. وهناك مجموعة أخرى من الوظائف التي يمكنها التعامل مع عدد عشوائي من العناصر حتى الحد الأقصى – مما يعني أنه يمكنك استدعاء واحد يقوم بفرز ما يصل إلى أربعة عناصر ، ولكن ليس أكثر.

قام DeepMind بتعيين AlphaDev على كل من هذه الوظائف ، لكنها تعمل بشكل مختلف تمامًا. بالنسبة للوظائف التي تتعامل مع عدد محدد من العناصر ، من الممكن كتابة كود بدون أي فروع حيث تقوم بتنفيذ كود مختلف بناءً على حالة المتغير. نتيجة لذلك ، يتناسب أداء هذا الرمز بشكل عام مع عدد من التعليمات المطلوبة. كان AlphaDev قادرًا على حلق تعليمات كل من الفرز 3 و Sort-5 و Sort-8 ، وحتى أكثر من الفرز 6 و Sort-7. كان هناك واحد فقط (الترتيب 4) حيث لم يجد طريقة لتحسين الشفرة البشرية. أظهر التشغيل المتكرر للشفرة على الأنظمة الفعلية أن عددًا أقل من التعليمات أدى إلى أداء أفضل.

يتضمن فرز عدد متغير من الإدخالات التفريع في الكود ، وتحتوي المعالجات المختلفة على كميات مختلفة من الأجهزة المخصصة للتعامل مع هذه الفروع. لذلك ، تم تقييم الكود بناءً على أدائه على 100 جهاز مختلف. هنا مرة أخرى ، وجد AlphaDev طرقًا للضغط على أداء إضافي ، وسوف نلقي نظرة على كيفية القيام بذلك في موقف واحد: وظيفة تقوم بفرز ما يصل إلى أربعة عناصر.

في التطبيق الحالي في مكتبة C ++ ، يقوم الكود بسلسلة من الاختبارات لمعرفة عدد العناصر التي يحتاجها لفرز واستدعاء وظيفة الفرز المخصصة لهذا العدد من العناصر. الكود المنقح يفعل شيئًا أكثر غرابة. يختبر ما إذا كان هناك عنصرين ويستدعي وظيفة منفصلة لفرزهما إذا لزم الأمر. إذا كان العدد أكبر من عنصرين ، فإن الكود يستدعي فرز العناصر الثلاثة الأولى. إذا كان هناك ثلاثة عناصر ، فسيتم إرجاع نتائج هذا الفرز.

ومع ذلك ، إذا كان هناك أربعة عناصر لفرزها ، فإنها تقوم بتشغيل رمز متخصص فعال للغاية في إدراج عنصر رابع في المكان المناسب ضمن مجموعة من ثلاثة عناصر مرتبة. يبدو هذا وكأنه نهج غريب ، لكنه تفوق باستمرار على الكود الحالي.

في الانتاج

نظرًا لأن AlphaDev أنتج رمزًا أكثر كفاءة ، فقد أراد الفريق إعادة دمجها في مكتبة LLVM القياسية C ++. المشكلة هنا هي أن الكود كان في التجميع بدلاً من C ++. لذلك ، كان عليهم العمل للخلف واكتشاف كود C ++ الذي سينتج نفس التجميع. بمجرد الانتهاء من ذلك ، تم دمج الكود في سلسلة أدوات LLVM – وهي المرة الأولى التي يتم فيها تعديل بعض التعليمات البرمجية منذ أكثر من عقد.

نتيجة لذلك ، قدر الباحثون أن كود AlphaDev يتم تنفيذه الآن تريليونات المرات في اليوم.

الطبيعة ، 2023. DOI: 10.1038 / s41586-023-06004-9 (حول DOIs).