Data Organizer Documentation


Patrick Bryant and Yangyang Cheng





Table of Contents


  1. 1.Structural Overview

  2. Input Stream

  3. 2.Write Mode

  4. Animation

  5. 3.Read Mode

  6. Animation

  7. 4.Finite State Machine

5.Code Hierarchy






Structural Overview


    The purpose of the Data Organizer is most easily described in the following two pieces:

  1. Store the tracking data (hits in the pixel and SCT detectors) from an event while the Associative Memory Board (AMB) checks a massive bank (~4 million patterns) of corse grain track patterns called Roads for matches with the corse grain hit information called Super Strips (SSIDs). This step is called Write Mode.

  2. Retrieve the full resolution hit data for the matched RoadIDs coming from the AMB to be sent to the Track Fitter. This step is called Read Mode.


    In order for this process to be as fast and resource efficient as needed, the Data Organizer is designed around a highly parallel architecture and two copies of the DO are used so that one is always ready to receive new hits while the other is always ready to provide the hit data corresponding to roads.

    Each DO is composed of 11 functionally identical layers which independently store and retrieve hit information from 11 parallel data streams. There are 3 layers in the pixel (PIX) detector and 5 in the SCT. The DO further parallelizes the 3 PIX layers by splitting each stream in two so that there are 6 effective PIX layers which gives 11 layers. The PIX layers are split according to the lsb of the AMSSID, (even/odd AMSSID or 0/1 on SSID[3]). The data streams each contain two types of data:

  1. Hits are 32 bit words for the PIX layers and 16 bit words for the SCT layers which encode precise information about the physical location in the detector which interacted with a charged particle. An event will generally contain a few thousand hits.

  2. SSIDs are 14 bit words which label small regions of the detector layers. An SSID can correspond to a region of the detector with multiple hits. Up to 3lsb of the SSID can be ignored during Read Mode (Any SSIDs whose unignored bits match will be treated as the same SSID). The ignored bits are called Don’t Care (DC) bits. Ignoring these bits effectively increases the area covered by the SSID (when looking up the hits associated with an SSID, the SSIDs only need to match up to the DC bits) and can allow additional hits to be associated with it.  The 11msb of the SSID are called the AMSSID. I will refer to the 3lsb of the SSID as the MDC (maximal don’t care bits).


The data streams are synchronized and latched with logic called MidLatches (MLs) which are registers that set the output high when the latch request is set high. Inputs from the transceivers are identified as either Hits or SSIDs and then send to corresponding MLs. During Write Mode, Hits go to MLDATA, SSIDs to MLADD where they are synchronized and sent out in pairs on the next rising clock edge. During Read Mode, RoadIDs are sent through MLRDDATA to the Track Fitter and the AMMap. The SSIDs and DCFlags generated by the AMMap are latched by MLRDADD before arriving in the DO layers.


    Each layer contains three types of storage RAM:

  1. The Hit List Memory (HLM) is just a list of all the hits in an event. The hits are stored in the order in which they arrive. Hits arrive at the DO grouped by SSID, therefore hits with the same SSID are stored sequentially.

  2. The Hit List Pointer (HLP) stores the address of the first hit with a given SSID (base address). It is composed of 8 identical RAMs which are addressed by the AMSSID while the input data is the address of the HLM which is being written. Each RAM is mapped to a different value of the MDC bits. The RAM into which the base address is written corresponds to the MDC bits of the incoming SSID. During Read Mode this makes it possible to simultaneously read out the address of the first hit of all 8 SSIDs that could possibly correspond to a given AMSSID.

  3. The Hit Count Memory (HCM) stores the number of hits in a given SSID. Each time a hit/SSID pair arrives during Write Mode, the SSID is compared to the previous SSID. If it is the same, the hit count is incremented. The HCM is also built out of 8 identical RAMs which are each mapped to an MDC value. Their contents are addressed by the AMSSID and only the RAM which corresponds to the MDC value of the incoming SSID has its hit count incremented. During Read Mode this structure makes it possible to read out the hit count for all 8 SSIDs that could possibly correspond to a given AMSSID.


    The HCM and HLP make it possible to retrieve the hits that correspond to an SSID without the added complexity of a dictionary structure (which would be needed if the hits were not grouped by SSID).

    During Read Mode, when a RoadID arrives, a lookup is performed on an external memory to find the SSIDs and associated number of DC bits (called the DCFlag) which make up the given Road. This has to be done because it would take a huge bandwidth to transmit the SSIDs with the matched RoadIDs. Also, encoding the SSID information for each Road on the Associative Memory (AM) chips would take up space that can be used for patterns. The lookup is performed by the AMMap which outputs 11 SSID/DCFlag streams, one for each layer. It also outputs an 11 bit word called the hitmask which indicates which layers could have hits. The AMMap is stored on an external RAM physically located near the processor FPGAs on the board.

    Let DCFlag_int be the integer value of DCFlag. Then any hits which arrived with an SSID matching SSID[13..DCFlag_int] are retrieved and sent to the Track Fitter. There can be multiple hits in a layer for a given track candidate. The Track Fitter tries all of the combinations taking one hit from each of at least 7 of 8 layers.






