BACKGROUND

1. Field

[0001] The present disclosure relates to network processor. More particularly, this invention is directed toward pre-fetching and processing work for processor cores in a network processor.

2. Description of Related Technology

[0002] A network processor is specialized processor, often implemented in a form of an integrated circuit, with a feature set specifically designed for processing packet data received or transferred over a network. Such packet data is transferred using a protocol designed, e.g., in accordance with an Open System Interconnection (OSI) reference model. The OSI defines seven network protocol layers (LI -7). The physical layer (LI) represents the actual interface, electrical and physical that connects a device to a transmission medium. The data link layer (L2) performs data framing. The network layer (L3) formats the data into packets. The transport layer (L4) handles end to end transport. The session layer (L5) manages communications between devices, for example, whether communication is half-duplex or full-duplex. The presentation layer (L6) manages data formatting and presentation, for example, syntax, control codes, special graphics and character sets. The application layer (L7) permits communication between users, e.g. , by file transfer, electronic mail, and other communication known to a person of ordinary skills in the art.

[0003] The network processor may schedule and queue work, i.e. , packet processing operations, for upper level network protocols, for example L4-L7, and being specialized for computing intensive tasks, e.g. , computing a checksum over an entire payload in the packet, managing TCP segment buffers, and maintain multiple timers at all times on a per connection basis, allows processing of upper level network protocols in received packets to be performed to forward packets at wire-speed. Wire-speed is the rate of data transfer of the network over which data is transmitted and received. By processing the protocols to forward the packets at wire- speed, the network services processor does not slow down the network data transfer rate.

[0004] To improve network processor efficiency, multiple cores are scheduled to carry the processing via a scheduling, module. An example of such network processor may be found in U.S. patent no. 7,895,431 , where the scheduling module is disclosed as a packet work order module.

[0005] However, with increasing frequency of the multiple processor cores, the amount of time spent in communicating with the scheduling module becomes an impediment to performance. Specifically, the latency between a processor asking for work and getting that work may be long, causing long latencies.

[0006] Accordingly, there is a need in the art for method and an apparatus, providing a solution to the above identified problems, as well as additional advantages.

SUMMARY

[0007] In an aspect of the disclosure, a method and an apparatus implementing the method for pre-fetching and processing work for processor cores in a network processor according to appended independent claims is disclosed. Additional aspects are disclosed in the dependent claims.

BRIEF DESCRIPTION OF THE DRAWINGS

[0008] The foregoing aspects described herein will become more readily apparent by reference to the following description when taken in conjunction with the accompanying drawings wherein:

[0009] FIG. 1 depicts a conceptual structure of a network processor in accordance with an aspect of this disclosure; [0010] FIG. 2a depicts a first part of a flow chart enabling a process of pre-fetching and processing work for processor cores in a network processor in accordance with an aspect of this disclosure; and

[0011] FIG. 2b depicts a second part of the flow chart enabling the process of pre-fetching work for processor cores in the network processor in accordance with the aspect of this disclosure.

[0012] Any unreferenced arrow or double-arrow line indicates a possible information flow between the depicted entities. An expression " X" in a reference indicates an instance of an element of a drawing.

DETAILED DESCRIPTION

[0013] Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by a person having ordinary skill in the art to which this invention belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and this disclosure.

[0014] As used herein, the singular forms "a," "an," and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms "comprise," "comprises," and/or "comprising," when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. The term "and/or" includes any and all combinations of one or more of the associated listed items.

[0015] Various disclosed aspects may be illustrated with reference to one or more exemplary configurations. As used herein, the term "exemplary" means "serving as an example, instance, or illustration," and should not necessarily be construed as preferred or advantageous over other configurations disclosed herein.

[0016] Various aspects of the present invention will be described herein with reference to drawings that are schematic illustrations of conceptual configurations of the present invention, unless explicitly noted. The various aspects of this disclosure are provided to enable a person having ordinary skill in the art to practice the present invention. Modifications to various aspects of a presented throughout this disclosure will be readily apparent to a person having ordinary skill in the art, and the concepts disclosed herein may be extended to other applications.

[0017] FIG. 1 depicts a conceptual structure of a network processor 100. A packet is received over a network (not shown) at a physical interface unit 102. The physical interface unit 102 provides the packet to a network processor interface 104.

[0018] The network processor interface 104 carries out L2 network protocol pre-processing of the received packet by checking various fields in the L2 network protocol header included in the received packet. After the network processor interface 104 has performed L2 network protocol processing, the packet is forwarded to a packet input unit 106.

