Subversion Repositories cryptosorter

//----------------------------------------------------------------------//
// The MIT License 
// 
// Copyright (c) 2008 Alfred Man Cheuk Ng, mcn02@mit.edu 
// 
// Permission is hereby granted, free of charge, to any person 
// obtaining a copy of this software and associated documentation 
// files (the "Software"), to deal in the Software without 
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//

//////////////////////////////////////////////////////////////////////////
// Summary
//
// This file describes the implementation of VLevelFIFO which time multiplex
// a single memory instance with one write port and one read port between
// multiple logical fifos. The implementation is parameteric in the following
// ways: 1) the number of logical fifos, 2) the size of each logical fifo,
// 3) the data type stored in the fifo      
//////////////////////////////////////////////////////////////////////////

// import standard library
import DReg::*;
import FIFO::*;
import RegFile::*;
import StmtFSM::*;
import Vector::*;

// import self-made library
import BRAM::*;
import EHRReg::*;
import VLevelFIFO::*;

`define Debug False

// try to update the new value of vec[idx] to f(vec[idx]) 
function Vector#(sz,a) parUpdate (Vector#(sz,a) vec, Bit#(isz) idx, 
                                  function a f (a val));
   Vector#(sz,a) new_vec = newVector();
   for (Integer i = 0; i < valueOf(sz); i = i + 1)
      begin
         if (idx == fromInteger(i))
            new_vec[i] = f(vec[i]);
         else
            new_vec[i] = vec[i];
      end
   return new_vec;
endfunction
   
function Bit#(a) decrBy(Bit#(a) snd, Bit#(a) fst);
   return fst - snd;
endfunction
 
// implementation of VLevelFIFO with BRAM
module mkBRAMVLevelFIFO (VLevelFIFO#(no_fifo, fifo_sz, data_t))
   provisos (Bits#(data_t,data_sz),
             Add#(TLog#(no_fifo),TLog#(fifo_sz),bram_idx_sz));   

   // instantiate an unguarded 1 cycle latency bram (i.e. the read response will only valid for 1 cycle)  
   UGBRAM#(Bit#(bram_idx_sz), data_t)           ugbram <- mkBypassUGBRAM_Full();
   
   RegFile#(Bit#(TLog#(no_fifo)),Bit#(TLog#(fifo_sz)))  head <- mkRegFileFull();
   RegFile#(Bit#(TLog#(no_fifo)),Bit#(TLog#(fifo_sz)))  tail <- mkRegFileFull();
   Reg#(Bit#(TLog#(no_fifo))) i <- mkReg(0);
   Reg#(Bool) finishInit <- mkReg(False);
   
   EHRReg#(2,Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))))  usedReg;
   usedReg <- mkEHRReg(replicate(0));  
   EHRReg#(2,Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))))  freeReg;
   freeReg <- mkEHRReg(replicate(fromInteger(valueOf(fifo_sz))));

   Wire#(Maybe#(Bit#(TLog#(no_fifo))))  enqIdx <- mkDWire(tagged Invalid);
   Wire#(data_t)                        enqVal <- mkDWire(?);
   Reg#(Maybe#(Bit#(TLog#(no_fifo))))   lastEnqIdx <- mkDReg(tagged Invalid);     
   
   Wire#(Maybe#(Bit#(TLog#(no_fifo))))  deqIdx <- mkDWire(tagged Invalid);
   Reg#(Maybe#(Bit#(TLog#(no_fifo))))   lastDeqIdx <- mkDReg(tagged Invalid);     

   Wire#(Maybe#(Bit#(TLog#(no_fifo))))  firstIdx <- mkDWire(tagged Invalid);
   
   Wire#(Maybe#(Bit#(TLog#(no_fifo))))  decrFreeIdx <- mkDWire(tagged Invalid);
   Wire#(Bit#(TLog#(TAdd#(fifo_sz,1)))) decrFreeAmnt <- mkDWire(?);
      
   let enqIdxVal         = fromMaybe(0,enqIdx);
   let deqIdxVal         = fromMaybe(0,deqIdx);
   let firstIdxVal       = fromMaybe(0,firstIdx);
   let decrFreeIdxVal    = fromMaybe(0,decrFreeIdx);
   let deqIdxNEQFirstIdx = deqIdxVal != firstIdxVal;  
   let readResp          = ugbram.read_resp();
     
   // start the initialization processor
   rule initialization(!finishInit);
      head.upd(i,0);
      tail.upd(i,0);
      i <= i + 1;
      if (i == fromInteger(valueOf(no_fifo)-1))
         finishInit <= True;
   endrule   
   
   rule processEnq(finishInit && isValid(enqIdx));
      let tailVal = tail.sub(enqIdxVal);
      tail.upd(enqIdxVal, (tailVal + 1));
      ugbram.write({enqIdxVal,tailVal},enqVal);
      lastEnqIdx <= enqIdx;
      
      if(`Debug) $display("%m enq data %d to fifo %d with tailVal %d",enqVal,enqIdxVal,tailVal);
   endrule
    
   // last cycle someone enq, we update the usedReg this cycle (conservative
   rule updateUsedReg (isValid(lastEnqIdx));
      let idx = fromMaybe(?,lastEnqIdx);
      usedReg[0] <= parUpdate(usedReg[0], idx, \+ (1));

      if(`Debug) $display("%m updateUsedReg idx %d old val %d new val %d",idx,usedReg[0][idx], usedReg[1][idx]);
   endrule  
      
   // last cycle someone deq, we update the freeReg this cycle (conservative)
   rule updateFreeReg (isValid(lastDeqIdx));
      let idx = fromMaybe(?,lastDeqIdx);
      freeReg[0] <= parUpdate(freeReg[0], idx, \+ (1));

      if(`Debug) $display("%m updateFreeReg idx %d old val %d new val %d",idx,freeReg[0][idx], freeReg[1][idx]);
   endrule  
   
   rule processDeq(finishInit && isValid(deqIdx));
      let headVal = head.sub(deqIdxVal);
      head.upd(deqIdxVal, (headVal + 1));     
      usedReg[1] <= parUpdate(usedReg[1], deqIdxVal, decrBy(1));
      lastDeqIdx <= deqIdx;

      if(`Debug) $display("%m deq fifo %d",deqIdxVal);
   endrule
   
   rule processFirstReq(finishInit && isValid(firstIdx));
      let headVal = head.sub(firstIdxVal);
      ugbram.read_req({firstIdxVal,headVal});
//       if (deqIdxNEQFirstIdx || !isValid(deqIdx))
//          begin
//             ugbram.read_req({firstIdxVal,headVal});
            
//             if(`Debug) $display("%m first read idx %d headVal %d",firstIdxVal,headVal);
//          end
//       else // the fifo is dequeued at that cycle, we should read the next head
//          begin
//             ugbram.read_req({firstIdxVal,headVal+1});
            
