A compiler-controlled technique for scheduling threads to execute different regions of a program. A compiler analyzes program code to determine a control flow graph for the program code. The control flow graph contains regions and directed edges between regions. The regions have associated execution priorities. The directed edges indicate the direction of program control flow. Each region has a thread frontier which contains one or more regions. The compiler inserts one or more update predicate mask variable instructions at the end of a region. The compiler also inserts one or more conditional branch instructions at the end of the region. The conditional branch instructions are arranged in order of execution priority of the regions in the thread frontier of the region, to enforce execution priority of the regions at runtime.

Claims

20 · 3 independent · depth 4

20 granted claims

›1.independentA method for scheduling threads to execute different regions of a program, the method comprising:nanalyzing a control flow graph that is based on prog…+8

›2.↳ 1The method of claim 1, further comprising determining that a branch instruction is included at the end of the first region, and replacing the branch i…d2+2

›5.↳ 1The method of claim 1, wherein each region in the control flow graph has one or more successor regions and one or more predecessor regions, each succe…d2

›6.↳ 1The method of claim 1, wherein inserting the one or more conditional branch instructions further comprises:ninserting a plurality of conditional branc…d2

›7.↳ 1The method of claim 1, further comprising inserting one or more instructions at the beginning of the first region to set a predicate mask for the firs…d2

›8.↳ 1The method of claim 1, further comprising optimizing the one or more update predicate mask variable instructions and the one or more conditional branc…d2

›9.↳ 1The method of claim 1, further comprising:ninserting one or more update predicate mask variable instructions at the end of a second region in the plur…d2

›10.independentA non-transitory computer-readable medium storing instructions, that when executed by a processor, cause a computer system to schedule threads to exec…+8

›11.↳ 10The non-transitory computer-readable medium of claim 10, further comprising:ndetermining that a branch instruction is included at the end of the first…d2+2

›12.↳ 11The non-transitory computer-readable medium of claim 11, wherein:neach region in the control flow graph has one or more successor regions and one or m…d3+1

›14.↳ 10The non-transitory computer-readable medium of claim 10, wherein each region in the control flow graph has one or more successor regions and one or mo…d2

›15.↳ 10The non-transitory computer-readable medium of claim 10, wherein inserting the one or more conditional branch instructions further comprises:ninsertin…d2

›16.↳ 10The non-transitory computer-readable medium of claim 10, further comprising inserting one or more instructions at the beginning of the first region to…d2

›17.↳ 10The non-transitory computer-readable medium of claim 10, further comprising optimizing the one or more update predicate mask variable instructions and…d2

›18.↳ 10The non-transitory computer-readable medium of claim 10, further comprising:ninserting one or more update predicate mask variable instructions at the …d2

›19.independentA computing device for scheduling threads to execute different regions of a program, the computing device comprising:na processor; anda memory coupled…+1

Classifications

2 codes

IPC · International Patent Classification

Section G — Physics

G06F9/30
G06F9/45

Claim changes

Soon

Coming soonHow the claims changed between publication and grant

See which claims were amended, added or cancelled during examination, with every added and removed word marked.

AmendedAddedCancelledUnchanged

The published claims of this patent are not paired with the granted ones in what we hold.

File wrapper

Pendency

3.2 y

1,177 days filing → grant

Office actions

non-final + final

Responses

1 RCE

Examiner

Tuan Vu

art unit 2193 · TC 2100

Law firm

Law firm · Log in to unlock

Citations: 15 back · 0 forward

See the full prosecution history — every USPTO and applicant action on this file, in order.

Term & fees

See the term timeline — pendency span, in-force span, the maintenance fees paid and both computed expiry dates.

Priority chain

1 priority documents

›Priority documents — 1

Type	Document	Date
related publication	US 20140165049 A1	12 Jun 2014

Validity challenges

See the validity challenges on record — reexaminations, IPRs and PGRs, with their institution decisions and outcomes.

Citations

See every patent this one cites and every patent that cites it back — publication, assignee, and how each one was found.