Skip to contentSkip to conversation

Need better is_better_time_interpolator() algorithm

DISCUSSION [email protected] 3 participants 3 messages Aug 25, 2005 – Aug 26, 2005

lore
Share & tools
lore
#0 lore raw
Quoted 1 line

(frequency) * (1/drift) * (1/latency) * (1/(jitter_factor * cpus))

(Note that 1/cpus, being a constant for all evaluations of this expression, has no effect on the final ranking.)
The usual way it's done is with some fiddle factors:

quality_a^a * quality_b^b * quality_c^c

Or, equivalently:

a * log(quality_a) + b * log(quality_b) + c * log(quality_c)

Then you use the a, b and c factors to weight the relative importance of them. Your suggestion is equivalent to setting all the exponents to 1.

But you can also say that "a is twice as important as b" in a consistent manner.

Note that computing a few bits of log_2 is not hard to do in integer math if you're not too anxious about efficiency:

unsigned log2(unsigned x)

{
	unsigned result = 31;
	unsigned i;

	assert(x);
	while (!x & (1u<<31)) {
		x <<= 1;
		result--;
	}
	/* Think of x as a 1.31-bit fixed-point number, 1 <= x < 2 */
	for (i = 0; i < NUM_FRACTION_BITS; i++) {
		unsigned long long y = x;
		/* Square x and compare to 2. */
		y *= x;
		result <<= 1;
		if (y & (1ull<<63)) {
			result++;
			x = (unsigned)(y >> 32);
		} else {
			x = (unsigned)(y >> 31);
		}
	}
	return result;
}

Setting NUM_FRACTION_BITS to 16 or so would give enough room for reasonable-sized weights and not have the total overflow 32 bits.

#1 lore raw
Quoted 4 lines · On Thu, 2005-08-25 at 17:40 -0400, [email protected] wrote:
Quoted 1 line

(frequency) * (1/drift) * (1/latency) * (1/(jitter_factor * cpus))

(Note that 1/cpus, being a constant for all evaluations of this expression, has no effect on the final ranking.)

I was sloppy expressing how the jitter factors in, but I've got code
below that should make it more clear.

Quoted 6 lines

The usual way it's done is with some fiddle factors:

quality_a^a * quality_b^b * quality_c^c

Or, equivalently:

Quoted 7 lines

a * log(quality_a) + b * log(quality_b) + c * log(quality_c)

Then you use the a, b and c factors to weight the relative importance of them. Your suggestion is equivalent to setting all the exponents to 1.

But you can also say that "a is twice as important as b" in a consistent manner.

Right. It's the weighting factors themselves that I'm clueless
about. I'm hoping someone will chime in to help us prioritize and weight clock attributes appropriately. The code I've been poking at is below (by no means ready for inclusion). I think this brings the components I'm aware of together, and makes an attempt to do something meaningful with them.

On my system, I have 2 NUMA nodes, each with 4 processors. The cycle
counter runs at 1.5GHz with a 750ppm drift. The latency of this timer comes out to ~30ns. The cycle counter is subject to drift, so I divide by the square of the cpus and arrive at a "goodness" factor of around 950.

I also have 2 HPETs on the system, one on each node. These run at
250MHz with an assumed drift of 500ppm (although the current hpet code makes the drift much higher). I measure the access latency of these to be around 200ns. Because the HPETs have different access latency depending on the node, I use the NUMA info to get a average access latency of ~300ns. These timers are not subject to jitter, eliminating that factor. This results in a "goodness" factor of ~1450.

I don't really know if this makes sense, but it seems to do what I
think it should. If I where to add another node to the system, I would more strongly favor the HPETs time, if I removed a node I would revert to the cycle counter. Anyway, I think it might be a good starting point for further experimentation. Patch below.

Alex

Signature · 287 lines
Alex Williamson                             HP Linux & Open Source Lab


 arch/ia64/kernel/cyclone.c      |    3 -
 arch/ia64/kernel/time.c         |    3 -
 arch/ia64/sn/kernel/sn2/timer.c |    3 -
 arch/sparc64/kernel/time.c      |    3 -
 drivers/char/hpet.c             |   12 +++-
 include/linux/hpet.h            |    1 
 include/linux/timex.h           |    2 
 kernel/timer.c                  |  113 +++++++++++++++++++++++++++++++++++++++-
 8 files changed, 133 insertions(+), 7 deletions(-)

