The ubiquitous use of online tools, contractors and homework sites, has made plagiarism a concerning topic in computer science education. With the introduction of ChatGPT, it poses a threat now more than ever. Many cheating detection tools, such as similarity checkers and style anomaly checkers, help instructors decide whether a student has plagiarized. However, these are not scalable to large classes. Similarity tools can produce high rates of suspected cheating and thus ineffectively use an instructor's time in weeding out the actual cheating cases, especially in the early weeks of CS courses where programs can be small and student solutions can be very similar. We developed a new approach using outlier detection to filter inconsistent performers based on their lab scores throughout the course and their midterm exam scores. Instructors can then manually analyze a manageable amount of students even with large class sizes. We performed our experiment on two large course offerings of CS1 (a total of 177 students) using our algorithm and compared it to a manual analysis performed by an experienced CS1 instructor. The detection approach identified 11 students in the first offering (Winter 2019) and 12 students in the second offering (Spring 2023). With an average precision of 83%, our tool produces a list of concerning students with high precision. This significantly helps teachers efficiently allocate their time and pursue cheating early in the term in order to address and prevent further issues.

Student cheating on at-home programming assignments is a well- known problem. A key contributor is externally-obtained solutions from websites, contractors, and recently generative AI. In our experience, such externally-obtained solutions often use coding styles that depart from a class' style, which we call "style anomalies," such as using untaught or advanced constructs like pointers or ternary operators, or having different indenting or brace usage from the class style. We developed a tool to auto-count style anomalies. For six labs across four terms in 2021-2022, and 50 sampled students per lab, we found 18% of submissions on average had unusually-high style anomaly counts. Importantly, 8% of submissions on average had a high style anomaly count but were not flagged by a similarity checker, meaning 8% of submissions are suspicious but might have been missed if using similarity checking alone. We repeated a similar analysis for Spring 2023 when generative AI (ChatGPT) was gaining popularity, and the numbers rose to 26% and 18%, respectively. Detailed investigations by instructors led to a majority (but not all) high style anomaly submissions being deemed cheating. Even for high-similarity submissions, counting style anomalies can help instructors focus investigations on the most-likely cheating cases, and can strengthen cases sent to student conduct offices. With the rise of externally-obtained solutions from websites, contractors, and generative AI, counting style anomalies may become an increasingly important complement to similarity checking; in fact, it is now the primary cheat-detection tool in our CS1 at a large state university, with similarity secondary.

We experimented with ChatGPT's ability to write programs in a CS1 class, and the ability of a popular tool to auto-detect ChatGPT-written programs. We found ChatGPT was proficient at generating correct programs from a mere copy-paste of the English programming assignment specifications. However, running ChatGPT for 10 programming assignments and acting as 20 different students, and using zyBook's APEX beta tool for academic integrity, we found: (1) ChatGPT-generated programs tend to use a programming style departing from the style taught in the textbook or by the instructor, and these "style anomalies" were automatically detected. (2) Although ChatGPT may for the same assignment generate a few different program solutions for different students, ChatGPT often generates highly-similar programs for different students, so if enough students in a class (e.g., 5 or more) use ChatGPT, their programs will likely be flagged by a similarity checker. (3) If students are required to do all programming in the autograder's IDE, then a student using ChatGPT ends up showing very little time relative to classmates, which is automatically flagged. (4) Manually, we observed that if a student consistently uses ChatGPT to submit programs, the programming style may vary across programs, something normal students don't do; automation of style inconsistency detection was recently added to APEX. In short, while there will no doubt be an arms race between AI-generated programs and automatic detection of AI-generated programs, currently students using ChatGPT for multiple CS1 programs can be detected by automated tools such as zyBooks' APEX.

College cheating is common, including in computer science (CS) classes like introductory programming (CS1). Much research surveys college students about cheating, but few survey students actually caught cheating, or analyze their performance. We analyzed performance of 24 students sanctioned for cheating on programs in our CS1 over three terms, out of 300+ students, mostly non-CS science and engineering majors. Sanctioned students participated less in lectures (scoring 77% vs. 91%, p = 0.00002), and were less earnest in their completion of the online book's readings (51% vs. 80%, p = 0.0000001) during weeks 1-5. Those findings suggest early disengagement which would correlate with a tendency to cheat, and might also suggest a lack of learning which might help cause cheating. Sanctioned students scored dramatically lower on the earlier midterm exam (61% vs. 83%, p = 0.0001). After being sanctioned with Fs in the course (typically post-midterm), most agreed to an optional later interview to help the professor learn how to prevent cheating, at which point most were quite forthright. Key themes included an inability or unwillingness to devote the time needed to learn programming, a belief that the required CS1 course was not important for non-CS majors, and a disbelief that cheating students would be caught or punished despite warnings. More studies of such experiences may help instructors reduce cheating; in our case, the findings suggest instructors should emphasize relevance, make detection/punishment efforts clear, and detect early disengagement and potentially intervene.

Student cheating on at-home programming assignments is a well-known problem. A key contributor is externally obtained solutions from websites, contractors, and recently generative AI. In our experience, such externally obtained solutions often use coding styles that depart from a class's style, which we call "style anomalies". Examples of style anomalies include using untaught or advanced constructs like pointers or ternary operators or having different indenting or brace usage from the class style. We developed a tool to automatically count style anomalies in student code submissions. We used this tool to find suspected cheating in student submissions for lab assignments across five terms of CS1. This poster presents our findings: Some student submissions were suspected of cheating due to high style anomaly counts and were not flagged as suspicious by a code similarity checker. With the rise of externally obtained solutions from websites, contractors, and generative AI, style anomalies may become an important complement to similarity checking for detecting cheating.

This microteaching session is like Nifty Assignments for instruction. Instead of having the presenters just talk about their teaching, they will simulate how they would actually teach something. Covering a range of topics and grade levels, six educators will demo how they would teach a specific topic. To help identify the pedagogical practices that cut across grade bands and topics, the moderator, Colleen Lewis, will describe how their pedagogical practices connect with education research. The goal of the session is to inspire SIGCSE attendees by highlighting innovative instruction by exceptional educators. Attendees can adopt the content and/or pedagogical practices from each microteaching example.

Many CS1 teachers focus on specific content approaches in CS1. Some want objects early, some functions early, some decisions/loops first. Some put emphasis on language details, some on language-neutral problem solving. Some demand real-world IDEs, code versioning tools, industry-quality comments, specifications, documentation, or test coverage. While the focus shows teachers care and may indeed provide benefits, those specific focuses can also prevent increased cooperation among universities in defining a more "common" CS1 curricula. With a more common curriculum, better content and tool support is enabled due to economies of scale. Such cooperation could yield a more powerful approach to teaching CS1, elevating the role of CS1 instructors. CS1 instructors, by being more flexible in their content approaches, may help show the college education community the great benefits of increased cooperation among universities, especially in the design and delivery of introductory gateway courses taken by large numbers of students. We describe results of discussions with over 100 instructors at over 50 universities during the past decade, highlighting frequently-stated content approaches that have little or no evidence supporting the approach and that may hamper cooperation, and we end by encouraging flexibility in content approaches to enable the community and publishers to provide better CS1 support.

We describe our experience organizing and teaching a CS1 "common course" pilot across 7 institutions during the 2023 spring term. A common course is a comprehensive centrally-designed course taught nearly identically across multiple institutions. It goes beyond common inter-institution sharing of ideas and resources, and instead is essentially the same course taught by different instructors, akin to multiple coordinated sections of a course at one institution. We describe the experience of 7 instructors who voluntarily joined the pilot, which included instructors at 5 state universities and 2 community colleges. The common course's comprehensive design included a 15-week configured CS1 C++ online zyBook having weekly interactive readings, coding homeworks, programming assignments, and quizzes (all auto-graded); a midterm and final exam; a syllabus with schedule, grade weights, policies (late policies, cheating policies, etc.); support for teaching active lectures including detailed lecture notes and coding examples; and bi-weekly meetings among the 7 instructors plus an informal shared TA. Overall, the courses went smoothly for students, and the instructors all strongly indicated they benefited from the experience, and would do it again and recommend it to others. They listed key benefits to include time savings (which freed them to perform higher-value, more enjoyable tasks), state-of-the-art tools and pedagogy (like auto-grading and active lectures), the coding examples in the lecture notes, the ability to compare their students' performance to others, and the camaraderie and idea exchanges at the bi-weekly meetings.

Automated assistance for detecting cheating on programs has long been investigated by CS educators, especially with the rise of "homework help" websites over the past decade, and recently with AI tools like ChatGPT. The main detection approach has long been flagging similar submission pairs. Modern cheating, like hiring contractors or using ChatGPT, may not yield such similarity. And, cases based on similarity alone may be weak. Thus, over the past several years, building on logs from an online program auto-grader (zyBooks), we developed additional "cheating concern metrics": points rate, style anomalies, style inconsistencies, IP address anomalies, code replacements, and initial copying. Most are defined not only for one programming assignment but also across a set of assignments. The metrics can help catch more kinds of cheating, provide more compelling evidence of cheating, reduce false cheating accusations based on similarity alone, and help instructors focus their limited cheat-detection time on the most egregious cases. We describe the techniques, and our experiences (via our own Python scripts and a commercial tool) for several terms, showing benefits of having more metrics than just similarity. Of 30 cheating cases over 3 terms and 300 students, most were based on metrics beyond similarity, all students admitted, none later contested, and time per student was only 1-2 hours (far less than previously). Our goal is to prevent cheating in the first place, by reducing opportunity via strong detection tools, as part of a multi-faceted approach to having students truly learn and stay out of trouble.

Similarity checking is a common approach for detecting cheating in programming courses. A known limitation is high rates of similar pairs for programs lacking variability in possible solutions, especially for small programs. We experienced this issue in our CS1 course, where similarity checking in early weeks yielded many highly-similar pairs, many of which were not likely due to copying. Yet, we wish to catch copying students early, so that we can intervene and help those students avoid developing copying habits that may cause them trouble later. Our approach is to modify the program specifications to include variability-inducing requirements, namely places in the specifications where students make choices in their solutions, where different choices reduce the similarity scores. Those variability-inducing requirements are intentionally designed to avoid making the problem much harder for students. Examples of variability-inducing requirements include adding requirements to check for invalid input, or counting items. Such requirements have many different possible ways of implementing each. Essentially, variability-inducing requirements decrease the odds that two students would submit programs scored as highly-similar by a similarity checker, even for small programs. For 5 programs in our CS1 course, we added some variability-inducing requirements. Compared to an earlier term, the similarity checker's highly-similar-pairs rate dropped from 52% to 20% on average. Students' scores stayed the same from 98% to 96%, though time did increase from 18 min to 31 min on average. Adding such requirements helps instructors to do similarity detection and perform early interventions if desired.

CS educators have increasing interest in equitable grading, to support differing student backgrounds, perspectives, and current life situations. Our course is heavily scaffolded (one aspect of equitable grading), with points for readings, homeworks, and lab assignments, every week. All those items are auto graded with instant feedback, partial credit, and resubmissions. Previously, we did not accept late work, except for rare exceptions. In Spring 2022, following equitable-grading advice to reduce emphasis on deadlines, we allowed work to be submitted (and resubmitted) up to 14 days after target dates, with a small 1% deduction/day, with students receiving whatever max score occurred across those 14 days. This paper analyzes how students made use of this "late policy." The main finding was students did not shift all work by 1-2 weeks, as we originally feared; instead, students did most work by target dates. We found many of our 265 students only used the policy lightly (51%) or used it moderately (35%) to earn a few more points 1-2 days after target dates. Only 14% were heavy users of the policy, and they had reasonable course outcomes. Student feedback was positive, and instructors stated they saved time and energy due to reduced late requests.

Computer science instructors have long advised students that success in CS1 requires many hours, such as 8-10 hours/week outside class time, but students often don't believe it. Recently, the most-widely used CS1 learning system (zyBooks), which is web-native and records student activity data, began providing instructors with data on student time spent reading and answering reading questions, solving small homework problems, and coding the programming assignments, all online and auto-graded, representing nearly all a student's time outside class. In our 300+ student CS1 course at a large state university in Spring 2022, we required all work to be done in the zyBook and analyzed student time, including analysis relative to self-reported prior programming experience. Students who completed the class averaged 6.1 hours/week, with a large standard deviation of 2.3, and averaged a B+. Students averaged 6.9 hours in weeks 1-5 leading up to the midterm, peaking at 9 hours in Week 5. We found that over 90% of students who averaged 9-12 hours/week earned As or Bs, even those reporting no prior programming experience. Spending under 4 hours/week nearly guaranteed failing the midterm, and almost no students who spent fewer than 6 hours/week got an A on the midterm (unless they had prior experience). We also found that measuring actual time is important because students overreport time in surveys. With this concrete time data available to share with CS1 students, the hope is that future students may be more likely to allocate the time needed for success in CS1.

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.

Early prediction of students at risk of doing poorly in CS1 can enable early interventions or class adjustments. Preferably, prediction methods would be lightweight, not requiring much extra activity or data-collection work from instructors beyond what they already do. Previous methods included giving surveys, collecting (potentially sensitive) demographic data, introducing clicker questions into lectures, or using locally-developed systems that analyze programming behavior, each requiring some effort by instructors. Today, a widely used textbook / learning system in CS1 classes is zyBooks, used by several hundred thousand students annually. The system automatically collects data related to reading, homework, and programming assignments. For a 300+ student CS1 class, we found that three data metrics, auto-collected by that system in early weeks (1-4), were good at predicting performance on the week-6 midterm exam: non-earnest completion of the assigned readings, struggle on the coding homework, and low scores on the programming assignments, with correlation magnitudes of 0.44, 0.58, and 0.72, respectively. We combined those metrics in a decision tree model to predict students at-risk of failing the midterm exam (<70%, meaning D or F), and achieved 85% prediction accuracy with 82% sensitivity and 89% specificity, which is higher than previously-published early-prediction approaches. The approach may mean that thousands of instructors already using zyBooks (or a similar system) can get a more accurate early prediction of at-risk students, without requiring extra effort or activities, and avoiding collection of sensitive demographic data.

