[DRAFT] Flattening loops of combinations, again!?

We had problems implementing the 3x1 flattened four nested loops generating 4-combinations in (Dash et al., 2021).

\[\begin{align*} q &\gets (\sqrt{729 \lambda^2 -3} + 27 \lambda)^{1/3} \\ k &\gets \lfloor (q/3^2)^{1/3} + 1/(3q)^{1/3} - 1 \rfloor \\ T_z &\gets k (k + 1) (k + 2) / 6 \\ \lambda' &= \lambda - T_z \\ j &\gets \lfloor \sqrt{1/4 + 2\lambda'} -1/2 \rfloor \\ i &\gets \lambda' - j (j + 1) / 2 \end{align*}\]

References

2021

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Sajal Dash, Qais Al-Hajri, Wu-chun Feng, and 2 more authors

In 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2021

Abs DOI

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈ 48\texttimes106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%-97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Enjoy Reading This Article?

Here are some more articles you might like to read next: