US 9,069,545 B2 · Relaxation of synchronization for iterative convergent computations

Abstract

Systems and methods are disclosed that allow atomic updates to global data to be at least partially eliminated to reduce synchronization overhead in parallel computing. A compiler analyzes the data to be processed to selectively permit unsynchronized data transfer for at least one type of data. A programmer may provide a hint to expressly identify the type of data that are candidates for unsynchronized data transfer. In one embodiment, the synchronization overhead is reducible by generating an application program that selectively substitutes codes for unsynchronized data transfer for a subset of codes for synchronized data transfer. In another embodiment, the synchronization overhead is reducible by employing a combination of software and hardware by using relaxation data registers and decoders that collectively convert a subset of commands for synchronized data transfer into commands for unsynchronized data transfer.

Claims30

Dependent claims

A method of relaxing synchronization in a parallel computing system, said method comprising:

providing a system including a plurality of processors, said plurality of processors including at least one processor containing relaxation data registers and decoders;
generating an application program from a source program, said application running multiple processing threads in parallel, at least one thread performing iterative convergent computations in an iterative loop, wherein said application program includes an instruction for storing data representing a mode of synchronization relaxation in one of said relaxation data registers;
and
running said application program in said system to store said data in said relaxation data registers, wherein said system decodes at least one command in said application program for synchronized data access between processors in said system as at least one command for unsynchronized data access based on said stored data, said at least one command for unsynchronized data access employed to substitute an atomic operation applied to a variable in an iterative loop with a non-atomic operation.

1 more element

A method of relaxing synchronization in parallel computing, said method comprising:

providing a compiler module that enables recognition of a compiler directive for selective relaxation of synchronization during compilation;
providing a source program for an application, said source program including at least one instance of said compiler directive;
generating, employing a complier program that runs in at least one computing means, an application program from said source program by compiling said source program, said application running multiple processing threads in parallel, at least one thread performing iterative convergent computations in an iterative loop wherein at least one command for synchronized data access in said source program is compiled as at least one command for unsynchronized data access in said application program, said at least one command for unsynchronized data access substituting an atomic operation applied to a variable in an iterative loop with a non-atomic operation;
and
running said application program in a system including a plurality of processors and configured for parallel computing.

2 more elements

At least one non-transitory machine readable data storage medium embodying a plurality of programs, said plurality of programs comprising:

a compiler module including a code for enabling recognition of a compiler directive for selective relaxation of synchronization during compilation;
and
a compiler configured to use said complier module to recognize said compiler directive and to compile at least one command for synchronized data access in a source program as at least one command for unsynchronized data access in an application program upon detection of said compiler directive for selective relaxation of synchronization, wherein said application program runs multiple processing threads in parallel, at least one thread performing iterative convergent computations in an iterative loop, and said at least one command for unsynchronized data access employed substitutes an atomic operation applied to a variable in an iterative loop with a non-atomic operation.

Dependencies are inferred from the claim text.

Relaxation of synchronization for iterative convergent computations

Life of this patent

Relaxation of synchronization for iterative convergent computations

Life of this patent

Abstract

Claims30