Coral was introduced several years ago to ease the learning in college-level introductory programming courses. Coral consists of a simple textual code language and corresponding flowchart language and a free web-based educational simulator. Previous researchers described the benefits of Coral in CS0 courses and the first weeks of CS1 courses. We previously used Coral in CS1 and enjoyed the teaching experience, due to: the simple intuitive syntax, the simulator's auto-creation of a flowchart from code, and the simulator's visualization of code and flowchart program execution. However, we wanted to ensure we weren't hurting students with the transition from Coral to C++. This paper describes our experiences of teaching Coral in a ~100-student CS1 section for weeks 1-3 versus two other sections that taught C++ only. We performed analyses to answer three research questions: (1) Do students learn Coral more easily than C++? (2) Do students easily transition from Coral to C++? and (3) Do Coral-treated students do equally well on later C++ programs? We analyzed performance on auto-graded code-writing problems in zyBooks. We did not find support for (1), but did find support for (2) and (3), with Coral-treated students easily switching to C++ and performing equally well on later C++ programs. We conclude that CS1 instructors who enjoy the early-weeks teaching benefits of Coral can do so confidently knowing that students will perform equally well later in the course.

Cheating in introductory programming classes (CS1) is a well-known problem. Various methods have been suggested to reduce cheating, but many are time-consuming, resource intensive, or don't scale to large classes. We introduced a class intervention having 6 low-effort commonly-suggested methods to reduce cheating: (1) Discussing academic integrity for 20-30 minutes, several weeks into the term, (2) Requiring an integrity quiz with explicit do's and don'ts, (3) Allowing students to retract program submissions, (4) Reminding students mid-term about integrity and consequences of getting caught, (5) Showing instructor tools in class (including a similarity checker, statistics on time spent, and access to a student's full coding history), (6) Normalizing help and pointing students to help resources. Via manual evaluation of similarity checker results on 7 held-constant labs with one instructor teaching 100-student sections, for two pre-intervention and two intervention sections, suspected-cheating reduced 62% (30.5% down to 11.5%). Because manual evaluation could be biased and is time consuming, we developed two automated coding-behavior metrics per lab -- time spent programming, and % of students with highly-similar code -- that may suggest how much cheating is happening. Time spent increased by 56% (7 min to 10.9 min), and % of students with highly-similar code dropped 48% (38.5% to 20%). We later repeated the intervention with a second instructor and different labs and achieved similar (in fact, even stronger) results, with time rising 84% (13 min to 24 minutes) and % dropping 66% (55.5% to 19%). All findings were statistically significant with p < 0.0001.

College textbook publishing is transforming from a model of static textbooks to a modern model of customizable textbooks. Customization may involve reconfiguring content, combining textbooks, authoring one's own content, adding notes to content, and more. As such, publishing is moving away from a model of selling static textbooks, and toward a model of providing a library of content from which instructors can build a course. This Full Paper provides data for one digital-only publisher, zyBooks, on the prevalence and trends around reconfiguring and combining Computer Science and Engineering textbooks, instructor-authored sections, and instructor-added notes. The data show that for over 4,000 classes in 2020, over 85% of classes reconfigured their books, over 30% of classes combined two or more books with hundreds combining three or more, about 30% of books had instructor notes added, and about 65% of zyLabs-enabled zyBooks included instructor-created labs. The trend away from static textbooks and toward customizable content has substantial implications on how content is authored, requiring more modularity of content sections to support reconfiguration, and requiring more consistency across subjects to enable combining content. The trend also has substantial implications on book marketing, pricing, renewals, and more.

In recent years, hundreds of CS1 classes have adopted a many small programs (MSP) approach to weekly programming assignments. The MSP approach involves assigning students several smaller programming assignments per week, for example 5-7, versus the traditional one larger program (OLP) per week. This shift is largely made possible by easy-to-use program auto-graders that have arisen in recent years. Such auto-graders make grading so many programs feasible, while also providing students with immediate feedback. The MSP approach has been shown to yield advantages that include earlier starts, reduced anxiety, increased confidence, the ability to switch to another program if stuck, better exam performance, and less attrition, with analysis showing students easily transition to larger programs later. We desired to gain insight on how our CS1 students were working through our weekly MSPs. Thus, in 2018, we began exploring automated creation of concise representations of student behavior while they developed their programs, what we call "workflow charts". We used a popular commercial auto-grader that has a built-in development environment and provides detailed log files of every program compile/run by each student. We describe the goals of such a representation, the evolution of our representation to its current status, various design trade-offs, our current usage, and numerous possible future uses in CS1 classes. We plan to create a website for any instructor to upload such log files to gain insight on their own class' performance.

This innovative practice full paper presents new learning content, developed natively for the web, that teaches core programming concepts using interactive activities, such as animations, learning questions, and interactive tools, in addition to text and figures. The core programming concepts are topics typically covered in CS1 (and often in CS0), including input/output, variables, branching, loops, arrays, and functions. Usually, programming is introduced with an industry language, such as Java or Python, which were developed for professionals, not for students. Sometimes, programming is introduced visually, such as Scratch or Alice, but many instructors want a more serious feel for college students, writing textual code. Our content teaches programming using an ultra-simple language, Coral, designed specifically to teach core concepts. The content presents a Coral program as code or a flowchart that closely resembles the code's structure. Each chapter starts by introducing the programming concept visually with flowchart examples, so students develop a strong ability to read a program and understand how the program executes. Later in the chapter, the content introduces the corresponding textual code. The student then writes code to solve homework problems. Such incremental learning (first master program reading, then master program writing) is a key feature. Another key feature is a strong emphasis on visualization and intuition: The content uses animations that show Coral programs being executed line-by-line, along with variables shown in memory, including variable value updates from assignments. Further, the content has an online educational simulator where a student or instructor can write and execute Coral code. This paper includes early student usage data, such as amount of time spent to complete learning and homework, that shows students can quickly learn programming concepts. Some surveyed students commented on liking the incremental practice.

Modern program auto-graders enable new CS1 approaches. Instructors can easily create new assignments, with students receiving immediate score feedback and resubmitting assignments. With such auto-graders, one approach assigns many small programs (MSPs) each week instead of one large program (OLP). Earlier research showed MSPs in CS1 yielded happier students and better grades. Our university and other schools have switched to MSPs in CS1. This paper addresses common questions about MSPs. We analyzed submissions for a 76-student section of our MSP CS1 course. Given 7 MSPs per week each worth 10 points, students needed 50 points for full credit. Students averaged 17 minutes per MSP and 120 minutes per week. Given 7 days, students on average started 2.2 days ahead of the due date, with 37% starting at least 3 days ahead. 40% of students exceeded the required 50 points per week (no extra credit was given). 50% of students "pivoted" -- switching to another program before completing the previous one. 54% used MSPs to study for exams. Students used MSPs in ways beneficial to their learning and stress reduction: spending sufficient time, completing more than necessary, preparing for exams, and pivoting to avoid getting stuck. A common concern is that MSP CS1 students will do poorly in a CS2 using OLPs. We analyzed 5 quarters of CS2 and found MSP students do fine (in fact slightly better). These results encourage use and refinement of MSPs in CS1 and other courses.

Program auto-graders used to be tough applications to install and use by instructors, meaning many instructors avoided them, and for those that used them, most assignments were created by specialists with scripting and other expertise. As such, creating new auto-graded programming assignments was a rare event done by just a few people. But modern cloud-based program auto-graders enable nearly any instructor or TA to create new auto-graded assignments in just tens of minutes, fully created and carried out via the web. This capability has led to an explosion in the number of instructors and TAs creating auto-graded programming assignments, benefiting students via immediate feedback and the option to resubmit, and saving teachers huge amounts of grading time. BUT, this new frontier is very different from hand-graded assignments, with plenty of pitfalls for teachers to avoid, and emerging best practices. This BOF allows teachers to share do's and don'ts, so each can improve their use of auto-graded labs, and teachers new to auto-graded labs can benefit from others' experiences. Special focus is on early CS classes (CS0, CS1, CS2) but topics may apply to many CS classes.

Advanced control methodologies have helped the development of modern vehicles that are capable of path planning and path following. For instance, Model Predictive Control (MPC) employs a predictive model to predict the behavior of the physical system for a specific time horizon in the future. An optimization problem is solved to compute optimal control actions while handling model uncertainties and nonlinearities. However, these prediction routines are computationally intensive and the computational overhead grows with the complexity of the model. Switching MPC addresses this issue by combining multiple predictive models, each with a different precision granularity. In this artcle, we proposed a novel switching predictive control method based on a model reduction scheme to achieve various model granularities for path following in autonomous vehicles. A state-based model with tunable parameters is proposed to operate as a reconfigurable predictive model of the vehicle. A runtime switching algorithm is presented that selects the best model using machine learning. We employed a metric that formulates the tradeoff between the error and computational savings due to model reduction. Our simulation results show that the use of the predictive model in the switching scheme as opposed to single granularity scheme, yields a 45% decrease in execution time in tradeoff for a small 12% loss in accuracy in prediction of future outputs and no loss of accuracy in tracking the reference trajectory.

Many teachers of CS 1 (introductory programming) have switched to Python rather than C, C++, or Java. One reason is the belief that Python's interpreted nature plus simpler syntax and semantics ease a student's learning, but data supporting that belief is scarce. This paper addresses the question: Do Python learners struggle less than C++ learners? We analyzed student submissions on small coding exercises in CS 1 courses at 20 different universities, 10 courses using Python, and 11 using C++. Each course used either the Python or C++ version of an online textbook from one publisher, each book having 100+ small coding exercises, expected to take 2-5 minutes each. We considered 11 exercises whose Python and C++ versions were nearly identical and that appeared in various chapters. We defined struggle rate for exercises, where struggle means a student spent excessive time or attempts on an exercise. Based on that rate, we found the learning for Python was not eased; in fact, Python students had significantly higher struggle rates than C++ students (26% vs. 13%). Higher rates were seen even when considering only classes with no prerequisites, classes for majors only, or classes for non-majors only. We encourage the community to do further analyses, to help guide teachers when choosing a CS 1 language.

Introductory programming courses often use a full-featured programming language, such as Python, Java, or C++, wherein students concurrently learn programming concepts along with language syntax. However, many instructors believe that learning programming concepts first, then learning a specific language's syntax, may be more effective than learning both concurrently. Thus, some courses first teach programming via flowcharts and pseudocode. Some tools and materials support teaching programming via flowcharts, but we felt much improvement was needed. Therefore, we developed a new flowchart language, named Coral-Charts, specifically intended to teach fundamental programming constructs like assignments, branches, loops, functions, and arrays. We developed a web-based graphical simulator for Coral-Charts; no local tool installation is necessary (unlike the most common existing flowchart tool). The simulator always displays the values of variables, which helps students comprehend the impact of statements. The simulator enforces a layout that intentionally mirrors textual code's top-to-bottom execution and sub-statement indentation, easing the transition to a textual language. Furthermore, we defined a new pseudocode-like language, named Coral (corallanguage.org), that is executable and that matches Coral-Charts. Syntax is ultra-simple and only essential constructs are included. Certain features automatically detect or eliminate many new-learner errors. Students can type Coral code, from which a Coral-Charts flowchart is auto-generated, and students can execute both the code and flowcharts. Coral was carefully designed to naturally lead into languages Python, Java, or C++. Coral and Coral-Charts are used in the textbook Fundamental Programming Concepts (zybooks.com/catalog/fundamental-programming-concepts). We welcome feedback on the approach and potential collaborators in implementing experiments.

This lightning talk presents new free, online material to provide new programmers with a solid foundation in debugging. Nearly every instructor who teaches programming notices that students have weak debugging skills. Faced with a failing program, many students make random changes and hope things improve. Or they shrug their shoulders, say "I have no idea what/s wrong", and ask an instructor for help. Most textbooks and websites provide insufficient coverage or training of debugging. This new material teaches a basic systematic process for debugging: Create a hypothesis, test the hypothesis, repeat. Seems obvious, but it/s not to most students. The material first teaches a general troubleshooting process using everyday systems, like smartphones can cars. With a solid foundation of the basic systematic process, the material then teaches basic debugging using a generic programming language. The material starts from the basics, following that adage that one must walk before they can run. Students typically don/t have the concept of "Hypothesize / Test". But after repeated examples that stress those items, they will hopefully have developed a habit of thinking of troubleshooting more systematically. The material is targeted at the fifth week of a CS1 course, when students have some programming experience and are beginning to face harder debugging challenges, but is also beneficial for any programming class beyond CS1, where it could be used in the first week. The material is delivered as free two-chapter online book available with sign in at http://www.zybooks.com/catalog/troubleshooting-basics/.

