Image Processing Reference
In-Depth Information
17
Entropic Complexity Measured
in Context Switching
Paul Pukite and Steven Bankes
BAE Systems
USA
1. Introduction
Abstract : A complexity metric for concurrent software controlled systems is defined and
derived. It is equivalent or comparable to the Shannon information metric, which
essentially measures entropy of a system, but uses a novel and efficient technique based
on a FFT to calculate its value. This can be extended to other temporal realizations of
behaviour.
For concurrent software, the amount of context switching that occurs indicates the level of
complexity of the program. If the program consists of a fixed period cyclic scheduler,
context switches will occur very predictably at those same fixed intervals. However, if the
program consists of a mix of periods, some long, some short, and some perhaps sporadically
aperiodic, the complexity of such a program will be much greater. Further, the greater the
spread between short periods and long periods will indicate that the program will be much
harder to verify, as the shorter cycles will accumulate more testing coverage than the longer
or sporadic interval context switching.
In some sense, this is what makes clock-driven synchronous logic much easier to test. The
state space of possible events is reduced in direct relation to the reduction of available slots
for computation. As the context switching and potential interactions between threads occurs
only at these slots, a simplification of the temporal behaviour here will result in a better
chance to verify the correctness of its execution.
By the same token, any concurrent program will show greater non-determinism than an
equivalent sequential program. The benefits of making a concurrent program more
synchronous grants a greater predictability in its execution semantics. In terms of meeting
hard real-time constraints, a synchronously designed program will have predictable points
for schedulability, allowing for techniques such as rate-monotonic scheduling (Klein, 1993)
to meet strict timing deadlines. These categories of techniques grant a concurrent program
the same possibilities for verification as a sequential one.
Even though these strict scheduling programs are effective for their problem domains, they
are difficult to maintain and do not scale that well for the large software systems required.
In fact most interactive programs and other soft real-time systems use the concept of event-
driven semantics, which can allow interruption at any point in time. These have the benefit
of dealing with interactions only upon demand, and so scale better, especially in terms of
not placing a huge computational or communication load on the system when not needed.
Search WWH ::




Custom Search