# US 2019/0317746 A1 · Low-overhead detection techniques for synchronization problems in parallel and concurrent software

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0317746 A1
- Document ID: US20190317746A1
- Status: Published application
- Kind: A1
- Application number: 16/385,118
- Filed: 2019-04-16
- Published: 2019-10-17
- Earliest claimed: 2018-04-17
- Assignees: Board of Regents, The University of Texas System
- Applicants: The Board of Regents of The University of Texas System
- Inventors: Tongping Liu; Mohammad Mejbah ul Alam; Abdullah Al Muzahid
- Web page: https://patentgrep.com/patent/US20190317746A1

## CPC

- G06F 8/458: {Synchronisation, e.g. post-wait, barriers, locks (synchronisation among tasks G06F9/52)}
- G06F 9/453: {Help systems}
- G06F 9/4856: {resumption being on a different machine, e.g. task migration, virtual machine migration (G06F9/5088 takes precedence)}
- G06F 9/524: {Deadlock detection or avoidance}
- G06F 9/526: {Mutual exclusion algorithms}
- G06F 9/528: {by using speculative mechanisms}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The techniques described herein may provide techniques to detect, categorize, and diagnose synchronization issues that provide improved performance and issue resolution. For example, in an embodiment, a method may comprise detecting occurrence of synchronization performance problems in software code, when at least some detected synchronization performance problems occur when a contention rate for software locks is low, determining a cause of the synchronization performance problems, and modifying the software code to remedy the cause of the synchronization performance problems so as to improve synchronization performance of the software code.

## Claims

### Claim 1

A method implemented in a computer system comprising a processor, memory accessible by the processor, and program instructions stored in the memory and executable by the processor to perform a method comprising:
detecting occurrence of synchronization performance problems in software code;
when at least some detected synchronization performance problems occur when a contention rate for software locks is low, determining a cause of the synchronization performance problems; and
modifying the software code to remedy the cause of the synchronization performance problems so as to improve synchronization performance of the software code.

### Claim 2 (depends on 1)

The method of claim 1, wherein the cause of the synchronization performance problems comprises at least one of: improper primitives, improper granularity, over-synchronization, asymmetric contention, and load imbalance.

### Claim 3 (depends on 2)

The method of claim 2, wherein:
when the cause of the synchronization performance problems comprises improper primitives, modifications to the software code include modifying atomic instructions and spin locks;
when the cause of the synchronization performance problems comprises improper granularity, modifications to the software code include modifying fineness of locks and reducing a critical section;
when the cause of the synchronization performance problems comprises over-synchronization, modifications to the software code include removing an unnecessary lock and removing a common lock;
when the cause of the synchronization performance problems comprises asymmetric contention, modifications to the software code include distributing contentions;
when the cause of the synchronization performance problems comprises load imbalance, modifications to the software code include redistributing tasks among threads.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
when at least some detected synchronization performance problems occur when a contention rate for software locks is high and a frequency of lock acquisitions is low, determining a cause of the synchronization performance problems; and
modifying the software code to remedy the cause of the synchronization performance problems so as to improve synchronization performance of the software code.

### Claim 5 (depends on 1)

The method of claim 1, wherein detecting occurrence of synchronization performance problems in software code comprises using a first-phase detection tool.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
when at least some detected synchronization performance problems occur when a contention rate for software locks is high and a frequency of lock acquisitions is low, a contention rate for software locks is high and a frequency of lock acquisitions is high, or a contention rate for software locks is low and a frequency of lock acquisitions is high, determining a cause of the synchronization performance problems comprises using a second-phase diagnosis tool.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
monitoring execution of the software code and collecting information about explicit synchronization primitives.

### Claim 8 (depends on 7)

The method of claim 7, wherein the collecting information comprises:
for a lock, how many times the lock is acquired, how many times the lock is found to be contended, and how long a thread waits for the lock,
for a try-lock, how many times the try-lock is called and how many times the try-lock fails because of contention, and
for load imbalance, how long different threads execute and how long they are waiting for synchronizations.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
collecting callsites for each synchronization operation.

### Claim 10 (depends on 9)

The method of claim 9, wherein the detection comprises at least one of:
checking behavior of all locks with similar callsites to identify asymmetric contention;
computing and comparing waiting time of different threads to identify load imbalance; and
checking individual as well as collective information of locks, using callsites, to identify other synchronization performance problems.

### Claim 11

A system comprising a processor, memory accessible by the processor, and program instructions stored in the memory and executable by the processor to perform a method comprising:
detecting occurrence of synchronization performance problems in software code;
when at least some detected synchronization performance problems occur when a contention rate for software locks is low, determining a cause of the synchronization performance problems; and
modifying the software code to remedy the cause of the synchronization performance problems so as to improve synchronization performance of the software code.

### Claim 12 (depends on 11)

The system of claim 11, wherein the cause of the synchronization performance problems comprises at least one of: improper primitives, improper granularity, over-synchronization, asymmetric contention, and load imbalance.

### Claim 13 (depends on 12)

The system of claim 12, wherein:
when the cause of the synchronization performance problems comprises improper primitives, modifications to the software code include modifying atomic instructions and spin locks;
when the cause of the synchronization performance problems comprises improper granularity, modifications to the software code include modifying fineness of locks and reducing a critical section;
when the cause of the synchronization performance problems comprises over-synchronization, modifications to the software code include removing an unnecessary lock and removing a common lock;
when the cause of the synchronization performance problems comprises asymmetric contention, modifications to the software code include distributing contentions;
when the cause of the synchronization performance problems comprises load imbalance, modifications to the software code include redistributing tasks among threads.

### Claim 14 (depends on 11)

The system of claim 11, further comprising:
when at least some detected synchronization performance problems occur when a contention rate for software locks is high and a frequency of lock acquisitions is low, determining a cause of the synchronization performance problems; and
modifying the software code to remedy the cause of the synchronization performance problems so as to improve synchronization performance of the software code.

### Claim 15 (depends on 11)

The system of claim 11, wherein detecting occurrence of synchronization performance problems in software code comprises using a first-phase detection tool.

### Claim 16 (depends on 15)

The system of claim 15, further comprising:
when at least some detected synchronization performance problems occur when a contention rate for software locks is high and a frequency of lock acquisitions is low, a contention rate for software locks is high and a frequency of lock acquisitions is high, or a contention rate for software locks is low and a frequency of lock acquisitions is high, determining a cause of the synchronization performance problems comprises using a second-phase diagnosis tool.

### Claim 17 (depends on 11)

The system of claim 11, further comprising:
monitoring execution of the software code and collecting information about explicit synchronization primitives.

### Claim 18 (depends on 17)

The system of claim 17, wherein the collecting information comprises:
for a lock, how many times the lock is acquired, how many times the lock is found to be contended, and how long a thread waits for the lock,
for a try-lock, how many times the try-lock is called and how many times the try-lock fails because of contention, and
for load imbalance, how long different threads execute and how long they are waiting for synchronizations.

### Claim 19 (depends on 11)

The system of claim 11, further comprising:
collecting callsites for each synchronization operation.

### Claim 20 (depends on 19)

The system of claim 19, wherein the detection comprises at least one of:
checking behavior of all locks with similar callsites to identify asymmetric contention;
computing and comparing waiting time of different threads to identify load imbalance; and
checking individual as well as collective information of locks, using callsites, to identify other synchronization performance problems.
