producer and consumer concept ( I )

今天我想討論一個觀念，producer(生產者) and consumer(消費者) ordering model。我覺得這是一個做為一個系統整合的數位工程師應該要具備的基本觀念。但是，這個觀念是來自於 PCI 規格書裏。相信很多人都沒有看過 PCI 的規格，我怕我在解釋這個觀念時，有人會因此而看不懂。但如果省略，又怕很多工程師在做系統整合時，常犯一些讀寫設計的問題。實在很兩難 !

掙扎許多，還是決定試著解釋看看，希望有人可以看懂，如果有不懂的，可以留言給我，或是寫信來討論。

做為一個數位設計工程師，必須有一個觀念，那就是在數位訊號處理過程中，訊號不會無中生有。必須要有人給你訊號，然後你才能做事。而這時，就會有生產者的角色產生。有了生產者，當然就必須要有消費者來消費。在這生產-消費的過程中，產生了讀寫動作，造成許許多多讀寫順序的問題。也讓我們知道「資料前後一致性(consistent view of data)」的觀念在系統中扮演的角色是有多重要了。

在生產者與消費者的模型裏我們要探討的是: 

1. 生產者與消費者的順序觀念(the ordering of producer and consumer)

2. 資料的前後一致性的觀念( the consistent view of data)

Fig1: producer and consumer

假設，有一個生產者，一個消費者。生產者想把生產出來的資料存入data buffer中，它必須先確定是否data buffer沒有正在被讀，或是完全沒有被讀過？當生產者在寫入時，flag會被設定為1，而當寫完時，status會被清除為0。當消費者要讀出來時，必須先確定是否data buffer沒有正在被寫或是完全沒有被寫過。當消費者在讀出時，flag會被消除為0，而當讀完時，status會被設定為1。經由這些動作，我們可以確保資料不會被覆寫，也不會被覆讀。flag和status的做法的概念是很好的基礎觀念，值得我們拿來借鏡，應用在設計資料存取的一致性，尤其是設計hardware和firmware在對同一塊資料存取時，是一個很好用的方法。

如Fig1所示，當生產者和消費者都是在同一個bus(匯流排)時，讀寫動作是簡單，不會有任何的問題。但是如果生產者和消費者是如Fig2所示，讀寫動作就不再是單純的。這時就產生了優先順序的問題，不然就會有死結(dead lock)的情況產生。

Fig2: complex producer and consumer

如果生產者已經讀過 flag 和 status，想確定目前data內的資料是否是舊的，所以發出一筆讀status命令給Bridge。同時，消費者正在讀資料回來，所以發出一筆讀data的命令給Bridge。Bridge同時接受兩個不相同方向的命令，放入buffer中，接著對收入的命令的目地端的匯流排發出要求，來完成所被托付的任務。但是此時，生產者佔住了它自已的bus，而消費者也佔了它自己的bus，而在Bridge兩端的命令都無法被執行，因為它沒有拿到使用bus的權限。此時，生產者無法完成它的動作，因為消費端的bus它無法取得使用權，所以命令被卡在Bridge，下不去。消費者也無法得到它想要的data，因為它的命令也同樣是被卡在生產端的bus，無法執行。這時該怎麼辦？或許你會想，那就做一個timer，如果等 timeout，就重新執行。就可以解決死結的問題。這樣子的方式，確實可以解決死結。但是，如果每次都需要重新開始，每次開始的時間點都是一樣的，那麼是不是每次都會遇到死結的情形都會發生。這時，我們就遇到另外一個問題-飢餓狀態(starvation)，這又是另一個問題的產生。

亦或者你會想要把兩邊的 timer 設成不一樣長，這樣子是不是就有機會可以解？是的，但是這樣子的做法有效率嗎？遇到死結->等 timeout ->遇到死結 -> 等 timeout ->終於沒有死結。這種把問題丟給「機率」解決，似乎不是很好的辦法。如果我們把每個命令制定優先順序，我們就可以試著找到一種順序來解決所有的死結問題。
所以，制定一個「命令的優先順序」就變得很重要。但優先順序要怎麼制定?才可以保有效率，也可以保持資料前後一致性的特性，不會造成資料存取的錯誤。這又是另一個大篇長論，請容我賣個關子，待下回分解 !

