This paper introduces the PrairieLearn Question Sharing System (PQSS), which enables instructors to share question generators with other instructors, either as open educational resources or privately. PQSS is integrated into PrairieLearn, an open-source, problem-driven online learning platform. PQSS addresses a critical need for more open-source assessments by making it easier for instructors to share assessments and for instructors to use those assessments. Instructors often do not share questions due to the time it takes to publish them and the lack of recognition for their work. Because it is directly integrated into PrairieLearn, PQSS reduces the aforementioned friction of sharing and using shared questions, and we can report usage statistics to help question authors receive recognition for their work. In this paper, we share design and implementation details of the system, as well as experiences using it to share course content across courses and between universities.

Reading and understanding code are fundamental skills for novice programmers, and especially important with the growing prevalence of AI-generated code and the need to evaluate its accuracy and reliability. ''Explain in Plain English'' questions are a widely used approach for assessing code comprehension, but providing automated feedback, particularly on comprehension levels, is a challenging task. This paper introduces a novel method for automatically assessing the comprehension level of responses to ''Explain in Plain English'' questions. Central to this is the ability to distinguish between two response types: multi-structural, where students describe the code line-by-line, and relational, where they explain the code's overall purpose. Using a Large Language Model (LLM) to segment both the student's description and the code, we aim to determine whether the student describes each line individually (many segments) or the code as a whole (fewer segments). We evaluate this approach's effectiveness by comparing segmentation results with human classifications, achieving substantial agreement. We conclude with how this approach, which we release as an open source Python package, could be used as a formative feedback mechanism.

''Explain in Plain English'' (EiPE) questions are widely used to assess code comprehension skills but are challenging to grade automatically. Recent approaches like Code Generation Based Grading (CGBG) leverage large language models (LLMs) to generate code from student explanations and validate its equivalence to the original code using unit tests. However, this approach does not differentiate between high-level, purpose-focused responses and low-level, implementation-focused ones, limiting its effectiveness in assessing comprehension level. We propose a modified approach where students generate function names, emphasizing the function's purpose over implementation details. We evaluate this method in an introductory programming course and analyze it using Item Response Theory (IRT) to assess the difficulty and discrimination of function naming exercises as exam items and to compare their alignment with traditional EiPE grading standards. We also publish this work as an open source Python package for auto-grading EiPE questions, providing a scalable solution for adoption.

Computerized exams have benefits for large enrollment courses and computer science classes, specifically. In this research paper, we compare student self-reported test anxiety between two modes of administering computerized exams: a computer-based testing facility (CBTF) and a bring-your-own-device (BYOD) setup. We conducted crossover design experiments in two computer science courses, measuring trait anxiety, as well as students' test anxiety and their test performance after each exam.

Novice programmers often struggle to develop computational thinking (CT) skills in introductory programming courses. This study investigates the use of Large Language Models (LLMs) to provide scalable, strategy-driven feedback to teach CT. Through think-aloud interviews with 17 students solving code comprehension and writing tasks, we found that LLMs effectively guided decomposition and program development tool usage. Challenges included students seeking direct answers or pasting feedback without considering suggested strategies. We discuss how instructors should integrate LLMs into assessments to support students' learning of CT.

Alternative grading practices, such as specifications grading, have been reported to increase student engagement, decrease instructor workload, and ensure a minimum mastery of all course topics. However, there are also reports of decreased student learning and there have been few comparisons between different policies. In this experience report, we explore the effects of adopting different types of specifications grading systems in a project-based Embedded Systems course taught at a South American institution. We tested three different grading policies for exams in three different course offerings, varying both the number of times mastery needed to be demonstrated and whether exams specified two (pass/fail) or five (I, D, C, B, A) proficiency levels. For each policy, we list potential problems we were trying to address and evaluate how the change impacted the course. We use a mixed-methods approach to do a retrospective analysis, focusing on three aspects: (i)exam attendance and pass rates,(ii) grades on labs and projects and, (iii) student perceptions. We find that attendance remains high and pass rates increase with the pass/fail model. Also, lab and project grades decrease after students receive a passing grade in the first exam, indicating a possible decrease in engagement with the course. In terms of student perception, students described a mix of procrastination, low engagement with the course, and a desire to learn and create a challenging project. Finally, we discuss how we believe these findings could be used to increase engagement and learning.

Delivery of affordable, secure, and scalable assessments is an essential component of large university courses, whether online or in-person. The transition to Computer-Based Testing (CBT) has a transformational effect on pedagogy. Modern CBT systems provide almost unlimited flexibility in the types of questions they can support for manual grading and autograding. In this BoF, faculty interested in learning about various components of CBT and how to implement it at their institution are invited to ask their questions and learn from others who have already done this. To facilitate these discussions, in this BOF we will break into four smaller groups to discuss CBT pedagogy, building and sharing question banks, technical or logistical considerations, and building buy-in from all levels of the institution.

Code-reading ability has traditionally been under-emphasized in assessments as it is difficult to assess at scale. Prior research has shown that code-reading and code-writing are closely related skills; thus being able to assess and train code reading skills may be necessary for student learning. One way to assess code-reading ability is using Explain in Plain English (EiPE) questions, which ask students to describe what a piece of code does with natural language. Previous research deployed a binary (correct/incorrect) autograder using bigram models that performed comparably with human teaching assistants on student responses. With a dataset of 3,064 student responses from 17 EiPE questions, we investigated multiple autograders for EiPE questions. We evaluated methods as simple as logistic regression trained on bigram features, to more complicated Support Vector Machines (SVMs) trained on embeddings from Large Language Models (LLMs) to GPT-4. We found multiple useful autograders, most with accuracies in the \(86\!\!-\!\!88\%\) range, with different advantages. SVMs trained on LLM embeddings had the highest accuracy; few-shot chat completion with GPT-4 required minimal human effort; pipelines with multiple autograders for specific dimensions (what we call 3D autograders) can provide fine-grained feedback; and code generation with GPT-4 to leverage automatic code testing as a grading mechanism in exchange for slightly more lenient grading standards. While piloting these autograders in a non-major introductory Python course, students had largely similar views of all autograders, although they more often found the GPT-based grader and code-generation graders more helpful and liked the code-generation grader the most.

Background: Previous work has shown that students can understand more complicated pieces of code through the use of common software development tools (code execution, debuggers) than they can without them.

Background: In CS1 courses, Parsons problems are a popular activity in which students are given blocks of code and asked to rearrange them into the correct order. Parsons problems often include incorrect blocks of code referred to as distractor blocks. Despite their widespread use, there have been few investigations into how distractor blocks impact student learning. Objectives: Our goals are to understand (1) the impact that including distractor blocks in Parsons problems has on learning and (2) the causality underlying that learning, if any. Methods: In this paper, we present the results of an explanatory sequential mixed methods study investigating the impact of distractor blocks on student learning. For the initial, quantitative stage, we use a randomized control trial to quantify the learning outcomes from practice with Parsons problems that include distractor blocks, as measured via post-test taken immediately after the practice activity and a retention test taken a week later. This study is followed by think-aloud interviews with 10 students practicing using a mix of Parsons problems that do and do not contain distractors to understand differences in how students approach those problems. Findings: Our findings show that students who practiced using Parsons problems that contained distractors performed 11 percentage points better on the immediate post-test (statistically significant) and 10 percentage points better on the retention test (approaching significance). The results of the think-aloud interviews indicate that grouping distractors with blocks of correct code causes students to more closely attend to the details of the code within those blocks. Implications: The results of this study indicate that distractors are essential when Parsons problems are used in a formative context. When they are not included, students may be able to successfully place blocks of code without attending to details of the code. This in turn limits their ability to learn new concepts or reinforce existing knowledge from those code blocks.

In this paper, we explore three different methods for administering computer-based tests at scale: (1) a dedicated Computer-Based Testing Center (CBTC), (2) Bring Your Own Device (BYOD) exams proctored in person in the classroom, and (3) BYOD exams proctored online via Zoom. We conducted two randomized crossover experiments to compare pairs of modalities against each other (CBTC vs BYOD-in-person and CBTC vs BYOD-online). We found that testing modality did not impact students' exam performance or students' preparation before exams. However, we observed that students preferred the modalities in which they had recently received the highest scores. Our results indicate that several different modalities can be effectively used to administer testing at scale for CS courses.

