Causality filters A tool for the online visualization and steering of parallel and distribu
Causality Filters:A Tool for the Online Visualization and Steering of Parallel and
Distributed Programs
Eileen Kraemer
Department of Computer Science
School of Engineering and Applied Science
Washington University in St.Louis
St.Louis,MO63130-4899
eileen@https://www.wendangku.net/doc/535700344.html,
Abstract
Interactive program steering is a promising technique for improving the performance of parallel and distributed ap-plications.Steering decisions are typically based on visual presentations of some subset of the computation’s current state,a historical view of the computation’s behavior,or views of metrics based on the program’s performance.As in any endeavor,good decisions require accurate information. However,the distributed nature of the collection process may result in distortionsin the portrayal of the program’s ex-ecution.These distortions stem from the merging of streams of information from distributed collection points into a sin-gle stream without enforcing the ordering relationships that held among the program components that produced the in-formation.An ordering?lter placed at the point at which the streams are merged can ensure a valid ordering,leading to more accurate visualizations and better informed steering decisions.In this paper we describe the implementation of such?lters and present a methodology for their speci?cation and automated generation.
1.Introduction
Interactive program steering is a promising technique for improving the performance of parallel and distributed ap-plications,for permitting researchers to guide the progress of their long-running applications to achieve better qual-ity of solution or faster time to solution,and for support-ing the ability of scientists to interpret,control,and ad-just the parameters of their applications in close-to-real-time.Recently,interactive steering techniques have been applied to scienti?c and engineering Fortran codes,im-age?ltering[22],molecular dynamics simulation[4],and global atmospheric modeling code[28].To achieve these ends,researchers have developed toolkits and libraries such as Falcon[7],Progress[28],CUMULVS[6],and the V ASE environment[11].Interactive systems such as these permit users to monitor and control,or steer,particular parameters of their applications online.Steering decisions are typically based on visual presentations of some subset of the compu-tation’s current state,a historical view of the computation’s behavior,or views of metrics based on the program’s per-formance.
As in any endeavor,good decisions require accurate in-formation,truly representative of the state of the underlying system.However,the distributed nature of the collection process presents an obstacle to the presentation of infor-mation that represents a causally consistent[17,5]view of the program’s execution and to the construction of a consis-tent snapshot[3]of the global state of the executing system. Although algorithms exist for the collection of consistent global snapshots[16,23,1,20],these algorithms typically entail additional overhead on the part of the monitored pro-cess.
Minimizing the perturbation of the underlying applica-tion suggests that causal ordering and consistent snapshots be calculated post-collection,on a processor other than those involved in the application under study.The collected infor-mation,often referred to as program event records or events, consists of records describing a state transition or the state of the process at particular points of interest.The goal of this post-collection processing is to merge the streams of events from each of the nodes of the computation into a single stream.Although information collected at any one node of the parallel or distributed system will be correctly ordered, the indiscriminate merging of these streams,without enforc-ing the ordering relationships that held among the program components that produced the information,can result in out-of-order information in the?nal stream.This out-of-order stream of information may lead to updates to graphical dis-
plays that mislead the viewer,causing the viewer to perform steering actions that are less than optimal,if not harmful.
Visualization systems for parallel and distributed sys-tems have dealt with similar concerns regarding consistency in the context of post-mortem visualization[14,13].De-velopers of interactive steering systems recognize this dan-ger,and have devised strategies to present time-coherent views.For example,some steering systems ensure con-sistent views through checkpointing at embedded barrier synchronizations.The Falcon system for interactive pro-gram steering[7]relies on the existence of an ordering?lter placed at the point at which the streams are merged to ensure a valid ordering.These consistent orderings lead to more accurate visualizations,and thus better informed steering decisions.
In this paper,we address the problem of on-the-?y re-ordering of events for online visualization and its importance in interactive steering and describe a speci?cation to permit the automated generation of a“reordering”or“causality”?lter to produce visualizations that more accurately re?ect the state of the monitored computation,thus permitting users to perform steering based on more realistic representations of program state and behavior.Section2describes the characteristics of consistent orderings and presentations and summarizes our prior work with reordering in the context of program visualization.In Section3,we discuss online visualization and describe its role in interactive program steering.In Section4we provide an analysis of the chal-lenges presented by on-the-?y?ltering of event streams,as opposed to a post-mortem determination of consistent order. Sections5and6provide detail on the structure and function of the ordering?lters developed for use with Falcon,and the speci?cation for automated generation of such?lters.Fi-nally,Section7summarizes our results and describes future work.
2.Timestamps,Causality,Consistency,and
Global Snapshots
Information regarding the causal relationships between events is an essential factor in the analysis of distributed sys-tems.These causal relationships are important in such types of analysis as trace?le reduction for purposes of replay[24], online program steering[7],[11],[2],and the visualization of parallel and distributed systems[18],[31],[10],[14],[27], [29],[8].Unfortunately,the causal relationships that form the basis of these types of analysis are not always apparent in the traces or event streams generated by monitoring soft-ware and hardware.Although the records contained in these traces are often timestamped,timestamps alone are not suf-?cient to compute causal relationships.In fact,timestamps are often not suf?cient to determine the actual event order. This is due to the common situation in which clocks may not be synchronized,may drift at different rates,or may be of inadequate resolution to separate events in time.
One criterion for event ordering is consistency.This requires only that the ordering of the events in the event stream produced by the monitoring system does not violate any of the causal relationships.There are several approaches to producing these consistent orderings.One approach in-volves periodic clock resynchronization[30,19,21].An-other approach makes use of a system of logical clocks or“Lamport”timestamps[17]to present an ordering that is consistent with causality.In this method,if event a causally precedes(“happens before”)event b,then event a must have an“earlier”timestamp than event b.
A stronger criterion for ordering requires that the infor-mation available about the causal relationships be suf?cient to characterize causality.In an ordering that characterizes causality,event a will have an“earlier”timestamp than event b if and only if there is a causal relationship,either direct or transitive,between events a and b.Consistent orderings dif-fer in that they may impose false orderings on events that are causally unrelated.For example,event a and event b may be logically concurrent,yet in a consistent ordering,event a may have an“earlier”timestamp.Loosely speaking,char-acteristic causality provides suf?cient information to deter-mine all event sequences that“could have happened”given the causal relationships existing in the program execution under study.Timestamps,even if produced by synchronized clocks with adequate resolution and no clock drift,do not characterize causality.“Lamport”timestamps are similarly lacking in the information needed to characterize causality.
A stronger notion,such as vector time[26],or an equivalent representation,is required for this purpose.
In earlier work with program visualization for paral-lel and distributed systems,we developed a methodology for detecting causal relationships based on synchroniza-tion events and producing a represenation that character-izes causality without dependence on vector timestamps. The tool that embodies this methodology,the Animation Choreographer[27,15],generates a set of alternative feasi-ble event orderings,permitting users to explore alternative orderings through display and manipulation of graphical objects,and employs these orderings in animated graphical displays of the program’s execution.To use this tool,user’s specify the format of the records produced by the monitoring system and the types of synchronization events(those events or occurrences in the program that re?ect the causal rela-tionships in the program’s execution).A Choreographer-generator tool then produces a version of the Choreogra-pher that will correctly process the events produced by the speci?ed system,and produce a structure that embodies the causal relationships that exist in the program execution un-der study.However,a drawback to the Choreographer is that it relies on the post-mortem analysis and visualization
of the program of interest.For systems that produce volu-minous trace?les and for interactive program steering,this is not a practical approach.Thus,in this paper we address the problem of“on the?y”reordering of events for online visualization.
3.Online Visualization and Interactive Steer-
ing
The interactive steering of parallel programs has been de?ned as“the on-line con?guration of a program by al-gorithms or by human users,with the purpose of improv-ing the program’s performance or simply affecting its ex-ecution behavior.”[7]This steering can consist of changes to both system-level structures such as locks,buffers,and queues,and to application level abstractions such as the cur-rent“temperature”in a simulated annealing program,or the choice of bounding criterion in a branch-and-bound algo-rithm.In either case,information is captured from the exe-cuting program,and presented to the user and/or algorithm to inspect and analyze.The purpose of on-line steering is to allow the users to experiment with program parameters, improve program performance,and understand and direct the program’s execution.
Online visualization can be a useful tool in presenting this run-time information to the user in a format that can be readily understood.For example,performance information such as load balance and cpu utilization may be depicted using bar charts and kiviat graphs.Figure3shows a thread lifetime view(courtesy of Weiming Gu)produced for use with the Falcon system for the interactive steering of parallel threads[7]programs.This view provides information about the number of threads,their histories,and current states. Application-speci?c displays can be used to provide the information necessary for application-level steering.
Quite often,these types of displays rely on an event stream in which the events are“in-order”.That is,they do not violate the“happened-before”relationship described in [17,5].An out-of-order event stream can result in displays that are misleading or that fail.The event stream produced by a real-time monitoring system may contain out-of-order events.For example,an event record that describes a partic-ular thread’s attempt to access a mutual exclusion variable may precede the event record that describes the creation of the thread itself.This would most certainly produce a mis-leading display and might cause a less-than-robust display routine to fail.Adding a layer of error-checking code to the display can prevent most display failures.However,this adds execution overhead,makes displays more dif?cult to design,and still leaves the viewer with displays that don’t always make sense.
Of course,an event ordering such as the one described in the previous paragraph could never occur in a real ex-ecution.Why does it occur in the event stream produced by the real-time monitoring system?The primary cause of these out-of-order events is the buffering method employed in the monitoring system.Ef?cient performance(low mon-itoring perturbation)requires that events for each thread be buffered until a local monitor is ready to pick them up.Also, local monitors ship off events to the central monitor at dif-ferent speeds because on-line processing requirements and workload vary from one local monitor to another.
Thus,the event stream that emerges from the monitoring system is in-order within each thread,but is not in order overall.How can we deal with these out-of-order events? Many post-mortem systems[9],[25]rely on a simple sort by timestamp to impose a total order on the events.As mentioned in the introduction,because of problems with clock synchronization,drift,and resolution,this approach does not guarantee an in-order event stream.In addition,the real-time nature of a system for interactive program steering precludes such a solution.
So,we see that timestamps alone are not suf?cient to order the events,nor would such a sorting process be feasible in a real-time system.Instead,we employ an ordering?lter between the central monitor and the display system to ensure that the event stream that reaches the display system adheres to a causal ordering.
4.On-the-?y versus Post-mortem analysis
Applications that require online event reordering oper-ate under a different set of constraints than post-mortem systems.Some of these differences complicate the task of the online event reordering tool,while others simplify the task.To meet the real-time needs of the application that it serves,an online reordering tool often must work with not-yet-complete trace information and must avoid creating a bottleneck between the monitoring system that produces the events and the application that waits to receive them. These are complicating factors.However,the online nature of these applications also precludes the investigation of al-ternative feasible orderings as there is no time available in which to explore these possibilities.Thus,the calculation of characteristic causality is not necessary.The online re-ordering tool needs only to compute a consistent ordering, thus simplifying the calculations that must be performed.In general,there will be a great number of event orderings that are consistent with the causal relationships in the program. In this approach,the user may generate a?lter that con-forms to one of several prede?ned policies such as minimal intervention,maximal concurrency,or adjusted timestamp, described in Section6.
Further,in dealing with online event reordering,we seek to answer a different question than with post-mortem re-ordering.With post-mortem analysis and the calculation of
characteristic causality,for each event record that we exam-ine,we seek to determine all of the events that were or could have been causally succeeded or preceded by the event in question.With“on the?y”reordering for visualization, the goal is to send the events to the visualization system in an order that“could have happened”,and that meets some additional criteria,depending on the policy selected by the user.Thus,as we examine each record,the question that we seek to answer is“Is it valid to send this record to the visualization system yet?”
Because the“question to be answered”differs from a post-mortem system such as the Choreographer to an online system such as these“causality”?lters,the method by which we specify the causal relationships in the program differs as well.In the Choreographer,causal relationships are spec-i?ed by identifying a synchronization event as belonging to one of the classes of synchronization events known to the Choreographer system,and by specifying the mapping from the synchronization event’s parameters to the parame-ters required for that class of synchronization event.A more detailed discussion of the method used to specify causal re-lationships in the Choreographer can be found in[14].The structure and function of the online reordering?lter and the method by which we specify the causal relationships for the generation of online causality?lters is described below. 5.Filter Structure and Function
The Falcon system employs a reordering or“causality”?lter between the monitoring system and the display sys-tem.This reordering?lter follows a set of ordering rules, and employs a“minimum-intervention”policy.That is,it examines each incoming event record,checks the applicable ordering rules(causal relations),and,if no rules would be violated,passes the event record on to the display system. If a rule violation is indicated,the event record is held back until the causal relations are satis?ed.
Figure1shows some of the data structures involved.At the left are the event records arriving from the monitor in a single stream,correctly ordered within each thread
id encountered in the event stream, shown at the center of the?gure.Event records that are not ready to be processed(that do not yet satisfy the rules)are stored in these queues.The ordering?lter then continues to examine new event records,checking the head of each active queue in every round to see if it is now possible to place the event record in the stream going to the display system,shown at the right hand side of the?gure.
Let us look at a few of the rules that are de?ned for the Falcon system for the interactive steering of cthreads programs.Of course,other systems will have their own sets of rules.A speci?cation in the format shown below may be
thread 0
thread 1
thread 2
thread n
...
out-of-order events
display system
are held back in
per-thread queues
before being sent
to the display
structures.
?lter for those
n=sequence number
pt=parent thread
ct=child thread
jt=join_to thread number
bn=beginning sequence number
en=ending sequence number
p=processor number
x=don’t care value
Initial conditions:
for each m:n=0
for each c:bn=0and en=0
Ordering rules for each event:
THREAD_INIT t<-();
This is the initial event.All prior events are ignored.An internal buffer is created for this thread number,and it is turned"on".
THREAD_FORK t ct<-
(THREAD_INIT t||THREAD_FORK pt t);
The parent thread must be"on"for this event to be processed. An internal buffer is created for the child thread and the child thread is turned"on".This is the required initial event for the child thread.
THREAD_EXIT t<-
(THREAD_INIT t||THREAD_FORK pt t);
The internal buffer is de-allocated and the thread is turned "off".Any succeeding events recorded by this thread are ignored.
Note that the queues shown in Figure1are not acti-vated until a THREAD
FORK event(all other threads)is processed for that thread
EXIT is encountered.
As another example,let us look at the rules for mutex events shown below.Notice that for a MUTEX
INIT or MUTEX
BEGIN
END END
END
UNLOCK event for variable m sequence number n-1has already been passed on to the display system.”Each of the expressions involved in this rule has its own set of rules,which must be met.
MUTEX_INIT t m<-
((THREAD_INIT t||THREAD_FORK pt t)&&
!(MUTEX_INIT m||MUTEX_ALLOC m));
MUTEX_ALLOC t m<-
((THREAD_INIT t||THREAD_FORK pt t)&&
!(MUTEX_INIT m||MUTEX_ALLOC m));
MUTEX_BEGIN_LOCK t m n<-
((THREAD_INIT t||THREAD_FORK pt t)&&
(MUTEX_INIT m||MUTEX_ALLOC m));
MUTEX_END_LOCK t m n<-
((THREAD_INIT t||THREAD_FORK pt t)&& (MUTEX_INIT m||MUTEX_ALLOC m)&&
(MUTEX_UNLOCK m n-1))
MUTEX_UNLOCK t m n<-
((THREAD_INIT t||THREAD_FORK pt t)&&
(MUTEX_INIT m||MUTEX_ALLOC m)&&
(MUTEX_END_LOCK m n));
Each mutex id is assigned a data struc-ture that keeps track of the sequence numbers associated with it that have been processed thus far.An example of these data structures is shown in Figure2.
These structures are dynamically allocated as the events are observed in the stream.The MUTEX
ALLOC event causes the data structure to be al-located for this mutex
id may be processed until after the MU-TEX ALLOC.MUTEX LOCK and MUTEX
name:?eld
is the?eld type name.The other?eld types are similar to those used in the c language printf statement-f is?oat,d is integer,s is string,c is character,etc.
THREAD_INIT:id ts:f rid:f lid:d function:d
parent_rid:f parent_lid:d
THREAD_INVOKE:id ts:f rid:f lid:d function:d function_name:s
THREAD_RETURN:id ts:f rid:f lid:d function:d function_name:s
THREAD_TERMINATE:id ts:f rid:f lid:d parent_rid:f parent_lid:d
THREAD_DETACH:id ts:f rid:f lid:d whom:d
THREAD_JOIN:id ts:f rid:f lid:d whom:d
THREAD_INACTIVE:id ts:f rid:f lid:d
THREAD_ACTIVE:id ts:f rid:f lid:d
Finally,the user must specify the policy or policies to be followed by the?lter.In a“minimal intervention”policy, each event is sent to the display system as soon as it is valid to do so.This policy invokes the least overhead and is use-ful when latency is an issue.In the“maximal concurrency”policy,events that could be concurrent and that are found at the head of their queues in the same round are batched together and sent to the display system at the same time. This policy is useful for visualizing concurrency in display systems that are capable of representing https://www.wendangku.net/doc/535700344.html,stly,some display views may rely on the timestamps recorded with an event record to correctly place the associated graphical ob-jects on the screen.Although the other policies will deliver the event records to the display system in-order,the actual timestamp values may be out-of-order,and this may result in a confusing display.The“adjusted timestamp”policy adjusts each timestamp by just enough so that it is consis-tent with the order in which the event records are delivered to the display system.It is also possible to append a?eld containing the difference between the actual and adjusted timestamp,as indication of the perturbation resulting from monitoring and display.
7.Conclusions
We have described the need for reordering tools in the online visualization and interactive steering of parallel and distributed systems.Although it is possible to hand-craft ?ltering code for each system and set of attributes to be monitored,we believe it to be more elegant,more ef?cient, and less prone to error to have a general method for the speci?cation and generation of such a reordering tool in the form of a causality?lter.We describe the speci?cation and function of such a?lter,and outline the method for automated generation.References
[1] A.Acharya and B.Badrinath.Recording distributed snap-
shots basedon causal order of https://www.wendangku.net/doc/535700344.html,rmation Processing Letters,44(6):317–21,Dec.1992.
[2]T.Bemmerl and P.Braun.Visualization of message pass-
ing programs with the TOPSYS parallel programming en-vironment.Journal of Parallel and Distributed Computing, 18(2):118–128,June1993.
[3]K.Chandy and https://www.wendangku.net/doc/535700344.html,mport.Distributed snapshots:determin-
ing global states of distributed systems.ACM Transactions on Computer Systems,3(1):63–75,1985.
[4]G.Eisenhauer,W.Gu,K.Schwan,and N.Mallavarupu.
Falcon-toward interactive parallel programs:The On-line steering of a molecular dynamics application.In Proceed-ings of High Performance Distributed Computing(HPDC-
3),Aug.1994.
[5] C.Fidge.Logical time in distributed computing systems.
Computer,24(8):28–33,Aug.1991.
[6]G.A.Geist,J.A.Kohl,and P.M.Papadopoulos.CU-
MULVS:Providing fault-tolerance,visualization,and steer-ing of parallel applications.SIAM,Aug.1996.
[7]W.Gu,G.Eisenhauer,E.Kraemer,K.Schwan,J.Stasko,
J.Vetter,and N.Mallavarupu.Falcon:on-line monitoring and steering of large-scale parallel programs.In Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation,pages422–429,McClean,V A,Feb.1995. [8]M.C.Hao,A.H.Karp,A.Waheed,and M.Jazayeri.VIZIR:
An integrated environment for distributed program visualiza-tion.In Proceedings of the International Workshop on Mod-eling,Analysis and Simulation of Computer and Telecom-munication Systems(MASCOTS‘95),Tools Fair,Durham, NC,Jan.1995.
[9]M.T.Heath and J.A.Etheridge.Visualizing the performance
of parallel programs.IEEE Software,8(5):29–39,Sept.
1991.
[10] D.P.Helmbold,C.E.McDowell,and J.-Z.Wang.Analyzing
traces with anonymous synchronization.Technical Report UCSC-CRL-89-42,Univ.of California at Santa Cruz,Santa Cruz,CA,Dec.1989.
[11] D.Jablonowski,J.Bruner,B.Bliss,and R.Haber.V ASE:
The Visualization and Application Steering Environment.
In Proceedings of Sumpercomputing’93,pages560–569, Portland,OR,Nov.1993.
[12] E.Kraemer.Causality?lters:A tool for the online visu-
alization and steering of parallel and distributed programs.
Technical Report WUCS-97-xx,Washington University,De-partment of Computer Science,St.Louis,MO,Jan.1997.
[13] E.Kraemer and J.T.Stasko.The visualization of parallel
systems:An overview.Journal of Parallel and Distributed Computing,18(2):105–117,June1993.
[14] E.Kraemer and J.T.Stasko.Toward?exible control of the
temporal mapping from concurrent program eventsto anima-tions.ProceedingsEighth International Parallel Processing Symposium,pages902–908,1994.
[15] E.T.Kraemer.A Framework,Tools,and Methodology for
the Visualization of Parallel and Distributed Systems.PhD thesis,Georgia Institute of Technology,Atlanta,GA,Aug.
1995.
[16] A.Kshemkalyani,M.Raynal,and M.Singhal.An introduc-
tion to snapshot algorithms in distributed computing.Dis-tributed Systems Engineering,2(4):224–33,Dec.1995. [17]https://www.wendangku.net/doc/535700344.html,mport.Time,clocks,and the ordering of events in a
distributed https://www.wendangku.net/doc/535700344.html,munications of the ACM,21(7):558–565,July1978.
[18]T.J.LeBlanc and J.M.Mellor-Crummey.Debugging par-
allel programs with Instant Replay.IEEE Transactions on Computers,C-36(4):471–482,Apr.1987.
[19] E.Luit and J.Martin.A convergence function for clock
synchronization protocols.In Proceedings of the Second Workshop on Parallel and Distriubed Real-Time Systems, pages9–16,Cancun,Mexico,1994.
[20] F.Mattern.Ef?cient algorithms for distributed snapshotsand
global virtual time approximations.Journal of Parallel and Distributed Computing,18:423–434,1993.
[21] https://www.wendangku.net/doc/535700344.html,ls.Internet time synchronization:The network time
https://www.wendangku.net/doc/535700344.html,work Working Group Request for Comments: 1129,Oct.1989.
[22]K.Moore and P.Robertson.Interactive steering of image
?ltering using visualization of space-variant?lter kernels.
In Proceedings of the SPIE-The Internation Society for Optical Engineering,pages323–333,San Jose,CA,1995.
[23]https://www.wendangku.net/doc/535700344.html,zer and J.Xu.Necessary and suf?cient conditions for
consistent global snapshots.IEEE Transactions on Parallel and Distributed Systems,6(2):165–9,Feb.1995.
[24]https://www.wendangku.net/doc/535700344.html,zer and https://www.wendangku.net/doc/535700344.html,ler.Optimal tracing and re-
play for debugging message-passing parallel programs.In Proceedings of Supercomputing’92,pages502–521,Min-neapolis,MN,Nov.1992.
[25]S.R.Sarukkai and D.Gannon.Performance visualization
of parallel programs using SIEVE.1.In Proceedings of the 1992International Conference on Supercomputing,pages 157–166,Washington,D.C.,July1992.
[26]R.Schwarz and F.Mattern.Detecting causal relationships
in distributed computations:in search of the holy grail.Dis-tributed Computing,7:149–174,1994.
[27]J.T.Stasko and E.Kraemer.A methodology for build-
ing application-speci?c visualizations of parallel programs.
Journal of Parallel and Distributed Computing,18(2):258–264,June1993.
[28]J.Vetter and K.Schwan.Progress:a toolkit for interactive
program steering.In Proceedings of the24th International Conferenceon Parallel Processing,pages139–142,Urbana, IL,1995.
[29] A.Waheed,A.Bakic,D.Pierce,M.W.Mutka,and D.T.
Rover.Vista:A framework for instrumentation system de-sign for multidisciplinary applications.In Proceedingsof In-ternational Workshop on Modeling,Analysis,and Simulation of Computer and Telecommunications Systems(MASCOTS ’96),Tools Fair,San Jose,CA,Feb.1996.
[30]L.D.Wittie.Debugging distributed C programs by real
time replay.SIGPLAN Notices,24(1):57–67,Jan.1989.
(Proceedings of the Workshop on Parallel and Distributed Debugging,Madison,WI,May1988).
[31] D.Zernik and L.Rudolph.Animating work and time for
debugging parallel programs-foundations and experience.
SIGPLAN Notices,26(12):46–56,Dec.1991.In Proceed-ings of the SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging,Santa Cruz,CA,May1991.
Mutexes
mutex_id
max_seq_num 774
mutex_id
max_seq_num
9912
Conditions
Figure 2.Mutex and condition id
data structures are used to keep track of active id numbers and current sequence numbers.
Figure 3.Falcon threads lifetime view provides information about the number of threads,their histo-ries,and current states.Out of order events can mislead the viewer or cause display to fail.