Write Mode


    During write mode, Hits and their associated SSIDs arrive at the DO from the SSMap which is firmware that maps hits onto super strips. The hits arrive in groups of equal SSID and the Hits are written sequentially into the HLM. For each new hit a hit count is incremented and written into the one of eight HCM RAMs which corresponds to the MDC of the current SSID. When a new SSID arrives the hit count is set back to one and the process repeats. Meanwhile the current address of the HLM is written into the HLP RAM which corresponds to the MDC of the current SSID at the address AMSSID (if the SSID is not the same as the previous one).

    Because of timing limitations it is not possible to clear the DO memories between each event. To make up for this we keep track of which addresses in the HCM and HLP have been written in a given event with a single 2^11=2048 (2^10=1024 in the PIX layers because of the even/odd AMSSID splitting) bit word called DCReset (11 being the length an AMSSID in bits). This word is all zeros at the start of an event and DCReset at index AMSSID is set to 1 for each new AMSSID of an event. The value of DCReset is checked at index AMSSID for each new incoming SSID. If DCReset[AMSSID] == 0 then the HCM and HLP RAMs are zeroed at the address AMSSID (except for the RAMs which correspond to the MDC of the SSID which are written with HitCnt=1 and the BaseAddr respectively) and DCReset[AMSSID] => 1. If DCReset[AMSSID] == 1 then the HitCnt for RAM corresponding to the MDC of the SSID is set to 1 (since DCReset is only checked for new SSIDs and the hits arrive grouped by SSID meaning it must be the first hit for that SSID).


Summary

  1. DCReset

  2. 2^11 bits (2^10 bits in the PIX layers since they were previously split by even/odd AMSSID; there are half as many addresses in the PIX layers), each bit corresponds to an AMSSID which is an address in the HCM.

  3. All bits set to 0 at the beginning of each event

  4. When a new AMSSID arrives, DCReset[AMSSID] is checked. If it is 0 it is set to 1 on the next clock edge

  5. Ensures HCM addresses are only cleared at most once per event and allows the other addresses to not be cleared which would take time

  6. AMSSID

  7. Set to SSID[13..3] for each incoming SSID

  8. AMSS_index is the integer value of AMSSID and is used to check DCReset

  9. MDC

  10. Set to SSID[2..0] and used to select the RAM in the HCM and HLP effectively allowing for an 8 port RAM structure

  11. DC_Index is the integer value of MDC


  1. HLCtrl_WR (Hit List Control Write)

  2. Control logic which compares the incoming SSID (WR_tempSSID) to the previous SSID (WR_savedSSID)

  3. -If WR_tempSSID==WR_savedSSID => increment HitCnt do not write BaseAddr

  4. -If WR_tempSSID/=WR_savedSSID => New SSID, reset HitCnt to 1 and write new BaseAddr to HLP[DC_Index]

  5. Compares incoming AMSSID (WR_tempAMSSID) to previous AMSSID (WR_savedAMSSID)

  6. -If WR_tempAMSSID==WR_savedAMSSID => write TempHitCnt to HCM[DC_Index]

  7. -If WR_tempAMSSID/=WR_savedAMSSID => Check DCReset[AMSS_Index]

  8. If DCReset[AMSS_Index]==0 => reset all 8 RAMs in HCM at addr=AMSSID and write TempHitCnt (which should be 1) to HCM[DC_Index]

  9. If DCReset[AMSS_Index]==1 => Write TempHitCnt (which should be 1) to HCM[DC_Index]


Here is a step by step animation of the data flow in Write Mode for a toy event with 4 hits and 3 SSIDs, two have the same full SSID and two have the same AMSSID but not the same MDC. There is also an animation of Read Mode.






