Patent Description:
<CIT> discloses a method comprising: receiving input data comprising a number of read and write uncached transactions, a transaction density, a number of active cores (N active cores) of the at least two cores, main memory address layout, and number of and an identifier for each of: banks and ranks in main memory, interconnects, cache pools, and memory controllers; defining all sets of active cores; defining up to N sets of memory pools; performing, for combinations of at least one set of active cores with each of at least one subset, the specified number of read and write uncached transactions with main memory at a specified transaction density for each defined combination of each active core combination and each defined memory pools; measuring the execution time of such performance for each combination; storing the execution time for each combination; and identifying at least one combination having a lower execution time.

<NPL>) discloses a software-only mechanism to partition both compute and memory resources of a GPU to allow parallel execution of GPU workloads with performance isolation.

<CIT> discloses a method comprising dividing a main memory into a plurality of pools, the plurality of pools including a first pool and one or more second pools, wherein the first pool is only associated with a set of one or more lines in a first cache such that data in the first pool is only cached in the first cache and wherein the one or more second pools are each associated with one or more lines in a second cache and data in the second cache is cacheable by the first cache.

<CIT> discloses a system having one or more caches coupled to a shared memory through a communications medium, a method for inserting information into a particular cache includes specifying curiosity region to be monitored independent of cache content and prior access to the curiosity regions; monitoring operations with the shared memory to identify curiosity regions; and writing information from the communications medium into the associated cache.

<CIT> discloses a computing system comprising at least one processing unit, at least one memory controller in communication with the processing unit, and a main memory in communication with the processing unit through the memory controller. A memory hierarchy of the computing system includes at least one cache, the memory controller, and the main memory. The memory hierarchy is divided into a plurality of memory pools. The main memory comprises a set of memory modules split in ranks each having a rank address defined by a set of rank address bits. Each rank has a set of memory devices comprising one or more banks each having a bank address defined by a set of bank address bits. A plurality of threads execute on the processing unit, and are assigned to the memory pools based on one or more memory partitioning techniques, including bank partitioning, rank partitioning, or memory controller partitioning.

The present invention is defined by the independent claim, to which reference should now be made.

In one example, a computing system includes at least one central processing unit, one or more central processing unit caches, and a main memory comprising a plurality of locations. Each location of the plurality of locations maps to a set in the one or more central processing unit caches. A first subset of locations of the plurality of locations are partitioned for one or more threads of a first application and assigned to non-contiguous memory locations of the main memory based on a respective set of one or more sets in the one or more central processing unit caches to which each location is mapped. The computing system further includes a first input/output (I/O) device configured to store data in a second subset of locations of the plurality of locations that are different from the first subset of locations partitioned for the one or more threads of the first application. The second subset of locations are non-contiguous memory locations of the main memory that are separated in address space according to a predefined pattern.

Understanding that the drawings depict only some embodiments and are not therefore to be considered limiting in scope, the exemplary embodiments will be described with additional specificity and detail using the accompanying drawings, in which:.

In accordance with common practice, the various described features are not drawn to scale but are drawn to emphasize specific features relevant to the example embodiments.

In the following detailed description, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration specific illustrative embodiments. However, it is to be understood that other embodiments may be utilized, and that logical, mechanical, and electrical changes may be made. Furthermore, the method presented in the drawing figures and the specification is not to be construed as limiting the order in which the individual steps may be performed. The following detailed description is, therefore, not to be taken in a limiting sense.

Modern computing platforms in the avionics domain are characterized by their timing non-determinism because there might be multiple sources of memory interference (e.g., processor cores, Direct Memory Accesses (DMAs), graphics processing unit (GPU), and specialized co-processors). The timing non-determinism makes the application WCET difficult to determine. In a modern computing platform, the application WCET is often empirically measured by introducing cross-interference to the shared hardware resources. An example of a shared hardware resource can be for example the memory hierarchy - memory buses, caches, memory controllers, and DDR memory. One effective means to bound interference between applications and thus reduce its WCET is to partition/isolate by allocating a dedicated hardware shared resources to specific application(s). For example, to eliminate the cache interference, some systems, such as those described in <CIT> (hereinafter "the '<NUM> patent") partition the cache by using of memory pools.