Getting students to read and study before class, to be better prepared for lecture, or to enable a flipped classroom is a long-standing difficulty for teachers of introductory programming classes. Furthermore, getting students to do homework, consisting of small practice problems and questions, is also a long-standing difficulty without massive grading resources. And even then, preventing students from copying others' solutions is difficult as well. Today, the web enables new interactive learning material that is replacing past forms of textbooks and homework assignments, and students today commonly have access to needed devices and the internet. This paper provides data on student reading and homework completion rates for web-based interactive learning material we created that automatically records reading and homework activity by students. The data is for several thousand students at over 10 universities, for introductory programming classes in Java, Python, and C++. The data shows that, with an appropriate amount of awarded points, required-reading completion rate was 84%, and auto-graded homework completion rate was 75%, varying somewhat based on how many course grade points those items were worth. Students on average spent about 10 minutes reading each section, and about 3 minutes per homework problem, both appropriate amounts for those items. Furthermore, we developed measures of whether students were earnestly attempting the reading and homeworks, versus just "cheating the system" to get course grade points. We describe those earnestness measures in this paper. With proper design and amount of assigned work, 80%-90% of students earnestly did the reading and homework activities, even when no penalty existed for cheating the system, and fewer than 3% blatantly cheated the system to get their points.

New college engineering textbooks and other online learning materials use activities like interactive questions to engage students and improve learning. Some such materials use a safe learning approach where activity solutions are readily available to students, as opposed to being graded like a homework assignment. Instructors have inquired how few course points are sufficient to ensure students complete such assigned activities. Furthermore, some wonder if assigning course points might lead students to cheat the system by revealing solutions to quickly earn points, rather than earnestly attempting to answer the questions. We analyzed behavior data of 1,394 students in 8 engineering classes at different colleges. We found that surprisingly few course points — just 5 or 10 points, and as few as 2 points — were sufficient to achieve over 90% average completion of activities by students. For comparison, assigning no points yielded only about 50% completion. Furthermore, we found that assigning points had only a minor impact on students earnestly attempting to answer questions, versus showing themselves the answer first, with earnestness changing only modestly from 92% to 86% when points were assigned.

For textbooks on technical topics, the typical amount of text used is more than what many college students will read. Some teachers observe, and students report, that students commonly skim such text. As such, a writing style that aggressively minimizes text while still teaching the core technical topic may improve student learning; if text is short enough, students may then read and study the text more carefully. The objective of this study was to compare the effect of text quantity on amount learned. We created and compared content styles using a lesson that taught Google search techniques. The two main content styles were normal text and minimal text. The normal text style included 6-12 sentences followed by 1-3 examples. The minimal text style included 1-2 sentences followed by 1-3 examples. We conducted a randomized control study with 168 participants enrolled in a college-level Introduction to Computing course for non-computing majors. Each participant was randomly assigned one lesson style. We provided a pre-lesson and post-lesson quiz, each with ten questions. Additionally, the participants completed background and follow-up surveys. The study was part of a course homework assignment, so self-selection bias was limited. The course is primarily taken by non-majors and covers the basics of Word, Excel, and HTML. An improvement score is a participant's post-lesson minus pre-lesson quiz scores. The average improvement score for minimal text was 2.4 (6.5 - 4.1), which is higher (p-value <; 0.01) than the average improvement score for normal text of 1.1 (5.1 - 4.0). Thus, teaching the same topic using less text led to more learning. The conclusion is not that materials should be watered down, but rather that great attention should be paid to using minimal text while teaching the same core topics.

Interactive activities in textbooks and online courses are no longer just decorative, but have become compelling tools for engaging students. This BOF, lead by professors and authors with experience in designing complex interactive tutoring materials, invites interested instructors and authors to discuss best practices in designing activities, integrating them into courses, and measuring outcomes.

Physical models utilize mathematical equations to characterize physical systems like airway mechanics, neuron networks, or chemical reactions. Previous work has shown that field programmable gate arrays (FPGAs) execute physical models efficiently. To improve the implementation of physical models on FPGAs, this article leverages graph theoretic techniques to synthesize physical models onto FPGAs. The first phase maps physical model equations onto a structured virtual processing element (PE) graph using graph theoretic folding techniques. The second phase maps the structured virtual PE graph onto physical PE regions on an FPGA using graph embedding theory. A simulated annealing algorithm is introduced that can map any physical model onto an FPGA regardless of the model's underlying topology. We further extend the simulated annealing approach by leveraging existing graph drawing algorithms to generate the initial placement. Compared to previous work on physical model implementation on FPGAs, embedding increases clock frequency by 25% on average (for applicable topologies), whereas simulated annealing increases frequency by 13% on average. The embedding approach typically produces a circuit whose frequency is limited by the FPGA clock instead of routing. Additionally, complex models that could not previously be routed due to complexity were made routable when using placement constraints.

This paper outlines a transparent and nonintrusive checkpointing mechanism for use with FPGA-based digital mockups. A digital mockup is an executable model of a physical system and used for real-time test and validation of cyber-physical devices that interact with the physical system. These digital mockups are typically defined in terms of a large set of ordinary differential equations. We consider digital mockups impelemented on field-programmable gate arrays (FPGAs). A checkpoint is a snapshot of the internal state of the model at a specific point in time as captured by some controller that resides on the same FPGA. We require that the model continues uninterrupted execution during a checkpointing operation. Once a checkpoint is created, the corresponding state information is transferred from the FPGA to a host computer for visualization and other off-chip processing. We outline the architecture of a checkpointing controller that captures and transfers the state information at a desired clock cycle using an aggressive compression technique. Our compression technique achieves 90% reduction in data transferred from the FPGA to the host computer under periodic checkpointing scenarios. The checkpointing with compression yields 15-36% FPGA size overhead, versus 6-11% for checkpointing without compression.

Physical models capture environmental phenomena such as biochemical reactions, a beating heart, or neuron synapses, using mathematical equations. Previous work has shown that physical models can execute orders of magnitude faster on FPGAs (Field-Programmable Gate Arrays) compared to desktop PCs. Different models of the same physical phenomenon may vary, with "upgraded" models being more accurate but using more FPGA area and having slower performance. We propose that design space exploration considering upgradable models can dramatically increase the useful design space. We present an analysis of the solution space for utilizing networks of processing-elements (PEs) on FPGAs to emulate physical models, implement a web-based frontend to a compiler and cycle-accurate simulator of PE networks to estimate solution metrics, and utilize design-of-experiments (DOE) statistical methods to identify Pareto points. By considering upgradeable models during the design space exploration of a human lung physical model, the solution space of possible speedup, area, and accuracy is increased by 6X, 7.3X, and 1.5X, respectively, compared to evaluating a single model.

College-level online learning took off in a big way in 2012, and is likely to impact every department and teacher in some manner. This workshop will highlight major developments in online education technology in engineering and computer science. The workshop will highlight recent online trends like flipped classrooms and MOOCs, will survey various authoring and delivery platforms like EdX and Zyante, summarize some research on online/flipped teaching, discuss methods for instructors to collaborate on delivering instructional experiences, and highlight experiences by teachers of online and hybrid courses.

Physical models utilize mathematical equations to model physical systems like airway mechanics, neuron networks, or chemical reactions. Previous work has shown that physical models can execute fast on FPGAs (field-programmable gate arrays). We introduce an approach for implementing physical models on FPGAs that applies graph theoretic techniques to make use of a physical model's natural structure--tree, ring, chain, etc.--resulting in model execution speedups. A first phase of the approach maps physical model equations to a structured virtual PE (processing element) graph using graph theoretic folding techniques. A second phase maps the structured virtual PE graph to physical PE regions on an FPGA using graph embedding theory. We also present a simulated annealing approach with custom cost and neighbor functions that can map any physical model onto an FPGA with low wire costs. Average circuit speedup improvements over previous works for various physical models are 65% using the graph embedding and 35% using the simulated annealing approach. Each approach's more efficient use of FPGA resources also enables larger models to be implemented on an FPGA device.

Fast execution of physical system models has various uses, such as simulating physical phenomena or real-time testing of medical equipment. Physical system models commonly consist of thousands of differential equations. Solving such equations using software on microprocessor devices may be slow. Several past efforts implement such models as parallel circuits on special computing devices called Field-Programmable Gate Arrays (FPGAs), demonstrating large speedups due to the excellent match between the massive fine-grained local communication parallelism common in physical models and the fine-grained parallel compute elements and local connectivity of FPGAs. However, past implementation efforts were mostly manual or ad hoc. We present the first method for automatically converting a set of ordinary differential equations into circuits on FPGAs. The method uses a general Processing Element (PE) that we developed, designed to quickly solve a set of ordinary differential equations while using few FPGA resources. The method instantiates a network of general PEs, partitions equations among the PEs to minimize communication, generates each PE's custom program, creates custom connections among PEs, and maintains synchronization of all PEs in the network. Our experiments show that the method generates a 400-PE network on a commercial FPGA that executes four different models on average 15x faster than a 3 GHz Intel processor, 30x faster than a commercial 4-core ARM, 14x faster than a commercial 6-core Texas Instruments digital signal processor, and 4.4x faster than an NVIDIA 336-core graphics processing unit. We also show that the FPGA-based approach is reasonably cost effective compared to using the other platforms. The method yields 2.1x faster circuits than a commercial high-level synthesis tool that uses the traditional method for converting behavior to circuits, while using 2x fewer lookup tables, 2x fewer hardcore multiplier (DSP) units, though 3.5x more block RAM due to being programmable. Furthermore, the method does not just generate a single fastest design, but generates a range of designs that trade off size and performance, by using different numbers of PEs.

Emulating a physical system in real-time or faster has numerous applications in cyber-physical system design and deployment. For example, testing of a cyber-device's software (e.g., a medical ventilator) can be done via interaction with a real-time digital emulation of the target physical system (e.g., a human's respiratory system). Physical system emulation typically involves iteratively solving thousands of ordinary differential equations (ODEs) that model the physical system. We describe an approach that creates custom processing elements (PEs) specialized to the ODEs of a particular model while maintaining some programmability, targeting implementation on field-programmable gate arrays (FPGAs). We detail the PE micro-architecture and accompanying automated compilation and synthesis techniques. Furthermore, we describe our efforts to use a high-level synthesis approach that incorporates regularity extraction techniques as an alternative FPGA-based solution, and also describe an approach using graphics processing units (GPUs). We perform experiments with five models: a Weibel lung model, a Lutchen lung model, an atrial heart model, a neuron model, and a wave model; each model consists of several thousand ODEs and targets a Xilinx Virtex 6 FPGA. Results of the experiments show that the custom PE approach achieves 4X-9X speedups (average 6.7X) versus our previous general ODE-solver PE approach, and 7X-10X speedups (average 8.7X) versus high-level synthesis, while using approximately the same or fewer FPGA resources. Furthermore, the approach achieves speedups of 18X-32X (average 26X) versus an Nvidia GTX 460 GPU, and average speedups of more than 100X compared to a six-core TI DSP processor or a four-core ARM processor, and 24X versus an Intel I7 quad core processor running at 3.06 GHz. While an FPGA implementation costs about 3X-5X more than the non-FPGA approaches, a speedup/dollar analysis shows 10X improvement versus the next best approach, with the trend of decreasing FPGA costs improving speedup/dollar in the future.

Cyber-physical systems have become more difficult to test as hardware and software complexity grows. The increased integration between computing devices and physical phenomena demands new techniques for ensuring correct operation of devices across a broad range of operating conditions. Manual test methods, which involve test personnel, require much effort and expense and lengthen a device's time to market. We describe a method for test automation of devices wherein a device is connected to a digital mockup of the physical environment, where both the device and the digital mockup are managed by PC-based software. A digital mockup consists of a behavioral model of the interacting environment, such as a medical ventilator device connected to a digital mockup of human lungs. We introduce Mockup Electronic Data Sheets (MEDS) as a method for embedding model information into the digital mockup, allowing PC software to automatically detect configurable model parameters and facilitate test automation. We summarize a case study showing the effectiveness of digital mockups and MEDS as a framework for test automation on a medical ventilator, resulting in 5× less time spent testing compared to methods requiring test personnel.

The instruction cache is a popular optimization target due to the cache's high impact on system performance and power and because of the cache's predictable temporal and spatial locality. This article is an in depth study on the interaction of code reordering (a long-known technique) and cache configuration (a relatively new technique). Experimental results show that code reordering coupled with cache configuration reveals additional energy savings as high as 10--15% for several benchmarks with reduced cache area as high as 48%. To exploit these additional benefits, we architect and evaluate several design exploration heuristics for combining these two methods.

We introduce thread warping, a dynamic optimization technique that customizes multicore architectures to a given application by dynamically synthesizing threads into custom accelerator circuits on FPGAs (Field-Programmable Gate Arrays). Thread warping builds upon previous dynamic synthesis techniques for single-threaded applications, enabling dynamic architectural adaptation to different amounts of thread-level parallelism, while also exploiting parallelism within each thread to further improve performance. Furthermore, thread warping maintains the important separation of function from architecture, enabling portability of applications to architectures with different quantities of microprocessors and FPGAs, an advantage not shared by static compilation/synthesis approaches. We introduce an approach consisting of CAD tools and operating system support that enables thread warping on potentially any microprocessor/FPGA architecture. We evaluate thread warping using a simulator for high-performance computing systems with different interconnections in addition to multicore embedded systems having between 4 and 64 ARM11 microprocessors. On average, thread warping achieved approximately 3x speedup compared to a high-performance quad-core Intel Xeon and 109x compared to an embedded system consisting of 4 ARM11 cores, with a size cost approximately equal to 36 ARM11 cores.

