Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improved Occurrence Insertion Algorithm for Visualizing Data on Hierarchical Time Lines

IP.com Disclosure Number: IPCOM000115521D
Original Publication Date: 1995-May-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 166K

Publishing Venue

IBM

Related People

Lehr, TF: AUTHOR

Abstract

It is often desirable to trace software in order to more fully understand its behavior. Traces consisting of time-stamped events executed by the software are useful in debugging the software as well as ascertaining performance problems. Traces often yield hundreds or even thousands of pages of text, rendering them practically useless without the assistance of tools to translate or filter the data into more manageable forms. Visualizing trace data is one way of simplifying the interpretation of them. Although there are many ways to visualize trace data, this disclosure addresses visualizations which draw events along a time-line.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Improved Occurrence Insertion Algorithm for Visualizing Data on Hierarchical
Time Lines

      It is often desirable to trace software in order to more fully
understand its behavior.  Traces consisting of time-stamped events
executed by the software are useful in debugging the software as well
as ascertaining performance problems.  Traces often yield hundreds or
even thousands of pages of text, rendering them practically useless
without the assistance of tools to translate or filter the data into
more manageable forms.  Visualizing trace data is one way of
simplifying the interpretation of them.  Although there are many ways
to visualize trace data, this disclosure addresses visualizations
which draw events along a time-line.

      PieScope is a trace visualization tool which collates and draws
events along several parallel time lines.  It is used internally
within IBM* to diagnose application and system performance problems.
The PieScope visualization format stores trace events in tree-like
data structures.  The Figure shows a typical PieScope visualization
of AIX* trace output.

      Correct, versatile and fast insertion of the events into the
trees is important if the tool is to be "user-friendly."  For
example, other state-of-the art trace visualization tools represent
traces using a single time-line per processing element (a processor,
for example).  The one-time-line per processor assignment arises from
assumptions about what kind of problems the tool will address.  Other
state-of-the art tools target simple application programs which
rarely have more than one process per processor.  The problem with
such an assignment is that if such a tool is used visualize the
performance of operating systems or complex multi-process
applications, the purported ability of visualization to simply trace
analysis vanishes as the amount of information being packed into a
single medium explodes.

      PieScope handles complex traces by permitting many time-lines
per processor so that every process, interrupt stream and device can
be studied as isolated threads of activity or as part of a community
of threads.  One may liken the difference between other state-of-the
art trace visualizers and PieScope to a situation where a group of
persons are simultaneously talking to another group of persons on a
telephone.  Other trace visualizers provide a single telephone.
PieScope provides as many as are needed.

      An occurrence insertion algorithm is a procedure for deciding
where a trace occurrence goes in the data structure representing the
trace visualization.  A "trace occurrence" is two events, paired as
the begin and end of the occurrence.  An event is a single,
time-stamped action found in the trace record.  PieScope's current
insertion algorithm is more powerful than any other algorithm used by
competing systems because it has had to address system traces with
complex and inelegant event mixes.

      Although th...