是否long pulse 訊號一定要拿來做同步處理？

是否long pulse 訊號一定要拿來做同步處理？不做同步處理可以嗎？

如果不做同步處理?
任何的訊號，如果不做同步處理的話，都會有meta stable的產生的疑慮。而long pulse做同步
處理是比one-pulse訊號做同步處理來得容易多了。
很多人都認為long pulse不需要做同步處理，因為我下一個時間(next period time)，就可
以得到正確的long pulse訊號。就對下一個時間點而言，這樣子的說法這是正確的，但是對
目前的時間點而言，你已經沒有辦法保證你所設計的系統是穩定的，除非，你設計一個
會mask meta stable訊號的設計，但是，這有可能嗎？同步處理是每一個 T (period time)都
在進行的，你要怎麼知道每一個小段時間的起始點? 任何訊號你想要得到之前，都是要同步過的。所以沒有辦法知道每一小段的起始點，因為連知道這個起始點的訊息，也是要同步的。

不做同步處理的原因有很多，總結上來說，是因為你的設計不管有沒有meta stable，都不
會影響系統的正確性，所以才會省略一個D-F.F.(D-Flip-Flop)。

如果做同步處理?
如果做同步處理, 則所有的訊號都會是收斂在同一個clock domain，提高系統穩定度。

做同步處理和不做同步處理，相差的D-F.F.只有幾個，並不會太多，就整個系統來說，也不會太多。就我的經驗，整個晶片裏，同步處理的D-F.F.並沒有佔到整個晶片的1%(甚至可能不到0.1%或是0.01%)，為什麼要省這些D-F.F.，來讓系統有不穩定的機會。
降低成本的方式有很多，我們也可以用轉進更微小製程來降低成本，例如：90ns轉進到28ns製程。節省這個D-F.F，就節省面積來說，節省不到1%面積(甚至可能不到0.1%或是0.01%)的方式，換算成成本，應該會是多少錢呢？比起因系統不穩，而需付出NRE的費用來說，哪一個才是比較少的？

並不是說long-pulse 訊號在cross clock domain的處理上，一定要做同步；而是說，如果同步處理是你無法避免的過程，那麼省略這幾個D-F.F.的做法，能不做還是不做，因為它帶來的實際上的效益並沒有太大。對於有meta stable的訊號，標準流程應該是直接捨棄不用，而不用去考慮它是否會帶給系統不穩定的機會有多大。

module介面訊號的收斂與發散的思考

在離散數學課程中，曾學到如何把一個發散的數學式子轉換到收斂的數學式子；其做法是把原來式子做整理(積分或是微分的處理)，重新寫出新的數學式子，這樣子才可能把發散的條件轉換到收斂的條件，然後才能得到我們想要的結果。

同理，一個控制流程的很好的module(模組)，它在介面訊號上，也會是一個收斂的。如何確保你的module是一個收斂的介面module。

第一步: 選擇一個clock為主要的clock domain，所有的控制訊號都是在這個主要的clock domain下被控制、操作。

第二步: 把所有不同步的控制訊號處理同步到主clock domain。這種做法就是把原來發散條件轉換到收斂條件。以下是示意圖。

Fig1: Divergence and convergence

以下的波形圖是用來解釋上面圖形的。從波形圖中clockA有一個需求reqA，向clockB的module提出。因為不相同頻率的訊號直接使用，會有meta stable問題，所以reqB_syn1就是來解決meta stable。之後再拿reqB_syn2和reqB_syn3來操作，得到一個需求訊號reqB_get。Module B用這個reqB_get是安全的。然後再產生reqB_clr去回覆module A 的需求。reqB_clr一樣，也是經過一連串的同步處理，最後，module A得到在clockA domain 下reqA_clr，module A則用reqA_clr來清除reqA訊號，這也是安全的。以下是波形圖。

