With over 25 years across industry and academia, I led Android system software, platform engineering, and On-Device AI architecture for global Galaxy flagships as Corporate EVP and Head of the System R&D Team at Samsung Electronics MX. Earlier in my career, I architected the SYZYGY scalable cross-module interprocedural optimization (IPO) framework for HP-UX Itanium compilers at Hewlett-Packard after earning my PhD in Computer Science from USC.
Coverage analysis has been playing an important role in testing traditional single threaded applications. As the number of multicore hardware being used increases, the number of multithreaded applications grows as well. In multi-threaded environment, traditional code coverage models cannot really cover the nondeterministic behavior of simultaneously running threads. The concept of synchronization coverage was invented to solve this problem. In this paper, we present a new coverage testing tool which maximizes synchronization coverage rates with less time and repetition. After searching for synchronization primitives, our tool instruments special code segments to these points and forces the application executions to maximize its synchronization coverage by scheduling individual threads. This enables achieving maximum synchronization coverage without manipulating source code or writing unit test code. We implemented this method and showed that our method achieves maximum synchronization coverage rates 1.5 to over 144 times faster than random method.
BibTeX Citation
@inproceedings{kim_maximizing_2011,
title = {Maximizing {Synchronization} {Coverage} {Via} {Controlling} {Thread} {Schedule}},
url = {https://ieeexplore.ieee.org/abstract/document/5766365},
doi = {10.1109/CCNC.2011.5766365},
booktitle = {2011 IEEE Consumer Communications and Networking Conference ({CCNC'11})},
author = {Kim, HyoYoung and Cho, DaeHyun and Moon, Sungdo},
month = jan,
year = {2011},
pages = {1186--1191}
}
Performing analysis across module boundaries for an entire program is important for exploiting several runtime performance opportunities. However, due to scalability problems in existing full-program analysis frameworks, such performance opportunities are only realized by paying tremendous compile-time costs. Alternative solutions, such as partial compilations or user assertions, are complicated or unsafe and as a result, not many commercial applications are compiled today with cross-module optimizations. We present SYZYGY, a practical framework for performing efficient, scalable, interprocedural optimizations. The framework is implemented in the HP-UX Itanium compilers and we have successfully compiled many very large applications consisting of millions of lines of code. We achieved performance improvements of up to 40% over optimization level two and compilation time improvements in the order of 100% and more compared to a previous approach.
BibTeX Citation
@inproceedings{moon_syzygy_2004,
title = {{SYZYGY} - {A} {Framework} for {Scalable} {Cross}-{Module} {IPO}},
url = {https://ieeexplore.ieee.org/abstract/document/1281664},
doi = {10.1109/CGO.2004.1281664},
booktitle = {2004 International Symposium on Code Generation and Optimization ({CGO'04})},
author = {Moon, Sungdo and Li, Xinliang D. and Hundt, Robert and Chakrabarti, Dhruva R. and Lozano, Luis A. and Srinivasan, Uma and Liu, Shin-Ming},
month = mar,
year = {2004},
pages = {65--74}
}
This paper presents the results of an experiment to measure empirically the remaining opportunities for exploiting loop-level parallelism that are missed by the Stanford SUIF compiler, a state-of-the-art automatic parallelization system targeting shared-memory multiprocessor architectures. For the purposes of this experiment, we have developed a run-time parallelization test called the Extended Lazy Privatizing Doall (ELPD) test, which is able to simultaneously test multiple loops in a loop nest. For 29 programs in three benchmark suites, the ELPD test was executed at run time for each candidate loop left unparallelized by the SUIF compiler to identify which of these loops could safely execute in parallel for the given program input. The results of this experiment point to two main requirements for improving the effectiveness of parallelizing compiler technology: incorporating control flow tests into analysis and extracting low-cost run-time parallelization tests from analysis results.
BibTeX Citation
@article{moon_evaluating_2000,
title = {Evaluating {Automatic} {Parallelization} in {SUIF}},
volume = {11},
number = {1},
url = {https://ieeexplore.ieee.org/abstract/document/824639},
doi = {10.1109/71.824639},
journal = {IEEE Transactions on Parallel and Distributed Systems},
author = {Moon, Sungdo and So, Byoungro and Hall, Mary W.},
month = jan,
year = {2000},
pages = {36--49}
}
Loop tiling is a well-known compiler transformation that increases data locality, exposes parallelism and reduces synchronization costs. Tiling increases the amount of data reuse that can be exploited by reordering the loop iterations so that accesses to the same data are closer together in time. However, tiled loops often suffer from cache interference in the direct-mapped or low-associativity caches typically found in state-of-the-art microprocessors. A solution to this problem is to choose a tile size that does not exhibit self interference. In this paper, we propose a new tile selection algorithm for eliminating self interference and simultaneously minimizing capacity and cross-interference misses. We have automated the algorithm in the SUIF compiler and used it to generate tiles for a range of problem sizes for three scientific computations. Our experimental results show that the algorithm consistently finds tiles that yield lower miss rates than existing tile selection algorithms.
BibTeX Citation
@inproceedings{chame_tile_1999,
series = {{ICS} '99},
title = {A {Tile} {Selection} {Algorithm} for {Data} {Locality} and {Cache} {Interference}},
url = {https://dl.acm.org/doi/10.1145/305138.305245},
doi = {10.1145/305138.305245},
booktitle = {The 13th International Conference on Supercomputing ({ICS'99})},
publisher = {Association for Computing Machinery},
author = {Chame, Jacqueline and Moon, Sungdo},
month = jun,
year = {1999},
pages = {492--499}
}
This paper presents an evaluation of a new analysis for parallelizing compilers called predicated array data-flow analysis. This analysis extends array data-flow analysis for parallelization and privatization to associate predicates with data-flow values. These predicates can be used to derive conditions under which dependences can be eliminated or privatization is possible. These conditions can be used both to enhance compile-time analysis and to introduce run-time tests that guard safe execution of a parallelized version of a computation. As compared to previous work that combines predicates with array data-flow analysis, our approach is distinguished by two features: (1) it derives low-cost, run-time parallelization tests; and, (2) it incorporates predicate embedding and predicate extraction, which translate between the domain of predicates and data-flow values to derive more precise analysis results. We present extensive experimental results across three benchmark suites and one additional program, demonstrating that predicated array data-flow analysis parallelizes more than 40% of the remaining inherently parallel loops left unparallelized by the SUIF compiler and that it yields improved speedups for 5 programs.
BibTeX Citation
@inproceedings{moon_evaluation_1999,
series = {{PPoPP} '99},
title = {Evaluation of {Predicated} {Array} {Data}-{Flow} {Analysis} for {Automatic} {Parallelization}},
url = {https://dl.acm.org/doi/10.1145/301104.301112},
doi = {10.1145/301104.301112},
booktitle = {The 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming ({PPoPP'99})},
publisher = {Association for Computing Machinery},
author = {Moon, Sungdo and Hall, Mary W.},
month = may,
year = {1999},
pages = {84--95}
}
