Architecture and services supporting reconfigurable synchronization in a multiprocessing system

• US 10,360,079 B2
• Filed: 06/16/2017
• Issued: 07/23/2019
• Est. Priority Date: 06/16/2017
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations LLC (General Motors Company)
• Inventors: Wang, Shige, Lusko, Stephen G.
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US15/625,051
• Publication Number:
  US 20180365080A1
• Time in Patent Office: 767 Days
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A synchronization method in a multiprocessor system is provided. The method includes providing a plurality of synchronization mechanisms for synchronizing data to be accessed by a plurality of concurrently executable tasks, analyzing design information and runtime information for application software that includes the concurrently executable tasks, identifying, based on the analysis, software architecture patterns for the concurrently executable tasks that access a shared variable, and associating, based on the analysis, each of the software architecture patterns to one or more of the synchronization mechanisms. The method further includes generating synchronization table entries for a synchronization table that identify the shared variable, the software architecture pattern for the concurrently executable tasks that access the shared variable, and the one or more synchronization mechanisms associated with the software architecture pattern and also includes accessing the shared variable using the one or more synchronization mechanisms identified in the synchronization table.

Claims

1. A synchronization method in a multiprocessor system, the method comprising:

providing a plurality of synchronization mechanisms as library services for synchronizing data to be accessed by a plurality of concurrently executable tasks that are executable on one or more processor cores;

analyzing design information and runtime information for application software that includes the concurrently executable tasks;

identifying, based on the analysis, software architecture patterns for the concurrently executable tasks that access a shared variable;

associating, based on the analysis, each of the software architecture patterns to one or more of the synchronization mechanisms;

generating synchronization table entries for a synchronization table that identify the shared variable, the software architecture pattern for the concurrently executable tasks that access the shared variable, and the one or more synchronization mechanisms associated with the software architecture pattern; and

accessing the shared variable using the one or more synchronization mechanisms identified in the synchronization table for accessing the shared variable, wherein accessing the shared variable comprises;

locating the shared variable in the synchronization table;

identifying the one or more synchronization mechanisms assigned to the shared variable in the synchronization table;

waiting until access is granted to the shared variable;

protecting data in the shared variable by invoking the assigned one or more synchronization mechanisms; and

adjusting task execution per the assigned one or more synchronization mechanisms; and

releasing the data protection for the shared variable after access to the shared variable is complete.

2. The method of claim 1 wherein:

the synchronization table comprises a sync type table and a sync management table;

the sync type table records an identifier for the shared variable and information regarding the software architectural pattern for the tasks that access the shared variable; and

the sync management table records the identifier for the shared data sets recorded in the sync type table, the synchronization mechanisms to be employed to control access to the shared variables, and additional management information for use in managing the implementation of the sync mechanisms.

3. The method of claim 2 wherein the sync type table comprises a data record for each shared variable and wherein each record comprises:

the identifier for one of the shared variables;

the identity of an executable function that provides data to the one shared variable;

an identifier for a task that schedules the executable provider function;

the identity of the executable function that consumes data from the one shared variable;

an identifier for a task that schedules the executable consumer function; and

an indication regarding whether the task that schedules the executable provider function and the task that schedules the executable consumer function are performed by the same processor core.

4. The method of claim 2 wherein the information regarding the software architectural pattern for the tasks that access the shared variable is determined from a static dependency analysis of the tasks.

5. The method of claim 2 wherein the sync management table comprises a data record for each shared variable and wherein each record comprises:

the identifier for one of the shared variables;

an identifier for the synchronization mechanism assigned to the task that schedules the executable function that provides data to the one shared variable;

an identifier for the synchronization mechanism assigned to the task that schedules the executable function that consumes data from the one shared variable; and

a preempt ceiling count that may be used to limit the number of synchronization mechanisms that may be active concurrently.

6. The method of claim 2 wherein the synchronization mechanisms to be employed to control access to the shared variables is determined from a dynamic dependency analysis and throughput analysis of application software.

7. The method of claim 6 wherein:

the protection operation comprises a provider protection operation when data is to be written to the shared variable and a consumer protection operation when data is to be read from the shared variable; and

the release operation corresponding the to the provider protection operation comprises a provider release operation and the release operation corresponding to the consumer protection operation comprises a consumer release operation.

8. The method of claim 1 wherein the design information comprises the software architecture, the executing tasks, and the accessed data.

9. The method of claim 1 wherein the runtime information comprises parallelism, concurrency, and throughput.

10. The method of claim 9 wherein releasing the shared variable further comprises releasing the resource count update entry in the synchronization table corresponding to the shared variable.

11. The method of claim 1 further comprising:

providing an application program interface (API) to be called by a software application to invoke a synchronization mechanism during runtime.

12. The method of claim 11 wherein a call to the API comprises:

a protection operation in the software application prior to an operation involving the shared variable; and

