In some classification problems the feature space is heterogeneous in that the best features on which to base the classification are different in different parts of the feature space. In some other problems the classes can be divided into subsets such that distinguishing one subset of classes from another and classifying examples within the subsets require very different decision rules, involving different sets of features. In such heterogeneous problems, many modeling techniques (including decision trees, rules, and neural networks) evaluate the performance of alternative decision rules by averaging over the entire problem space, and are prone to generating a model that is suboptimal in any of the regions or subproblems. Better overall models can be obtained by splitting the problem appropriately and modeling each subproblem separately. This paper presents a new measure to determine the degree of dissimilarity between the decision surfaces of two given problems, and suggests a way to search for a strategic splitting of the feature space that identifies regions with different characteristics. We illustrate the concept using a multiplexor problem, and apply the method to a DNA classification problem.

This paper describes a system (AVPGEN) for generating tests (called architecture verification programs or AVP's) to check the conformance of processor designs to the specified architecture. To generate effective tests, AVPGEN uses novel concepts like symbolic execution and constraint solving, along with various biasing techniques. Unlike many earlier systems that make biased random choices, AVPGEN often chooses intermediate or final values and then solves for initial values that can lead to the desired values. A language called SIGL (symbolic instruction graph language) is provided in AVPGEN for the user to specify templates with symbolic constraints. The combination of user-specified constraints and the biasing functions is used to focus the tests on conditions that are interesting in that they are likely to activate various kinds of bugs. The system has been used successfully to debug many S/390 processors and is an integral part of the design process for these processors.>

High performance processor designs use techniques such as pipelining, multiple execution units, register renaming, bypass paths, and branch prediction to meet their goals. These techniques make them susceptible to design errors that are triggered only when executing complex sequences of instructions. We introduce a language called SIGL for specifying symbolic instruction graphs (SIGs) that can be used as templates for such test cases. SIGL allows specification of constraints in a high level template from which many test cases can be generated, all targeting some specific characteristic of a processor design. SIGL has been used successfully to check the conformance of various industrial processor designs to their architectural specifications.>

Delay testing, as opposed to static testing introduces the parameter of time as a new variable. Time impacts the way defects manifest themselves and are modeled as faults, as well as how defect sizes and system timing statistics interact with tester timing constraints in the detection of causes for dynamic system malfunctions. This paper briefly discusses some of the issues that had to be addressed in the development of a comprehensive system for delay testing in a Level Sensitive Scan Design environment.

Elimination of partial redundancies is a powerful optimization that has been implemented in at least three important production compilers and has inspired several similar optimizations. The global data flow analysis that supports this family of optimizations includes some bidirectional problems. (A bidirectional problem is one in which the global information at each basic block depends on both control flow predecessors and control flow successors.) This paper contributes two ways to simplify and expedite the analysis, especially for large programs. For each global data flow question, we examine only the places in the program where the question might have an answer different from a trivial default answer. In a large program, we may examine only a small fraction of the places conventional algorithms would examine. We reduce the relevant bidirectional problems to simpler unidirectional problems. These bidirectional problems can be solved by applying a quick correction to a unidirectional approximation.

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization.A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable.Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow propertiee of programs.Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimization.Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use.We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs.The algorithms use dominance frontiers, a new concept that may have other applications.We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program.This paper thus presents strong evidence that these structures can be of practical use in optimization.

Defects in integrated circuits can cause delay faults of various sizes. Testing for delay faults has the goal of detecting a large fraction of these faults for a wide range of fault sizes. Hence, an evaluation scheme for a delay fault test must not only compute whether or not a delay fault was detected, but also calculate the sizes of detected delay faults. Delay faults have the counterintuitive property that a test for a fault of one size need not be a test for a similar fault of a larger size. This makes it difficult to answer questions about the sizes of delay faults detected by a set of tests. A model for delay faults that answers such questions correctly, but with calculations simple enough to be done for large circuits, is presented.>

A method is presented for simulation with two zillion and three values. The values that are propagated by the simulation include the familiar 0, 1, and X and also a collection of named unknowns and their formal negations. Each value fits into a single computer word. Applications of this restricted symbolic evaluation include design rule checking for circuits with embedded arrays and timing verification. The authors explore these two applications briefly. By carefully choosing rules for combining the two zillion and three values, and the representations of the values, it is possible to make simulation surprisingly efficient. The authors present two variants and an implementation of each. Both are fast; the faster one sometimes yields less information.>

Article An efficient method of computing static single assignment form Share on Authors: R. Cytron IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , J. Ferrante IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , B. K. Rosen IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Computer Science Dept., Brown University, Providence, RI Computer Science Dept., Brown University, Providence, RIView Profile Authors Info & Claims POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1989 Pages 25–35https://doi.org/10.1145/75277.75280Online:03 January 1989Publication History 308citation1,950DownloadsMetricsTotal Citations308Total Downloads1,950Last 12 Months119Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An approach to test for delay faults is presented. A variable size delay fault model is used to represent these failures. The nominal gate delays with the manufacturing tolerances are an integral part of the model and are used in the propagation of simplified waveforms through the logic network. The faulty waveforms are functions of the variable-size delay fault. For each fault and test pattern, a threshold is computed such that this fault is detected if its size exceeds epsilon . This threshold is used (along with the minimum slack at the fault site) to determine a metric called quality. The quality of detection for a fault measures how close the test came to exposing the ideally smallest-size fault at that point. This metric (together with the traditional fault coverage) gives a complete measure of the goodness of the test.>

For pt.I see ibid., p.857-66 (1988). A novel algebra is introduced for delay test generation. The algebra combines the nine natural logic values (00 , 01, 0X, 10, 11, 1X, X1, XX) with special attributes that record both heuristic choices and whatever information about waveforms is deducible algebraically (i.e. without numerical computations using actual gate delays). A test generator uses this algebra in an efficiently organized backtrack search. The test generator is linked to a delay fault simulator. Previous event-driven simulators have considered different types of events; one type of event is a change in faultless values from one test to another test, and the other type of event is a difference between faulty and faultless values. The presented simulator is driven by both types of events. Each generated test is simulated to determine the quality of detection.>

Article Free Access Share on Global value numbers and redundant computations Authors: B. K. Rosen IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Department of Computer Science, Brown University, Providence, RI Department of Computer Science, Brown University, Providence, RIView Profile Authors Info & Claims POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1988 Pages 12–27https://doi.org/10.1145/73560.73562Published:13 January 1988Publication History 278citation1,997DownloadsMetricsTotal Citations278Total Downloads1,997Last 12 Months240Last 6 weeks26 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The High-Speed Simulator (HSS) is a fast and flexible system for gate-level fault simulation. Originally limited to combinational logic, it is being extended to handle sequential logic. It may also prove useful as a functional simulator. The speed of HSS is obtained by converting the cycle-free portions of a circuit into optimized machine code for a general-purpose computer. This compiled code simulates the circuit's response for 16 or 32 test patterns in parallel. Faults are injected into the circuit by changing the machine instruction corresponding to the fault location. From the range of speeds seen in recent measurements, we take 240 million gates per second as a fair general estimate of the speed of 2-valued simulation running on a 3081/K computer. For 3-valued simulation, divide by 2.9. The paper discusses the merits and drawbacks of the HSS strategy. It also sketches the extensions of HSS to model sequential logic and the various applications of HSS. These include functional verification, design for testability, good machine signatures, and accurate simulation of transistor-level defects in certain CMOS technologies. Finally, there is some discussion of how the simulation requirements of future designs can be met, and of the lessons to be drawn from long-term experimentation with HSS.

This paper deals with concepts recently introduced to avoid duplication of effort when several global data flow problems share the same underlying control flow. The flow scheme is the control flow portion of the input to data flow analysis. By finding a family of formal expressions called a flow cover for a given flow scheme, one can be ready to solve any problem with that scheme by interpreting the expressions in light of the remaining portions of the problem. Our main result relates the problem of finding a flow cover to that of finding regular expressions to describe certain sets of paths in the graph. The following is a major consequence of this relationship (slightly oversimplified). If a family of formal expressions acts like a flow cover for one special problem constructed from a given flow scheme, then it is a flow cover. The constructed problem has several algebraic properties that fail in some of the problems encountered in practice but that may be assumed anyway, at least when one wishes to construct flow covers. Applications include updating a given flow cover in light of a small change in the flow scheme, and improving upon the folkloric way to cope with multiple entry nodes.

In analysis of programs and many other kinds of computation, algorithms are commonly written to have an input P and an output Q, where both P and Q are large and complicated objects. For example, P might be a routing problem and Q might be a solution to P. Although documented and discussed in this exhaustive style, algorithms are sometimes intended for use in contexts with two departures from the one-time analysis of an entire new input. First, the current value of P is the result of a small change to a previous value of P. We want to update the results of the previous analysis without redoing all of the work. Second, accurate information is only wanted in some designated portion of the large output Q. Possibly inaccurate information may appear elsewhere in Q. We want the analysis to be demand-driven: accurate where accuracy is demanded, but not burdened by the cost of providing much more than is demanded. This paper studies demand-driven algorithms capable of updating without extensive reanalysls. Such algorithms are called incremental, in contrast with the one-time analysis of an entire new input contemplated by exhaustive algorithms. In some cases, it is shown that an exhaustive algorithm can be easily recast in an efficient incremental style. Other algorithms for the same problem may be much less amenable to incremental use. It is shown that traditional exhaustive computational complexity bounds are poor predictors of incremental performance. The main examples are taken from global data flow analysis.

It is known that not aU paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is, therefore, usual for analytic methods to consider aU paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include aUl possible paths, but smaU enough to exclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set Q. The paths that qualify to be considered are (essentially) those for which the composition of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data-flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a smaUl set of real programs) indicate that qualified analysis is feasible and substantialy more informative than ordinary analysis.

