Widespread student adoption of large language models (LLMs) has prompted many CS instructors to assign greater weight to handwritten, proctored assessments. However, this approach struggles to scale as class sizes outpace course staff resources. To address this challenge, our study explores LLM-assisted grading to reduce required grading time. While prior work has emphasized tool accuracy, we evaluate both time and accuracy by comparing outcomes when course staff use an LLM-assisted grader versus Gradescope. We also incorporate a mixed-methods analysis of student and staff perceptions. In a CS1 course of 166 students supported by four teaching assistants (TAs), we observed that LLM-assisted grading reduced overall grading time by 40% compared to Gradescope, with time savings of 48% for exams and 25% for quizzes. Across all assessments, short answer questions showed a 46% time improvement, and free response questions showed a 37% time improvement. In terms of accuracy, accepted regrade requests increased negligibly from 0.1% to 0.5% across three exams and six quizzes. Students were generally neutral about LLM-assisted grading, but stressed the value of TA feedback and oversight. Meanwhile, TAs expressed positive sentiments towards the tool, tempered by concerns of skewed perceptions of students caused by the tool. Overall, these findings indicate that LLM-assisted grading can greatly reduce grading time, with only minor accuracy trade-offs that can be mitigated. As a result, LLM-assisted grading emerges as a promising approach for enhancing grading efficiency in CS courses, meriting further exploration for broader adoption.

Computing Education Research (CER) is increasingly considering digital accessibility, yet the current state of disability inclusion remains unexplored. To understand how and to what extent disabled people and their voices are involved in CER, we conducted a systematic literature review of 68 full papers about accessibility published between 2008 and 2025 in the SIGCSE Technical Symposium, the premiere CER venue. Our analysis reveals that less than half of papers about accessibility involve disabled participants, accessibility research papers are more likely to address visual disabilities or accessibility topics more generally, and use of disability-focused theories or frameworks is uncommon. Based on these findings, we advocate for increased involvement of disabled people in all aspects of computing education research, including in designing and evaluating accessible curricula and prototypes, examining disabled experiences in the classroom, and conducting research itself. We conclude with specific recommendations for methods and frameworks that computing education researchers and teachers can use to meaningfully incorporate disabled perspectives into their practices.

This work investigates the impact of Large Language Models (LLMs) and the COVID-19 pandemic on student behavior with autograder systems in three programming-heavy courses. We examine whether the release of LLMs like ChatGPT and GitHub Copilot, along with post-pandemic effects, has modified student interactions with autograders. Using data from student submissions over five years, totalling over 4,500 students across over 420,000 submissions, we analyze trends in submission behaviors before and after these events. Our methodology involves tracking submission patterns, focusing on timing, frequency, and score.

Computer Science (CS) students at the University of California, Irvine (UCI) have experienced academic probation rates higher than 50%. Particularly concerning, statistical analysis showed that students who self-identified as belonging to an underrepresented group (URG) experienced an even higher probation rate. Moreover, students who entered academic probation were twice as likely to leave the CS program. We designed and conducted a comprehensive survey involving 757 CS1 students at UCI to delve further into their past experiences, challenges, and perspectives to gain further insights into the factors contributing to these trends. Specifically, we studied (1) the role of socioeconomic factors such as mental health, academic preparedness, and computing participation in CS students' success, (2) to what extent these factors affect underrepresented group, first-generation, and female students, and (3) experiences that distinguish the most impacted minority groups. Our findings reveal significant correlations between underperformance in CS1 and socioeconomic factors, including satisfaction with course completion regardless of grade, mental health challenges, and insufficient pre-college math preparation. Many of these factors had strong associations with all minority groups. Moreover, our data shows that most URG students enter the program with weaker math preparation than their peers, often don't have prior programming experience, and once enrolled, they have limited interactions within the CS community. These insights highlight the urgency of redesigning academic support practices to support students with diverse backgrounds and experiences. There is a growing need to implement tailored interventions and support mechanisms for CS students, focusing on addressing the disparities in preparation, perspectives, and experiences. Our findings highlight the pressing need to reevaluate current academic support practices and provide a foundation for developing targeted support programs to guide struggling students toward greater success in CS.