Field-programmable gate arrays (FPGAs) have recently been used as platforms to emulate SystemC descriptions. Emulation supports in-system testing using real input and output. We previously showed emulation speed to be competitive with SystemC simulations on a PC when the emulator uses acceleration engines. A limit on the number of acceleration engines that can fit on an emulation platform creates new online problems involving runtime decisions as to when to load a SystemC process into an acceleration engine. We define the online SystemC emulation acceleration problem. In contrast to previous works that focus on statically improving SystemC (and the more general event-driven) simulations, we utilize online heuristics to manage the use of a limited number of SystemC acceleration engines in an emulation framework, where the kernel must adapt and react to dynamically changing process and event queues. We test several online heuristics and show 9x improvement over microprocessor-only emulation and 5x over statically preloaded acceleration engines. We further improve emulation performance by 10--20% by adding kernel bypass connections between acceleration engines and by adapting the online heuristics to make use of those connections.

FPGAs are increasingly used to implement coprocessors for applications running on desktop platforms, and soon such FPGA coprocessing may appear in mobile devices. Because one device may run different applications from another device, different coprocessor sets are needed for each device based on the device's usage. We introduce an approach wherein a device profiles application usage and uploads that information to a server when docked. The server then determines the best coprocessor set based on such usage and on the device's particular FPGA constraints. The server creates the coprocessor set by combining pre-synthesized coprocessors for each application, and considers multiple versions of the same coprocessor, versions that tradeoff speed and size. We introduce a coprocessor set selection problem and propose a Pareto-optimal merge heuristic for the server that yields near-optimal solutions with linear time complexity. We also use a method that avoids time-consuming resynthesis of the coprocessors into a single FPGA binary, by using small reconfigurable regions with reserved inter-region communication channels. Our experiments show that the Pareto-optimal merge heuristic generates results within 1% of the optimal on average and run 5-20x faster than simulated annealing. The experiments also show that a 3x speedup and 70% energy reduction can be achieved by using FPGA coprocessors versus running the applications only on a microprocessor.

Field-programmable gates arrays (FPGAs) are increasingly used in general-purpose computing platforms to augment microprocessors, enabling runtime loading of coprocessors customized to speed up some applications. Such transmuting coprocessors create new dynamic management problems involving decisions as to when to load a coprocessor, where to place the coprocessor in the FPGA, or which resident coprocessor to replace. We define a transmuting coprocessor problem based on Intel's FSB-FPGA architecture, with attention on communication and memory contention. We develop an online algorithm to manage coprocessor loading, the AG algorithm, which uses aggregated gains to guide coprocessor load, placement, replacement, and wait decisions. Experiments using embedded system applications, for random, biased, and periodic input application sequences, a range of reconfiguration times, and different FPGA types with different numbers of partial reconfigurable regions, demonstrate that the AG algorithm is robust across a variety of situations. The AG algorithm results are within 15% of an unlimited-size FPGA on average, exhibit a small standard deviation, and show a 1.4× speedup versus a static coprocessor loading approach and a 3× speedup over execution on a microprocessor-only solution.

Field-programmable gate arrays (FPGAs) commonly implement system architectures composed from soft-core configurable components, such as a cache with configurable size or associativity, a processor with configurable datapath units, or a configurable network-on-chip connecting dozens of processors. Configurable components increasingly exist even on pre-fabricated platforms. Tuning configurable components to the particular application running on the architecture and to particular design constraints represents a challenging task often left to a designer. Knowledge of the Pareto-optimal points of a system for particular applications can be of benefit to designers seeking to make appropriate design tradeoffs for given constraints. Previous methods for generating Pareto points required extensive knowledge of an architecture's parameter interdependencies, used a simplistic approach that failed to find many parameters, or used randomized search algorithms that may have long runtimes. We introduce an algorithm for finding Pareto points, based on statistically rigorous methods derived from the Design of Experiments paradigm and extended for the purpose of finding Pareto points. The resulting DoE-based Pareto point Generator, or DPG, algorithm finds thorough Pareto points while running 3 times faster than randomized search algorithms, without requiring designer knowledge of parameter interdependencies--in fact, the approach determines those interdependencies automatically, representing an added bonus. We demonstrate DPG on Platune's configurable processor-bus-cache system-on-chip, Noxim's configurable network-on-chip, and the configurable Microblaze FPGA processor.

While soft processor cores provided by FPGA vendors offer designers with increased flexibility, such processors typically incur penalties in performance and energy consumption compared to hard processor core alternatives. The recently developed technology of warp processing can help reduce those penalties. Warp processing is the dynamic and transparent transformation of critical software regions from microprocessor execution to much faster circuit execution on an FPGA. In this article, we describe an implementation of a warp processor on a Xilinx Virtex-II Pro and Spartan3 FPGAs incorporating one or more MicroBlaze soft processor cores. We further provide a detailed analysis of the energy overhead of dynamically partitioning an application's kernels to hardware executing within an FPGA. Considering an implementation that periodically partitions the executing application once every minute, a MicroBlaze-based warp processor implemented on a Spartan3 FPGA achieves average speedups of 5.8× and energy reductions of 49% compared to the MicroBlaze soft processor core alone—providing competitive performance and energy consumption compared to existing hard processor cores.

Technology trends have enabled deployment of low-cost sensor-based systems, but designing customized sensor-based systems to carry out specific tasks still requires costly engineering by experts. We briefly summarize eBlocks, a technology enabling nonexperts to quickly construct basic customized sensor-based systems, without requiring electronics or knowledge of programming languages. We describe experiments illustrating successful construction of Boolean sensor-based systems by novice users, focusing on intuitive logic and state block design. Additionally, we present preliminary experiments demonstrating usability of integer-based blocks and introduce a programmable block and the corresponding configuration methodology intended for nonexpert users.

Tuning a configurable cache subsystem to an application can greatly reduce memory hierarchy energy consumption. Previous tuning methods use a level one configurable cache only, or a second level with separate instruction and data configurable caches. We instead use a commercially-common unified second level cache, a seemingly minor difference that actually expands the configuration space from 500 to about 20 000. We develop additive way tuning for tuning a cache subsystem with this large space, yielding 61% energy savings and 9% performance improvements over a nonconfigurable cache, greatly outperforming an extension of a previous method.

Various commercial programmable compute platforms have their processor architecture enhanced with field-programmable gate arrays (FPGAs). In a common usage scenario, an application loads custom processors into the FPGA to speed up application execution compared to processor-only execution. Transient applications, changing application workloads, and limited FPGA capacity have led to a new problem of operating-system-controlled dynamic management of the loading of coprocessors into the FPGAs for best overall performance or energy. We define the Dynamic Coprocessor Management problem and provide a mapping to an online optimization problem known as Metrical Task Systems. We introduce a robust heuristic, called the fading cumulative benefit (FCBenefit) heuristic, that outperforms other heuristics, including a previously developed one for MTS. For two distinct application sets, we generate numerous workloads and show that the FCBenefit heuristic provides best results across all considered workloads. In our simulations, the heuristic's results were within 9% of the offline optimal for performance, and within 3% for energy. The heuristic may be applicable to a wide variety of dynamic architecture management problems.

Designing circuits for FPGAs involves challenges often distinct from designing circuits for ASICs. We describe efforts to convert a pattern counting circuit architecture, based on a pipelined binary tree and originally designed for ASIC implementation, into a circuit suitable for FPGAs. The original architecture, when mapped to a Spartan 3e FPGA, could process 10 million patterns per second and handle up to 4,096 patterns. The modified architecture could instead process 100 million patterns per second and handle up to 32,768 patterns, representing a 10x performance improvement and a 4x efficiency improvement. The redesign involved partitioning large memories into smaller ones at the expense of redundant control logic. Through this and other case studies, design patterns may emerge that aid designers in building high-performance efficient circuits for FPGAs

Synthesizing common sequential algorithms, captured in a language like C, to FPGA circuits is now well-known to provide dramatic speedups for numerous applications, and to provide tremendous portability and adaptability advantages over circuit implementations of an application. However, many applications targeted to FPGAs are still designed and distributed at the circuit level, due in part to tremendous human ingenuity being exercised at that level to achieve exceptional performance and efficiency. A question then arises as to whether applications for FPGAs will have to be distributed as circuits to achieve desired performance and efficiency, or if instead a more portable language like C might be used. Given a set of common synthesis transformations, we studied the extent to which circuits published in FCCM in the past 6 years could be captured as sequential code and then synthesized back to the published circuit. The study showed that a surprising 82% of the 35 circuits chosen for the study could be re-derived from some form of standard C code, suggesting that standard C code, without extensions, may be an effective means for distributing FPGA applications

Due to the large contribution of the memory subsystem to total system power, the memory subsystem is highly amenable to customization for reduced power/energy and/or improved performance. Cache parameters such as total size, line size, and associativity can be specialized to the needs of an application for system optimization. In order to determine the best values for cache parameters, most methodologies utilize repetitious application execution to individually analyze each configuration explored. In this paper we propose a simplified yet efficient technique to accurately estimate the miss rate of many different cache configurations in just one single-pass of execution. The approach utilizes simple data structures in the form of a multi-layered table and elementary bitwise operations to capture the locality characteristics of an application's addressing behavior. The proposed technique intends to ease miss rate estimation and reduce cache exploration time.

The memory hierarchy of a system can consume up to 50% of microprocessor system power. Previous work has shown that tuning a configurable cache to a particular application can reduce memory subsystem energy by 62% on average. We introduce a self-tuning cache that performs transparent runtime cache tuning, thus relieving the application designer and/or compiler from predetermining an application's cache configuration. The self-tuning cache applies tuning at a determined tuning interval. A good interval balances tuning process energy overhead against the energy overhead of running in a sub-optimal cache configuration, which we show wastes much energy. We present a self-tuning cache that dynamically varies the tuning interval, resulting in average energy reduction of as much as 29%, falling within 13% of an oracle-based optimal method.

We introduce a new non-intrusive on-chip cache-tuning hardware module capable of accurately predicting the best configuration of a configurable cache for an executing application. Previous dynamic cache tuning approaches change the cache configuration several times as part of the tuning search process, executing the application using inferior configurations and temporarily causing energy and performance overhead. The introduced tuner uses a different approach, which non-intrusively collects data on addresses issued by the microprocessor, analyzes that data to predict the best cache configuration, and then updates the cache to the new best configuration in "one-shot", without ever having to examine inferior configurations. The result is less energy and less performance overhead, meaning that cache tuning can be applied more frequently. We show through experiments that the one-shot cache tuner can reduce memory-access related energy for instructions by 35% and comes within 4% of a previous intrusive approach, and results in 4.6 times less energy overhead and a 7.7 times speedup in tuning time compared to a previous intrusive approach, at the main expense of 12% larger size

Parameterized components are becoming more commonplace in system design. The process of customizing parameter values for a particular application, called tuning, can be a challenging task for a designer. Here we focus on the problem of tuning a parameterized soft-core microprocessor to achieve the best performance on a particular application, subject to size constraints. We map the tuning problem to a well-established statistical paradigm called design of experiments (DoE), which involves the design of a carefully selected set of experiments and a sophisticated analysis that has the objective to extract the maximum amount of information about the effects of the input parameters on the experiment. We apply the DoE method to analyze the relation between input parameters and the performance of a soft-core microprocessor for a particular application, using only a small number of synthesis/execution runs. The information gained by the analysis in turn drives a soft-core tuning heuristic. We show that using DoE to sort the parameters in order of impact results in application speedups of 6times-17times versus an un-tuned base soft-core. When compared to a previous single-factor tuning method, the DoE-based method achieves 3times-6times application speedups, while requiring about the same tuning runtime. We also show that tuning runtime can be reduced by 40-45% by using predictive tuning methods already built into a DoE tool

The integration of microprocessors and field-programmable gate array (FPGA) fabric on a single chip increases both the utility and necessity of tools that automatically move software functions from the microprocessor to accelerators on the FPGA to improve performance or energy. Such hardware/software partitioning for modern FPGAs involves the problem of partitioning functions among two levels of accelerator groups - tightly-coupled accelerators that have fast single-clock-cycle memory access to the microprocessor's memory, and loosely-coupled accelerators that access memory through a bridge to avoid slowing the main clock period with their longer critical paths. This new two-level accelerator-partitioning problem was introduced, and a novel optimal dynamic programming algorithm was described to solve the problem. By making use of the size constraint imposed by FPGAs, the algorithm has what is effectively quadratic runtime complexity, running in just a few seconds for examples with up to 25 accelerators, obtaining an average performance improvement of 35% compared to a traditional single-level bus architecture

Modern systems-on-a-chip platforms support multiple clock domains, in which different sub-circuits are driven by different clock signals. Although the frequency of each domain can be customized, the number of unique clock frequencies on a platform is typically limited. We define the clock-frequency assignment problem to be the assignment of frequencies to processing modules, each with an ideal maximum frequency, such that the sum of module processing times is minimized, subject to a limit on the number of unique frequencies. We develop a novel polynomial-time optimal algorithm to solve the problem, based on dynamic programming. We apply the algorithm to the particular context of post-improvement of accelerator-based hardware/software partitioning, and demonstrate 1.5times-4times additional speedups using just three clock domains

Modern FPGAs' parallel computing capability and their ability to be reconfigured make them an ideal platform to build accelerators for supercomputing systems. As a multi-core processor, the recently announced Cell Broadband EngineTM1 offers tremendous computing power. In this paper, we introduce a prototype system that combines these two types of computing devices together in a reconfigurable blade and we describe its architecture, memory system and abundant interfaces. On the reconfigurable blade it is desirable that the FPGA devices can be partially reconfigured at run-time. This paper presents the dynamic partial reconfiguration (DPR) technique and its design flow for the reconfigurable blade. We report our experimental results of the blade doing partial reconfiguration. DPR allows the reconfigurable blade to be a powerful, run-time changeable computing engine. A sample application is presented that was both simulated for the Cell processor and dynamically loaded to run on the FPGA.

