Systems and methods for creating and using a data structure for parallel programming

• US 10,585,845 B2
• Filed: 10/14/2016
• Issued: 03/10/2020
• Est. Priority Date: 11/02/2015
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Chen, Liya, Tian, Chen, Hu, Ziang
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): Huynh, Tina
• Application Number:
  US15/293,413
• Publication Number:
  US 20170124020A1
• Time in Patent Office: 1,243 Days
• CPC Class Codes: G06F 15/17318 Parallel communications techniques, e.g. gather, scatter, reduce, roadcast, multicast, all to all
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/445 Program loading or initiating bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

System and method embodiments are provided for creating data structure for parallel programming. A method for creating data structures for parallel programming includes forming, by one or more processors, one or more data structures, each data structure comprising one or more global containers and a plurality of local containers. Each of the global containers is accessible by all of a plurality of threads in a multi-thread parallel processing environment. Each of the plurality of local containers is accessible only by a corresponding one of the plurality of threads. A global container is split into a second plurality of local containers when items are going to be processed in parallel and two or more local containers are merged into a single global container when a parallel process reaches a synchronization point.

Claims

1. A method in a data processing system for creating data structures for parallel programming, comprising:

forming, by one or more processors, a first global container including a plurality of local containers, the first global container having a first serial data structure comprising an ordered array-based data structure, the first global container being accessible by all threads of a plurality of threads in a multi-thread parallel processing environment, each local container of the plurality of local containers being accessible only by a corresponding thread of the plurality of threads, each local container of the plurality of local containers comprising a trace identifier (tid), a start index, and an end index, the tid identifying the corresponding thread, the start index and the end index identifying a corresponding data region of the first global container, each local container of the plurality of local containers having a same second serial data structure different from the first serial data structure of the first global container;

splitting the first global container into a second plurality of local containers when items in the first global container are to be processed in parallel;

executing a parallel process by the plurality of threads, each thread of the plurality of threads data stored in the corresponding data region of the each thread during the parallel process;

merging two or more local containers into a second global container when the parallel process reaches a synchronization point;

executing instructions provided by at least one of the first and second global containers to obtain a result; and

transmitting the result to a node in a network,

the result comprising path information for a path across the network from a source node to an end node, the transmitting comprising transmitting at least a portion of the path information to the node, the path information causing the node to facilitate transmitting data from the source node to the end node.

2. The method of claim 1, wherein the first and second global containers and the plurality of local containers support a set of access methods to the data structures comprising one or more of:

a push( ) method;

a pop( ) method;

a split( ) method; and

a merge( ) method.

3. The method of claim 1, wherein the one or more processors comprise a multi-core processor.

4. The method of claim 1, wherein the first and second global containers and the plurality of local containers include a respective serial common data structure.

5. The method of claim 1, wherein executing the instructions further comprises executing instructions provided by the merged local containers.

6. The method of claim 1, wherein executing the instructions comprises executing instructions provided by the first global container.

7. The method of claim 1, wherein executing the instructions comprises executing instructions provided by the second global container.

8. The method of claim 1, wherein the transmitting comprises transmitting the result to the node in the network and causing the data processing system to present one or more images, a sound, or a vibration to a user.

21. The method of claim 1, wherein the merging the two or more local containers into the second global container is performed after executing a portion of the parallel process, and further comprising:

after merging the two or more local containers into the second global container, continuing execution of the parallel process by the plurality of threads.

9. A data processing system for creating data structures for parallel programming comprising:

one or more processors; and

a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including computer instructions for;

forming a first global container including a plurality of local containers, the first global container having a first serial data structure comprising an ordered array-based data structure, the first global container being accessible by all threads of a plurality of threads in a multi-thread parallel processing environment, each local container of the plurality of local containers being accessible only by a corresponding thread of the plurality of threads, each local container of the plurality of local containers comprising a trace identifier (tid), a start index, and an end index, the tid identifying the corresponding thread, the start index and the end index identifying a corresponding data region of the first global container, each local container of the plurality of local containers having a same second serial data structure being different from the first serial data structure of the first global container;