It is known that not all paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is therefore usual for analytic methods to consider all paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include all possible paths but small enough to exclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set Q. The paths that qualify to be considered are (essentially) those for which the composition of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a small set of real programs) indicate that qualified analysis is feasible and substantially more informative than ordinary analysis. The methodology also has a beneficial feedback effect on the delicate task of passing from programs to meaningful data flow analysis problems. Even when all paths qualify, unusually sharp information can be obtained by passing from programs to problems in ways suggested by our theorems.

We propose a mathematical foundation for reasoning about the correctness and computational complexity of record handling algorithms, using algebraic methods recently introduced in graph theory. A class of pattern matching and replacement rules for graphs is specified, such that applications of rules in the class can readily be programmed as rapid transformations of record structures. When transformations of record structures are formalized as applications of rules to appropriate graphs, recent Church–Rosser type theorems of algebraic graph theory become available for proving that families of transformations are well behaved. In particular, we show that any Church–Rosser family of transformations can be combined with housekeeping operations involving indirect pointers and garbage collection without losing the Church–Rosser property, provided certain mild conditions on the rules defining the family are satisfied. This leads to suggestions for the design of record handling facilities in high level languages, especially when housekeeping chores are to be performed asynchronously by service processes that run in parallel with the main process. These results and the general theorems that support them can be used to analyze the behavior of a large record structure that can be updated asynchronously by several parallel processes or users.