Recent high-level synthesis approaches and C-based hardware description languages attempt to improve the hardware design process by allowing developers to capture desired hardware functionality in a well-known high-level source language. However, these approaches have yet to achieve wide commercial success due in part to the difficulty of incorporating such approaches into software tool flows. The requirement of using a specific language, compiler, or development environment may cause many software developers to resist such approaches due to the difficulty and possible instability of changing well-established robust tool flows. Thus, in the past several years, synthesis from binaries has been introduced, both in research and in commercial tools, as a means of better integrating with tool flows by supporting all high-level languages and software compilers. Binary synthesis can be more easily integrated into a software development tool-flow by only requiring an additional backend tool, and it even enables completely transparent dynamic translation of executing binaries to configurable hardware circuits. In this article, we survey the key technologies underlying the important emerging field of binary synthesis. We compare binary synthesis to several related areas of research, and we then describe the key technologies required for effective binary synthesis: decompilation techniques necessary for binary synthesis to achieve results competitive with source-level synthesis, hardware/software partitioning methods necessary to find critical binary regions suitable for synthesis, synthesis methods for converting regions to custom circuits, and binary update methods that enable replacement of critical binary regions by circuits.

Numerous variations of configurable caches, having variable parameters like total size, line size, and associativity, have been proposed in commercial microprocessors in recent years. Tuning a configurable cache to a target application has been shown to reduce memory-access power by over 50%. However, searching the configuration space for the best configuration can require much time or power, even when using recent cache tuning heuristics. We sought to determine, for a particular domain of applications, the smallest subset of cache configurations that would still enable effective tuning. For a suite of 34 benchmarks and a cache with 18 possible configurations, we determine through an exhaustive search of all possible subsets, that only 3 or 4 candidate configurations are necessary to support tuning. We introduce a new heuristic, adapted from an efficient and effective heuristic developed for data mining, to quickly determine the best configurations for any sized subset, with near optimal results. We then consider a configurable cache with 17,640 possible configurations and improve our heuristic to include a pre-pruning step, yielding near optimal tuning results. We conclude that only 3 or 4 possible cache configurations are needed to offer a near optimal configuration for every benchmark in our suite - resulting in a 91% reduction in design space exploration time over a state-of-the-art cache tuning heuristic.

Soft-core microprocessors mapped onto field-programmable gate arrays (FPGAs) represent an increasingly common embedded software implementation option. Modern FPGA soft-cores are parameterized to support application-specific customization, wherein pre-defined units, such as a multiplication unit or floating-point unit, may be included in the microprocessor architecture to speed up software execution at the expense of increased size. We introduce a methodology for fast applicationspecific customization of a parameterized FPGA soft core, using synthesis and execution to obtain size and performance data in order to create a tool that can be used across a variety of tool platforms and FPGA devices. As synthesizing a soft core takes tens of minutes, developing heuristics that execute in an acceptable time of an hour or two, yet find near-optimal results, is

Soft-core programmable processors on field-programmable gate arrays (FPGAs) can be custom synthesized to instantiate only those hardware units, such as multipliers and floating-point units, that an application requires to meet performance demands, thus minimizing soft-core size on the FPGA. Conjoining processors, meaning to share hardware units among two or more processors, can further reduce soft-core size, leaving more resources for other circuits such as custom coprocessors. Using Xilinx MicroBlaze coprocessors and standard embedded system benchmarks, we show that conjoining two processors can provide 16% processor size reductions on average, with less than 1% cycle count overhead. We introduce an efficient dynamic-programming-based exploration method to find the best custom instantiation of hardware units, considering both standalone and conjoined options, for soft-core processors.

Although many recent advances have been made in hardware synthesis techniques from software programming languages such as C, the performance of synthesized hardware commonly suffers due to the use of C constructs and coding practices that are not appropriate for hardware. Most previous approaches to addressing this problem require drastic changes to coding practice. We present an approach that instead requires only minimal changes but yields significant speedups. In this approach, a software developer initially writes C code as they normally would, and then applies simple refinement guidelines to only the performance-critical code regions, which are the regions most likely to be synthesized to hardware. Alternatively, if a designer is aware of performance-critical parts of the application, the guidelines could be followed during development. In this study, we analyze dozens of embedded benchmarks to determine the most common C coding practices that limit hardware performance, and introduce coding guidelines to make the code more amenable to synthesis. Those guidelines typically require minimal coding effort, generally consisting of less than ten lines of code for each guideline. The guidelines typically represent modifications that require designer knowledge, making the guidelines difficult or impossible for synthesis tools to automate. We apply these guidelines to six benchmarks, resulting in average speedups of 3.5x compared to synthesis from the original code with a negligible software size and performance overhead.

We describe a new processing architecture, known as a warp processor, that utilizes a field-programmable gate array (FPGA) to improve the speed and energy consumption of a software binary executing on a microprocessor. Unlike previous approaches that also improve software using an FPGA but do so using a special compiler, a warp processor achieves these improvements completely transparently and operates from a standard binary. A warp processor dynamically detects the binary's critical regions, reimplements those regions as a custom hardware circuit in the FPGA, and replaces the software region by a call to the new hardware implementation of that region. While not all benchmarks can be improved using warp processing, many can, and the improvements are dramatically better than those achievable by more traditional architecture improvements. The hardest part of warp processing is that of dynamically reimplementing code regions on an FPGA, requiring partitioning, decompilation, synthesis, placement, and routing tools, all having to execute with minimal computation time and data memory so as to coexist on chip with the main processor. We describe the results of developing our warp processor. We developed a custom FPGA fabric specifically designed to enable lean place and route tools, and we developed extremely fast and efficient versions of partitioning, decompilation, synthesis, technology mapping, placement, and routing. Warp processors achieve overall application speedups of 6.3X with energy savings of 66% across a set of embedded benchmark applications. We further show that our tools utilize acceptably small amounts of computation and memory which are far less than traditional tools. Our work illustrates the feasibility and potential of warp processing, and we can foresee the possibility of warp processing becoming a feature in a variety of computing domains, including desktop, server, and embedded applications.

Field programmable gate arrays (FPGAs) provide designers with the ability to create hardware circuits quickly. Increases in FPGA configurable logic capacity and decreasing FPGA costs have enabled designers to incorporate FPGAs more readily in their designs. FPGA vendors have begun providing configurable soft processor cores that can be synthesized onto their FPGA products. While FPGAs with soft processor cores provide designers with increased flexibility, such processors typically have degraded performance and energy consumption compared to hard-core processors. Previously, we proposed warp processing, a technique capable of optimizing a software application by dynamically and transparently re-implementing critical software kernels as custom circuits in on-chip configurable logic. We now study the potential of a MicroBlaze soft-core based warp processing system to eliminate the performance and energy overhead of a soft-core processor compared to a hard-core processor. We demonstrate that the soft-core based warp processor achieves average speedups of 5.8 and energy reductions of 57% compared to the soft core alone. Our data shows that a soft-core based warp processor yields performance and energy consumption competitive with existing hard-core processors, thus expanding the usefulness of soft processor cores on FPGAs to a broader range of applications.

The advent of sensor networks presents untapped opportunities for synthesis. We examine the problem of synthesis of behavioral specifications into networks of programmable sensor blocks. The particular behavioral specification we consider is an intuitive user-created network diagram of sensor blocks, each block having a pre-defined combinational or sequential behavior. We synthesize this specification to a new network that utilizes a minimum number of programmable blocks in place of the predefined blocks, thus reducing network size and hence network cost and power. We focus on the main task of this synthesis problem, namely partitioning pre-defined blocks onto a minimum number of programmable blocks, introducing the efficient but effective PareDown decomposition algorithm for the task. We describe the synthesis and simulation tools we developed. We provide results showing excellent network size reductions through such synthesis and significant speedups of our algorithm over exhaustive search while obtaining near-optimal results for 15 real network designs as well as nearly 10000 randomly generated designs.

We present a software compilation approach for microprocessor/FPGA platforms that partitions a software binary onto custom hardware implemented in the FPGA. Our approach imposes fewer restrictions on software tool flow than previous compiler approaches, allowing software designers to use any software language and compiler. Our approach uses a back-end partitioning tool that utilizes decompilation techniques to recover important high-level information, resulting in performance comparable to high-level compiler-based approaches.

Just-in-time (JIT) compilation has been used in many applications to enable standard software binaries to execute on different underlying processor architectures. We previously introduced the concept of a standard hardware binary, using a just-in-time compiler to compile the hardware binary to a field-programmable gate array (FPGA). Our JIT compiler includes lean versions of technology mapping, placement, and routing algorithms, of which routing is the most computationally and memory expensive step. As FPGAs continue to increase in size, a JIT FPGA compiler must be capable of efficiently mapping increasingly larger hardware circuits. In this paper, we analyze the scalability of our lean on-chip router, the Riverside on-chip router (ROCR), for routing increasingly large hardware circuits. We demonstrate that ROCR scales well in terms of execution time, memory usage and circuit quality, and we compare the scalability of ROCR to the well known versatile place and route (VPR) timing-driven routing algorithm, comparing to both their standard routing algorithm and their fast routing algorithm. Our results show that on average ROCR executes 3 times faster using 18 times less memory than VPR. ROCR requires only 1% more routing resources, while creating a critical path 30% longer VPR's standard timing-driven router. Furthermore, for the largest hardware circuit, ROCR executes 3 times faster using 14 times less memory, and results in a critical path 2.6% shorter than VPR's fast timing-driven router.

Just-in-time (JIT) compilation has been used in many applications to enable standard software binaries to execute on different underlying processor architectures, yielding software portability benefits. We previously introduced the concept of a standard hardware binary to achieve similar portability benefits for hardware, using a JIT compiler to compile the hardware binary to an FPGA. Our JIT compiler includes lean versions of technology mapping, placement, and routing algorithms that implement the standard hardware binary on a simple custom FPGA fabric designed specifically for JIT compilation. While directly implementing a custom FPGA fabric on silicon may be feasible for some applications, we investigated the option of implementing the simple FPGA fabric as a circuit mapped to a physical FPGA - a virtual FPGA. We described our simple fabric in structural VHDL, synthesized the fabric onto a Xilinx Spartan-IIE FPGA, and mapped 18 benchmark circuits onto the resulting virtual FPGA. Our results show a 6X decrease in performance and a 100X increase in hardware resource usage for the virtual FPGA approach compared to mapping the circuits directly to the physical FPGA. For applications in which hardware portability is essential, a designer could leverage the large capacity of current commercially available FPGAs to implement a virtual FPGA with tens of thousands of configurable gates, providing about the same amount of configurable logic as FPGAs produced in the mid 1990s. Nevertheless, the large overheads clearly indicate the need to develop a virtual FPGA approach tuned to physical fabrics in order to reduce the overhead.

Recent works demonstrate several benefits of synthesizing software binaries onto FPGA hardware, including incorporating hardware design into established software tool flows with minimal impact, porting existing binaries to FPGAs, and even dynamically synthesizing software kernels to faster FPGA coprocessors. Those works showed that standard binary decompilation methods can recover enough high-level control information to result in reasonably-efficient hardware. However, recent synthesis methods for FPGAs utilize advanced memory structures, such as a "smart buffer," that require recovery of additional high-level information, specifically information about loops and arrays. We incorporate decompilation techniques into an existing binary synthesis tool flow to recover loops and arrays in order to take advantage of advanced memory structures when performing synthesis from a binary. We demonstrate through experiments on six benchmarks that our methods improve binary synthesis performance by 53%, by making effective use of smart buffers. Furthermore, we compare the binary results using smart buffers with results of synthesis directly from the original C code for the benchmarks, and show that our methods achieved almost identical performance results with only 10% area overhead.

The instruction cache is a popular target for optimizations of microprocessor-based systems because of the cache's high impact on system performance and power, and because of the cache's predictable temporal and spatial locality. Optimization techniques can be designed based on this predictability. We explore for the first time the interplay of two popular instruction cache optimization techniques: the long-known technique of code reordering and the relatively-new technique of cache configuration. We address the question of whether those two optimizations complement each other or if one optimization dominates the other. Through experiments using embedded system benchmarks, we show that cache configuration dominates a particular category of code reordering techniques with respect to optimizing performance and energy, obviating the need for reordering. We also examine the modern scenario of synthesized custom caches, and show that combining cache configuration with code reordering results in cache size reductions of 13% on average, and up to 89% in some benchmarks, beyond just cache configuration alone.

Existing ASIPs (application-specific instruction-set processors) and compiler-based co-processor synthesis approaches meet the increasing performance requirements of embedded applications while consuming less power than high-performance gigahertz microprocessors. However, existing approaches place restrictions on software languages and compilers. Binary-level co-processor generation has previously been proposed as a complementary approach to reduce impact on tool restrictions, supporting all languages and compilers, at the cost of some decrease in performance. In a binary-level approach, decompilation recovers much of the high-level information, like loops and arrays, needed for effective synthesis, and in many cases yields hardware similar to that of a compiler-based approach. However, previous binary-level approaches have not considered the effects of software compiler optimizations on the resulting hardware. In this paper, we introduce two new decompilation techniques, strength promotion and loop rerolling, and show that they are necessary to synthesize an efficient custom hardware coprocessor from a binary in the presence of software compiler optimizations. In addition, unlike previous approaches, we show the robustness of binary-level co-processor generation by achieving order of magnitude speedups for binaries generated for three different instruction sets, MIPS, ARM, and MicroBlaze, using two different levels of compiler optimizations.

