CN1698031A - Methods to prefetch data/instructions associated with externally triggered events - Google Patents

Abstract

Method of prefetching data /instructions related to externally triggered events in a system including an infrastructure (18) having an input interface (20) for receiving data/ instructions to be handled by the infrastructure and an output interface (22) for transmitting data after they have been handled, a memory (14) for storing data/instructions when they are received by input interface, a processor (10) for processing at least some data/instructions, the processor having a cache wherein the data/instructions are stored before being processed, and an external source (26) for assigning sequential tasks to the processor. The method comprises the following steps which are performed while the processor is performing a previous task: determining the location in the memory of data/ instructions to be processed by the processor, indicating to the cache the addresses of these memory locations, fetching the contents of the memory locations and writing them into the cache, and assigning the task of processing the data/instructions to the processor.

Description

Methods to prefetch data/instructions associated with externally triggered events

technical field

The present invention relates generally to systems where an external source such as a scheduler in a network processor can interrupt a processor for a task where data/instructions are not relevant to a previous task, and in particular to prefetching Data/command methods associated with externally triggered events.

Background technique

The efficiency of modern microprocessors and microprocessor cores is very dependent on the efficiency of cache memories because instruction cycle times are much smaller than memory access times. A cache exploits the locality property of memory accesses, which is the fact that one memory access is more likely to be closer to previous accesses.

The cache contains a mechanism, the cache controller, for loading selected areas (cache lines) with new content, and in doing so, the cache reserves for this action by discarding old entries. out of space. The cache controller can currently be activated by software with cache prefetch instructions (eg, Data Cache Block Touch for all PowerPC compliant devices). Also, there are proposals for cache controllers to recognize regular access patterns for data structures such as linear strides or links. Unfortunately, existing methods do not cover externally triggered events, where the required memory content in these cases is independent of the preceding processing. In such cases, the only knowledge about the required memory contents is the source of the event, such as the source of the interrupt, the scheduler or other processor that assigned the task.

In systems where an external source, such as a scheduler in a network processor, can be interrupted for processing data unrelated to previously processed data, the processor generates a cache miss. This means that the processor stops processing until the data it needs is loaded from memory into cache memory. This wastes quite a bit of time. Thus, with current memory technology and a processor clock speed of 400MHz, each cache miss involves 36 processor clock cycles, which means about 40 instructions. Because current technology trends show that the increase in processor instruction rate is stronger than memory latency. Thus the number of lost instructions per cache hit miss increases.

Contents of the invention

Therefore, the main object of the present invention is to implement a method for prefetching data/instructions associated with external triggering events in order to avoid cache misses for data whose address can be easily determined.

The present invention thus relates to a method for prefetching data/instructions associated with external triggering events in a system comprising an infrastructure having means for receiving data/instructions to be processed by said infrastructure input interface, an output interface for sending data after they have been processed; memory, for storing data/instructions as they are received by the input interface; processor, for processing at least some of the data/instructions, said processing The processor has a cache memory, where data/instructions are stored before being processed; an external source, used to assign sequential tasks to the processor. The method comprises the following steps, which are performed while the processor is executing a previous task: determining the locations in memory of data/instructions to be processed by the processor; indicating addresses of these memory locations to a cache memory; fetching memory locations contents of locations and writes them into cache memory; tasks processors with processing data/instructions.

Description of drawings

By reading the following more specific description of the present invention in conjunction with the accompanying drawings, the above-mentioned and other objects, features and advantages of the present invention can be better understood, wherein:

Figure 1 is a block diagram of a network processing system in which the method according to the invention is implemented.

Figure 2 is a flow chart representing the steps of the method according to the invention.

Detailed ways

Such a system includes a processor core 10, such as a PowerPC processor core equipped with a data/instruction cache. The system is structured with a high performance bus 12, such as a Processor Local Bus (PLB), which provides connectivity to external memory 14, such as SDRAM, which includes data as well as a memory controller 16, the memory controller 16 provides bus structure independence from the memory by generating, for example, all necessary timing, refresh signals, etc.

Bus 12 and memory 14 are also used by infrastructure 18 , which processes data packets received on input interface 20 from the network. Infrastructure 18 manages reception and transmission including packet assembly, memory allocation and deallocation, and insertion and deletion from packet queues.

Some packets do not need to be processed and are sent directly over the network by the output interface 22 . Other packets need to be processed by processor 10 . A lookup and classification unit 24 makes a determination of whether a packet needs to be processed and what kind of processing needs to be performed. In order to process a data packet, the processor 10 needs several pieces of information. For this, it requires the header of the access packet and additional information generated in the infrastructure 18 . For example, the infrastructure may have several ports where packets can arrive, and the processor needs information on where the packets came from.

The scheduler 26 handles all data packets that need to be processed by the processors in one or several queues. These queues do not have to physically exist in the scheduler. At least the first item of each queue needs to be stored on-chip. This scheduler records processor behavior. When a processor has finished processing a packet, it requests a new task from the scheduler. However, if several queues with different priorities are managed, the scheduler 26 can also interrupt the processor's processing of low priority tasks and process higher priority tasks.

In any case, the scheduler 26 knows the next task that the processor 10 will process. The selected task determines which data will be accessed. In the case of the network processor described here, the relationship between the task (entry of the queue) and the address to be accessed first, ie packet header and additional information is very simple. The translation from the queue entry to a set of addresses is done by the address calculation unit.