Developing embedded microcontroller code is a complex task, especially for undergrad students new to this area. These students often make high-level conceptual mistakes beyond the scope of commercial standards like MISRA-C. These conceptual errors need to be checked manually through code feedback, a process that is time-consuming, error-prone, and does not scale well with an increasing number of students and/or assignments. In this paper, we present an embedded-check an automated tool that can detect common and critical errors students make when learning to code firmware. A set of 13 rules (baremetal and FreeRTOS) was devised based on our experience from several years of teaching Embedded systems. To validate our tool, we compared its results with manual code review of N=99 projects from the last 3 course offerings. We furthered our analysis by running our tool on N=1132 coding lab submissions that did not receive manual feedback and were used as part of classroom activities. We found that the top-3 errors flagged in the projects were already present when students completed the lab activities. We found that (i) our tool also identified all issues discovered during manual code feedback, (ii) our tool detected issues in 86% of student submissions, whereas manual code feedback only flagged 28% of the submissions as problematic, and (iii) 94.3% of students made some code quality error on individual assignments. Within this results, we believe that our tool can have a significant impact when used both as an formative assessment tool to support learning and as a learning analytics tool to improve teaching.

Small, auto-gradable programming exercises provide a useful tool with which to assess students' programming skills in introductory computer science. To reduce the time needed to produce programming exercises of similar difficulty, previous research has applied a permutation strategy to existing questions. Prior work has left several open questions: is prior exposure to a question typically indicative of higher student performance? Are observed changes in difficulty due to the specific surface feature permutations applied? How is student performance impacted by the first version of a question to which they may be exposed?

Comprehending and conveying the purpose of code is often cited as being a key learning objective within introductory programming courses. To address this objective, "Explain in Plain English'' questions, where students are shown a segment of code and asked to provide an abstract description of the code's purpose, have been adopted. However, given EiPE questions require a natural language response, they often require manual grading which is time-consuming for course staff and delays feedback for students. With the advent of large language models (LLMs) capable of generating code, responses to EiPE questions can be used to generate code segments, the correctness of which can then be easily verified using test cases. We refer to this approach as "Code Generation Based Grading'' (CGBG) and in this paper we explore its agreement with human graders using EiPE responses from past exams in an introductory programming course taught in Python. Overall, we find that all CGBG approaches achieve moderate agreement with human graders with the primary area of disagreement being its leniency with respect to low-level and line-by-line descriptions of code.

Background: ChatGPT became widespread in early 2023 and enabled the broader public to use powerful generative AI, creating a new means for students to complete course assessments.

To address the challenges of running exams in large enrollment CS courses, we set up and operated an in-person testing center at a minority serving institution. We have run the testing center for two quarters, proctoring over 6,000 exams for eight CS courses with approximately 1,800 students. In this experience report, we discuss the motivation for the testing center, its set-up and operation, and the lessons that we have learned from our first two quarters of operation. In addition, we present student and instructor feedback regarding use of the testing center, future steps, and improvements.

Affordable, secure, and scalable assessment delivery is an essential component of large university courses, whether online or in-person. The switch to Computer-Based Testing (CBT) can have a surprising, and almost transformational effect on pedagogy. Modern CBT systems provide almost unlimited flexibility in the types of questions they can support, for both manual grading and autograding, and CBT has now been adopted at several universities and is under serious consideration at others. In this BoF, faculty interested in learning about CBT and how to implement it at their institution are invited to ask their questions. Faculty experienced with CBT are invited to share how CBT has changed their approach, pedagogy, and behavior and how to advocate for its adoption.

We compare the exam security of three proctoring regimens of Bring-Your-Own-Device, synchronous, computer-based exams in a computer science class: online un-proctored, online proctored via Zoom, and in-person proctored. We performed two randomized crossover experiments to compare these proctoring regimens. The first study measured the score advantage students receive while taking un-proctored online exams over Zoom-proctored online exams. The second study measured the score advantage of students taking Zoom-proctored online exams over in-person proctored exams. In both studies, students took six 50-minute exams using their own devices, which included two coding questions and 8--10 non-coding questions. We find that students score 2.3% higher on non-coding questions when taking exams in the un-proctored format compared to Zoom proctoring. No statistically significant advantage was found for the coding questions. While most of the non-coding questions had randomization such that students got different versions, for the few questions where all students received the same exact version, the score advantage escalated to 5.2%. From the second study, we find no statistically significant difference between students' performance on Zoom-proctored vs. in-person proctored exams. With this, we recommend educators incorporate some form of proctoring along with question randomization to mitigate cheating concerns in BYOD exams.

Allowing students to re-attempt assessments has been shown to be effective in traditional university-level courses in improving student mastery of course content. In this paper, we analyse an intensive programming introductory experience, where first semester university students' full load is a single semester-long course that teaches the basics of programming and software engineering. We study its use of mastery-based grading: offering five (formative) low-stakes quizzes (with retakes), each focused on a single topic, and five (summative) higher-stakes exams that assess all learning objectives. Our research questions are: (i) ''Do second chances help students to increase their performance over time in intensive courses?''; and (ii) ''Are second chances effective in reducing stress/mental load/weight of assessments in intensive courses?''. We find that (i) offering second chances on quizzes decreases the number of students at risk of failing before the first exam; (ii) students' proficiency in coding tasks (as measured by exam grades) improve during the semester; and (iii) that our schedule reduces anxiety and mental load for students, but only after students take the first chance.

The ability of students to ''Explain in Plain English'' (EiPE) the purpose of code is a critical skill for students in introductory programming courses to develop. EiPE questions serve as both a mechanism for students to develop and demonstrate code comprehension skills. However, evaluating this skill has been challenging as manual grading is time consuming and not easily automated. The process of constructing a prompt for the purposes of code generation for a Large Language Model, such OpenAI's GPT-4, bears a striking resemblance to constructing EiPE responses. In this paper, we explore the potential of using test cases run on code generated by GPT-4 from students' EiPE responses as a grading mechanism for EiPE questions. We applied this proposed grading method to a corpus of EiPE responses collected from past exams, then measured agreement between the results of this grading method and human graders. Overall, we find moderate agreement between the human raters and the results of the unit tests run on the generated code. This appears to be attributable to GPT-4's code generation being more lenient than human graders on low-level descriptions of code.

Training the growing number of Computer Science Education (CSEd) PhD students is a pressing concern for our community. To meet the needs of our CSEd PhD students at University of Illinois Urbana-Champaign, we have developed a new course designed to strengthen students’ foundation in relevant fields. Through a collaborative process, we developed a reading list that covers the educational theory and perspectives that most inform our own work, as well as concepts that prepare our graduates to engage with the broader CSEd community.

No abstract available.

Background: Prior work has primarily been concerned with identifying: (1) how Open Education Resources (OERs) can be used to increase the availability of educational materials, (2) what motivations are behind their adoption and usage in classrooms, and (3) what barriers impede said adoption. However, there is relatively little work investigating the motives and barriers to contribution in OER.

Background and context. “Explain in Plain English” (EiPE) questions ask students to explain the high-level purpose of code, requiring them to understand the macrostructure of the program’s intent. A lot is known about techniques that experts use to comprehend code, but less is known about how we should teach novices to develop this capability.

Errors in AI grading and feedback often have an intractable set of causes and are, by their nature, difficult to completely avoid. Since inaccurate feedback potentially harms learning, there is a need for designs and workflows that mitigate these harms. To better understand the mechanisms by which erroneous AI feedback impacts students’ learning, we conducted surveys and interviews that recorded students’ interactions with a short-answer AI autograder for “Explain in Plain English” code reading problems. Using causal modeling, we inferred the learning impacts of wrong answers marked as right (false positives, FPs) and right answers marked as wrong (false negatives, FNs). We further explored explanations for the learning impacts, including errors influencing participants’ engagement with feedback and assessments of their answers’ correctness, and participants’ prior performance in the class.

