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

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

الگوهای گام‌دار یا الگوهای دسترسی دو‌بعدی و سه‌بعدی ساده (مثلاً پیمایش آرایه‌های چندبعدی) به‌طور مشابه قابل پیش‌بینی هستند و در پیاده‌سازی الگوریتم‌های جبر خطی و پردازش تصویر دیده می‌شوند. تکنیک «بلاک‌بندی حلقه‌ها» (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 کند. این اساس عملکرد کل خط لولهٔ GPU هنگام رندر سه‌بعدی است: gather کردن رئوس ایندکسی و بافت‌ها، و scatter کردن پیکسل‌های سایه‌خورده در فضای تصویر. رستره‌سازی اجسام مات با استفاده از بافر عمق «جابجاپذیر» است، که امکان مرتب‌سازی و اجرای موازی را فراهم می‌کند. در حالت کلی، نیاز به سازوکارهای همگام‌سازی وجود دارد.

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

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