Automatic Parallelization: New Approaches to Code Generation, Data Distribution, and Performance prediction

سیستم‌های چند پردازشی با حافظه توزیع‌شده (DMS)، مانند هایپرمکعب‌های اینتل، Paragon، CM-5 ماشین فکری، و سطح محاسباتی Meiko، به سرعت مورد قبول کاربران قرار گرفته‌اند و وعده ارائه قدرت محاسباتی مورد نیاز برای حل این چالش بزرگ را می‌دهند. مشکلات علم و مهندسی ساخت این ماشین ها نسبتاً ارزان است و به طور بالقوه برای تعداد زیادی پردازنده مقیاس پذیر هستند. با این حال، برنامه‌نویسی آنها دشوار است: عدم یکنواختی حافظه که دسترسی‌های محلی را بسیار سریع‌تر از انتقال داده‌های غیرمحلی از طریق عملیات ارسال پیام می‌کند، دلالت بر این دارد که موقعیت الگوریتم‌ها باید برای دستیابی به عملکرد قابل قبول مورد سوء استفاده قرار گیرد. مدیریت داده ها، با اهداف دوگانه گسترش حجم کار محاسباتی و به حداقل رساندن تأخیرهای ناشی از زمانی که یک پردازنده باید منتظر داده های غیر محلی باشد، از اهمیت بالایی برخوردار می شود. هنگامی که یک کد با دست موازی می شود، برنامه نویس باید کار و داده های برنامه را بین پردازنده هایی که آن را اجرا می کنند توزیع کند. یکی از رویکردهای رایج برای انجام این کار، استفاده از منظم بودن اکثر محاسبات عددی است. این به اصطلاح داده های چندگانه یک برنامه (SPMD) یا مدل محاسبات موازی داده است. با استفاده از این روش، آرایه‌های داده در برنامه اصلی هر کدام بین پردازنده‌ها توزیع می‌شوند و یک رابطه مالکیت ایجاد می‌کنند و محاسباتی که یک آیتم داده را تعریف می‌کنند توسط پردازنده‌های صاحب داده انجام می‌شود.

Distributed-memory multiprocessing systems (DMS), such as Intel's hypercubes, the Paragon, Thinking Machine's CM-5, and the Meiko Computing Surface, have rapidly gained user acceptance and promise to deliver the computing power required to solve the grand challenge problems of Science and Engineering. These machines are relatively inexpensive to build, and are potentially scalable to large numbers of processors. However, they are difficult to program: the non-uniformity of the memory which makes local accesses much faster than the transfer of non-local data via message-passing operations implies that the locality of algorithms must be exploited in order to achieve acceptable performance. The management of data, with the twin goals of both spreading the computational workload and minimizing the delays caused when a processor has to wait for non-local data, becomes of paramount importance. When a code is parallelized by hand, the programmer must distribute the program's work and data to the processors which will execute it. One of the common approaches to do so makes use of the regularity of most numerical computations. This is the so-called Single Program Multiple Data (SPMD) or data parallel model of computation. With this method, the data arrays in the original program are each distributed to the processors, establishing an ownership relation, and computations defining a data item are performed by the processors owning the data.