diff -r b40794c1ac45 arch/ia64/kernel/cyclone.c
--- a/arch/ia64/kernel/cyclone.c	Wed Aug 24 12:00:22 2005
+++ b/arch/ia64/kernel/cyclone.c	Thu Aug 25 16:29:22 2005
@@ -23,7 +23,8 @@
 	.shift =	16,
 	.frequency =	CYCLONE_TIMER_FREQ,
 	.drift =	-100,
-	.mask =		(1LL << 40) - 1
+	.mask =		(1LL << 40) - 1,
+	.node =		-1
 };
 
 int __init init_cyclone_clock(void)
diff -r b40794c1ac45 arch/ia64/kernel/time.c
--- a/arch/ia64/kernel/time.c	Wed Aug 24 12:00:22 2005
+++ b/arch/ia64/kernel/time.c	Thu Aug 25 16:29:22 2005
@@ -48,7 +48,8 @@
 static struct time_interpolator itc_interpolator = {
 	.shift = 16,
 	.mask = 0xffffffffffffffffLL,
-	.source = TIME_SOURCE_CPU
+	.source = TIME_SOURCE_CPU,
+	.node = -1
 };
 
 static irqreturn_t
diff -r b40794c1ac45 arch/ia64/sn/kernel/sn2/timer.c
--- a/arch/ia64/sn/kernel/sn2/timer.c	Wed Aug 24 12:00:22 2005
+++ b/arch/ia64/sn/kernel/sn2/timer.c	Thu Aug 25 16:29:22 2005
@@ -25,7 +25,8 @@
 	.drift = -1,
 	.shift = 10,
 	.mask = (1LL << 55) - 1,
-	.source = TIME_SOURCE_MMIO64
+	.source = TIME_SOURCE_MMIO64,
+	.node = -1
 };
 
 void __init sn_timer_init(void)
diff -r b40794c1ac45 arch/sparc64/kernel/time.c
--- a/arch/sparc64/kernel/time.c	Wed Aug 24 12:00:22 2005
+++ b/arch/sparc64/kernel/time.c	Thu Aug 25 16:29:22 2005
@@ -1048,7 +1048,8 @@
 static struct time_interpolator sparc64_cpu_interpolator = {
 	.source		=	TIME_SOURCE_CPU,
 	.shift		=	16,
-	.mask		=	0xffffffffffffffffLL
+	.mask		=	0xffffffffffffffffLL,
+	.node		=	-1
 };
 
 /* The quotient formula is taken from the IA64 port. */
diff -r b40794c1ac45 drivers/char/hpet.c
--- a/drivers/char/hpet.c	Wed Aug 24 12:00:22 2005
+++ b/drivers/char/hpet.c	Thu Aug 25 16:29:22 2005
@@ -82,6 +82,7 @@
 	unsigned long hp_delta;
 	unsigned int hp_ntimer;
 	unsigned int hp_which;
+	acpi_handle handle;
 	struct hpet_dev hp_dev[1];
 };
 
@@ -702,6 +703,7 @@
 {
 #ifdef	CONFIG_TIME_INTERPOLATION
 	struct time_interpolator *ti;
+	int pxm;
 
 	ti = kmalloc(sizeof(*ti), GFP_KERNEL);
 	if (!ti)
@@ -714,7 +716,12 @@
 	ti->frequency = hpet_time_div(hpets->hp_period);
 	ti->drift = ti->frequency * HPET_DRIFT / 1000000;
 	ti->mask = -1;
-
+	ti->node = -1;
+	pxm = acpi_get_pxm(hpetp->handle);
+#ifdef CONFIG_NUMA
+	if (pxm >= 0) 
+		ti->node = pxm_to_nid_map[pxm];
+#endif
 	hpetp->hp_interpolator = ti;
 	register_time_interpolator(ti);
 #endif
@@ -871,6 +878,7 @@
 	}
 
 	hpetp->hp_delta = hpet_calibrate(hpetp);
+	hpetp->handle = hdp->handle;
 	hpet_register_interpolator(hpetp);
 
 	return 0;