a release operation in the software application after the operation involving the shared variable.

13. The method of claim 1 wherein accessing the shared variable further comprises entering a resource count update entry in the synchronization table corresponding to the shared variable.

14. The method of claim 1 wherein the synchronization mechanisms are selected from a group comprising a lock schedule, a spinlock, a semaphore, a barrier, a mutex, a readers-writer lock, a read-copy-update (RCU), a turnstile, a conditional variable, an adaptive mutex, and a non-waiting synchronization mechanism such as wait-free or lock-free.

15. A computer system comprising:

a plurality of processor cores; and

non-transient computer readable storage medium embodying programming instructions configurable to perform a method, the method comprising;

providing a plurality of synchronization mechanisms as library services for synchronizing data to be accessed by a plurality of concurrently executable tasks that are executable on one or more processor cores;

analyzing design information and runtime information for application software that includes the concurrently executable tasks to form a database of constraints, the database of constraints including the software architecture pattern for the concurrently executing tasks that access a shared variable;

associating, based on the analysis, each of the software architecture patterns to one or more of the synchronization mechanisms;

generating synchronization table entries for a synchronization table from the database of constraints, the synchronization table identifying the shared variable, the software architecture pattern for the concurrently executable tasks that access the shared variable, and the one or more synchronization mechanisms associated with the software architecture pattern;

accessing the shared variable using the one or more synchronization mechanisms identified in the synchronization table for accessing the shared variable, wherein accessing the shared variable comprises;

locating the shared variable in the synchronization table;

identifying the one or more synchronization mechanisms assigned to the shared variable in the synchronization table;

waiting until access is granted to the shared variable;

protecting data in the shared variable by invoking the assigned one or more synchronization mechanisms; and

adjusting task execution per the assigned one or more synchronization mechanisms; and

releasing the data protection for the shared variable after access to the shared variable is complete.

16. The computer system of claim 15, wherein:

the synchronization table comprises a sync type table and a sync management table;

the sync type table records an identifier for the shared variable and information regarding the software architectural pattern for the tasks that access the shared variable; and

the sync management table records the identifier for the shared data sets recorded in the sync type table, the synchronization mechanisms to be employed to control access to the shared variables, and additional management information for use in managing the implementation of the sync mechanisms.

17. The computer system of claim 16, wherein the sync type table comprises a data record for each shared variable and wherein each record comprises:

the identifier for one of the shared variables;

the identity of an executable function that provides data to the one shared variable;

an identifier for a task that schedules the executable provider function;

the identity of the executable function that consumes data from the one shared variable;

an identifier for a task that schedules the executable consumer function; and

an indication regarding whether the task that schedules the executable provider function and the task that schedules the executable consumer function are performed by the same processor core.

18. The computer system of claim 16, wherein the sync management table comprises a data record for each shared variable and wherein each record comprises:

the identifier for one of the shared variables;

an identifier for the synchronization mechanism assigned to the task that schedules the executable function that provides data to the one shared variable;

an identifier for the synchronization mechanism assigned to the task that schedules the executable function that consumes data from the one shared variable; and

a preempt ceiling count that may be used to limit the number of synchronization mechanisms that may be active concurrently.

19. A non-transitory computer readable storage medium embodying programming instructions configurable to cause a multiprocessor system to perform a method, the method comprising:

providing a plurality of synchronization mechanisms as library services for synchronizing data to be accessed by a plurality of concurrently executable tasks that are executable on one or more processor cores;

analyzing design information and runtime information for application software that includes the concurrently executable tasks to form a database of constraints, the database of constraints including the software architecture pattern for the concurrently executing tasks that access a shared variable;

associating, based on the analysis, each of the software architecture patterns to one or more of the synchronization mechanisms;

generating synchronization table entries for a synchronization table from the database of constraints, the synchronization table identifying the shared variable, the software architecture pattern for the concurrently executable tasks that access the shared variable, and the one or more synchronization mechanisms associated with the software architecture pattern;

accessing the shared variable using the one or more synchronization mechanisms identified in the synchronization table for accessing the shared variable, wherein accessing the shared variable comprises;

locating the shared variable in the synchronization table;

identifying the one or more synchronization mechanisms assigned to the shared variable in the synchronization table;

waiting until access is granted to the shared variable;

protecting data in the shared variable by invoking the assigned one or more synchronization mechanisms; and

adjusting task execution per the assigned one or more synchronization mechanisms; and

releasing the data protection for the shared variable after access to the shared variable is complete.

20. The non-transitory computer readable storage medium of claim 19, wherein:

the synchronization table comprises a sync type table and a sync management table;

the sync type table records an identifier for the shared variable and information regarding the software architectural pattern for the tasks that access the shared variable; and

the sync management table records the identifier for the shared data sets recorded in the sync type table, the synchronization mechanisms to be employed to control access to the shared variables, and additional management information for use in managing the implementation of the sync mechanisms.