When using memory pools for threads of an application as described in the '<NUM> patent, the memory allocated to each application is not contiguous. For example, one application may be allocated every 16th memory page, and the next application may be allocated the next page and every 16th memory page from that page. Each cache-unique set of pages is considered as a cache partition. Memory pools typically encompass one or more cache pools according to the cache and memory needs of the applications. The memory management unit (MMU) of the processor is configured to make any set of pages allocated to an application appear to be contiguous to the application, so the application sees a virtual address space that is contiguous even though the allocated underlying physical memory region is not contiguous.

It is desirable to enable applications, and the computing system generally, to interact with a file system and receive data from outside sources. Typically, input/output (I/O) devices (for example, DMA engines, GPUs, or co-processors) save data in the main memory using physically contiguous memory regions, which are only compatible with a computing system utilizing memory pools if these regions are uncached from the processor's perspective. This is because accesses to such regions by an application would pollute many or all of the memory pools by evicting data when reading or by leaving dirty data behind in pools in which the application has no quota. This is because these contiguous regions, if more than a page in size, will cut across the cache partitions allocated to each application. To avoid interference with the memory pools in the cache, these computing systems utilizing memory pools typically allocate shared I/O data to uncached memory regions even if the IO device is capable of snooping the CPU's cache. Accesses by CPU cores to uncached memory regions to read or write I/O data are much slower than to cached regions, so while necessary to protect the integrity of the cache partitioning, performance is impacted by this strategy.

The example systems and methods described herein enable a computing system using memory pools to interact with I/O devices that respect an existing CPU cache partitioning strategy. By using the techniques described herein, cache effects associated with DMA operations can be constrained to a single memory pool, and CPU accesses to the I/O memory space can be performed using fast cached accesses rather than slow uncached accesses. This yields a reduction in WCET for the application accessing the I/O resource. Also, since cache effects are limited to one memory pool, applications utilizing other memory pools see no impact to their cache state, thus their WCET is unaffected. As a result, platform performance is improved when utilizing an I/O device (for example, an I/O device such as DMA, GPU, or co-processor).

<FIG> illustrates a block diagram of an example computing system <NUM>. In the example shown in <FIG>, the computing system <NUM> includes at least one central processing unit (CPU) <NUM>, one or more CPU caches <NUM>, a main memory <NUM>, and one or more input/output (I/O) devices <NUM>.

In the example shown in <FIG>, the computing system includes multiple CPUs <NUM> that share memory resources (CPU cache <NUM> and main memory <NUM>). In some examples, the computing system <NUM> includes a microprocessor chip <NUM> that includes N CPUs, or cores, which are capable of executing one or more threads in parallel. Each CPU is coupled to at least a CPU cache <NUM> (for example, level <NUM> (L1) cache). The CPU cache <NUM> contains memory and computing logic, and the CPU cache <NUM> is coupled to main memory <NUM>. In some examples, the main memory <NUM> can also be coupled to secondary storage (not shown). The CPU cache <NUM> in the computing system is generally a smaller, faster memory than main memory <NUM>.

It should be understood, however, that the configuration shown in <FIG> and other arrangements and processes described herein are set forth for purposes of example only, and other arrangements and elements (e.g., machines, interfaces, functions, orders of elements, etc.) can be added or used instead. Further, as in most computer architectures, those skilled in the art will appreciate that many of the elements described herein are functional entities that may be implemented as discrete components or in conjunction with other components, in any suitable combination and location. For example, the computing system <NUM> may consist of multiple independent CPU busses so that each CPU can access the CPU cache <NUM> and other components without contending for a CPU bus with the other CPUs. Furthermore, the computing system <NUM> may include more than one cache (for example, an L2 and/or L3 cache), which may be either within the microprocessor chip <NUM> or part of another chip in the computing system <NUM>. Even further, a system may contain multiple independent main memories and secondary storages, not shown in <FIG>. Each unit of memory in the computing system <NUM> may comprise semiconductor memory, magnetic memory, optical memory, acoustic memory, biological memory, or any combination of these memory technologies, or any other memory technology used in conjunction with computational devices.