We describe the development of a set of embedded system building blocks, known as eBlocks. An eBlock network can be viewed as a basic form of sensor network that can be developed by non-programming engineers, scientists, and others. Each eBlock has a defined function, either one of a few predefined combinational or sequential functions, a custom-programmed function defined by an automated tool, or by user with programming skills. A user creates an application simply by connecting blocks, and possibly performing simple configuration via dials and switches. We have built over 100 physical eBlock prototypes, and tested their usability with over 100 non-programming users to date. We will describe the architecture of the blocks, including design tradeoffs we considered and the benefit of an exploration tool that we developed to help optimize the power and performance of the design. We have also built a graphical eBlock simulator that users can utilize to quickly build and test systems before deployment, and that we have used in experiments with over 300 non-programming users to help us define intuitive block functions and interfaces. We will describe the simulator architecture, as well as a tool that automatically converts a user's eBlock network into a much smaller network of programmable blocks with accompanying automatically generated programs.

Tuning a configurable cache subsystem to an application can greatly reduce memory hierarchy energy consumption. Previous tuning methods use a level one configurable cache only, or a second level with separate instruction and data configurable caches. We instead use a commercially-common unified second level, a seemingly minor difference that actually expands the configuration space from 500 to about 20,000. We develop additive way tuning for tuning a cache subsystem with this large space, yielding 62% energy savings and 35% performance improvements over a non-configurable cache, greatly outperforming an extension of a previous method

Caches contribute to much of a microprocessor system's power and energy consumption. Numerous new cache architectures, such as phased, pseudo-set-associative, way predicting, reactive-associative, way-shutdown, way-concatenating, and highly-associative, are intended to reduce power and/or energy, but they all impose some performance overhead. We have developed a new cache architecture, called a way-halting cache, that reduces energy further than previously mentioned architectures, while imposing no performance overhead. Our way-halting cache is a four-way set-associative cache that stores the four lowest-order bits of all ways' tags into a fully associative memory, which we call the halt tag array. The lookup in the halt tag array is done in parallel with, and is no slower than, the set-index decoding. The halt tag array predetermines which tags cannot match due to their low-order 4 bits mismatching. Further accesses to ways with known mismatching tags are then halted, thus saving power. Our halt tag array has an additional feature of using static logic only, rather than dynamic logic used in highly associative caches, making our cache simpler to design with existing tools. We provide data from experiments on 29 benchmarks drawn from Powerstone, Mediabench, and Spec 2000, based on our layouts in 0.18 micron CMOS technology. On average, we obtained 55% savings of memory-access related energy over a conventional four-way set-associative cache. We show that savings are greater than previous methods, and nearly twice that of highly associative caches, while imposing no performance overhead and only 2% cache area overhead.

Dynamic software optimization methods are becoming increasingly popular for improving software performance and power. The first step in dynamic optimization consists of detecting frequently executed code, or "critical regions." Most previous critical region detectors have been targeted to desktop processors. We introduce a critical region detector targeted to embedded processors, with the unique features of being very size and power efficient and being completely nonintrusive to the software's execution-features needed in timing-sensitive embedded systems. Our detector not only finds the critical regions, but also determines their relative frequencies, a potentially important feature for selecting among alternative dynamic optimization methods. Our detector uses a tiny cache-like structure coupled with a small amount of logic. We provide results of extensive explorations across 19 embedded system benchmarks. We show that highly accurate results can be achieved with only a 0.02 percent power overhead, acceptable size overhead; and zero runtime overhead. Our detector is currently being used as part of a dynamic hardware/software partitioning approach, but is applicable to a wide variety of situations.

Energy consumption is a major concern in many embedded computing systems. Several studies have shown that cache memories account for about 50% of the total energy consumed in these systems. The performance of a given cache architecture is determined, to a large degree, by the behavior of the application executing on the architecture. Desktop systems have to accommodate a very wide range of applications and therefore the cache architecture is usually set by the manufacturer as a best compromise given current applications, technology, and cost. Unlike desktop systems, embedded systems are designed to run a small range of well-defined applications. In this context, a cache architecture that is tuned for that narrow range of applications can have both increased performance as well as lower energy consumption. We introduce a novel cache architecture intended for embedded microprocessor platforms. The cache has three software-configurable parameters that can be tuned to particular applications. First, the cache's associativity can be configured to be direct-mapped, two-way, or four-way set-associative, using a novel technique we call way concatenation . Second, the cache's total size can be configured by shutting down ways. Finally, the cache's line size can be configured to have 16, 32, or 64 bytes. A study of 23 programs drawn from Powerstone, MediaBench, and Spec2000 benchmark suites shows that the configurable cache tuned to each program saved energy for every program compared to a conventional four-way set-associative cache as well as compared to a conventional direct-mapped cache, with an average savings of energy related to memory access of over 40%.

Just-in-time (JIT) compilation has previously been used in many applications to enable standard software binaries to execute on different underlying processor architectures. However, embedded systems increasingly incorporate Field Programmable Gate Arrays (FPGAs), for which the concept of a standard hardware binary did not previously exist, requiring designers to implement a hardware circuit for a single specific FPGA. We introduce the concept of a standard hardware binary, using a just-in-time compiler to compile the hardware binary to an FPGA. A JIT compiler for FPGAs requires the development of lean versions of technology mapping, placement, and routing algorithms, of which routing is the most computationally and memory expensive step. We present the Riverside On-Chip Router (ROCR) designed to efficiently route a hardware circuit for a simple configurable logic fabric that we have developed. Through experiments with MCNC benchmark hardware circuits, we show that ROCR works well for JIT FPGA compilation, producing good hardware circuits using an order of magnitude less memory resources and execution time compared with the well known Versatile Place and Route (VPR) tool suite. ROCR produces good hardware circuits using 13X less memory and executing 10X faster than VPR's fastest routing algorithm. Furthermore, our results show ROCR requires only 10% additional routing resources, and results in circuit speeds only 32% slower than VPR's timing-driven router, and speeds that are actually 10% faster than VPR's routability-driven router.

The power consumed by the memory hierarchy of a microprocessor can contribute to as much as 50% of the total microprocessor system power, and is thus a good candidate for optimizations. We present an automated method for tuning two-level caches to embedded applications for reduced energy consumption. The method is applicable to both a simulation-based exploration environment and a hardware-based system prototyping environment. We introduce the two-level cache tuner, or TCaT - a heuristic for searching the huge solution space of possible configurations. The heuristic interlaces the exploration of the two cache levels and searches the various cache parameters in a specific order based on their impact on energy. We show the integrity of our heuristic across multiple memory configurations and even in the presence of hardware/software partitioning - a common optimization capable of achieving significant speedups and/or reduced energy consumption. We apply our exploration heuristic to a large set of embedded applications. Our experiments demonstrate the efficacy of our heuristic: on average the heuristic examines only 7% of the possible cache configurations, but results in cache sub-system energy savings of 53%, only 1% more than the optimal cache configuration. In addition, the configured cache achieves an average speedup of 30% over the base cache configuration due to tuning of cache line size to the application's needs.

In previous work, we showed the benefits and feasibility of having a processor dynamically partition its executing software such that critical software kernels are transparently partitioned to execute as a hardware coprocessor on configurable logic - an approach we call warp processing. The configurable logic place and route step is the most computationally intensive part of such hardware/software partitioning, normally running for many minutes or hours on powerful desktop processors. In contrast, dynamic partitioning requires place and route to execute in just seconds and on a lean embedded processor. We have therefore designed a configurable logic architecture specifically for dynamic hardware/software partitioning. Through experiments with popular benchmarks, we show that by specifically focusing on the goal of software kernel speedup when designing the FPGA architecture, rather than on the more general goal of ASIC prototyping, we can perform place and route for our architecture 50 times faster, using 10,000 times less data memory, and 1,000 times less code memory, than popular commercial tools mapping to commercial configurable logic. Yet, we show that we obtain speedups (2x on average, and as much as 4x) and energy savings (33% on average, and up to 74%) when partitioning even just one loop, which are comparable to commercial tools and fabrics. Thus, our configurable logic architecture represents a good candidate for platforms that will support dynamic hardware/software partitioning, and enables ultra-fast desktop tools for hardware/software partitioning, and even for fast configurable logic design in general.

Customizing a memory hierarchy to a particular application or applications is becoming increasingly common in embedded system design, with one benefit being reduced energy. Adding a victim buffer to the memory hierarchy is known to reduce energy and improve performance on average, yet victim buffers are not typically found in commercial embedded processors. One problem with such buffers is, while they work well on average, they tend to hurt performance for many applications. We show that a victim buffer can be very effective if it is considered as a parameter in designing a memory hierarchy, like the traditional cache parameters of total size, associativity, and line size. We describe experiments on PowerStone and MediaBench benchmarks, showing that having the option of adding a victim buffer to a direct-mapped cache can reduce memory-access energy by a factor of 3 in some cases. Furthermore, even when other cache parameters are configurable, we show that a victim buffer can still reduce energy by 43%. By treating the victim buffer as a parameter, meaning the buffer can be included or excluded, we can avoid performance overhead of up to 4% on some examples. We discuss the victim buffer in the context of both core-based and pre-fabricated platform based design approaches.

Memory access can account for about half of a microprocessor system's power consumption. Customizing a microprocessor cache's total size, line size and associativity to a particular program is well known to have tremendous benefits for performance and power. Customizing caches has until recently been restricted to core-based flows, in which a new chip will be fabricated. However, several configurable cache architectures have been proposed recently for use in pre-fabricated microprocessor platforms. Tuning those caches to a program is still however a cumbersome task left for designers, assisted in part by recent computer-aided design (CAD) tuning aids. We propose to move that CAD on-chip, which can greatly increase the acceptance of configurable caches. We introduce on-chip hardware implementing an efficient cache tuning heuristic that can automatically, transparently, and dynamically tune the cache to an executing program. We carefully designed the heuristic to avoid any cache flushing, since flushing is power and performance costly. By simulating numerous Powerstone and MediaBench benchmarks, we show that such a dynamic self-tuning cache can reduce memory-access energy by 45% to 55% on average, and as much as 97%, compared with a four-way set-associative base cache, completely transparently to the programmer.

Static energy dissipation in cache memories will constitute an increasingly larger portion of total microprocessor energy dissipation due to nanoscale technology characteristics and the large size of on-chip caches. We propose to reduce the static energy dissipation of an on-chip data cache by taking advantage of the frequent values (FV) that widely exist in a data cache memory. The original FV-based low-power cache design aimed at only reducing dynamic power, at the cost of a 5% slowdown. We propose a better design that reduces both static and dynamic cache power, and that uses a circuit design that eliminates performance overhead. A designer can utilize our architecture by simulating an application and then synthesizing the FVs into an application-specific cache design when values will not change, or by simulating and then writing to an FV-cache with configuration registers when values could change. Furthermore, we describe hardware that can dynamically determine FVs and write to the configuration registers completely transparently. Experiments on 11 Spec 2000 benchmarks show that, in addition to the dynamic power savings, 33% static energy savings for data caches can be achieved.

The speedup over a microprocessor that can be achieved by implementing some programs on an FPGA has been extensively reported. This paper presents an analysis, both quantitative and qualitative, at the architecture level of the components of this speedup. Obviously, the spatial parallelism that can be exploited on the FPGA is a big component. By itself, however, it does not account for the whole speedup. In this paper we experimentally analyze the remaining components of the speedup. We compare the performance of image processing application programs executing in hardware on a Xilinx Virtex E2000 FPGA to that on three general-purpose processor platforms: MIPS, Pentium III and VLIW. The question we set out to answer is what is the inherent advantage of a hardware implementation over a von Neumann platform. On the one hand, the clock frequency of general-purpose processors is about 20 times that of typical FPGA implementations. On the other hand, the iteration level parallelism on the FPGA is one to two orders of magnitude that on the CPUs. In addition to these two factors, we identify the efficiency advantage of FPGAs as an important factor and show that it ranges from 6 to 47 on our test benchmarks. We also identify some of the components of this factor: the streaming of data from memory, the overlap of control and data flow and the elimination of some instruction on the FPGA. The results provide a deeper understanding of the tradeoff between system complexity and performance when designing Configurable SoC as well as designing software for CSoC. They also help understand the one to two orders of magnitude in speedup of FPGAs over CPU after accounting for clock frequencies.

Caches contribute to much of a microprocessor system's power and energy consumption. We have developed a new cache architecture, called a way-halting cache, that reduces energy while imposing no performance overhead. Our way-halting cache is a four-way set-associative cache that stores the four lowest-order bits of all ways' tags into a fully associative memory, which we call the halt tag array. The lookup in the halt tag array is done in parallel with, and is no slower than, the set-index decoding. The halt tag array pre-determines which tags cannot match due to their low-order four bits mismatching. Further accesses to ways with known mismatching tags are then halted, thus saving power. Our halt tag array has an additional feature of using static logic only, rather than dynamic logic used in highly associative caches. We provide data from experiments on 17 benchmarks drawn from MediaBench and Spec 2000, based on our layouts in 0.18 micron CMOS technology. On average, 55% savings of memory-access related energy were obtained over a conventional four-way set-associative cache. We show that energy savings are greater than previous methods, and nearly twice that of highly-associative caches, while imposing no performance overhead and only 2% cache area overhead.

