موضوع فارسی :نام مستعار ثبت نام تخصیص برای برنامه خط مستقیم انپی کامل است
موضوع انگلیسی :Aliased register allocation for straight-line programs is NP-complete
تعداد صفحه :16
فرمت فایل :PDF
سال انتشار :2008
زبان مقاله : انگلیسی
ثبت نام تخصیص است NP کامل را به طور کلی، اما می تواند در زمان خطی برای خط مستقیم حل
برنامه های که در آن هر متغیر دارای حداکثر یک نقطه تعریف اگر بانک از
ثبت همگن است. در این مقاله ما به مطالعه ثبت نام مستعار که ممکن است: یک نام مستعار
ثبت نام می تواند هر دو به طور مستقل و یا در ترکیب با ثبت نام در مجاورت استفاده می شود.
چنین ثبات ها در معماری معمولا استفاده می شود مانند معماری x86، پرینتر PA-RISC پیدا شده است،
پردازنده خورشید SPARC و MIPS ممیز شناور. در سال 2004، اسمیت، رمزی و هالووی
بهترین الگوریتم برای تخصیص ثبت نام مستعار ارائه تا کنون؛ الگوریتم آنها است
در روش اکتشافی برای رنگ آمیزی از نمودار به طور کلی. بیشتر معماریهای با aliasing به ثبت نام
اجازه می دهد ثبت تنها تراز وسط قرار دارد به ترکیب شود: به عنوان مثال، ثبت نام کم آدرس باید
حتی تعداد. گسترش تا به حال این سوال را بوده است که آیا کار با
کلاس های محدود از برنامه ها می تواند پیچیدگی تخصیص ثبت نام مستعار بهبود
با محدودیت ترازی. در این مقاله ما نشان می دهد که تخصیص ثبت نام مستعار با
محدودیت هست برای برنامه خط مستقیم NP-کامل است. ما همچنین در حال حاضر اثبات
از نتیجه مرتبط با Stockmeyer: مشکل کشتی سازی NP-کامل است.