With the mainstream adoption of Large Language Models (LLMs) over the last year, members of both academia and the media have raised concerns around the potential impact on student learning and pedagogy. Many students and educators wonder about the pedagogical fit of this emerging technology. We aim to measure the adoption and perception of LLMs among the CS education community in an R1 University to distinguish reality from hype. To this end, we conduct a large survey study targeting three populations participating in computing courses at the university: intro-sequence students (ISS), experienced students (ES), and faculty. Our survey seeks to gather insight around the different populations' perceptions of LLMs in education, as well as how these perceptions may be changing as LLMs improve. Our results show several significant differences across the views of 760 respondents. Most students report LLMs' un-paralleled potential for quick information access, yet many harbor concerns about their reliability and impact on academic integrity. Additionally, while ES rapidly integrate LLMs into their learning, ISS and faculty remain cautious, highlighting a stark contrast in adoption rates. Faculty are unconvinced of LLMs' educational benefits and are concerned about potential challenges in evaluating students' learning outcomes. LLMs are reshaping pedagogical approaches and student engagement. However, with the notable reservations expressed by certain segments, particularly by faculty and ISS, there is an imperative for careful, informed, and ethical integration to ensure that these tools enhance rather than compromise the educational experience.

This full innovative practice paper describes a computational tool designed to optimally match students to industry-sponsored capstone projects in a software engineering capstone course for Computer Science undergraduates at an R1 University (R1U). In the context of these capstone courses, where students stand at the culmination of their academic journey, aligning students' personal learning goals and existing computing skills with team formations becomes critical. This paper presents the Student-Project Matching Tool (SPMT), created to help students find the best available industry-sponsored projects based on their desired learning outcomes, project requirements, and their interests in each project. To choose the learning outcomes they aim to achieve, students can select from a list of predefined software engineering categories and the skills needed to achieve proficiency in each category. The initial list of technical skills for each category was recorded from job postings on a variety of well-known job-search websites, and was further refined by the capstone program's industry partners. Allowing students to select the skills they will work on ensures that they have opportunities and exposure to the skill sets required for employment while still working on one of their most appealing projects. We have developed and piloted the SPMT, which utilizes student vectors to represent their interests and experiences across various software engineering skill sets. Similarly, this tool uses vectors to represent the skills required by each available project, aligning with the exact dimensions as those of the student vectors. The SPMT calculated Euclidean distances between the student interest and project requirement vectors. Next, the resulting Euclidean distances were multiplied with weights associated with students' level of interest in each industry-sponsored project. Subsequently, we framed the student-project matching process as a linear sum assignment problem, aiming to minimize the total sum of Euclidean distances between each student-project pair. The output of the SPMT process consistently matched students with teams that met their software engineering interests and project priorities. Our results reveal increased engagement and growth toward students' desired learning outcomes and computing skills. Specifically, after the first term of the capstone sequence, most students self-reported higher levels of proficiency growth in the skills within their desired software engineering category. This suggests that the SPMT effectively provides students with valuable learning experiences relevant to their career interests and representative of real-world settings.

More than 50% of Computer Science (CS) students at the University of California, Irvine (UCI) experienced academic probation over a 10-year span. Particularly concerning, underrepresented groups (URG) faced an even higher probation rate, and probation students were twice as likely to leave the CS program.

With the mainstream adoption of Large Language Models (LLMs), members of both academia and the media have raised concerns around their impact on student learning and pedagogy. Many students and educators wonder about the pedagogical fit of this emerging technology. We aim to measure the adoption of and attitudes toward LLMs among the CS student population at an R1 University to determine how students are using these new tools. To this end, we conducted a large survey study targeting two populations participating in computing courses at the university: intro-sequence students (ISS) and experienced students (ES).

Algorithms courses are a core part of many CS programs, but have received little focus in computing education, lacking statistical data about how they are generally taught. To remedy this, we present the results of the first large-scale comprehensive survey of undergraduate introductory algorithms courses at four-year institutions in the United States. Questions in the survey targeted instructor information, course concepts, the ways students are evaluated, challenges instructors encountered, and instructor envisioned improvements. We received 87 responses from 34 different states, across a wide variety of 4-year institutions. The results indicate that algorithms courses vary dramatically in most surveyed areas.

Existing assembly programming simulator tools used for educational instruction are stand-alone programs with aged user-interfaces. These tools are antiquated for modern programmers who are accustomed to powerful IDE environments. VSCode has emerged as the go-to in an academic and industry setting. Dashmips is a MIPS Interpreter and Debugger which adds MIPS assembly programming support to VSCode. The interpreter, developed in Python, has a functional design that is easily customizable and extensible for academic instruction specific to a course. Inline Python documentation automatically generates program usage and help documentation for student support. Additionally, the MIPS interpreter is stand-alone from the debugger and can be utilized on the command-line and programmatically via scripting or a Python program allowing integration into auto-grading frameworks. This demo will provide a brief introduction to the features of Dashmips as an educational tool, including simple setup, one-click debugging, clear visualization of register and memory data, and framework for instructor customizations. A step-by-step tutorial for creating a new program and interacting with the debugging environment will illustrate the accessibility of the environment for modern programmers. Information about Dashmips and the Dashmips Debugger can be found at https://github.com/nbbeeken/dashmips and https://github.com/nbbeeken/dashmips-debugger, respectively.

