الگوی دسترسی به حافظه

در رایانش، الگوی دسترسی به حافظه یا الگوی دسترسی ورودی/خروجی (IO) به روشی اشاره دارد که یک سیستم یا برنامه داده‌ها را در حافظه یا فضای ذخیره‌سازی ثانویه می‌خواند یا می‌نویسد. این الگوها از نظر میزان محلیّت ارجاع با یکدیگر تفاوت دارند و به‌طور چشمگیری بر کارایی کش تأثیر می‌گذارند. همچنین بر نحوهٔ به‌کارگیری موازی‌سازی و توزیع بار کاری در سیستم‌های حافظهٔ اشتراکی نیز اثر دارند. علاوه بر این، مسائل مربوط به همگام‌سازی کش (cache coherency) می‌توانند کارایی چندپردازنده‌ها را کاهش دهند، که به این معنی است که برخی الگوهای دسترسی به حافظه سقفی برای میزان موازی‌سازی ایجاد می‌کنند (سقفی که رویکردهای چند‌هسته‌ای گسترده تلاش می‌کنند آن را از میان بردارند).

حافظهٔ رایانه معمولاً «تصادفی‌دسترسی» توصیف می‌شود، اما روش‌هایی که نرم‌افزار حافظه را پیمایش می‌کند همچنان الگوهایی از خود نشان می‌دهد که می‌توان برای افزایش کارایی از آن‌ها بهره برد. ابزارهای مختلفی برای کمک به طراحان سیستم و برنامه‌نویسان در درک، تحلیل و بهبود الگوهای دسترسی به حافظه وجود دارد، از جمله VTune و Vectorization Advisor، و همچنین ابزارهایی برای رسیدگی به الگوهای دسترسی حافظه در GPUها.

الگوهای دسترسی به حافظه پیامدهایی در حوزهٔ امنیت نیز دارند؛ به همین دلیل، برخی تلاش می‌کنند فعالیت برنامه را برای حفظ حریم خصوصی پنهان یا مبهم کنند.

## نمونه‌ها

برخی منابع الگوهای «دنباله‌ای» و «خطی» را به‌اشتباه در برابر هم قرار می‌دهند؛ در حالی که بارهای پردازشی دنیای واقعی تقریباً الگوهای بی‌شماری دارند.

### دنباله‌ای

ساده‌ترین حالت افراطی، الگوی دسترسی دنباله‌ای است؛ جایی که داده با آدرس‌دهی افزایشی یا کاهشی ساده خوانده، پردازش و نوشته می‌شود. این نوع الگوها بسیار برای پیش‌واکشی مناسب‌اند.

### گام‌دار
الگوهای گام‌دار یا الگوهای دسترسی دو‌بعدی و سه‌بعدی ساده (مثلاً پیمایش آرایه‌های چندبعدی) به‌طور مشابه قابل پیش‌بینی هستند و در پیاده‌سازی الگوریتم‌های جبر خطی و پردازش تصویر دیده می‌شوند. تکنیک «بلاک‌بندی حلقه‌ها» (loop tiling) یک روش مؤثر است. برخی سیستم‌ها با استفاده از DMA یک حالت گام‌دار برای انتقال داده بین زیر‌بلوک‌های آرایه‌های دو‌بعدی بزرگ و حافظهٔ Scratchpad ارائه کرده‌اند.

### خطی
یک الگوی دسترسی خطی نزدیک به الگوی «گام‌دار» است، جایی که آدرس حافظه از یک ترکیب خطیِ شاخص‌ها محاسبه می‌شود. پیمایش شاخص‌ها به‌صورت دنباله‌ای، الگوی گام‌دار را تولید می‌کند. یک الگوی دسترسی خطی برای نوشتن (با هر نوع الگوی غیرهم‌پوشان برای خواندن) می‌تواند تضمین کند که یک الگوریتم قابل موازی‌سازی است، و این موضوع در سیستم‌هایی که از هسته‌های محاسباتی پشتیبانی می‌کنند مورد بهره‌برداری قرار می‌گیرد.