Building a sensor-based system typically requires some programming and electronics expertise. However, some applications require only basic logic transformations and/or state maintenance of sensor information. This paper describes a set of electronic blocks, called eBlocks, that enable non-experts to build basic small-scale sensor-based systems. Each block performs a particular sensing, logic/state, or output function. A user builds a system by connecting blocks together. Each block contains a hidden microprocessor executing a pre-determined low-power compute and communication protocol. A difference between eBlocks and widely known sensor-network nodes is that each eBlock has a specific easy-to-understand function, and thus does not require programming. Further, eBlocks are designed to be connected in particular configurations to create an end application, while traditional nodes form a wireless network that must be programmed to form an application. Our physical prototypes can last for several years or more on a 9-volt battery, or can receive power from wall outlets. We describe the domain of applications for which eBlocks are suitable, including being used to build complete systems or to interface with existing sensor-network compute nodes, and we summarize the eBlock compute/communication protocol. We describe experiments, involving hundreds of users of varying levels of expertise, that demonstrate how systems that otherwise would have taken weeks or more to build can be built by non-experts in just a few minutes using eBlocks.

We present results of extensive hardware/software partitioning experiments on numerous benchmarks. We describe our loop-oriented partitioning methodology for moving critical code from hardware to software. Our benchmarks included programs from PowerStone, MediaBench, and NetBench. Our experiments included estimated results for partitioning using an 8051 8-bit microcontroller or a 32-bit MIPS microprocessor for the software, and using on-chip configurable logic or custom application-specific integrated circuit hardware for the hardware. Additional experiments involved actual measurements taken from several physical implementations of hardware/software partitionings on real single-chip microprocessor/configurable-logic devices. We also estimated results assuming voltage scalable processors. We provide performance, energy, and size data for all of the experiments. We found that the benchmarks spent an average of 80% of their execution time in only 3% of their code, amounting to only about 200 bytes of critical code. For various experiments, we found that moving critical code to hardware resulted in average speedups of 3 to 5 and average energy savings of 35% to 70%, with average hardware requirements of only 5000 to 10,000 gates. To our knowledge, these experiments represent the most comprehensive hardware/software partitioning study published to date.

Memory accesses often account for about half of a microprocessor system's power consumption. Customizing a microprocessor cache's total size, line size, and associativity to a particular program is well known to have tremendous benefits for performance and power. Customizing caches has until recently been restricted to core-based flows, in which a new chip will be fabricated. However, several configurable cache architectures have been proposed recently for use in prefabricated microprocessor platforms. Tuning those caches to a program is still, however, a cumbersome task left for designers, assisted in part by recent computer-aided design (CAD) tuning aids. We propose to move that CAD on-chip, which can greatly increase the acceptance of tunable caches. We introduce on-chip hardware implementing an efficient cache tuning heuristic that can automatically, transparently, and dynamically tune the cache to an executing program. Our heuristic seeks not only to reduce the number of configurations that must be examined, but also traverses the search space in a way that minimizes costly cache flushes. By simulating numerous Powerstone and MediaBench benchmarks, we show that such a dynamic self-tuning cache saves on average 40% of total memory access energy over a standard nontuned reference cache.

We introduce a novel memory architecture that can count the occurrences of patterns on a system's bus, a task known as profiling. Such profiling can serve a variety of purposes, like detecting a microprocessor's software hot spots or frequently used data values, which can be used to optimize various aspects of the system. The memory, which we call ProMem, is based on a pipelined binary search tree structure, yielding several beneficial features, including nonintrusiveness, accurate counts, excellent size and power efficiency, very fast access times, and the use of standard memories with only simple additional logic. The main limitation is that the set of potential patterns must be preloaded into the memory. We describe the ProMem architecture, and show excellent size and performance advantages compared with content-addressable memory (CAM) based designs.

Dynamic software optimization methods are becoming increasingly popular for improving software performance and power. The first step in dynamic optimization consists of detecting frequently executed code, or "critical regions." Previous critical region detectors have been targeted to desktop processors. We introduce a critical region detector targeted to embedded processors, with the unique features of being very size and power efficient, and being completely non-intrusive to the software's execution - features needed in timing-sensitive embedded systems. Our detector not only finds the critical regions, but also determines their relative frequencies, a potentially important feature for selecting among alternative dynamic optimization methods. Our detector uses a tiny cache coupled with a small amount of logic. We provide results of extensive explorations across seventeen embedded system benchmarks. We show that highly accurate results can be achieved with only a 0.02% power overhead and acceptable size overhead. Our detector is currently being used as part of a dynamic hardware/software partitioning approach, but is applicable to a wide-variety of situations.

While Boolean logic minimization is typically used in logic synthesis, logic minimization can be useful in numerous other applications. However, many of those applications, such as Internet Protocol routing table and network access control list reduction, require logic minimization during the application's runtime, and hence could benefit from minimization executing on-chip alongside the application. On-chip minimization can even enable dynamic hardware/software partitioning. We discuss requirements of on-chip logic minimization, and present our new on-chip logic minimization tool, ROCM. We compare with the well-known Espresso logic minimizer and show that ROCM is 10 times smaller, executes 10-20 times faster, and uses 3 times less data memory, with a mere 2% quality penalty, for the routing table and access control list applications. We show that ROCM solves real-sized problems on an ARM7 embedded processor in just seconds.

Partitioning an application among software running on a microprocessor and hardware co-processors in on-chip configurable logic has been shown to improve performance and energy consumption in embedded systems. Meanwhile, dynamic software optimization methods have shown the usefulness and feasibility of runtime program optimization, but those optimizations do not achieve as much as partitioning. We introduce a first approach to dynamic hardware/software partitioning. We describe our system architecture and initial on-chip tools, including profiler, decompiler, synthesis, and placement and routing tools for a simplified configurable logic fabric, able to perform dynamic partitioning of real benchmarks. We show speedups averaging 2.6 for five benchmarks taken from Powerstone, NetBench, and our own benchmarks.

Energy consumption is a major concern in many embedded computing systems. Several studies have shown that cache memories account for about 50% of the total energy consumed in these systems. The performance of a given cache architecture is largely determined by the behavior of the application using that cache. Desktop systems have to accommodate a very wide range of applications and therefore the manufacturer usually sets the cache architecture as a compromise given current applications, technology and cost. Unlike desktop systems, embedded systems are designed to run a small range of well-defined applications. In this context, a cache architecture that is tuned for that narrow range of applications can have both increased performance as well as lower energy consumption. We introduce a novel cache architecture intended for embedded microprocessor platforms. The cache can be configured by software to be direct-mapped, two-way, or four-way set associative, using a technique we call way concatenation, having very little size or performance overhead. We show that the proposed cache architecture reduces energy caused by dynamic power compared to a way-shutdown cache. Furthermore, we extend the cache architecture to also support a way shutdown method designed to reduce the energy from static power that is increasing in importance in newer CMOS technologies. Our study of 23 programs drawn from Powerstone, MediaBench and Spec2000 show that tuning the cache's configuration saves energy for every program compared to conventional four-way set-associative as well as direct mapped caches, with average savings of 40% compared to a four-way conventional cache.

Loops constitute the most executed segments of programs and therefore are the best candidates for hardware software partitioning. We present a set of profiling tools that are specifically dedicated to loop profiling and do support combined function and loop profiling. One tool relies on an instruction set simulator and can therefore be augmented with architecture and micro-architecture features simulation while the other is based on compile-time instrumentation of gcc and therefore has very little slow down compared to the original program We use the results of the profiling to identify the compute core in each benchmark and study the effect of compile-time optimization on the distribution of cores in a program. We also study the potential speedup that can be achieved using a configurable system on a chip, consisting of a CPU embedded on an FPGA, as an example application of these tools in hardware/software partitioning.

Instruction caches have traditionally been used to improve software performance. Recently, several tiny instruction cache designs, including filter caches and dynamic loop caches, have been proposed to instead reduce software power. We propose several new tiny instruction cache designs, including preloaded loop caches, and one-level and two-level hybrid dynamic/preloaded loop caches. We evaluate the existing and proposed designs on embedded system software benchmarks from both the Powerstone and MediaBench suites, on two different processor architectures, for a variety of different technologies. We show on average that filter caching achieves the best instruction fetch energy reductions of 60--80%, but at the cost of about 20% performance degradation, which could also affect overall energy savings. We show that dynamic loop caching gives good instruction fetch energy savings of about 30%, but that if a designer is able to profile a program, preloaded loop caching can more than double the savings. We describe automated methods for quickly determining the best loop cache configuration, methods useful in a core-based design flow.

Profiling an application executing on a microprocessor is part of the solution to numerous software and hardware optimization and design automation problems. Most current profiling techniques suffer from runtime overhead, inaccuracy, or slowness, and the traditional non-intrusive method of using a logic analyzer doesn't work for today's system-on-a-chip having embedded cores. We introduce a novel on-chip memory architecture that overcomes these limitations. The architecture, which we call ProMem, is based on a pipelined binary tree structure. It achieves single-cycle throughput, so it can keep up with today's fastest pipelined processors. It can also be laid out efficiently and scales very well, becoming more efficient the larger it gets. The memory can be used in a wide-variety of common profiling situations, such as instruction profiling, value profiling, and network traffic profiling, which in turn can be used to guide numerous design automation tasks.

We examine the energy savings possible by re-mapping critical software loops from a microprocessor to configurable logic appearing on the same-chip in commodity chips now commercially available. That logic is typically intended to implement peripherals and coprocessors without increasing chip count-but we show that reduced software energy is an additional benefit, making such chips even more useful. We find critical software loops and re-implement them in the configurable logic such that a repeating software task completes sooner, allowing us to put the system in a low-power state for longer periods, thus reducing energy. We use simulations and estimations for a hypothetical device having a 32-bit MIPS processor plus configurable logic, yielding energy savings of 25%, increasing to 39% assuming voltage scaling. We physically measured several examples running on two commercial single-chip devices having an 8-bit 8051 microprocessor plus configurable logic and a 32-bit ARM microprocessor with configurable logic, with energy savings of 71% and 53% respectively, increasing to an estimated 89% and 75% assuming voltage scaling.

Embedded system programs tend to spend much time in small loops. Introducing a very small loop cache into the instruction memory hierarchy has thus been shown to substantially reduce instruction fetch energy. However, loop caches come in many sizes and variations -- using the configuration best on the average may actually result in worsened energy for a specific program. We therefore introduce a loop cache exploration tool that analyzes a particular program's profile, rapidly explores the possible configurations, and generates the configuration with the greatest power savings. We introduce a simulation-based approach and show the good energy savings that a customized loop cache yields. We also introduce a fast estimation-based approach that obtains nearly the same results in seconds rather than tens of minutes or hours.

Partitioning an embedded system application among a microprocessor and custom hardware has been shown to improve the performance, power or energy of numerous examples. The advent of single-chip microprocessor/FPGA platforms makes such partitioning even more attractive. Previous partitioning approaches have partitioned sequential program source code, such as C or C++. We introduce a new approach that partitions at the software binary level. Although source code partitioning is preferable from a purely technical viewpoint, binary-level partitioning provides several very practical benefits for commercial acceptance. We demonstrate that binary-level partitioning yields competitive speedup results compared to source-level partitioning, achieving an average speedup of 1.4 compared to 1.5 for eight benchmarks partitioned on a single-chip microprocessor/FPGA device.

Dynamically-loaded tagless loop caching reduces instruction fetch power for embedded software with small loops, but only supports simple loops without taken branches. Preloaded tagless loop caching supports complex loops with branches and thus can reduce power further, but has a limit on the total number of instructions cached. We show that each does well on particular benchmarks, but neither is best across all of those benchmarks. We present a new hybrid loop cache that only preloads the complex loops, while dynamically loading other loops, thus achieving the strengths of each approach. We demonstrate better power savings than either previous approach alone.

System-on-a-chip (SOC) platform manufacturers are increasingly adding configurable features that provide power and performance flexibility in order to increase a platform's applicability. This paper presents a framework, called Platune, for performance and power tuning of one such SOC platform. Platune is used to simulate an embedded application that is mapped onto the SOC platform and output performance and power metrics for any configuration of the SOC platform. Furthermore, Platune is used to automatically explore the large configuration space of such an SOC platform. The versatility, in terms of accuracy and speed of exploration, of Platune is demonstrated experimentally using three large benchmark examples. The power estimation techniques for processors, caches, memories, buses, and peripherals combined with the design space exploration algorithm deployed by Platune form a methodology for design-of tuning frameworks for parameterized SOC platforms in general.

Reuse of cores can reduce design time for systems-on-a-chip. Such reuse is dependent on being able to easily interface a core to any bus. To enable such interfacing, many propose separating a core's interface from its internals by using a bus wrapper. However, this separation can lead to a performance penalty when reading a core's internal registers. In this paper, we introduce prefetching, which is analogous to caching, as a technique to reduce or eliminate this performance penalty, involving a tradeoff with power and size. We describe the prefetching technique, classify different types of registers, describe our initial prefetching architectures and heuristics for certain classes of registers, and highlight experiments demonstrating the performance improvements and size/power tradeoffs. We further introduce a technique for automatically designing a prefetch unit that satisfies user-imposed register-access constraints. The technique benefits from mapping the prefetching problem to the well-known real-time process scheduling problem. We then extend the technique to allow user-specified register interdependencies, using a Petri net model, resulting in even more efficient prefetch schedules.