Fig2: waveform of divergence and convergence

這樣子的做法，可解決大部份介面訊號發散的情況，也可以運用到所有的控制訊號的處理。目前我唯一遇過比較不同的是DDR PHY的控制訊號處理，它沒有辦法把所有的訊號線同步到相同的clock domain，而這是因為DDR PHY的設計上比較講究latency的長短以及它本身是clock的上升緣及下降緣都是資料處理的時間點，所以做法上更複雜，但是其基本精神也是沒有脫離上述的觀念。

在設計一個模組時，一定都要隨時隨地保有發散、收斂的觀念在心中，並確保每個控制訊號都是收斂的環境下操作，這樣子才可以確保每個IP都是收斂且穩定高的module。 

恐龍版OS裏的哲學家問題的思考

在做controller時，常需要去思考一個問題，那就是權杖是由誰主導？一個好的controller就是把權杖的問題處理好，讓各個部份都能各司其職，也不會相突衝。這樣子說明，或許有許多人不明瞭，以下我舉一個例子。

在PCIE的規格裏，有一個skip order set的機制，是被用來做在傳輸中補償機制。但是傳送skip order是由誰做，卻沒有明確的說明，但是這部份的描述是放在LTSSM章節。而PCIE大致上是被分為Tx, Rx, LTSSM三大部份。既然被寫在LTSSM章節，那應該由LTSSM做即可；但是LTSSM並沒有負責全部的流程機制，有部份是由Tx負責。一旦權杖沒有做好，就會造成溝通問題。

PCIE的controller要操控性好、流暢，Tx, RX以及LTSSM都是重要的部份。Skip order set則應該算是其中會影響的重要螺絲。從LTSSM的FSM來看，當進入L0時，權杖(Token)就已經不在LTSSM那一層，而是到Tx的DLP或是TLP。如果把skip order set只做在LTSSM那一層，而當Tx進入L0時，Tx已經拿到權杖，而當skip order set倒數時間到，需要發送skip封包時，因為Tx沒有做skip order set的機制，所以要把權杖還給LTSSM，LTSSM需要把權杖搶走，送完Skip order set後再歸還權杖。此時Tx所需要做的事就是保證在未來的傳送skip order set的時間內，都不會有TLP或是DLP要傳送，靜待LTSSM 完成工作。這是我常看到的hand shake；但是常因hand shake時間溝通不清楚，進而影響了skip order set的傳送。

在PCIE的規格書裏，說明進入L0後，就是屬於Tx的負責範圍，那為什麼還要要求 LTSSM做事？很多人都以為這只是hand shake機制沒有做好，做好後就不會發生問題。在我看來，這樣子的做法只是治標，不是治本。當你以後要增加新功能時，會不會受到影響？你還能確定你的hand shake還可以運作嗎？其實整個核心問題就是「權杖」，恐龍版的OS明確的說出，權杖拿到手，就要做事，不做事就會dead lock。為什麼Tx你已經拿到權杖，還要把skip order set的工作往外推出，叫LTSSM做？這和恐龍的觀念不符合。

換個角度想，拿到權杖的人負責做事，而且要把所有的事都做完。移出權杖的人，則是已經把該做的事情做完了，沒有任何責任。用這樣子的想法去架構你的control flow，簡單而且不太會出錯。尤其是用在數位和類比之間的溝通，其實還滿好用的。

之後，我也常常用這個方法去思考控制轉移的問題，簡化了不少複雜控制。再一次驗證了，經典真是不愧為經典。

註解：1. 恐龍版的書名應該是Operating System Concepts

      2. 作者: Abraham Silberschatz．Peter B. Galvin．Greg Gagne

case裏default中don't care的使用經驗

以上是有人發現的文章，然後和我討論，建議應該把” default: y=1’bx” 換成是” default: y=1’b0” 或是default: y=1’b1”。反正就是不應該是1’bx，不然會造成系統不穩，或是合成時，會有問題。

