利用拉丁方陣設計執行矩陣相乘演算法之圈狀陣列

Abstract

圈狀陣列 (orbital array) 是一種規律陣列 (regular array), 它的資 料流路徑可以規律的安排在一個環狀物或圓柱體的表面上. 圈狀陣列的執 行效率比傳統韻律陣列 (systolic array) 有顯著的改進. 在這篇論文 中, 我們提出一種一致的方法以設計圈狀陣列. 為了設計圈狀陣列, 我們 用兩個表格, 時間排序表 (timing level table) 及處理機排列表 (processor assignment table), 來表示一個平行演算法 (algorithm). 我們建構時間排序表及處理機排列表的方法是以拉丁方陣 (Latin square) (其為一種特殊的矩陣) 的某些特性為基礎.我們所提出的方法已 經可以應用到某一類型的矩陣演算上: 包括矩陣相乘, 帶狀矩陣相乘 (band matrix multiplication), 三個矩陣連乘,矩陣相量相乘, Winograd's 演算方法, 以及有時間限制的矩陣連乘 (time-constrained triple matrix multiplication). An orbital array is a regular array whose data flow paths may be arranged regularly on the surface of a torus or a cylinder. Performances of orbital arrays are significantly better than that of conventional systolic arrays. In this dissertation, a unified approach to designing orbital arrays is proposed. For the purpose of designing an orbital array, we represent the timing schedule and processor assignment for the parallel execution of an algorithm by tables, called timing level table and processor assignment table, respectively. Our approach to constructing the timing level table and the processor assignment table is based on the characteristics of a special type of matrices: Latin squares. The proposed approach has been applied to a class of matrix algorithms, including matrix multiplication, band matrix multiplication, simultaneous triple matrix multiplication, matrix-vector multiplication, Winograd's algorithm, and time-constrained triple matrix multiplication.