In recent years Parsons problems have grown in popularity as both a pedagogical tool and as an assessment item alike. In these problems, students are expected to take existing but jumbled blocks of code and organize them to form a working solution. It is common for these problems to include incorrect blocks of code, typically referred to as "distractors," alongside the correct blocks. However, the utility of these distractors and their impact on a problems difficulty has yet to be thoroughly investigated. This study contributes to filling this gap by comparing performance, time spent, and item discrimination statistics for 32 pairs of Parsons problems from CS1 Python exams and quizzes. Our findings indicate that the inclusion of distractors has a large impact on the amount of time students spend on the questions and a low to moderate impact on score. Additionally, problems without distractors were already found to have high discrimination and including distractors did little to improve their discrimination. These findings suggest that the inclusion of distractors does little to improve the quality of these problems as exam questions but may have a negative impact on students by causing them to spend significantly more time on the problems and reducing the time they have for the rest of the exam.

"A's for All (as time and interest allow)" is a position that says it is increasingly possible to aim for a world in which students can achieve any grade (level of mastery) that they are willing to work for, even if some students take longer than others or require more practice to get there. Achieving this goal would have profound effects on fairness, equity, and participation in computing, to say nothing of student learning outcomes. We describe what this goal would entail, why it is worth pursuing, what the mechanism and policy requirements are for making progress, and why now is a good time to do it. We give specific and actionable recommendations, many based on our own experience so far, that our colleagues who are excited about the approach can put into immediate practice, and address a number of concerns and objections that our proposal may raise. Importantly, our proposed approach is not all-or-nothing, but all-or-something: there are many things instructors can do within existing policy frameworks and course constraints to move their course experience in this direction.

In recent years, a diverse body of research in computing education has discussed new pedagogies and curriculum changes to improve learning and students' experiences. Topics such as growth mindset, mastery learning, grading for equity, and specifications grading are important steps towards the Holy Grail: "A's for All" (as time and interest allow). In this new teaching approach, the "A" line does not move, but instead every student is given an opportunity to achieve proficiency and earn it, as long as they are willing to put in the time and effort it takes. In other words, students can all achieve the same learning outcomes at a different pace, instead of the traditional approach where students achieve different learning outcomes in a fixed amount of time. This workshop will provide educators and administrators with tools to implement the "A's for All" (as time and interest allow) approach in their courses and institutions. It will take attendees through elements of advocacy, hands-on randomized question generator design and implementation using a computer-based assessment system, best practices, and course policies to reduce friction.

To recognize the current and future trends and challenges in computer science education educational materials for the next decade, the authors of this work provide a conversation to voice the computer science community's experience and expertise on these trends. One of the biggest challenges for introductory computing courses in the next few years will be leveraging the new capabilities of Artificial Intelligent systems such as Open AI CodeX and GPT3 that can generate code from a textual description, explain code, and translate code between programming languages. These tools could drastically change how introductory programming is taught by allowing students to focus more on understanding code, modifying code, and testing code than on writing code. Learning content is increasingly shifting from paper textbooks to online learning systems, which include not just traditional text and figures, but increasingly use interactive items to provide students with better explanations and illustrations, extensive practice, and frequent immediate formative feedback, typically at a lower cognitive load than classical programming assignment. We will discuss challenges and opportunities for interoperability with publishing and learning management platforms. Another example is how guided-based instruments, such as peer team learning, open educational resources, or workbooks, are adaptive and hybrid according to students' needs.

Explain in Plain English (EiPE) questions evaluate whether students can understand and explain the high-level purpose of code. We conducted a qualitative think-aloud study of introductory programming students solving EiPE questions. In this paper, we focus on how students use tracing (mental execution) to understand code in order to explain it.

PrairieLearn is an open source, extensible online assessment platform built on modern web technologies. In this workshop, we will focus on how PrairieLearn can be used to improve student learning in undergraduate computer science classes. However, the platform is also more than suitable for use as an assessment engine in a variety of courses including the humanities, social, physical, and life sciences. In the first part of the workshop, we will showcase multiple question styles that highlight PrairieLearn's abilities as an online platform, including deploying automatically and manually graded questions at scale in large classes. In the second part of the workshop, we will discuss the anatomy of a PrairieLearn question, create several custom questions, and design assessments in PrairieLearn. In the third part, we will share strategies on adopting PrairieLearn at your institution. In particular, how algorithmically generated questions can be used in support of alternative grading schemes such as Mastery- or Specifications-Grading. Finally, we will share how PrairieLearn can be extended to support other coding languages and paradigms with custom and external autograders. There will be plenty of opportunities for questions throughout the workshop, and we intend to leave plenty of time for additional 1:1 support and training. Attendees will be able to attend the session virtually and are recommended to bring a web-connected computing device. By the end of the session, attendees will know enough to run a whole class on PrairieLearn including designing questions appropriate for homework, labs, and tests.

We conducted an across-semester quasi-experimental study that compared students' outcomes under frequent and infrequent testing regimens in an introductory computer science course. Students in the frequent testing (4 quizzes and 4 exams) semester outperformed the infrequent testing (1 midterm and 1 final exam) semester by 9.1 to 13.5 percentage points on code writing questions.

In this paper, we make three contributions related to the selection and use of distractors (lines of code reflecting common errors or misconceptions) in Parsons problems. First, we demonstrate a process by which templates for creating distractors can be selected through the analysis of student submissions to short answer questions. Second, we describe the creation of a tool that uses these templates to automatically generate distractors for novel problems. Third, we perform a preliminary analysis of how the presence of distractors impacts performance, problem solving efficiency, and item discrimination when used in summative assessments. Our results suggest that distractors should not be used in summative assessments because they significantly increase the problem's completion time without a significant increase in problem discrimination.

In technical writing, certain statements must be written very carefully in order to clearly and precisely communicate an idea. Students are often asked to write these statements in response to an open-ended prompt, making them difficult to autograde with traditional methods. We present what we believe to be a novel approach for autograding these statements by restricting students' submissions to a pre-defined context-free grammar (configured by the instructor). In addition, our tool provides instantaneous feedback that helps students improve their writing, and it scaffolds the process of constructing a statement by reducing the number of choices students have to make compared to free-form writing. We evaluated our tool by deploying it on an assignment in an undergraduate algorithms course. The assignment contained five questions that used the tool, preceded by a pre-test and followed by a post-test. We observed a statistically significant improvement from the pre-test to the post-test, with the mean score increasing from 7.2/12 to 9.2/12.

Assessment is critical for learning, and summative assessment (e.g., exams) is one aspect of teaching that can be hard to scale to the large enrollments common in lower division CS courses. In this demo, I'll share my experiences in developing and using the Computer-Based Testing Facility (CBTF) that has be in operation at the University of Illinois since 2014. The CBTF provides proctored, secure computer-based exams, making it well suited to assessment in large-enrollment courses in computer science and other STEM disciplines. In recent semesters, our CBTF has averaged more than 65,000 exams per semester for over 9,000 unique students.

This session takes inspiration from the highly successful "Nifty Assignments" special session, but instead highlights high quality multiple-choice questions that can be used for Peer Instruction. Peer Instruction is a pedagogical practice characterized by asking students to answer challenging, conceptual questions in class. For each question, students individually respond, discuss the question in small groups, and respond again based on their new understanding. Peer Instruction has been widely identified as an important instructional technique in teaching computing. In this session, members of the community will present some of their best Peer Instruction questions along with a short explanation that provides the pedagogical content knowledge indicating why the question is a good question. If you are interested in learning more about Peer Instruction or finding new questions for your course(s), this session is for you.

The SIGCSE-MEMBERS mailing list of the ACM Special Interest Group in Computer Science Education is the main forum for educators worldwide to discuss computing education research, pedagogy, and curriculum. In early 2022 it was abuzz with several connected movements: growth mindset, proficiency (aka mastery) learning, grading for equity, and specifications grading. Each of these is an important step toward the Holy Grail: A's for All (as time and interest allow); the "A" line doesn't move, but every student should be given an opportunity to achieve proficiency and earn it, as long as they are willing to put in the time and effort it might take. The mantra is not "fixed time, variable learning", but "fixed learning, variable time". The goal of this full-day workshop is to provide educators and administrators with tools to achieve it in their courses and institutions.