” default: y=1’bx” 真的會有問題嗎？

做為一個數位工程師，邏輯推理能力應該是我們自豪的。原英文描述是說在模擬(simulation)時，會有pre-synthesis simulation和post-synthesis simulation的結果不相同(mismatch)，所以如果你是想要它相同的話，你應該是把1’bx換成是固定的值，這樣子，每次模擬時，就都會是一樣的。對於這樣子的建議，我同意的它的說法。但是，它的前面有個前提，你的1’bx是會被當成是”don’t care”來處理。我們都知道，don’t care就是不在乎它的結果，甚至每次都是不一樣也沒有關係。所以這樣子的”don’t care”當然會在不同的模擬過程，造成不同的結果。

我們都學過真值表(truth table)。

A  fun   B	0	1
0	0	1
1	1	X

上面的truth table表示什麼？當A=1、B=1時，我們不在乎它的值是0還是1。那你當然可以把它當成是0來做一個式子，你也可以用1來做另一個式子。那你也真的只是上面有1的結果來做你的式子。但不管哪一種，都會是你要的結果，都是不會錯的。因為會為1的等式必定成立。

上面的verilog 程式也是一樣的。如果這個don’t care是你真的想要的don’t care時，那模擬結果不同時，有差別嗎？答案是沒有；因為你已經把這個會發生的情形考慮清楚，做好所有的處理所以不會讓整個系統發生錯誤。

從上面的英文，都沒有描述到這樣子的做法會讓系統不穩定，或是合成時，會發生問題，以致於netlist是合錯的。

數位工程師最怕的模擬結果是mismatch，但是不是所有的mismatch都是錯誤。要從系統面和真值表中去了解設計的核心。不應該是怕mismatch，所以把所有的mismatch都是當成是錯誤的。這樣子的想法是不對的。

我再舉一個例子，請看下面的verilog的程式。

wire a;

reg [2:0] FSM, FSM_nxt;

always(posedge clki or negedge rstni)

begin

    if(~rstni)

        FSM <=3'b001;

    else

        FSM <= FSM_nxt;

end

always@(*)

begin

    case(FSM)

    3'b001:

        if(a)

            FSM_nxt = 3'b010;

        else

            FSM_nxt = FSM;

    3'b010:

        if(a)

            FSM_nxt = 3'b100;

        else

            FSM_nxt = FSM;

    3'b100:

        if(a)

            FSM_nxt = 3'b001;

        else

            FSM_nxt = FSM;

    default:

        FSM_nxt = 3'bxxx;

    endcase

end

同樣地，default都是有don’t care的描述，但是上面的don’t care並不會讓pre-post simulation和post-simulation產生 result mismatch的問題？原因你知道嗎？因為default 的情況並不會產生，因為FSM的路徑是001->010->100的循環，並不會到別的狀態(例如: 011,110,111,000…等等)。因為FSM不會到達don’t case的狀態，所以不會產生mismatch。

那換另一個角度來思考，如果真的跑到don’t case的狀態，那又代表什麼？到目前為止，我遇到的都是表示你的這部份程式的timing violation產生。所以你應該再檢查一次你的synthesis的結果。或許你忽略了這部份的timing，亦或是你的synthesis constrain沒有設定正確，所以這部份的timing被忽視了。不管是哪一個情況，我們都知道don’t care是我們不想發生的情況，所以simulation看到xxx時，你可以很容易就警覺到問題，這對工程師是很有幫助的。

上述的英文讓我們了解到，如果你沒有把所有的情況考思清楚(含有用的狀態和沒有用的狀態)，反而直觀地把所有沒有用的狀態都當成是don’t care時，這時會容易發生英文上所描述的事形發生，這時你就很容易被混淆，而誤會系統是不穩定的。

所以應該是，當你不知道要做什麼時，你不應該用don’t care的語法，因為這會讓你的系統發生你沒有預期的行為。而當你知道你真的是要用don’t care時，而你用don’t care語法，這表示你已經考慮到所有的狀態，並讓系統清楚知道要做出什麼的反應和行為，此時，系統就不會發生任何錯誤。