The purpose of the CPU cache <NUM> in the computing system <NUM> is to temporarily hold instructions, data, or both, that are being used by tasks executing on one of CPUs <NUM>. As is known to those skilled in the art, patterns of computer memory access exhibit both spatial and temporal locality of reference. That is, once a main memory <NUM> location is accessed, it is likely that a nearby main memory location will also be accessed, and it is also likely that main memory <NUM> location will again be accessed soon. Thus, it is advantageous to store data from recently accessed main memory locations and their neighboring locations in a fast-memory cache, such as CPU cache <NUM>, because it is likely that a CPU <NUM> will once again have to access one of those main memory locations. By storing the data from main memory locations in the CPU cache <NUM>, the system avoids the latency of having to access main memory <NUM> or any secondary storage to read the data.

While the basic unit of storage in many programming languages is the byte (<NUM> bits), most CPUs <NUM> use a unit of operation that is several bytes. For example, in a <NUM>-bit microprocessor, memory addresses are typically <NUM> bits wide. Thus, for main memories that are byte-addressable, a <NUM>-bit microprocessor can address <NUM><NUM> (<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>) individual bytes (<NUM> exabytes), where those bytes are numbered <NUM> through <NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>, for example. Due to spatial locality of reference, most microprocessors cache main memory <NUM> in groups of bytes called "cache lines. " Each cache line is a fixed number of contiguous bytes. For example, a <NUM>-bit microprocessor might have a cache line size of <NUM> bytes, which means that when a byte from main memory <NUM> is fetched into the CPU cache, the rest of the cache line is brought into CPU cache <NUM> as well.

Regardless of the mechanics of memory accesses, the fact that CPU cache <NUM> is typically much smaller than main memory <NUM> means that not all main memory locations can be simultaneously resident in CPU cache <NUM>. In order to maintain performance, CPU cache <NUM> typically will execute a simple operation to map a main memory location to a limited number of CPU cache locations (cache associativity). In some examples, the computing system <NUM> is configured to avoid cache related interference between applications being executed by the CPUs <NUM> using similar techniques to those described in the '<NUM> patent. For example, the computing system <NUM> is configured to store one or more threads of respective applications in main memory locations that map to respective portions of the CPU cache <NUM>.

In the example shown in <FIG>, the one or more I/O device <NUM> are communicatively coupled to the main memory <NUM> and configured to read/write data to/from the main memory <NUM>. In some examples, at least one I/O device <NUM> is also communicatively coupled to the CPU <NUM> and/or the CPU cache <NUM>. The one or more I/O devices <NUM> can be a DMA engine, a GPU, co-processor, or a hardware accelerator utilized by the computing system <NUM>.

As discussed above, typical approaches for I/O data storage cannot be used when utilizing the memory pools for applications discussed in the '<NUM> patent. The one or more I/O devices <NUM> of the computing system <NUM> are configured to store data in the main memory <NUM> in a manner that does not interfere with the memory pools for the applications that are executed by the CPUs <NUM>. <FIG> illustrate diagrams of example patterns of non-contiguous memory locations of the main memory <NUM> for different I/O scenarios. It should be understood that some connections between components are omitted from <FIG> for ease of illustration, and that the features included in <FIG> could also be included in <FIG>.

Typically, an I/O device <NUM> is configured to directly write/read data to/from the physical memory. In the examples shown in <FIG>, the I/O device <NUM> is directly communicatively coupled to the main memory locations <NUM>-<NUM>, <NUM>-<NUM>, and the I/O device <NUM> is configured to directly write/read I/O data to/from the main memory locations <NUM>-<NUM>, <NUM>-<NUM> via the link between the I/O device <NUM> and the main memory locations <NUM>-<NUM>, <NUM>-<NUM>.