[0019] The packet input unit 106 performs pre-processing of L3 and L4 network protocol headers included in the received packet, e.g., checksum checks for Transmission Control Protocol (TCP)/User Datagram Protocol (UDP). The packet input unit 106 writes packet data into a level L2 cache 108 and/or a memory 112. A cache is a component, implemented as a block of memory for temporary storage of data likely to be used again, so that future requests for that data can be served faster. If requested data is contained in the cache (cache hit), this request can be served by simply reading the cache, which is comparatively faster. Otherwise (cache miss), the data has to be recomputed or fetched from its original storage location, which is comparatively slower. The memory 112 may comprise any physical device(s) used to store instructions and/or data on a temporary or permanent basis. Any type of memory known to a person skilled in the art is contemplated. In an aspect, the memory 112 is external to the network processor 100 and is accessed via a memory controller 110. The packet input unit 106 supports a programmable buffer size and can distribute packet data across multiple buffers to support large packet sizes.

[0020] Any additional work, i.e. , another operation of additional packet processing, required on the packet data is carried out by a software entity executing on one or more processor cores 114. Although only two processor cores 114_1, 114_2 are shown, a person of ordinary skills in the art will understand that other number, including a single core is contemplated. Each of the one or more processor cores 114 is communicatively coupled to the L2 cache 108.

[0021] Work is scheduled by a Schedule, Synchronize, and Order (SSO) unit 116. Generally, work is a software routine or handler to be performed on some data. With regards to the SSO unit 116, work is a pointer to memory, where that memory contains a specific layout. In an aspect, the memory comprises the cache 108 and/or the memory 112. In an aspect, the layout comprises a work-queue entry storing the data and/or the instructions to be processed by the software entity executing on one or more of the processor cores 114, initially created by the packet input unit 106 or the software entity executing on each processor core 114. In an aspect, the work-queue entry may further comprise metadata for the work. In another aspect, the metadata may be stored in a work queue 122. In an aspect, the metadata may comprise a group- indicator, a tag, and a tag- type.

[0022] A person skilled in the art will appreciate that the SSO unit 116 comprises additional hardware units in addition to the hardware units explicitly depicted and described in FIG. 1 and associated text. Thus, reference to a step or an action carried out by the SSO unit 116 is carried out by one of such additional hardware units depending on a specific implementation of the SSO unit 116.

[0023] A group 120 comprises a collection of one of more work queues 121. Although only two groups are depicted, a person of ordinary skills in the art will understand that other number of groups is contemplated. Each group 121 is associated with at least one processor core 114. Consequently, when a software entity executing on the processor core 114 or the processor core 114 itself requests work, the arbitration does not need to be made for the groups 121 not associated with the processor core 114, improving performance. Although both the software entity and the processor core may be the requestor, in order to avoid unnecessary repetitiveness, in the reminder of the disclosure only the software entity is recited.

[0024] Because the number of the work queues is irrelevant for the subject-matter of this disclosure, only a single work queue, i.e. , admission queue is shown for simplicity; however, in addition to the admission queue 121, the group 120 may further comprise other queues, e.g. , a de- scheduled queue, a conflicted queue. Role of such queues is disclosed in a co-pending application no. 14/170,955, filed on February 3, 2014, by Wilson P. Snyder II, et al., entitled A METHOD AND AN APPARATUS FOR WORK PACKET QUEUING, SCHEDULING, AND ORDERING WITH CONFLICT QUEUING.

[0025] The admission queue 121 may comprise at least one entry comprising work, and, optionally, also a tag, and tag -type to enable scheduling of the work to one or more processor cores 114; thus allowing different work to be performed on different processor cores 114. By means of an example, packet processing can be pipelined from one processor core to another, by defining the groups from which a processor core 114 will accept work.

