Global optimal path determination utilizing parallel processing

Patent metadata

Field	Value
Publication number	US-10515431-B2
Application number	US-201715839640-A
Country	US
Kind code	B2
Filing date	Dec 12, 2017
Priority date	Dec 12, 2017
Publication date	Dec 24, 2019
Grant date	Dec 24, 2019

Abstract

Embodiments are generally directed to global optimal path determination utilizing parallel processing. An embodiment of an apparatus includes a central processing unit (CPU); a graphical processing unit (GPU), the GPU being capable of a plurality of processing threads; and a memory to store data for a system under evaluation, the system under evaluation including a set of nodes having a first endpoint, a second endpoint, and multiple paths between the first endpoint and the second endpoint. The apparatus is to determine a most energy efficient path between the first endpoint and the second endpoint utilizing parallel processing of a push and relabel graph cut algorithm. Performance of the push and relabel algorithm includes a plurality of process iterations, each process iteration including performance of a relabel operation, a push operation in a first direction, and a push operation in a second direction.

First claim

What is claimed is:

1. An apparatus comprising:
a central processing unit (CPU);
a graphical processing unit (GPU), the GPU being capable of a plurality of processing threads; and
a memory to store data for a system under evaluation, the system under evaluation including a set of nodes having a first endpoint, a second endpoint, and multiple paths between the first endpoint and the second endpoint;
wherein the apparatus is to determine a most energy efficient path between the first endpoint and the second endpoint utilizing parallel processing of a push and relabel graph cut algorithm, the parallel processing of the push and relabel graph cut algorithm including the apparatus to partition the system under evaluation into a plurality of blocks; and
wherein performance of the push and relabel algorithm includes a plurality of process iterations, each process iteration including performance of a relabel operation, a push operation in a first direction, and a push operation in a second direction, wherein the push operation in a first direction is a vertical push operation for each row in each block and the push operation in a second direction is a horizontal push operation for each column in each block.

2. The apparatus of claim 1 , wherein the parallel processing of the push and relabel graph cut algorithm is performed at least in part by the GPU.

3. The apparatus of claim 2 , wherein the system under evaluation includes a set of pixels for a vision technology.

4. The apparatus of claim 3 , wherein the vision technology includes one of an image segmentation technology or a video stitching technology.

5. The apparatus of claim 2 , wherein the parallel processing of the push and relabel graph cut algorithm includes application of SIMD (Single Instruction Multiple Data) operations.

6. The apparatus of claim 1 , wherein the parallel processing of the push and relabel graph cut algorithm includes assigning threads to the blocks for the relabel operation and assigning threads to the blocks for the push operation.

7. The apparatus of claim 1 , wherein the horizontal push operation includes a transposition operation of the block, performance of a vertical push, and a reverse transposition of the block.

8. The apparatus of claim 1 , wherein the push and relabel algorithm is performed without enforcing dependencies of all neighboring nodes in the set of nodes.

9. A processing system comprising:
a central processing unit (CPU);
a graphical processing unit (GPU), the GPU being capable of a plurality of processing threads; and
dynamic random access memory (DRAM) to store data for a system under evaluation, the system under evaluation including a set of pixels to perform a vision technology, the system having a source endpoint, a sink endpoint, and multiple paths between the source and the sink;
wherein the processing system is to determine a most energy efficient path between the source and the sink utilizing parallel processing of a push and relabel graph cut algorithm, the parallel processing of the push and relabel graph cut algorithm being performed at least in part by the GPU, the parallel processing of the push and relabel graph cut algorithm including the processing system to partition the set of pixels into a plurality of blocks; and
wherein performance of the push and relabel algorithm includes a plurality of process iterations, each process iteration including performance of a relabel operation, a push operation in a first direction, and a push operation in a second direction, wherein the push operation in a first direction is a vertical push operation for each row of pixels in each block and the push operation in a second direction is a horizontal push operation for each column of pixels in each block.

10. The processing system of claim 9 , wherein the vision technology includes one of an image segmentation technology or a video stitching technology.

11. The processing system of claim 9 , wherein the parallel processing of the push and relabel graph cut algorithm includes application of SIMD (Single Instruction Multiple Data) operations.

12. The processing system of claim 9 , wherein the parallel processing of the push and relabel graph cut algorithm includes assigning threads to the blocks for the relabel operation and assigning threads to the blocks for the push operation.

13. The processing system of claim 9 , wherein the horizontal push operation includes a transposition operation of the block, performance of a vertical push, and a reverse transposition of the block.

Assignees

• Intel Corp

Inventors

• Yang Yuenian
• Chen Kaiyu
• Kuzma Andrew

Classifications

• G06T15/005

  General purpose rendering architectures · CPC title

• G06F9/3897

  with adaptable data path · CPC title

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06T2210/52

  Parallel processing · CPC title

• G06T1/60

  Memory management · CPC title