Adaptive queuing methodology for system task management

• US 8,640,140 B2
• Filed: 03/31/2011
• Issued: 01/28/2014
• Est. Priority Date: 10/25/2010
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Tian, Chen, Waddington, Daniel
• Primary Examiner(s): Tang, Kenneth
• Application Number:
  US13/077,567
• Publication Number:
  US 20120102501A1
• Time in Patent Office: 1,034 Days
• Field of Search: None
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

A task management methodology for system having multiple processors and task queues adapts a queuing topology by monitoring a queue pressure and adjusting the queue topology from a selection of at least two different queue topologies. The queue pressure may be periodically monitored and queues with different granularities selected. The methodology reduced contention when there is high pressure on the queues while also reducing overhead to manage queues when there is less pressure on the queues.

Claims

1. In a Multiple Instruction Multiple Data (MMID) architecture in which tasks are mapped to task queues in a first mapping, task queues are mapped to threads in a second mapping, and threads are mapped to processing resources in a third mapping, a method comprising:

monitoring a queue pressure of at least one task queue; and

adapting a queue topology of the architecture based on said queue pressure and at least one threshold level associated with said queue pressure, wherein said queue topology is selected from at least two different queue topologies;

wherein said first mapping, said second mapping and said third mapping are based on said queue topology; and

wherein said at least two different queue topologies comprise a fine grained queue topology for reducing contention when said queue pressure is greater than said at least one threshold level, and a coarse grained queue topology for reducing computational overhead when said queue pressure is less than or equal to said at least one threshold level.

2. The method of claim 1, wherein said at least two different queue topologies includes queue topologies having different levels of queue granularities.

3. The method of claim 1, further comprising using a sampling thread to sample queue pressure of at least one task queue and to select said queue topology for all worker threads.

4. The method of claim 3, wherein:

said queue pressure is based on a task producing pressure of at least one task queue and a task consuming pressure of at least one task queue, wherein a task producing pressure of a task queue is based on a number of failed queue locks relating to said task queue, and wherein a task consuming pressure of a task queue is based on a number of tasks relating to said task queue that have migrated.

5. The method of claim 4, wherein:

said fine grained queue topology is selected as said queue topology if a task producing pressure of at least one task queue is greater than said at least one threshold level; and

said coarse grained queue topology is selected as said queue topology if a task producing pressure of at least one task queue is less than or equal to said at least one threshold level.

6. The method of claim 3, wherein said sampling thread monitors a shared memory resource associated with at least one task queue and modifies a queue pointer of each worker thread to adjust said queue topology.

7. The method of claim 1, wherein each queue topology defines a mapping between one or more tasks and one or more threads.

8. In a Multiple Instruction Multiple Data (MMID) architecture, a method of operating a task manager logically programming tasks to physical processing resources, comprising:

monitoring a shared memory resource supporting at least one task queue, wherein each task queue comprises at least one task mapped to said task queue; and

adaptively changing a queue configuration of the architecture based on a queue pressure of said at least one task queue and at least one threshold level associated with said queue pressure, wherein said queue configuration is selected from at least two different queue configurations;

wherein a task is mapped to a task queue based on said queue configuration; and

wherein said at least two different queue configurations comprise a fine grained queue configuration for reducing contention when said queue pressure is greater than said at least one threshold level, and a coarse grained queue configuration for reducing computational overhead when said queue pressure is less than or equal to said at least one threshold level.

9. The method of claim 8, wherein:

said queue pressure is based on a task producing pressure of at least one task queue and a task consuming pressure of at least one task queue, wherein a task producing pressure of a task queue is based on a number of failed queue locks relating to said task queue, and wherein a task consuming pressure of a task queue is based on a number of tasks relating to said task queue that have migrated.

10. The method of claim 9, wherein:

said fine grained queue configuration is selected as said queue configuration to reduce contention if said queue pressure is greater than said at least one threshold level; and

said coarse grained queue configuration is selected as said queue configuration to reduce computational overhead if said queue pressure is less than or equal to said at least one threshold level.

11. The method of claim 10, wherein:

said coarse grained queue configuration comprises a shared global task queue for task creation/servicing volume to minimize cost of concurrency; and

said fine grained queue configuration comprises one of multiple distributed queues or multiple hierarchical queues.

12. The method of claim 8, wherein said monitoring is a periodic monitoring.

13. A Multiple Instruction Multiple Data (MMID) system, wherein lightweight tasks are mapped to task queues, and wherein task queues are mapped to threads, the system comprising:

multiple processing cores and associated links;

memory space for at least one task queue, wherein each task queue comprises at least one task mapped to said task queue; and

a task manager monitoring queue pressure of said at least one task queue and adapting a queue topology of the system based on said queue pressure and at least one threshold level associated with said queue pressure, wherein said queue topology is selected from at least two different queue topologies;

wherein a task is mapped to a task queue based on said queue topology;

wherein a task queue is mapped to a thread based on said queue topology; and

wherein said at least two different queue topologies comprise a fine grained queue topology for reducing contention when said queue pressure is greater that than said at least one threshold level, and a coarse grained queue topology for reducing computational overhead when said queue pressure is less than or equal to said at least one threshold level.

14. The system of claim 13, wherein a queue pointer of at least one of worker thread is adapted to configure said queue topology.

15. The system of claim 13, wherein

said fine grained queue topology is selected as said queue topology to reduce contention if said queue pressure is greater than said at least one threshold level;

and

said coarse grained queue topology is selected as said queue topology to reduce computational overhead if said queue pressure is less than or equal to said at least one threshold level.

16. The system of claim 13, wherein said queue topology is selected from at least two different queue topologies that include queue topologies having different levels of queue granularities.

17. The system of claim 13, further comprising using a sampling thread to sample queue pressure of at least one task queue and select said queue topology.

18. The system of claim 17, wherein said queue pressure is based on a task producing pressure of at least one task queue and a task consuming pressure of at least one task queue, wherein a task producing pressure of a task queue is based on a number of failed queue locks relating to said task queue, and wherein a task consuming pressure of a task queue is based on a number of tasks relating to said task queue that have migrated.

19. The system of claim 17, wherein:

said fine grained queue topology is selected as said queue topology if a task producing pressure of at least one task queue is greater than said at least one threshold level; and

said coarse grained queue topology is selected as said queue topology if a task producing pressure of at least one task queue is less than or equal to said at least one threshold level.

20. The system of claim 17, wherein said sampling thread monitors a shared memory resources associated with at least one task queue and modifies an attribute of said at least one task queue to adjust said queue topology.

21. A computer program product for a Multiple Instruction Multiple Data (MMID) architecture in which tasks are mapped to task queues, task queues are mapped to threads in a second mapping, and threads are mapped to processing resources in a third mapping, comprising computer code stored on a non-transitory computer readable medium to implement a method comprising:

monitoring a queue pressure of at least one task queue; and

adapting a queue topology of the architecture based on said queue pressure and at least one threshold level associated with said queue pressure, wherein said queue topology is selected from at least two different queue topologies;

wherein said first mapping, said second mapping and said third mapping are based on said queue topology; and

wherein said at least two different queue topologies comprise a fine grained queue topology for reducing contention when said queue pressure is greater than said at least one threshold level, and a coarse grained queue topology for reducing computational overhead when said queue pressure is less than or equal to said at least one threshold level.