Search

The dawn of the twenty-first century has witnessed an explosion in the number of digital devices and data. While the emerging deep learning algorithms to extract information from this vast sea of data are becoming increasingly compute-intensive, traditional means of improving computing power are no longer yielding gains at the same rate due to the diminishing returns from traditional technology scaling. To minimize the increasing gap between computational demands and the available resources, the paradigm of approximate computing is emerging as one of the potential solutions. Specifically, the resource-efficient approximate arithmetic units promise overall system efficiency, since most of the compute-intensive applications are dominated by arithmetic operations. This thesis primarily presents design techniques for approximate hardware multipliers and dividers. The thesis presents the design of two approximate integer multipliers and an approximate integer divider. These are: an error-configurable minimally-biased approximate integer multiplier (MBM), an error-configurable reduced-error approximate log based multiplier (REALM), and error-configurable integer divider INZeD. The two multiplier designs and the divider designs are based on the coupling of novel mathematically formulated error-reduction mechanisms in the classical approximate log based multiplier and dividers, respectively. They exhibit very low error bias and offer Pareto-optimal error vs. resource-efficiency trade-offs when compared with the state-of-the-art approximate integer multipliers/dividers. Further, the thesis also presents design of approximate floating-point multipliers and dividers. These designs utilize the optimized versions of the proposed MBM and REALM multipliers for mantissa multiplications and the proposed INZeD divider for mantissa division, and offer better design trade-offs than traditional precision scaling.The existing approximate integer dividers as well as the proposed INZeD suf

Information leakage is a fundamental concern in most computing systems. The memory bus between the processor chip and external memory in processor-based systems is one of the most vulnerable points that can be exploited for snooping attacks. The data encryption schemes are commonly used to protect the confidentiality of data transmitted over the bus; however, it is not sufficient alone as the information can still be revealed through the plain memory addresses used for access. The memory access pattern can reveal how a program execution flow is diverted, how many iterations of a loop are executed, how frequently a memory location is accessed, to name a few. The Oblivious RAM (ORAM) schemes have been proposed to close this side channel. ORAM is a cryptographic primitive that prevents the information leakage from the memory access patterns by obfuscating each true access to memory through a sequence of dummy memory accesses and continuously shuffling the encrypted memory contents. However, its utilization in the real processor system is not feasible because the existing ORAM designs incur hefty performance and area overheads and do not scale well with the memory size. It is highly desirable to have an efficient ORAM design that can be used in the processor system for real-life applications. In this thesis, a novel ORAM design has been proposed that hides a true memory in a flock of random memory accesses in a way that makes the flock size independent of the memory scale; hence the performance overhead does not increase with the size of the memory. The design also offers high flexibility with many tunable design parameters that resulted in high memory access obliviousness at a low overhead of performance and area. Furthermore, the design has been extended to efficiently work with multi-core processor systems. In such systems, memory access requests can be generated frequently and in parallel, which makes the ORAM performance overhead issue even more critical. Therefore

From the initial computing machines, Colossus of 1943 and ENIAC of 1945, to modern high-performance data centers and Internet of Things (IOTs), four design goals, i.e., high-performance, energy-efficiency, resource utilization, and ease of programmability, have remained a beacon of development for the computing industry. During this period, the computing industry has exploited the advantages of technology scaling and microarchitectural enhancements to achieve these goals. However, with the end of Dennard scaling, these techniques have diminishing energy and performance advantages. Therefore, it is necessary to explore alternative techniques for satisfying the computational and energy requirements of modern applications. Towards this end, one promising technique is analyzing and surrendering the strict notion of correctness in various layers of the computation stack. Most modern applications across the computing spectrum---from data centers to IoTs---interact and analyze real-world data and take decisions accordingly. These applications are broadly classified as Recognition, Mining, and Synthesis (RMS). Instead of producing a single golden answer, these applications produce several feasible answers. These applications possess an inherent error-resilience to the inexactness of processed data and corresponding operations. Utilizing these applications' inherent error-resilience, the paradigm of Approximate Computing relaxes the strict notion of computation correctness to realize high-performance and energy-efficient systems with acceptable quality outputs. The prior works on circuit-level approximations have mainly focused on Application-specific Integrated Circuits (ASICs). However, ASIC-based solutions suffer from long time-to-market and high-cost developing cycles. These limitations of ASICs can be overcome by utilizing the reconfigurable nature of Field Programmable Gate Arrays (FPGAs). However, due to architectural differences between ASICs and FPGAs, the utilizati