In some examples, the most recent memory requests are cached prior to be written to the main memory <NUM>. In the examples shown in <FIG>, the I/O device <NUM> is communicatively coupled to the cache <NUM>, and the I/O device <NUM> is configured to cache the I/O data via the link between the I/O device <NUM> and the cache <NUM>. In such examples, the I/O data is included in the cache <NUM> and only then the cached I/O data is written to the main memory <NUM>.

In some examples, the CPUs <NUM> are configured to perform uncached memory transfers in certain situations. In the examples shown in <FIG>, the CPUs <NUM> are communicatively coupled to the virtual address space <NUM>-<NUM>, <NUM>-<NUM>, and the CPUs <NUM> are optionally configured to write/read data with uncached memory transfers via the link between the CPUs <NUM> and the virtual address space <NUM>-<NUM>, <NUM>-<NUM>.

In the examples shown in <FIG>, the CPUs <NUM> are communicatively coupled to the I/O device <NUM>. In some examples, the link from the CPUs <NUM> to the I/O device <NUM> is used for control and particularly where the CPUs <NUM> are the master and the I/O device <NUM> is the slave in the computing systems shown. In some examples, the line from the I/O device <NUM> to the CPUs <NUM> is optionally included and can be used for signaling (for example, through interrupts) the CPUs <NUM> when data transfer is completed by the I/O device.

In the example shown in <FIG>, the I/O device <NUM> is configured to have its own memory pool(s) that is distinct from the memory pools for an application (Application A in <FIG>) executed by the CPUs <NUM>. In such examples, the I/O device <NUM> is configured to store I/O data in a subset of locations <NUM>-<NUM> of the main memory <NUM> that map to different memory pools of the CPU cache <NUM> than those that are allocated to one or more threads of the application. The subset of locations where the I/O device <NUM> stores the I/O data are non-contiguous memory locations <NUM>-<NUM> of the main memory <NUM> and the locations are separated in address space according to a predefined pattern that is different than the pattern used for storing the one or more threads of the application in non-contiguous memory locations <NUM>-<NUM>. In such examples, the non-contiguous memory locations allocated for the I/O data from the I/O device <NUM> will be included in a separate and distinct memory pool than the memory pool for the application.

In the example shown in <FIG>, at least one of the I/O devices <NUM> is configured to be a private I/O device <NUM> for a specific application (Application A in <FIG>) executed by the CPU(s) <NUM> and share the cache partition and memory pool with the specific application. In such examples, the I/O device <NUM> is configured to store I/O data in a subset of locations of the main memory <NUM> that map to the portions of the CPU cache <NUM> partitioned for the specific application. The subset of locations <NUM>-<NUM> where the I/O device <NUM> stores the I/O data are non-contiguous memory locations <NUM>-<NUM> of the main memory <NUM> and the locations are separated in address space according to a predefined pattern that is the same as the pattern used for storing the one or more threads of the specific application in non-contiguous memory locations <NUM>-<NUM>. In such examples, the non-contiguous memory locations allocated for the I/O data from the I/O device <NUM> will be included in the CPU cache partition for the specific application.

In the example shown in <FIG>, two or more of the I/O devices <NUM>-<NUM>, <NUM>-<NUM> are configured to be private I/O devices <NUM> for a specific application (Application A in <FIG>) executed by the CPU(s) <NUM> and share the cache partition and memory pool with the specific application. In such examples, the I/O devices <NUM>-<NUM>, <NUM>-<NUM> are configured to store I/O data in respective subsets of locations of the main memory that map to the portions of the CPU cache <NUM> partitioned for the specific application. The subset of locations <NUM>-<NUM> where the I/O device <NUM>-<NUM> stores the I/O data are non-contiguous memory locations <NUM>-<NUM> of the main memory <NUM> and the locations are separated in address space according to a predefined pattern that is the same as the pattern used for storing the one or more threads of the specific application in non-contiguous memory locations <NUM>-<NUM>. Similarly, the subset of locations where the I/O device <NUM>-<NUM> stores the I/O data are non-contiguous memory locations <NUM>-<NUM> of the main memory <NUM> and the locations are separated in address space according to a predefined pattern that is the same as the pattern used for storing the one or more threads of the specific application in non-contiguous memory locations <NUM>-<NUM>. In such examples, the non-contiguous memory locations allocated for the I/O data from the I/O devices <NUM>-<NUM>, <NUM>-<NUM> will be aligned to the memory pool for the specific application.