Read Mode


    Prior to the start of Read Mode, the SSIDs for the event are passed through the AMB which checks ~4 million patterns for matches. The matched patterns called Roads are identified by 22 bit words called RoadIDs. Roads are a set of SSIDs, one for each layer. The SSIDs for a layer of a Road are the same except for up to 3 lsb called Don’t Care (DC) bits. The RoadIDs enter the AMMap which looks up the SSIDs and the number of DC bits (DCFlag) for each layer in the Road. The road stream also contains an 8 bit word called the BitMask which is used to signal if a layer is used in the Road. The 3 PIX layers are split by even/odd AMSSID and an 11 bit word called the HitMask is generated from the BitMask.  For each layer (if the HitMask bit corresponding to the layer is 1) the SSIDs and DCFlags from that layer are passed into the DOLayer and used to look up any hits that are in the Road.

    This is done in a few steps. First two things happen simultaneously:

                The 8 HCM and HLP RAMs are read out at the address corresponding to the incoming

            AMSSID (keep in mind that these SSIDs are not necessarily the same as the SSIDs

            which arrived during Write Mode)

                An 8 bit word called the DCIndex (not the same as DC_Index, I would suggest changing

            DC_Index to MDC_int and DCIndex to MDC_mask) is generated from the DCFlag.

            DCIndex is used to identify possible values for MDC which can have hits. The

            possible values of MDC are the ones which match SSID[2..DCFlag] (if DCFlag is 3, this is

            an empty set so all 8 values of MDC are possible)

    Next, DCIndex is used to check the output of the HCM and HLP. Starting at MDC=000 and stepping up to MDC=111, if the HitCnt is not zero and DCIndex is 1, then the HitCnt and BaseAddr for that MDC value are written into one of a set of 8 FIFOs called FIFOSS0...FIFOSS7. The first valid HitInfo (HitCnt and BaseAddr pair) that is found is written to FIFOSS0, the next is written to FIFOSS1 etc. The number number of valid sets of HitInfo is written to FIFOIndex. This processes is repeated for each incoming Road.

    When FIFOIndex is not empty, it is popped and the value is used to pop the corresponding number of FIFOSSs starting at FIFOSS0. The popped HitInfo is written onto a register called BaseAddr&HitCnt. When BaseAddr&HitCnt is not empty the HLM is read starting at the BaseAddr which is then incremented HitCnt times. When this is done, the next FIFOSS is popped onto the BaseAddr&HitCnt register. When the last FIFOSS for that FIFOIndex value is popped, the next FIFOIndex is popped and the process repeats. The hits are written into a FIFO that can be popped at the request of the Track Fitter.


Summary

  1. HitMask

  2. 11 bit word identifying layers that should be checked for hits in the given Road.

  3. Generated from the 8 bit BitMask (which is sent to the AMMap in the Road stream) by checking if the AMSSIDs in the initial 3 PIX layers are even or odd. The PIX SSID streams are split according to this and the 3 bits of the BitMask are also split into 6 bits.

  4. DCFlag

  5. 2 bit word whose integer value is the number of bits in the SSID generated by the AMMap which do not have to match the SSIDs of the Hits

  6. Int(DCFlag)=DCCnt

  7. DCCombNum=2^DCCnt

  8. DCIndex

  9. 8 bits, each bit corresponds to an MDC value which is included in the given layer of the road. Calculated as follows:

  10. -DCIndex=”00000000”

  11. -DCCombNum=2^int(DCFlag)

  12. -For i in range 0 to DCCombNum-1:

  13. -    if DCFlag = “00” => tempDCComb(2..0)=SSID(2..0)

  14. -    if DCFlag = “01” => tempDCComb(2..0)=SSID(2..1)+binary(i)

  15. -    if DCFlag = “01” => tempDCComb(2..0)=SSID(2..2)+binary(i)

  16. -    if DCFlag = “01” => tempDCComb(2..0)=                   binary(i)

  17. -    DCIndex(int(tempDCindex))=1

  18. AMSSID

  19. Set to SSID[13..3] for each incoming SSID

  20. AMSS_index is the integer value of AMSSID and is used to check DCReset

  21. MDC

  22. Set to SSID[2..0] and used to select the RAM in the HCM and HLP effectively allowing for an 8 port RAM structure

  23. DC_Index is the integer value of MDC


  1. HLCtrl_RD (Hit List Control Read)

  2. Generates the DCIndex as shown above

  3. -Checks the 8 HCM outputs against the DCIndex for nonzero HitCnt at MDC locations where DCIndex is 1

  4. -Writes corresponding HitCnt and BaseAddr values to one of 8 FIFOSSs. FIFOSS1 for the first valid hitinfo, FIFOSS2 for the second valid hitinfo etc.

  5. Calculates the number of MDC locations which have hits and DCIndex is high. This number is written to FIFOIndex which is used to pop only the FIFOSSs which have hitinfo. (Saves time because only rarely will more than 2 FIFOSSs be used)


