半同步電路是指時鐘訊號到達每一個暫存器的時間儘管滿足其週期性,但到達時間並不一致。雖然最佳時序差異排序的方法可以改善電路的效率,但是它無法完全發揮半同步電路的最佳化性能。最佳時序差異排序方法的問題在於兩暫存器間最小傳遞延遲的時序競跑情形將形成電路的關鍵路徑。也就是說,如果在兩暫存器間的最小傳遞延遲可以適當地增加的話,時鐘週期將可以作進一步的最小化。在這篇論文當中,我們提出了多項式時間複雜度的一套演算法,其中針對半同步電路合成上整合了時序差異排序與插入訊號延遲。我們的演算法包含兩方面,首先我們重覆地解決電路的競跑情形所造成的時序限制,以達到時鐘週期最小化的目標。接下來的部分,在最小時鐘週期不變的前提之下,我們主要的目的在於求得插入訊號延遲的最小值。實驗數據的結果同時顯示出我們的這套演算法的確能有效地改善最佳時序差異排序的結果。同時,我們也將利用標準元件庫來實現我們的最佳化半同步電路。
A semi-synchronous circuit is a design style in which the clock signal is distributed to every register periodically, but not necessarily simultaneously. Although optimal clock skew scheduling can improve the circuit performance, it does not fully utilize the semi-synchronous framework. A problem of optimal clock skew schedule is that the minimum propagation delay between two registers may be a critical path with respect to the clock period due to race condition. Thus, an increase of the minimum propagation delay between the two registers may lead to further clock period minimization. In this paper, we present a polynomial time complexity algorithm, which incorporates clock skew scheduling and delay insertion, for the synthesis of semi-synchronous circuits. The proposed algorithm includes two phases. In the first phase, our objective is to minimize the clock period by iteratively resolving the limitations of race conditions. Then, in the second phase, our objective is to minimize the inserted delays under the minimum clock period. Benchmark results consistently show that our algorithm can effectively improve the optimal clock skew scheduling. We also demonstrate that our optimized semi-synchronous circuits can be realized by using a standard cell library.