In some examples, at least one of the I/O devices <NUM> is configured to be shared by two or more applications executed by the CPU(s) <NUM>. In such examples, the I/O device <NUM> is configured to store I/O data in a subset of locations of the main memory that map to the portions of the CPU cache <NUM> partitioned for each respective application. For example, a first subset of locations where the I/O device <NUM> stores the I/O data are non-contiguous memory locations of the main memory <NUM> and the locations are separated in address space according to a predefined pattern that is the same as the pattern used for storing the one or more threads of a first application in non-contiguous memory locations, and a second subset of locations where the I/O device <NUM> stores the I/O data are non-contiguous memory locations of the main memory <NUM> and the locations are separated in address space according to a predefined pattern that is the same as the pattern used for storing the one or more threads of a second application non-contiguous memory locations. In such examples, the first and second subsets of non-contiguous memory locations allocated for the I/O data from the I/O device <NUM> will be included in the cache partition for the first and second applications, respectively.

The one or more I/O devices <NUM> can be configured to operate in different operational modes that enable I/O data to be read from and write to the non-contiguous memory locations of the main memory <NUM>. In some examples, the one or more I/O devices <NUM> are configured to operate in a linked-list descriptor mode. A linked-list descriptor mode includes reading/writing data to different addresses using pointers that indicate where data is to be read/written next. Rather than starting at a particular address and reading/writing data to contiguous memory locations in a sequential manner, a linked-list descriptor mode enables the I/O device <NUM> to store I/O data in non-contiguous memory locations of the main memory <NUM> as defined in the linked-list.

In some examples (such as the linked list descriptor technique described above), the computing system <NUM> is configured to utilize software-only to enable the one or more I/O devices <NUM> to respect the memory pools of the one or more applications executed by the CPU(s) <NUM>. In some examples, the CPUs <NUM> are configured to call an I/O device <NUM> to perform a data transfer. In the software-only implementations, the predefined non-contiguous memory access pattern utilized by the I/O device <NUM> can be stored in the main memory <NUM>. In some such examples, the predefined non-contiguous memory access pattern is represented as a linked-list, and the one or more I/O devices <NUM> are configured to retrieve the linked-list descriptors from the main memory <NUM> prior to each time the I/O devices <NUM> input data to the main memory <NUM> in order to determine where to store the I/O data. In some examples, the descriptor tables in the main memory are precomputed for particular page masks, but the source and destination addresses need to be taken into account or computed.

In some examples, the computing system <NUM> utilizes specialized hardware and software to enable the I/O devices <NUM> to respect the memory pools of the one or more applications executed by the CPU(s) <NUM>. Similar to the software-only configuration, the CPUs <NUM> can be configured to command an I/O device <NUM> to perform a data transfer. However, in some specialized hardware and software examples, the one or more I/O devices <NUM> are configured to interact with a memory management unit (MMU) of the computing system <NUM> in order to access the page table used for the computing system <NUM> rather than retrieving the non-contiguous memory access pattern (for example, linked-list descriptors) from the main memory <NUM>. For example, the MMU can be configured to partition the CPU cache <NUM> and main memory <NUM> for different CPUs <NUM> and/or CPU cores, and the MMU can be configured to provide information regarding the CPU cache partitions and memory pools to the one or more I/O devices <NUM>. In some examples, the I/O device <NUM> is configured to query the CPU's MMU or a special purpose I/O MMU and the MMU is configured to return the memory addresses that the I/O device <NUM> can access for reading/writing I/O data to the main memory <NUM>. In some such examples, the translation lookaside buffer (TLB) of the MMU can include the linked-list descriptors and the I/O device <NUM> can be provided access to the TLB. In other examples, the I/O device <NUM> is configured to perform a continuous read/write and the MMU is configured to save the I/O data to the particular non-contiguous locations of the main memory <NUM>. In some examples, the computing system <NUM> includes an I/O MMU configured to provide I/O address translation for I/O data to/from the I/O device <NUM>.

