Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison http://digital.library.wisc.edu/1793/56968 2026-03-05T17:12:58Z 2026-03-05T17:12:58Z Rotenberg, Eric Jacobson, Quinn Smith, Jim http://digital.library.wisc.edu/1793/95388 2025-06-26T13:33:26Z 1998-12-18T00:00:00Z

A Study of Control Independence in Superscalar Processors Rotenberg, Eric; Jacobson, Quinn; Smith, Jim An instruction is control independent of a preceding conditional branch if the decision to execute the instruction does not depend on the outcome of the branch -- this typically occurs if the two paths following the branch re-converge prior to the control independent instruction. A speculative instruction that is control independent of an earlier predicted branch does not necessarily have to be squashed and re-executed if the branch is predicted incorrectly. Consequently, control independence has been put forward as a significant new source of instruction level parallelism in future generation processors. However, its performance potential under practical hardware constraints is not known, and even less is understood about the factors that contribute to or limit the performance of control independence. A study of control independence in the context of superscalar processors is presented. First, important aspects of control independence are identified and singled out for study, and a series of idealized machine models are used to isolate and evaluate these aspects. It is shown that much of the performance potential of control independence is lost due to data dependences and wasted resources consumed by incorrect control dependent instructions. Even so, control independence can close the performance gap between real and perfect branch prediction by as much as half. Next, important implementation issues are discussed and some design alternatives are given. This is followed by a more detailed set of simulations, where the key implementation features are realistically modeled. These simulations show typical performance improvements of 10 to 30 percent over a baseline superscalar processor. n/a

1998-12-18T00:00:00Z Cyphert, John http://digital.library.wisc.edu/1793/84817 2024-01-06T10:49:19Z 2024-01-01T00:00:00Z

Compositional, Monotone, and Non-linear Program Analysis Cyphert, John The presence of bugs in deployed software can lead to great economic and or human cost. One strategy for mitigating these losses is to prove the functional correctness of programs---or sometimes aspects of a program's functional correctness---during development. With an appropriate analysis technique, one can guarantee that deployed software will satisfy important properties for all possible inputs. This dissertation presents several lines of research that advance the state-of-the-art in the topic area of automatically characterizing program behavior to prove functional correctness. More specifically, this dissertation focuses on building program-analysis techniques and tools that exhibit some combination of (1) producing non-linear invariants, (2) reasoning compositionally by building up more complex program summaries from simpler ones, and (3) being predictable by satisfying a monotonicity property. The first line of research presented in this dissertation gives a program-analysis technique that is compositional and produces non-linear invariants. The key feature of the method is how it analyzes loops. To analyze loops, loop bodies are abstracted with the newly introduced wedge abstract domain. Furthermore, wedges admit a recurrence-extraction procedure that results in a set of c-finite recurrence relations that are implied by the original loop body. In this dissertation, we solve these c-finite recurrences using a technique based on operational calculus. In combination, these advancements yield a program-analysis tool that is able to produce program summaries that include equalities and inequalities between expressions that include polynomial, exponential, and logarithmic terms. Experimental results show that our method is able to generate precise non-linear summaries that are able to prove more programs correct in comparison to other state-of-the-art tools. The second line of research presented in this dissertation focuses on automatically improving the precision of a base compositional analysis by modifying the way the base analysis summarizes loops. Specifically, this line of research presents a method that automatically rewrites a program-analysis problem to a semantically sound alternative problem, with the goal of achieving a more-precise analysis result. In pursuit of this goal, we introduce the notion of a pre-Kleene algebra (PKA) as model for reasoning about analysis precision. A key property of PKAs is that they have a monotonicity property. Our method then refines a program-analysis problem with respect to the laws of PKAs. Then, as long as the base analysis satisfies the axioms of PKAs, our method guarantees that the refined program-analysis problem will yield a result that is at least as good as (and often better than) the result obtained from the original analysis formulation. Although this result is technically a "no-degradation" result, an experimental evaluation showed that our method allows for an analysis to prove roughly 25% more programs correct at the expense of an approximately 50% increase in analysis time. The third line of research presented in this dissertation introduces the optimal symbolic-bound synthesis (OSB) problem. In short, an instance of the OSB problem has as input a term t and a formula phi, and asks to find a symbolic term t* such that (i) phi implies that t* upper-bounds t, and (ii) t* exhibits some "term-desirability" properties. We present a heuristic method for finding a symbolic term t* when t and phi may contain non-linear terms. Our method works by extracting an implied cone of polynomials from phi and then reducing t by the cone of polynomials to obtain a sound upper bound t*. At a high level, our method makes use of Groebner-basis techniques for reducing with respect to equations, and a novel local-projection method for reducing with respect to inequalities. To show the utility of our method, we apply our techniques to the setting of bounding relevant terms, such as those representing the value of some financial asset, in Solidity smart contracts. The fourth line of research presented in this dissertation gives another compositional program analysis that is able to produce non-linear invariants. The method follows a similar structure to the method from the first line of research; however, the subsequent method has the additional benefit of being monotone. We implemented our monotone technique in a tool named Abstractionator. Instead of wedges, Abstractionator uses solvable transition ideals as an intermediate abstraction of a loop. Abstractionator then uses a summarization technique inspired by prior complete methods based on solvable polynomial maps to summarize abstracted solvable transition ideals. Thus, by utilizing an abstraction procedure for solvable transition ideals, Abstractionator brings to bear prior complete polynomial-invariant-generation methods to the setting of programs with a more general syntactic structure. Experiments show that Abstractionator compares favorably with other program-analysis tools, especially in the case where non-linear invariants are required.