[0026] A tag is used by the SSO unit 116 to order, schedule, and synchronize the scheduled work, according to the tag and a tag-type selected by the processor core 114. The tag allows work for the same flow (from a source to a destination) to be ordered and synchronized. The tag- type selects how the work is synchronized and ordered. There are three different tag-types. Ordered, i.e. , work ordering is guaranteed, however, atomicity is not. Such a tag-type may be used during a de-fragmentation phase of packet processing, so that fragments for the same packet flow are ordered. Atomic i.e. , work ordering and atomicity are guaranteed, in other words, when two work items have the same tag, the work must be processed in order, with the earlier work finishing before the later work can begin. Such a tag-type may be used for IPSec processing to provide synchronization between packets that use the same IPSec tunnel. Thus, IPSec decryption is carried out with atomic tag-type. Untagged, i. e. , work ordering among the processor cores is not guaranteed, and the tag is not relevant with this tag-type. Such a tag may be used for processing different packet flows, which will likely have different tags, so will likely not be ordered and synchronized relative to each other, and can be executed completely in parallel on different processor cores 114.

[0027] Work queue entry may be created by hardware units, e.g. , the packet input unit 106, in the memory 112. The add work request may then be submitted to the SSO unit 116 via an add- work entity 118. Alternatively, work queue entry may be created and add work request may be submitted by a software entity running at a processor core 114. In an aspect, work queue entry is created and add work request is submitted via the add-work entity 118 upon each packet arrival. In other aspects, work queue entry may be created upon completion of sending a packet, completion of compressing/decompressing data from a packet, and/or other events known to person of ordinary skills in the art.

[0028] Upon receiving the add work request, the SSO unit 116 adds the work, the tag, and the tag -type associated with the work into an admission queue 121 corresponding to the group 120 indicated by the add work request. In an aspect, the admission queue 121 may overflow to the cache 108 and/or the memory 112.

[0029] Software entity executing on processor cores 114, may request work from the SSO unit 116 via work-slot structures 126. The work-slot structure 126 comprises a memory. As disclosed supra, the work request indicates one or more groups associated with the processor cores 114; consequently, only those groups need to be arbitrated among. In response to the request, a get-work arbiter 122 arbitrates among the groups 120, associated with the requesting processor core 114, which have work in one of the admission queues 121, evaluates tags of the work at the top of the admission queue 121, selects one of the admission queues 121 and provides the work into the work-slot structure 126 corresponding to the requesting processor core 114 as disclosed in detail infra. Additionally, the get- work arbiter 122 provides the tag, and tag- type associated with the work to a memory, which is a part of a tag-chain manager interfacing the memory with other elements of the network processor 100. Any type of memory known to a person skilled in the art is contemplated. In an aspect, the memory comprises a Content Addressable Memory (CAM). The tag-chain manager 124 thus assists the SSO unit 116, to account for work that cannot be processed in parallel due to ordered or atomic requirements by keeping track of tags corresponding to the work being provided into the work-slot structure 126; therefore, knowing what work each processor core 114 is acting upon.

[0030] Each of the work-slots structures 126 comprises at least two work-slots 126 X X. One of the work-slots, e.g., work-slot 126_1_1, in the work-slots structures 126_1, may contain the work that is presently pending in the corresponding processor core 114_1; another of the work-slots, e.g., work-slot 126_1_2 may contain the work that is pre-fetched for processing, commencing after the presently pending work, i.e., work in the work slot 126_1_2, is finished at the processor core 114_1. Consequently, the processor core 114_1 may commence processing the pre-fetched work immediately after completing processing of the presently pending work; thus avoiding or mitigating latencies. Although only one pre-fetched work-slot are shown, a person skilled in the art will understand that more than one pre-fetched work-slot is contemplated.

[0031] Reference is made to FIG. 2, depicting a flow chart enabling the process of prefetching and processing work for processor cores in a network processor in accordance with an aspect of this disclosure. To clarify the relationship between certain elements of a conceptual structure and information flow among the elements of the structure enabling the process of prefetching and processing work for processor cores in a network processor depicted in FIG. 1, in the FIG. 2 description the references to structural elements of FIG. 1 are in parenthesis.

[0032] In step 202, a software entity executing on one of the processor cores (114) is ready to obtain work to process. The software entity executing on, e.g. , the processor core (114_1) issues a GET WORK requesting work from the SSO unit (116) via the associated work-slot structure (126_1). As disclosed supra, the work request indicates one or more groups associated with the processor core (114_1); consequently, only those groups need to be arbitrated among. In an aspect, the GET WORK request is initiated by a load instruction to an input/output (I/O) address. In another aspect, the GET WORK request is initiated by a store instruction and returned into a memory location specified by the processor core (114_1). The process continues in step 204. In step 204, the SSO unit (116) determines whether a pre-fetched work is ready for the processor core (114_1) by determining whether all the pre-fetched work-slots (121_1_2) comprise prefetched work. In an aspect, the SSO unit (116) examines content of all the pre-fetched work-slots (126_1_2). In another aspect, the SSO unit (116) examines for all the pre-fetched work-slots (126_1_2) an associated bit indicating whether a particular pre-fetched work-slot (126_1_2) is empty or not empty.. When the determination is affirmative, i.e. , none of the pre-fetched work- slot (126_1_2) is not empty, thus comprising the pre-fetched work, the processing continues in step 206; otherwise, the processing continues in step 208.

