Topic: dependency analysis

topics > computer science > data > Group: type checking

coordination system
change notification
code optimization
code optimization by flow analysis
code optimization by global analysis
configuration management
consistency testing
data caching
database consistency and reliability
debugging by usage rules
flavor analysis and typestates for supplementary type checking
optimization of object-oriented programs
register allocation by use-def graphs
reliable communication
software change management
static single assignment; SSA
system builds
version control


A is dependent on B if changes in B can effect A. A is dependent on B if a possible execution sequence of B includes a causal chain to a possible execution sequence of A.

Dependency analysis determines the dependencies of a system. Dependency analysis requires an exhaustive analysis of system behavior. Exhaustive analysis requires a complete model of the system. The model must be automatically extracted from the system, otherwise changes to the system may invalidate the model. Even with automatic extraction dependencies are easily missed.

Analysis is simplified if dependencies are limited. Besides simplifying formal analysis, fewer dependencies makes a system easier to understand and change. Fewer dependencies reduces the chance of unintended consequences.

A uses hierarchy or levels reduces the scope of dependency analysis. Upper levels of the hierarchy depend on lower levels, but not vice versa. Ideally, the leaves are independent of each other. In practice, the hierarchy is informally defined and too imprecise for analysis.

Access control reduces the scope of dependency analysis. If a system can not read A, changes to A can not effect B. Similarly if a system can not change B, then changes to A can not effect B. If access is unavailable by default, then a request for access provides evidence of a possible dependency.

Cached data must be flushed if it depends on modified data elsewhere. (cbb 7/06)

Subtopic: dependency as specification up

Quote: a UML dependency occurs when a change in one thing affects the semantics of another [»boocG_1999]
Quote: a dependency between modules is an assumption about a module's specification in an environment; a module may have multiple specifications, one per dependency [»jackD10_2002]
Quote: dependency specification better than dependency graph; no transitivity problem, allows polymorphism, supports pre- and post-conditions, enables substitutivity [»jackD10_2002]
Quote: a design pattern may complicate the code; dependency specifications simplify a pattern [»jackD10_2002]

Subtopic: coordination up

Quote: survey of coordination theory for managing dependencies among activities; e.g., shared resources, producer/consumer, simultaneity constraints, task/subtask [»maloTW3_1994]

Subtopic: casual dependency up

Quote: CATOCS message ordering does not enforce casual dependencies due to a shared database or external environment; e.g. a sensor [»cherDR12_1993]

Subtopic: uses hierarchy up

Quote: 'A uses B' if the correct functioning of A depends on a correct implementation of B [»parnDL5_1978]
Quote: should organize modules in a hierarchy over the 'uses' or 'depends on' relation; allows independent use of lower levels
Quote: the connections between parts of programs are the assumptions that the parts make about each other; these connections limit change and make proof difficult [»parnDL_1978]

Subtopic: dependent types up

Quote: in the theory of dependent types, Modula-3's generic interface is a function from module-values to module-types and a generic module is a function from module-values to module-values [»nelsG_1991]

Subtopic: class dependency up

Quote: reduce class dependencies by following the Law of Demeter; restrict message-sending to arguments, self, and self's components [»liebKJ9_1989]
Quote: design patterns are motivated by dependence considerations; e.g., the Observer pattern uses a generic observer specification, allowing reuse by other observer classes [»jackD10_2002]

Subtopic: scheduling dependency up

Quote: model static scheduling with DAG of dependencies between atomic, program tasks and communication costs

Subtopic: compilation dependency up

Quote: a compilation dependency occurs when one module is used to compile another; if a module is recompiled, then so are all dependent modules [»laueHC_1979]
Quote: if one module depends on the implementation details of another module, it may need changing when the other changes
Quote: maintain intermodule dependencies by augmenting a graph with factoring and filtering nodes; reduces recompilation size to one seventh of a header file-based scheme [»chamC4_1995]
Quote: a filtering node is a program to check an intermodule dependency; e.g., compare old and new callee set and invalidate on change; compilers may need to do this work anyway [»chamC4_1995]
Quote: Cedar uses system layering to reduce compilation dependencies and increase use of system components [»swinDC7_1985]

Subtopic: single-assignment graph up

Quote: implement field analysis with static, single-assignment (SSA) graph; analyze loads and stores without optimization or context-sensitive information [»ghemS6_2000]
Quote: ABCD-eliminate array bounds checks on demand; sparse SSA analysis; removes 45% of bounds checks [»bodiR6_2000]

Subtopic: points-to analysis up

Quote: field-based Andersen-style points-to analysis of a million lines of code in under a second [»heinN6_2001]
Quote: points-to analysis with a database, on-the-fly transitive closure, caching of reachability computations, and cycle elimination

Subtopic: result cache up

Quote: Vesta caches the results of expensive function calls with precise, dynamic, fine-grained dependencies
Quote: the Vesta cache is indexed by the fingerprint of all dependencies at a function invocation site; secondary dependencies checked by their name and fingerprint [»heydA_2006]
Quote: dependency paths are the secondary keys for Vesta's function cache; a dependency path is a type and a path; e.g., complete value, existence, false existence [»heydA_2006]
Quote: an immutable directory and system model limits the propagation of dependencies; alternatively, a system model is a closure of its file and import clauses [»heydA_2006]
Quote: consistency test by annotating procedure with dependency relations for each result; useful for large, untidy structures [»jackD6_1993]
Quote: index function cache by primary dependencies; i.e., body of function, values of scalar arguments [»heydA6_2000]
Quote: function cache's secondary key is the names and values that the function call depends on
Quote: the EROS kernel caches all state; requires explicit allocation of the memory map and dependency tracking [»shapJS1_2002]

Subtopic: annotated dependency up

Quote: in source control, users should define dependencies between elements for warnings prior to changes and notification after changes [»leblDB5_1984]

Subtopic: frozen configuration up

Quote: freeze configurations of local applications; avoids spontaneous replacement of dependent components; need private copies [»briaM10_1999]

Subtopic: problems due to dependency up

Quote: abstract data type is difficult to extend; many changes to representation [»cookWR5_1990]

Subtopic: problems with dependency up

Quote: dependency models do not capture shared information; e.g., a format shared between modules

Related Topics up

Group: coordination system   (8 topics, 217 quotes)
Topic: change notification (19 items)
Topic: code optimization (54 items)
Topic: code optimization by flow analysis (47 items)
Topic: code optimization by global analysis (24 items)
Topic: configuration management (25 items)
Topic: consistency testing (60 items)
Topic: constraints (35 items)
Topic: data caching (35 items)
Topic: database consistency and reliability (15 items)
Topic: debugging by usage rules (41 items)
Topic: flavor analysis and typestates for supplementary type checking (68 items)
Topic: optimization of object-oriented programs (16 items)
Topic: register allocation by use-def graphs (9 items)
Topic: reliable communication (29 items)
Topic: software change management (48 items)
Topic: static single assignment; SSA (19 items)
Topic: system builds (43 items)
Topic: version control
(34 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.