Entropic Complexity Measured in Context Switching - Applications of Digital Signal Processing - page 355

nature. When the concurrency becomes an integral aspect of the system and in particular
when threads must interact with one another does the complexity start to increase quickly.
That becomes the essence of the disorder or entropy that we try to capture.
System designers will use tools such as state diagrams, activity diagrams, and Petri nets
(Peterson 1981) to architect concurrency behaviors. A typical Petri net is shown below which
illustrates the parallel activities and synchronous behaviors. These have various levels of
contol, in that they can abstract some of the temporal scale differences by encapsulation of
behaviours (Pukite & Ludwig, 2007). However, the actual synchronization will always
reveal itself in the realized system.
Fig. 3. A typical concurrent automata represented by a Petri net. Multiple threads are
represented by filled tokens (places), and context switches occur when threads meet at
synchronization points (bars). For large systems, the complexity of interactions canl grow
well beyond this level.
2.1 Application
To effectively put the temporal complexity measure into practice, the program or simulation
implementation will need a way to time stamp and data log context switches during
execution. An implementation of a discrete event task scheduler such as the public source
Degas (Ludwig & Pukite, 2006) provides such an instrumentation facility.
The simplest input stream is a list of events signified by time-stamps, which will serve to
capture the c(t) signal. The values for c(t) can be as simple as delta functions with a value of
unity indicating a context switch.
2.2 Computation
This algorithm needs a FFT routine. The following pseudo-code guides the calculation
calling a generic FFT routine named Fourier8 . This assumes that each line contains the
number of events that occur in the time step and is read through standard input. (This is set
to read in exactly 2N lines, where N is an order 15 FFT) If sparse input is provided with time
stamps then the data must be transferred into a discrete set of lines with either 0 or N events
on each line, due to the nature of the discrete time FFT.