The SIGCSE-MEMBERS mailing list of the ACM Special Interest Group in Computer Science Education is the main forum for educators worldwide to discuss computing education research, pedagogy, and curriculum. In early 2022 it was abuzz with several connected movements: growth mindset, proficiency (aka mastery) learning, grading for equity, and specifications grading. Each of these is an important step toward the Holy Grail: A's for All (as time and interest allow); the "A" line doesn't move, but every student should be given an opportunity to achieve proficiency and earn it, as long as they are willing to put in the time and effort it might take. The mantra is not "fixed time, variable learning", but "fixed learning, variable time".

"Explain in plain English'' (EipE) questions have been proposed as an important activity and assessment for studying novice programmers' grasp of programming knowledge and their ability to communicate their understanding. However, EipE questions aren't widely used in introductory programming courses in part because of the large grading effort required. In this paper, we present our experience of using peer grading for EipE questions in a large-enrollment introductory programming course, where students were asked to categorize other students' responses. We developed a novel Bayesian algorithm for performing calibrated peer grading on categorical data, and we used a heuristic grade assignment method based on the Bayesian estimates. The peer-grading exercises served both as a way to coach students on what is expected from EipE questions and as a way to alleviate the grading load for the course staff. Based on four rounds of peer-grading activities, we found that students are generally capable of categorizing responses to EiPE questions and that our proposed Bayesian method is more robust than unweighted voting.

With the increase of large enrollment courses and the growing need to offer online instruction, computer-based exams randomly generated from question pools have a clear benefit for computing courses. Such exams can be used at scale, scheduled asynchronously and/or online, and use versioning to make attempts at cheating less profitable. Despite these benefits, we want to ensure that the technique is not unfair to students, particularly when it comes to equivalent difficulty across exam versions.

When students attempt to solve code-tracing problems, sometimes students make mistakes as they read code that get in the way of correctly solving the problem. In this paper, we explore the degree to which students can correct their misunderstandings by executing the provided code on a computer. Specifically, we performed a qualitative between-subjects think-aloud study to compare what kinds of errors students can resolve by just executing the code versus which they can resolve by using a line-by-line debugger.

Deployment of AI assessment tools in education is widespread, but work on students’ interactions and attitudes towards imperfect autograders is comparatively lacking. This paper presents students’ perceptions surrounding a ∼ 90% accurate automated short-answer grader that determined homework and exam credit in a college-level computer science course. Using surveys and interviews, we investigated students’ knowledge about the autograder and their attitudes.

This full research paper explores students' attitudes toward second-chance testing and how second-chance testing influences students' behavior. Second-chance testing refers to giving students the opportunity to take a second instance of each exam for some sort of grade replacement. Previous work has demonstrated that second-chance testing can lead to improved student outcomes in courses, but how to best structure second-chance testing to maximize its benefits remains an open question. We complement previous work by interviewing a diverse group of 23 students that have taken courses that use second-chance testing. From the interviews, we sought to gain insight into students' views and use of second-chance testing. We found that second-chance testing was almost universally viewed positively by the students and was frequently cited as helping to reduce test takers' anxiety and boost their confidence. Overall, we find that the majority of students prepare for second-chance exams in desirable ways, but we also note ways in which second-chance testing can potentially lead to undesirable behaviors including procrastination, overreliance on memorization, and attempts to game the system. We identified emergent themes pertaining to various facets of second-chance test-taking, including: 1) concerns about the time commitment required for second-chance exams; 2) a belief that second-chance exams promoted fairness; and 3) how second-chance testing incentivized learning. This paper will provide instructors and other stakeholders with detailed insights into students' behavior regarding second-chance testing, enabling instructors to develop better policies and avoid unintended consequences.

“Explain in plain English” (EipE) questions are seen as an important developmental activity and assessment tool in the research community studying how people learn to program, but they aren’t widely used in practice because of difficulty of grading and workload issues. In this paper, we interviewed eleven members of the introductory programming education research community about their thoughts on EipE questions as a whole and how individual borderline student answers should be graded. Through inductive coding of the interview transcripts, we identify: (1) themes relating to how EipE questions should be used in class, (2) the importance of training students to complete EipE questions, (3) standards for the selection and presentation of code in EipE questions, (4) the theoretical and practical considerations relating to grading EipE questions, and (5) English as a second language (ESL) concerns. In addition, we attempt to extrapolate from our observations what the underlying grading process is that faculty are using to grade EipE questions.

In this paper, we perform a comparative analysis using a within-subjects ‘think-aloud’ protocol of introductory programming students solving tracing problems in both paper-based and computer-based formats. We demonstrate that, on computer-based exams with compiler/interpreter access, students can achieve significantly higher scores on tracing problems than they do on similar paper-based questions, through brute-force execution of the provided code. Furthermore, we characterize the students’ usage of machine execution as they solve computer-based tracing problems.

Previous research suggests that "Explain in Plain English" (EiPE) code reading activities could play an important role in the development of novice programmers, but EiPE questions aren't heavily used in introductory programming courses because they (traditionally) required manual grading. We present what we believe to be the first automatic grader for EiPE questions and its deployment in a large-enrollment introductory programming course. Based on a set of questions deployed on a computer-based exam, we find that our implementation has an accuracy of 87-89%, which is similar in performance to course teaching assistants trained to perform this task and compares favorably to automatic short answer grading algorithms developed for other domains. In addition, we briefly characterize the kinds of answers that the current autograder fails to score correctly and the kinds of errors made by students.

Assessing student performance on programming questions is important for introductory computer science courses, both for student learning and for ensuring students demonstrate competence. Part of being a competent programmer includes the ability to transfer learning from solved to analogous problems. Additionally, particularly in computer-based and online assessment, mitigating cheating efforts is another important consideration. One way to mitigate cheating is by randomly selecting from large pools of equivalent questions. In order to produce large pools of questions quickly, we used a permutation strategy to rapidly make new question variants by altering existing questions' surface features. In this work, we present the results of our first set of surface feature permuted questions in an introductory Python course. We find surface feature permutations to be an effective way to produce questions of a similar difficulty to other new questions for students while mitigating potential cheating. However, we also see permutations expose potential student knowledge fragility and transfer concerns, as performance on permutations of homework questions is not strictly better than performance on questions that are entirely new on assessments

Expert programmers rarely think at the syntactic level. Instead, they think at higher levels of abstraction, mentally "chunking" groups of syntactic elements into a single abstraction. Explicitly teaching common "chunks" in early programming courses has been proposed in the research literature using the term "pattern-oriented instruction", but this practice appears not to be emphasized, nor is there a consensus about which patterns to teach or in what order.

Using multiple versions of exams is a common exam security technique to prevent cheating in a variety of contexts. While psycho-metric techniques are routinely used by large high-stakes testing companies to ensure equivalence between exam versions, such approaches are generally cost and effort prohibitive for individual classrooms. As such, exam versions practically present a tension between exam security (which is enhanced by the versioning) and fairness (which results from difficulty variation between versions).

We explore how course policies affect students' studying and learning when a second-chance exam is offered. High-stakes, one-off exams remain a de facto standard for assessing student knowledge in STEM, despite compelling evidence that other assessment paradigms such as mastery learning can improve student learning. Unfortunately, mastery learning can be costly to implement. We explore the use of optional second-chance testing to sustainably reap the benefits of mastery-based learning at scale. Prior work has shown that course policies affect students' studying and learning but have not compared these effects within the same course context. We conducted a quasi-experimental study in a single course to compare the effect of two grading policies for second-chance exams and the effect of increasing the size of the range of dates for students taking asynchronous exams. The first grading policy, called 90-cap, allowed students to optionally take a second-chance exam that would fully replace their score on a first-chance exam except the second-chance exam would be capped at 90% credit. The second grading policy, called 90-10, combined students' first- and second-chance exam scores as a weighted average (90% max score + 10% min score). The 90-10 policy significantly increased the likelihood that marginally competent students would take the second-chance exam. Further, our data suggests that students learned more under the 90-10 policy, providing improved student learning outcomes at no cost to the instructor. Most students took exams on the last day an exam was available, regardless of how many days the exam was available.

