應用整數線性規劃達成架構層級合成上 最佳化通道與暫存器配置之技術

Abstract

在深次微米科技裡，連線的延遲已經不再能被忽略。而且隨著製程的日益進步，更漸漸地主導了系統的時間延遲。規律分散式暫存器架構著眼在這個問題上。其相對的合成流程分散了暫存器並且利用實體區域化的特性來改善整個系統的時間延遲。然而，多出來的溝通代價，包含連線和暫存器卻限制了應用程式的規模。我們針對這個問題並且提出了所謂“在架構合成層次上通道與暫存器配置”的問題。輸入這個問題的是經過排程而且已經指定運算單元的資料流程圖、運算單元的擺置和代表目標架構的拓樸圖。目標是得到一個配置，它將每一個週期的所有傳輸資料對應到可使用的通道和暫存器上同時降低溝通的資源。除此之外，我們提出了這個問題正式的模型。藉由比重分配過的目標函式，我們能使用處理線性規劃的程式來得到最佳解。除此之外，由捕捉到每一個基本傳輸行為的好處，我們延伸了這一個模型，以利用後製的方式使他得到更進一步的改進並且模擬了雙向的通道。在實驗的結果裡，相較於之前僅僅使用專屬溝通的方法，我們所提出的線性規劃模型分別改善了平均58% 和35% 在連線和暫存器的使用上。就算和使用了管線連線而且執行了傳輸排程的方法比較，我們提出的方法也擁有分別為46% 和54% 的改善在連線和暫存器的使用上。

In deep submicron technology, the wiring delay has no longer been trivial and dominated the system latency gradually. The regular distributed register architecture is proposed to resolve this problem. The corresponding synthesis flow partitions the registers and exploits the physical locality to improve the system latency. However, it introduces the extra interconnection overhead, which includes wires and registers, and limits the scale of applications. We address this problem and formulate it as channel and register allocation in architecture level synthesis problem. The inputs are the scheduled and bound DFG, placed FUs and topology information of the target architecture. The goal is to get the assignment which maps all transferred data to available channels and registers at each cycle while minimizing the interconnection resource at the same time. Besides, we propose a formal model for this problem. With the weighted objective function, we can get the optimal solution through an ILP solver. Furthermore, due to the benefit of capturing the basic transfer behavior in our formulation, we also extend the model to get the further improvement and model the bi-directional channel through post processing. According to the experimental results, our proposed ILP method improves 58% and 35% on average in terms of usage on wires and registers compared to the previous method, which uses dedicated interconnections only. Even compared to another one, which uses pipelined wires and performs transfer scheduling, our method gets 46% and 54% improvement in terms of the usage on wires and registers.