[0033] In step 206, the SSO unit (116) provides the pre-fetched work and when a tag and a tag-type associated with the pre-fetched work exists also the tag and the tag-type from the prefetched work-slot (126_1_2) to the work-slot (126_1_1), and deletes the pre-fetched work and when a tag and a tag-type associated with the pre-fetched work exists also the tag and the tag- type from the pre-fetched work-slot (126_1_2). The processing continues in step 216.

[0034] In step 216, the work-slot (126_1_1) provides the work to the processor. In an aspect, providing corresponds to the load instruction to an input/output (I/O) address.

[0035] In step 208, the arbiter (122) searches for work by determining whether any of the groups (120) associated with the processor core (114_l)have work in the admission queue (121) and may thus bid, i.e. , participate in an arbitration. The get- work arbiter (122) arbitrates among only the groups (120) that have work in the admission queue (120) to select one group (120), from which work will be provided to the work-slot (126_1_1) and, eventually, to the software entity executing the processor core (114_1). A person of ordinary skills in the art will understand that any arbitration employed by the arbiter (122) known in the art may be used, e.g., a round- robin process. A novel arbitration that may be employed by the arbiter (122) is disclosed in a copending application no. 14/171 ,108, filed on February 3, 2014, by Wilson P. Snyder II, et al., entitled A METHOD AND AN APPARATUS FOR WORK REQUEST ARBITRATION IN A NETWORK PROCESSOR. The processing continues in step 210.

[0036] In step 210, the SSO unit (116) determines whether the arbiter (122) found work for the processor core (114_1). When the determination is affirmative, the processing continues in step 212; otherwise, the processing continues in step 214.

[0037] In step 212, the arbiter (122) via the SSO unit (116) provides the found work and when a tag and a tag-type associated with the found work exists also the tag and the tag-type to the work-slot (126_1_1). The processing continues in step 216.

[0038] In step 214, the SSO unit (116) provides an indicator that no work has been found to the processor core (114_1). In an aspect where the load instruction to an input/output (I/O) address was used to GET WORK, a specific data value indicating no-work are returned to the load instruction; otherwise, a flag is set, which the processor core (114_1) may read at a later time . The processing continues in step 218.

[0039] In step 218, the software entity executing on the processor core (114_1), determines whether a work has been provided. When the determination is negative, the software entity may enter a low power mode, carry-out non-work related processing, or may issue another GET WORK request as disclosed in step 202. The non-work related processing comprises any processing not handled via the SSO unit (116). By means of an example, such non-work may comprise user processes, kernel processes, or other processes known to a person of ordinary skills in the art. When the determination is affirmative, the processing continues in step 220.

[0040] In step 220, the software entity executing on the processor core (114_1) processes the work. This usually involves using the work in the work-slot (126_1_1) as a pointer to a work- queue entry stored in a cache (108) and/or a memory (112). The SSO unit (116) determines a range of addresses starting at the pointer to be dereferenced and read from the data structure stored in the cache (108) or loaded from the memory (112) into the cache (108).

[0041] When the work-queue entry is being accessed for the first time, reading the work- queue entry is slow due to the fact that the cache (108) does not yet contain the instructions and/or the data, and accessing the memory (112) is slow because the memory (112) may be physically distant from the network processor (100). However, pre-fetching increases the probability that the dereferenced range of addresses indicates that the work-queue entry is already in the cache (108), which yields faster access than memory (112) as disclosed supra. The processing continues in step 222.

[0042] In step 222, to accelerate next work, the software entity executing on the processor core (114_1) issues a PRE-FETCH WORK, requesting work to be pre-fetched to the SSO unit (116) via the associated work-slot structure (126_1).. As with the GET WORK, the processor core may also be a requestor. The PRE-FETCH WORK request may be issued before the currently processed work is finished. In an aspect, the PRE-FETCH WORK request is a store instruction to an I/O address. While the pre-fetch process disclosed in the following steps 224- 238 is being carried out by the SSO unit (116), the software entity executing at the processor core (114_1) may carry out previous work, and/or other processes, e.g. , process non-work related tasks, as disclosed supra; therefore, improving efficiency of the network processor (100).

