This thesis proposes a automated test case generation technique for the aim of verifying/debugging High-level synthesis (HLS) tools. The work in this thesis builds a framework that automatically generates random programs with user specified features. These programs are used to verify the correctness of the compiled hardware by comparing the hardware simulation results with the software execution results. This way, users can have a large number of benchmarks to test their algorithms for HLS without having to manually develop test programs. The tool also provides additional ways of analyzing performance of HLS tools. Rather than being a replacement, this technique should serve as a useful complement to existing manually constructed test suites. Together, they can provide more comprehensive verification and analysis for HLS tools.

Multi-core machines have become common and have led to an increase in multithreaded software. In turn, the number of concurrency bugs has also increased. Such bugs are elusive and remain difficult to solve, despite existing research. Thus, this thesis proposes a system which detects, prevents and optionally helps expose concurrency bugs. Specifically, we focus on bugs caused by atomicity violations, which occur when thread interleaving violates the programmer’s assumption that a code section executes atomically. At compile-time, our system performs static analysis to identify code sections where violations could occur. At run-time, we use debug registers to monitor these sections for interleaving thread accesses which would cause a violation. If detected, we undo their effects and thus prevent the violation. Optionally, we help expose atomicity violations by perturbing thread scheduling during execution. Our results demonstrate that the system is effective and imposes low overhead.

Peer-assisted Video-on-Demand (VoD) systems have not only received substantial recent research attention, but also been implemented and deployed with success in large-scale real-world streaming systems. Despite the remarkable popularity in real-world systems, the design of such systems are not well understood. In this thesis, we seek to address two design problems in peer-assisted VoD systems. First, we focus on the design of cache replacement algorithms. We construct an analytical framework based on dynamic programming, to help us form an in-depth understanding of optimal strategies to design cache replacement algorithms. Second, we shift our attention to the surplus upload bandwidth allocation problem in multi-channel systems. Through theoretical analysis and realistic simulations, we conclude that surplus upload bandwidth from peers can be utilized more efficiently than conventional prefetching strategies when it is devoted to redistributing content to those channels in deficit state.

Facial feature point detection is a key issue in facial image processing. One main challenge of facial feature point detection is the variation of facial structures due to expressions. This thesis aims to explore more accurate and robust facial feature point detection algorithms, which can facilitate the research on facial image processing, in particular the facial expression analysis. This thesis introduces a facial feature point detection system, where the Multilinear Principal Component Analysis is applied to extract the highly descriptive features of facial feature points. In addition, to improve the accuracy and efficiency of the system, a skin color based face detection algorithm is studied. The experiment results have indicated that this system is effective in detecting 20 facial feature points in frontal faces with different expressions. This system has also achieved a higher accuracy during the comparison with the state-of-the-art, BoRMaN.

Parallel software is now required to exploit the abundance of threads and processors in modern multicore computers. Unfortunately, manual parallelization is too time-consuming and error-prone for all but the most advanced programmers. While automatic parallelization promises threaded software with little programmer effort, current auto-parallelizers are easily thwarted by pointers and other forms of ambiguity in the code. In this dissertation we profile the loops in SPEC CPU2006, categorize the loops in terms of available parallelism, and focus on promising loops that are not parallelized by IBM's XL C/C++ V10 auto-parallelizer. For those loops we propose methods of improved interaction between the programmer and compiler that can facilitate their parallelization. In particular, we (i) suggest methods for the compiler to better identify to the programmer the parallelization-blockers; (ii) suggest methods for the programmer to provide guarantees to the compiler that overcome these parallelization-blockers; and (iii) evaluate the resulting impact on performance.

Modern processors use branch prediction to predict branch outcomes, in order to fetch ahead in the instruction stream, increasing concurrency and performance. Larger predictor tables can improve prediction accuracy, but come at the cost of larger area and longer access delay. This work introduces a new branch predictor design that increases the perceived predictor capacity without increasing its delay, by using a large virtual second-level table allocated in the second-level caches. Virtualization is applied to a state-of-the-art multi- table branch predictor. We evaluate the design using instruction count as proxy for timing on a set of commercial workloads. For a predictor whose size is determined by access delay constraints rather than area, accuracy can be improved by 8.7%. Alternatively, the design can be used to achieve the same accuracy as a non-virtualized design while using 25% less dedicated storage.

