Controlling tasks performed by a computing system using instructions generated to control initiation of subroutine execution

Patent metadata

Field	Value
Publication number	US-9665396-B2
Application number	US-201414259451-A
Country	US
Kind code	B2
Filing date	Apr 23, 2014
Priority date	Apr 23, 2013
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

Controlling tasks includes: receiving ordering information that specifies at least a partial ordering among a plurality of tasks; and generating instructions for performing at least some of the tasks based at least in part on the ordering information. Instructions are stored for executing a first subroutine corresponding to a first task, including a first control section that controls execution of at least a second subroutine corresponding to a second task, the first control section including a function configured to change state information associated with the second task, and to determine whether or not to initiate execution of the second subroutine based on the changed state information. Instructions are stored for executing the second subroutine, including a task section for performing the second task and a second control section that controls execution of a third subroutine corresponding to a third task.

First claim

What is claimed is:

1. A method for controlling tasks performed by a computing system, the method including:
receiving ordering information that specifies at least a partial ordering among a plurality of tasks; and
generating, using at least one processor, instructions for performing at least some of the tasks based at least in part on the ordering information, the generating including:
storing instructions for executing a first subroutine corresponding to a first task, the first subroutine including a first control section that controls execution of at least a second subroutine corresponding to a second task, the first control section including a function configured to change state information associated with the second task, and to determine whether or not to initiate execution of the second subroutine based on the changed state information; and
storing instructions for executing the second subroutine, the second subroutine including a task section for performing the second task and a second control section that controls execution of a third subroutine corresponding to a third task.

2. The method of claim 1 , wherein the ordering information includes a control flow graph that includes directed edges between pairs of the nodes that represent respective tasks, where a directed edge from an upstream node to a downstream node indicates that the task represented by the upstream node precedes the task represented by the downstream node in the partial ordering.

3. The method of claim 2 , wherein the control flow graph includes a directed edge between a first node representing the first task and a second node representing the second task, and a directed edge between the second node and a third node representing the third task.

4. The method of claim 1 , wherein the function is configured to: decrement or increment a counter associated with the second task, and determine whether or not to initiate execution of the second subroutine based on the value of the counter.

5. The method of claim 4 , wherein the function is configured to perform an atomic operation that atomically decrements or increments the counter and reads a value of the counter.

6. The method of claim 1 , wherein the changed state information comprises a history of previous calls of the function with an argument that identifies the second task.

7. The method of claim 6 , wherein the function is one of a plurality of different functions, and the state information captures a history of previous calls of any of the plurality of different functions with an argument that identifies the second task.

8. The method of claim 1 , wherein the second control section includes logic that determines whether or not the task section for performing the task is called.

9. The method of claim 8 , wherein the logic determines whether or not the task section for performing the task is called based on the value of a flag associated with the second task.

10. The method of claim 1 , wherein the first control section controls execution of at least: the second subroutine corresponding to the second task, and a fourth subroutine corresponding to a fourth task.

11. The method of claim 10 , wherein the ordering information indicates that the first task precedes the second task in the partial ordering, and indicates that the first task precedes the fourth task in the partial ordering, and does not constrain the order of the second and forth tasks relative to each other in the partial ordering.

12. The method of claim 10 , wherein the first control section includes: a first function that determines whether or not to spawn a new process for executing the second subroutine, and a second function that initiates execution of the fourth subroutine using the same process that executed the first subroutine.

13. A computer program stored on a non-transitory medium, for controlling tasks, the computer program including instructions for causing a computing system to:
receive ordering information that specifies at least a partial ordering among a plurality of tasks; and
generate instructions for performing at least some of the tasks based at least in part on the ordering information, the generating including:
storing instructions for executing a first subroutine corresponding to a first task, the first subroutine including a first control section that controls execution of at least a second subroutine corresponding to a second task, the first control section including a function configured to change state information associated with the second task, and to determine whether or not to initiate execution of the second subroutine based on the changed state information; and
storing instructions for executing the second subroutine, the second subroutine including a task section for performing the second task and a second control section that controls execution of a third subroutine corresponding to a third task.

14. The computer program of claim 13 , wherein the ordering information includes a control flow graph that includes directed edges between pairs of the nodes that represent respective tasks, where a directed edge from an upstream node to a downstream node indicates that the task represented by the upstream node precedes the task represented by the downstream node in the partial ordering.

15. The computer program of claim 14 , wherein the control flow graph includes a directed edge between a first node representing the first task and a second node representing the second task, and a directed edge between the second node and a third node representing the third task.

16. The computer program of claim 13 , wherein the function is configured to: decrement or increment a counter associated with the second task, and determine whether or not to initiate execution of the second subroutine based on the value of the counter.

17. The computer program of claim 16 , wherein the function is configured to perform an atomic operation that atomically decrements or increments the counter and reads a value of the counter.

18. The computer program of claim 13 , wherein the changed state information comprises a history of previous calls of the function with an argument that identifies the second task.

19. The computer program of claim 18 , wherein the function is one of a plurality of different functions, and the state information captures a history of previous calls of any of the plurality of different functions with an argument that identifies the second task.

20. The computer program of claim 13 , wherein the second control section includes logic that determines whether or not the task section for performing the task is called.

21. The computer program of claim 20 , wherein the logic determines whether or not the task section for performing the task is called based on the value of a flag associated with the second task.

22. The computer program of claim 13 , wherein the first control section controls execution of at least: the second subroutine corresponding to the second task, and a fourth subroutine corresponding to a fourth task.

23. The computer program of claim 22 , wherein the ordering information indicates that the first task precedes the second task in the partial ordering, and indicates that the first task precedes the fourth task in the partial ordering, and does not constrain the order of the second and forth tasks relative to each other in the partial ordering.

24. The computer program of claim 22 , wherein the first control sectio

Assignees

• Ab Initio Technology Llc

Inventors

• Stanfill Craig W

Classifications

• G06F9/4843 Primary

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F9/4494 Primary

  data driven · CPC title

• G06F9/4881

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

• G06F9/4436

  Physics · mapped topic