  Computational protein structure determination involves optimization in a
problem space much too large to exhaustively search. Existing approaches
include optimization algorithms such as gradient descent and simulated
annealing, but these typically only find local minima. One novel approach
implemented in REDcRAFT is to instead of folding a protein all at the same
time, fold it residue by residue. This simulates a protein folding as each
residue exits from the generating ribosome. While REDcRAFT exponentially
reduces the problem space so it can be explored in polynomial time, it is still
extremely computationally demanding. This algorithm does have the advantage
that most of the execution time is spent in inherently parallelizable code.
However, preliminary results from parallel execution indicate that
approximately two-thirds of execution time is dedicated to system overhead.
Additionally, by carefully analyzing and timing the structure of the program
the major bottlenecks can be identified. After addressing these issues,
REDcRAFT becomes a scalable parallel application with nearly two orders of
magnitude improvement.
