System, method and computer program product for accelerating iterative graph algorithms by memory layout optimization

Patent metadata

Field	Value
Publication number	US-10740232-B2
Application number	US-201816217163-A
Country	US
Kind code	B2
Filing date	Dec 12, 2018
Priority date	Jan 31, 2017
Publication date	Aug 11, 2020
Grant date	Aug 11, 2020

Abstract

An iterative graph algorithm accelerating method, system, and computer program product, include recording an order of access nodes in a memory layout, reordering the access nodes in the memory layout in accordance with the recorded order, and updating edge information of the reordered access nodes.

First claim

What is claimed is:

1. A computer-implemented iterative graph algorithm accelerating method, the method comprising:
in a first phase, running a generic graph algorithm on a memory layout to determine an order of the access nodes in the memory layout;
recording the order of the access nodes in a memory layout;
reordering the access nodes in the memory layout in accordance with the recorded order; and
updating edge information of the reordered access nodes,
wherein the generic graph algorithm comprises one of a sequential graph algorithm and a parallel graph algorithm.

2. The computer-implemented method of claim 1 , further comprising, in a second phase, running generic graph algorithm on the reordered memory layout and updated edge information with all necessary computation for the algorithm.

3. The computer-implemented method of claim 1 , further comprising, during the first phase, confirming that each of the reordered access nodes is singularly visited in the memory layout.

4. The computer-implemented method of claim 1 , wherein the edge information comprises a node index.

5. The computer-implemented method of claim 1 , wherein the reordering relocates neighboring access nodes and connected access nodes together in the memory layout.

6. The computer-implemented method of claim 1 , wherein the reordering relocates an access node of the access nodes and each neighboring access node together in series in the memory layout, and
wherein the reordering relocates each connected access node to each of the neighboring access nodes relocated together to a location together after a last access node in the series in the memory layout.

7. The computer-implemented method of claim 1 , wherein the reordering changes a location of the access nodes in a cache memory of the memory layout.

8. The computer-implemented method of claim 1 , embodied in a cloud-computing environment.

9. A computer program product for iterative graph algorithm accelerating, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform:
in a first phase, running a generic graph algorithm on a memory layout to determine an order of the access nodes in the memory layout;
recording the order of the access nodes in a memory layout;
reordering the access nodes in the memory layout in accordance with the recorded order; and
updating edge information of the reordered access nodes,
wherein the generic graph algorithm comprises one of a sequential graph algorithm and a parallel graph algorithm.

10. The computer-program product of claim 9 , further comprising, in a second phase, running generic graph algorithm on the reordered memory layout and updated information with all necessary computation for the algorithm.

11. The computer-program product of claim 9 , further comprising, during the first phase, confirming that each of the reordered access nodes is singularly visited in the memory layout.

12. The computer-program product of claim 9 , wherein the edge information comprises a node index.

13. The computer-program product of claim 9 , wherein the reordering relocates neighboring access nodes and connected access nodes together in the memory layout.

14. The computer-program product of claim 9 , wherein the reordering relocates an access node of the access nodes and each neighboring access node together in series in the memory layout, and
wherein the reordering relocates each connected access node to each of the neighboring access nodes relocated together to a location together after a last access node in the series in the memory layout.

15. The computer-program product of claim 9 , wherein the reordering changes a location of the access nodes in a cache memory of the memory layout.

16. An iterative graph algorithm accelerating system, said system comprising:
a processor; and
a memory operably coupled to the processor, the memory storing instructions to cause the processor to perform:
in a first phase, running a generic graph algorithm on a memory layout to determine an order of the access nodes in the memory layout;
recording the order of the access nodes in a memory layout;
reordering the access nodes in the memory layout in accordance with the recorded order; and
updating edge information of the reordered access nodes,
wherein the generic graph algorithm comprises one of a sequential graph algorithm and a parallel graph algorithm.

17. The system of claim 16 , further comprising, in a second phase, running generic graph algorithm on the reordered memory layout and updated edge information with all necessary computation for the algorithm.

18. The system of claim 16 , further comprising, during the first phase, confirming that each of the reordered access nodes is singularly visited in the memory layout.

19. The system of claim 16 , wherein the edge information comprises a node index.

20. The system of claim 16 , embodied in a cloud-computing environment.

Assignees

• IBM

Inventors

• Cho Minsik
• Brand Daniel
• Finkler Ulrich Alfons
• Kung David Shing-Ki
• Puri Ruchir

Classifications

• G06F12/0893 Primary

  Caches characterised by their organisation or structure · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F2212/1008

  Correctness of operation, e.g. memory ordering · CPC title