A Code Mapping Scheme for Dataflow Software Pipelining

این تک نگاری از پایان نامه دکتری من که در آزمایشگاه علوم کامپیوتر MIT در تابستان 1986 تکمیل شد، تکامل یافته است. در پایان نامه خود یک طرح نگاشت کد خط لوله برای عملیات آرایه در معماری های جریان داده ایستا را پیشنهاد کردم. افزوده اصلی به این کار در فصل 12 یافت می شود که منعکس کننده نتایج تحقیقات جدید است که طی سه سال گذشته از زمان پیوستن من به دانشگاه مک گیل نتایج بر اساس اصول پایان نامه من ایجاد شده است. از زمان انتشار مقاله ما در سال 1988 در مورد مدل معماری جریان داده واکشی آرگومان در دانشگاه مک گیل [43]، اصطلاحات خط لوله نرم افزار جریان داده به طور مداوم مورد استفاده قرار گرفته است. در بخش اول این کتاب، مدل نمودار جریان داده ایستا را به عنوان یک مدل عملیاتی برای محاسبات همزمان توصیف می کنیم. ما به ملاحظات زمان بندی برای اجرای گراف برنامه در یک کامپیوتر جریان داده ایستا ایده آل نگاه می کنیم، مفهوم پوشش لوله را بررسی می کنیم و عملکرد آن را مشخص می کنیم. ما در مورد تکنیک‌های متعادل‌سازی مورد استفاده برای تبدیل گراف‌های خاص به نمودارهای جریان داده کاملاً خط لوله بحث می‌کنیم. به طور خاص، ما نشان می‌دهیم که چگونه تعادل بهینه یک نمودار جریان داده‌های غیر چرخه‌ای را می‌توان به عنوان یک مسئله برنامه‌ریزی خطی که یک راه‌حل بهینه برای آن وجود دارد، فرموله کرد. به عنوان یک نتیجه اصلی، ما نشان می‌دهیم که مشکل متعادل‌سازی بهینه نمودارهای جریان داده‌های غیر چرخه‌ای قابل کاهش به یک کلاس از مسئله برنامه‌ریزی خطی، مسئله جریان کار خالص است، که الگوریتم‌های کارآمد شناخته شده برای آن وجود دارد. این نتیجه این حدس را رد می کند که چنین مسائلی از نظر محاسباتی سخت هستند.

This monograph evolved from my Ph. D dissertation completed at the Laboratory of Computer Science, MIT, during the Summer of 1986. In my dissertation I proposed a pipelined code mapping scheme for array operations on static dataflow architectures. The main addition to this work is found in Chapter 12, reflecting new research results developed during the last three years since I joined McGill University-results based upon the principles in my dissertation. The terminology dataflow soft­ ware pipelining has been consistently used since publication of our 1988 paper on the argument-fetching dataflow architecture model at McGill University [43]. In the first part of this book we describe the static data flow graph model as an operational model for concurrent computation. We look at timing considerations for program graph execution on an ideal static dataflow computer, examine the notion of pipe lining, and characterize its performance. We discuss balancing techniques used to transform certain graphs into fully pipelined data flow graphs. In particular, we show how optimal balancing of an acyclic data flow graph can be formulated as a linear programming problem for which an optimal solution exists. As a major result, we show the optimal balancing problem of acyclic data flow graphs is reduceable to a class of linear programming problem, the net­ work flow problem, for which well-known efficient algorithms exist. This result disproves the conjecture that such problems are computationally hard.