Proctoring educational assessments (e.g., quizzes and exams) has a cost, be it in faculty (and/or course staff) time or in money to pay for proctoring services. Previous estimates of the utility of proctoring (generally by estimating the score advantage of taking an exam without proctoring) vary widely and have mostly been implemented using an across subjects experimental designs and sometimes with low statistical power.

In this paper, we study a computerized exam system that allows students to attempt the same question multiple times. This system permits students either to receive feedback on their submitted answer immediately or to defer the feedback and grade questions in bulk. An analysis of student behavior in three courses across two semesters found similar student behaviors across courses and student groups. We found that only a small minority of students used the deferred feedback option. A clustering analysis that considered both when students chose to receive feedback and either to immediately retry incorrect problems or to attempt other unfinished problems identified four main student strategies. These strategies were correlated to statistically significant differences in exam scores, but it was not clear if some strategies improved outcomes or if stronger students tended to prefer certain strategies.

Previous research has identified the ability to read code and understand its high-level purpose as an important developmental skill that is harder to do (for a given piece of code) than executing code in one's head for a given input ("code tracing"), but easier to do than writing the code. Prior work involving code reading ("Explain in plain English") problems, have used a scoring rubric inspired by the SOLO taxonomy, but we found it difficult to employ because it didn't adequately handle the three dimensions of answer quality: correctness, level of abstraction, and ambiguity. In this paper, we describe a 7-point rubric that we developed for scoring student responses to "Explain in plain English'' questions, and we validate this rubric through four means. First, we find that the scale can be reliably applied with with a median Krippendorff's alpha (inter-rater reliability) of 0.775. Second, we report on an experiment to assess the validity of our scale. Third, we find that a survey consisting of 12 code reading questions had a high internal consistency (Cronbach's alpha = 0.954). Last, we find that our scores for code reading questions in a large enrollment (N = 452) data structures course are correlated (Pearson's R = 0.555) to code writing performance to a similar degree as found in previous work.

This paper presents the results of a controlled crossover experiment designed to measure the score advantage that students have when taking exams asynchronously (i.e., the students can select a time to take the exam in a multi-day window) compared to synchronous exams (i.e., all students take the exam at the same time). The study was performed in an upper-division undergraduate computer science course with 321 students. Stratified sampling was used to randomly assign the students to two groups that alternated between the two treatments (synchronous versus asynchronous exams) across a series of four exams during the semester. These non-programming exams consisted of a mix of multiple choice, checkbox, and numeric input questions. For some questions, the parameters were randomized so that students received different versions of the question and some questions were identical for all students. In our results, students taking the exams asynchronously had scores that were on average only 3% higher (0.2 of a standard deviation). Furthermore, we found that the score advantage was decreased by the use of randomized questions, and it did not significantly differ based on the type of question. Thus, our results suggest that asynchronous exams can be a compelling alternative to synchronous exams.

For the past five years we have been operating a Computer-Based Testing Facility (CBTF) as the primary means of summative assessment in large-enrollment STEM-oriented classes. In each of the last three semesters, it has proctored over 50,000 exams for over 6,000 unique students in 25–30 classes. Our CBTF has simultaneously improved the quality of assessment, allowed the testing of computational skills, and reduced the recurring burden of performing assessment in a broad collection of STEM-oriented classes, but it does require an up-front investment to develop the digital exam content. We have found our CBTF to be secure, cost-effective, and well liked by our faculty, who choose to use it semester after semester. We believe that there are many institutions that would similarly benefit from having a Computer-Based Testing Facility.

In this research category full paper, we present our findings on the effects of different course policies for second-chance testing on students' studying and exam taking behavior. Second-chance testing, where students are allowed to take a second instance of an exam for some form of grade replacement, is a less expensive approximation of mastery-based learning that can be easily integrated into a broad range of college course structures. It encourages students to review course material after poor performance on an examination but limits the amount of resources instructors must invest in the creation of examinations or in grading them. There exists, however, a large space of potential course policies for integrating second-chance testing into a course and little prior research on how these policies affect student behavior. This paper analyzes three different grading policies in use at Midwestern University. All of the policies attempt to encourage students to prepare adequately for the first-chance exam and review the material again before the second-chance exam, if they elect to take it. The first policy used a partial grade replacement policy with insurance: students' grades could only improve by taking the second-chance exam but the first-chance exam always counts for at least one-third of a students' grade on the examination. The second policy is identical, but required students to complete a zero-credit, online-homework assignment before being allowed to take the second-chance exam. The third policy implemented full grade replacement (even if the second score is lower) and capped the score that could be achieved on the second exam. By comparing these different course policies, we show that grading policies have a significant effect on whether students take second-chance exams. We also performed a quasi-experimental study, adding second-chance exams to a course. We present data from students' exam performance and from the course's learning management system that suggest that adding a second-chance exam had no effect on student performance or study habits for the first-chance exam. However, the total amount of time that students studied did increase substantially as students who took the second-chance exam studied an additional 60% of their original effort.

To design good assessments, it is useful to have an estimate of the difficulty of a novel exam question before running an exam. In this paper, we study a collection of a few hundred automatic item generators (short computer programs that generate a variety of unique item instances) and show that their exam difficulty can be roughly predicted from student performance on the same generator during pre-exam practice. Specifically, we show that the rate that students correctly respond to a generator on an exam is on average within 5% of the correct rate for those students on their last practice attempt. This study is conducted with data from introductory undergraduate Computer Science and Mechanical Engineering courses.

We describe uAssign, an assignment system for teaching and assessing command line terminal skills. uAssign allows instructors to create auto-graded terminal assignments that require students to perform a high-level action that can be completed in many ways. Assignments can be randomized so that students can't re-use old solutions. uAssign is implemented via an in-browser terminal emulator that uses WebSockets to connect to a Docker container. Performance testing and its use in a large-enrollment lecture course show that it is efficient enough to handle a large number of concurrent users. A survey of students shows significant improvement in terminal skill confidence after using uAssign and that students have a high level of satisfaction with uAssign assignments.

This Innovative Practice Full Paper describes lessons learned from and operational details of a full-scale Computer-Based Testing Facility (CBTF) over a period of almost 4 years. The CBTF has grown into a key resource for enabling the graceful scaling of many of the largest classes in our College of Engineering. In Fall 2017, the CBTF served 21 courses from seven different departments and over 6,000 unique students. Over 52,000 exams were delivered, including 3,500 final exams.This paper discusses five main aspects of our CBTF. First, we present the basic operation of the CBTF. Second, we discuss the precautions we take to maintain a secure exam environment. Third, we discuss how we support students that require testing accommodations like extra time and/or a distraction-reduced environment. Fourth, we discuss how we organize our policies to handle exceptional circumstances with minimal intervention by faculty. Finally, we discuss the cost of operating the CBTF and how it compares to traditional exams and online services.

This paper investigates randomization on asynchronous exams as a defense against collaborative cheating. Asynchronous exams are those for which students take the exam at different times, potentially across a multi-day exam period. Collaborative cheating occurs when one student (the information producer) takes the exam early and passes information about the exam to other students (the information consumers) that are taking the exam later. Using a dataset of computerized exam and homework problems in a single course with 425 students, we identified 5.5% of students (on average) as information consumers by their disproportionate studying of problems that were on the exam. These information consumers ("cheaters") had a significant advantage (13 percentage points on average) when every student was given the same exam problem (even when the parameters are randomized for each student), but that advantage dropped to almost negligible levels (2--3 percentage points) when students were given a random problem from a pool of two or four problems. We conclude that randomization with pools of four (or even three) problems, which also contain randomized parameters, is an effective mitigation for collaborative cheating. Our analysis suggests that this mitigation is in part explained by cheating students having less complete information about larger pools.

Many students underperform on exams due to experiencing high test anxiety. We report on a study comparing a novel intervention of seeking support from one's social network to the more common approaches of expressive writing and studying task-relevant materials for simulated open-ended test questions. We measured in-the-moment (state) anxiety before and after each intervention, and correctness of the solutions. We also surveyed students to learn about their perceptions of the interventions. Our results showed that social support decreased the anxiety of high test-anxious students by 21% with the reduction in anxiety correlating with the number of messages received. Social support also allowed high test-anxious students to score at the level of low test-anxious students. Expressive writing showed a similar effect, but increased the anxiety of low test-anxious students by 61%. Studying task materials had no effect on anxiety and high test-anxious students performed worse than low test-anxious students. Despite benefiting from social support, we found that students were uncomfortable soliciting support from their online social network. Realizing the benefits of this approach may therefore require different formulations of social support in practice.