Most hardware and software venders suggest disabling hardware prefetching in virtualized environments. They claim that prefetching is detrimental to application performance due to inaccurate prediction caused by workload diversity and VM interference on shared cache. However, no comprehensive or quantitative measurements to support this belief have been performed.

We introduce LiPS, a new cost-efficient data and task co-scheduler for MapReduce in a cloud environment. By using linear programming to simultaneously co-schedule data and tasks, LiPS helps to achieve minimized dollar cost globally. We evaluated LiPS both analytically and on Amazon EC2 in order to measure actual dollar charges. The results were significant; LiPS saved 62–81% of the dollar costs when compared with the Hadoop default scheduler and the delay scheduler, while also allowing users to fine-tune the cost-performance tradeoff.

As the trends move towards data outsourcing and cloud computing, the efficiency of distributed data centers increases in importance. Cloud-based services such as Amazon's EC2 rely on virtual machines (VMs) to host MapReduce clusters for large data processing. However, current VM scheduling does not provide adequate support for MapReduce workloads, resulting in degraded overall performance. For example, when multiple MapReduce clusters run on a single physical machine, the existing VMMscheduler does not guarantee fairness across clusters.

This paper presents a new desynchronization algorithm aimed at providing collision-free transmission scheduling for single-hop and acyclic multi-hop wireless sensor networks. The desynchronization approach is resilient to the hidden terminal problem and topology changes. Each node distributively converges upon a single collision-free transmission slot, utilizing only minimal neighbor information. In addition, we propose two strategies which facilitate increased convergence time. We evaluate the proposed algorithm via simulations over a range of network densities on both single-hop and acyclic multi- hop networks. Convergence and throughput comparison are performed against two previously proposed desynchronization algorithms. Finally, using an experimental tested of TelosB motes we verify the performance, practicality, and correctness of the desynchronization algorithm on varying network topologies.

Packet reordering (RO) is an Internet event that degrades the performance of both TCP and UDP-based applications. In this paper, we present an end-to-end measurement study of packet reordering of UDP traffic. The goal of our measurement study is to characterize packet reordering in the current Internet as it is reflected by PlanetLab infrastructure. Overall, our analysis shows that current UDP traffic reordering is consistent to prior 1990's studies, despite increased Internet load and technology advancements. In addition, our study adds to the previous results by identifying additional reordering characteristics. More specifically, we show that packet reordering is asymmetric as well as temporal and site-dependent, packet size does influence the likelihood of reordering, that there exists a time-of-the-day dependency, and reordering primarily exists at two timescales (a few milliseconds or multiple tens of milliseconds).

Synthesizing high-level semantic knowledge from low-level sensor data is an important problem in many sensor network applications. Programming a network to perform such synthesis in situ is especially difficult due to the stringent resource constraints, unreliable wireless communication, and complex distributed algorithms and network protocols required to manipulate the data. Recently, a declarative programming language called Snlog [5] has been developed to address this problem. However, statistical reasoning for modeling noise in the context of sensor networks has not been addressed in Snlog. In this paper, we develop a methodology based on the PRISM [36] framework, which integrates logical and statistical reasoning, for specifying sensor network programs that deal with noisy data and tolerate faults in the network. The relationship between high-level (synthesized) and low-level (observed) data is captured by logical rules, while statistical models are used to specify computations in the presence of noise and faults. We illustrate our methodology with three examples: (i) estimating temperature at various points in a region, (ii) evaluating the trajectory of an object observed by a sensor network, based on the Hidden Markov Model, and (iii) evaluating most reliable communication paths between sensor nodes. We analyze the results of simulations as well as an experimental deployment to evaluate the practical feasibility of our approach.

There is a wide consensus that performance and power consumption of IC designs in deep submicron technologies is mainly dictated by interconnect requirements. Our goal is demonstrate how compilation and architectural techniques can be used to minimize and balance interconnect requirements. Specifically, we target the use of bypass units to reduce routing congestion and eliminate long interconnections while essentially preserving or even improving the throughput requirements. We formulate the bypassing problem, establish its complexity and develop an efficient integer-linear programming (ILP) formulation. In addition to satisfying user specified interconnect requirements, we simultaneously optimize the number of operations and, therefore runtime of the targeted application. The approach is prototyped and evaluated using a platform consisting of the Trimaran architecture and compilation tools and the CPLEX ILP solver.

