Abstract: Optimizing complex algorithms using conventional programming languages can be a difficult task. The performance aspect of such implementations relies on the programmer and the target architectures. Minor alterations to the algorithm can result in a considerable amount of reprogramming effort.
In our work, we experiment with equational programming using the AlphaZ tool. We illustrate our work using a fairly complex algorithm for RNA
secondary structure prediction. The algorithm is extracted from the UNAFold software package, a huge C library, by identifying the time consuming parts. It is then represented as equations, which are transformed for optimizations, followed by code generation and finally validating the generated code by plugging it back into the original C program. The algorithm, in its basic form, has complexity O(N^4). We show that the optimized O(N^3) algorithm can be derived systematically using AlphaZ. We used the AlphaZ system to automatically generate a C program that implements this improved algorithm. Our work forms the basis for future optimizations and also acts as a case-study for polyhedral equational programming in the real world.
Adviser: Dr. Sanjay Rajopadhye Co-Adviser: N/A Non-ECE Member: Dr. A. P. Willem Bohm (Dept. of Computer Science) Member 3: Dr. Sudeep Pasricha Addional Members: N/A