Using a data set from 29,492 asynchronous exams in an on-campus proctored computer-based testing facility (CBTF), we observed correlations between when a student chooses to take their exam within the exam period and their score on the exam. Somewhat surprisingly, instead of increasing throughout the exam period, which might be indicative of widespread collaborative cheating, we find that exam scores decrease throughout the exam period. While this could be attributed to weaker students putting off exams, this effect holds even when accounting for student ability as measured by a synchronous exam taken during the same semester. This suggests that precautions can be taken by a CBTF to maintain cheating at a low level (e.g., the level of proctored synchronous exams), in spite of the fact that students are taking their exams over a multi-day period.

We analyzed 6 semesters of data from a large enrollment data structures course to identify instances of plagiarism in 4 assignments. We find that the majority of the identified plagiarism instances involve cross-semester cheating and are performed by students for whom the plagiarism is an isolated event (in the studied assignments). Second, we find that providing students an opportunity to work with a partner doesn't decrease the incidence of plagiarism. Third, while plagiarism on a given assignment is correlated with better than average scores on that assignment, plagiarism is negatively correlated with final grades in both the course that the plagiarism occurred and in a subsequent related course. Finally, we briefly describe the Algae open-source suite of plagiarism detectors and characterize the kinds of obfuscation that students apply to their plagiarized submissions and observe that no single algorithm appears to be sufficient to detect all of the cases.

When undergraduate students are allowed to choose a time slot in which to take an exam from a large number of options (e.g., 40), the students exhibit strong preferences among the times. We found that students can be effectively modelled using constrained discrete choice theory to quantify these preferences from their observed behavior. The resulting models are suitable for load balancing when scheduling multiple concurrent exams and for capacity planning given a set schedule.

While control speculation is highly effective for generating good schedules in out-of-order processors, it is less effective for in-order processors because compilers have trouble scheduling in the presence of unbiased branches, even when those branches are highly predictable. In this paper, we demonstrate a novel architectural branch decomposition that separates the prediction and deconvergence point of a branch from its resolution, which enables the compiler to profitably schedule across predictable, but unbiased branches. We show that the hardware support for this branch architecture is a trivial extension of existing systems and describe a simple code transformation for exploiting this architectural support. As architectural changes are required, this technique is most compelling for a dynamic binary translation-based system like Project Denver.

Indirect branches have historically been a challenge for microarchitectures and code generators alike. The recent steady increase in indirect branch predictability has translated into continual performance improvements especially for Out-of-Order processors which benefit more readily from improvements in branch prediction. In contrast, in-order processors which rely on code generators for performance are still challenged by indirect branches; they are a frequent source of issue stalls and the large number of indirect branch targets and unbiased nature of indirect branches complicate the use of traditional branch handling techniques like assert conversion and predication.

In this paper, we set out to study the performance advantages of an Out-of-Order (OOO) processor relative to in-order processors with similar execution resources. In particular, we try to tease apart the performance contributions from two sources: the improved sched- ules enabled by OOO hardware speculation support and its ability to generate different schedules on different occurrences of the same instructions based on operand and functional unit availability. We find that the ability to express good static schedules achieves the bulk of the speedup resulting from OOO. Specifically, of the 53% speedup achieved by OOO relative to a similarly provisioned in- order machine, we find that 88% of that speedup can be achieved by using a single "best" static schedule as suggested by observing an OOO schedule of the code. We discuss the ISA mechanisms that would be required to express these static schedules. Furthermore, we find that the benefits of dynamism largely come from two kinds of events that influence the application's critical path: load instructions that miss in the cache only part of the time and branch mispredictions. We find that much of the benefit of OOO dynamism can be achieved by the potentially simpler task of addressing these two behaviors directly.

The ability to reason with formal logic is a foundational skill for computer scientists and computer engineers that scaffolds the abilities to design, debug, and optimize. By interviewing students about their understanding of propositional logic and their ability to translate from English specifications to Boolean expressions, we characterized common misconceptions and novice problem-solving processes of students who had recently completed a digital logic design class. We present these results and discuss their implications for instruction and the development of pedagogical assessment tools known as concept inventories.

In this paper we evaluate the atomic region compiler abstraction by incorporating it into a commercial system. We find that atomic regions are simple and intuitive to integrate into an x86 binary-translation system. Furthermore, doing so trivially enables additional optimization opportunities beyond that achievable by a high-performance dynamic optimizer, which already implements superblocks.

A concept inventory (CI) is a standardized assessment tool that evaluates how well a student's conceptual framework matches the accepted conceptual framework of a discipline. In this paper, we present our process in creating and evaluating the alpha version of a CI to assess student understanding of digital logic. We have checked the validity and reliability of the CI through an alpha administration, follow-up interviews with students, analysis of administration results, and expert feedback. So far the feedback on the digital logic concept inventory is positive and promising.

A concept inventory is a standardized assessment tool intended to evaluate a student’s understanding of the core concepts of a topic. In order to create a concept inventory it is necessary to accurately identify these core concepts. A Delphi process is a structured multi-step process that uses a group of experts to achieve a consensus opinion. We present the results of three Delphi processes to identify topics that are important and difficult in each of three introductory computing subjects: discrete mathematics, programming fundamentals, and logic design. The topic rankings can not only be used to guide the coverage of concept inventories, but can also be used by instructors to identify what topics merit special attention.

Several recent processor designs have proposed to enhance performance by increasing the clock frequency to the point where timing faults occur, and by adding error-correcting support to guarantee correctness. However, such timing speculation (TS) proposals are limited in that they assume traditional design methodologies that are suboptimal under TS. In this paper, we present a new approach where the processor itself is designed from the ground up for TS. The idea is to identify and optimize the most frequently-exercised critical paths in the design, at the expense of the majority of the static critical paths, which are allowed to suffer timing errors. Our approach and design optimization algorithm are called BlueShift. We also introduce two techniques that, when applied under BlueShift, improve processor performance: on-demand selective biasing (OSB) and path constraint tuning (PCT). Our evaluation with modules from the OpenSPARC T1 processor shows that, compared to conventional TS, BlueShift with OSB speeds up applications by an average of 8% while increasing the processor power by an average of 12%. Moreover, compared to a high-performance TS design, BlueShift with PCT speeds up applications by an average of 6% with an average processor power overhead of 23% . providing a way to speed up logic modules that is orthogonal to voltage scaling.

In this work, we analyze the memory-intensive bioinformatics problem of ldquode novordquo DNA sequence assembly, which is the process of assembling short DNA sequences obtained by experiment into larger contiguous sequences. In particular, we analyze the performance scaling challenges inherent to de Bruijn graph-based assembly, which is particularly well suited for the data produced by ldquonext generationrdquo sequencing machines. Unlike many bioinformatics codes which are computation-intensive or control-intensive, we find the memory footprint to be the primary performance issue for de novo sequence assembly. Specifically, we make four main contributions: 1) we demonstrate analytically that performing error correction before sequence assembly enables larger genomes to be assembled in a given amount of memory, 2) we identify that the use of this technique provides the key performance advantage to the leading assembly code, Velvet, 3) we demonstrate how this pre-assembly error correction technique can be subdivided into multiple passes to enable de Bruijn graph-based assembly to scale to even larger genomes, and 4) we demonstrate how Velvet's in-core performance can be improved using memory-centric optimizations.

We propose a new instruction, branch-on-random, that is like a standard conditional branch, except rather than specifying the condition on which the branch should be taken, it specifies a frequency at which the branch should be taken. We show that branch-on-random is useful for reducing the overhead of program instrumentation, via sampling. Specifically, branch-on-random provides an order-of-magnitude reduction in execution time overhead compared to previously proposed software-only frameworks for instrumentation sampling.

We present a new approach to performing program analysis through profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.

