DISCRETE-TIME MODELING OF PIPELINE COMPUTERS UNDER FLOW PERTURBATIONS (RESIDUAL-TIME, TRACE TRANSFORMATIONS, DATA DEPENDENCY)

We have developed a unified methodology for modeling instruction flow in pipelined computers at a discrete-time level where localized flow perturbations are fully accounted for.; We have introduced the notion of a probabilistic variable-time segment to develop a new class of models called residual-time models which solve for pipeline performance degradation due to machine-dependent perturbations. Residual-time models are completely general, and two machines require distinct models only if their general topology differs. Independence assumptions, although convenient, are not necessary with residual-time models. The state space for a residual-time model is significantly smaller than that for an equivalent discrete-time model.; These models require job-load statistics for their solution. A new set of trace transformations provides these statistics. These transformations operate on any data-dependency graph, and reduce it to an equivalent graph in which there is no interference between dependencies. Dependency statistics collected from the reduced graph are simple, and contain all of the required job-load information.; These modeling techniques are applied to four different machines. The residual-time technique produces performance estimates that are significantly more accurate than those obtainable with classical modeling techniques.