Compiler for translating between a virtual image processor instruction set architecture (ISA) and target hardware having a two-dimensional shift array structure

Patent metadata

Field	Value
Publication number	US-9785423-B2
Application number	US-201514694856-A
Country	US
Kind code	B2
Filing date	Apr 23, 2015
Priority date	Apr 23, 2015
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

A method is described that includes translating higher level program code including higher level instructions having an instruction format that identifies pixels to be accessed from a memory with first and second coordinates from an orthogonal coordinate system into lower level instructions that target a hardware architecture having an array of execution lanes and a shift register array structure that is able to shift data along two different axis. The translating includes replacing the higher level instructions having the instruction format with lower level shift instructions that shift data within the shift register array structure.

First claim

The invention claimed is:

1. A method, comprising:
translating higher level program code including higher level instructions having an instruction format that identifies pixels to be accessed from a memory with first and second coordinates from an orthogonal coordinate system into lower level instructions that target a hardware architecture having an array of execution lanes and a shift register array structure that is able to shift data along two different axis,
the translating comprising replacing some of the higher level instructions having the instruction format with lower level shift instructions that are to shift data within the shift register array structure when executed by respective execution units of the execution lanes, the translating also comprising replacing others of the higher level instructions having the instruction format with lower level memory access instructions that specify a respective external memory address, the lower level memory access instructions to be executed by respective memory units within respective execution lanes of the execution lane array to access respective external memory space that is external to the respective execution lanes that execute the lower level memory access instructions to access the external memory space.

2. The method of claim 1 wherein the translating further comprises reordering a sequence of pixel accesses articulated in the some of the higher level instructions having the instruction format with a shift friendly sequence of lower level shift instructions.

3. The method of claim 2 wherein the higher level instructions having the instruction format include load instructions.

4. The method of claim 2 wherein the higher level instructions having the instruction format include store instructions.

5. The method of claim 1 wherein the hardware architecture includes a plurality of memories coupled to said shift register array structure to receive spill-over data from shifting operations of said shift-register array structure.

6. The method of claim 5 , further comprising:
identifying those of the higher level instructions that will cause a conflict accessing a particular one of the memories if implemented in hardware according to an accessing pattern specified at the higher level; and,
restructuring the access pattern to avoid the conflict.

7. The method of claim 6 wherein the conflict comprises two or more accesses of a same memory on a same cycle and the restructuring includes unrolling the two or more access to be sequential across multiple cycles.

8. The method of claim 7 wherein the accesses are targeted to a same look-up table.

9. The method of claim 7 wherein the accesses result from a same atomic update.

10. The method of claim 1 , further comprising:
recognizing that in a same cycle different execution lanes of the execution lane array desire to process respective data from different channels of an image, wherein the data is at an offset relative to the execution lanes' respective positions;
inserting program code to shift, by the offset, a sheet of index information identifying the respective data each execution lane desires;
inserting program code to cause a different set of different execution lanes spaced apart from the different execution lanes by the offset to load from the sheet of index information and to load from a corresponding appropriate channel for each such load; and,
inserting program code to shift the desired data to its respective one of the different execution lanes.

11. A non-transitory machine readable storage medium having stored thereon program code that when processed by a computing system causes a method to be performed, the method comprising:
translating higher level program code including higher level instructions having an instruction format that identifies pixels to be accessed from a memory with first and second coordinates from an orthogonal coordinate system into lower level instructions that target a hardware architecture having an array of execution lanes and a shift register array structure that is able to shift data along two different axis, the translating comprising replacing the higher level instructions having the instruction format with lower level shift instructions that are to shift data within the shift register array structure when executed by respective execution units of the execution lanes, the translating also comprising replacing others of the higher level instructions having the instruction format with lower level memory access instructions that specify a respective external memory address, the lower level memory access instructions to be executed by respective memory units within respective execution lanes of the execution lane array to access respective external memory space that is external to the respective execution lanes that execute the lower level memory access instructions to access the external memory space.

12. The non-transitory machine readable storage medium of claim 11 wherein the translating further comprises reordering a sequence of pixel accesses articulated in the some of the higher level instructions having the instruction format with a shift friendly sequence of lower level shift instructions.

13. The non-transitory machine readable storage medium of claim 12 , wherein the method further comprises re-ordering mathematical operation instructions to consume input values consistently with the shift friendly sequence.

14. The non-transitory machine readable storage medium of claim 12 wherein the higher level instructions having the instruction format include load instructions and/or store instructions.

15. The non-transitory machine readable storage medium of claim 11 wherein the hardware architecture includes a plurality of memories coupled to said shift register array structure to receive spill-over data from shifting operations of said shift-register array structure.

16. The non-transitory machine readable storage medium of claim 15 , wherein the method further comprises:
identifying those of the higher level instructions that will cause a conflict accessing a particular one of the memories if implemented in hardware according to an accessing pattern specified at the higher level; and,
restructuring the access pattern to avoid the conflict.

17. The non-transitory machine readable storage medium of claim 16 wherein the conflict comprises two or more accesses of a same memory on a same cycle and the restructuring includes unrolling the two or more access to be sequential across multiple cycles.

18. The non-transitory machine readable storage medium of claim 17 wherein the accesses are targeted to a same look-up table.

19. The non-transitory machine readable storage medium of claim 17 wherein the accesses result from a same atomic update.

20. A computing system comprising a plurality of processing cores and a machine readable medium, the machine readable medium containing program code that when processed by the plurality of processing cores causes a method to be performed, the method comprising:
translating higher level program code including higher level instructions having an instruction format that identifies pixels to be accessed from a memory with first and second coordinates from an orthogonal coordinate system into lower level instructions that target a hardware architecture having an array of execution lanes and a shift register array structure that is able to shift data along two different axis, the translating comprising replacing the higher level instructions havin

Assignees

• Google Inc

Inventors

• Meixner Albert

Classifications

• G06F9/30032

  Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE · CPC title

• G06F9/30145

  Instruction analysis, e.g. decoding, instruction word fields · CPC title

• G06F8/4441

  Reducing the execution time required by the program code · CPC title

• G06F8/451 Primary

  Code distribution (considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083) · CPC title

• G06F8/445

  Exploiting fine grain parallelism, i.e. parallelism at instruction level (run-time instruction scheduling G06F9/3836) · CPC title