Synchronization of independent clocks
AssigneeInternational Business Machines Corporation
InventorsMarina Biberstein, Yuval Harel, Andre Heilper
Life of this patent
Estimating the term…
Abstract
A system and method to synchronize independent local clocks in multi-core processing system are disclosed. A shared counter or a shared memory/file is provided to establish a partial happened-before relationship (e1<e2 in the happened-before order if we know that the event e1 happened before the event e2) and a synchronizer device is utilized to generate a global time of events in threads or processes. The synchronizer device estimates each clock's start time and approximates elapsed time between events in threads or processes by executing an all-pair shortest-path algorithm.
Claims2
A method to perform synchronization of independent local clocks governing processes executed by independent processing cores in multi-processing system for program debugging, performance analysis, and visualization comprising:
- (a) detecting events generated at local processing cores;
- (b) recording local timestamps of events based on clocks upon detecting said events;
- (c) optionally establishing happened-before relationship by utilizing a shared resource;
- (d) deriving a set of constraints on said clocks' relative start time by using said local timestamps and said happened-before relationship;
- (e) processing to improve said set of constraints;
- (f) if no solution of said set of constraints is found while said processing, relaxing the set of constraints;
- (g) repeating step (f) until a solution which satisfies said set of constraints is found;
- (h) based on resulting constraints, calculating elapsed times between said clocks' start times;
- (i) assigning global timestamps to said clocks' start times based on said elapsed times;
- and
- (j) assigning global timestamps to said events based on said local timestamps and said global timestamps of said clocks' start times.
A processing system to perform synchronization of independent local clocks governing processes executed by independent processing cores in multi-processing system for program debugging, performance analysis, and visualization comprising:
- means for detecting events generated at local processing cores;
- means for recording local timestamps of events based on clocks upon detecting said events;
- means for optionally establishing happened-before relationship by utilizing a shared resource;
- means for deriving a set of constraints on said clocks' relative start time by using said local timestamps and said happened-before relationship;
- means for processing to improve the set of constraints;
- means for relaxing the set of constraints, if no solution of said set of constraints is found while said processing;
- means for repeating said relaxing the set of constraints, until a solution which satisfies said set of constraints is found;
- means for calculating elapsed times between said clocks' start times, based on resulting constraints;
- means for assigning global timestamps to said clocks' start times based on said elapsed times;
- and
- means for assigning global timestamps to said events based on said local timestamps and said global timestamps of said clocks' start times.
Dependencies are inferred from the claim text.