設計執行矩陣演算法之高速規律陣列

Abstract

在本論文中，我們藉由規律法及空時映射合成矩陣演算法之規律陣列。一 些新的觀念及設計被提出。首先，我們介紹“ 兩步規律法 ”：選擇排列 順序及廣播平面。藉由此法可以推導出數個矩陣乘法的對等規律陣列。這 些陣列包括有網狀陣列、雙層網狀陣列、圈狀陣列以及軌道陣列。我們將 進一步地利用兩步規律法，合成出更快的矩陣乘法之規律陣列。第二、我 們設計出一些新的輾轉封閉及代數路徑問題的多重象限平行演算法。這些 新的演算法將可藉由所提出的多重象限排序，映射出有較短執行時間的規 律陣列。同時，經由陣列堆疊可以合成出有較少處理單元的規律陣列，且 經由陣列線性可以設計出一些一維的規律陣列。第三、我們研究時空映射 法（ 反向的空時映射法 ）及其廣泛之應用。利用時空映射法，我們可以 排除複雜的重新定位處理、可以藉由對等轉換使規律陣列重新架構、並且 可以轉換一非韻律的律規律演算法成一對等之韻律的規律演算法。此外， 我們亦提出一個較時空映射法更為廣泛的方法“ 空間擴展法 ”，此法可 以加大規律陣列設計的空間 。第四、我們提出新的技術解決最佳空間設 計的問題。其中有三個新的非線性處理機分配方法被提出，每一方法都是 利用同一分割技術但配合著不同的非線性處理機分配程序，以解決不同狀 況的問題。最後，我們研究可沿伸模組線性陣列以及低維規律陣列的設計 。一個多項式時間的設計法被提出。其設計出之線性陣列及低維陣列的陣 列大小及執行時間，有著近似最佳的結果。此設計法的複雜度與問題大小 無關，只和所給的演算法維數有關。 This dissertation addresses design of regular arrays for matrix algorithms by regularization and spacetime mapping techniques. First, we propose the method of two step regularization -- the selection of permutation sequences and broadcast planes. We can derive several equivalent regular arrays (including mesh arrays ,two-layered mesh arrays, cylindrical arrays, and torus arrays) for matrix multiplication. Several faster regular arrays are synthesized by the two step regularization. Second, we design some new multi-phase regular algorithms for transitive closure and algebraic path problem. Using the multi-phase linear schedules, these algorithms can be mapped to regular arrays with less execution time. Meanwhile, by array piling we can synthesize regular arrays with fewer processing elements and by array linearization we can design 1-D regular arrays for these problems. Third,with timespace mapping, the complex process of reindexing can be bypassed, regular arrays can be restructured by equivalent transformations, and a nonsystolic regular algorithm can be transformed to an equivalent systolic one. Furthermore, the concept of dimension extension, a generalized method of the timespace mapping, is proposed with which we can enlarge the design space of regular arrays. Fourth, we present new technique to solve the problem of space-optimal design. Three novel nonlinear processor allocation methods, each of which works by combining a partitioning technique (gcd- partition) with different nonlinear processor allocation procedures, are proposed. Finally, we study the method of designing modular extensible linear arrays and lower dimensional regular arrays. A polynomial time method is proposed and the designed linear and lower dimensional arrays are asymptotically optimal in space and time. The time complexity of the method is independent on the problem size and dependent only on the number of dimensions of the given regular algorithm.