本发明的实施例涉及通过互联网络的适当配置使用共享存储器池的多个并联查找。为每个查找保留的共享存储器的数目可基于该查找所需的存储器能力而重配置。共享存储器被分组为同质块。基于该查找所需的存储器能力，每个查找被分派一组块。为每个查找分派的块不与其他查找重叠，以便所有查找能并行执行而不冲突。每个查找可重配置为基于哈希或直接访问。基于怎样为每个查找分派块，对互联网络进行编程。
1.一种片上系统，配置为使用共享存储器池支持N个并行查找，所述片上系统包括：T×M个共享存储器池，被分组为T个块；
用于N个查找路径中的每个查找路径的M个索引转换器；
中央可重配置互联结构，用于将N个输入端口连接到所述T个块；
输出可重配置互联结构，用于将所述T个块连接到N个输出端口；和N个输出结果收集器，其中所述N个输出结果收集器每个是每一个查找路径，其中，所述片上系统被配置为沿着N个查找路径相对于所述T×M个共享存储器池来执行N个并行查找，其中N，T和M是正整数值。
2.根据权利要求1所述的片上系统，其中所述T个块基于每个查找路径所需的存储能力而被分区并分派给所述查找路径。
3.根据权利要求1所述的片上系统，其中为所述N个查找路径中的每个查找路径分派的块的数目为2的幂，并且块不能在分区之间重叠。
4.根据权利要求1所述的片上系统，其中所述T个块的每一个包括：M个存储器，用于支持D-LEFT查找，其中每个查找有M路；
匹配区块，用于比较M个存储器中的预编程密钥与输入密钥；和选择区块，用于为该块选择命中结果，其中N，T和M是正整数值。
5.根据权利要求1所述的片上系统，其中所述共享存储器的每一个具有2m个条目，其中所述条目的每一个含有P对可编程{密钥,数据}，用于以每路P桶支持D-LEFT查找，其中P，N，T，m和M是正整数值。
6.根据权利要求1所述的片上系统，其中每个查找路径可配置为基于哈希的查找或直接访问查找。
7.根据权利要求1所述的片上系统，其中所述N个查找路径中的每个查找路径的M个索引转换器的索引转换器i被用于在分派给该查找路径的所述T个块的一个中访问存储器i。
8.根据权利要求1所述的片上系统，其中所述N个查找路径中的每个查找路径的M个索引转换器的每一个基于为所述N个查找路径中的该查找路径分派的多个块可配置。
9.根据权利要求1所述的片上系统，其中每个查找路径的M个索引转换器每个还包括：log2(T)+1个哈希函数和log2(T)+1个非哈希函数，其中函数的输出的位宽的范围从m位到log2(T)+m位；
第二可配置寄存器，用于选择块偏移，以便查找索引指向该查找路径的所分派块中正确的块，其中所述所分派的块从所述T个块中选择，其中m，N，T和M是正整数值。
10.根据权利要求1所述的片上系统，其中所述M个索引转换器的每一个的输出索引具有log2(T)+m位，其中所述输出索引中的所述log2(T)个最高有效位被用于指向所述T个块的一个，并且所述输出索引中的所述m个最低有效位被用作存储器读取地址，其中m，N，T和M是正整数值。
11.根据权利要求1所述的片上系统，其中所述中央可重配置互联结构包括M个可配置的N×T网络。
12.根据权利要求11所述的片上系统，其中所述N×T网络每个是交叉开关和可配置蝶形开关中的一个。
13.根据权利要求1所述的片上系统，其中所述输出可重配置互联结构包括T个可配置的1×N去多路复用器。
14.根据权利要求1所述的片上系统，其中与所述N个查找路径中的查找路径关联的N个输出结果收集器的一个被配置为从为所述查找路径分派的块收集结果，并且被配置为从由所述分派的块输出的结果选择一个最终结果。
15.根据权利要求1所述的片上系统，其中用于所述T个块的每个块的命中结果基于在该块的存储器中的预编程密钥和该块的输入密钥之间的密钥匹配结果。
16.一种使用共享存储器池执行N个并行查找的方法：
将T个块分区为N组，其中所述T个块每个包括M个存储器，并且其中N个查找路径的每个与输入端口和输出端口关联，并且其中N个查找路径每个分配给所述N组的一个；和执行所述N个并行查找，包括：为N个输入密钥的每个：
将所述输入密钥转换为多个查找索引，其中所述多个查找索引每个包括由各个查找路径访问的所述N组的一个中的特定块的块ID，并且也包括将从中读取数据的所述特定块中的存储器的存储器地址；
通过使用来自所述特定块的匹配信息的收集确定返回哪个命中信息；和通过使用来自由所述多个查找索引指示的那些块的命中信息的收集，确定针对与所述输入密钥关联的查找路径返回哪个最终查找结果。
17.根据权利要求16所述的方法，其中在确定哪个命中信息从所述特定块返回中，将最高优先级给予该特定块中的存储器，所述存储器具有在该特定块中的所有存储器中最低的存储器ID。
18.根据权利要求16所述的方法，其中所述命中信息包括与匹配密钥相对应的命中数据和所述命中数据的位置，其中所述命中数据的所述位置包括存储器ID、与所述存储器ID关联的存储器的地址和在所述存储器中的所述命中数据的位置。
19.根据权利要求16所述的方法，其中在确定为查找路径返回哪个最终查找结果中，将最高优先级给予在为所述查找路径分派的所有块中具有最低块ID的块。
20.根据权利要求19所述的方法，其中所述最终查找结果包括命中数据、含有所述命中数据的块的块ID和读取所述命中数据的存储器地址。
21.根据权利要求16所述的方法，在执行所述N个并行查找之前，还包括：为每个查找路径计算哈希尺寸；
为哈希选择生成配置位并且为每个查找路径生成块偏移；
22.根据权利要求21所述的方法，其中用于为每个查找路径编程所述存储器的技术基于具有M路和P桶的D-LEFT查找技术。
23.一种转换器件，被配置为支持N个并行密钥到查找索引转换，包括：在所述转换器接收到的N个密钥，其中所述N个密钥的每个与来自T个块的块组关联，其中所述T个块每个包括M个存储器；
N×M个查找索引，其在所述N个密钥并行转换为所述N×M个查找索引之后从所述转换器返回；和N×M个转换器，其中所述N×M个转换器每个被配置为将来自所述N个密钥的密钥转换为来自所述N×M个查找索引的查找索引，并且包括：log2(T)+1个哈希函数和log2(T)+1个非哈希函数，其中函数的输出的位宽范围从m位到log2(T)+m位；
第二可配置寄存器，用于选择块偏移，以便所述查找索引指向来自与所述密钥关联的所述块组的正确的块。
24.根据权利要求23所述的转换器件，其中所述N×M个查找索引被转发到中央可重配置互联结构，其中所述中央可重配置互联结构被配置为将所述N×M个查找索引的每个连接到T个块的一个，用于将所述密钥与该块中存储的预编程密钥相比较。
M个存储器，其中所述M个存储器每个包括2m个条目，其中每个所述条目含有P对可编程{密钥，数据}，并且m是正整数值；和匹配和选择逻辑，被配置为接收输入密钥并输出查找结果，其中所述匹配和选择逻辑包括：匹配区块，被配置为确定所述输入密钥是否匹配所述M个存储器中的任何预编程密钥；
选择区块，被配置为从所述M个存储器的含有与所述输入密钥匹配的所述预编程密钥的那些存储器中选择存储器，其中所述选择的存储器具有在那些存储器中最低的存储器ID，其中所述查找结果包括与所述预编程密钥配对的预编程数据。
26.根据权利要求25所述的块器件，其中所述查找结果还包括存储器ID和存储所述预编程数据的存储器地址。
27.根据权利要求25所述的块器件，其中所述查找结果被转发到输出重配置互联结构，其中所述输出重配置互联结构被配置为将T个块的每个块连接到用于N个查找路径的N个最终输出选择器件的一个。
28.根据权利要求27所述的块器件，其中所述N个最终输出选择器件每个包括：收集区块，被配置为从保留各个查找路径的所有块接收查找结果；和选择区块，被配置为从由所述收集区块收集的所有查找结果中选择一个最终查找结果，其中所述选择的最终查找结果来自具有最低块ID的命中块。
29.根据权利要求27所述的块器件，其中所述选择的最终查找结果包括命中数据、块ID、存储器ID和存储所述命中数据的存储器地址。
用于使用多个共享存储器可重配置并行查找的方法和系统
技术领域
[0001] 本发明涉及使用共享存储器池的多个并行查找。更尤其地，本发明涉及用于使用多个共享存储器可重配置并行查找的方法和系统。
背景技术
[0002] 在网络处理器中，存在许多应用，这些应用需要快速查找，诸如每流状态管理、IP查找和包分类。能够使用几种技术实现查找系统，诸如基于TCAM、基于哈希和直接访问查找。基于哈希的查找技术和直接访问查找技术具有较低的存储成本，并且比基于TCAM查找技术更快。现有技术的基于哈希的查找技术是基于D-LEFT哈希查找方案，因为其在使用存储器时效率高。然而，在使用这些查找技术的现有技术的查找系统中，用于每个查找的存储器的数目是固定的。这种不灵活性禁止在系统制造后对每个查找的存储量的任何改变。此外，现有技术的查找系统不能从一种查找技术变为另一种查找技术，诸如从基于哈希到诸如直接访问，以实现100％存储器利用，而100％存储器利用能够在包括精确匹配查找的应用中有用。
发明内容
[0003] 片上系统支持共享一个存储器池的多个并行查找。保留给每个查找的存储器的数目可基于该查找所需的存储器的量重配置。此外，每个查找能够被配置为实行为基于哈希查找或直接访问查找。共享存储器被分组成同质块。每个查找被分派一组块。该组中的块与其他组共享，以便所有查找能并行实行，而不冲突。系统也包括可重配置连接网络，其基于怎样为每个查找分派块来编程。
[0004] 在一个方面，提供了片上系统，其被配置为使用共享存储器池支持N个并行查找。片上系统包括T×M个共享存储器，其被分组为T个块、用于每个查找路径的M索引转换器、用于将N个输入端口连接到T个块的中心可重配置互联结构、用于将T个块连接到N个输出端口的输出可重配置相互联接结构、和N个输出结果收集器。N个输出结果收集器的每个为每个查找路径。
[0005] 在一些实施例中，T个块被分区并基于每个查找路径所需的存储器量被分派给查找路径。被分派给每个查找路径的块的数目为2的幂。块在分区间重叠。
[0006] 在一些实施例中，T个块的每个都包括用于以每查找M个路径支持D-LEFT查找的M个存储器、用于比较M个存储器中的预编程密钥和输入密钥的匹配区块、和用于为块选择命中结果的选择区块。
[0007] 在一些实施例中，每个共享存储器都具有2m个条目。每个条目容纳用于以每路P个桶支持D-LEFT查找的P对可编程密钥{密钥，数据}。
[0008] 在一些实施例中，每个查找路径可配置为基于哈希查找或直接访问查找。
[0009] 在一些实施例中，每个查找路径的M个索引转换器的索引转换器i被用于访问在为该查找路径分派的T个块的一个中的存储器i。
[0010] 在一些实施例中，每个查找路径的M个索引转换器的每个可基于分派给该查找路径的块的数目配置。
[0011] 在一些实施例中，每个查找路径的M个索引转换器每个都进一步包括log2(T)+l哈希函数和log2(T)+1非哈希函数，其中该函数的输出具有从m位到log2(T)+m位的位宽度、用于选择一个函数的第一可配置寄存器、和用于选择块偏移的第二可配置寄存器，以便查找索引指向该查找路径的所分派块中的正确块，其中分派的块从T个块中选择。
[0012] 在一些实施例中，M个索引转换器的每个的输出索引具有log2(T)+m位。在输出索引中log2(T)最高有效的位被用于指向T个块的一个，并且输出索引中m个最不高有效的位被用作存储器读取地址。
[0013] 在一些实施例中，中央可重配置互联结构包括M个可配置的N×T网络。N×T网络的每个都能够是交叉开关(crossbar)或可配置蝶形开关。
[0014] 在一些实施例中，输出可配置互联结构包括M个可配置的I×N去多路复用器。
[0015] 在一些实施例中，与查找路径关联的N个输出结果收集器的一个被配置为从用于查找路径的分派块收集结果，并且被配置为从由分派的块输出的结果中选择一个最终结果。
[0016] 在一些实施例中，用于T个块的每个的命中结果给予匹配该块的草丛中的预编程密钥和该块的输入密钥之间的结果的密钥。
[0017] 在另一个方面，提供了使用共享存储器池实行N个并行查找的方法。该方法包括将T个块分区为N组。T个块的每个都包括M个存储器。每个查找路径与输入端口和输出端口关联。N个查找路径的每个都被分派到N个组中的一组。该方法也包括执行N个并行查找。
[0018] N个并行查找的执行对于每个TV输入密钥包括(1)将输入密钥转换为多个查找索引，其中多个查找索引的每个都包括在由各自查找路径访问的N个组的一组中的特定块的块ID，并且也包括将从其读取数据的特定块中的存储器的存储器地址，(2)通过使用许多匹配信息从命中返回信息的特定块确定，和(3)通过使用许多命中信息，从由最终查找结果为与输入密钥关联的查找路径返回的多个查找索引所指示的块确定。
[0019] 在一些实施例中，在确定从特定块返回的命中信息中，最高优先级给定在该特定块中的存储器，该特定块在这些特定块中的所有存储器中具有最低存储器ID。在一些实施例中，该命中信息包括命中数据和相应于匹配密钥的命中数据的位置。命中数据的位置包括存储器TD、与存储器ID关联的存储器的地址、和存储器中命中数据的位置。
[0020] 在一些实施例中，在确定为查找路径返回的最终查找结果中，最高优先级给定在为查找路径分派的所有块中的块ID最低的块。在一些实施例中，最终查找结果包括命中数据、容纳命中数据的块的块ID、存储器ID和读取命中数据的存储器地址。
[0021] 在一些实施例中，该方法也包括，在执行N个并行查找之前，为每个查找路径计算哈希尺寸、为哈希选择生成配置位，并为每个查找路径生成块偏移、配置连接查找路径和块的网络、和为每个查找路径编程存储器。在一些实施例中，用于为每个查找路径编程存储器的技术基于具有M个路和P个桶的D-LEFT查找技术。
[0022] 在还另一个方面，提供了转换器件，其被配置为支持N个并行密钥-到-查找索引转换。该转换器件包括在转换器接收的N个密钥。N个密钥的每个都与来自T个块的块组关联。T个块的每个都包括M个存储器。
[0023] 转换器件也包括N×M个查找索引，以在N个密钥到N×M个查找索引的并行转换之后，从转换器返回。
[0024] 转换器件也包括N×M个转换器。N×M个转换器每个都被配置为将来自N个密钥的密钥转换为来自N×M个查找索引的查找索引。N×M个转换器每个都包括log2(T)+l哈希函数和log2(T)+1非哈希函数，其中该函数的输出具有从m位到log2(T)+m位的位宽度、用于选择一个函数的第一可配置寄存器、和用于选择块偏移的第二可配置寄存器，以便查找索引指向来自与该密钥关联的块组的正确块。
[0025] 在一些实施例中，N×M个查找索引传送到中央重配置互联结构。中央重配置互联结构被配置为将N×M个查找索引连接到T个块的一个，用于比较该密钥与该块中保存的预编程密钥。
[0026] 在还另一个方面，提供了块器件。块器件包括M个存储器。M个存储器的每个都包括2m条目。每个条目都容纳P对可编程{密钥，数据}。
[0027] 块器件也包括匹配和选择逻辑，其被配置为接收输入密钥并输出查找结果。匹配和选择逻辑包括匹配区块和选择区块，匹配区块被配置为确定输入密钥是否匹配M个存储器中任何预编程密钥，并且选择区块被配置为从容纳与输入密钥匹配的预编程密钥的M个存储器的这些存储器的存储器。选择的存储器在这些存储器中具有最低存储器ID。查找结果包括与预编程密钥配套的预编程数据。该查找结果也包括存储器ID和存储预编程数据的存储器地址。
[0028] 在一输出些实施例中，查找结果传送到输出重配置互联结构。输出重配置互联结构被配置为将T个块的每个都连接到用于N个查找路径的N个最终输出选择器件的一个。在一些实施例中，N个最终输出选择器件每个都包括收集区块和选择区块，收集区块被配置为从各自查找路径保留的所有块接收查找结果，并且选择区块被配置为从由收集区块收集的所有查找结果选择一个最终查找结果，其中选择的最终查找结果来自具有最低块ID的命中块。选择的最终查找结果包括命中数据、块ID、存储器ID和存储命中数据的存储器地址。
附图说明
[0029] 图1示出根据本发明的实施例的并行查找系统。
[0030] 图2示出根据本发明的实施例的共享存储器的示例性分组的图表。
[0031] 图3示出根据本发明的实施例的用于查找路径的共享块(tile)的示例性分派的图表。
[0032] 图4示出根据本发明的实施例的密钥-到-查找索引转换器。
[0033] 图5示出根据本发明的实施例的索引转换器。
[0034] 图6示出根据本发明的实施例的中央可重配置的互联结构。
[0035] 图7示出根据本发明的实施例在块内的存储器的格式。
[0036] 图8示出根据本发明的实施例的示例性块的示意图。
[0037] 图9示出根据本发明的实施例在选择区块中选择命中结果的方法。
[0038] 图10示出根据本发明的实施例的输出可重配置互联结构。
[0039] 图11示出根据本发明的实施例在结果收集器中选择命中结果的方法。
[0040] 图12示出根据本发明的实施例的配置和编程并行查找系统的方法。
[0041] 如附图中所说明的，上文从本发明的实例实施例的下列更特定描述中将显而易见，在附图中贯穿不同视图，同样的附图标记指代相同的部分。附图不需要按比例，而是将重点放在说明本发明的实施例上。
具体实施方式
[0042] 在下列描述中，为了解释的目的阐述了许多细节。然而，本领域普通技术人员将认识到，能够实践本发明而无需使用这些具体细节。因此，本发明不是意图被限制于所示的实施例，而是符合与本文中所述的原理和特征一致的最宽的保护范围。
[0043] 片上系统支持共享一个存储器池的多个并行查找。为每个查找保留的存储器的数目可基于该查找所需的存储器能力而重配置。此外，每个查找能够被配置为实行为基于哈希查找或直接访问查找。共享存储器被集合成同质块。每个查找被分派一组块。该组中的块不与其他组共享，以便所有查找能并行实行而不冲突。系统也包括可重配置连接网络，其基于怎样为每个查找分派块来编程。
[0044] 图1示出根据本发明的实施例的并行查找系统100。系统100被配置为用于使用多个共享存储器的N个同时或并行查找路径，而无冲突。该系统100为每个查找路径的每个k位输入密钥返回n位数据。该系统100包括区块105-130，在详细讨论其各自特征之前首先一般地讨论每个区块。
[0045] 在区块115的共享存储器的池被分组为T个共享同质块。每个块含有M个存储器。每个查找路径被分派来自这些T个块的多个块。为每个查找路径的块分派通常可由软件重配置。
[0046] 在区块105，每个查找路径的输入密钥转换为多个查找索引。用于读取查找数据的信息，诸如查找路径将访问的各个块的块ID以及在将从中读取数据的这些块中的存储器的地址，变为查找索引的一部分。
[0047] 块ID和每个输入密钥的存储器地址通过区块110被发送给相应的块，区块110为中央可重配置互联结构(fabric)。中央可重配置互联结构110包括多个可配置中央网络。这些中央网络通常基于为各个查找路径保留的块的位置来配置。
[0048] 在每个块中，在区块120，在先前已经从相应输入密钥转换的地址(例如，在区块110的转换)从存储器读取预编程密钥和数据。位于存储器中的这些预编程密钥与用于各个查找路径的输入密钥相比较。如果在具有输入密钥的这些预编程密钥中存在任何匹配，那么块返回命中数据和命中地址。
[0049] 每个块的命中信息由各个查找路径收集，这些查找路径通过区块125拥有该块，该区块125为输出可重配置互联网络。在为查找路径返回最终查找结果之前，每个查找路径在区块130拥有的所有块的命中信息中执行另一轮选择。
[0050] 图2示出根据本发明的实施例的共享存储器200的示例性分组的图表。图表示出在使用块205的并行查找系统中，诸如图1中的并行查找系统100，共享存储器的组织。共享存储器被分组为T个共享同质块205。每个块205含有M个存储器，其用于以在区块215用M个路径支持D-LEFT查找。因此，并行查找系统100具有总共T×M个存储器。每个块205都具有用于识别并行查找系统100中的块的TileID。每个块205内的存储器210都与从0到M-1的存储器ID关联，存储器ID用于识别在该块205中的存储器210。
[0051] 在执行查找之前，每个查找路径被分派来自共享块的一组连续块。分派给每个查找路径的块的数目为2的幂，并且其取决于该查找路径所需的存储能力。允许在任何两个查找路径之间不存在块重叠。在示例性方案中假设，并行查找系统100具有八个块和四个并行查找路径。用于这些查找路径的块分区能够为{8,0,0,0}或{4,4,0,0}或{4,2,2,0}或{4,2,1,1}或{2,2,2,2}或对这些分区的一个的任何变更。这个示例性的方案将不断被提及并基于其说明并行查找系统100。
[0052] 图3示出根据本发明的实施例的用于查找路径300的共享块的示例性分派的图表。继续参照具有八个块和四个并行查找路径的并行查找系统100的示例性方案，八个块被分区305如下：{4,1,2,1}。基于这个分区实例，查找路径0被分派四个块(尤其是，块0,1,2和
3)，查找路径1被分派一个块(尤其，块4)，查找路径2被分派两个块(尤其，块5和6)而查找路径三被分派一个块(尤其，块7)。
[0053] 在为每个查找路径分派一组块之后，用于每个查找路径的输入密钥在图1的区块105被转换为多个查找索引。查找索引被用于为各个查找路径访问所分派的块。用于每个密钥的每个查找索引具有log2(T)+m个位。查找索引的log2(T)个最高有效位(MSB)被用于TileID，并且查找索引的m个最不高有效位(LSB)用于存储器读取地址。TileID指向用于相应查找路径的分派块的一个，而存储器读取地址为从中读取数据的该块内的存储器的地址。继续参照具有八个块和四个并行查找路径的并行查找系统100的示例性方案，假设每个块中的每个存储器为1k条目宽度。由于每个TileID为3位宽并且每个存储器读取地址为10位宽，那么每个查找索引为13位宽。
[0054] 由于在块(即，M)中存在存储器，每个查找路径通常配备相同数目的索引转换器。图4示出根据本发明的实施例的密钥-到-查找索引转换器400。在一些实施例中，图1的区块
105同样被配置如密钥到查找索引转换器400那样。每个查找路径的每个输入密钥被发送给所有其M个索引转换器405。因此，为每个查找路径的每个输入密钥获得M个查找索引。通过使用TileID的值，每个查找索引能够在用于相应查找路径的分派块中访问任何块，但是查找索引i只能够访问块中的存储器i，下面进一步讨论。
[0055] 每个索引转换器405都包括一组哈希函数。如果并行查找系统具有T个块，那么每个索引转换器405都具有1og2(T)+1个哈希函数。这些哈希函数的输出的位宽从m位到log2(T)+m个位。哈希大小指哈希函数的位宽。基于为查找路径保留的块的数目，为每个查找路径选择的哈希大小可重配置。如果查找路径分派q个块，那么为查找路径选择的用于每个索引转换器的哈希大小为m+log2(q)。继续参照具有八个块的并行查找系统100的示例性方案，每个索引转换器都具有log2(8)+l＝4(四个)哈希函数。
[0056] 图5示出根据本发明的实施例的索引转换器500。在一些实施例中，图4的索引转换器405类似地被配置为如索引转换器500那样。继续参照示例性方案，假设每个块中的存储器地址为10位宽。四个哈希函数的哈希大小分别为10、11、12和13，(10到log2(8)+10)，因为这个示例性方案中的系统具有八个块。因为哈希大小不一致，零位在这些四个哈希函数的输出的前缀连接(concatenate)，以便每个输出为13位宽。
[0057] 可重配置cfg_hash_sel寄存器能够用于为每个查找路径选择哈希函数。在图5中，如果查找路径分派一个块，那么选择10位哈希函数(log2(1)+10＝10)。如果查找分派两个块，那么选择11位哈希函数(log2(2)+10＝11)。如果查找路径分派四个块，那么选择12位哈希函数(log2(4)+10＝12)。如果查找分派八个块，那么选择13位哈希函数(log2(8)+10＝13)。
[0058] 类似地，cfg_hash_sel寄存器能够用于为每个查找路径选择非哈希函数。尤其是，索引转换器500也包括一组非哈希函数，其与哈希函数大小相同。非哈希函数内不具有逻辑。相反，非哈希函数简单地从输入密钥取最低有效位(LSB)。当用户需要直接访问存储器(通过使用输入密钥作为直接存储器指示器)而不是通过哈希时，使用非哈希函数。以这个设计，诸如图1的并行查找系统100的系统能支持基于哈希和直接访问查找。为查找选择基于哈希或直接访问是通过配置cfg_hash_sel寄存器进行的。例如，如果查找被分派四个块，那么cfg_hash_sel寄存器为基于哈希查找选择12位哈希函数，或者为直接访问查找选择12位非哈希函数。
[0059] 索引转换器500也包括可重配置cfg_tile_offsel寄存器，以调整每个查找索引的TileID，以便查找索引正确指向被分派给各个查找路径的块的一个。为cfg_tile_offset寄存器配置的值通常在为相应的查找分派的块的组中的第一TileID。例如，在图3中，用于查找路径0的cfg_tile_offset寄存器被配置为0，因为为查找路径0分派的块为块0,1,2和3。类似地，用于查找路径1,2和3的cfg_tile_offset寄存器分别被配置为4,5和7。
[0060] 返回图1，并行查找系统100包括中央可重配置互联结构110。中央可重配置互联结构100包括与块中存在的存储器相同数目的单独的中央网络(即，M个)。每个中央网络具有与存在的查找路径相同数目的输入端口(即，N)，并且具有与存在的块相同数目的输出端口(即，T)。每个中央网络将所有查找路径的索引转换器i的输出连接到所有块中的存储器i。
[0061] 图6示出根据本发明的实施例的中央可重配置的互联结构600。在一些实施例中，中央可重配置的互联结构110被类似地配置为如可重配置的互联结构600那样。再次继续参照示例性方案，存在使用八个块615的四个并行查找路径，每个块具有两个存储器，并因此每个查找路径有两个索引转换器605。中央可重配置互联结构600具有两个4*8的中央网络610a，610b(统称为610)。网络0将所有查找路径的索引转换器0的输出连接到所有块615的存储器0，并且网络1将所有查找路径的索引转换器1的输出连接到所有块615的存储器1。
[0062] 这些中央网络610被配置为将每个查找路径正确地连接到其保留的块615。例如，在图3中，查找0被分派至块0,1,2和3。同样，网络0被配置为将输入端口0连接到输出端口0,1,2,3。类似地，输入端口1连接到输出端口4。类似地，输入端口2连接到输出端口5和6。类似地，输入端口3连接到输出端口7。这些连接在图6中示出。所有中央网络610具有相同配置设定。这样，网络1的配置与网络0准确相同。
[0063] 每个中央网络610都可以是交叉开关。然而，这些中央网络610通常在执行查找之前预先配置，这意味着是其在运行时间期间不变化。替代地，中央网络610能够从蝶形开关网络建立，其比交叉开关更廉价。存在能够实现的几个普通的可重配置蝶形开关网络，诸如Clos网络、Benes网络或Omega网络。
[0064] 在配置中央网络610之后，每个查找路径都将其输入密钥和输入密钥的查找索引发送给所有分派的块615，查找索引包括TileID和存储器地址。一旦分派的块615接收查找索引，分派的块615检查这个查找索引的TileID是否实际上指向块615。如果TileID是该块的，那么该块将使用查找索引中的存储器地址从相应的存储器读取。如果TileID不是该块的，那么可忽略接收的索引。
[0065] 当块615接收TileID指向的查找索引时，这个查找索引被称作有效索引。由于每个块615都具有M个存储器，所以每个块615都能够通过M个中央网络从相同密钥接收直到M个有效查找索引。例如，在图6中，每个块615能够为其两个本地存储器接收两个有效索引。
[0066] 图7示出根据本发明的实施例在块内的存储器700的格式。存储器700的深度通常为2m个条目(m位地址)。存储器700的每个条目含有用于以每路径P个桶支持D-LEFT查找的P对预编程{密钥，数据}705。因此，存储器700的宽度为P×(k+n)位，其中k为每个密钥的位宽，并且n为每个数据的位宽。块的本地存储器中的密钥和数据的值可依赖于怎样为每个查找路径分区并分派共享块来编程。用于这些存储器的编程原理基于D-LEFT查找技术。
[0067] 当块为本地存储器接收有效索引时，在这个有效索引中的存储器地址被用于读取本地存储器。本地存储器的输出在由存储器地址指出的条目处含有P对预编程{密钥，数据}。在块为其M个本地存储器接收M个有效索引的极端情况下，存在M×P对{密钥，数据}。M×P个密钥被发送到该块内的匹配逻辑区块，以决定这些预编程密钥哪些与输入密钥匹配。匹配结果用于选择预编程数据，以返回作为该块的查找结果。
[0068] 图8示出根据本发明的实施例的示例性块800的示意图，在一些实施例中，图1的区块115中的块被类似地配置为如块800那样。再次继续参照示例性的方案，块800包括两个存储器805，每个都具有三对预编程{密钥,数据}。对于每个输入密钥，块800能够从其两个存储器805获得多达六对有效预编程{密钥，数据}的最大值。六个或预编程的存储密钥被发送给块800的匹配区块810。来自匹配区块810的匹配结果被发送给选择区块815，以输出块800的查找结果。在一些实施例中，图2的区块215类似地被配置为如匹配区块810和选择区块815那样。
[0069] 图9示出根据本发明的实施例在选择区块900中选择命中结果的方法。在一些实施例中，图8的选择区块815类似地被配置为如选择区块900那样。该方法900在步骤905开始，其中用于所有存储的密钥的匹配结果是从图8的匹配部件810接收的。在步骤910，确定在预编程或存储密钥中是否存在与输入密钥匹配的任何匹配。如果在步骤910没有确定匹配，那么在步骤915，设定缺失位并且不返回结果。如果在步骤910确定至少一个匹配，那么在步骤920，确定在与输入密钥匹配的预编程密钥中是否存在超过一个匹配。如果在步骤920仅仅确定一个匹配，那么在步骤925，设定命中位，并且与预编程密钥配对的预编程数据作为命中数据返回。如果在步骤920确定超过一个匹配，那么在步骤930，设定命中位，并且与具有最低存储器ID的存储器中预编程密钥配对的预编程数据被选定并作为命中数据返回。
[0070] 除了为输入密钥返回命中数据之外，块也返回命中数据的位置，其包括TileID和存储命中数据的存储器地址。命中数据的位置对用户系统调试有用，也对统计目的有用。在步骤915、925和930后，方法900回到步骤905。
[0071] 返回参考图8，块800的查找结果通过输出可重配置互联结构，诸如图1的输出可重配置互联结构125，被发送到每个查找路径的结果收集器重配置。
[0072] 图10示出根据本发明的实施例的输出可重配置互联结构1000。在一些实施例中，输出可重配置互联结构125类似地被配置为如输出可重配置互联结构1000那样。输出可重配置互联结构1000包括输出重配置连接网络1010。输出重配置连接网络1010包括T1-输入×N输出可重配置去多路复用器。输出重配置连接网络1010将每个块1005的输出连接到查找路径的适当结果收集器1015。例如，在图3中，输出重配置连接网络1010被配置为将块0,1,2和3的输出连接到查找路径0的结果收集器1015。输出重配置连接网络1010也被配置为将块4的输出连接到查找路径1的结果收集器1015。输出重配置连接网络1010也被配置为将块5和6连接到查找路径2的结果收集器1015。输出重配置连接网络1010也被配置为将块7的输出连接到查找路径3的结果收集器1015。这些连接在图10中示出。每个查找路径的结果收集器1015从块1005中选择其拥有的一个结果，以输出该结果收集器1015的最终查找结果。
[0073] 图11示出根据本发明的实施例在结果收集器1100中选择命中结果的方法。在一些实施例中，图10的结果收集器类似地被配置为如结果收集器1100那样。方法1100从步骤1105开始，其中从分派的块接收查找结果。在步骤1110，确定是否存在任何块命中。如果在步骤1110未确定命中，那么在步骤1115，设定缺失位并且不返回结果。如果在步骤1110确定至少一个命中，那么在步骤1120，确定是否存在来自块的超过一个命中。如果在步骤1120仅仅确定一个命中，那么在步骤1125，设定命中位，并且命中结果或命中数据作为查找结果返回。如果在步骤1120确定超过一个命中，那么在步骤1130，设定命中位，并且选择来自块命中中TileID最低的块的命中结果并且将该结果作为查找结果返回。
[0074] 除了返回命中结果，结果收集器也返回TileID、存储器ID和读取命中数据的存储器地址。TileID、存储器ID和存储器地址对用户系统调试有用，也对统计目的有用。在步骤1115、1125和1130后，方法1100回到步骤1105。
[0075] 图12示出根据本发明的实施例来配置和编程并行查找系统1200的方法。该方法1200为用户提供建立并行查找系统的指南，诸如图1的并行查找系统100。并行查找系统100具有带T个共享块的N个并行查找路径。每个块都具有M个存储器。每个存储器都具有m位宽的存储器地址。每个存储器条目都含有可通过软件编程的P对{密钥,数据}。系统100中的每个查找为具有M路和每路P桶的D-LEFT查找。
[0076] 方法1200在步骤1205开始，其中用户为每个查找路径分派块。分派给每个查找路径的块的数目必须为2的幂。块分区也必须保证在查找路径中不存在块重叠。
[0077] 在步骤1210，计算每个查找路径的哈希的大小。用于每个查找路径的哈希大小基于为该查找路径分派的块的数目。如果查找路径分派q个块，那么其哈希大小等于log2(q)+m。
[0078] 在已知每个查找的哈希大小之后，在步骤1215，索引转换器中的寄存器cfg_hash_sel和cfg_tile_offset被相应配置。cfg_hash_sel寄存器为查找路径选择函数。cfg_tile_offset寄存器为查找路径调整查找索引的TileID。
[0079] 其间，在步骤1220，中央和输出互联网络被配置为将查找路径与其保留的块连接。所有用于索引转换器和网络的配置位能够由脚本根据本文中所述的原理自动生成。
[0080] 在步骤1225，为每个查找路径分派的存储器被编程。编程技术基于D-LEFT查找技术，其具有每查找M路和每路P桶。
[0081] 在编程所有分派的存储器后，在步骤1230，并行查找系统100准备接收输入密钥并且并行执行N个查找。在步骤1230之后，方法1200结束。
[0082] 本发明的实施例涉及多并行查找，所述多并行查找使用通过互联网络的适当配置的共享存储器的池。为每个查找保留的共享存储器的数目可根据该查找需要的存储能力而重配置。共享存储器被分组为同质块。基于该查找所需的存储能力，每个查找分派一组块。为每个查找分派的块不与其他查找重叠，以便所有查找能够并行执行而不冲突。每个查找可重配置为基于哈希或直接访问。基于如何为每个查找分派这些块而编程所述互联网络。
[0083] 本领域技术人员将认识到也存在其他使用和优点。尽管已经参考许多具体细节描述本发明，但是本领域技术人员将认识到，本发明能够以其他具体形式涵盖，而不偏离本发明的精神。因此，本领技术人员会理解，本发明不限制于上文说明性的细节，而是通过附加权利要求限定。
