AUTOMATIC SOFTWARE PERFORMANCE OPTIMIZATION ON MODERN ARCHITECTURES BY

As computer architectures become more complex, the task of writing efficient program to best utilize the underlying architecture’s power increasingly becomes an extremely difficult and expensive process. Traditional approach of expert manual tuning of software performance becomes infeasible as both software and hardware complexity grow. To make things even worse, the relative cost of man labor compared with that of machine computation increases rapidly. One approach to attacking the problem is automatic library generation via empirical evaluation. The essential idea is to have a meta-program automatically generate other high performance program via empirical evaluation and intelligent search. The methodology has been successfully applied in several application domains, such as numerical computing, signal processing, sorting, etc. This dissertation extends the automatic library generation methodology to emerging untraditional computer archi-tectures and to a more complex application domain. Specifically, it consists of two parts of work: First, it studies and implements an automatic matrix multiply library generator for graphics hardware – a specialized architecture with enormous computing power for graphics applications; Second, it uses machine learning techniques to automatically select the best algorithm for frequent pattern mining problems according to input characteristics. In order to utilize the tremendous computing power of graphics hardware and to automatically adapt to the fas