Method of deadlock detection and synchronization-aware optimizations on asynchronous architectures

Patent metadata

Field	Value
Publication number	US-11429359-B2
Application number	US-202016933186-A
Country	US
Kind code	B2
Filing date	Jul 20, 2020
Priority date	Jun 22, 2018
Publication date	Aug 30, 2022
Grant date	Aug 30, 2022

Abstract

A method for improving the performance of applications executed within asynchronous processor architectures. In an embodiment, a method for improving execution time of compiled synchronized source code on an asynchronous processor architecture includes receiving, by a processing system, synchronized source code comprising synchronization instructions to synchronize execution of the synchronized source code on different pipelines of the asynchronous processor architecture. The method also includes analyzing, by the processing system, the synchronized source code to determine whether the synchronized source code includes a broken code condition. The method also includes, after determining, by the processing system, that the synchronized source code does not include a broken code condition, outputting an optimized synchronized source code generated by performing a corrective action on the synchronized source code to correct a synchronization inaccuracy, inconsistency, or inefficiency in the synchronized source code.

First claim

What is claimed is:

1. A method comprising:
receiving, by a processing system, synchronized source code comprising synchronization instructions to synchronize execution of the synchronized source code on different pipelines of an asynchronous processor architecture, wherein the synchronization instructions comprise wait events and set events;
determining, by the processing system, whether the synchronized source code includes a broken code condition, wherein the broken code condition is a deadlock condition determined according to a mismatch in the synchronization instructions of the synchronized source code, and wherein the mismatch in the synchronization instructions comprises one of a wait event without a corresponding set event or a set event without a corresponding wait event;
after determining, by the processing system, that the synchronized source code does not include any broken code condition, outputting an indication of synchronization inaccuracy, inconsistency, or inefficiency in the synchronized source code based on an optimization analysis of the synchronized source code; and
outputting, by the processing system, optimized synchronized source code generated by performing a corrective action on the synchronized source code to correct the synchronization inaccuracy, inconsistency, or inefficiency in the synchronized source code, wherein the corrective action comprises reduction of synchronization control overhead in the synchronized source code, and wherein the reduction of synchronization control overhead comprises:
moving one of the wait event or a barrier up in the synchronized source code when no condition in the synchronized source code between a first location in the synchronized source code occupied by the wait event or the barrier and a second location to which the wait event or the barrier is moved depend on the wait event, or
moving the set event down from a first location in the synchronized source code to a second location in the synchronized source code when no condition in the synchronization instructions depends on the set event is located between the first and the second location.

2. The method of claim 1 , further comprising:
presenting an alert that the synchronized source code includes a broken source code condition when the synchronized source code comprises a missing set event corresponding to the wait event.

3. The method of claim 2 , wherein the corrective action comprises:
providing a report comprises suggestion to a programmer to one of remove the wait event or insert the corresponding set event.

4. The method of claim 3 , wherein the synchronization inaccuracy, inconsistency, or inefficiency comprises a redundant synchronization instruction.

5. The method of claim 4 , wherein the corrective action comprises removing the redundant synchronization instruction.

6. The method of claim 4 , wherein the reduction of synchronization control overhead further comprises:
merging the redundant synchronization instruction in the synchronized source code.

7. The method of claim 1 , wherein the reduction of synchronization control overhead comprises:
hoisting synchronization instructions outside of a loop in the synchronized source code when there is no condition in the synchronized source code that uses the synchronization instructions inside the loop.

8. The method of claim 1 , wherein the outputting comprises:
outputting a report that includes information obtained from the optimization analysis.

9. The method of claim 1 , further comprising:
after determining, by the processing system, that the synchronized source code includes a broken source code condition, outputting a report that includes information indicative of the broken source code condition.

10. The method of claim 1 , the determining further including:
determining, by the processing system, whether the synchronized source code includes a second broken code condition, wherein the second broken code condition is one of an undefined behavior condition or a data race condition.

11. The method of claim 1 , further comprising:
generating a stage graph according to the synchronized source code, wherein the determining comprises determining whether the synchronized source code includes the broken code condition according to the stage graph.

12. The method of claim 11 , wherein the optimization analysis of the synchronized source code is performed using the stage graph.

13. The method of claim 1 , wherein the determining, whether the synchronized source code includes the broken code condition is based on a diagnostic analysis of the synchronized source code.

14. The method of claim 1 , wherein the outputting the indication and the outputting the optimized synchronized source code are performed without any runtime analysis.

15. A data processing system comprising:
a memory storing instructions; and
one or more processors in communication with the memory, wherein the one or more processors execute the instructions for the data processing system to perform:
receiving a synchronized source code comprising synchronization instructions to synchronize execution of the synchronized source code on different pipelines of an asynchronous processor architecture, wherein the synchronization instructions comprise wait events and set events;
determining whether the synchronized source code includes a broken code condition, wherein the broken code condition is a deadlock condition determined according to a mismatch in the synchronization instructions of the synchronized source code, and wherein the mismatch in the synchronization instructions comprises one of a wait event without a corresponding set event or a set event without a corresponding wait event;
after determining that the synchronized source code does not include any broken code condition, outputting an indication of synchronization inaccuracy, inconsistency, or inefficiency in the synchronized source code based on an optimization analysis of the synchronized source code; and
outputting optimized synchronized source code generated by performing a corrective action on the synchronized source code to correct the synchronization inaccuracy, inconsistency, or inefficiency in the synchronized source code, wherein the corrective action comprises reduction of synchronization control overhead in the synchronized source code, and wherein the reduction of synchronization control overhead comprises:
moving one of the wait event or a barrier up in the synchronized source code when no condition in the synchronized source code between a first location in the synchronized source code occupied by the wait event or the barrier and a second location to which the wait event or the barrier is moved depend on the wait event, or
moving the set event down from a first location in the synchronized source code to a second location in the synchronized source code when no condition in the synchronization instructions depends on the set event is located between the first and the second location.

16. A non-transitory computer-readable medium storing instructions that, when executed by one or more processors of a computing device, causes the one or more processors to perform operations, the operations comprising:
receiving synchronized source code comprising synchronization instructions to synchronize execution of the synchronized source code on different pipelines of an asynchronous processor architecture, wherein the synchronization instructions comprise wait events and set events;
determining whether the synchronized source code includes a broken code condition, wherein the

Assignees

• Huawei Tech Co Ltd

Inventors

• Eltantawy Ahmed Mohammed Elshafiey Mohammed
• Gao Yaoqing
• Rodrigues Christopher
• Hai Lijuan

Classifications

• G06F8/4435 Primary

  Detection or removal of dead or redundant code · CPC title

• G06F8/454

  Consistency (cache consistency protocols in hierarchically structured memory systems G06F12/0815) · CPC title

• G06F9/524 Primary

  Deadlock detection or avoidance · CPC title

• G06F8/71

  Version control (security arrangements therefor G06F21/57); Configuration management · CPC title