Source: http://www.freepatentsonline.com/8954700.html
Timestamp: 2018-06-21 10:43:25
Document Index: 91271040

Matched Legal Cases: ['Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61']

Method and apparatus for managing processing thread migration between clusters within a processor - Cavium, Inc.
United States Patent 8954700
Ansari, Najeeb I. (San Jose, CA, US)
13/565749
711/5, 711/167, 711/E12.002
G06F12/02; G06F9/46; G06F9/50; G06F12/04; G06F12/08; G06F13/16; G06N5/02; H04L12/26; H04L12/741; H04L12/747; H04L12/801; H04L12/851; H04L29/06; H04L29/08
711/165, 711/5, 711/167, 711/E12.002
Download PDF 8954700 PDF help
20130036288 METHOD AND APPARATUS FOR ASSIGNING RESOURCES USED TO MANAGE TRANSPORT OPERATIONS BETWEEN CLUSTERS WITHIN A PROCESSOR 2013-02-07 Ansari et al.
20130036284 METHOD AND APPARATUS FOR MANAGING TRANSFER OF TRANSPORT OPERATIONS FROM A CLUSTER IN A PROCESSOR 2013-02-07 Ansari et al.
20130036185 METHOD AND APPARATUS FOR MANAGING TRANSPORT OPERATIONS TO A CLUSTER WITHIN A PROCESSOR 2013-02-07 Ansari et al.
20110258420 EXECUTION MIGRATION 2011-10-20 Devadas et al. 712/225
7565508 Allocating clusters to storage partitions in a storage system 2009-07-21 Nakamura
First Action Interview Pilot Program Pre-Interview Communication, U.S. Appl. No. 13/565,746, dated Mar. 25, 2014.
Non-Final Office Action, dated Oct. 3, 2014, for U.S. Appl. No. 13/565,743, consisting of 14 pages.
First Action Interview Office Action Summary, for U.S. Appl. No. 13/565,746, dated Jul. 14, 2014, consisting of 3 pages.
This application claims the benefit of U.S. Provisional Application No. 61/514,344, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,382, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,379, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,400, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,406, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,407, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,438, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,447, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,450, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,459, filed on Aug. 2, 2011; and U.S. Provisional Application No. 61/514,463, filed on Aug. 2, 2011. The entire teachings of the above applications are incorporated herein by reference.
1. A method of managing processing thread migrations within a plurality of memory clusters, the method comprising: embedding, in memory components of the plurality of memory clusters, instructions indicative of processing thread migrations wherein the instructions indicative of processing thread migrations include instructions preventing migrating a processing thread to a memory cluster from which the processing thread migrated previously; storing, in one or more memory components of a particular memory cluster among the plurality of memory clusters, data configured to designate the particular memory cluster as a sink memory cluster, the sink memory cluster preventing an incoming migrated processing thread from migrating out of the sink memory cluster; and processing one or more processing threads, in one or more of the plurality of memory clusters, in accordance with at least one of the embedded migration instructions and the data stored in the one or more memory components of the sink memory cluster.
2. A method according to claim 1, wherein the one or more processing threads include at least one tree search thread.
6. An apparatus of managing processing thread migrations within a plurality of memory clusters, the apparatus comprising: one or more processors configured to: cause embedding, in memory components of the plurality of memory clusters, of instructions indicative of processing thread migrations wherein the instructions indicative of processing thread migrations include instructions preventing migrating a processing thread to a memory cluster from which the processing thread migrated previously; cause storing, in one or more memory components of a particular memory cluster among the plurality of memory clusters, of data configured to designate the particular memory cluster as a sink memory cluster, the sink memory cluster preventing an incoming migrated processing thread from migrating out of the sink memory cluster; and process one or more processing threads, in one or more of the plurality of memory clusters, in accordance with at least one of the embedded migration instructions and the data stored in the one or more memory components of the sink memory cluster.
7. An apparatus according to claim 6, wherein the one or more processing threads include at least one tree search thread.
8. An apparatus according to claim 6, wherein the one or more processing threads include at least one bucket search thread.
9. An apparatus according to claim 6, wherein the instructions indicative of processing thread migrations include instructions to cause migrated processing threads to be migrated out to a sink memory cluster or a memory cluster in a path to a sink memory cluster, the path to a sink memory cluster being a sequence of memory clusters representing a migration flow path and ending with the sink memory cluster.
10. An apparatus according to claim 6, wherein in each of the plurality of memory clusters at least one processing engine is reserved to handle migrating processing threads.
According to an example embodiment, a method of managing processing thread migrations within a plurality of memory clusters, includes embedding, in memory components of the plurality of memory clusters, instructions indicative of processing thread migrations; storing, in one or more memory components of a particular memory cluster among the plurality of memory clusters, data configured to designate the particular memory cluster as a sink memory cluster, the sink memory cluster preventing an incoming migrated processing thread from migrating out of the sink memory cluster; and processing one or more processing threads, in one or more of the plurality of memory clusters, in accordance with at least one of the embedded migration instructions and the data stored in the one or more memory components of the sink memory cluster.
According to another example embodiment, an apparatus of managing processing thread migrations within a plurality of memory clusters, includes one or more processors configured to cause embedding, in memory components of the plurality of memory clusters, of instructions indicative of processing thread migrations; cause storing, in one or more memory components of a particular memory cluster among the plurality of memory clusters, of data configured to designate the particular memory cluster as a sink memory cluster, the sink memory cluster preventing an incoming migrated processing thread from migrating out of the sink cluster; and process one or more processing threads, in one or more of the plurality of memory clusters, in accordance with at least one of the embedded migration instructions and the data stored in the one or more memory components of the sink memory cluster.
A TCAM is a hardware device that functions as a fully associative memory. A TCAM cell stores three values: 0, 1, or ‘X,’ which represents a don't-care bit and operates as a per-cell mask enabling the TCAM to match rules containing wildcards, such as a kleene star ‘*’. In operation, a whole packet header can be presented to a TCAM to determine which entry, or rule, it matches. However, the complexity of TCAMs has allowed only small, inflexible, and relatively slow implementations that consume a lot of power. Therefore, a need continues for efficient algorithmic solutions operating on specialized data structures.
Proposed mathematic solutions have been reported to have excellent time/spatial complexity. However, methods of this kind have not been found to have any implementation in real-life network devices because mathematical solutions often add special conditions to simplify a problem and/or omit large constant factors which might conceal an explicit worst-case bound.
Packet classifiers may analyze and categorize rules in a classifier table and create a decision tree that is used to match received packets with rules from the classifier table. A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. Decision trees are commonly used in operations research, specifically in decision analysis, to help identify a strategy most likely to reach a goal. Another use of decision trees is as a descriptive means for calculating conditional probabilities. Decision trees may be used to match a received packet with a rule in a classifier table to determine how to process the received packet.
FIG. 1 is a block diagram 100 of a typical network topology including network elements where a search processor may be employed. The network topology includes an Internet core 102 including a plurality of core routers 104a-h. Each of the plurality of core routers 104a-h is connected to at least one other of the plurality of core routers 104a-h. Core routers 104a-h that are on the edge of the Internet core 102, e.g., core routers 104b-e and 104h, are coupled with at least one edge router 106a-f. Each edge router 106a-f is coupled to at least one access router 108a-e.
The core routers 104a-104h are configured to operate in the Internet core 102 or Internet backbone. The core routers 104a-104h are configured to support multiple telecommunications interfaces of the Internet core 102 and are further configured to forward packets at a full speed of each of the multiple telecommunications protocols.
The edge routers 106a-106f are placed at the edge of the Internet core 102. Edge routers 106a-106f bridge access routers 108a-108e outside the Internet core 102 and core routers 104a-104h in the Internet core 102. Edge routers 106a-106f may be configured to employ a bridging protocol to forward packets from access routers 108a-108e to core routers 104a-104h and vice versa.
The access routers 108a-108e may be routers used by an end user, such as a home user or an office, to connect to one of the edge routers 106a-106f, which in turn connects to the Internet core 102 by connecting to one of the core routers 104a-104h. In this manner, the edge routers 106a-106f may connect to any other edge router 106a-104f via the edge routers 106a-104f and the interconnected core routers 104a-104h.
The search processor described herein may reside in any of the core routers 104a-104h, edge routers 106a-106f, or access routers 108a-108e. The search processor described herein, within each of these routers, is configured to analyze Internet protocol (IP) packets based on a set of rules and forward the IP packets along an appropriate network path.
FIG. 2A is a block diagram 200 illustrating an example embodiment of an edge router 106 employing a search processor 202. An edge router 106, such as a service provider edge router, includes the search processor 202, a first host processor 204 and a second host processor 214. Examples of the first host processor include processors such as a network processor unit (NPU), a custom application-specific integrated circuit (ASIC), an OCTEON® processor available from Cavium Inc., or the like. The first host processor 204 is configured as an ingress host processor. The first host processor 204 receives ingress packets 206 from a network. Upon receiving a packet, the first host processor 204 forwards a lookup request including a packet header, or field, from the ingress packets 206 to the search processor 202 using an Interlaken interface 208. The search processor 202 then processes the packet header using a plurality of rule processing engines employing a plurality of rules to determine a path to forward the ingress packets 206 on the network. The search processor 202, after processing the lookup request with the packet header, forwards the path information to the first host processor 204, which forwards the processed ingress packets 210 to another network element in the network.
Likewise, the second host processor 214 is an egress host processor. Examples of the second host processor include processors such as a NPU, a custom ASIC, an OCTEON processor, or the like. The second host processor 214 receives egress packets 216 to send to the network. The second host processor 214 forwards a lookup request with a packet header, or field, from the egress packets 216 to the search processor 202 over a second Interlaken interface 218. The search processor 202 then processes the packet header using a plurality of rule processing engines employing a plurality of rules to determine a path to forward the packets on the network. The search processor 202 forwards the processed egress packets 220 from the host processor 214 to another network element in the network.
FIG. 2B is a block diagram 220 illustrating another example embodiment of an edge router 106 configured to employ the search processor 202. In this embodiment, the edge router 106 includes a plurality of search processors 202, for example, a first search processor 202a and a second search processor 202b. The plurality of search processors 202a-202b are coupled to a packet processor 228 using a plurality of Interlaken interfaces 226a-b, respectively. Examples of the packet processor 228 include processors such as NPU, ASIC, or the like. The plurality of search processors 202a-202b may be coupled to the packet processor 228 over a single Interlaken interface. The edge router 106 receives a lookup request with a packet header, or fields, of pre-processed packets 222 at the packet processor 228. The packet processor 228 sends the lookup request to one of the search processors 202a-202b. The search processor, 202a or 202b, searches a packet header for an appropriate forwarding destination for the pre-processed packets 222 based on a set of rules and data within the packet header, and responds to the lookup request to the packet processor 228. The packet processor 228 then sends the post processed packets 224 to the network based on the response to the lookup request from the search processors 202a-202b.
FIG. 3 shows an example architecture of a search processor 202. The processor includes, among other things, an interface, e.g., Interlaken LA interface, 302 to receive requests from a host processor, e.g., 204, 214, 228, 242, or 244, and to send responses to the host processor. The interface 302 is coupled to Lookup Front-end (LUF) processors 304 configured to process, schedule, and order the requests and responses communicated from or to the interface 302. According to an example embodiment, each of the LUF processors is coupled to one of the super clusters 310. Each super cluster 310 includes one or more memory clusters, or search clusters, 320. Each of the memory, or search, clusters 320 includes a Lookup Engine (LUE) component 322 and a corresponding on-chip memory (OCM) component 324. A memory, or search, cluster may be viewed as a search block including a LUE component 322 and a corresponding OCM component 324. Each LUE component 322 is associated with a corresponding OCM component 324. A LUE component 322 includes processing engines configured to search for rules in a corresponding OCM component 324, given a request, that match keys for packet classification. The LUE component 322 may also include interface logic, or engine(s), configured to manage transport of data between different components within the memory cluster 320 and communications with other clusters. The memory clusters 320, in a given super cluster 310, are coupled through an interface device, e.g., crossbar (XBAR) 312. The XBAR 312 may be viewed as an intelligent fabric enabling coupling LUF processors 304 to different memory clusters 320 as well as coupling between different memory clusters 320 in the same super cluster 310. The search processor 202 may include one or more super clusters 310. A lookup cluster complex (LCC) 330 defines the group of super clusters 310 in the search processor 202.
FIG. 4 is a block diagram 400 illustrating an example embodiment of loading rules, by a software compiler, into OCM components. According to an example embodiment, the software compiler 404 is software executed by a host processor or control plane processor to store rules into the search processor 202. Specifically, rules are loaded to at least one OCM component 324 of at least one memory cluster, or search block, 320 in the search processor 202. According to at least one example embodiment, the software compiler 404 uses multiple data structures, in storing the rules, in a way to facilitate the search of the stored rules at a later time. The software compiler 404 receives a rule set 402, parameter(s) indicative of a maximum tree depth 406 and parameter(s) indicative of a number of sub-trees 408. The software compiler 404 generates a set of compiled rules formatted, according at least one example embodiment, as linked data structures referred to hereinafter as rule compiled data structure (RCDS) 410. The RCDS is stored in at least one OCM component 324 of at least one memory cluster, or search block, 320 in the search processor 202. The RCDS 410 includes at least one tree 412. Each tree 412 includes nodes 411a-411c, leaf nodes 413a-413b, and a root node 432. A leaf node, 413a-413b, of the tree 412 includes or points to one of a set of buckets 414. A bucket 414 may be viewed as a sequence of bucket entries, each bucket entry storing a pointer or an address, referred to hereinafter as a chunk pointer 418, of a chunk of rules 420. Buckets may be implemented, for example, using tables, linked lists, or any other data structures known in the art adequate for storing a sequence of entries. A chunk of rules 420 is basically a chunk of data describing or representing one or more rules. In other words, a set of rules 416 stored in one or more OCM components 324 of the search processor 202 include chunks of rules 420. A chunk of rules 420 may be a sequential group of rules, or a group of rules scattered throughout the memory, either organized by a plurality of pointers or by recollecting the scattered chunk of rules 420, for example, using a hash function.
2) The GID indexes an entry in a global definition/description table (GDT). Each GDT entry includes n number of table identifiers (TID), a packet header index (PHIDX), and key format table index (KFTIDX).
FIG. 5 shows a block diagram illustrating an example embodiment of a memory, or search, cluster 320. The memory, or search, cluster 320 includes an on-chip memory (OCM) 324, a plurality of processing, or search, engines 510, an OCM bank slotter (OBS) module 520, and a cross-bar controller (XBC) 530. The OCM 324 includes one or more memory banks According to an example implementation, the OCM 324 includes two mega bytes (MBs) of memory divided into 16 memory banks According to the example implementation, the OCM 324 includes 64 k, or 65536, of rows each 256 bits wide. As such, each of the 16 memory banks has 4096 contiguous rows, each 256 bits wide. A person skilled in the art should appreciate that the described example implementation is provided for illustration and the OCM may, for example, have more or less than 2 MBs of memory and the number of memory banks may be different from 16. The number of memory rows, the number of bits in each memory row, as well as the distribution of memory rows between different memory banks may be different from the illustration in the described example implementation. The OCM 324 is configured to store, and provide access to, the RCDS 410. In storing the RCDS 410, the distribution of the data associated with the RCDS 410 among different memory banks may be done in different ways. For example, different data structures, e.g., the tree data structure(s), the bucket storage data structure(s), and the chunk rule data structure(s), may be stored in different memory banks. Alternatively, a single memory bank may store data associated with more than one data structure. For example, a given memory bank may store a portion of the tree data structure, a portion of the bucket data structure, and a portion of the chunk rule data structure.
The response that an appropriate leaf node is found includes, for example, a pointer to a bucket passed by the TWE 512 to the BWE 514. The BWE 514 is configured to issue requests to access buckets 414 in the OCM 324 and receive corresponding responses. The BWE 514, for example, uses the pointer to the bucket received from the TWE 512 to access one or more buckets 414 and retrieve at least one chunk pointer 418 pointing to a chunk of rules. The BWE 514 provides the retrieved at least one chunk pointer 418 to at least one RWE 516. According to at least one example, BWE 514 may initiate a plurality of rule searched to be processed by one RWE 516. However, the maximum number of outstanding, or on-going, rule searches at any point of time may be constrained, e.g., maximum of 16 rule searches. The RWE is configured to issue requests to access rule chunks 420 in the OCM 324 and receive corresponding responses. The RWE 516 uses a received chunk pointer 418 to access rule chunks stored in the OCM 324 and retrieve one or more rule chunks. The retrieved one or more rule chunks are then passed to one or more RMEs 518. An RME 518, upon receiving a chunk rule, is configured to check whether there is a match between one or more rules in the retrieved rule chunk and the field corresponding to the key.
FIG. 6A shows a block diagram illustrating an example embodiment of processing a remote access request between two search clusters. A remote access request is a request generated by an engine/entity in a first search cluster to access data stored in a second search cluster or memory outside the first search cluster. For example, a processing engine in cluster 1, 320a, sends a remote access request for accessing data in another cluster, e.g., cluster N 320b. The remote access request may be, for example, a tree data access request generated by a TWE 512a in cluster 1, a bucket access request generated by a BWE 514a in cluster 1, or a rule chunk data access request generated by a RWE 516a or RME in cluster 1. The remote access request is pushed by the XBC 530a of cluster 1 to the XBAR 312 and then sent to the XBC 530b of cluster N. The XBC 530b of cluster N then forwards the remote access request to the OBS module 520b of cluster N. The OBS module 520b directs the remote access request to OCM 324b of cluster N and a remote response is sent back from the OCM 324b to the XBC 530b through the RDP 540b. The XBC 530b forwards the remote response to the XBC 530a through the XBAR 312. The XBC 530a then forwards the remote response to the respective processing engine in the LUEs component 322a.
FIG. 6B shows a block diagram illustrating an example embodiment of a processing thread migration between two search clusters. Migration requests originate from a TWE 512 or BWE 514 as they relate mainly to a bucket search/access process or a tree search/access process, in a first cluster, that is configured to continue processing in a second cluster. Unlike remote access where data is requested and received from the second cluster, in processing thread migration the process itself migrates and continues processing in the second cluster. As such, information related to the processing thread, e.g., state information, is migrated to the second cluster from the first cluster. As illustrated in FIG. 6B, processing thread migration requests are sent from TWE 512a or BWE 514a directly to the XBC 530a in the cluster 1, 320a. The XBC 530a sends the migration request through the crossbar (XBAR) 312 to the XBC 530b in cluster N, 320b. At the receiving cluster, e.g., cluster N 320b, the XBC 530b forwards the migration request to the proper engine, e.g., TWE 512b or BWE 514b. According to at least one example embodiment, the XBC, e.g., 530a and 530b, does not just forward requests. The XBC arbitrates which, among remote OCM requests, OCM response data, and migration requests, to be sent at a clock cycle.
FIG. 7 shows an example hardware implementation of the OCM 324 in a cluster 320. According to the example implementation shown in FIG. 7, the OCM includes a plurality, e.g., 16, single-ported memory banks 705a-705p. Each memory bank, for example, includes 4096 memory rows, each of 256 bits width. A person skilled in the art should appreciate that the number, e.g., 16, of the memory banks and their storage capacity are chosen for illustration purposes and should not be interpreted as limiting. Each of the memory banks 705a-705p is coupled to at least one input multiplexer 715a-715p and at least one output multiplexer 725a-725-p. Each input multiplexer, among the multiplexers 715a-715p, couples the input logical ports 710a-710d to a corresponding memory bank among the memory banks 705a-705p. Similarly, each output multiplexer, among the multiplexers 725a-725p, couples the output logical ports 720a-720d to a corresponding memory bank among the memory banks 705a-705p.
The input logical ports 710a-710d carry access requests' data from the OBS module 520 to respective memory banks among the memory banks 705a-705p. The output logical ports 720a-720d carry access responses' data from respective memory banks, among the memory banks 705a-705p, to RDP component 540. Given that the memory banks 705a-705p are single-ported, at each clock cycle a single access is permitted to each of the memory banks 705a-705p. Also given the fact that there are four input logical/access ports, a maximum of four requests may be executed, or served, at a given clock cycle because no more than one logical port may be addressed to the same physical memory bank at the same clock cycle. For a similar reason, e.g., four output logical/access ports, a maximum of four responses may be sent out of the OCM 324 at a given clock cycle. An input multiplexer is configured to select a request, or decide which request, to access the corresponding physical memory bank. An output multiplexer is configured to select an access port on which a response from a corresponding physical memory bank is to be sent. For example, an output multiplexer may select an output logical port, to send a response, corresponding to an input logical port on which the corresponding request was received. A person skilled in the art should appreciate that other implementations with more, or less, than four ports may be employed.
According to an example embodiment, an access request is formatted as an 18 bit tuple. Among the 18 bits, two bits are used as wire interface indicating an access instruction/command, e.g., read, write, or idle, four bits are used to specify a memory bank among the memory banks 705a-705p, and 12 bits are used to identify a row, among the 4096 rows, in the specified memory bank. In the case of a “write” command, 256 bits of data to be written are also sent to the appropriate memory bank. A person skilled in the art should appreciate that such format/structure is appropriate for the hardware implementation shown in FIG. 7. For example, using 4 bits to specify a memory bank is appropriate if the total number of memory banks is 16 or less. Also the number of bits used to identify a row is correlated to the total number of rows in each memory bank. Therefore, the request format described above is provided for illustration purpose and a person skilled in the art should appreciate that many other formats may be employed.
Processing operations, e.g., tree search, bucket search, or rule chunk search, may include processing across memory clusters. For example, a processing operation running in a first memory cluster may require accessing data stored in one or more other memory clusters. In such a case, a remote access request may be generated, for example by a respective processing engine, and sent to at least one of the one or more other memory clusters and a remote access response with the requested data may then be received. Alternatively, the processing operation may migrate to at least one of the one or more other memory clusters and continue processing therein. For example, a remote access request may be generated if the size of the data to be accessed from another memory cluster is relatively small and therefore the data may be requested and acquired in relatively short time period. However, if the data to be accessed is of relatively large size, then it may be more efficient to proceed with a processing thread migration where the processing operation migrates and continue processing in the other memory cluster. The transfer of data, related to a processing operation, between different memory clusters is referred to hereinafter as a transport operation. Transport operations, or transactions, include processing thread migration operation(s), remote access request operation(s), and remote access response operation(s). According to an example embodiment, transport operations are initiated based on one or more instructions embedded in the OCM 324. When a processing engine, fetching data within the OCM 324 as part of a processing operation, reads an instruction among the one or more embedded instructions, the processing engine responds to the read instruction by starting a respective transport operation. The instructions are embedded, for example, by software executed by the host processor, 204, 214, 228, 242, 244, such as the software compiler 404.
FIGS. 8B and 8C show logical diagrams illustrating an example implementation of the transmitting component 845, of the XBC 530, and the resource state manager 850. The transmitting component 845 is coupled to the OCM 324 and the processing engines 510, e.g., TWEs 512, BWEs 514, and RWEs 516 or RMEs 518, as shown in the logical diagrams. Among the processing engines 510, the TWEs 512 make remote tree access requests, the BWEs 514 make remote bucket access requests, and the RWEs 516 make remote rule access requests. The remote requests are stored in one or more first in first out (FIFO) buffers 834 and then pushed into per-destination FIFO buffers, 806a . . . 806g, to avoid head-of-line blocking. The one or more FIFO buffers 834 may include, for example, a FIFO buffer 832 for storing tree access requests, FIFO buffer 834 for storing bucket access requests, FIFO buffer 836 for storing rule chunk access requests, and an arbitrator/selector 838 configured to select remote requests from the different FIFO buffers to be pushed into the per-destination FIFO buffers, 806a-806g. Similarly, remote access responses received from the OCM 324 are stored in a respective FIFO buffer 840 and then pushed into a per-destination FIFO buffers, 809a-809g, to avoid head-of-line blocking.
The TWEs 512 make tree processing thread migration requests, BWEs 514 make bucket processing thread migration requests. In the following, processing thread migration may be initiated either by TWEs 512 or BWEs 514. However, according to other example embodiments the RWEs 516 may also initiate processing thread migrations. When TWEs 512 or BWEs 514 make processing thread migration requests, the contexts of the corresponding processing threads are stored in per-destination FIFO buffers, 803a-803g. According to an example embodiment, destination decoders, 802, 805, and 808, are configured to determine the destination memory cluster for processing thread migration requests, remote access requests, and remote access responses, respectively. Based on the determined destination memory cluster, data associated with the respective transport operation is then sent to a corresponding per-destination FIFO buffer, e.g., 803a-803g, 806a-806g, and 809a-809g. The logic diagrams in FIGS. 8B and 8C assume a super cluster 310 including eight memory, or search, clusters 320. As such, each transport operation in a particular memory cluster may be destined to at least one of seven memory clusters referred to in the FIGS. 8B and 8C with the letters a . . . g.
According to an example embodiment, a per-destination arbitrator, 810a-810g, is used to select a transport operation associated with the same destination memory cluster. The selection may be made, for example, based on per-type priority information associated with the different types of transport operations. Alternatively, the selection may be made based on other criteria. For example, the selection may be performed based on a sequential alternation between the different types of transport operations so that transport operations of different types are treated equally. In another example embodiment, data associated with a transport operation initiated in a previous clock cycle may be given higher priority by the per-destination arbitrators, 810a-810g. As shown in FIG. 8C, each per-destination arbitrator, 810a-810g, may include a type selector, 812a-812g, a retriever, 814a-814g, and a destination FIFO buffer, 816a-816g. The type selector, 812a-812g, selects a type of a transport operation and passes information indicative of selected type to the retriever, 814a-814g, which retrieves the data at the head of a corresponding per-destination FIFO buffer, e.g., 803a-803g, 806a-806g, or 809a-809g. The retrieved data is then stored in the destination FIFO buffer, 816a-816g.
The transmitting component 845 also includes an arbitrator 820. The arbitrator 820 is coupled to the resource state manager 850 and receives or checks information related to the states of resources, in destination memory clusters, allocated to the source memory cluster processing the transport operations to be transmitted. The arbitrator 820 is configured to select data associated with at least one transport operation, or transaction, among the data provided by the arbitrators, 810a-810g, and schedule the at least one transport operation to be transported over the XBAR 312. The selection is based at least in part on the information related to the states of resources and/or other information such as priority information. For example, resources in destination memory clusters allocated to the source memory cluster are associated with remote access requests and processing thread migrations but no resources are associated with remote access responses. In other words, for a remote access response a corresponding destination memory cluster is configured to receive the remote access response at any time regardless of other processes running in the destination memory cluster. For example, resources in the destination memory clusters allocated to the source memory cluster include buffering capacities for storing data associated with transport operations received at the destination memory clusters from the source memory cluster. As such no buffering capacities, at the destination memory clusters, are associated with remote access responses.
According to an example embodiment, the arbitrator 820 includes a destination selector 822 configured to select a destination FIFO buffer, among the destination FIFO buffers 816a-816g, from which data to be retrieved and forwarded, or scheduled to be forwarded, to the XBAR 312. The destination selector passes information indicative of the selected destination to a retriever 824. The retriever 824 is configured to retrieve transport operation data from the respective destination FIFO buffer, 814a-814g, and forward the retrieved transport operation data to the XBAR 312.
FIGS. 8D and 8E show logical diagrams illustrating an example implementation of the receiving component 895, of the XBC 530. According to at least one example embodiment, the receiving component 895, e.g., in a first memory cluster, includes a type identification module 860. The type identification module 860 receives information related to transport operations destined to the first memory cluster with data in the XBAR 312. The received information, for example, includes indication of the respective types of the transport operations. According to the example implementation shown in FIG. 8E, the type identification module 860 includes a source decoder 862 configured to forward the received information, e.g., transport operation type information, to per-source FIFO buffers 865a-865g also included in the type identification module 860. For example, received information associated with a given source memory cluster is forwarded to a corresponding per-source memory FIFO buffer. An arbitrator 870 then acquires the information stored in the per-source FIFO buffers, 865a-865g, and selects at least one transport operation for which data is to be retrieved from the XBAR 312. Data corresponding to the selected transport operation is then retrieved from the XBAR 312.
In the example implementation shown in FIG. 8E, the arbitrator 870 includes first selectors 871-873 configured to select a transport operation among each type and a second selector 875 configured to select a transport operation among the transport operations of different types provided by the first selectors 871-873. The second selector 875 sends indication of the selected transport operation to the logic operators 876a-876c, which in turn pass only data associated with the selected transport operation. The example receiving component 895 shown in FIG. 8D also includes a logic operator, or type decoder, 883 configured direct processing thread migration data to separate buffers, e.g., 882 and 884, based on processing thread type, e.g., tree or bucket. Upon forwarding a transport operation to the OCM 324 or a respective processing engine 510, a signal is sent to a resource return logic 852. The resource return logic 852 is part of the resource state manager 850 and is configured to cause updating of resource state information.
FIG. 9A is a block diagram illustrating an example implementation of the XBAR 312. A person skilled in the art should appreciate that the XBAR 312 as described herein is an example of an interface device coupling a plurality of memory clusters. In general, different interface devices may be used. The example implementation shown in FIG. 9A is an eight port fully-buffered XBAR that is constructed out of modular slices 950a-950d. For example, the memory clusters are arranged in two rows, e.g., north memory clusters, 320a, 320c, 320e, and 320g, are indexed with even numbers and south memory clusters, 320b, 320d, 320f, and 320h, are indexed with odd numbers. The XBAR 312 is constructed to connect these clusters. To match the cluster topology, the example XBAR 312 in FIG. 9A is built as a 2×4 (8-port) XBAR 312. Each slice connects a pair of North-South memory clusters to each other and to its neighboring slice(s).
FIG. 9B is a block diagram illustrating implementation of two slices, 950a and 950b, of the XBAR 312. Each slice is built using half-slivers 910 and full-slivers 920. The half-slivers 910 and the full-slivers 920 are, for example, logic circuits used in coupling memory clusters to each other. For an N-port XBAR 312, each slice contains N−2 full-slivers 920 and 2 half-slivers 910. The full-slivers 920 correspond to memory cluster ports that are used to couple memory clusters 320 belonging to distinct slices 950. For the slice 950a, for example, full-slivers 920 correspond to ports 930c to 930h which couple memory clusters in the slice 950a to the memory clusters 320b-320d, respectively, in other slices 950. For the memory cluster ports coupling memory cluster within the same slice, the slivers are optimized to half-slivers 910. For the slice 950a, for example, half-slivers correspond to ports 930a and 930b.
FIG. 9C shows an example logic circuit implementation of a full-sliver 920. The full-sliver 920 contains two FIFO buffers, 925a and 925b, for storing data from other ports through a neighboring slice. One FIFO buffer, e.g., 925a, is for storing data destined to the north memory cluster and one FIFO buffer, e.g., 925b, is for storing the data destined to the south memory cluster. The control (GRQs) signals 922a and 922b identify which port the data is destined to. The data (GRFs) 921 is pushed into the appropriate full-sliver FIFO 925a or 925b. For example, when data from the memory cluster_320c is destined to the memory cluster_320b, GRQ2 and GRF2 will signal to the south FIFO buffer 925b of the full sliver SLV2 in slice 950a to capture and keep the data until it is demanded by the memory cluster 320b. Continuing with the same example, if data was destined to the memory cluster_320a, GRQ2 will signal the north FIFO buffer 925a the full sliver SLV2 in slice 950a to capture and keep the data until demanded by the memory cluster_320a.
FIG. 9D shows an example logic circuit implementation of a half-sliver 910. Each half-sliver 910 contains one FIFO buffer 925 for storing data from one of two memory clusters within a given slice. The data in each half-sliver 910 is meant for the opposite memory cluster in the same slice. For example, in the slice 950a, the half-sliver HSLV0 gets data (GRF0) from the memory cluster_320a and is destined to the memory cluster_320b.
When a memory cluster decides to fetch the data from a particular FIFO buffer, e.g., 925, 925a, or 925b, it sends a pop signal, 917, 927a, or 927b, to that FIFO buffer. When the FIFO buffer, e.g., 925, 925a, or 925b, is not selected by the memory cluster the logic AND operator 914, 924a, or 924b, outputs zeros. An OR operator, e.g., 916, 926a, or 926b, in each sliver is applied to the data resulting in a chain of OR operators either going north or going south. According to an example embodiment, one clock cycle delay between pop signal and data availability at the memory cluster that's pulling the data.
The XBAR 312 is the backbone for transporting various transport transactions, or operations, such as remote requests, remote responses, and processing thread migrations. The XBAR 312 provides the transport infrastructure, or interface. According to at least one example embodiment, transaction scheduling, arbitration and flow control is handled by the XBC 320. In any given clock cycle multiple pairs of memory clusters may communicate. For example, the memory cluster 320a communicates with the memory cluster 320b, the memory cluster 320f communicates to the memory cluster 320c, etc. The transfer time for transferring a transport operation, or a partial transport operation, from a first memory cluster to a second memory cluster is fixed with no queuing delays in the XBAR 312 or any of the XBCs of the first and second memory clusters. However, in the case of queuing delays, the transfer time, or latency, depends on other transport operations, or partial transport operations, in the queue and the arbitration process.
Resources are measured in units, e.g., “credits.” For example, a resource in a first memory cluster, e.g., destination memory cluster, allocated to a second memory cluster, e.g. source memory cluster, represented by one credit corresponds to one slot in a respective buffer, e.g., 882, 884, or 886. According to another example, one credit may represent storage capacity equivalent to the amount of data transferable in a single clock cycle. XBAR resources refer, for example, to storage capacity of FIFO buffers, e.g., 915, 925a, 925b, in the XBAR. In yet another example, one credit corresponds to storage capacity for storing a migration packet or message.
In increasing the number of processing resources allocated to the first memory cluster from the second memory cluster, the host processor determines whether a number of non-allocated processing resources, in the second memory cluster, is larger than or equal to a number of processing resources to be increased. For example if the number of allocated processing resources is to be increased from 5 to 8 in the first memory cluster, the number of non-allocated resources in the second memory cluster is compared to 3, i.e., 8-5. Upon determining that the number of non-allocated processing resources, in the second memory cluster, is larger than or equal to the number of processing resources to be increased, the host processor sends information, to the search processor 202, indicative of changes to be made to processing resources allocated to the first memory cluster from the second memory cluster. Upon the information being received by the search processor 202, the resource state manager 850 in the first memory cluster modifies the information indicative of allocated processing resources to reflect the increase in processing resources, in the second memory cluster, allocated to the first memory cluster. The resource state manager then uses the updated information to facilitate management of transport operations between the first memory cluster and the second memory cluster. According to another example, the XBC 530 of the first memory cluster may apply blocking of transport operations and partial transport operations both when increasing or decreasing allocated processing resources.
FIG. 14 shows a flow diagram illustrating a deadlock scenario in processing thread migrations between two memory clusters. Assume two migration credits are allocated to memory cluster 320a from memory cluster 320b and two migration credits are allocated to the memory cluster 320b from the memory cluster 320a. Also assume that a single processing engine is handling migration work in each of the memory clusters 320a and 320b. Two processing threads, 1410 and 1420, are migrated from the memory cluster 320a to 320b and two other processing threads, 1415 and 1425, are migrated from the memory cluster 320b to 320a. The processing threads 1410 and 1420 want to migrate back to the memory cluster 320a, while the processing threads 1415 and 1425 want to migrate back to the memory cluster 320b. Also the processing thread 1430 wants to migrate to the memory cluster 320b and the processing thread 1435 wants to migrate to the memory cluster 320a. However each memory cluster, 320a or 320b, can handle a maximum of three processing threads at any point in time, e.g., one by the processing engine and two in the buffers indicated by the credits. Given that there are three processing threads in each memory cluster, none of the processing threads, 1410, 1415, 1420, 1425, 1430, or 1435, can migrate. As such, a deadlock occurs with none of the migration works proceeding. The deadlock is mainly caused by allowing migration loops where a processing may migrate back to memory cluster that it migrated from previously.
Wmax⁡(Int⁡(MN-1)+k)*2-1,
FIG. 15 shows graphical illustration of another approach to avoid deadlock. The idea behind approach to avoid deadlocks is to prevent any migrations loops where a migrating processing thread may migrate to a memory cluster from which it previously migrated. In the example shown in FIG. 15, migration of four different processing threads, 1510, 1520, 1530, and 1540, across the memory clusters 320a-320d are illustrated, with the memory cluster 320a assigned as a drain, or sink, memory cluster. A sink, or drain, memory cluster prevents a processing thread that migrated to it from another memory cluster to migrate out. In addition, a processing thread that migrated to a particular memory cluster may not migrate to another memory cluster from which other processing threads, e.g., of the same type, migrate to the particular memory cluster and therefore preventing migration loops. In other words, migrated processing threads may migrate to a sink memory cluster or memory cluster in a path to a sink memory cluster. A path to a sink memory cluster may not have structural migration loops. As illustrated in FIG. 15, such design, of migrations, prevent structural migration loops from occurring.
<- Previous Patent (Techniques for ident...) | Next Patent (Address space manage...) ->