We have developed a new statistical timing analysis approach that does not impose any assumptions on the nature of manufacturing variability and takes into account an arbitrary model of spatial correlation as well as all types of functional correlations (e.g. reconvergence-based correlations). The starting point for statistical timing analysis is small scale Monte Carlo (MC) simulation. In order to speed-up the MC simulation process we use stratified balanced sampling and postprocessing of the simulation data using non-parametric kernel estimation. The MC simulation and the statistical analysis procedure are interleaved with the calculation of the critical paths. In order to speed up simulation, we identify and simulate only gates relevant for calculation of the clock cycle time. The application of statistical techniques enable not only accurate statistical timing analysis, but also stability and scalability analysis. The approach is evaluated using MCNC benchmarks and yields more than six orders of magnitude speed improvement compared with the standard MC simulation.

In this paper, the classic wire-length estimation problem is addressed and a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing is proposed. These types of models are highly instrumental in formalizing a complete and consistent probabilistic approach to design automation and design closure where, along with optimizing the pertinent cost function, the associated prediction error is also considered. The wire-length prediction model was developed using a combination of parametric and nonparametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics after placement will have a particular length. The model is validated using the learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound, and therefore realistic, instances of designs. The net models were applied to the probabilistic buffer-insertion problem and substantial improvement was obtained in net delay after routing (~ 20%) when compared to a traditional bounding box (BBOX)-based buffer-insertion strategy

ASIC provides more than an order of magnitude advantage in terms of density, speed, and power requirement per gate. However, economic (cost of masks) and technological (deep micron manufacturability) trends favor FPGA as an implementation platform. In order to combine the advantages of both platforms and alleviate their disadvantages, recently a number of approaches, such as structured ASIC/regular fabrics, have been proposed. Our goal is to introduce an approach that has the same objective, but is orthogonal to those already proposed. The idea is to implement several ASIC designs in such a way that they share the datapath, memory structure, and several bottom layers of interconnect, while each design has only a few unique metal layers. We identified and addressed two main problems in our quest to develop a CAD flow for realization of such designs. They are: (i) the creation of the datapath, and (ii) the identification of common and unique interconnects for each design. Both problems are solved optimally using ILP formulations. We assembled a design flow platform using two new programs and the Trimaran and Shade tools. We quantitatively analyzed the advantages and disadvantages of the approach using the Mediabench benchmark suite.

Context-aware applications pose new challenges, including a need for new computational models, uncertainty management, and efficient optimization under uncertainty. Uncertainty can arise at two levels: multiple and single tasks. When a mobile user changes environments, the context changes resulting in the possibility of the user requesting tasks which are specific for the new environment. However as the user moves these requested tasks may no longer be context relevant. Additionally, the runtime of each task is often highly dependent on the input data. We introduce an hierarchical multi-resolution statistical task model that captures relevant aspects at the task and intertask levels, and captures not only uncertainty, but also introduces the notion of utility for the user. We have developed a system of nonparametric statistical techniques for modeling the runtime of a specific task. This model is a framework where we define problems of design and optimization of statistical soft real-time systems (SSRTS). The main algorithmic novelty is a cumulative potential-based task scheduling heuristic for maximizing utility. The heuristic conducts global optimization and induces low runtime overhead. We demonstrate the effectiveness of the scheduling heuristic using a Trimaran-based evaluation platform.

Recently, several wireless sensor network studies demonstrated large discrepancies between experimentally observed communication properties and properties produced by widely used simulation models. Our first goal is to provide sound foundations for conclusions drawn from these studies by extracting relationships between location (e.g. distance) and communication properties (e.g. reception rate) using non-parametric statistical techniques. The objective is to provide a probability density function that completely characterizes the relationship. Furthermore, we study individual link properties and their correlation with respect to common transmitters, receivers and geometrical location. The second objective is to develop a series of wireless network models that produce networks of arbitrary sizes with realistic properties. We use an iterative improvement-based optimization procedure to generate network instances that are statistically similar to empirically observed networks. We evaluate the accuracy of our conclusions using our models on a set of standard communication tasks, like connectivity maintenance and routing.