@@ -923,6 +931,8 @@
 	struct hpet_data data;
 
 	memset(&data, 0, sizeof(data));
+
+	data.handle = device->handle;
 
 	result =
 	    acpi_walk_resources(device->handle, METHOD_NAME__CRS,
diff -r b40794c1ac45 include/linux/hpet.h
--- a/include/linux/hpet.h	Wed Aug 24 12:00:22 2005
+++ b/include/linux/hpet.h	Thu Aug 25 16:29:22 2005
@@ -118,6 +118,7 @@
 	unsigned short hd_flags;
 	unsigned int hd_state;	/* timer allocated */
 	unsigned int hd_irq[HPET_MAX_TIMERS];
+	acpi_handle handle;
 };
 
 #define	HPET_DATA_PLATFORM	0x0001	/* platform call to hpet_alloc */
diff -r b40794c1ac45 include/linux/timex.h
--- a/include/linux/timex.h	Wed Aug 24 12:00:22 2005
+++ b/include/linux/timex.h	Thu Aug 25 16:29:22 2005
@@ -298,6 +298,8 @@
 	long drift;			/* drift in parts-per-million (or -1) */
 	unsigned long skips;		/* skips forward */
 	unsigned long ns_skipped;	/* nanoseconds skipped */
+	unsigned long latency;		/* access latency, set by register_time_interpolator() */
+	long node;			/* NUMA node where the device lives, or -1 */
 	struct time_interpolator *next;
 };
 
diff -r b40794c1ac45 kernel/timer.c
--- a/kernel/timer.c	Wed Aug 24 12:00:22 2005
+++ b/kernel/timer.c	Thu Aug 25 16:29:22 2005
@@ -39,6 +39,8 @@
 #include <asm/div64.h>
 #include <asm/timex.h>
 #include <asm/io.h>
+#include <asm/smp.h>
+#include <asm/topology.h>
 
 #ifdef CONFIG_TIME_INTERPOLATION
 static void time_interpolator_update(long delta_nsec);
@@ -1408,6 +1410,26 @@
 static struct time_interpolator *time_interpolator_list;
 static DEFINE_SPINLOCK(time_interpolator_lock);
 
+static u64 time_interpolator_read(struct time_interpolator *ti)
+{
+	unsigned long (*x)(void);
+
+	switch (ti->source)
+	{
+		case TIME_SOURCE_FUNCTION:
+			x = ti->addr;
+			return x();
+
+		case TIME_SOURCE_MMIO64	:
+			return readq((void __iomem *) ti->addr);
+
+		case TIME_SOURCE_MMIO32	:
+			return readl((void __iomem *) ti->addr);
+
+		default: return get_cycles();
+	}
+}
+
 static inline u64 time_interpolator_get_cycles(unsigned int src)
 {
 	unsigned long (*x)(void);
@@ -1517,13 +1539,99 @@
 	}
 }
 
