Technique for dynamically restricting thread concurrency without rewriting thread code

• US 8,245,207 B1
• Filed: 04/18/2008
• Issued: 08/14/2012
• Est. Priority Date: 07/31/2003
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: English, Robert M., Kukavica, Zdenko, Roussos, Konstantinos
• Primary Examiner(s): Rutten, James D
• Application Number:
  US12/105,451
• Time in Patent Office: 1,579 Days
• Field of Search: 717/149
• US Class Current: 717/149
• CPC Class Codes: G06F 8/456 Parallelism detection
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for executing uniprocessor (UP) coded workloads in a computer capable of concurrent thread execution is disclosed. The method identifies threads in the uniprocessor coded workloads (UP-workloads) which can execute concurrently, and identifies threads in the UP-workloads which cannot execute concurrently. First threads which cannot execute concurrently are assigned to a first concurrency group. Second threads which cannot execute concurrently are assigned to a second concurrency group. Any thread in the first concurrency group can execute concurrently with any thread in the second concurrency group. The computer capable of concurrent thread execution then executes the UP-coded workloads in the first concurrency group at substantially the same time as executing the UP-coded workloads in the second concurrency group.

Claims

1. A method for executing uniprocessor (UP) coded workloads (UP-workloads) in a computer capable of concurrent execution, comprising:

assigning first UP-workloads which are not permitted to execute concurrently to a first concurrency group, and assigning second UP-workloads which are not permitted to execute concurrently to a second concurrency group, where any UP-workload in the first concurrency group is permitted to execute concurrently with any UP-workload in the second concurrency group; and

executing safely, on the computer capable of concurrent execution, the UP-coded workloads in the first concurrency group at substantially the same time as executing the UP-coded workloads in the second concurrency group, and where the first UP-workloads in object code share, without conventional synchronization, access to a common set of memory addresses in a memory.

2. The method as in claim 1, wherein the step of assigning occurs at compile-time.

3. The method as in claim 1, further comprising:

scheduling the first concurrency group to execute on a first processor of the computer capable of concurrent execution; and

scheduling the second concurrency group to execute on a second processor of the computer capable of concurrent execution, to execute the first group and the second group at substantially the same time.

4. The method as in claim 3, wherein the step of scheduling the first concurrency group comprises:

dequeuing a first UP-workload on a first queue, while at substantially the same time dequeuing another UP-workload from a second queue.

5. The method as in claim 1, further comprising:

using a multiprocessor system as the computer capable of concurrent execution.

14. The method as in claim 1, wherein the step of assigning occurs at run-time.

15. The method as in claim 1, where the common set of memory addresses references a data structure.

16. The method as in claim 1, wherein the common set of memory addresses references a message.

6. A computer to execute uniprocessor (UP) coded workloads using concurrent execution, comprising:

a processor and a memory;

uniprocessor coded workloads (UP-workloads);

an operating system to assign first UP-workloads which are not permitted to execute concurrently to a first concurrency group, and the operating system assigning second UP-workloads which are not permitted to execute concurrently to a second concurrency group, where any UP-workload in the first concurrency group is permitted to execute concurrently with any UP-workload in the second concurrency group; and

the computer to safely execute the UP-coded workloads in the first concurrency group at substantially the same time as executing the UP-coded workloads in the second concurrency group, where the first UP-workloads in object code share access to a common set of memory addresses in a memory without a conventional synchronization mechanism, and wherein the conventional synchronization mechanism is selected from the group consisting of lock, monitor, and domain.

7. The computer as in claim 6, where the UP-workloads are executed using threads.

8. The computer as in claim 7, further comprising:

a scheduler configured to schedule the first concurrency group to execute on a first processor of the computer; and

the scheduler configured to schedule the second concurrency group to execute on a second processor of the computer, to execute the first concurrency group and the second concurrency group at substantially the same time.

9. The computer as in claim 6, further comprising:

a multiprocessor system to serve as the computer.

10. The computer as in claim 6, where the common set of memory addresses references a data structure.

11. The computer as in claim 6, where the common set of memory addresses references a message.

12. The computer as in claim 6, the operating system further comprising:

a scheduler configured to enqueue a first UP-workload on a first queue and dequeue another UP-workload from a second queue.

13. A computer readable medium containing executable program instructions for execution by a processor, comprising:

program instructions that execute uniprocessor object code workloads (UP-workloads);

program instructions that assign first UP-workloads which are not permitted to execute concurrently to a first concurrency group, and assign second UP-workloads which are not permitted to execute concurrently to a second concurrency group, where any UP-workload in the first concurrency group is permitted to safely execute concurrently with any UP-workload in the second concurrency group, and where the first UP-workloads share access to a common set of memory addresses in a memory without conventional synchronization; and

program instructions that schedule execution of the UP-coded workloads in the first concurrency group at substantially the same time as execution of the UP-coded workloads in the second concurrency group.

17. A method for scheduling uniprocessor (UP) coded workloads (UP-workloads) in a computer capable of concurrent thread execution, comprising:

identifying threads in the UP-workloads which are permitted to execute concurrently, identifying threads in the UP-workloads which are not permitted to execute concurrently, where the UP-workloads which are not permitted to execute concurrently are multiprocessor unsafe workloads in object code;

assigning, at run-time, first threads which are not permitted to execute concurrently to a first concurrency group, and assigning, at run-time, second threads which are not permitted to execute concurrently to a second concurrency group, where any thread in the first concurrency group is permitted to execute concurrently with any thread in the second concurrency group, and where any thread in the first concurrency group does not have a conventional synchronization with any thread in the second concurrency group; and

dequeuing sequentially for execution a thread of the first threads from a first queue, where the dequeued thread of the first threads on the first queue runs to completion before dequeuing another thread of the first threads from the first queue.

18. The method as in claim 17, wherein the step of identifying occurs at run-time.

19. The method as in claim 17, further comprising:

dequeuing for execution a thread of the second threads from a second queue at substantially the same time as performing the step of dequeuing a thread of the first threads from the first queue.

20. The method as in claim 17, further comprising:

enqueuing a thread of the first threads to a third queue at substantially the same time as performing the step of dequeuing a thread of the first threads from the first queue.