### نزدیک‌ترین همسایه
الگوهای دسترسی حافظهٔ نزدیک‌ترین همسایه در شبیه‌سازی‌ها ظاهر می‌شوند و به الگوهای دنباله‌ای یا گام‌دار مرتبط‌اند. یک الگوریتم ممکن است یک ساختار داده را با استفاده از اطلاعات نزدیک‌ترین همسایه‌ها (در یک یا چند بعد) پیمایش کند. این الگوها در شبیه‌سازی‌های فیزیکی مبتنی بر شبکه رایج‌اند. 
عبارت «نزدیک‌ترین همسایه» همچنین می‌تواند به ارتباطات میان گره‌ها در یک خوشه اشاره داشته باشد؛ شبیه‌سازی‌هایی که بر چنین دسترسی‌های محلی تکیه دارند را می‌توان با تقسیم داده‌ها میان گره‌ها موازی‌سازی کرد، به‌گونه‌ای که تنها ارتباطات نزدیک‌ترین همسایه بین گره‌ها لازم باشد. این حالت با توپولوژی شبکهٔ توری (torus) تطابق خوبی دارد.

### دو‌بعدی با انسجام فضایی
در رندرینگ سه‌بعدی، الگوهای دسترسی برای نگاشت بافت و رستره‌سازی اجزای کوچک (با اعوجاج‌های پیچیدهٔ سطوح) خطی نیستند، اما همچنان می‌توانند محلیّت فضایی نمایش دهند (مثلاً در فضای صفحه یا فضای بافت). این محلیّت فضایی را می‌توان با ترکیبی از ترتیب مورتون و بلاک‌بندی (tiling) برای بافت‌ها و بافر فریم به محلیّت مناسب حافظه تبدیل کرد. همچنین مرتب‌سازی اجزا در رندرینگ مبتنی بر کاشی (tile-based deferred rendering) می‌تواند سودمند باشد.  
ذخیره‌سازی ماتریس‌ها در ترتیب مورتون در برخی کتابخانه‌های جبر خطی نیز مزیت دارد.

### پاششی
یک الگوی دسترسی پاششی ترکیبی از خواندن دنباله‌ای و نوشتن ایندکسی/تصادفی است.در مقایسه با gather، این الگو ممکن است بار کمتری روی سلسله‌مراتب کش وارد کند، زیرا عنصر پردازشی می‌تواند نوشتن‌ها را به‌صورت «بفرست و فراموش کن» انجام دهد (و حتی کش را دور بزند)، درحالی‌که دادهٔ منبع به‌صورت پیش‌بینی‌پذیر با پیش‌واکشی یا DMA خوانده می‌شود.

با این حال، موازی‌سازی آن دشوارتر است زیرا تضمینی وجود ندارد که نوشتن‌ها با یکدیگر تداخل نکنند.بسیاری از سیستم‌ها همچنان فرض می‌کنند سخت‌افزار کش چندین نوشتن کوچک را به نوشتن‌های بزرگ‌تر ادغام خواهد کرد.

در گذشته، نگاشت بافت رو‌به‌جلو تلاش می‌کرد تصادفی‌بودن نوشتن‌ها را مدیریت کند، درحالی‌که دادهٔ منبع به‌صورت دنباله‌ای خوانده می‌شد.

کنسول PlayStation 2 از نگاشت بافت معکوس استفاده کرد، اما فرایند‌های scatter/gather را به‌صورت «روی‌تراشه» با EDRAM انجام می‌داد، در حالی که مدل سه‌بعدی و بخش زیادی از دادهٔ بافت از حافظهٔ اصلی به‌صورت دنباله‌ای با DMA تغذیه می‌شد. به همین دلیل این کنسول از primitiveهای ایندکسی پشتیبانی نمی‌کرد و گاهی لازم بود بافت‌ها از قبل مدیریت شوند.

### گردآوری
در الگوی gather، خواندن‌ها به‌صورت ایندکسی یا تصادفی انجام می‌شود، درحالی‌که نوشتن‌ها دنباله‌ای یا خطی هستند.نمونه‌ای از آن در نگاشت بافت معکوس دیده می‌شود، جایی که داده‌ها به‌صورت خطی در خطوط اسکن نوشته می‌شوند، درحالی‌که آدرس‌های بافت برای هر پیکسل محاسبه می‌گردند.

در مقایسه با scatter، عیب gather این است که کش (و پنهان‌سازی تأخیر) برای خواندن کارآمد عناصر کوچک ضروری است؛ با این حال موازی‌سازی آسان‌تر است زیرا نوشتن‌ها هم‌پوشانی ندارند. به همین دلیل روش gather در برنامه‌نویسی GPGPU رایج‌تر است،[27] چراکه حجم بالای threading برای مخفی‌کردن تأخیر خواندن‌ها استفاده می‌شود.