//             if(`Debug) $display("%m first read idx %d headVal+1 %d",firstIdxVal,headVal+1);
//          end
   endrule
           
   rule processDecrFree(finishInit && isValid(decrFreeIdx));             
      freeReg[1] <= parUpdate(freeReg[1], decrFreeIdxVal, decrBy(decrFreeAmnt));
      
      if(`Debug) $display("%m decrFree fifo %d by %d",decrFreeIdxVal,decrFreeAmnt);
   endrule

   // enq is unguarded here, we expect the user to check it before they enq
   method Action enq(Bit#(TLog#(no_fifo)) idx, data_t data) if (finishInit);
      enqIdx <= tagged Valid idx;
      enqVal <= data;      
   endmethod
   
   // deq is unguarded here, we expect the user to check it before they deq
   method Action deq(Bit#(TLog#(no_fifo)) idx)  if (finishInit);
      deqIdx <= tagged Valid idx;    
   endmethod
   
   method Action firstReq(Bit#(TLog#(no_fifo)) idx)  if (finishInit);
      firstIdx <= tagged Valid idx;
   endmethod
   
   // first is unguarded here, we expecte the user to check it before they call first
   method data_t firstResp()  if (finishInit);
      return readResp;
   endmethod
   
   method Action clear()  if (finishInit);
      noAction;
   endmethod
   
   // return the usage of each fifo at the beginning of the cycle
   method Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))) used()  if (finishInit);
      return usedReg[0];
   endmethod
   
   // return enq credit token available for each fifo
   method Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))) free()  if (finishInit);
      return freeReg[0];
   endmethod
   
   // get credit token to enq fifo idx in the future
   // this method is unguarded (i.e. user need to call method free 
   // and check for token availability before calling this action)
   method Action decrFree(Bit#(TLog#(no_fifo)) idx, Bit#(TLog#(TAdd#(fifo_sz,1))) amnt)  if (finishInit);
      decrFreeIdx  <= tagged Valid idx;
      decrFreeAmnt <= amnt; 
   endmethod
   
endmodule
 
// implementation of VLevelFIFO with BRAM decrFree is always treated as deq one token
module mkDecrOneBRAMVLevelFIFO (VLevelFIFO#(no_fifo, fifo_sz, data_t))
   provisos (Bits#(data_t,data_sz),
             Add#(TLog#(no_fifo),TLog#(fifo_sz),bram_idx_sz));   

   // instantiate an unguarded 1 cycle latency bram (i.e. the read response will only valid for 1 cycle)  
   UGBRAM#(Bit#(bram_idx_sz), data_t)           ugbram <- mkBypassUGBRAM_Full();
   
   RegFile#(Bit#(TLog#(no_fifo)),Bit#(TLog#(fifo_sz)))  head <- mkRegFileFull();
   RegFile#(Bit#(TLog#(no_fifo)),Bit#(TLog#(fifo_sz)))  tail <- mkRegFileFull();
   Reg#(Bit#(TLog#(no_fifo))) i <- mkReg(0);
   Reg#(Bool) finishInit <- mkReg(False);
   
   Reg#(Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))))  usedReg <- mkReg(replicate(0));
   
   Reg#(Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))))  freeReg <- mkReg(replicate(fromInteger(valueOf(fifo_sz))));
   
   Wire#(Maybe#(Bit#(TLog#(no_fifo)))) enqIdx <- mkDWire(tagged Invalid);
   Wire#(data_t)                       enqVal <- mkDWire(?);
   
   Wire#(Maybe#(Bit#(TLog#(no_fifo)))) deqIdx <- mkDWire(tagged Invalid);

   Wire#(Maybe#(Bit#(TLog#(no_fifo)))) firstIdx <- mkDWire(tagged Invalid);
   
   Wire#(Maybe#(Bit#(TLog#(no_fifo)))) decrFreeIdx <- mkDWire(tagged Invalid);
      
   let enqIdxVal         = fromMaybe(0,enqIdx);
   let deqIdxVal         = fromMaybe(0,deqIdx);
   let firstIdxVal       = fromMaybe(0,firstIdx);
   let decrFreeIdxVal    = fromMaybe(0,decrFreeIdx);
   let deqIdxNEQFirstIdx = deqIdxVal != firstIdxVal;  
   let readResp          = ugbram.read_resp();
     
   // start the initialization processor
   rule initialization(!finishInit);
      head.upd(i,0);
      tail.upd(i,0);
      i <= i + 1;
      if (i == fromInteger(valueOf(no_fifo)-1))
         finishInit <= True;
   endrule
   
   rule updateUsedReg(finishInit && (isValid(enqIdx) || isValid(deqIdx)));
      Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))) newUsedReg = newVector();
      for (Integer i = 0; i < valueOf(no_fifo); i = i + 1)
         begin
            Bit#(TLog#(no_fifo)) iVal = fromInteger(i);
            let checkEnqIdx = enqIdxVal == iVal;
            let checkDeqIdx = deqIdxVal == iVal;
            if (isValid(enqIdx) && checkEnqIdx && !(isValid(deqIdx) && checkDeqIdx))
               newUsedReg[i] = usedReg[i] + 1;
            else
               if (isValid(deqIdx) && checkDeqIdx && !(isValid(enqIdx) && checkEnqIdx))
                  newUsedReg[i] = usedReg[i] - 1;
               else
                  newUsedReg[i] = usedReg[i];
         end
      usedReg <= newUsedReg;

      if(`Debug) $display("%m updateUsedReg");
   endrule
   
   rule updateFreeReg(finishInit && (isValid(decrFreeIdx) || isValid(deqIdx)));
      Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))) newFreeReg = newVector();
      for (Integer i = 0; i < valueOf(no_fifo); i = i + 1)
         begin
            Bit#(TLog#(no_fifo)) iVal = fromInteger(i);
            let checkDecrFreeIdx      = decrFreeIdxVal == iVal;
            let checkDeqIdx           = deqIdxVal == iVal;
            if (isValid(decrFreeIdx) && checkDecrFreeIdx && !(isValid(deqIdx) && checkDeqIdx))
               newFreeReg[i] = freeReg[i] - 1;
            else
               if (isValid(deqIdx) && checkDeqIdx && !(isValid(decrFreeIdx) && checkDecrFreeIdx))
                  newFreeReg[i] = freeReg[i] + 1;               
               else
                  newFreeReg[i] = freeReg[i];               
         end
      freeReg <= newFreeReg;

      if(`Debug) $display("%m updateFreeReg");
   endrule
   
   rule processEnq(finishInit && isValid(enqIdx));
      let tailVal = tail.sub(enqIdxVal);
      tail.upd(enqIdxVal, (tailVal + 1));
      ugbram.write({enqIdxVal,tailVal},enqVal);

      if(`Debug) $display("%m enq data %d to fifo %d with tailVal %d",enqVal,enqIdxVal,tailVal);
   endrule
   
   rule processFirstReq(finishInit && isValid(firstIdx));
      let headVal = head.sub(firstIdxVal);
      ugbram.read_req({firstIdxVal,headVal});
      
