Effective scheduling of producer-consumer processes in a multi-processor system

Patent metadata

Field	Value
Publication number	US-9436506-B2
Application number	US-201314141089-A
Country	US
Kind code	B2
Filing date	Dec 26, 2013
Priority date	Oct 31, 2008
Publication date	Sep 6, 2016
Grant date	Sep 6, 2016

Abstract

A novel technique for improving throughput in a multi-core system in which data is processed according to a producer-consumer relationship by eliminating latencies caused by compulsory cache misses. The producer and consumer entities run as multiple slices of execution. Each such slice has an associated execution context that comprises of the code and data that particular slice would access. The execution contexts of the producer and consumer slices are small enough to fit in the processor caches simultaneously. When a producer entity scheduled on a first core completed production of data elements as constrained by the size of cache memories, a consumer entity is scheduled on that same core to consume the produced data elements. Meanwhile, a second slice of the producer entity is moved to another core and a second slice of a consumer entity is scheduled to consume elements produced by the second slice of the producer.

First claim

What is claimed is:

1. A method for data processing in a producer-consumer environment on a multi-core processor system, comprising:
executing a producer-consumer pair of processes at the multi-core processor system;
executing a producer process of the producer-consumer pair on a first processing core of the multi-core processor system to produce data elements;
scheduling a consumer process of the producer-consumer pair to execute on the first processing core and executing the consumer process on the first processing core to consume a first portion of the data elements;
moving the producer process to execute on a second processing core of the multi-core system to produce a second portion of the data elements, wherein the second portion of the data elements are cached in a second cache of the second processing core; and
in response to producing the second portion of the data elements cached in the second cache, scheduling the consumer process to execute on the second processing core and executing the consumer process on the second processing core to consume the second portion of the data elements cached at the second processing core.

2. The method of claim 1 wherein a first portion of the data elements is cached in a first cache of the first processing core that references data in a memory shared by the producer-consumer pair.

3. The method of claim 1 , further comprising yielding the first processing core to a scheduler module to schedule a second producer-consumer pair of processes for execution on the first processing core.

4. The method of claim 1 , further comprising loading first execution contexts of the producer and the consumer process to a first cache of the first processing core.

5. The method of claim 4 , further comprising loading second execution contexts of a second producer-consumer pair of processes to the first cache of the first processing core when the consumer process finishes processing the data elements produced by the producer process.

6. The method of claim 1 , further comprising executing the producer-consumer pair of processes as multiple slices of execution.

7. The method of claim 1 , further comprising executing by the first processing core a first slice of execution of the producer-consumer pair and a first slice of execution of a second producer-consumer pair, and executing by the second processing core a second slice of execution of the producer-consumer pair and a second slice of execution of the second producer-consumer pair.

8. The method of claim 1 , wherein producing the data elements comprises:
receiving a data item;
processing the data item;
storing the data item in the shared memory;
storing in the memory a data element of the data elements, wherein the data element references the data item; and
storing the data element in a first cache at the first processing core where the producer process is executed.

9. A non-transitory computer-readable medium containing executable program instructions executed by a processor, comprising:
program instructions that execute a producer-consumer pair of processes at a multi-core processor system;
program instructions that execute a producer process of the producer-consumer pair on a first processing core of the multi-core processor system to produce data elements;
program instructions that schedule a consumer process of the producer-consumer pair to execute on the first processing core and execute the consumer process on the first processing core to consume the first portion of the data elements;
program instructions that move the producer process to execute on a second processing core of the multi-core system to produce a second portion of the data elements, wherein the second portion of the data elements are cached in a second cache of the second processing core; and
program instructions that, in response to producing the second portion of the data elements cached in the second cache, schedule the consumer process to execute on the second processing core and execute the consumer process on the second processing core to consume the second portion of the data elements cached at the second processing core.

10. The non-transitory computer readable medium of claim 9 wherein a first portion of the data elements is cached in a first cache of the first processing core that references data in a memory shared by the producer-consumer pair.

11. A system for data processing in a producer-consumer environment on a multi-core processor system, comprising:
means for executing a producer-consumer pair of processes at the multi-core processor system; and
means for executing a producer process of the producer-consumer pair on a first processing core of the multi-core processor system to produce data elements;
means for scheduling a consumer process of the producer-consumer pair to execute on the first processing core and to execute the consumer process on the first processing core to consume the first portion of the data elements;
means for moving the producer process to execute on a second processing core of the multi-core system to produce a second portion of the data elements, wherein the second portion of the data elements are cached in a second cache of the second processing core; and
means for scheduling the consumer process to execute on the second processing core and means for executing the consumer process on the second processing core to consume the second portion of the data elements cached at the second processing core in response to producing the second portion of the data elements cached in the second cache.

12. The system of claim 11 , further comprising means for pre-loading an execution context of the consumer process in the first processing core on which the producer process is executed.

13. The system of claim 11 , wherein the means for pre-loading the execution context comprises means for loading memory mapping information associated with the producer process.

14. The system of claim 11 wherein a first portion of the data elements is cached in a first cache of the first processing core that references data in a memory shared by the producer-consumer pair.

Assignees

• Netapp Inc

Inventors

• Radhakrishnan Prashanth
• Srinivasan Kiran

Classifications

• G06F12/0811

  with multilevel cache hierarchies · CPC title

• G06F12/0806

  Multiuser, multiprocessor or multiprocessing cache systems · CPC title

• G06F2209/483

  Multiproc · CPC title

• G06F2209/484

  Precedence · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title