Recently, several studies have analyzed the statistical properties of low power wireless links in real environments, clearly demonstrating the differences between experimentally observed communication properties and widely used simulation models. However, most of these studies have not performed in depth analysis of the temporal properties of wireless links. These properties have high impact on the performance of routing algorithms.Our first goal is to study the statistical temporal properties of links in low power wireless communications. We study short term temporal issues, like lagged autocorrelation of individual links, lagged correlation of reverse links, and consecutive same path links. We also study long term temporal aspects, gaining insight on the length of time the channel needs to be measured and how often we should update our models.Our second objective is to explore how statistical temporal properties impact routing protocols. We studied one-to-one routing schemes and developed new routing algorithms that consider autocorrelation, and reverse link and consecutive same path link lagged correlations. We have developed two new routing algorithms for the cost link model: (i) a generalized Dijkstra algorithm with centralized execution, and (ii)a localized distributed probabilistic algorithm.

We address the classic wire-length estimation problem and propose a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing. The wire-length prediction model was developed using a combination of parametric and non-parametric statistical techniques. The model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics obtained after placement will have a particular length. The model is validated using both learn-and-test and resubstitution techniques. The model can be used for a variety of purposes, including the generation of a large number of statistically sound and therefore realistic instances of designs. We applied the net models to the probabilistic buffer insertion problem and obtained substantial improvement in net delay after routing.

We propose the use of multiple gateways to significantly reduce latency and energy consumption in multi-hop wireless sensor networks during data aggregation. We have derived efficient integer linear programming formulations as well as a novel negative selection statistically-tuned heuristics. The heuristics are based on newly developed relaxation based lower bounds that are also used to quantify the effectiveness of the proposed heuristics. Our simulation study indicates that the use of gateways can often reduce latency and energy consumption by several times.

Fingerprinting is an approach that assigns a unique and invisible ID to each sold instance of the intellectual property (IP). One of the key advantages fingerprinting-based intellectual property protection (IPP) has over watermarking-based IPP is the enabling of tracing stolen hardware or software. Fingerprinting schemes have been widely and effectively used to achieve this goal; however, their application domain has been restricted only to static artifacts, such as image and audio, where distinct copies can be obtained easily. In this paper, we propose the first generic fingerprinting technique that can be applied to an arbitrary synthesis (optimization or decision) or compilation problem and, therefore to hardware and software IPs. The key problem with design IP fingerprinting is that there is a need to generate a large number of structurally unique but functionally and timing identical designs. To reduce the cost of generating such distinct copies, we apply iterative optimization in an incremental fashion to solve a fingerprinted instance. Therefore, we leverage on the optimization effort already spent in obtaining previous solutions, yet we generate a uniquely fingerprinted new solution. This generic approach is the basis for developing specific fingerprinting techniques for four important problems in VLSI CAD: partitioning, graph coloring, satisfiability, and standard-cell placement. We demonstrate the effectiveness of the new fingerprinting-based IPP techniques on a number of standard benchmarks.

We have developed a new optimization paradigm for solving computationally intractable combinatorial optimization and synthesis problems. The technique, named probabilistic constructive, combines the advantages of both constructive and probabilistic optimization mechanisms. Since it is a constructive approach, it has a relatively short runtime and is amenable for the inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible tradeoff between runtime and the quality of solution, suitability for the superimposition of a variety of control strategies, and simplicity of implementation. After presenting the generic technique, we apply it to a generic NP-complete problem (maximum independent set) and a synthesis and compilation problem (sequential code covering). Extensive experimentation indicates that the new approach provides very attractive tradeoffs between the quality of solution and runtime, often outperforming the best previously published approaches.

Computational forensic engineering (CFE) aims to identify the entity that created a particular intellectual property (IP). Specifically, our goal is to identify the synthesis tool or compiler which was used to produce a specific design or program. Rather than relying on watermarking content or designs, the generic CFE methodology analyzes the statistics of certain features of a given IP and quantizes the likelihood that a well known source has created it. In this paper, we describe the generic methodology of CFE and present a set of techniques that, given a set of compilation tools, identify the one used to generate a particular hardware/software design. The generic CFE approach has four phases: 1) feature and statistics data collection; 2) feature extraction; 3) entity clustering; and 4) validation. In addition to IP protection, the developed CFE paradigm can have other potential applications: optimization algorithm selection and tuning, benchmark selection, and source-verification for mobile code.

Watermarking is one of the most effective mechanisms for intellectual property protection (IPP) of hardware and software artifacts. Numerous watermarking-based IPP techniques have been proposed that satisfy a spectrum of IPP desiderata, including full preservation of functionality, low timing, area and power overhead, transparency to the synthesis and compilation process, and resilience against attacks. Two objectives that are very important, but, until now have not yet been properly addressed, are credibility and fairness. We present a new watermarking technique that specifically targets credibility and fairness. Using a combinatorial result by Valiant and Vazirani, we demonstrate how these two desiderata can be achieved during the watermarking of a satisfiability (SAT) instance. The effectiveness of the technique is demonstrated on both specially created examples, where the number of solutions is known, as well as on common computer-aided design and operational research SAT benchmark instances.