In other examples of using specialized hardware and software, the I/O device <NUM> is configured to interact with the microprocessor chip <NUM> directly via a specialized interface. In some such examples, the I/O device <NUM> is configured to determine the predefined pattern either from an I/O configuration interface or directly from the processor architecture. In some such examples, the I/O device <NUM> includes a set of registers that includes the page mask, the source and destination addresses, and bytes to be read/written. In such examples, the I/O device <NUM> is configured to determine the predefined pattern (for example, using logic, state machines, etc.) based on the information in the set of registers (for example, using the page mask and destination address).

In some examples, the I/O device <NUM> or other component of the computing system <NUM> is configured to automatically copy the I/O data that is saved in the non-contiguous memory locations of the main memory <NUM> to the CPU cache <NUM>. In such examples, the CPU(s) <NUM> would be enabled to access the I/O data more quickly than if the CPU(s) had to read the data from the main memory <NUM> into the CPU cache <NUM>.

<FIG> illustrates a flow diagram of an example method <NUM> for data input/output for a computing system utilizing memory pools. The common features discussed above with respect to computing system <NUM> with respect to <FIG> can include similar characteristics to those discussed with respect to method <NUM> and vice versa. In some examples, the method <NUM> is performed using one or more components of the computing system <NUM>.

The method <NUM> includes dividing the CPU cache into a plurality of memory pools (block <NUM>). In some examples, the CPU cache is divided such that each application executed by the CPUs of a computing system has a respective memory pool assigned to it.

The method <NUM> further includes dividing the main memory into a plurality of locations that map to the memory pools (block <NUM>) and assigning one or more threads of a first application to a first subset of the plurality of main memory locations associated with a first memory pool (block <NUM>). In some examples, the first subset of the plurality of main memory locations is a non-contiguous set of locations of the main memory that are separated in address space according to a predefined pattern.

The method <NUM> further includes assigning I/O data from a first I/O device to a second subset of the plurality of main memory locations associated with the first memory pool or a second memory pool (block <NUM>). The I/O device can be, for example, a DMA engine, GPU, co-processor, or hardware accelerator. In some examples, the second subset of the plurality of main memory locations is a non-contiguous set of locations of the main memory that are separated in address space according to a predefined pattern.

In some examples, the first I/O device is exclusively used by the first application. In such examples, the I/O data from the first I/O device is saved in the main memory using a similar pattern to the one or more threads of the first application (for example, as discussed above with respect to <FIG>) and associated with the first memory pool. In other examples, the first I/O device is not exclusively used (or used at all) by the first application. In such examples, the I/O data from the first I/O device is saved in the main memory using a wholly different pattern than the pattern used to save the one or more threads of the first application.

In some examples, the first I/O device is shared by multiple applications. In such examples, the I/O data from the first I/O device is saved in the main memory in a similar pattern to that used for saving each of the one or more threads of the multiple applications. For example, a subset of the I/O data saved by the first I/O device is saved in the main memory using a similar pattern used to save the one or more threads of the first application and another subset of the I/O data saved by the first I/O device is saved in the main memory using a similar pattern used to save the one or more threads of the second application.

The method optionally includes assigning I/O data from other I/O device(s) to other subset(s) of the plurality of main memory locations associated with the first memory pool or a second memory pool (block <NUM>). The other I/O device can be the same type as the first I/O device or could also be different. In some examples, the other subset(s) of the plurality of main memory locations are non-contiguous set of locations of the main memory that are separated in address space according to a predefined pattern, which may be the same or different as the patterns used to associate data with the first memory pool or the second memory pool.