//       if (deqIdxNEQFirstIdx || !isValid(deqIdx))
//          begin
//             ugbram.read_req({firstIdxVal,headVal});
//             if(`Debug) $display("%m first read idx %d headVal %d",firstIdxVal,headVal);
//          end
//       else // the fifo is dequeued at that cycle, we should read the next head
//          begin
//             ugbram.read_req({firstIdxVal,headVal+1});
//             if(`Debug) $display("%m first read idx %d headVal+1 %d",firstIdxVal,headVal+1);
//          end
   endrule

   rule processDeq(finishInit && isValid(deqIdx));
      let headVal = head.sub(deqIdxVal);
      head.upd(deqIdxVal, (headVal + 1));      
   endrule
   
   // enq is unguarded here, we expect the user to check it before they enq
   method Action enq(Bit#(TLog#(no_fifo)) idx, data_t data) if (finishInit);
      enqIdx <= tagged Valid idx;
      enqVal <= data;      
   endmethod
   
   // deq is unguarded here, we expect the user to check it before they deq
   method Action deq(Bit#(TLog#(no_fifo)) idx)  if (finishInit);
      deqIdx <= tagged Valid idx;
      
      if(`Debug) $display("%m deq fifo %d",idx);
   endmethod
   
   method Action firstReq(Bit#(TLog#(no_fifo)) idx)  if (finishInit);
      firstIdx <= tagged Valid idx;
   endmethod
   
   // first is unguarded here, we expecte the user to check it before they call first
   method data_t firstResp()  if (finishInit);
      return readResp;
   endmethod
   
   method Action clear()  if (finishInit);
      noAction;
   endmethod
   
   // return the usage of each fifo at the beginning of the cycle
   method Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))) used()  if (finishInit);
      return usedReg;
   endmethod
   
   // return enq credit token available for each fifo
   method Vector#(no_fifo,Bit#(TLog#(TAdd#(fifo_sz,1)))) free()  if (finishInit);
      return freeReg;
   endmethod
   
   // get credit token to enq fifo idx in the future
   // this method is unguarded (i.e. user need to call method free 
   // and check for token availability before calling this action)
   method Action decrFree(Bit#(TLog#(no_fifo)) idx, Bit#(TLog#(TAdd#(fifo_sz,1))) amnt)  if (finishInit);
      decrFreeIdx <= tagged Valid idx;
   endmethod
   
endmodule