Ambitious optimizing compilers have alertness and selectivity properties that lead to a serious discrepancy between the total cost of data flow analysis and the partial cost covered by the usual kind of theoretical estimate. This discrepancy motivates a new high-level analysis method for data flow problems expressible in terms of a semilattice L and monoid M of isotope maps from L to L, under algebraic constraints somewhat weaker than those imposed by Graham and Wegman in solving data flow problems on reducible graphs. The cost of the new method is roughly similar to that of the method of Graham and Wegman when estimates are made in the usual way, while the cost of updating in alert and selective compilers tends to be lower. The new method copes with arbitrary escapes and jumps, can find sharper information than fixpoint methods when M is not distributive, and can be tuned to trade time for sharpness of information.

Global analysis and optimization techniques presuppose local data flow information about the effects of program statements on the values associated wRh names For procedure calls this information is not immediately available but can presumably be obtained through flow analysis of procedure bodies Accurate mformatlon proves to be surprisingly difficult to obtain This paper includes a language independent formulation of the problem, an interprocedural data flow algorithm, and a proof that the algorithm is correct Symbohc data flow analysis is introduced in the course of optimizing the algorithm We move much of the work outside of a loop by manipulating partially evaluated symbolic expressions for the data within the loop Foundational difficulties are revealed when the theory of data flow analysis is extended to support extensive optimization of procedural language programs Several widespread assumptions become false or ambiguous A few of the problems are resolved here Inductive arguments are facilitated by a simple path tree representation of control flow that allows for both recurslon and side effects

