Embedded systems based on FPGAs frequently incorporate soft processors. The prevalence of soft processors in embedded systems is due to their flexibility and adaptability to the application. However, soft processors provide moderate performance compared to hard cores and custom logic, hence faster performing soft processors are desirable. Many soft processor architectures have been studied in the past including Vector processors and VLIWs. These architectures focus on regular applications in which it is possible to extract data and/or instruction level parallelism offline. However, applications with irregular parallelism only benefit marginally from such architectures. Targeting such applications, we investigate superscalar, out-of-order, and Runahead execution on FPGAs. Although these architectures have been investigated in the ASIC world, they have not been studied thoroughly for FPGA implementations. We start by investigating the challenges of implementing a typical inorder pipeline on FPGAs and propose effective solutions to shorten the processor critical path. We then show that superscalar processing is undesirable on FPGAs as it leads to low clock frequency and high area cost due to wide datapaths. Accordingly, we focus on investigating and proposing FPGA-friendly OoO and Runahead soft processors. We propose FPGA-friendly alternatives for various mechanisms and components used in OoO execution. We introduce CFC, a novel copy-free checkpointing which exploits FPGA block RAMs for fast and dense storage. Using CFC, we propose an FPGA-friendly register renamer and investigate the design and implementation of instruction schedulers on FPGAs. We then investigate Runahead execution and introduce NCOR, an FPGA-friendly non-blocking cache tailored for FPGAs. NCOR removes CAM-based structures used in conventional designs and achieves the high clock frequency of 278 MHz. Finally, we introduce SPREX, a complete Runahead soft core incorporating CFC and NCOR. Compared to Nios~II, SPREX provides as much as 38% higher performance for applications with irregular data-level parallelism with minimal area overhead.

Master of Science / Department of Biological & Agricultural Engineering / Stacy Lewis Hutchinson / In 2000, world leaders adopted the United Nations Millennium Declaration in hopes of drastically reducing the amount of people affected by poverty by 2015. One of the goals of the report pledged to “halve the proportion of people who are unable to reach or afford safe drinking water” (Juma, et al., 2001). For developing countries, where the water crisis is most concentrated, the achievement of this goal is nowhere close to being realized. With a world that is becoming increasingly interconnected, the ability to generate change on a global scale and in areas with the most need is attainable. The focus of engineering education today should prepare students to provide sustainable solutions worldwide. Engineering curricula, especially in regions of the world with standardized tests (e.g. United States and Canada) look toward preparing students for licensure. However, a need for more diversified, interdisciplinary education would benefit the future success of engineering designs. Knowledge of appropriate social, economic, and environmental needs must be considered to ensure sustainability and effectiveness of solutions. A case study focused on water quality tests located in Nyeri, Kenya enforces the importance of international pre-professional engineering experience. The study also demonstrates the need for increased efforts needed to achieve the drinking water target outlined by the Millennium Development Goals by 2015. In order for students to be successful, education must be targeted to cover both cultural and technological aspects of designing and especially the externalities associated with international design.

Video streaming applications over wireless networks have turned out to be immensely popular recently. In this thesis, we first study the buffering schemes for the VBR video streaming in heterogeneous wireless networks. An analytical framework is presented to derive the expected number of jitters and average buffering delay. Through experimenting with a wide range of buffering schemes, we quantify the bene¯t of incorporating user location information in streaming over heterogeneous wireless networks. Second, we consider the delivery of scalable VBR video streams over wireless channels. We propose adaptive rate control algorithms to improve the combined system performance of video frame quality and playout smoothness based on the feedback information of wireless network estimation, buffer content and playback situation. The proposed adaptive rate control algorithms provide significantly improved streaming quality compared with the non-control policy.

Carboxyl esterases, particularly arylesterases, were predicted from 16 microbial genomes, and then expressed in E. coli. Of the more than 175 cloned genes, 86 were expressed in soluble form. These were screened for activity using a range of both commercial and natural substrates. Forty-eight proteins were active on pNP-acetate at pH 8 whereas 38 proteins did not exhibit any activity towards any substrates. Among the 48 active proteins, 20 proteins showed arylesterase activity. To date, 8 bacterial esterases and 2 archaeal arylesterases were characterized in terms of pH stability and optima, thermal inactivation, solvent stability, and kinetics. To our knowledge there is only one other published report of arylesterases from archaea. The synthetic capability of arylesterases can transform phenolic acids to value-added chemicals. Accordingly, this project provides an arsenal of industrially significant activities that can extend the antioxidant properties of lignin-derived molecules in a broader range of renewable products.

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.

Carboxyl esterases, particularly arylesterases, were predicted from 16 microbial genomes, and then expressed in E. coli. Of the more than 175 cloned genes, 86 were expressed in soluble form. These were screened for activity using a range of both commercial and natural substrates. Forty-eight proteins were active on pNP-acetate at pH 8 whereas 38 proteins did not exhibit any activity towards any substrates. Among the 48 active proteins, 20 proteins showed arylesterase activity. To date, 8 bacterial esterases and 2 archaeal arylesterases were characterized in terms of pH stability and optima, thermal inactivation, solvent stability, and kinetics. To our knowledge there is only one other published report of arylesterases from archaea. The synthetic capability of arylesterases can transform phenolic acids to value-added chemicals. Accordingly, this project provides an arsenal of industrially significant activities that can extend the antioxidant properties of lignin-derived molecules in a broader range of renewable products.

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.

Video streaming applications over wireless networks have turned out to be immensely popular recently. In this thesis, we first study the buffering schemes for the VBR video streaming in heterogeneous wireless networks. An analytical framework is presented to derive the expected number of jitters and average buffering delay. Through experimenting with a wide range of buffering schemes, we quantify the bene¯t of incorporating user location information in streaming over heterogeneous wireless networks. Second, we consider the delivery of scalable VBR video streams over wireless channels. We propose adaptive rate control algorithms to improve the combined system performance of video frame quality and playout smoothness based on the feedback information of wireless network estimation, buffer content and playback situation. The proposed adaptive rate control algorithms provide significantly improved streaming quality compared with the non-control policy.

This thesis explores a single microphone tap localization interface for smartphones - Extended Touch(ET), that detects user-tapped locations on any neighboring surface. The algorithm combines accelerometer and microphone detection making it robust to noise, and does not require knowledge of surface parameters or sensor positioning. It uses acoustic signal as the feature vector and solves for tap inference in two phases - training and detection. The training phase builds a prior-model of the system by storing one or more templates of known tap locations. These templates are used in the detection phase to carry out a k-nearest neighbor classification to detect new tap locations. The algorithm achieves a 92% detection rate on knock taps. A method to detect contiguous tap locations is also proposed.

This thesis explores a single microphone tap localization interface for smartphones - Extended Touch(ET), that detects user-tapped locations on any neighboring surface. The algorithm combines accelerometer and microphone detection making it robust to noise, and does not require knowledge of surface parameters or sensor positioning. It uses acoustic signal as the feature vector and solves for tap inference in two phases - training and detection. The training phase builds a prior-model of the system by storing one or more templates of known tap locations. These templates are used in the detection phase to carry out a k-nearest neighbor classification to detect new tap locations. The algorithm achieves a 92% detection rate on knock taps. A method to detect contiguous tap locations is also proposed.