Walter Scott, Jr. College of Engineering

Graduate Exam Abstract

swetha varadarajan
M.S. Final
Oct 26, 2017, 3:00 pm - 5:00 pm
CSB 305
POLYHEDRAL OPTIMIZATIONS OF RNA-RNA INTERACTION COMPUTATIONS
Abstract: Studying RNA-RNA interaction has led
to major successes in the treatment of
some cancers, including colon, breast
and pancreatic cancer by suppressing
the gene expression involved in the
development of these diseases. The
problem with such programs is that
they are computationally and memory
intensive: O(N4) space and O(N6) time
complexity. Moreover, the entire
application is complicated, and
involves many mutually recursive data
variables. We address the problem of
speeding up a surrogate kernel
(named OSPSQ) that captures the
main dependence pattern found in two
widely used RNA-RNA interaction
applications - IRIS and piRNA.

The structure of the OSPSQ kernel
perfectly fits the constraints of the
polyhedral model, a well-developed
technology for optimizing codes that
belong to many specialized domains.
However, the current state-of-the-art
automatic polyhedral tools do not
significantly improve the performance
of the baseline implementation of
OSPSQ.

With simple techniques like loop
permutation and skewing, we achieve
an average of 17x sequential and 31x
parallel speedup on a standard modern
multi-core platform (Intel Broadwell,
E5-1650v4). This performance
represents 75% and 88% of attainable
single-core and multi-core L1
bandwidth. For further performance
improvement, we describe how to tile
all six dimensions and also formulate
the associated memory trade-off.

In the future, we plan to implement
these tiling strategies, explore the
performance of the code for various tile
sizes and optimize the whole piRNA
application.
Adviser: Sanjay Rajopadhye
Co-Adviser: N.A.
Non-ECE Member: Wim Bohm, Computer Science
Member 3: Jesse Wilson, Electrical & Computer Engineering
Addional Members: N.A.
Publications:
N.A.
Program of Study:
ECE 561
CS 475
ECE 554
CS 575
MATH 510
CS 545
N.A.
N.A.