Loop-nests in most scientific applications perform repetitive operations on array(s) and account for most of the program execution time. Traditional loop transformations, such as tiling, leverage data locality and maximize program performance on modern micro-architectures. These transformations, however, effectively maximize performance of programs when loop-nests exhibit uniform reuse patterns.

In this thesis, a new loop transformation is presented to target loop-nests with non-uniform reuse patterns. The proposed loop transformation uses the norms of the Polyhedral Model to represent the loop-nests and then leverages such a representation to partition the iteration space into polygonally shaped partitions. These partitions optimize locality resulting in an improvement in performance for both serial and parallel execution. Improving locality in parallel execution requires selective mapping of partitions on threads based on the type of reuse these partitions exhibit.

The experiments on certain loop-nests show that a significant portion of the achievable performance is missed when applying the traditional loop transformations. Compared to state-of-the-art Polyhedral Model frameworks, the transformation shows a consistent performance speedup in serial (up to 1.2x over Polly) and parallel (up to 3.17x over PLuTo) executions for certain loop-nests with non-uniform reuse patterns.

Production compilers have achieved a high level of maturity in terms of generating efficient code. Compilers are embedded with numerous code optimization techniques, with special focus on loop nest optimizations, that have been developed over the last four decades. The code generated by any two production compilers can turn out to be very different based on pros and cons of their respective Intermediate Representation (IR), implemented loop transformations and their ordering, cost models used and even instruction selection (such as vector instructions) and scheduling. The compilers also need to predict the behavior of a multi-core processor which has complex pipelines, multiple functional units, complex memory hierarchy, etc. on the overall performance. Hence, the performance of produced code for a program segment by a given compiler may not necessarily be matched by other compilers. Additionally, there is no way of knowing how close a compiler gets to optimal performance or if there is any headroom for improvement.The complexity and rigidity of the compilation process makes it very difficult to modify a given compiler to improve the performance of generated code for every case where it couldn’t produce the best possible code. Therefore, this thesis presents a compilation approach that turns the differences between compilation processes and performance optimizations in each compiler from a weakness to a strength. This approach is implemented as a novel compilation framework, the MCompiler . This meta-compilation framework allows different segments of a program to be compiled using an ensemble of compilers/optimizers and combined into a single executable. Utilizing the highest performing code for each segment, identified via Exploratory Search, can lead to a significant overall improvement in performance. The framework is shown to produce performance improvements for serial (including auto-vectorized code), auto-parallelized and hand-optimized (using OpenMP) parallel code. Next, this thesis explores the possibility of learning which compiler will produce the best code for a segment. This is accomplished using Machine Learning. The Machine Learning models learn about inherent characteristics of loop nests and then predict which code optimizer is the most suited for each loop nest in an application. These Machine Learning models are then incorporated into the MCompiler to predict the best code optimizer, during compilation, for each code segment of the application. This feature allows the MCompiler to replace the expensive Exploratory Search with Machine Learning predictions and still keep performance very close to the Exploratory Search. Finally, this thesis expands the compilation approach to achieve energy efficiency on modern architectures. Prior research has advocated both for and against the hypothesis that optimizing for performance translates into optimizing for energy efficiency. No production compiler optimizes for energy efficiency directly, expecting optimizing for performance to translate into higher energy efficiency. Optimizing for performance is complex for recent generations of processors and, with automatic DVFS management in these processors, optimizing for energy efficiency would add another level of complexity for compilers with no guarantee of success. Using the MCompiler, this thesis shows how the performance-oriented compiler optimizations can be used to achieve energy efficiency.

Computer vision is an interdisciplinary field to obtain high-level understanding from digital images. It has many applications that impact our daily lives, such as automation, entertainment, healthcare, etc. However, computer vision is very challenging. This is in part due to the intrinsically difficult nature of the problem and partly due to the complexity and size of visual data that need to be processed. To be able to deploy computer vision in many practical use cases, sophisticated algorithms and efficient implementations are required.

In this thesis, we consider two platforms that are suitable for computer vision processing, yet they were not easily accessible to algorithm designers and developers: the Web and FPGA-based accelerators. Through the development of open-source software components, we highlight challenges associated with vision development on each platform and demonstrate opportunities to mitigate them.

The Web is the world's most ubiquitous computing platform which hosts a plethora of visual content. Due to historical reasons such as insufficient compute performance and lack of API support for acquiring and manipulating images, computer vision is not mainstream on the Web. We show that in light of recent web developments such as vastly improved JavaScript performance and the addition of APIs such as WebRTC, efficient computer vision processing can be realized on web clients. Through novel engineering techniques, we translate a popular open-source computer vision library (OpenCV) from C++ to JavaScript and optimize its performance for the web environment. We demonstrate that hundreds of computer vision functions run in browsers with performance close to their original C++ version. We believe this will result in an immersive and perceptual web with transformational effects, including in online shopping, education, and entertainment, among others.

Field Programmable Gate Arrays (FPGA)s are a promising solution to mitigate the computational cost of vision algorithms through hardware pipelining and parallelism. However, an efficient FPGA implementation of computer vision algorithms requires hardware design expertise and a considerable amount of engineering person-hours. We show that graph-based specifications, such as OpenVX can significantly improve FPGA design productivity. Since such abstraction lacks implementation details, a vision algorithm designer can only focus on the algorithm itself and rely on another party with hardware knowledge to implement the design efficiently on a specific platform. During this process, different implementation configurations that satisfy various design constraints, such as performance and power consumption, can be explored. Furthermore, the graph-based model permits system-level optimizations that are not possible with traditional function-level acceleration. Towards this goal, we develop a framework that optimizes and implements vision algorithms that are described in OpenVX spec on different FPGA architectures. This framework hides low-level hardware optimization and implementation details from computer vision algorithm designers and enables them to quickly develop and verify FPGA implementations of vision algorithms without sacrificing performance.

Background

New method

Results

Comparison with existing method(s)

Conclusions

Background

New method

Results

Comparison with existing method(s)

Conclusions