2024-01-01T00:00:00Z Barford, Paul Ng, Tony http://digital.library.wisc.edu/1793/84773 2023-12-01T11:42:35Z 2023-11-30T00:00:00Z

NSF Workshop on Emerging Research Opportunities at the Intersection of Statistics and Internet Measurement Final Report Barford, Paul; Ng, Tony The Workshop on Emerging Research Opportunities at the Intersection of Statistics and Internet Measurement was held in January 2023 at Boston University. The goal of the workshop was to bring together Internet measurement researchers and statisticians/mathematicians to identify important and promising future research directions and exchanging research ideas that could lead to future collaborations. Forty-two scholars from academia, industry, and the NSF participated. The workshop agenda consisted of a series of 17 keynote talks interspersed by small group discussions. Talks and discussions addressed a wide range of topics including Internet traffic analysis, connectivity and topology analysis, application and user behavior, challenges and opportunities in Internet data collection and data processing, cutting-edge models, and methodologies in different areas of statistics, applied mathematics and data science. More specifically, talks discussed selection biases and qualifying biases in estimates from crowdsourced and other non-random samples, process monitoring, anomaly detection, adversarial risk analysis, data protection, models and methods for network and Internet traffic data collection and processing, and advanced and innovative statistical models, methods, algorithms, and tools that can be applied directly in Internet measurement research. The major outcomes from the workshop are twofold. First, the workshop was successful in facilitating introductions between participants from the Internet measurement and statistics/mathematics communities. Conversations in small group sessions were cordial and carried on beyond allotted times. Second, opportunities for future collaborations were clearly identified over the range of topics that were discussed from experimental design and data gathering to data analysis and modeling to data privacy and visualization. The possibility of holding this workshop again in the future to toward the goal of fostering new research and new collaborations was also discussed.

2023-11-30T00:00:00Z Henkel, Jordan http://digital.library.wisc.edu/1793/83813 2022-12-08T10:03:03Z 2022-08-17T00:00:00Z

Learning from Code and Non-Code Artifacts Henkel, Jordan Three things are fundamentally true about software: (i) every day that passes we, as a society, generate more software (more code, more documentation, and more software-related artifacts of all kinds), (ii) it is easier to write new software than it is to understand and maintain existing software, and (iii) we depend on software in every area of our lives (from critical infrastructure to entertainment and everything in between). These three fundamental truths set the stage for one massive problem: if there is more software every day, and it is hard to understand and maintain, how can we ever ``keep up'' with this unbounded growth? How can we ever truly understand the software we depend on if we are adding to it every single day? In this thesis, we provide new ideas and tools that help with some of these issues. More specifically, this thesis takes the position that we need tools and techniques for understanding and learning from software. To do this, we consider software to be a composite of source code and other, non-code, artifacts (build scripts, documentation, etc.). We introduce techniques for working with both code and non-code artifacts; for code, we introduce a form of code embeddings (learned from a semantic representation of code: abstracted symbol traces); we then create a novel specification mining technique that uses these semantic code embeddings; additionally, we explore the robustness of models of code; and, to address non-code artifacts, we mine tree-association rules from Dockerfiles, from which we learn best practices; we take these learned best practices and create a human-in-the-loop technique for automated repair of Dockerfiles. Finally, to accelerate empirical research on software and lay a groundwork for a more comprehensive solution to trusting the growing amount of software we---as a society---create, we introduce code-book. code-book is a tool for interactively querying and analyzing code inspired by the great successes of the Data Science community. With code-book, we introduce a novel query-by-example-based query language for asking questions about code. Furthermore, we develop this query language so that users can ask questions that incorporate both code structure and ``fuzzy'' semantic constraints (based on code embeddings).

2022-08-17T00:00:00Z