When processor 10 processes new packets and accesses data such as packet headers, it typically generates a cache miss if the present invention is not used. This means that the processor will stop processing until the cache is loaded with the required data from the external memory 14, which, as mentioned above, wastes a lot of time. The cache memory prefetching according to the present invention avoids cache misses of data accesses that must occur, and addresses of cache misses can be easily determined.

In order to function, the instruction cache must be loaded with the required data before the access occurs. The initiation of this behavior comes from the scheduler, which uses a direct connection 28 to the cache memory. After having determined the location in memory where the packet header and additional information have been stored, the scheduler assigns an address to be fetched into the cache memory, and the cache memory controller fetches the data from memory into the cache memory middle. After this write is complete, either the scheduler interrupts the processor and allocates a new packet for processing when the new task has a higher priority than the previous task, or the scheduler waits for the previous packet before delivering the new packet. The completion of the task.

The method according to the invention is represented by the flow chart shown in FIG. 2 . First, the infrastructure waits to receive new data, ie data packets in the example (step 30). The headers of the packets are used for classification, and the headers and additional information resulting from the processing of the search and classification unit are stored in an external memory (step 32). The lookup and sort unit determines whether the packet needs to be processed by software and determines its priority (step 34). If the packet does not require processing, processing loops back to waiting for new data to be received (step 30).

When a data packet needs to be processed, the scheduler needs to calculate the address in memory that corresponds to the data that the processor is going to access. In the example it is the address of the packet header and of additional information such as classifier results, input ports (step 36). These addresses are then passed to the processor's data cache controller (step 38). The data cache controller writes the corresponding data into the data cache (step 40). This is done by interleaving the memory accesses created by the current packet processing.

At this stage, processing depends on whether the just arriving packet has a higher priority than the previous one (step 42). If so, the scheduler interrupts the previous task currently being executed by the processor (step 44), and allocates a new packet for processing, and the processor starts processing and finding the relevant data in the cache memory (step 46). If the new packet does not have a higher priority than the previous one, the processor must complete the previous processing (step 46) before processing the new packet (step 48).

Note that in the case of packets with higher priority, the scheduler needs to wait for the data cache fetch to complete before interrupting the processor. For this, the scheduler can observe the activity on the bus and wait until all allocated accesses have been completed. Alternatively, the scheduler may wait a fixed amount of time, or may use direct feedback from the cache controller to the scheduler.

It must also be noted that for two packets where the processing of the first packet is interrupted as described above in order to process the second higher priority packet, this should in both cases occur on disjoint parts of the cache memory. Otherwise, prefetched data can be deleted before it is accessed. This can be achieved by using a mapping in the processor from virtual addresses to real addresses, since caches are usually indexed using virtual addresses.

Although the method of the present invention has been described in the context of a network processor, it will be clear to those skilled in the art that the method can be used in any system where access to some data by the processor must occur and can be easily determine its address. In all cases, external events are connected to some data to be processed. Therefore, assume that in a robot that uses cameras for navigation, new images arrive at regular time intervals. The arrival of an image is the event, and the image data itself is the associated data that is prefetched.

It must be noted that for standard microprocessors, the address bus can be used as an external source, as it has been observed for cache coherency. In this case, only one external wire is required to indicate the prefetch request.

Claims (8)

1. the method for the data/commands that is associated with external trigger of in a system, looking ahead, described system comprises: foundation structure (18), and it has the input interface (20) that is used to receive the data/commands that will be handled by described foundation structure, the output interface (22) that is used for sending them after data are processed; Storer (14) is used for storage data/commands when data/commands is received by described input interface; Processor (10) is used to handle at least some described data/commands, and described processor has cache memory, and wherein data/commands was stored before processed; External source (26) is used for to described processor distribution sequence task;

Described method is characterised in that, it comprises the following steps, these steps are performed when carrying out previous task when processor:

Determining will be by the position of data/commands in described storer of described processor processing;

Indicate the address of described memory location to described cache memory;

Obtain the content of described memory location and they are write in the described cache memory;

Task to described processor distribution processing said data/instruction.

2. the method for claim 1, wherein said processor (10) is a network processing unit, and data to be processed are in the head of the packet that is received by described foundation structure (18).

3. method as claimed in claim 2, wherein said external source is a scheduler (26) that is directly connected to the described cache memory in the described processor (10), described scheduler is determined the position of data/commands to be processed in described storer (14), and directly indicates described address to described cache memory.

4. method as claimed in claim 3, wherein said scheduler (26) is determined the position of the described data/commands in described storer (14) by calculating described address.

5. as any one described method of claim 2-4, wherein the step of the task of the described prefetch data of allocation process/instruction comprises: interrupt the processing of previous grouping, begin to have than described previous grouping the processing of the new grouping of higher priority.

6. as any one described method of claim 3-5, wherein said cache memory is associated with a cache controller, described cache controller is responsible for obtaining its address by the content of the definite described memory location of described scheduler (26), and they are write in the described cache memory.

7. method as claimed in claim 5, wherein said processor (10) and described scheduler (26) use a processor local bus (PLB), described scheduler obtains the back and interrupts described processor determining to finish data caching, wherein by when data from described storer (14) monitor when returning described bus and accurately observation finish data caching and obtain.

8. system comprises by the adaptive device of realizing according to the step of the method for claim 1-7.

Images