splitting the first global container into a second plurality of local containers when items in the first global container are to be processed in parallel;

executing a parallel process by the plurality of threads, each thread of the plurality of threads processing data stored in the corresponding data region of the each thread during the parallel process;

merging two or more local containers into a second global container when the parallel process reaches a synchronization point;

executing instructions provided by at least one of the first and second global containers to obtain a result; and

transmitting the result to a node in a network,

the result comprising path information for a path across the network from a source node to an end node, the transmitting comprising transmitting at least a portion of the path information to the node, the path information causing the node to facilitate transmitting data from the source node to the end node.

10. The data processing system of claim 9, wherein the first and second global containers and the plurality of local containers support a set of access methods to the data structures comprising one or more of:

a push( ) method;

a pop( ) method;

a split( ) method; and

a merge( ) method.

11. The data processing system of claim 9, wherein the one or more processors comprise a multi-core processor.

12. The data processing system of claim 9, wherein the first and second global containers and the plurality of local containers include a respective serial common data structure.

13. The data processing system of claim 9, wherein executing the instructions further comprises executing instructions provided by the merged local containers.

14. The data processing system of claim 9, wherein the transmitting comprises transmitting the result to the node in the network and causing the data processing system to present one or more images, a sound, or a vibration to a user.

19. The data processing system of claim 9, wherein the first global container and the second global container are different containers.

20. The data processing system of claim 9, wherein the first global container and the second global container are the same containers.

22. The data processing system of claim 9, wherein the computer instructions for merging the two or more local containers into the second global container are performed after executing a portion of the parallel process, and wherein the programming includes further computer instructions for:

after merging the two or more local containers into the second global container, continuing execution of the parallel process by the plurality of threads.

15. A non-transitory computer-readable media storing computer instructions for creating data structures for parallel programming in a data processing system, that when executed by one or more processors, cause the one or more processors to perform the steps of:

forming a first global container including a plurality of local containers, the first global container having a first serial data structure comprising an ordered array-based data structure, the first global container being accessible by all threads of a plurality of threads in a multi-thread parallel processing environment, each local container of the plurality of local containers being accessible only by a corresponding thread of the plurality of threads, each local container of the plurality of local containers comprising a trace identifier (tid), a start index, and an end index, the tid identifying the corresponding thread, the start index and the end index identifying a corresponding data region of the first global container, each local container of the plurality of local containers having a same second serial data structure, the second serial common data structure being different from the first serial common data structure of the first global container;

splitting the first global container into a second plurality of local containers when items in the first global container are to be processed in parallel;

executing a parallel process by the plurality of threads, each thread of the plurality of threads processing data stored in the corresponding data region of the each thread during the parallel process;

merging two or more local containers into a second global container when the parallel process reaches a synchronization point;

executing instructions provided by at least one of the first and second global containers to obtain a result; and

transmitting the result to a node in a network,

the result comprising path information for a path across the network from a source node to an end node, the transmitting comprising transmitting at least a portion of the path information to the node, the path information causing the node to facilitate transmitting data from the source node to the end node.

16. The non-transitory computer-readable media of claim 15, wherein the first and second global containers and the plurality of local containers support a set of access methods to the data structures comprising one or more of:

a push( ) method;

a pop( ) method;

a split( ) method; and

a merge( ) method.

17. The non-transitory computer-readable media of claim 15, wherein the one or more processors comprise a multi-core processor.

18. The non-transitory computer-readable media of claim 15, wherein the first and second global containers and the plurality of local containers include a respective serial common data structure.

23. The non-transitory computer-readable media of claim 15, wherein the computer instructions for merging the two or more local containers into the second global container are performed after executing a portion of the parallel process, and wherein the non-transitory computer-readable media further stores computer instructions that cause the one or more processors to perform the steps of:

after merging the two or more local containers into the second global container, continuing execution of the parallel process by the plurality of threads.

24. The data processing system of claim 15, wherein the transmitting comprises transmitting the result to the node in the network and causing the data processing system to present one or more images, a sound, or a vibration to a user.