The systems and methods described herein provide enable the computing system <NUM> to use CPU cache partitions and memory pools and also access I/O data as a cached transaction, which is typically many times faster than uncached transactions of the previous systems. The CPUs are more efficient with cached transactions and the WCET when utilizing an I/O device (for example, a DMA, GPU, or co-processor) is greatly reduced. The systems and methods described herein can be utilized in high-performance system to efficiently handle high-throughput network interfaces using multiple DMA engines to send/receive data to a GPU or other co-processor. The systems and methods described herein can also be used to accelerate machine learning applications and aid other I/O intensive applications.

In various aspects, system elements, method steps, or examples described throughout this disclosure (such as the computing, or components thereof, for example) may be implemented on one or more computer systems, field programmable gate array (FPGA), application specific integrated circuit (ASIC) or similar devices comprising hardware executing code to realize those elements, processes, or examples, said code stored on a non-transient data storage device. These devices include or function with software programs, firmware, or other computer readable instructions for carrying out various methods, process tasks, calculations, and control functions, used in a distributed antenna system.

These instructions are typically stored on any appropriate computer readable medium used for storage of computer readable instructions or data structures. The computer readable medium can be implemented as any available media that can be accessed by a general purpose or special purpose computer or processor, or any programmable logic device. Suitable processor-readable media may include storage or memory media such as magnetic or optical media. For example, storage or memory media may include conventional hard disks, Compact Disk - Read Only Memory (CD-ROM), volatile or non-volatile media such as Random Access Memory (RAM) (including, but not limited to, Synchronous Dynamic Random Access Memory (SDRAM), Double Data Rate (DDR) RAM, RAMBUS Dynamic RAM (RDRAM), Static RAM (SRAM), etc.), Read Only Memory (ROM), Electrically Erasable Programmable ROM (EEPROM), and flash memory, etc. Suitable processor-readable media may also include transmission media such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as a network and/or a wireless link.

The methods and techniques described here may be implemented in digital electronic circuitry, or with a programmable processor (for example, a special-purpose processor or a general-purpose processor such as a computer) firmware, software, or in combinations of them. Apparatus embodying these techniques may include appropriate input and output devices, a programmable processor, and a storage medium tangibly embodying program instructions for execution by the programmable processor. A process embodying these techniques may be performed by a programmable processor executing a program of instructions to perform desired functions by operating on input data and generating appropriate output. The techniques may advantageously be implemented in one or more programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Generally, a processor will receive instructions and data from a read-only memory and/or a random access memory. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and DVD disks. Any of the foregoing may be supplemented by, or incorporated in, specially-designed application-specific integrated circuits (ASICs).

Claim 1:
A computing system (<NUM>), comprising:
at least one central processing unit (<NUM>);
one or more central processing unit caches (<NUM>);
a main memory (<NUM>) comprising a plurality of locations, wherein each location of the plurality of locations maps to a set in the one or more central processing unit caches (<NUM>), wherein a first subset of locations (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>) of the plurality of locations are partitioned for one or more threads of a first application and assigned to non-contiguous memory locations of the main memory (<NUM>) based on a respective set of one or more sets in the one or more central processing unit caches (<NUM>) to which each location is mapped; and
a first input/output, I/O, device (<NUM>) configured to store data in a second subset of locations (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>) of the plurality of locations that are different from the first subset of locations (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>) partitioned for the one or more threads of the first application, wherein the second subset of locations (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>) are non-contiguous memory locations of the main memory (<NUM>) that are separated in address space according to a predefined pattern,
characterised in that
the first I/O device (<NUM>) is either configured to retrieve, prior to each time the first I/O device (<NUM>) inputs data to the main memory (<NUM>) in order to determine where to store the I/O data, the predefined pattern that is stored in the main memory (<NUM>) as linked-list descriptors that include pointers indicating where data is to be written next, or configured to determine the predefined pattern either from an I/O configuration interface or based on information stored in a set of registers of the first I/O device (<NUM>).