Program subgraph identification

• US 7,343,482 B2
• Filed: 01/31/2005
• Issued: 03/11/2008
• Est. Priority Date: 10/20/2004
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.), University of Michigan
• Original Assignee: Arm Limited (SoftBank Group Corp.), University of Michigan
• Inventors: Biles, Stuart David, Flautner, Krisztian, Clark, Nathan, Mahlke, Scott
• Primary Examiner(s): Coleman; Eric
• Application Number:
  US11/048,663
• Publication Number:
  US 20060095722A1
• Time in Patent Office: 1,135 Days
• Field of Search: 712/242, 712/15, 712/239
• US Class Current: 712/242
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

There is provided an apparatus for processing data under control of a program having program instructions and subgraph suggestion information identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said apparatus comprising:

• • a memory operable to store a program formed of separate program instructions;
  • processing logic operable to execute respective separate program instructions from said program; and
  • accelerator logic operable in response to reaching an execution point within said program associated with a subgraph suggestion to execute a sequence of program instructions corresponding to said subgraph suggestion as an accelerated operation instead of executing said sequence of program instructions as respective separate program instructions with said processing logic.

Claims

1. Apparatus for processing data under control of a program having program instructions and subgraph suggestion information identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said apparatus comprising:

a memory operable to store a program formed of separate program instructions;

processing logic operable to execute respective separate program instructions from said program; and

accelerator logic operable in response to reaching an execution point within said program associated with a subgraph suggestion to execute a sequence of program instructions corresponding to said subgraph suggestion as an accelerated operation instead of executing said sequence of program instructions as respective separate program instructions with said processing logic, wherein said apparatus stores accelerator configuration data operable to configure said accelerator logic to adopt one or more configurations to execute as accelerated operations one or more sequences of program instructions corresponding to computational subgraphs identified within said program, wherein said accelerator configuration data is stored in a configuration data memory, wherein said configuration memory is indexed with a value held within a branch prediction unit.

2. Apparatus as claimed in claim 1, wherein said accelerator logic is operable in response to reaching an execution point within said program associated with a subgraph suggestion corresponding to a sequence of program instructions not able to be executed as an accelerated operation by said accelerator logic to ignore said subgraph suggestion and allow said sequence of program instructions to be executed as respective separate program instructions with said processing logic.

3. Apparatus as claimed in claim 1, wherein said subgraph suggestion information comprises marker instructions embedded within said program.

4. Apparatus as claimed in claim 3, wherein a sequence start marker instruction is embedded within said program preceding an associated sequence of program instructions corresponding to a computational subgraph identified within said program.

5. Apparatus as claimed in claim 3, wherein a sequence end marker instruction is embedded within said program succeeding an associated sequence of program instructions corresponding to a computational subgraph identified within said program.

6. Apparatus as claimed in claim 3, wherein a sequence marker instruction is embedded within said program and indicates a location and length of an associated sequence of program instructions corresponding to a computational subgraph identified within said program.

7. Apparatus as claimed in claim 3, wherein a branch marker instruction is embedded within said program and identifies a branch instruction to an associated sequence of program instructions as corresponding to a computational subgraph identified within said program.

8. Apparatus as claimed in claim 1, wherein said subgraph information comprises subgraph branch instructions specifying a branch to an associated sequence of program instructions as corresponding to a computational subgraph identified within said program.

9. Apparatus as claimed in claim 1, wherein said accelerator configuration data is stored as part of said program.

10. Apparatus as claimed in claim 1, wherein said configuration data memory is part of a branch prediction unit.

11. Apparatus as claimed in claim 1, wherein said subgraph suggestion information comprises branch instructions indicating a branch to a sequence of program instructions of a length below a maximum length capable of being executed as a combined operation and said accelerator logic operable to detect if a sequence of program instructions indicated by a branch instruction is one which said accelerator logic is capable of executing as an accelerated operation.

12. Apparatus as claimed in claim 1, wherein said subgraph suggestion information comprises a sequence of program instructions having a predetermined form operable to trigger pattern matching logic within said accelerator logic.