Many computer-aided design problems involve solutions that require the partitioning of a large sequential program written in a language such as C or VHDL. Such partitioning can improve design metrics such as performance, power, energy, size, input/output lines, and even CAD tool run-time and memory requirements, by partitioning among hardware modules, hardware and software processors, or even among time-slices in reconfigurable computing devices. Previous partitioning approaches typically preselect the granularity at which the program is partitioned. In this article, we define three distinct partitioning steps: procedure determination, preclustering, and N -way partitioning, with the first two steps focusing on granularity selection. Using three steps instead of one can provide for a more thorough design space exploration and for faster partitioning. We emphasize the first two steps in this article since they represent the most novel aspects. We illustrate the approach on an example, provide results of several experiments, and point to the need for future research that more fully automates the three-step approach.

In this work, we provide a technique for efficiently exploring the power/performance design space of a parameterized system-on-chip (SOC) architecture to find all Pareto-optimal configurations. These Pareto-optimal configurations will represent the range of power and performance tradeoffs that are obtainable by adjusting parameter values for a fixed application that is mapped on the SOC architecture. Our approach extensively prunes the potentially large configuration space by taking advantage of parameter dependencies. We have successfully applied our technique to explore Pareto-optimal configurations of our SOC architecture for a number of applications.

Various core-based power evaluation approaches for microprocessors, caches, memories and buses have been proposed in the past. We propose a new power evaluation technique that is targeted toward peripheral cores. Our approach is the first to combine for peripherals both gate-level-obtained power data with a system-level simulation model written in an object-oriented language. Our approach decomposes peripheral functionality into so-called instructions. The approach can be applied with three increasingly fast methods: system simulation, trace simulation or trace analysis. We show that our models are sufficiently accurate in order to make power-related system-level design decisions but at a computation time that is orders of magnitude faster than a gate-level simulation.

Our earlier work for fast evaluation of power consumption of general cores in a system-on-a-chip described techniques that involved isolating high-level instructions of a core, measuring gate-level power consumption per instruction, and then annotating a system-level simulation model with the obtained data. In this work, we describe a method for speeding up the evaluation further, through the use of instruction traces and trace simulators for every core, not just microprocessor cores. Our method shows noticeable speedups at an acceptable loss of accuracy. We show that reducing trace sizes can speed up the method even further. The speedups allow for more extensive system-level power exploration and hence better optimization.

Provides a technique for efficiently exploring the configuration space of a parameterized system-on-a-chip (SOC) architecture to find all Pareto-optimal configurations. These configurations represent the range of meaningful power and performance tradeoffs that are obtainable by adjusting parameter values for a fixed application mapped onto the SOC architecture. The approach extensively prunes the potentially large configuration space by taking advantage of parameter dependencies. The authors have successfully incorporated the technique into the parameterized SOC tuning environment (Platune) and applied it to a number of applications.

We describe an approach for a microprocessor to tune itself to its fixed application to reduce power in an embedded system. We define a basic architecture and methodology supporting a microprocessor self-optimizing mode. We also introduce a loop table as a tunable component, although self-optimization can be done for other tunable components too. We highlight experimental results illustrating good power reductions with no performance penalty. Keywords System-on-a-chip, self-optimizing architecture, embedded systems, parameterized architectures, cores, low-power, tuning, platforms.

Architectures with parameterizable cache and bus can support large tradeoffs between performance and power. We provide simulation data showing the large tradeoffs by such an architecture for several applications and demonstrating that the cache and bus should be configured simultaneously to find the optimal solutions. Furthermore, we describe analytical techniques for speeding up the cache/bus power and performance evaluation by several orders of magnitude over simulation, while maintaining sufficient accuracy with respect to simulation-based approaches.

Reducing power consumption has become a key goal for systemon-a-chip (SOC) designs. Fast and accurate power estimation is needed early in the design process, since power reduction methods tend to have greater impact at higher abstraction levels. Unfortunately, current approaches to power estimation, which concentrate on register-transfer-level models or lower, are quite slow. Higherlevel approaches, while faster, may suffer from inaccuracy. However, the advent of cores enables a hybrid approach, described in this paper, yielding both fast and accurate estimates from high-level models. In particular, we use power estimation data obtained from the gate-level for a core’s representative input stimuli data (instructions), and we propagate this data to a higher (object-oriented) system-level model, which is parameterizable and executable. Depending on the kind of cores, various parameterizable equation or look-up table based techniques are used, resulting in self-analyzing core models. We have applied our technique to several cores of a digital camera SOC and have achieved simulation speedups of over 1000 with accuracies suitable for making reliable power-related system-level design decisions. Although we focus on power estimation, our approach can be used for estimating other metrics as well, such as performance and size. 1

We describe an automated environment to assist a system-on-achip designer to tune a microprocessor core to a particular application program that will run on the microprocessor, and vice-versa, with the goal of reducing embedded system power consumption.We limit such tuning to modifications that do not change the microprocessor instruction set, thus avoiding the large costs that would come with such a change.Our tuning environment for the 8051 microcontroller is freely-available on the web.

We present a technique for fast estimation of the power consumed by the cache and bus sub-system of a parameterized system-on-a-chip design for a given application. The technique uses a two-step approach of first collecting intermediate data about an application using simulation, and then using equations to rapidly predict the performance and power consumption for each of thousands of possible configurations of system parameters, such as cache size and associativity and bus size and encoding. The estimations display good absolute as well as relative accuracy for various examples, and are obtained in dramatically less time than other techniques, making possible the future use of powerful search heuristics.

Today's system-on-a-chip designs consist of many cores, To enable cores to be easily integrated into different systems, many propose creating cores with their internal logic separated from their wrapper. This separation may introduce extra read latency. Pre-fetching register data into register copies in the bus wrapper can reduce or eliminate this extra latency. In this paper, we introduce a technique for automatically designing a pre-fetch unit that satisfies user-imposed register-access constraints. The technique benefits from mapping the pre-fetching problem to the well-known real-time process scheduling problem. We then extend the technique to allow user-specified register interdependencies, using a Petri net model, resulting in even more efficient pre-fetch schedules.

Previous work has shown that sizable power reductions can be achieved by shutting down a system's sub-circuits when they are not needed. However, these shutdown techniques focus on shutting down only portions of the controller or the datapath of a single custom hardware processor. We propose a higher level shutdown technique that considers both the controller and datapath simultaneously; in particular, we partition a processor into multiple simpler mutually-exclusive communicating processors, and then shut down the inactive processors (i.e., the inactive controller/datapath pairs). Power reduction is accomplished because only one smaller processor is active at a time. In addition to power reduction, functional partitioning also provides solutions to a variety of synthesis problems and does not require the modification of the synthesis tool. We present results showing that this FSMD functional partitioning technique can reduce power, on average, 42% over unoptimized systems.

Minimizing power consumption is of paramount importance during the design of embedded (mobile computing) systems that come as systems-on-a-chip, since interdependencies between design characteristics like power, performance and area for various system parts (cores) are becoming increasingly influential. In this scenario, interfaces play a key role, since they allow one to control/exploit these interdependencies with the aim of meeting design constraints like power. In this paper, we present a comprehensive approach to explore this impact. We consider a whole system comprising a CPU, caches, a main memory and interfaces between those cores, and we demonstrate the high impact that an adequate adaptation between core parameters and interface parameters has in terms of power consumption. We find in particular that cache parameters and the configurations of cache buses have a significant impact in this respect. In addition, we make the important observation that optimizing for performance no longer implies that power is optimized as well in deep submicron technologies. Instead, we find that, especially for newer technologies, the relative interface power contribution increases, leading to scenarios where we obtain a real power/performance tradeoff. In summary, our explorations have revealed as yet uninvestigated interdependencies that represent the first step towards future efforts to optimize/adapt interfaces and caches in core-based systems for low-power designs.

Recent work has demonstrated numerous benefits of functionally partitioning a behavioral process into mutually exclusive subprocesses before synthesizing each process into a custom digital-hardware processor. A key problem during partitioning is minimizing the input/output (I/O) pins or wires between processors. The traditional structural partitioning approach is strongly restricted by such I/O. We previously showed that the new approach of functional partitioning eases this restriction. We now demonstrate a further relaxation of the I/O restriction by introducing the FunctionBus interprocessor bus and the port-calling functional transformation. The FunctionBus allows choice of any size for internal I/O by trading off I/O size for performance, while port calling allows distribution of external I/O almost arbitrarily among modules. We describe experiments showing large I/O reductions through these techniques, with only small performance penalties.

Functional partitioning assigns the functions of a system's program-like specification among system components, such as standard-software and custom-hardware processors. We introduce a new transformation, called procedure cloning, that significantly improves functional partitioning results. The transformation creates a clone of a procedure for sole use by a particular procedure caller, so the clone can be assigned to the caller's processor, which in turn improves performance through reduced communication. Heuristics are used to prevent the exponential size increase that could occur if cloning were done indiscriminately. We introduce a variety of cloning heuristics, highlight experiments demonstrating the improvements obtained using cloning, and compare the various cloning heuristics.

We present the SpecSyn system-level design environment supporting the specify-explore-re#ne #SER# design paradigm. This three-step approach includes precise speci#cation of system functionality, rapid exploration of numerous systemlevel design options, and re#nement of the speci#cation into one re#ecting the chosen option. A system-level design option consists of an allocation of system components like standard and custom processors, and a partitioning of functionality among those components. Focusing on SpecSyn's exploration techniques, we emphasize its two-phase estimation approach and highlight experiments using SpecSyn. 1 Introduction The focus of design e#ort on higher abstraction levels, driven by increasing system complexity, shorter design times, and migration of entire systems onto a single chip, demands a system-level design methodology and supporting tools. We can isolate three tasks in such a methodology. First, wemust specify the system's functionality and constraints. S...

Incorporating functional partitioning into a synthesis methodology leads to several important advantages. In functional partitioning, we first partition a functional specification into smaller subspecifications and then synthesize structure for each, in contrast to the current approach of first synthesizing structure for the entire specification and then partitioning that structure. One advantage is the improvement in I/O performance and package count, when partitioning among hardware blocks with size and I/O constraints, such as FPGAs or blocks within an ASIC. A second advantage is reduction in synthesis runtimes. We describe these important advantages, concluding that further research on functional partitioning can lead to inproved results from synthesis environments.

System-level design issues are gaining increasing attention, as behavioral synthesis tools and methodologies mature. We present the SpecSyn system-level design environment, which supports the new specify-explore-refine (SER) design paradigm. This three-step approach to design includes precise specification of system functionality, rapid exploration of numerous system-level design options, and refinement of the specification into one reflecting the chosen option. A system-level design option consists of an allocation of system components, such as standard and custom processors, memories, and buses, and a partitioning of functionality among those components. After refinement, the functionality assigned to each component can then he synthesized to hardware or compiled to software. We describe the issues and approaches for each part of the SpecSyn environment. The new paradigm and environment are expected to lead to a more than ten times reduction in design time, and our experiments support this expectation.

We improve upon a new approach for automatically partitioning a system among several FPGAs. The new approach partitions a system's functional specification, now commonly available, rather than its structural implementation. The improvement uses a bus, the FunctionBus, for implementing function calls among FPGA's, The bus can be used with any number of and its protocol uses only a small amount of existing FPGA hardware, requiring no special hardware. While functional rather than structural partitioning can substantially reduce the number of input/output pins using (I/O) the FunctionBus takes such reduction even further. In particular, performance and I/0can be traded-off by varying the bus size, as demonstrated using several examples.

As methodologies and tools for chip-level design mature, design effort becomes focused on increasingly higher levels of abstraction. We present a tutorial on a design methodology for chip and system design and present a test case that justifies the future goal of a 100 h design cycle.

VHDL and other hardware description languages are commonly used as specification languages during system design. However, the underlying model of those languages does not directly support the specification of embedded systems, making the task of specifying such systems tedious and error-prone. We introduce a new conceptual model, called Program-State Machines (PSM), that caters to embedded systems. We describe SpecCharts, a VHDL extension that supports capture of the PSM model. The extensions we describe can also be applied to other languages. SpecCharts can be easily incorporated into a VHDL design environment using automatic translation to VHDL. We highlight several experiments that demonstrate the advantages of significantly reduced specification time, fewer errors, and improved specification readability.>

To aid in the functional partitioning of a system into interacting hardware and software components, fast yet accurate estimations of hardware size are necessary. We introduce a technique for obtaining such estimates in two orders of magnitude less time than previous approaches without sacrificing substantial accuracy, by incrementally updating a design model for a changed partition rather than re-estimating entirely.>

There is a need for capturing behavioral specifications of entire systems and obtaining multi-chip designs from those specifications. The authors discuss system level specification and synthesis issues, along with the unique requirements they place on a specification language. Since no current language meets those requirements, the SpecCharts language was created on top of VHDL (VHSIC Hardware Description Language). The SpecCharts language permits concise, understandable, and accurate specification of systems while supporting the concept of behavioral hierarchy, which considerably aided the specification of hardware systems modeled by the authors. Its constructs aid system level synthesis tasks such as partitioning, estimation, interface synthesis, and bus merging by permitting high level communication, and maintaining information and permitting modification at the level at which most modelers think at.>

It is pointed out that many translation schemes from domain-specific languages to supposedly functionally equivalent VDHL (VHSIC hardware description language) have been developed as an approach to simulation. However, due to a subtle theoretical limitation to this approach, functionally equivalent VHDL cannot be created for the general case, making such translations an unsound technique. The authors propose an alternative approach which strives instead for functionally equivalent simulation, while still taking advantage of VHDL simulators. This method uses a novel time-shift transformation in conjunction with any translation scheme, making correct simulations easily obtainable. This bridges the gap to a sound and advantageous use of VHDL as a tool for simulating domain-specific languages.>