خوارزمية تشايتين

الموسوعة الحرة

خوارزمية تشايتين هي خوارزمية لتخصيص السجلات تعتمد على تلوين الرسم البياني من الأسفل إلى الأعلى، وتستخدم التكلفة/الدرجة كمقياس للتجاوز . سُميت الخوارزمية نسبةً إلى مصممها، غريغوري تشايتين . وكانت خوارزمية تشايتين أول خوارزمية لتخصيص السجلات تستخدم تلوين الرسم البياني للتداخل في كلٍ من تخصيص السجلات والتجاوز.

عُرضت خوارزمية تشايتين في ندوة SIGPLAN لعام 1982 حول بناء المترجمات، ونُشرت في وقائع الندوة. [ 1 ] وكانت امتدادًا لورقة بحثية سابقة نُشرت عام 1981 حول استخدام تلوين الرسوم البيانية لتخصيص السجلات. [ 2 ] وشكّلت خوارزمية تشايتين أساسًا لجزء كبير من الأبحاث المتعلقة بمخصصات السجلات. [ 3 ] [ 4 ]

مراجع

  1. ↑ تشايتين، جي جي (يونيو 1982). "تخصيص السجلات وتفريغها عبر تلوين الرسم البياني" . إشعارات ACM SIGPLAN . 17 (6): 98-101 . doi : 10.1145/872726.806984 .
  2. ↑ تشايتين، جي جي؛ أوسلاندر، إم إيه؛ تشاندرا، إيه كيه؛ كوك، جيه؛ هوبكنز، إم إي؛ ماركستين، بي دبليو (يناير 1981). "تخصيص السجلات عبر التلوين" (ملف PDF) . لغات الحاسوب . 6 : 45-57 . doi : 10.1016/0096-0551(81)90048-5 .
  3. ↑ بريغز، بريستون؛ كوبر، كيث د.؛ توركزون، ليندا (مايو 1994). "تحسينات على تخصيص سجلات تلوين الرسوم البيانية" . معاملات ACM في لغات البرمجة والأنظمة . 16 (3): 428-455 . doi : 10.1145/177492.177575 .
  4. ↑ كوبر، ك.د.؛ داسغوبتا، أ.؛ إيكهارت، ج. (2005). "إعادة النظر في تخصيص سجلات تلوين الرسوم البيانية: دراسة لخوارزميتي تشايتين-بريجز وكالاهان-كوبلنز" (ملف PDF) . ورشة العمل الدولية حول اللغات والمترجمات للحوسبة المتوازية . سلسلة محاضرات في علوم الحاسوب. المجلد 4339. سبرينغر. الصفحات 1-16 . doi : 10.1007/978-3-540-69330-7_1 . ISBN   978-3-540-69330-7.
  • غريغوري تشايتين (أبريل 2004). "تخصيص السجلات وتفريغها عبر تلوين الرسم البياني". إشعارات ACM SIGPLAN . 39 (4): 66-74 . doi : 10.1145/989393.989403 . S2CID 23108905 .