موضوع مقاله: مرتب سازی حافظه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب سازی حافظه | مقدمه: همچنین می‌تواند به ترتیب حافظه تولید شده توسط کامپایلر در زمان کامپایل یا ترتیب حافظه تولید شده توسط پردازنده در زمان اجرای برنامه، اشاره کند. | ## بخش 1: مرتب سازی حافظه | در ریزپردازنده‌های مدرن، ترتیب حافظه توانایی‌های پردازنده را برای مرتب کردن مجدد دستورهای حافظه، دسته‌بندی می‌کند. مرتب کردن مجدد می‌تواند برای بکارگیری کامل از پهنای باند گذرگاه در حافظه‌های مختلف مانند حافظه نهان و بانک حافظه، استفاده شود. در اکثر تک پردازنده‌های مدن، دستورهای حافظه به ترتیبی که کد برنامه تعیین می‌کند، اجرا نمی‌شود. در برنامه‌های تک رشته‌ای، تمام اجراهای خارج از ترتیب، از دید برنامه‌نویس پنهان می‌شوند. در نتیجه این‌طور به نظر می‌آید که همهٔ دستورهایی که در ترتیب تعیین شدند، اجرا شده‌اند. مرتب سازی حافظه در زمان کامپایل اکثر زبان‌های برنامه‌نویسی ایده ای از یک رشته اجرا دارند که دستورها را به ترتیب تعریف‌شده اجرا می‌کند. کامپایلرهای سنتی دستورهای سطح بالا را به دنباله ای از دستورالعمل‌ها ترجمه می‌کنند که این دستورالعمل‌ها در سطح ماشینی زیرین به شمارنده برنامه مرتبط هستند. تأثیر اجرایی در دو مرحله قابل رویت است: در کد برنامه در سطح بالا و در سطح ماشین (مانند زمانی که در برنامه‌نویسی همزمان توسط رشته‌ها یا عناصر پردازشی دیده می‌شود). در زمان اشکال زدایی (یک سخت‌افزار اشکال زدایی با دسترسی به وضعیت‌های ماشین این کار را انجام می‌دهد). مسائل کلی دستور برنامه تأثیر نظم برنامهٔ ارزیابی عبارت در طول زمان کامپایل، دستورالعمل‌های سخت‌افزاری معمولاً دقیق تر از آنچه که در کد سطح بالا مشخص شده‌است، تولید می‌شوند. اولین تأثیر قابل مشاهده در برنامه‌نویسی رویه ای، تخصیص یک مقدار جدید به یک متغیر نامگذاری شده‌است. وقتی که print به مقدار محاسبه شده متغیر sum ارجاع می‌دهد، نتیجه آن تأثیر قابل مشاهده دنباله اجرا شده قبلی است. در سطح ماشین، تعداد کمی از ماشین‌ها می‌توانند دستورهای جمع را برای سه عدد به‌طور همزمان و در یک دستورالعمل واحد انجام دهند؛ پس کامپایلر باید این عبارت را به دو دستور متفاوت ترجمه کند. اگر مفاهیم زبان برنامه، کامپایلر را محدود به ترجمه (برای مثال) چپ-به-راست کند، کدی که تولید می‌شود مانند این است که برنامه‌نویس دستورهای زیر را در برنامه اصلی نوشته باشد: ;sum = a + b ; sum = sum + c اگر کامپایلر اجازه استفاده از خاصیت شرکت پذیری جمع را داشته باشد، کد زیر تولید می‌شود: ;sum = b + c ;sum = a + sum اگر کامپایلر مجاز به استفاده از خاصیت جابه‌جایی جمع باشد، ممکن است کد زیر تولید شود : ;sum = a + c ;sum = sum + b باید توجه داشت که در اکثر زبان‌های برنامه‌نویسی، داده عدد صحیح فقط از جبر برای اعداد صحیح ریاضی در غیاب سرریز عدد صحیح استفاده می‌کند. همچنین در اغلب زبان‌های برنامه‌نویسی، محاسبه ممیز شناور در داده‌های اعشاری قابل جایگزینی با گرد کرد عدد نیست. اگر برنامه‌نویس نگران سرریز عدد صحیح یا تأثیر گرد کرد در اعداد اعشاری باشد، ممکن است برنامه مشابه در سطح بالا به صورت زیر باشد: ;sum = a + b ;sum = sum + c تأثیر ترتیب برنامه شامل فراخوانی تابع تعداد زیادی از زبان‌ها، مرز دستور را بعنوان نقطه دنباله تلقی می‌کنند و اجبار می‌کنند که اثر یک دستور قبل از اجرای دستور بعد کامل شوند. این مورد کامپایلر را مجبور می‌کند که کدی مطابق با ترتیب بیان شده تولید کند که در اغلب موارد شامل دستورهای پیچیده ایست و ممکن است شامل فراخوانی تابع درونی باشد. ;sum = f(a) + g(b) + h(c) در سطح ماشین، فراخوانی یک تابع معمولاً مستلزم تنظیم یک قاب پشته ای برای فراخوانی تابع است که شامل خواندن و نوشتن بسیاری در حافظه ماشین است. در اکثر زبان‌های کامپایل شده، کامپایلر آزاد است تا تابع f, g و h را به دلخواه خود ترتیب دهد و در نتیجه برنامه را دوباره مرتب کند. در یک زبان کاملاً کاربردی، تاثیر گذاشتن بر روی وضعیت برنامه قابل مشاهده توسط فراخوانی تابع ممنوع است (غیر از مقدار بازگشتی)، و تفاوت در ترتیب حافظه ماشین به دلیل ترتیب فراخوانی تابع برای معناشناسی برنامه بی‌اهمیت خواهد بود. در زبان‌های رویه‌ای، توابعی که نامیده می‌شوند می‌توانند اثر جانبی داشته باشند، مانند انجام دستورهای ورودی/خروجی یا به‌روزرسانی متغیرها در محدوده جهانی برنامه، که همگی اثر قابل مشاهده بر روی مدل برنامه دارند. برنامه نویسانی که به چنین جلوه‌هایی اهمیت می‌دهند می‌توانند برنامه منبع اصلی را با دقت بیشتری بیان کنند. مسائل خاص نظم حافظه جلوه‌های ترتیب برنامه شامل دستورهای اشاره گر حال موردی را در نظر بگیرید که در آن همان عمل جمع با اشاره گر غیرمستقیم بیان شود، مثلاً در زبان‌هایی مثل C/C++: ;sum = *a + *b + *c عبارت x* یک اشاره‌گر نامیده می‌شود و مکانی از حافظه را که با مقدار فعلی x مشخص شده‌است، می‌خواند. | ## بخش 2: مرتب سازی حافظه | هنگام خواندن از حافظه استاندارد برنامه، به دلیل ترتیب دستور خواندن حافظه، عوارض جانبی وجود ندارد. در برنامه‌نویسی سیستم‌های جاسازی شده، بسیار رایج است که I/O با نقشه حافظه داشته باشیم که در آن دستورهای I/O باعث خواندن و نوشتن در حافظه یا تغییر در حالت عملکرد پردازنده، که عوارض جانبی بسیار قابل مشاهده است، می‌شود. برای مثال بالا، فرض کنید که نشانگرها به حافظه برنامه منظم بدون این عوارض جانبی اشاره می‌کنند. کامپایلر آزاد است که این خوانش‌ها را به نحوی که مناسب می‌داند، مرتب کند و هیچ عوارض جانبی قابل‌مشاهده برنامه وجود نخواهد داشت. ;sum = *a + *b + *c* در این قسمت، اینکه زبان به کامپایلر اجازه تقسیم را به صورت زیر بدهد، بعید به نظر می‌رسد. // همان‌طور که توسط کامپایلر بازنویسی شده‌است // به‌طور کلی ممنوع است ;sum = *a + *b* ;sum = *sum + *c* این در اکثر موارد ناکارآمد است و نوشتن اشاره گر می‌تواند اثر جانبی بر روی وضعیت قابل مشاهده ماشین داشته باشد. کامپایلر اجازه این تبدیل تقسیم را نمی‌دهد، بنابراین تنها نوشته‌ها در مکان حافظه sum باید به‌طور منطقی از سه اشاره گر خوانده شده از عبارت پیروی کنند. اما فرض کنید برنامه‌نویس نگران سرریز اعداد صحیح بوده و این عبارت را در سطح برنامه به صورت زیر تقسیم کند: // به‌طور مستقیم توسط برنامه‌نویس نوشته شده‌است // با نگرانی‌های دیگر ;sum = *a + *b* ;sum = *sum + *c* عبارت اول دو خوانش حافظه را کد می‌کند، که باید قبل از اولین نامه به sum* باشد (به هر ترتیب). عبارت دوم دو خوانش حافظه (به هر ترتیب) را کد می‌کند که باید قبل از به روز رسانی دوم sum* باشد. این امر ترتیب دو دستور اضافه را تضمین می‌کند، اما به‌طور بالقوه یک مشکل جدید برای نام مستعار آدرس را معرفی می‌کند: هر کدام از این نکته‌ها می‌توانند به‌طور بالقوه به مکان حافظه مشابه مراجعه کنند. برای مثال، فرض کنید در این مثال c* و sum* نام مستعار در یک مکان حافظه دارند و هر دو نسخه برنامه را با sum* برای هر دو بازنویسی کنیم. مقدار اصلی چیزی که ما در ابتدا به عنوان c* نوشتیم در تخصیص به sum* و همچنین مقدار اصلی sum*از بین می‌رود، اما این در وهله اول بازنویسی شده بود و هیچ نگرانی خاصی ندارد. به دلیل اثرهای احتمالی، تغییر یافتن مجدد دستورهای اشاره‌گر بدون به خطر انداختن اثرهای برنامه قابل‌مشاهده دشوار است. در حالت معمول، ممکن است هیچ نام مستعاری وجود نداشته باشد، بنابراین به نظر می‌رسد که کد مانند قبل اجرا شود. حتی اگر این موارد به‌طور کامل در اجرای عادی وجود نداشته باشند، دری را برای یک دشمن مخرب باز می‌کند تا در جایی که نام مستعار وجود دارد، ورودی ایجاد کند، که منجر به یک سوء استفاده امنیتی از رایانه می‌شود. ترتیب مجدد امن برنامه قبلی به شرح زیر است: // یک متغیر محلی موقت 'temp' از نوع مناسب را اعلام کنید ;temp = *a + *b ;sum = temp + *c* در نهایت حالت غیر مستقیم با فراخوانی تابع اضافه را در نظر بگیرید : ;sum = f(*a) + g(*b)* کامپایلر ممکن است ارزیابی اشاره گرهای a* و b* را زودتر انتخاب کند، ممکن است ارزیابی b* را به بعد از فراخوانی تابع f یا ارزیابی a* را به بعد از فراخوانی تابع g به تعویق بیندازد. اگر تابع f و g اثر جانبی قابل مشاهده نداشته باشند، هر سه گزینه برنامه‌ای با اثر قابل‌مشاهده مشابه تولید خواهند کرد. اگر پیاده سازی f یا g دارای اثر جانبی هر اشاره‌گر باشد، این سه گزینه می‌توانند جلوه‌های برنامه قابل مشاهده مختلفی را ایجاد کنند. ترتیب حافظه در مشخصات زبان به‌طور کلی، زبان‌های کامپایل شده به اندازه کافی دقیق نیستند تا کامپایلر به‌طور رسمی در زمان کامپایل مشخص کند که کدام اشاره گرها نام مستعار دارند و کدام‌ها ندارند. امن‌ترین کار این است که کامپایلر فرض کند که همه اشاره گرها همیشه نام مستعار دارند. در نتیجه، بسیاری از زبان‌های کامپایل‌شده سطح بالا، مانند C و ++C، طوری تکامل یافته‌اند تا مشخصات معنایی پیچیده تری داشته باشند در این مورد که کامپایلر در کجا مجاز است در مرتب‌سازی مجدد کدها برای دستیابی به بالاترین عملکرد ممکن، مفروضات خوش‌بینانه داشته باشد، و در کجا باید برای جلوگیری از خطر معنایی، مفروضات بدبینانه ای را ایجاد کند. تا حد زیادی بزرگ‌ترین دسته‌بندی از عوارض جانبی در یک زبان رویه ای شامل دستورهای نوشتن حافظه است، بنابراین قوانین مربوط به ترتیب حافظه جزء غالب در تعریف معنایی ترتیب برنامه هستند. مرتب سازی مجدد فراخوانی‌های توابع بالا، ممکن است به نظر متفاوت باشند، اما این معمولاً به نگرانی‌هایی تبدیل می‌شود که در مورد اثر حافظه داخلی در تعامل با دستور حافظه است. | ## بخش 3: مرتب سازی حافظه | مشکلات و عوارض اضافی بهینه سازی تحت عنوانas-if کامپایلرهای مدرن بعضی وقت‌ها با استفاده از یک قاعده as-if یک گام جلوتر می‌روند، که در آن هرگونه ترتیب مجدد (حتی در بین عبارت‌ها) در صورتی که تأثیری بر نتایج معناشناسی برنامه نداشته باشد، مجاز است. بر اساس این قانون، ترتیب دستورها در کد ترجمه شده می‌تواند به شدت از ترتیب برنامه مشخص شده متفاوت باشد. اگر کامپایلر مجاز باشد در مورد دستورهای اشاره گر متمایز با عدم همپوشانی مستعار در موردی که چنین نام مستعاری وجود داشته باشد، مفروضات خوش‌بینانه داشته باشد (این امر معمولاً به عنوان یک برنامه نامناسب طبقه‌بندی می‌شود که رفتار نامشخصی از خود نشان می‌دهد)، نتایج نامطلوب یک تبدیل کد - بهینه‌سازی تهاجمی قبل از اجرای کد یا بازرسی مستقیم کد غیرممکن است. این مسئولیت برنامه‌نویس است که مشخصات زبان را به گونه ای در نظر بگیرد تا از نوشتن برنامه‌هایی که در آن معنا در نتیجهٔ هر گونه بهینه سازی کامپایلر تغییر می‌کند، جلوگیری کند. Fortran به‌طور سنتی بار زیادی را بر دوش برنامه نویسان قرار می‌دهد تا از این مسائل آگاه باشد چرا که زبان های برنامه‌نویسی C و C++ چندان از این موارد عقب نیستند. برخی از زبان‌های سطح بالا، ساختارهای اشاره گر را به‌طور کلی حذف می‌کنند چرا که این سطح هوشیاری و توجه به جزئیات بسیار بالاست و حتی در بین برنامه‌نویسان حرفه‌ای نمی‌توان آن را حفظ کرد. درک کامل از معناشناسی ترتیب حافظه به عنوان یک تخصص در میان گروهی از برنامه‌نویس‌های حرفه ای که در این زمینه بهترین هستند، در نظر گرفته می‌شود. اکثر برنامه نویسان به درک کافی از این مسائل در حوزه معمولی تخصص خود رضایت می‌دهند. در نهایت برنامه نویسانی هستند که چارچوب‌های نرم‌افزاری را برای پشتیبانی از مدل‌های محاسباتی همزمان ایجاد می کنند. نام مستعار متغیرهای محلی توجه داشته باشید که متغیرهای محلی را نمی‌توان بدون نام مستعار فرض کرد، اگر یک اشاره‌گر به چنین متغیری در اشاره کند : ;sum = f(&a) + g(a) ما نمی‌دانیم که تابع f با اشاره گر داده شده به a چه کرد. در ساده‌ترین حالت، f مقدار جدیدی برای متغیر a می‌نویسد و عبارت به ترتیب اجرا تعریف نشده‌است. f می‌تواند چنین رفتاری را با اعمال واجد شرایط ثابت در اعلان آرگومان اشاره گر پنهان کند و عبارت به درستی تعریف شود؛ بنابراین، فرهنگ C/C++ مدرن تا حدودی در مورد دادن اعلان‌های آرگومان تابع واجد شرایط ثابت در همه موارد قابل اجرا، وسواس زیادی پیدا کرده‌است. زبان‌های C و ++C به اجزای داخلی تابع f این اجازه را می‌دهند تا صفت سازگاری را به عنوان یک مصلحت خطرناک نشان دهد. اگر تابع f این کار را به گونه ای انجام دهد که بتواند عبارت بالا را از هم بشکند، در مرحله اول نباید نوع آرگومان اشاره گر را به عنوان ثابت اعلام کند. سایر زبان‌های سطح بالا به یک تضمین قوی بدون هیچ حفره حلقه ای برای نقض متمایل می‌شوند. اگر برنامه شما کتابخانه ای را که به زبان برنامه‌نویسی دیگری نوشته شده‌است پیوند دهد، همه شرط‌ها روی این زبان تضمین نمی‌شود (اگرچه این طراحی به شدت بد در نظر گرفته می‌شود). اجرای مانع حافظه در زمان کامپایل این مانع‌ها از مرتب سازی مجدد دستورها توسط کامپایلر در طول زمان کامپایل جلوگیری می‌کنند ولی مانع از مرتب سازی مجدد توسط CPU در طول زمان اجرا نمی‌شوند. بسته به معماری پردازنده که هدف است، این ساختارهای زبان به دستورالعمل‌های ویژه، به دستورالعمل‌های متعدد (به عنوان مثال مانع و بار)، یا به دستورالعمل‌های معمولی، بسته به تضمین‌های ترتیب حافظه سخت‌افزاری، ترجمه می‌شوند. چند مدل سازگاری با حافظه برای سیستم SMP وجود دارد: سازگاری متوالی (همه خواندن‌ها و همه نوشتن‌ها به ترتیب هستند) سازگاری آرام (برای برخی از انواع مرتب سازی مجدد مجاز است) بارها را می‌توان پس از بارگذاری، مجدداً مرتب کرد (برای عملکرد بهتر انسجام حافظه پنهان، مقیاس بندی بهتر) بارها را می‌توان پس از ذخیره سازی دوباره مرتب کرد. ممکن است دستورالعمل نامنسجمی برای خط لوله‌کش (حافظه نهان) وجود داشته باشد که از اجرای کدهای خودتغییر شونده بدون دستورالعمل‌های خیط و بارگذاری مجدد کش دستورالعمل‌ها جلوگیری می‌کند. اگر پردازنده بعد از این مرتب‌سازی مجدد، اشاره‌گر به برخی از داده‌ها واکشی کند، ممکن است خود داده‌ها را واکشی نکند، اما از داده‌های قدیمی که قبلاً کش کرده و هنوز باطل نشده‌اند استفاده کند. | ## جمع‌بندی | مشخصات معماری آلفا همچنین اجازه می‌دهد تا اشکال دیگر مرتب سازی مجدد بارهای وابسته، به عنوان مثال با استفاده از داده‌های گمانه زنی قبل از دانستن اشاره گر واقعی برای حذف ارجاع داده شود.