5NP4G
Tree Search Engine
Table 8-17. LUDefTable Entry Definitions (Page 4 of 4)
Field
Bit Length
Description
RopePLA
LeafCnt
26
26
Previous leaf address for rope
Number of leaves in tree
Threshold for the number of leaves in a tree. If the LeafCnt is greater than or equal to this
assigned threshold, then a class 0 interrupt is generated (bit 9 of the class 0 interrupt vec-
tor). Checking of the threshold is performed only for the TLIR rope command.
The threshold is formed by the generation of two 26-bit numbers that are bit-wise ORed
resulting in a threshold value that is compared to the LeafCnt:
LeafTh
10
threshold(25:0) = 2**(LeafTh(9:5))or 2**(LeafTh(4:0))
8.2.5.2 TSE Free Lists (TSE_FL)
The GTH has access to a set of 64 TSE free list control blocks, each defining a free list using the format
shown in Table 8-18. Free lists typically chain unused PSCBs and leaves into a linked list, but can also be
used by picocode to manage memory. The link pointer is stored in the control store at the address of the
previous list object. Objects stored in different memories and with different shapes should be placed in
different free lists. For example, a list of 64-bit PSCBs stored in both ZBT SRAM and internal RAM should
have different entries. The GTH thread executes the TSENQFL and TSDQFL commands to enqueue and
dequeue addresses on a free list. See Section 8.2.8.3 Tree Search Enqueue Free List (TSENQFL) on page
373 and Section 8.2.8.4 Tree Search Dequeue Free List (TSDQFL) on page 374.
A free list of N objects, each with shape of width = W, height = H and a start address of “A”, is created by
enqueueing address A, A+H, A+2H, A+3H, … A+(N-1)H in the free list. To prevent memory bottlenecks, free
lists can also be created in a “sprayed” manner for objects contained in SDRAM. For example, when
searching a large LPM tree with five PSCBs in a single bank, the bank must be accessed five times before
reaching a leaf. When the PSCBs are sprayed among multiple banks, the number of accesses remains iden-
tical but accesses are to multiple banks, thus eliminating bottlenecks.
Table 8-18. Free List Entry Definition
Field
Head
Tail
Bit Length
Description
Free list head address in the control store.
26
26
26
Free list tail address in the control store.
Number of entries in the free list.
QCnt
Threshold value for the free list control block entry. This field is initialized to 0. The
threshold is determined as 2**Threshold. When the QCnt is less than or equal to
the threshold, a Class 0 interrupt (bit 8) is generated.
Threshold
5
5NP4G Network Processor, Data Sheet, DS-0125-02
January 2006
Tree Search Engine
Page 343 of 607