均勻遞推方程式的時間排程問題之研究

Abstract

在這篇論文中, 我們針對均勻遞推方程式, 研究了一系列以超平面為 基礎的時間排程方法, 包括了線性排程、均勻線類排程、線類排程、多維 排程。結合線類排程及多維排程的觀念, 本文將推導出多維線類排程的線 性規劃, 希望能夠改善多維排程的執行時間。這些排程方法皆以線性規劃 的方式求其最佳排程向量。研究各種排程方法在平行計算上是一個相當重 要的課題, 因為這些排程觀念在設計處理陣列或平行編譯器上扮演這很重 要之角色。另外本文也將這些排程方法應用到許多實際的例子上, 包括了 數列相纏、選項排序法、二維濾波器及一個複雜的均勻遞推方程式系統, 由這些例子之說明, 可以看出各種排程方法在執行時間上的優劣與一些應 用上的限制, 而這些實際的應用也更加證明了時間排程問題在平行演算法 上的價值與重要地位。 In this thesis, we study a series of hyperplane-based time scheduling methods for uniform recurrence equations. The studied schedules are linear schedule, uniform affine schedule, affine schedule, and multi-dimensional schedule.In addition, a schedule named as multi-dimensional affine schedule is studied.It improves the execution time of the multi-dimensional schedule. All these scheduling problems are formulated as linear programs. Time scheduling problem is a very important problem on parallel cmputing field. It plays an important role in the designs of parallel processor array and parallel compilers. Besides, for illustration, these scheduling methods are implemented for some real examples, including convolution, selection sort, 2D filter and a complex example of uniform recurrence equations. From these illustrative examples, the quality of various time scheduling methods can be explored. Moreover, the importance of the time scheduling problem in parallel algorithms can be seen.