Browse Prior Art Database

System and Method to measure jitter in program execution

IP.com Disclosure Number: IPCOM000200898D
Publication Date: 2010-Oct-29
Document File: 9 page(s) / 1M

Publishing Venue

The IP.com Prior Art Database

Abstract

This document presents a non-intrusive hardware mechanism that can dynamically monitor the jitter experienced by applications. Jitter is defined as the non determinism in the execution of parallel programs. Jitter is in- troduced in programs due to various sources such as interrupts, daemons, kernels, other processes, and power management features. This might delay the critical parts of soft real time applications and limit the scalability of parallel applications. The proposed mechanism provides on-line jitter aware- ness to such parallel applications, and enables them to dynamically monitor jitter and to modify their behavior accordingly. The non-intrusive jitter mea- surement mechanism is created by instrumenting the standard C library and by adding jitter monitoring units to each core, which communicate with each other using a custom distributed protocol.

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

Page 01 of 9

System and Method to measure jitter in program execution

Characterization and Detection of Synchronization Jitter
Figure 1 shows the di~erent types of synchronization operations in the pthreads library, which contains all the synchronization routines in the standard C library. Lock-Unlock, start and end a critical section, using a memory address as a lock ad- dress. Signal-Wait and Broadcast-Wait are two paradigms in which one thread waits for another thread to signal it to resume. The di~erence between signal and broadcast is that signal is one-to-one communication, and broadcast is one-to-many commu- nication. We define a set of events that are fired when we enter a synchronization library call, and exit it. They are shown in figure 2.

Let us now look at typical communication scenarios for measuring signal-wait

jitte

Figure 1: Different thread communication patterns

r. Other cases can be handled similarly.

(This page contains 00 pictures or other non-text object)

1


Page 02 of 9

(This page contains 00 pictures or other non-text object)

Figure 2: List of events

List of Possible Cases

Case 1: In Figure 3, we look at a typical scenario for a signal-wait communication pattern. First, a process on core 1 issues a wait entry (w e) call. The jitter unit on core 1 makes an entry of this by logging it in the wait queue. Subsequently, a process on core 2 tries to signal the waiting process. The pthread library catches this event, and broadcasts the s e event to the other jitter units. The s e event contains the lock address, and the id of the pthread that is going to be woken up. We don't expect the overhead to be more than a couple of cycles. Once core 1 receives the s e event, it starts searching for entries in its wait queue that match the address and the thread
id. If a match is found, then a task is going to be woken up in the near future. The

y.

Now, the pthread code on core 2 typically does some pre-processing, and then sends an interrupt to the kernel (int 0x80 instruction on x86). The kernel can either send an inter-processor-interrupt to core 1 to resume the waiting process, or it can mark the waiting process as ready, and just return. Figure 3 shows the former case. The hardware or the kernel can monitor the inter-processor-interrupt (ipi). If an
ipi is sent after a signal entry, then we can log this event. The time between s e and ipi should be within limits. If it is not, then this means that there is some jitter in the kernel. Core 2 makes a note of this jitter and saves the value in scratchpad memory along with the lock address. Please note that it does not add this jitter value to the

jitter queue, as the signal might not correspond to any wakeups in future.

After core 1 receives the ipi, it immediately transitions to kernel mode. Let us assume that the waiting process has the highest priority. Then the kernel will exit (k x) and wakeup the process firing the w x event. After core 1 has woken up, it sends the jitter commit me...