This paper introduces hot potato behavioral synthesis transformation techniques. These techniques add deflection operations in the behavioral description of a computation in such a way that the requirements for two important components of the final implementation cost, the number of registers and the number of interconnects, are significantly reduced. Moreover, we demonstrate how hot potato techniques can be effectively used during behavioral synthesis to minimize the partial scan overhead to make the synthesized design testable.

Recently, a number of watermarking-based intellectual property protection techniques have been proposed. Although they have been applied to different stages in the design process and have a great variety of technical and theoretical features, all of them share two common properties: 1) they are applied solely to optimization problems and 2) do not involve any optimization during the watermarking process. In this paper, we propose the first set of optimization-intensive watermarking techniques for decision problems. In particular, we demonstrate, by example of the Boolean satisfiability (SAT) problem, how one can select a subset of superimposed watermarking constraints so that the uniqueness of the signature and the likelihood of satisfying the satisfiability problem are simultaneously maximized. We have developed three SAT watermarking techniques: adding clauses, deleting literals, and push-out and pull-back. Each technique targets different types of signature-induced constraint superimposition on an instance of SAT problem. In addition to comprehensive experimental validation, we theoretically analyze the potentials and limitations of the proposed watermarking techniques. Furthermore, we analyze the three proposed optimization-intensive watermarking SAT techniques in terms of their suitability for copy detection.

The majority of modern multimedia and mobile systems have two common denominators: quality-of-service (QoS) requirements, such as latency and synchronization, and strict energy constraints. However, until now no synthesis techniques have been proposed for the design and efficient use of such systems. We have two main objectives: conceptual and synthesis. The conceptual objective is to develop a generic practical technique for the automatic development of online adaptive algorithms from efficient off-line algorithms using statistical techniques. The synthesis objective is to introduce the first design technique for QoS low-power synthesis. We introduce a system of provably-optimal techniques that minimize energy consumption of stream-oriented applications under two main QoS metrics: latency and synchronization. Specifically, we study how multiple voltages can be used to simultaneously satisfy hardware constraints and minimize power consumption while preserving the requested level of QoS. The purpose of the off-line algorithm is threefold. First, it is used as input to statistical software which is used to identify important and relevant parameters of the processes. Second, the algorithm provides buffer occupancy rate indicators. Lastly, it provides a way to combine buffer occupancy and QoS metrics to form a fast and efficient online algorithm. The effectiveness of the algorithms is demonstrated on a number of standard multimedia benchmarks.

Majority of modern mobile systems have two common denominators: quality-of-service (QoS) requirements, such as latency and synchronization, and strict energy constraints. However, until now no synthesis techniques have been proposed for the design and efficient use of such systems. We have two main objectives: synthesis and conceptual. The synthesis goal is to introduce the first design technique for quality-of-service (QoS) low power synthesis. The conceptual objective is to develop a generic technique for the automatic development of on-line algorithms from efficient off-line algorithms using statistical techniques.We first summarize a system of provably-optimal techniques that minimize energy consumption of stream-oriented applications under two main QoS metrics: latency and synchronization. Specifically, we study how multiple voltages can be used to simultaneously satisfy hardware requirements and minimize power consumption, while preserving the requested level of QoS in terms of latency and synchronization. The off-line algorithm is used as input to statistical software used to identify important relevant parameters of the processes, buffer occupancy rate indicators, and a way how combine them to form a fast and efficient on-line algorithm which decides which task to run at which voltage. The effectiveness of the algorithms is demonstrated on a number of standard multimedia benchmarks.

We propose the first systematic, sensor-centric approach for quantitative design of sensor network appliances. We demonstrate its use by designing light appliance devices and the associated middleware. We have developed five models which are required to make this problem tractable and to undertake the challenging task of designing light sensor appliances: (i) physical world, (ii) light sensor, (iii) physical phenomenon, (iv) appliance design, and (v) computational model. With these models in place, we present the new design methodology that consists of two mains steps: (1) a procedure for placement of individual sensors of the appliance, and (2) error minimization-based sensor data interpretation middleware. We have developed new optimization techniques for both tasks. A portable light sensor system was designed using the optimization intensive procedure, and its effectiveness demonstrated.