### ترکیبیِ gather و scatter
یک الگوریتم ممکن است داده را از یک منبع gather کند، روی حافظهٔ محلی یا روی‌تراشه پردازش انجام دهد و نتایج را scatter کند. این اساس عملکرد کل خط لولهٔ GPU هنگام رندر سه‌بعدی است: gather کردن رئوس ایندکسی و بافت‌ها، و scatter کردن پیکسل‌های سایه‌خورده در فضای تصویر. رستره‌سازی اجسام مات با استفاده از بافر عمق «جابجاپذیر» است، که امکان مرتب‌سازی و اجرای موازی را فراهم می‌کند. در حالت کلی، نیاز به سازوکارهای همگام‌سازی وجود دارد.

### تصادفی
در انتهای دیگر طیف، الگوی دسترسی حافظهٔ کاملاً تصادفی قرار دارد. تعداد کمی از سیستم‌های چندپردازنده برای رسیدگی به این موارد تخصصی شده‌اند.رویکرد PGAS می‌تواند با مرتب‌سازی عملیات براساس داده در لحظه کمک‌ کند (زمانی که مسئله یافتن محلیّت داده‌های نامرتب است).  
ساختارهای داده که متکی بر اشاره‌گرها هستند معمولاً محلیّت ضعیفی دارند، هرچند مرتب‌سازی داده می‌تواند در برخی موارد کمک کند.  
برای یک الگوی واقعاً تصادفی، ممکن است بتوان آن را به بخش‌هایی (شامل scatter یا gather یا مرتب‌سازی میانی) تجزیه کرد تا محلیّت کلی بهبود یابد؛ این کار اغلب پیش‌نیاز موازی‌سازی است.

## رویکردها
### طراحی مبتنی بر داده
طراحی مبتنی بر داده رویکردی است که با سازمان‌دهی داده‌ها بر اساس نحوهٔ پیمایش آن‌ها در مراحل مختلف یک برنامه، قصد دارد محلیّت ارجاع را به حداکثر برساند. این رویکرد در تضاد با روش رایج برنامه‌نویسی شی‌گرا قرار دارد؛ در آن روش، داده‌ها معمولاً به‌گونه‌ای سازمان‌دهی می‌شوند که چیدمان آن‌ها مستقیماً بازتاب الگوی دسترسی باشد.

## مقایسه با محلیّت ارجاع
محلیّت ارجاع به ویژگی‌ای اشاره دارد که در الگوهای دسترسی به حافظه مشاهده می‌شود. یک برنامه‌نویس ممکن است برای بهبود محلیّت ارجاع و یا افزایش قابلیت موازی‌سازی با تغییر الگوریتم‌ها، الگوی دسترسی به حافظه را اصلاح کند. یک برنامه‌نویس یا طراح سیستم همچنین ممکن است چارچوب‌ها یا انتزاع‌هایی (مانند الگوهای C++ یا توابع مرتبهٔ بالا) ایجاد کند که یک الگوی دسترسی به حافظهٔ مشخص را در خود محصور کنند.

ملاحظات متفاوتی برای الگوهای دسترسی به حافظه در زمینهٔ موازی‌سازی وجود دارد که فراتر از محلیّت ارجاع هستند؛ ازجمله تفکیک عملیات خواندن و نوشتن. برای نمونه: حتی اگر خواندن و نوشتن از نظر محلیّت «کاملاً» مناسب باشند، ممکن است به‌دلیل وجود وابستگی‌ها امکان موازی‌سازی وجود نداشته باشد. جداکردن ناحیه‌های خواندن و نوشتن الگوی دسترسی متفاوتی ایجاد می‌کند که شاید در نگاه اول از نظر محلیّت ضعیف‌تر به‌نظر برسد، اما برای بهره‌گیری از سخت‌افزارهای موازی مدرن مطلوب است.

محلیّت ارجاع ممکن است به متغیرهای منفرد نیز اشاره داشته باشد (برای مثال توانایی کامپایلر در نگه‌داشتن آن‌ها داخل ثبات‌ها)، در حالی که اصطلاح «الگوی دسترسی به حافظه» تنها به داده‌های نگه‌داری‌شده در یک حافظهٔ قابل اندیس‌دهی (به‌ویژه حافظهٔ اصلی) اشاره دارد.

## منابع

رده:بهینه‌سازی نرم‌افزار