+#ifdef CONFIG_NUMA
+static long
+time_interpolator_latency_scale(struct time_interpolator *ti)
+{
+	int cpu;
+	long scale = 0;
+
+	if (ti->node == -1)
+		return 10;
+
+	for_each_online_cpu(cpu)
+		scale += node_distance(cpu_to_node(cpu), ti->node);
+
+	/* 
+	 * Penalize timers not on the timekeeper node.
+	 * FIXME: This isn't a good check for the timekeeper
+	 */
+	if (ti->node != 0)
+		scale += node_distance(cpu_to_node(0), ti->node);
+
+	return scale / num_online_cpus();
+}
+#else
+#define time_interpolator_latency_scale(x) (10)
+#endif
+
+static unsigned long
+get_time_interpolator_priority(struct time_interpolator *ti)
+{
+	unsigned long pri;
+
+	/*
+	 * -1 drift seems to indicate that someone really wants us to use
+	 *  their timer.
+	 */
+	if (ti->drift == -1)
+		return ~0UL;
+
+	pri = ti->frequency/ti->drift;
+	pri /= ti->latency * time_interpolator_latency_scale(ti) / 10;
+	if (ti->jitter)
+		pri /= num_online_cpus() * num_online_cpus();
+
+	return pri;
+}
+
 static inline int
 is_better_time_interpolator(struct time_interpolator *new)
 {
 	if (!time_interpolator)
 		return 1;
-	return new->frequency > 2*time_interpolator->frequency ||
-	    (unsigned long)new->drift < (unsigned long)time_interpolator->drift;
+
+	if (new == time_interpolator)
+		return 0;
+
+	return get_time_interpolator_priority(new) >
+	       get_time_interpolator_priority(time_interpolator);
+}
+
+static unsigned long
+time_interpolator_latency(struct time_interpolator *ti)
+{
+	volatile u64 start, end;
+	unsigned long latency;
+	int i, scale;
+
+	start = time_interpolator_read(ti);
+	for (i = 0; i < 100 ; i++)
+		end = time_interpolator_read(ti);
+	latency = ((end - start) * (1000000000UL/i))/ti->frequency;
+
+#ifdef CONFIG_NUMA
+	/*
+	 * On big boxes, an MMIO timer source may have different access times
+	 * from different nodes.  It's impractical to measure the latency from
+	 * each node, so we trust node distance to scale the latency to
+	 * the local acess time.
+	 */
+	switch (ti->source) {
+		case TIME_SOURCE_MMIO64:
+		case TIME_SOURCE_MMIO32:
+			if (ti->node == -1)
+				scale = 10;
+			else
+				scale = node_distance(cpu_to_node(
+				                smp_processor_id()), ti->node);
+			break;
+		default:
+			scale = 10;
+	}
+	latency = (latency * 10)/scale; /* SMP locality = 10 */
+#endif
+	return latency > 0 ? latency : 1UL;
 }
 
 void
@@ -1536,6 +1644,7 @@
 		BUG();
 
 	ti->nsec_per_cyc = ((u64)NSEC_PER_SEC << ti->shift) / ti->frequency;
+	ti->latency = time_interpolator_latency(ti);
 	spin_lock(&time_interpolator_lock);
 	write_seqlock_irqsave(&xtime_lock, flags);
 	if (is_better_time_interpolator(ti)) {
#2 lore raw
Quoted 5 lines · Alex Williamson

I don't really know if this makes sense, but it seems to do what I
think it should. If I where to add another node to the system, I would more strongly favor the HPETs time, if I removed a node I would revert to the cycle counter. Anyway, I think it might be a good starting point for further experimentation. Patch below.

Adding a node to the time interpolator does not make much sense since time needs to be universally accessible in order to be comparable. Unless you want to use the time interpolator time source as an interrupt source then you may want to change the node that the timer interrupt runs on.

Some time source like the Altix RTC are not bound to any node but are available with a node local mmio instruction. There is no way to assign a node number to it.

Moreover you may derive the node number from the mmio address if the need really arises.

Also the latency is only a minor criterion in the determination of the most suitable clock. More important are the clock characteristics like consistency over multiple processors, or the distribution of the timer.

One does not want a clock that is not consistent over multiple processors regardless of the latency. A distributed timer wins over a low latency timer on a node in a NUMA system.

I think it would be best add some flags that describe

1. The consistency scope of the time source
i.e. TIME_SOURCE_SYNC_PROCESSOR
Access to the time source yields a processor local result
TIME_SOURCE_SYNC_NODE
Access to the time source yields a result that is the same for all processors on the same node
TIME_SOURCE_SYNC_GLOBAL
Access to the time source yields a globally consistent result

2. The locality of the time source
TIME_SOURCE_IN_PROCESSOR -> Processor is the time source
TIME_SOURCE_DISTRIBUTED -> Distributed time source
TIME_SOURCE_NODE -> memory mapped time source on a
node.

Then the ITC would be configured as
TIME_SOURCE_SYNC_PROCESSOR | TIME_SOURCE_IN_PROCESSOR

If the ITC is syncd up per node
TIME_SOURCE_SYNC_NODE | TIME_SOURCE_IN_PROCESSOR

If this is an SMP system then it may even be
TIME_SOURCE_SYNC_GLOBAL | TIME_SOURCE_IN_PROCESSOR

For HPET this would be
TIME_SOURCE_SYNC_GLOBAL | TIME_SOURCE_NODE

For Altix RTC
TIME_SOURCE_SYNC_GLOBAL | TIME_SOURCE_DISTRIBUTED

Hope this makes sense.