Memory Storage Patterns in Parallel Processing

این پروژه در پاییز 1980 آغاز شد. در آن زمان رابرت واگنر به من پیشنهاد کرد که بهینه‌سازی کامپایلر سازمان داده‌ها را که برای استفاده در محیط ماشین موازی یا برداری مناسب است، بررسی کنم. ما طرحی را توسعه دادیم که در آن کامپایلر با داشتن دانش از الگوهای دسترسی ماشین، تجزیه و تحلیل کلی از عملیات یک برنامه را انجام می دهد و به طور خودکار سازماندهی بهینه را برای داده ها تعیین می کند. به عنوان مثال، برای معماری‌های خاص و عملیات خاص، با ذخیره‌سازی یک ماتریس در ردیف اصلی، می‌توان به پیشرفت‌های بزرگی در عملکرد دست یافت. با این حال، عملیات بعدی ممکن است به ماتریس به ترتیب اصلی ستون نیاز داشته باشد. باید تعیین کرد که آیا بهترین راه حل در سطح جهانی برای ذخیره ماتریس به ترتیب ردیف، ترتیب ستون، یا حتی داشتن دو نسخه از آن، هر کدام به طور متفاوتی سازماندهی شده است یا خیر. ما دو الگوریتم برای این تعیین توسعه داده ایم. این تکنیک در یک محیط ماشین برداری نویدبخش است، به ویژه اگر از interleaving حافظه استفاده شود. ابررایانه‌هایی مانند Cray، CDC Cyber ​​205، IBM 3090 و همچنین سوپرمینی‌هایی مانند Convex محیط‌های ممکن برای پیاده‌سازی هستند.

This project had its beginnings in the Fall of 1980. At that time Robert Wagner suggested that I investigate compiler optimi­ zation of data organization, suitable for use in a parallel or vector machine environment. We developed a scheme in which the compiler, having knowledge of the machine's access patterns, does a global analysis of a program's operations, and automatically determines optimum organization for the data. For example, for certain architectures and certain operations, large improvements in performance can be attained by storing a matrix in row major order. However a subsequent operation may require the matrix in column major order. A determination must be made whether or not it is the best solution globally to store the matrix in row order, column order, or even have two copies of it, each organized differently. We have developed two algorithms for making this determination. The technique shows promise in a vector machine environ­ ment, particularly if memory interleaving is used. Supercomputers such as the Cray, the CDC Cyber 205, the IBM 3090, as well as superminis such as the Convex are possible environments for implementation.