Here is a step by step animation of the data flow in Read Mode for a toy event with 4 hits and 3 SSIDs, two have the same full SSID and two have the same AMSSID but not the same MDC. It is the same event in the Write Mode animation.






Finite State Machine


    There are two types of Finite State Machines (FSMs) that control the state of the data organizer logic. The highest level is the FSM which switches the two DO copies between read and write mode. DO1 starts in state_write and DO2 starts in state_read. Next there are 11 copies of the same FSM for each copy of the DO. These state machines independently control each layer of the DO and they have six possible states:

  1. state_writeready

  2. ready to write new hit information

  3. switch to state_writenew when all layers are in state_writeready and hits have arrived in the input FIFOs and the other DO copy is in state_readready

  4. state_writenew

  5. fetching hits from input FIFOs

  6. switch to state_writewait when end of event word arrives from input FIFOs

  7. state_writewait

  8. finish writing in hits received from input FIFOs

  9. stop fetching new hits

  10. switch to state_readready when last hit has been written into HLM

  11. state_readready

  12. ready to receive roads and look up hitinfo

  13. switch to state_readnew when all layers are in readready and roads have arrived in input FIFOs and the other DO copy is in state_writeready

  14. state_readnew

  15. fetching roads from input FIFOs

  16. switch to state_readwait when end of event word arrives from road stream

  17. state_readwait

  18. reading out hits from last road in event

  19. stop fetching new roads

  20. switch to state_writeready when the last hit from the last road has been read out






Code Hierarchy


            Key:

            entity : instance : layers : array of layers


  1. DoubleDataOrganizer : inst129

  2. DO11L : b2v_DO1

  3. DO11L : b2v_DO2

        HLCTRL_RD

  1. hlcreadpix  : \HitListCtrlRDPIX  : 0..5 : Top_HitListControlRDPIX

  2. hlcreadsct  : \HitListCtrlRDSCT  : 0..4 : Top_HitListControlRDSCT

        HLCTRL_WR

  1. hlcwritepix : \HitListCtrlWRPix  : 0..5 : Top_HitListControlWRPix

  2. hlcwritesct : \HitListCtrlWRSCT  : 0..4 : Top_HitListControlWRSCT

        HCM, HLP, HLM

  1. hcmpixlayer : \HitCountMemPix    : 0..5 : Top_HitCountMemPix

  2. HCMPIX : hcmpix8times : 0..8 : hcmpixsingle

  3. hcmsctlayer : \HitCountMemSCT    : 0..5 : Top_HitCountMemSCT

  4. HCMSCT : hcmsct8times : 0..8 : hcmsctsingle

  5. hlppixlayer : \HitListPointerPix : 0..5 : Top_hitListPointerPIX

  6. HLPPIX : hlppix8times : 0..8 : hlppixsingle

  7. hlpsctlayer : \HitListPointerSCT : 0..4 : Top_hitListPointerSCT

  8. HLPSCT : hlpsct8times : 0..8 : hlpsctsingle

  9. HLMPIX      : \HitListMemPix     : 0..5 : Top_HitListMemPIX

  10. HLMSCT      : \HitListMemSCT     : 0..4 : Top_HitListMemSCT

        MLatches

  1. MLAdd     : \MLADD11L    : 0..10 : Top_MLADD

  2. MLPIXData : \MLPIXData6L : 0..5  : Top_MLPIXDATA

  3. MLSCTData : \MLSCTData5L : 0..4  : Top_MLSCTDATA

  4. MLRDAdd   : \MLRDADD11L  : 0..10 : Top_MLRDADD

     FSMs

  1. fsmdoubleDO : b2v_inst3

  2. fsm11L : DO1FSM

  3. fsm11L : DO2FSM

  4. fsmsingleL : \DOFSM11L : 0..10 : DOFSMSingleL