Abstract
在本篇論文中，我們研究了用整數線性規劃來同時解決超純量╱VLIW處理 器的指令排程及暫存器配置問題之可能性•在超純量╱VLIW處理器中，多 個指令可以在同一個指令週期中被執行以提升系統的效能•而因為超純量 處理器只能在一小群指令中找出可以同時被執行的指令且VLIW處理器必須 要知道確實的運算流程，所以編譯器就必須要擔當將指令排程以至於能儘 可能的用到多個指令在同一指令週期中執行的特性之重責大任•以前人們 所做，用在超純量╱VLIW處理器的編譯器，通常將指令排程及暫存器配置 問題分開考慮•但問題所在是愈多的指令被放在同一個指令週期中被執行 將可能需要有更多的暫存器•所以說指令排程及暫存器配置必須要同時考 慮才能夠達到最大限度的指令平行性並達到最小限度的暫存器需求量•我 們將假設我們要處理的指令其所用到之暫存器的生命週期不會超出同一基 本區塊內•我們已經成功地用整數線性規劃模製出我們要解的問題並且考 慮了兩個暫存器配置模式•在第一個模式中我們不考慮暫存器潑撒，而在 第二個模式中暫存器潑撒將列入考慮之中•雖然第二個模式比第一個要來 得一般化，但是解整數線性規劃的數學式子的時間卻要比第一個模式要大 得多了•因此第一個模式因它較簡單且求解的時間較少而比較受到青睞• 只是在用第一個模式時必須要先確定有足夠的暫存器可用才可以•除了考 慮有沒有暫存器潑撒外，我們還將問題做了兩種最佳化：（１）給定可用 暫存器的數目，求出這段指令最少將花多少指令週期數，（２）給定這段 指令所花的指令週期數，求出這段指令最少需要多少個暫存器•因為所有 指令所用到的暫存器的生命週期只有在基本區塊內，所以我們可以儘可能 地用到所有可用的暫存器，所以第一種最佳化對於超純量╱VLIW處理器的 編譯器比較實用•定出來的整數線性規劃數學式是用LINDO來解的•我們 在本文中舉了兩個例子，各有１３及１０個指令，而且做第一種最佳化• 若不考慮暫存器潑撒，此二例中將各有２０６及９３個數學式，並各有２ ３１及５６個變數•若有考慮暫存器潑撒，第二個例子有３３５個數學式 ，並有２４８個變數•此時我們不解第一個例子，因為很明顯地結果一定 很糟•本論文所得到的結果顯示出我們在解超純量╱VLIW處理器的指令排 程及暫存器配置問題方面已向一般化及實用化更進了一步•經由改進我們 得到的數學式及配合上一些啟發式演算法，我們相信在近期內一定能再前 進一大步•