Runtime specialization is used for optimizing programs based on partial information available only at runtime. In this paper we apply autotuning on runtime specialization of Sparse Matrix-Vector Multiplication to predict a best specialization method among several. In 91% to 96% of the predictions, either the best or the second-best method is chosen. Predictions achieve average speedups that are very close to the speedups achievable when only the best methods are used. By using an efficient code generator and a carefully designed set of matrix features, we show the runtime costs can be amortized to bring performance benefits for many real-world cases.

Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this paper, we explore the potential for obtaining speedups for sparse matrix-dense vector multiplication using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving runtime specialization, comparing them to methods that do not (including Intel's MKL library). For this work, our focus is the evaluation of the speedups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments use 23 matrices from the Matrix Market and Florida collections, and run on five different machines. In 94 of those 115 cases, the specialized code runs faster than any version without specialization. If we only use specialization, the average speedup with respect to Intel's MKL library ranges from 1.44x to 1.77x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines.

The Programming Studio in the University of Illinois Computer Science department is a required course in which small groups of students participate in weekly code reviews of each other's programs. To increase student engagement in the discussions, Tablet PCs were introduced for several weeks in the middle of the semester. By recording the discussions before, during, and after the use of tablets, we measure the effectiveness of this intervention. In doing so, we develop a simple metric to measure the "active engagement" of the participants. We found each section was significantly more engaging when using Tablet PCs (p<0.0001) and the large majority of individual participants were more engaged. This paper contributes both an objective measurement of "active engagement" and a successful intervention in a programming studio-type course.

Many tools for automated testing, model checking, and debugging store and restore program states multiple times. Storing/restoring a program state is commonly done with serialization/deserialization. Traditionally, the format for stored states is based on data: serialization generates the data that encodes the state, and deserialization interprets this data to restore the state. We propose a new approach, called CoDeSe, where the format for stored states is based on code: serialization generates code whose execution restores the state, and deserialization simply executes the code. We implemented CoDeSe in Java and performed a number of experiments on deserialization of states. CoDeSe provides on average more than 6X speedup over the highly optimized deserialization from the standard Java library. Our new format also allows simple parallel deserialization that can provide additional speedup on top of the sequential CoDeSe but only for larger states.

We describe a new system for building Tablet PC-based classroom software. The system, called SLICE, is built for extensibility, using a unique "explicit state" model.

Even after taking numerous programming courses, many students have poor programming skills. This is a problem not only in their post-graduation employment, but even in the higher-level Computer Science courses, where large programs are routinely assigned. Yet, teaching programming skills is expensive; like teaching writing, it can only be accomplished by a repeated cycle of writing, getting informed feedback, and rewriting. In this paper, we describe a computer science course designed around the concept of a studio course like those used in art and architecture. Its key elements are practice, public presentation, and review by peers in a small group. We discuss our experience in teaching the course for two years. We believe this course can be replicated and taught, at reasonable cost, even in large CS departments.

Program generators are most naturally specified using a quote/antiquote facility; the programmer writes programs with holes which are filled in, at program generation time, by other program fragments. If the programs are generated at compile-time, analysis and compilation follow generation, and no changes in the compiler are needed. However, if program generation is done at run time, compilation and analysis need to be optimized so that they will not overwhelm overall execution time. In this paper, we give a compositional framework for defining program analyses which leads directly to a method of staging these analyses. The staging allows the analysis of incomplete programs to be started at compile time; the residual work to be done at run time may be much less costly than the full analysis. We give frameworks for forward and backward analyses, present several examples of specific analyses, and give timing results showing significant speed-ups for the run-time portion of the analysis relative to the full analysis.

This paper describes Scavenger Hunt, a team-based orientation activity for incoming freshmen in the Department of Computer Science at the University of Illinois at Urbana-Champaign. Like many large research universities, Illinois has struggled with the high attrition rate of first-year students in computing disciplines. Scavenger Hunt, which has been held each of the past three years, is intended to foster a sense of community within the department and acclimate new students to undergraduate life as computer science majors. A unique aspect of the activity is the use of handheld computers to manage most aspects of the competition, which enables physically handicapped students to participate on an equal footing with their able-bodied peers. Thus far, Scavenger Hunt has been directly responsible for the increased participation of new students in departmental activities and organizations. In addition, we have observed a significant correlation between student participation in Scavenger Hunt and retention rates in the department. Along with other retention-oriented activities, Scavenger Hunt is measurably improving the attitude of new students towards computer science.

Established as a research project at the University of Illinois in the spring of 2002, eFuzion has proven to be a valuable and effective pedagogical set of tools. It provides the capacity to both mentor and assess students individually, both during and outside of class. In the summer of 2002, a study we conducted revealed that eFuzion's in-class tools increased student's final grade by more than 6 points. In this paper we describe the evolution of our system and experiences leading up to our "Classroom of the Future" demo for the Grand Opening of the Thomas M. Siebel Center for Computer Science. We conclude with a discussion of our future plans for eFuzion.

Programmers frequently write program generators using the simple model of programs as text. The essence of this approach is its lack of structure. For this reason, it gets no respect from academic researchers. But the flip side of lacking structure is freedom from restrictions. We argue that the latter is important, and perhaps essential, in finding a willing audience for program generation among working programmers. Jumbo is a system for producing run-time program generators, which is designed to offer the programmer a "programs as strings" model to as great an extent as possible, though some constraints are inevitable. We show by several examples that these constraints still allow for both a natural and a powerful program generation model. We then discuss how the approach taken by Jumbo, though possessing less structure than some competing methods, still raises scientific problems that ought to be of interest to researchers in this area.

Run-time code generation is a well-known technique for improving the efficiency of programs by exploiting dynamic information. Unfortunately, the difficulty of constructing run-time code-generators has hampered their widespread use. We describe Jumbo, a tool for easily creating run-time code generators for Java. Jumbo is a compiler for a two-level version of Java, where programs can contain quoted code fragments. The Jumbo API allows the code fragments to be combined at run-time and then executed. We illustrate Jumbo with several examples that show significant speedups over similar code written in plain Java, and argue further that Jumbo is a generalized software component system.

The Java .class file is a compact encoding of programs for a stack-based virtual machine. It is intended for use in a networked environment, which requires machine independence and minimized consumption of network bandwidth. However, as in all interpreted virtual machines, performance does not match that of code generated for the target machine. We propose verifiable, machine-independent annotations to the Java class file to bring the quality of the code generated by a ‘just-in-time’ compiler closer to that of an optimizing compiler without a significant increase in code generation time. This division of labor has expensive machine-independent analysis performed off-line and inexpensive machine-dependent code-generation performed on the client. We call this phenomenon ‘super-linear analysis and linear exploitation.’ These annotations were designed mindful of the concurrency features of the Java language. In this paper we report results from our machine-independent, prioritized register assignment. We also discuss other possible annotations. Copyright © 2000 John Wiley & Sons, Ltd.

A denotational semantic definition of SMALLTALK-80 is given. Its most notable characteristic is a surprisingly simple treatment of inheritance. An executable version of the semantics, written in STANDARD ML, is also described.

We present an overview of the FASE system for executable specifications based upon final, rather than initial, algebras. Particular emphasis is placed upon the execution of expressions involving quantifiers. The need for such expressions is explained, as is our method for evaluating them. By permitting quantifiers, we are able to give very natural specifications for many data types. As an example, we give the FASE specification of Kemmerer's library system.

A data type specification is a description of the properties of a data abstraction for the benefit of its users and implementers.The data abstraction has realizations, all of which behave in a certain way.It is those properties implied by this behavior which we consider essential; properties specific to some realization are extraneous.The specification problem is to present all of the essential properties and no extraneous ones.We propose a specification method based upon the notion of "final data type."A final data type is the smallest structure having a given behavior; every other structure having that behavior maps onto it homomorphically.This property makes the final data type specification a particularly good source of information about the abstraction it realizes, and eliminates "implementation bias" from the method.

A new specification method for data types is presented, which is distinguished by the semantic objects it specifies. In particular, only final data types [GGM,W] are specifiable. A final data type is one in which no two elements are "input-output equivalent". It is argued that the mathematical properties of final data types characterize abstractness on the semantic level.Examples are given to show that final data type specifications are easy to construct and use.

A sunple programming language ffm IS defined for which a complete axiomatics is obtamable.Completeness is shown by presemmg a relauvely complete Hoare ax~omaUcs, demonstrating, by direct constmcuon, that the first-order theory of addmon ~+ as express,ve, and noting that ~+ Is complete.It is then shown that • ~m aS maxunal wath this property Further, a notton of complexity of a Hoare system is introduced based upon the lengths of proofs (dasregardmg proofs m the underlying logsc), and the system -~m, .~+ is shown to have polynomial complexity The nouon ts shown to be nontnvlal by presenting a language for which any Hoare axiom system has exponenual complextty rK~v WORDS AND PHRASES venficatmn, logic, complexity, theory of computation, programming languages, subrecurslve functions CR CATEGORIES' 5 21, 5 24, 5 25

Article A complete and consistent hoare axiomatics for a simple programming language Share on Authors: J. Cherniavsky SUNY at Stony Brook, N.Y. SUNY at Stony Brook, N.Y.View Profile , S. Kamin SUNY at Stony Brook, N.Y. SUNY at Stony Brook, N.Y.View Profile Authors Info & Claims POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1977 Pages 1–9https://doi.org/10.1145/512950.512951Online:01 January 1977Publication History 3citation179DownloadsMetricsTotal Citations3Total Downloads179Last 12 Months21Last 6 weeks0 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