OPTIMIZING BIOINFORMATICS ALGORITHMS WITH AUTOMATIC INDEX SET SPLITTING

Abstract

A number of important and computationally-expensive bioinformatics algorithms belong to the class of non-serial polyadic dynamic programs (NPDPs). NPDPs tend to admit clever optimizations in the form of index-set splitting: a technique which involves partitioning a nested loop before applying separate transformations to each partition. Unfortunately, these partitions require vast manual effort to find by hand; no existing compiler is able to find index-set splits automatically. We present a linear programming technique which is able to automatically perform index-set splitting, allowing relevant programs to be tiled, which yields improvements in data locality and parallelism. We implement this technique in the AlphaZ system, and demonstrate massive performance gains.