With the ever increasing amount of digital information, information workers desire more screen real estate to process their daily desktop work. Thanks to the quick advance in display technology, big screens are increasingly affordable and have been gradually adopted in desktop computing environments. A large wall-size high resolution display, a recent emerging class of display which possesses a huge visualization surface, could potentially benefit information processing work. In this dissertation we investigate such a large display as the primary working space for information processing work. We firstly conducted a longitudinal diary study and three control experiments investigating effects of a large display on information processing work. The longitudinal diary study investigates large display use in a personal desktop computing context by comparing it with single- and dual-monitor. The three controlled experiments further investigate the effects of two factors determining resolution of a display—physical size and pixel-density on users’ performance and behaviors. The diary study reveals the distinct behavior patterns of large display users in partitioning screen space and managing windows, while the control experiments deeply reveal the effects of the physical size and pixel density of a display on different information processing tasks. Aside from studying a continuous large display, we also articulate how interior bezels within a tiled-monitor large display affect users’ performance and behaviors in basic visual search and action tasks via a series of controlled experiments. Based on the understanding of large display effects and users’ behavior patterns, we then design new interaction techniques to address a big challenge of working on a large display: managing overflowing windows. We design and implement a large display oriented window management system prototype: WallTop. It includes a set of interaction techniques that provide greater flexibility for managing windows. Usability tests show that users can quickly and easily learn the new techniques and apply them to realistic window management tasks with increased efficiency on a large display.

The default behavior of all commodity operating systems today is to restart the system when a critical error is encountered in the kernel. This terminates all running applications with an attendant loss of "work in progress" that is non-persistent. Our thesis is that an operating system kernel is simply a component of a larger software system, which is logically well isolated from other components, such as applications, and therefore it should be possible to reboot the kernel without terminating everything else running on the same system. In order to prove this thesis, we designed and implemented a new mechanism, called Otherworld, that microreboots the operating system kernel when a critical error is encountered in the kernel, and it does so without clobbering the state of the running applications. After the kernel microreboot, Otherworld attempts to resurrect the applications that were running at the time of failure. It does so by restoring the application memory spaces, open files and other resources. In the default case it then continues executing the processes from the point at which they were interrupted by the failure. Optionally, applications can have user-level recovery procedures registered with the kernel, in which case Otherworld passes control to these procedures after having restored their process state. Recovery procedures might check the integrity of application data and restore resources Otherworld was not able to restore. We implemented Otherworld in Linux, but we believe that the technique can be applied to all commodity operating systems. In an extensive set of experiments on real-world applications (MySQL, Apache/PHP, Joe, vi), we show that Otherworld is capable of successfully microrebooting the kernel and restoring the applications in over 97\% of the cases. In the default case, Otherworld adds negligible overhead to normal execution. In an enhanced mode, Otherworld can provide extra application memory protection with overhead of between 4% and 12%.

Employing a design solution can satisfy some requirements while having negative side-effects on some other software requirements and project objectives. Ultimately, selecting a design solution among multiple options involves making trade-offs among competing requirements. These trade-offs, especially at the early stages of software development, are often hard to identify or quantify, and can be subjective. Security is one critical requirement among many, which can cause critical trade-offs and severe costs. Damages from security attacks can be overwhelming and the costs increase every year. The threat of vulnerabilities and their exploitation by potential adversaries calls for careful analysis of security risks and trade-offs that security solutions impose, from the viewpoints of both defenders and attackers. Since software developers and analysts are usually not security experts, detecting potential threats within software systems can be problematic. Even when threats are known, the risk factors, either the probability of a successful attack or the resulting damage of a successful attack, are not always known or numerically measurable. In this situation, selecting proper security solutions can be challenging, when mitigating impacts and side-effects of solutions are often not quantifiable. This thesis addresses such challenges in identifying and making trade-offs among security and other system requirements and stakeholders' goals. This work introduces a framework for identifying and modeling security risks and requirements trade-offs. The central idea in this thesis is analyzing security requirements on the basis of predicting software vulnerabilities, weaknesses or flaws that can be exploited to break into the system. Vulnerabilities and exploitation scenarios are specified within goal-oriented requirements models of the system. This approach enables analysis of vulnerability exploitations and their impacts on the running system. The structure of goal-oriented security requirements models enables tracing the ultimate impacts of the exploitations on high-level goals of stakeholders and design objectives. In order to evaluate the risk of vulnerabilities, this framework intertwines the Common Vulnerability Scoring System (CVSS) with security requirements risk assessment. The proposed framework provides a decision aid method that takes into the account risks, competing requirements, security solutions, their impacts on risks, and their side-effects on other requirements, to aid decision makers to select a solution among alternative security solutions. The proposed decision analysis method helps analysts to make requirements trade-offs systematically, in the absence of quantitative data, or when a mixture of both quantitative and qualitative data are available.

As the field programmable gate array (FPGA) industry grows device capacity with Moore's law and expands its market to high performance computing, scalability of its key CAD algorithms emerges as a new priority to deliver a user experience competitive to parallel processors. Among the many walls to overcome, placement stands out due to its critical impact on both frontend synthesis and backend routing. To construct a scalable placement flow, we present three innovations in detailed placement: a legalizer that works well under low whitespace; a wirelength optimizer based on bipartite matching; and a cache-aware annealer. When applied to the hundred-thousand cell IBM benchmark suite, our detailed placer can achieve 27% better wirelength and 8X faster runtime against FastDP, the fastest academic detailed placer reported, and our full placement flow can achieve 101X faster runtime, with 5% wirelength overhead, against VPR, the de facto standard in FPGA placements.