In this work, we characterize a significant source of software derating that we call instruction-level derating. Instruction-level derating encompasses the mechanisms by which computation on incorrect values can result in correct computation. We characterize the instruction-level derating that occurs in the SPEC CPU2000 INT benchmarks, classifying it (by source) into six categories: value comparison, sub-word operations, logical operations, overflow/precision, lucky loads, and dynamically-dead values. We also characterize the temporal nature of this derating, demonstrating that the effects of a fault persist in architectural state long after the last time they are referenced. Finally, we demonstrate how this characterization can be used to avoid unnecessary error recoveries (when a fault will be masked by software anyway) in the context of a dual modular redundant (DMR) architecture.

A conceptually appealing approach to supporting a broad range of workloads is a system comprising many small cores that can be fused, on demand, into larger cores. We demonstrate that using in-order cores for this purpose, even under idealized assumptions about fusion-related overheads, would introduce fundamental obstacles to achieving good performance — obstacles that are not present when out-of-order cores are used. Matching the performance of modern dynamically-scheduled designs demands that a fused machine be able to simultaneously manage a large number of active dataflow chains, many more than the amount of ILP typically extracted from the code. When it is in-order cores that are fused, this requirement, in turn, demands either that the active dataflow chains be carefully interleaved among the available issue queues, or that enough cores be provided for them to reside at distinct queues. Using an abstract model for reasoning about the performance of these machines, we show that the former option is fundamentally hard, in the sense that it necessitates instruction steering hardware that would be too complex to build. The latter option would demand so many cores that the machine would be overwhelmed by fusion-related overheads. In short, if the goal is to match the performance of modern dynamically-scheduled machines, fusion of in-order cores is not a very compelling approach; either a fundamentally new method for fusing cores is needed, or some form of out-of-order capability must be provided at the constituent cores.

The ability to reason with formal logic is a foundational skill for computer scientists and computer engineers that scaffolds the abilities to design, debug, and optimize. By interviewing students about their understanding of propositional logic and their ability to translate from English specifications to Boolean expressions, we characterized common misconceptions and novice problem-solving processes of students who had recently completed a digital logic design class. We present these results and discuss their implications for instruction and the development of pedagogical assessment tools known as concept inventories.

We demonstrate how fine-grained memory protection can be used in support of transactional memory systems: first showing how a software transactional memory system (STM) can be made strongly atomic by using memory protection on transactionally-held state, then showing how such a strongly-atomic STM can be used with a bounded hardware TM system to build a hybrid TM system in which zero-overhead hardware transactions may safely run concurrently with potentially-conflicting software transactions. We experimentally demonstrate how this hybrid TM organization avoids the common-case overheads associated with previous hybrid TM proposals, achieving performance rivaling an unbounded HTM system without the hardware complexity of ensuring completion of arbitrary transactions in hardware. As part of our findings, we identify key policies regarding contention management within and across the hardware and software TM components that are key to achieving robust performance with a hybrid TM.

Transactional memory (TM) is a scalable and concurrent way to build atomic sections. One aspect of TM that remains unclear is how side-effecting operations – that is, those which cannot be transparently undone by a TM system – should be handled. This uncertainty poses a significant barrier to the general applicability and acceptance of TM. Further, the absence of transactional workloads makes it difficult to study this aspect In this paper, we characterize the usage of I/O, and in particular system calls, within critical sections in two large applications, exploring both the actions performed and the characteristics of the critical sections in which they are performed. Shared memory programs employing critical sections are the closest approximation available to transactional workloads, so using this characterization, we attempt to reason about how the behavior we observed relates to the previous proposals for handling side-effecting operations within transactions. We find that the large majority of syscalls performed within critical sections can be handled with a range of existing techniques in a way transparent to the application developer. We also find that while side-effecting critical sections are rare, they tend to be quite long-lasting, and that many of these critical sections perform their first syscall (and thus become side-effecting) relatively early in their execution. Finally, we show that while these long-lived, side-effecting critical sections tend to execute concurrently with many critical sections on other threads, we observe little concurrency between side-effecting critical sections.

A Delphi process is a structured multi-step process that uses a group of experts to achieve a consensus opinion. We present the results of three Delphi processes to identify topics that are important and difficult in each of three introductory computing subjects: discrete math, programming fundamentals, and logic design. The topic rankings can be used to guide both the coverage of standardized tests of student learning (i.e., concept inventories) and can be used by instructors to identify what topics merit emphasis.

Speculative compiler optimizations are effective in improving both single-thread performance and reducing power consumption, but their implementation introduces significant complexity, which can limit their adoption, limit their optimization scope, and negatively impact the reliability of the compilers that implement them. To eliminate much of this complexity, as well as increase the effectiveness of these optimizations, we propose that microprocessors provide architecturally-visible hardware primitives for atomic execution. These primitives provide to the compiler the ability to optimize the program's hot path in isolation, allowing the use of non-speculative formulations of optimization passes to perform speculative optimizations. Atomic execution guarantees that if a speculation invariant does not hold, the speculative updates are discarded, the register state is restored, and control is transferred to a non-speculative version of the code, thereby relieving the compiler from the responsibility of generating compensation code.

In this work, we present accordion arrays, a straight-forward and effective memory compression technique targeting Unicode-based character arrays. In many non-numeric Java programs, character arrays represent a significant fraction (30-40% on average) of the heap memory allocated. In many locales, most, but not all, of those arrays consist entirely of characters whose top bytes are zeros, and, hence, can be stored as byte arrays without loss of information. In order to get the almost factor of two compression rate for character vectors, two challenges must be overcome: 1) all code that reads and writes character vectors must dynamically determine which kind of array is being accessed and perform byte or character loads/stores as appropriate, and 2) compressed vectors must be dynamically inflated when an incompressible character is written. We demonstrate how these challenges can be overcome with minimal spaceand execution time overhead, resulting in an average speedup of 2% across our benchmark suite, with individual speedups as high as 8%.

Many word-based Software TransactionalMemory systems (STMs) have been proposed using tagless ownership tables, where read and write permissions are granted at the granularity of all addresses that map to a given ownership table entry. This optimization to reduce overhead potentially results in false conflicts. Using address traces from a multithreaded program, we demonstrate that the frequency of these false conflicts grows superlinearly with both the TM data footprint and concurrency and that increasing the size of the ownership table results in only a sub-linear reduction in conflict rate. These somewhat surprising relationships have a theoretical foundation that is also responsible for the (naively) unintuitive statistical result generally referred to as the "Birthday Paradox." We present an analytical model based on random population of an ownership table by concurrently executing transactions that correctly predicts the trends in measured data. These results call into question the viability of such an optimization that can undermine the scalability and concurrency claims of software transactional memory.

Hardware counters are a fundamental building block of modern high-performance processors. This paper explores two applications of probabilistic counter updates, in which the output of a pseudo-random number generator decides whether to perform a counter increment or decrement. First, we discuss a probabilistic implementation of counter hysteresis, whereby previously proposed branch confidence and criticality predictors can be reduced in size by factors of 2 and 3, respectively, with negligible impact on performance. Second, we build a frequency stratifier by making increment and decrement probabilities functions of the current counter value. The stratifier enables a 4-bit counter to classify an instruction's Likelihood of Criticality with sufficient accuracy to closely approximate the performance of an unbounded precision classifier. Because probabilistic updates are both simple and effective, we believe these ideas hold great promise for immediate use by industry, perhaps enabling the use of structures such as branch confidence predictors which may have previously been viewed as too expensive given their functionality.

Aggressive software speculation holds significant potential, because it enables program transformations to reduce the program's critical path. Like any form of speculation, however, the key to software speculation is employing it only where it is likely to succeed. While mechanisms for controlling hardware speculation (e.g., saturating counters updated after each instance) are well understood, these techniques do not translate directly to software techniques because changing a speculation requires changing the code. As it stands, the dominant software speculation control technique, non-reactive profile-guided optimization, lacks the robustness to support aggressive speculation. The primary thesis of this paper is that software speculation can be made to be robust by adding a reactive controller that can dynamically adjust the speculation. We make two primary observations about such systems: 1) reactive control systems can select behaviors on which to speculate with performance that equals or exceeds self-training, and 2) such control systems are remarkably latency tolerant. Although reactivity is required, it can be done at a low frequency; latencies of hundreds of thousands, or even millions of cycles, can be tolerated for most actions. Together these two characteristics imply that robust aggressive software speculation is a realistic goal.