[0043] If the software entity executing at the processor core (114_1) finishes these other processes before the SSO unit (116) completes the pre-fetch process, the software entity may issue another GET WORK request as disclosed in step 202 supra.. The requested work and the requested pre-fetch work are handled by the SSO unit (116) as disclosed in the flow chart and related text. The processing continues in step 224.

[0044] In step 224, the SSO unit (116) determines whether additional work may be accepted, therefore, pre-fetched for the processor core (114_1) by determining whether all the pre-fetched work-slots (121_1_2) comprise pre-fetched work. In an aspect, the SSO unit (116) examines content of all the pre-fetched work-slots (126_1_2). In another aspect, the SSO unit (116) examines for all the pre-fetched work-slots (126_1_2) an associated bit indicating whether a particular pre-fetched work-slot (126_1_2) is empty or not empty. When the determination is affirmative, the processing continues in step 226; otherwise, the processing continues in step 228.

[0045] In step 226, the SSO unit (116) completes the current process. In another aspect, the SSO unit (116) further generates an error interrupt. The interrupt is signaled to a software entity at the network processor (100), which logs the error to indicate a programming flaw. In either aspect, the processing continues in step 202.

[0046] In step 228, the arbiter (122) searches for work by the same process as disclosed in step 208 supra. The processing continues in step 230.

[0047] In step 230, the SSO unit (116) determines whether the arbiter (122) found work for the processor core (114_1). When the determination is negative, the processing continues in step 231 otherwise, the processing continues in step 232.

[0048] In step 231, the SSO unit (116) completes the current process. The processing continues in step 202.

[0049] In step 232, the arbiter (122) via the SSO unit (116) provides the found work to the pre-fetch work-slot (126_1_2). In an aspect, the pre-fetch work may comprise a "tag". The processing continues in step 234.

[0050] In step 234, the SSO unit (116) determines whether a tag associated with the found work exists. When the determination is affirmative, the processing continues in step 236; otherwise, the processing continues in step 238.

[0051] In step 236, the SSO unit (116) compares the tag of the found work against a tag for another work scheduled for the same processor core (114_1). When the comparison indicates that the pre-fetched work is atomic or ordered with respect to the another work, the processing continues in step 238; otherwise, the processing continues in step 231. [0052] In step 238, when all the work ahead of the pre-fetched work has been processed, the software entity executing on the processor core (114_1) processes the work. The SSO unit (116) provides the pre-fetched work and when a tag and a tag-type associated with the pre-fetched work exists also the tag and the tag-type from the pre-fetched work-slot (126_1_2) to the work-slot (126_1_1), and deletes the pre-fetched work and when a tag and a tag-type associated with the pre-fetched work exists also the tag and the tag-type from the pre-fetched work-slot (126_1_2). The SSO unit (116) determines a range of addresses starting at the pointer to be derefernced and read from the data structure stored in the cache (108) or loaded from the memory (112) into the cache (108).

[0053] In an aspect, the range of addresses are physical addresses; in another aspect, the range of addresses are a virtual memory addresses which is translated using the virtual memory context of the software entity which requested the GET WORK or the PRE-FETCH WORK. This happens without the processor core (114_1) being aware of the pre-fetching. In an aspect the processor's PRE-FETCH WORK can selectively enable this pre-fetching. The processing continues in step 202.

[0054] The various aspects of this disclosure are provided to enable a person having ordinary skill in the art to practice the present invention. Various modifications to these aspects will be readily apparent to persons of ordinary skill in the art, and the concepts disclosed therein may be applied to other aspects without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the aspects shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

[0055] Therefore, by means of an example a person having ordinary skill in the art will understand, that the flow chart is not exhaustive because certain steps may be added or be unnecessary and/or may be carried out in parallel based on a particular implementation.

[0056] All structural and functional equivalents to the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the various aspects described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the claims. Such illustrative logical blocks, modules, circuits, and algorithm steps may be implemented as electronic hardware, computer software, or combinations of both.

[0057] Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

[0058] Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the claims. No claim element is to be construed under the provisions of 35 U.S.C. § 1 12, sixth paragraph, unless the element is expressly recited using the phrase "means for" or, in the case of a method claim, the element is recited using the phrase "step for."