資料路徑合成中多重輸出入埠記憶體分配問題對埠使用率的提昇

Abstract

在本論文中，對多重輸出入埠分配問題提出一個以圖形理論來解決新方法 。我們針對以兩階段時脈（two-phase clock scheme）為目的結構的基礎 下，為提升多重輸出入埠記憶體上埠的使用率，使同一個埠能等不必要的 動作。在此原則下，我們共採三步驟來完成多重輸出入埠分配的問題：（ １）變數的分割：主要是依變數被使用的情況來分割的。我們使用了圖形 理論來解決的，不但能依變數的使用情況來分割，且產生較少數量的暫存 器。（２）埠的連接：是連接埠和在第（１）個步驟所產生的暫存器。我 們採用了 left-edge的演算法。（３）連線最小化：使埠和功能單元之間 的連線花費最小。我們採用 MAP的線性方程來解的。由實驗結果顯示我們 所提出的方法相當有效，且得到令人興奮的結果。 In this thesis, we present a new method based on graph theory to solve the problem of allocation of multiport memories. Based on the target architecture of two-phase clocking scheme, to enhance the ports utilization of multiport memory, we make the same port be written on the first phase and read on the second one. By such way, we can save many cost of internal connections (or control signals), and eliminate some unnecessary "pure data transfer" operations. Under such principle, we overcome the problem of allocation of multiport memories by three steps: (1) Partitioning of variables: it is mainly according to the conditions of variables being used. We solve it by graph theory. It is not only partitioning the variables according to the conditions of being used, but also producing fewer registers. (2) Connecting of ports : it connects ports with the registerd produced in step (1). Here , we adapt Left-Edge algorithm. (3) Interconnections minimization : minimize the cost of interconnections between ports and functional units. Here, we adapt linear programming method from MAP. Experimental results show that the method we presented is very effective, and get a promising result.