The earliest data flow analysis research dealt with concrete problems (such as detection of available expressions) and with low level representations of control flow (with one large graph, each of whose nodes represents a basic block). Several recent papers have introduced an abstract approach, dealing with any problem expressible in terms of a semilattice L and a monoid M of isotone maps from L to L, under various algebraic constraints. Examples include [CC77; GW76; KU76; Ki73; Ta75; Ta76; We75]. Several other recent papers have introduced a high level representation with many small graphs, each of which represents a small portion of the control flow information in a program. The hierarchy of small graphs is explicit in [Ro77a; Ro77b] and implicit in papers that deal with syntax directed analysis of programs written within the confines of classical structured programming [DDH72, Sec. 1.7]. Examples include [TK76; ZB74]. The abstract papers have retained the low level representations while the high level papers have retained the concrete problems of the earliest work. This paper studies abstract conditions on L and M that lead to rapid data flow analysis, with emphasis on high level representations. Unlike some analysis methods oriented toward structured programming [TK76; Wu75; ZB74], our method retains the ability to cope with arbitrary escape and jump statements while it exploits the control flow information implicit in the parse tree.

Theorists and implementers can easily interact in such a way that software performs improperly, even if there are no mathematical mistakes in the theory and no coding bugs in the implementation. This correspondence explains the problem and some ways to cope with it. Examples are drawn from program proving, language design, and code optimization.

Control flow relations in a high level language program can be represented by a hierarchy of small graphs that combines nesting relations among statements in an ALGOL-like syntax with relevant perturbations caused by goto or leave statements. Applications of the new style of representation include denotational semantics, data flow analysis, source level compiler diagnostics, and program proving.

Given partially ordered sets (posets) P and Q, it is often useful to construct maps g:P→Q which are chain-continuous: least upper bounds (supremums) of nonempty linearly ordered subsets are preserved. Chaincontinuity is analogous to topological continuity and is generally much more difficult to verify than isotonicity: the preservation of the order relation. This paper introduces the concept of an extension basis: a subset B of P such that any isotone f:B→Q has a unique chain-continuous extension g:P→Q. Two characterizations of the chain-complete posets which have extension bases are obtained. These results are then applied to the problem of constructing an extension basis for the poset [P→Q] of chain-continuous maps from P to Q, given extension bases for P and Q. This is not always possible, but it becomes possible when a mild (and independently motivated) restriction is imposed on either P or Q. A lattice structure is not needed. Finally, we consider extension bases which can be recursively listed and derive a recently established theorem as a corollary.

This paper discusses the desirability of procedure linkage optimization and sketches a general theory of interpretive semantics which is motivated by technical problems in specifying and validating program transformations that optimize procedure linkages. One particular transformation is treated in detail.Recursive ALGOL 60 procedures sometimes pass parameters by name in such a way that the general thunk mechanism is unnecessary and inefficient. We present an optimization which detects this kind of call-by-name and implements it thunklessly. We prove that the transformation preserves semantics and we discuss the effect on running time and memory management.

Subtree replacement systems form a broad class of tree-manipulating systems. Systems with the “Church-Rosser property” are appropriate for evaluation or translation processes: the end result of a complete sequence of applications of the rules does not depend on the order in which the rules were applied. Theoretical and practical advantages of such flexibility are sketched. Values or meanings for trees can be defined by simple mathematical systems and then computed by the cheapest available algorithm, however intricate that algorithm may be. We derive sufficient conditions for the Church-Rosser property and discuss their applications to recursive definitions, to the lambda calculus, and to parallel programming. Only the first application is treated in detail. We extend McCarthy's recursive calculus by allowing a choice between call-by-value and call-by-name. We show that recursively defined functions are single-valued despite the nondeterminism of the evaluation algorithm. We also show that these functions solve their defining equations in a “canonical” manner.

We define a general class of tree-manipulating systems that includes many of the special cases from logic, linguistics, and automata theory. Systems possessing what we call the “Church-Rosser property” are appropriate for evaluation or translation processes: the end result of a complete sequence of applications of the rules does not depend on the order in which the rules were applied. We sketch the theoretical and practical advantages of such flexibility.