13. Apparatus as claimed in claim 1, wherein said subgraph suggestion information comprises a table of data identifying said sequences of program instructions corresponding to computational subgraphs.

14. Apparatus as claimed in claim 1, wherein said subgraph suggestion information is added:

(i) prior to execution;

(ii) at runtime by software; and

(iii) at runtime by hardware.

15. A method of processing data under control of a program having program instructions and one or more subgraph markers identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said method comprising:

storing a program formed of separate program instructions within a memory;

executing respective separate program instructions from said program with processing logic;

in response to reaching an execution point within said program associated with a subgraph marker executing a sequence of program instructions corresponding to said subgraph marker as a combined operation with accelerator logic instead of executing said sequence of program instructions as respective separate program instructions with said processing logic; and

storing accelerator configuration data operable to configure said accelerator logic to adopt one or more configurations to execute as accelerated operations one or more sequences of program instructions corresponding to computational subgraphs identified within said program, wherein said accelerator configuration data is stored in a configuration data memory, wherein said configuration memory is indexed with a value held within a branch prediction unit.

16. A computer program product comprising a computer readable storage medium containing computer readable program instructions and one or more subgraph markers identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said computer program being operable to control an apparatus for processing data to perform the method as claimed in claim 15.

17. Apparatus for processing data under control of a program having program instructions and subgraph suggestion information identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said apparatus comprising:

a memory operable to store a program formed of separate program instructions;

processing logic operable to execute respective separate program instructions from said program; and

accelerator logic operable in response to reaching an execution point within said program associated with a subgraph suggestion to execute a sequence of program instructions corresponding to said subgraph suggestion as an accelerated operation instead of executing said sequence of program instructions as respective separate program instructions with said processing logic, wherein said subgraph suggestion information comprises marker instructions embedded within said program, wherein a sequence marker instruction is embedded within said program and indicates a location and length of an associated sequence of program instructions corresponding to a computational subgraph identified within said program.

18. Apparatus for processing data under control of a program having program instructions and subgraph suggestion information identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said apparatus comprising:

a memory operable to store a program formed of separate program instructions;

processing logic operable to execute respective separate program instructions from said program; and

accelerator logic operable in response to reaching an execution point within said program associated with a subgraph suggestion to execute a sequence of program instructions corresponding to said subgraph suggestion as an accelerated operation instead of executing said sequence of program instructions as respective separate program instructions with said processing logic,

wherein said apparatus stores accelerator configuration data operable to configure said accelerator logic to adopt one or more configurations to execute as accelerated operations one or more sequences of program instructions corresponding to computational subgraphs identified within said program, wherein said accelerator configuration data is stored in a configuration data memory, wherein said configuration data memory is part of a branch prediction unit.

19. A method of processing data under control of a program having program instructions and one or more subgraph markers identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said method comprising:

storing a program formed of separate program instructions within a memory;

executing respective separate program instructions from said program with processing logic; and

in response to reaching an execution point within said program associated with a subgraph marker executing a sequence of program instructions corresponding to said subgraph marker as a combined operation with accelerator logic instead of executing said sequence of program instructions as respective separate program instructions with said processing logic, wherein said subgraph suggestion information comprises marker instructions embedded within said program, wherein a sequence marker instruction is embedded within said program and indicates a location and length of an associated sequence of program instructions corresponding to a computational subgraph identified within said program.

20. A method of processing data under control of a program having program instructions and one or more subgraph markers identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said method comprising:

storing a program formed of separate program instructions within a memory;

executing respective separate program instructions from said program with processing logic; and

in response to reaching an execution point within said program associated with a subgraph marker executing a sequence of program instructions corresponding to said subgraph marker as a combined operation with accelerator logic instead of executing said sequence of program instructions as respective separate program instructions with said processing logic, wherein said apparatus stores accelerator configuration data operable to configure said accelerator logic to adopt one or more configurations to execute as accelerated operations one or more sequences of program instructions corresponding to computational subgraphs identified within said program, wherein said accelerator configuration data is stored in a configuration data memory, wherein said configuration data memory is part of a branch prediction unit.