Clustered machines partition hardware resources to circumvent the cycle time penalties incurred by large, monolithic structures. This partitioning introduces a long inter-cluster forwarding latency and the potential for load imbalance, both of which degrade IPC and thus counter the cycle time benefits of clustering. We show that program dataflow can be mapped to clustered machines so as to achieve an IPC rivaling that of an equivalent monolithic machine. That is, the IPC penalties observed by extant schemes are largely an artifact of instruction steering and scheduling policies. Using critical path analysis, we investigate and uncover the main causes for this performance loss. By way of code samples, we illustrate those causes and propose three policies for mitigating them. First, we introduce a new metric, likelihood of criticality, and show how it can halve the performance lost to contention-induced stalls. Second, we develop a stall-over-steer policy that addresses performance lost to inter-cluster forwarding delay. Finally, we show that a proactive load-balancing policy is necessary to improve the distribution of ready instructions among the clusters. Together, these three policies yield performance on 2-, 4- and 8-cluster implementations of an 8-wide machine that is within 2, 4, and 6%, respectively, of the monolithic equivalent.

This paper describes SPIMbot, an extension to James Larus's widely-used MIPS simulator SPIM, that allows virtual robots to be controlled by writing programs in the MIPS assembly language. SPIMbot was written to provide an engaging environment to motivate students to learn assembly language concepts. The SPIMbot tool allows the development of scenarios---in which students must program the robot to perform certain tasks---and provides the means to compete two robots against each other.In our sophomore/junior-level class, we structure the programming component as a collection of structured assignments that produce sub-components for the robot; these sub-components are then used in a final open-ended programming assignment to produce an entry for a SPIMbot tournament. In our experience, this has been an effective means of engaging students, with many students investing time to aggressively optimize their implementations. SPIMbot has been effectively used in large classes and its source code is freely available [7].

We present a technique for reducing the overhead of collecting path profiles in the context of a dynamic optimizer. The key idea to our approach, called targeted path profiling (TPP), is to use an edge profile to simplify the collection of a path profile. This notion of profile-guided profiling is a natural fit for dynamic optimizers, which typically optimize the code in a series of stages. TPP is an extension to the Ball-Lams efficient path profiling algorithm. Its increased efficiency comes from two sources: (i) reducing the number of potential paths by not enumerating paths with cold edges, allowing array accesses to be substituted for more expensive hash table lookups, and (ii) not instrumenting regions where paths can be unambiguously derived from an edge profile. Our results suggest that on average the overhead of profile collection can be reduced by half (SPEC95) to almost two-thirds (SPEC2000) relative to the Ball-Larus algorithm with minimal impact on the information collected.

Master/Slave Speculative Parallelization (MSSP) is an execution paradigm for improving the execution rate of sequential programs by parallelizing them speculatively for execution on a multiprocessor. In MSSP one processor - the master - executes an approximate version of the program to compute selected values that the full program's execution is expected to compute. The master's results are checked by slave processors that execute the original program. This validation is parallelized by cutting the program's execution into tasks. Each slave uses its predicted inputs (as computed by the master) to validate the input predictions of the next task, inductively validating the entire execution. The performance of MSSP is largely determined by the execution rate of the approximate program. Since approximate code has no correctness requirements (in essence it is a software value predictor), it can be optimized more effectively than traditionally generated code. It is free to sacrifice correctness in the uncommon case to maximize performance in the common case. A simulation-based evaluation of an initial MSSP implementation achieves speedups of up to 1.7 (harmonic mean 1.25) on the SPEC2000 integer benchmarks. Performance is currently limited by the effectiveness with which our current automated infrastructure approximates programs, which can likely be improved significantly.

Aggressive program optimization requires accurate profile information, but such accuracy requires many samples to be collected. We explore a novel profiling architecture that reduces the overhead of collecting each sample by including a programmable co-processor that analyzes a stream of profile samples generated by a microprocessor. From this stream of samples, the co-processor can detect correlations between instructions (e.g., memory dependence profiling) as well as those between different dynamic instances of the same instruction (e.g., value profiling). The profiler's programmable nature allows a broad range of data to be extracted, post-processed, and formatted, as well as provides the flexibility to tailor the profiling application to the program under test. Because the co-processor is specialized for profiling, it can execute profiling applications more efficiently than a general-purpose processor. The co-processor should not significantly impact the cost or performance of the main processor because it can be implemented using a small number of transistors at the chip's periphery We demonstrate the proposed design through a detailed evaluation of load value profiling. Our implementation quickly and accurately estimates the value invariance of loads, with time overhead roughly proportional to the size of the instruction working set of the program. This algorithm demonstrates a number of general techniques for profiling, including: estimating the completeness of a profile, a means to focus profiling on particular instructions, management of profiling resources.

A relatively small set of static instructions has significant leverage on program execution performance. These problem instructions contribute a disproportionate number of cache misses and branch mispredictions because their behavior cannot be accurately anticipated using existing prefetching or branch prediction mechanisms.

For many applications, branch mispredictions and cache misses limit a processor's performance to a level well below its peak instruction throughput. A small fraction of static instructions, whose behavior cannot be anticipated using current branch predictors and caches, contribute a large fraction of such performance degrading events. This paper analyzes the dynamic instruction stream leading up to these performance degrading instructions to identify the operations necessary to execute them early. The backward slice (the subset of the program that relates to the instruction) of these performance degrading instructions, if small compared to the whole dynamic instruction stream, can be pre-executed to hide the instruction's latency. To overcome conservative dependence assumptions that result in large slices, speculation can be used, resulting in speculative slices. This paper provides an initial characterization of the backward slices of L2 data cache misses and branch mispredictions, and shows the effectiveness of techniques, including memory dependence prediction and control independence, for reducing the size of these slices. Through the use of these techniques, many slices can be reduced to less than one tenth of the full dynamic instruction stream when considering the 512 instructions before the performance degrading instruction. 1

Common hardware exceptions, when implemented by trapping, unnecessarily serialize program execution in dynamically scheduled superscalar processors. To avoid the consequences of trapping the main program thread, multithreaded CPUs can exploit control and data independence by executing the exception handler in a separate hardware context. The main thread doesn't squash instructions after the excepting instruction, conserving fetch bandwidth and allowing execution of instructions independent of the exception. This leads to earlier branch resolution in the post exception code and additional memory latency tolerance. As a proof of concept, using threads to handle software TLB misses is shown to provide performance approaching that of an aggressive hardware TLB miss handler.

Haptic display is the process of applying forces to a human "observer" giving the sensation of touching and interacting with real physical objects. Touch is unique among the senses because it allows simultaneous exploration and manipulation of an environment. A haptic display system has three main components. The first is the haptic interface, or display device, generally some type of electro-mechanical system able to exert controllable forces on the user with one or more degrees of freedom. The second is the object model-a mathematical representation of the object containing its shape and other properties related to the way it feels. The third component, the haptic rendering algorithm, joins the first two components to compute, in real time, the model-based forces to give the user the sensation of touching the simulated objects. This paper focuses on a new haptic rendering algorithm for generating convincing interaction forces for objects modeled as rigid polyhedra. We create a virtual model of the haptic interface, called the god-object, which conforms to the virtual environment. The haptic interface can then be servo-ed to this virtual model. This algorithm is extensible to other functional descriptions and lays the groundwork for displaying not only shape information, but surface properties such as friction and compliance.

Haptic rendering is the process of computing and generating forces in response to user interactions with virtual objects. Recent efforts by our team at MIT's AI laboratory have resulted in the development of haptic interface devices and algorithms for generating the forces of interaction with virtual objects. This paper focuses on the software techniques needed to generate sensations of contact interaction and material properties. In particular, the techniques we describe are appropriate for use with the Phantom haptic interface, a force generating display device developed in our laboratory. We also briefly describe a technique for representing and rendering the feel of arbitrary polyhedral shapes and address issues related to rendering the feel of non-homogeneous materials. A number of demonstrations of simple haptic tasks which combine our rendering techniques are also described.