Reducing synchronization of tasks in latency-tolerant task-parallel systems

Abstract

Techniques are provided for reducing synchronization of tasks in a task scheduling system. A task queue includes multiple tasks, some of which require an I/O operation while other tasks require data stored locally in memory. A single thread is assigned to process tasks in the task queue. The thread determines if a task at the head of the task queue requires an I/O operation. If so, then the thread generates an I/O request, submits the I/O request, and places the task at (or toward) the end of the task queue. When the task reaches the head of the task queue again, the thread determines if data requested by the I/O request is available yet. If so, then the thread processes the request. Otherwise, the thread places the task at (or toward) the end of the task queue again.

What is claimed is: 
     
         1 . A method comprising:
 storing a plurality of tasks in the queue of tasks;   identifying, by a single thread, a particular task that is at the head of the queue, wherein the particular task is one of the plurality of tasks;   determining, by the single thread, whether the particular task requires an I/O operation;   in response to determining that the particular task requires an I/O operation:
 generating and sending an I/O request; 
 without placing the particular task in another queue, causing, by the single thread, the particular task to be placed at a position, within the queue, that is not at the head of the queue; 
   wherein the method is performed by one or more computing devices.   
     
     
         2 . The method of  claim 1 , further comprising:
 after causing the particular task to be placed at the position, processing, by the single thread, other tasks of the plurality of tasks without processing the particular task;   wherein after processing the other tasks, the particular task is at the head of the queue;   determining, by the single thread, whether data associated with the I/O request is available.   
     
     
         3 . The method of  claim 2 , further comprising:
 in response to determining that data associated with the I/O request is not available, causing, by the single thread, the particular task to be placed at a second position, within the queue, that is not at the head of the queue.   
     
     
         4 . The method of  claim 2 , further comprising:
 in response to determining that data associated with the I/O request is available, processing, by the single thread, the particular task based on the data associated with the I/O request.   
     
     
         5 . The method of  claim 4 , further comprising:
 after processing the particular task based on the data associated with the I/O request, determining, by the single thread, whether the particular task requires one or more other operations.   
     
     
         6 . The method of  claim 1 , wherein causing the particular task to be placed in the position within the queue comprises causing, by the single thread, the particular task to be placed at the end of the queue. 
     
     
         7 . The method of  claim 1 , wherein causing the particular task to be placed in the position within the queue comprises causing, by the single thread, the particular task to be placed at a position, within the queue, that is not the end of the queue. 
     
     
         8 . The method of  claim 7 , further comprising:
 determining, by the single thread, the position based on one or more criteria;   wherein the one or more criteria includes one or more of an estimated latency of a network, an estimated latency of each task, an estimated latency of a storage device, or a number of tasks in the queue.   
     
     
         9 . The method of  claim 1 , wherein the I/O operation is a network I/O operation or a disk I/O operation. 
     
     
         10 . The method of  claim 1 , further comprising:
 prior to identifying the particular task, assigning the single thread to the queue of tasks;   
     
     
         11 . The method of  claim 1 , further comprising:
 prior to identifying the particular task, assigning, to the queue of task, a plurality of threads that are of the same processing core, wherein the plurality of threads includes the single thread.   
     
     
         12 . One or more non-transitory computer-readable media carrying instructions which, when executed by one or more processors, cause:
 storing a plurality of tasks in the queue of tasks;   identifying, by a single thread, a particular task that is at the head of the queue, wherein the particular task is one of the plurality of tasks;   determining, by the single thread, whether the particular task requires an I/O operation;   in response to determining that the particular task requires an I/O operation:
 generating and sending an I/O request; 
 without placing the particular task in another queue, causing, by the single thread, the particular task to be placed at a position, within the queue, that is not at the head of the queue. 
   
     
     
         13 . The one or more non-transitory computer-readable media of  claim 12 , wherein the instructions, when executed by the one or more processors, further cause:
 after causing the particular task to be placed at the position, processing, by the single thread, other tasks of the plurality of tasks without processing the particular task;   wherein after processing the other tasks, the particular task is at the head of the queue;   determining, by the single thread, whether data associated with the I/O request is available.   
     
     
         14 . The one or more non-transitory computer-readable media of  claim 13 , wherein the instructions, when executed by the one or more processors, further cause:
 in response to determining that data associated with the I/O request is not available, causing, by the single thread, the particular task to be placed at a second position, within the queue, that is not at the head of the queue.   
     
     
         15 . The one or more non-transitory computer-readable media of  claim 13 , wherein the instructions, when executed by the one or more processors, further cause:
 in response to determining that data associated with the I/O request is available, processing, by the single thread, the particular task based on the data associated with the I/O request.   
     
     
         16 . The one or more non-transitory computer-readable media of  claim 15 , wherein the instructions, when executed by the one or more processors, further cause:
 after processing the particular task based on the data associated with the I/O request, determining, by the single thread, whether the particular task requires one or more other operations.   
     
     
         17 . The one or more non-transitory computer-readable media of  claim 12 , wherein causing the particular task to be placed in the position within the queue comprises causing, by the single thread, the particular task to be placed at the end of the queue. 
     
     
         18 . The one or more non-transitory computer-readable media of  claim 12 , wherein causing the particular task to be placed in the position within the queue comprises causing, by the single thread, the particular task to be placed at a position, within the queue, that is not the end of the queue. 
     
     
         19 . The one or more non-transitory computer-readable media of  claim 18 , wherein the instructions, when executed by the one or more processors, further cause:
 determining, by the single thread, the position based on one or more criteria;   wherein the one or more criteria includes one or more of an estimated latency of a network, an estimated latency of each task, an estimated latency of a storage device, or a number of tasks in the queue.   
     
     
         20 . The one or more non-transitory computer-readable media of  claim 12 , wherein the I/O operation is a network I/O operation or a disk I/O operation. 
     
     
         21 . The one or more non-transitory computer-readable media of  claim 12 , wherein the instructions, when executed by the one or more processors, further cause:
 prior to identifying the particular task, assigning the single thread to the queue of tasks;   
     
     
         22 . The one or more non-transitory computer-readable media of  claim 12 , wherein the instructions, when executed by the one or more processors, further cause:
 prior to identifying the particular task, assigning, to the queue of task, a plurality of threads that are of the same processing core, wherein the plurality of threads includes the single thread.   
     
     
         23 . A computer system comprising:
 one or more processors;   one or more computer-readable media storing instructions which, when executed by the one or more processors, cause:
 storing a plurality of tasks in the queue of tasks; 
 identifying, by a single thread, a particular task that is at the head of the queue, wherein the particular task is one of the plurality of tasks; 
 determining, by the single thread, whether the particular task requires an I/O operation; 
 in response to determining that the particular task requires an I/O operation:
 generating and sending an I/O request; 
 without placing the particular task in another queue, causing, by the single thread, the particular task to be placed at a position, within the queue, that is not at the head of the queue.