SYNCHRONIZATION OF INDEPENDENT CLOCKS

• US 20090158075A1
• Filed: 10/10/2008
• Published: 06/18/2009
• Est. Priority Date: 12/18/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Harel, Yuval, Heilper, Andre, Biberstein, Marina
• Application Number:
  US12/249,082
• Publication Number:
  US 20090158075A1
• Time in Patent Office: Days
• US Class Current: 713/375
• CPC Class Codes: G06F 1/12 Synchronisation of different clock signals provided by a plurality of clock generators
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0638 Clock or time synchronisation among nodes; Internode synchronisation synchronization for ring networks H04L12/422; data switching networks with synchronous transmission H04L12/43

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

Claims

1. A processing system to perform synchronization of independent local clocks comprising:

a multi-core processor having a plurality of processing cores, said multi-core processor having processes running on said processing cores, wherein each process is executed based on each different core, said processing cores having local clocks;

an event tracing component to record events occurring on said each core, to record timestamps of events according to said local clocks, and to record event data to establish a partial happened-before relationship of said events across said processing cores; and

an off-line clock synchronizer to establish constraints on the start times of said clocks based on the timestamps and the partial happened-before relationship, to execute an all-pairs shortest-path algorithm on said constraints, while repeatedly relaxing said constraints until no negative cycles is found, to calculate transitive closure of said constraints to improve said constraints, to calculate elapsed times between local clocks'"'"' start times based on said transitive closure of said constraints, to assign global timestamps to local clocks'"'"' start times based on said elapsed times, and to assign global timestamps to said events based on said global timestamps of said clocks'"'"' start times and said timestamps of said events,

wherein said assigned global timestamps of said clocks'"'"' start times and said assigned global timestamps of said events are used to facilitate one or more of;

program debugging, performance analysis and visualization of said processing system.