Browse Prior Art Database

High Performance Algorithm for Calculating a Multiprocessor Safe Global Counter

IP.com Disclosure Number: IPCOM000028724D
Original Publication Date: 2004-May-27
Included in the Prior Art Database: 2004-May-27
Document File: 2 page(s) / 33K

Publishing Venue

IBM

Abstract

This publication describes a new algorithm designed for systems that contain asynchronously clocked processors. The algorithm was designed to eliminate the use of any spin locks when calculating a global counter value because the amount of time required by each processsor in a multiprocessor environment to obtain a lock is indeterminate. In addition, the objective of the new design was to allow a smaller n-bit counter, that wraps once approximately every X minutes to run continuously without requiring the counter value to be reset to zero when the epoch value being maintained is adjusted.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

High Performance Algorithm for Calculating a Multiprocessor Safe Global Counter

Main Idea

A program is disclosed that removes the need for any spin locks
when calculating a multiprocessor safe global counter that may be
used for measuring a small unit of time for performance
measurements. The global counter is typically the sum of an
initial 64-bit value based on the system time, referred to as an
epoch, and a second measurement of time based on a processor
counter or a smaller (n-bit) counter that may wrap after some
defined period of time.

Intel processors provide a processor based timestamp counter
(TSC) and a read time stamp counter (RDTSC) instruction for
reading the value of the counter. These features provide adequate
functionality for systems built around a single system unit where
all the processors in a multiprocessor system are synchronously
clocked. Scalable systems that are built using multiple system
units and central electronics complexes (CECs), like the IBM
x440, result in asynchronous clocking for the processors in each

CEC and system unit. Consequently, over time the processor
timestamp counters diverge and may therefore return a smaller
global counter value for a subsequent system call.

Systems that utilize a smaller n-bit counter that wraps after
some defined period of time require that the initial 64-bit value
or epoch, being maintained is periodically updated. Periodically
updating the epoch and synchronizing this with the reset of the
counter ensures that the returned value is continuously
increasing. However, this typically results in the use of a spin
lock to guarantee that the epoch and the smaller n-bit counter
are updated synchronously in a multiprocessor environment.

The new algorithm defines two initial 64-bit values or epoch's.
When the n-bit counter is read, the high order bit is used to
select which epoch to add the n-bit counter value. In addition,
ANDing the high byte of the n-bit counter with a value that
contains 1's in the two highest bits allows the timing interval
to be broken into 4 distinct quadrants; 0, 1, 2, and 3.

The epochs are initialized to the same value, and a lock byte is
initialized to the highest state (ie waiting for state 3 to occur
in our example). When the highest state occurs, a constant value
that represents the highest possible value of the wrapping n-bit
counter plus 1 is added to the high word of the epoch used when
the high order bit is 0 and the lock byte changed to state...