DNA sequencing---the process that converts chemically encoded data in DNA molecules into a computer-readable form---is revolutionising the field of medicine. DNA sequencers, the machines which perform DNA sequencing, have evolved from the size of a fridge to that of a mobile phone over the last two decades. The cost of sequencing a human genome also has reduced from billions of dollars to hundreds of dollars. Despite these improvements, DNA sequencers output hundreds or thousands of gigabytes of data that must be analysed on computers to discover meaningful information with biological implications. Unfortunately, the analysis techniques have not kept the pace with rapidly improving sequencing technologies. Consequently, even today, the process of DNA analysis is performed on high-performance computers, just as it was a couple of decades ago. Such high-performance computers are not portable. Consequently, the full utility of an ultra-portable sequencer for sequencing in-the-field or at the point-of-care is limited by the lack of portable lightweight analytic techniques.This thesis proposes computer architecture-aware optimisation of DNA analysis software. DNA analysis software is inevitably convoluted due to the complexity associated with biological data. Modern computer architectures are also complex. Performing architecture-aware optimisations requires the synergistic use of knowledge from both domains, (i.e, DNA sequence analysis and computer architecture). This thesis aims to draw the two domains together. In this thesis, gold-standard DNA sequence analysis workflows (a workflow is a few software tools executed sequentially where each software tool is a complex system of dozens of algorithms) are systematically examined for algorithmic components that cause performance bottlenecks. Identified bottlenecks are resolved through architecture-aware optimisations at different levels, i.e., memory, cache, register and processor. The optimised software tools are used in

Treatment of patients using high-quality precision medicine requires a thorough understanding of the genetic composition of a patient. Ideally, the identification of unique variations in an individual's genome is needed for specifying the necessary treatment. Variant calling workflow is a pipeline of tools, integrating state of the art software systems aimed at alignment, sorting and variant calling for the whole genome sequencing data. This pipeline is utilised for identifying unique variations in an individual's genome compared to a reference genome). Currently, such a workflow is implemented on high-performance computers (with additional GPUs or FPGAs) or in cloud computers. Such systems are large, expensive, and internet dependent for genome data transfer which makes the system unusable in remote locationsunequipped with internet connectivity. It further raises privacy concerns due to processing being carried out in a different facility.To overcome such limitations, in this thesis, for the first time, I present a cost-efficient, offline, scalable, portable, and energy-efficient computing system named SWARAM for variant calling workflow processing. The system uses novel architecture and algorithms to match against partial reference genomes to exploit smaller memory sizes typically available in tiny processing systems. An optimised version of BWA-MEM targeting alignment using partitioned reference genome in distributed system architecture is also detailed in this thesis and is implemented on the proposed SWARAM system. Furthermore, I present a GPU based implementation using tiny processing systems with onboard GPU. The proposed GPU based system named SWARAM-GPU is low-cost, scalable, portable, offline and energy-efficient. The SWARAM-GPU system uses an advanced distributed system and data partitioning approach to exploit small memory sizestypically available in tiny processing systems with onboard GPU.Extensive tests on a standard benchmark data-set (NA12878 Illum

The importance of genomic applications in the fields of medicine, agriculture, environment etc., has focused attention in the area of genomic computation in the last two decades. New technologies make it affordable to extract genomic information (sequencing) on a scale hitherto unknown. This has resulted in decreasing the price of sequencing and has increased the number of areas in which the sequencing data is utilised. Thus there is a need to assemble more and more genomes. A significant computational effort is needed to process this sequenced data (assembly) to assemble data and search for variations. It has been predicted that genomic data will exceed the amount of astronomical data in a near future. The growth in computational capacity, based on Moore’s law, cannot continue to respond to this increased computational demand.This thesis is motivated in response to the extensive demand for processing of sequenced data. The author identifies several important related processes and aims to improve each of those methods. First, a comprehensive review has been done on recent assembly pipelines to evaluate them. The result of the study reveals important facts which are used to design an efficient assembly practice. Second, a novel assembly pipeline is introduced that successfully balances the trade-off between speed and accuracy. Third, a fast and accurate sequence alignment algorithm is proposed that is the core of several steps in the assembly workflow, as well as a wide range of other related analysis. Finally, a new data normalisation method is designed. Due to the probabilistic nature of genome assembly, evaluating accuracy is critical. The normalisation is a vital part of the evaluation process. Along with normalisation method, the author has proposed a metric to measure how well the data is normalised. Such a metric has been proposed for the first time.The proposed assembly pipeline is 6 times faster than Spades and results in 100 times larger contiguity than SOA