暫存器轉換階層硬體描述語言之硬體合成及相關圖形理論之研究

Abstract

硬體描述語言的硬體合成（HDL synthesis）是一個轉換的過程，這個轉換的過程將用硬體描述語言如Verilog和VHDL撰寫的設計轉成一個結構層次的網列（netlist），然而傳統的合成器採用特別的方法來解決硬體描述語言的硬體合成中的特別元件推論包括拴（latch）的推論、正反器（flip-flop）的推論及高阻抗緩衝器（tri-state buffer）的推論。這些特別的方法經由一個程序（process）一個程序的辨認一些語意的樣版來推論拴、正反器和高阻抗緩衝器。他們沒有考慮跨程序間的關聯性，因此，沒有辦法完整地正確地解決這些問題。這導致設計者必須遵守一些不合理的限制以便能得到正確又有效的網列。即使如此，傳統的合成器還是有可能產生錯誤的網列，因而造成驗證設計正確性上額外的負擔。 在本論文中，我們首先針對硬體描述語言之硬體合成提出一個合成的流程。不像傳統的合成器在產生組合電路網路前執行特殊元件的推論，我們的作法首先針對輸入硬體描述語言的描述產生完整的組合電路網路。然後，我們的方法是在這整個的組合電路網路上執行特殊元件的推論，因此可以考慮到跨程序間的關聯性。 根據上面提到的流程，本論文針對硬體描述語言的硬體合成中的拴的推論、正反器的推論和高阻抗緩衝器的推論提出有系統的演算法。在硬體描述語言硬體合成中拴的推論上，我們將拴的推論的問題化簡成圖形理論（graph theory）中的最小回饋點集合（minimum feedback vertex set）的問題，因此可以正確又有效的推論出最少的拴。在硬體描述語言硬體合成中正反器的推論上，根據多重時鐘正反器（multiple clocked flip-flop）的概念，我們提出一基於重新時序（retiming）技巧的架構，此架構可以對簡單和複雜的時鐘敘述（clocked statement）有系統且正確地推論出最小數量的正反器。更進一步的，我們也針對多重時鐘正反器提出了一種可能的實現方式。在多重時鐘正反器的支援下，傳統硬體描述語言可合成的子集合可以被進一步的延伸。在硬體描述語言硬體合成中高阻抗緩衝器的推論上，我們提出一個基於矯正（rectification）概念的合成的模型。首先，我們先從輸入硬體描述語言的描述建構出一個不能正確展現高阻抗行為的天真網列（naive netlist），然後再將一些由矯正電路控制器控制的矯正電路插入天真網列中使得被矯正的網列可以展現輸入硬體描述語言描述的行為。 本論文所提出的推論演算法有系統的解決在硬體描述語言硬體合成中拴的推論、正反器的推論和高阻抗緩衝器的推論。這些演算法可以增加硬體描述語言硬體合成的可靠性，使得設計者可以擺脫在撰寫型態（coding style）上不合理的限制，避免合成跟模擬間的不一致，因而可以降低驗證上的負擔。 在一個圖形中找出最小回饋點集合對很多電腦輔助設計的應用包括硬體描述語言硬體合成中拴的推論和可測試性設計（design for testability）中的部分掃瞄（partial scan）等等而言是一個重要的問題。在本論文的最後我們深入的探討圖形理論中最小回饋點集合的問題，並且基於一些創新的定理提出三個新的化簡操作。根據這些化簡操作，我們更進一步設計了一些有效的演算法，這些化簡操作跟這些演算法對部分掃瞄的問題而言已經被驗證是非常有效的。

HDL synthesis is a process that translates a design written in Hardware Description Language (HDL) such as Verilog and VHDL into a structural netlist. However, typical synthesizers adopt ad hoc methods to solve the special element inferences including latch inference, flip-flop inference and tri-state buffer inference in HDL synthesis. The ad hoc methods infer the latches, flip-flops, and tri-state buffers by recognizing some syntactic templates in HDL description process by process. They do not take into account the dependencies across processes and thus cannot completely and correctly solve the problems. It results in that designers must follow some unreasonable limitations in order to get correct and efficient netlists. Nonetheless, the typical synthesizers could still generate a wrong netlist and imposes extra overheads on verifying a design. In the dissertation, we first propose a synthesis flow for HDL synthesis. Unlike the typical synthesizers that conduct the special element inferences before the combinational circuit network generation, our approach first generates the overall combinational circuit network for the input HDL description. Then, it conducts the special element inferences on the overall combinational circuit network and thus can take into account the dependencies across processes. According to the flow mentioned above, the dissertation proposes systematical algorithms for the latch inference, flip-flop inference and tri-state buffer inference in HDL synthesis. On latch inference in HDL synthesis, we reduce the latch inference problem to the minimum feedback vertex set (MFVS) problem in graph theory. Therefore, the minimum number of latches can be inferred correctly and efficiently. On flip-flop inference in HDL synthesis, according to the concept of multiple clocked flip-flops (MC flip-flops), we propose a retiming based framework to infer the minimum number of flip-flops systematically and correctly for both simple and complex clocked statements. Furthermore, we also proposed a possible implementation for the MC flip-flops. With the support of MC flip-flops, the typical synthesizable subset of HDL could be extended. On the tri-state buffer inference in HDL synthesis, we propose a synthesis model based on the concept of rectification. First, a naive netlist that cannot correctly perform the high impedance behavior is constructed from input HDL description. Then, a set of rectification circuits that are controlled by a rectification circuit controller is inserted so that the compensated netlist can perform the behavior required by the input HDL description. The inference algorithms proposed in the dissertation systematically solve the problems of latch inference, flip-flop inference and tri-state buffer inference in HDL synthesis. It increases the reliability of HDL synthesis, makes designers get rids of unreasonable limitations on coding style, avoids the mismatches between synthesis and simulation in HDL synthesis, and thus reduces verification overheads. Finding the minimum feedback vertex set in a graph is an important problem for a variety of CAD applications including the latch inference in HDL synthesis, the partial scan in design for testability, etc. In the last of the dissertation, we make an in-depth exploration on the minimum feedback vertex set problem in graph theory and propose three new reduction operations based on some innovative theorems. According to the reduction operations, we further design some efficient algorithms. The reduction operations and the algorithms are demonstrated to be very effective in partial scan problem.