We have developed a generic integer linear programming(ILP)-based engineering change(EC) methodology. The EC methodology has three components: enabling, fast, and preserving. Enabling EC provides a user with the means to specify the amount of flexibility and how this flexibility should be distributed throughout the solution so that one can guarantee that a specific set of EC demands can be satisfied while preserving the quality of the initially obtained solution. Fast EC conducts changes in a fraction of the time needed to solve the problem while preserving or in some cases improving the quality of the initial solution. Preserving EC maintains either user specified components of the solution or as much as possible of the initial solution while still guaranteeing an optimal solution to the altered problem instance. We applied the generic methodology to Boolean Satisfiability (SAT) problem. The effectiveness of all proposed approaches and algorithms is demonstrated on standard benchmarks.

The effectiveness of traditional CAD optimization algorithms is proportional to the accuracy of the targeted objective functions. However, behavioral synthesis tools are not used in isolation; they form a strongly connected design flow where each tool optimizes its own objective function without considering the consequences on the optimization goals of the subsequently applied tools. Therefore, efforts to optimize one aspect of a design often have unforeseen negative impacts on other phases of the design process.

We address location discovery problem in ad-hoc wireless Networks. Location discovery is a task with fundamental role in multi-hop wireless networks since many other middleware tasks, such as coverage, tracking and routing, as well as many applications need accurate location of nodes. We have developed simple, yet accurate mathematical abstraction of the problem. We have also developed an atomic tri-lateration procedure for calculating the position of a node in presence of measurements errors. We have statistically analyzed the procedure with respect to a number of parameters, such as error distribution and relative positions of the nodes and used that information for improving effectiveness of the location discovery procedure. Furthermore, we have developed randomized iterative improvement algorithm for fast location discovery in wireless ad-hoc networks. We experimentally verified the exceptional effectiveness of the procedure in presence of errors for both cetralized and localized version of the algorithm.

Recently embedded wireless sensor networks (EWSN) have emerged as a solution to bridge the gap between the physical (and chemical and biological) world and the information world of the Internet. Deployment and effective use of EWSN posses numerous conceptual and technological challenges. In particular, there is a genuine need for the coordinated use of techniques from a variety of scientific and engineering fields, including DSP, computer science, information theory, communication, and applied mathematics. We address the problem of search in sensor networks using techniques from DSP and computer science. The search problem encompasses tasks such as indexing, stream searching, information filtering, semantic and syntax compression, profiling and recommending. The development of search tools will greatly facilitate efforts in many application of sensor networks, including event monitoring, low power operation, and physical space modelling. EWSN also poses unique challenges. For example, in the case of power and storage limitations, the key requirement is distributed space localized processing. The technical highlights of the paper include the first statistical stream search technique, the first technique for simultaneous search of correlated streams and the first technique for effective acquisition of correlated information under bandwidth and power constraints.

The authors introduce an Intellectual Property Protection (IPP) technique for graph partitioning which watermarks solutions to the graph partitioning problems so that they carry an author's signature. This technique is completely transparent to the actual computer-aided design tool which does the partitioning and is implemented by preprocessing and postprocessing alone. The authors propose five different schemes for the watermarking of partitioning solutions. The goal is to construct a partitioning solution which not only has a small edge cut, but also encodes the signature of the author. The key idea of all of our schemes is to map the signature into a set of constraints and then satisfy a disproportionate number of these constraints. Four of our schemes are based upon the idea of encouraging groups of vertices to be in the same partition. The fifth is based upon the encouragement of certain edges to be cut by the partitioning. The fifth scheme shows superior performances on all of the cases which we tested, including both two-way and multiway partitioning. The watermarking scheme produces solutions that have very low-quality degradation levels, yet carry signatures that are convincingly unambiguous, extremely unlikely to be present by coincidence and difficult to detect or remove without completely resolving the partitioning problem.

Watermarking of hardware and software designs is an effective mechanism for intellectual property protection (IPP). Two important criteria for watermarking schemes are credibility and fairness. In this paper, we present the unique solution-based watermarking technique which provides, in a sense, the ultimate answer to both credibility and fairness requirements. Leveraging on a combinatorial theorem of Valiant and Vazirani, we demonstrate how ultimate credibility and complete fairness can almost always be achieved with high probability during the watermarking of the solution of the satisfiability (SAT) problem. The effectiveness of the technique is demonstrated on both specially created examples where the number of solutions is known, as well as on common CAD and operation research SAT instances.