別再為了mismatch而去反抗mismatch；真正去了解為什麼會mismatch，並清楚知道整個系統的運作，會讓你學到更多的事情。

FIFO是基本功

有很多剛出社會的工程師，被指派FIFO設計工作時，心裏面一定都會想，這個這麼簡單，有沒有更難的，我可不是來這邊做這種簡單的設計。我是來學更難的東西。

其實，一個基本功好的工程師，他的FIFO design也一定是很紮實。FIFO常被用來解決很多的問題，所以FIFO的設計也牽扯到很多的問題，例如：跨clock domain的處理？serial轉parallel問題？兩邊不同的Spec要怎麼溝通？兩個存取速度不同時，要怎麼溝通？這些問題看似不同，但是其實都是同一種的本質—FIFO兩邊的步調不同。既然核心問題只有一個，那解法不就是一種就可以了？那為什麼網路上FIFO的架構有那麼多？(當然，條條道路通羅馬。我不是表達這麼多種做法不對，而是所有的做法，其本質是只有一種。了解一種做法應該就夠了，其他的都是相似的道理。)

各位看官你可以細細看，這麼多不同架構的FIFO，大都是在探討一個問題，那就是訊號在跨clock domain的處理。如果你對跨clock domain訊號處理的觀念正確了，且了解你要解決的問題是什麼，也知道自己所處理的訊號是屬於哪一種的訊號(long-pulse signal or one-pulse signal)？是連續還是不連續的處理？這些如果你都有清楚知道的話，那麼我相信，你所設計出來的FIFO，相信一定可以解決你的需求。

從宏觀的角度來說，FIFO就好像是水管，而data就像是流水一樣。FIFO design像是設計水管的接法，直到出水口的速度和流量符合你想要的結果。設計水管時，我們所會遇到的問題是什麼？

1. 當水流又強又快時，你想放慢它，你會怎麼做？

2. 當水流又慢又多時，你想加快它，你會怎麼做？

第一題的做法應該是找更粗的水管慢慢地加大，直到你想要的流速及流量。第二題的做法應該是和第一題相反的做法。

FIFO的基本解法，也不外乎是這些做法。剩下來的就是實作經驗以及跨clock domain處理的觀念建立。

那麼FIFO可以用來解決哪些問題呢 ？

FIFO可以用來解決兩邊不同interface不相容的問題。FIFO可以用來解決系統中write/read順序的問題(PCI ordering)。FIFO可以用來解決producer&consumer的write/read racing問題。FIFO可以用來做排程(scheduling)的處理。FIFO可以用來serial轉parallel，當然也可以parallel轉serial。FIFO可以用來解決的問題這麼多。這樣子，你還會認為FIFO是簡單的設計嗎？

之前討論過，FIFO核心問題只有一個，當你了解到FIFO本質時，你就會知道怎麼做FIFO。很多人不了解跨clock domain和FIFO之間的本質，所以才會有很多種不同的想法、做法，甚至想要用reset來解決同步的問題。

其實認真處理跨clock domain訊號，認真設計一個實用的FIFO，將兩個合在一起，你就可以用這個架構一輩子。

gray code encode and decode(下)

上個星期提出如何將binday code 轉換成gray code。

今天就示範如何將gray code轉換成binary code. 

module gray2binary(

  gray

, bin

);

input [4:0] gray;

output [4:0] bin;

assign bin[4] = gray[4];

assign bin[3] = ^gray[4:3];

assign bin[2] = ^gray[4:2];

assign bin[1] = ^gray[4:1];

assign bin[0] = ^gray;

endmodule

有興趣的人可以試著推看看，是不是這樣子就可以將gray code還原成binary code. 

以上的gray code的encode和decode都是很簡單的做法。或許有些人已經知道原理，但是卻不知道怎麼做？亦或許已經有人都知道了。

不管怎麼樣，都希望能提供一個方法給大家參考! 如果有人的方法更好，歡迎大家來提出來討論。