Here is the current set of notes I have listing types of interleaving
we've found so far. It includes pointers to examples, mostly from the
NAIF library. Please look it over and see if there are better ways of
categorizing and organizing these cases of interleaving. The list may
also include some cases that you feel don't belong, so figuring out
why they don't belong will help us better characterize this
phenomenon. Also, if you run across additional examples, post them to
the newsgroup and we'll try to hash out where they fit.
Linda
___________________________________________________________________________
Notes on Forms of Interleaving (with Examples)
Oct 13, 1994
TEXTUAL
- same var name used for 2 different purposes
[should be able to handle it by dflow analysis, renaming]
- no sharing, just interleaved in text
-- scaling/unscaling wrapped around core computation (NPEDLN)
More generally, delocalized relationships btwn
computational fragments or pieces of data:
- "Wrapped" computations are special cases of this.
- data coupling is another form (e.g., ellipsoid is usually represented
by 3 separate DP integers A,B,C, which specify the lengths of its
semi-axes). With good coding style, these components are acted upon
consistently, all at the same time, in localized computations. So in
the NAIF library, for instance, they might not be involved in really
interesting cases of interleaving.
-- error handling involving inputs.
-- multiple entry points to a routine (e.g., dafana.f)
IMPLEMENTATION LEVEL (algorithmic, data structure)
- loop fusion
- error handling (NPEDLN: error checks on SCLA**2 an intermediate result)
- multiple outputs w/ different roles
NPEDLN: 1) computation of nearest point on ellipsoid to a line and
2) shortest distance btwn the line and the ellipsoid.
- multiple special cases, with sharing
-- special idiosyncratic case that needs special handling (not covered by
general case or would complicate general case if not handled separately):
e.g., SURFPT: finds intersection of ellipsoid and line-of-sight vector.
sets up problem as one of solving a quadratic equation and then does a
case analysis on conditions involving the equation's coefficients.
Each of these cases means something different in terms of the position
of the observer relative to the ellipsoid and how to compute the
intersection.
e.g., DIAGS2: Diagonalize a symmetric 2x2 matrix (SYMMAT).
special case: check for the case of a diagonal input matrix early on:
C We check for the case of a diagonal input matrix, since
C eigenvector determination is simplified by ruling out this
C case.
-- multiple special cases result in single output that can be
interpreted differently, depending on which case occurred
(e.g., INELPL -- NXPTS XPT1 XPT2 -- these are interpreted
differently, depending on flag NXPTS -- a data tag saying how to
interpret the outputs; like a control flag, saying whether the
other outputs are defined (similar to FOUND), but it's not just
a control flag: if it is -1, it is saying the ellipse lies on
the plane and the answer is infinity.)
- control coupling
INEDPL: 1) intersection of ellipse and plane
2) control flag FOUND saying whether intersection exists.
(control coupling -- also outputs like FAILED, ERROR)
- data space sharing
-- same output value used for two different purposes (clock and
accumulator) (length and existence-flag)
-- same dstruc slot used for 2 different purposes
- multiple entry pts to routine -- these act as subroutines w/ access
to global state that NAIF builders want treated as private. * Global
interactions involving global state. *
[Some interleavings at the implementation level are specializations at
the design level. For example, special cases interleaved in case stmt may
share control condition checking and some preliminary computations (as
in INELPL). At implem. level this can be seen as interleaving several
special computations for the various cases (ellipse lies on plane,
does not intersect plane, intersects at 1 pt, intersects at 2), while
at design level, might be seen as separate encapsulations of
computations that are done, depending on which case the data falls into.]
DESIGN LEVEL (can think in terms of OO design)
architectural level interleaving -- executions
- interleaved input data streams -- master file updates
- interleaved output data streams -- report writer
-- can be 2 separate computations, but may be interleaved in
interactions with each other (page layout and computations of data)
- error handling architecture in subroutine library: error flags
(continue, default, return, etc.)
DOMAIN LEVEL
??
perhaps interacting objects.
-- -Linda Wills (linda@cc.gatech.edu)