Trends in the semiconductor industry towards extensive design and code reuse motivate a need for adequate Intellectual Property Protection (IPP) schemes. We offer a new general IPP scheme called constraint-based watermarking and analyize it in the context of the graph partitioning problem. Graph partitioning is a critical optimization problem that has many applications, particularly in the semiconductor design process. Our IPP technique for graph partitioning watermarks solutions to graph partitioning problems so that they carry an author's signature. Our technique is transparent to the actual CAD tool which does the partitioning. Our technique produces solutions that have very low quality degradation levels, yet carry signatures that are convincingly unambiguous, extremely unlikely to be present by coincidence, and difficult to detect or remove without completely resolving the partitioning problem.

We propose a new optimization paradigm for solving intractable combinatorial problems. The technique, named Probabilistic Constructive (PC), combines the advantages of both constructive and probabilistic algorithms. The constructive aspect provides relatively short runtime and makes the technique amenable for the inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible trade-off between runtime and the quality of solution. In addition to presenting the generic technique, we apply it to the Maximal Independent Set problem. Extensive experimentation indicates that the new approach provides very attractive trade-offs between the quality of the solution and runtime, often outperforming the best previously published approaches.

Many intellectual property protection (IPP) techniques have been proposed. Their primary objectives are providing convincible proof of authorship with least degradation of the quality of the intellectual property (IP), and achieving robustness against attacks. These are also well accepted as the most important criteria to evaluate different IPP techniques. The essence of such techniques is to limit the solution space by embedding signatures as constraints. One key issue that should be addressed but has not been discussed is the fairness of the techniques: what is the quality of the solution subspace for different signatures, that is, how large the solution subspace is (uniqueness), and how difficulty it is to get a solution from such subspace (hardness)? In this paper, we introduce fairness as one of the metrics for good IPP techniques and post the challenge problem of how to design fair watermarking techniques. We claim that all fair techniques have to be instanceoriented and due to the complexity of the problem itself, we propose an approach that utilizes the statistical information of the problem instance. We use the satisfiability (SAT) problem as an example to illustrate how fairness could be achieved. We make the observation that the unfairness of the previous watermarking techniques comes from the global embedding of the signature and propose fair watermarking techniques. We test the uniqueness and hardness on a model with full knowledge of the solution and real life benchmarks as well. The experimental results show fairness can be achieved. 1

The proliferation of the Internet has affected the business model of almost all semiconductor and VLSI CAD companies that rely on intellectual property (IP) as their main source of revenues. The fact that IP has become more accessible and easily transferable, has influenced the emergence of copyright infringement as one of the most common obstructions to e-commerce of IP.

While previous watermarking-based approaches to intellectual property protection (IPP) have asymmetrically emphasized the IP provider's rights, the true goal of IPP is to ensure the rights of both the IP provider and the IP buyer.Symmetric fingerprinting schemes have been widely and effectively used to achieve this goal; however, their application domain has been restricted only to static artifacts, such as image and audio.In this paper, we propose the first generic symmetric fingerprinting technique which can be applied to an arbitrary optimization/synthesis problem and, therefore, to hardware and software intellectual property.The key idea is to apply iterative optimization in an incremental fashion to solve a fingerprinted instance; this leverages the optimization effort already spent in obtaining a previous solution, yet generates a uniquely fingerprinted new solution.We use this approach as the basis for developing specific fingerprinting techniques for four important problems in VLSI CAD: partitioning, graph coloring, satisfiability, and standard-cell placement.We demonstrate the effectiveness of our fingerprinting techniques on a number of standard benchmarks for these tasks.Our approach provides an effective tradeoff between runtime and resilience against collusion.

Recently, a number of watermarking-based intellectual property protection techniques have been proposed. Although they have been applied to different stages in the design process and have a great variety of technical and theoretical features, all of them share two common properties: they all have been applied solely to optimization problems and do not involve any optimization during the watermarking process. In this paper, we propose the first set of optimization-intensive watermarking techniques for decision problems. In particular, we demonstrate how one can select a subset of superimposed watermarking constraints so that the uniqueness of the signature and the likelihood of satisfying an instance of the satisfiability problem are simultaneously maximized. We have developed three watermarking SAT techniques: adding clauses, deleting literals, push-out and pull-back. Each technique targets different types of signatureinduced constraint superimposition on an instance of the SAT proble...

We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to previous watermarking-based IP protection methods in finding and proving improper use of design IP. After reviewing related literature (notably in the text processing domain), we propose a generic methodology for copy detection based on determining basic elements within structural representations of solutions (IPs), calculating (context-independent) signatures for such elements, and performing fast comparisons to identify potential violators of IP rights. We give example implementations of this methodology in the domains of scheduling, graph coloring and gate-level layout; experimental results show the effectiveness of our copy detection schemes as well as the low overhead of implementation. We remark on open research areas, notably the potentially deep and complementary interaction between watermarking and copy detection.