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}
}
In this dissertation, we investigate how good today's parallelizing compilers are, what opportunities remain to improve them, and what technology is needed to exploit the remaining opportunities. To answer these questions, we perform experiments that measure the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF compiler's automatic parallelization system. The experimental results demonstrate that significant improvements to automatic parallelization technology require that existing systems be extended in two ways: (1) they must combine high-quality compile-time analysis with low-cost run-time testing; and, (2) they must take control flow into account during analysis. In order to exploit these remaining opportunities, we have developed a new compile-time analysis technique called predicated array data-flow analysis. Experimental results with a prototype implementation show that predicated array data-flow analysis parallelizes more than 40% of the remaining inherently parallel loops left unparallelized by the SUIF compiler, demonstrating improved speedups with negligible run-time overhead.
BibTeX Citation
@phdthesis{moon_combining_2002,
title = {Combining {Compile}-{Time} and {Run}-{Time} {Parallelization}},
url = {https://doi.org/10.25549/usctheses-c16-224653},
school = {University of Southern California},
author = {Moon, Sungdo},
month = may,
year = {2002}
}
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}
}
This paper demonstrates that significant improvements to automatic parallelization technology require that existing systems be extended in two ways: (1) they must combine high-quality compile-time analysis with low-cost run-time testing; and (2) they must take control flow into account during analysis. We support this claim with the results of an experiment that measures the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF compiler’s automatic parallelization system. We present results of measurements on programs from two benchmark suites – SPECFP95 and NAS sample benchmarks – which identify inherently parallel loops in these programs that are missed by the compiler. We characterize remaining parallelization opportunities, and find that most of the loops require run-time testing, analysis of control flow, or some combination of the two. We present a new compile-time analysis technique called predicated array data-flow analysis that can be used to parallelize most of these remaining loops.
BibTeX Citation
@article{moon_combining_1999,
title = {Combining {Compile}-{Time} and {Run}-{Time} {Parallelization}},
volume = {7},
number = {3-4},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1155/1999/490628},
doi = {10.1155/1999/490628},
journal = {Scientific Programming},
author = {Moon, Sungdo and So, Byoungro and Hall, Mary W.},
year = {1999},
pages = {247--260}
}
This paper presents a new analysis for parallelizing compilers called predicated array data-flow analysis, whereby array dataflow analysis for parallelization and privatization is extended 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, which can consist of arbitrary program statements, 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. We have implemented predicated array data-flow analysis in the Stanford SUIF compiler. We describe features of the implementation and present experimental results that demonstrate this analysis improves the performance of three programs from the SPEC95FP benchmark suite.
BibTeX Citation
@inproceedings{moon_predicated_1998,
series = {{ICS} '98},
title = {Predicated {Array} {Data}-{Flow} {Analysis} for {Run}-{Time} {Parallelization}},
url = {https://dl.acm.org/doi/10.1145/277830.277874},
doi = {10.1145/277830.277874},
booktitle = {The 12th International Conference on Supercomputing ({ICS'98})},
publisher = {Association for Computing Machinery},
author = {Moon, Sungdo and Hall, Mary W. and Murphy, Brian R.},
month = jul,
year = {1998},
pages = {204--211}
}
This paper presents both an experiment and a system for inserting run-time dependence and privatization testing. The goal of the experiment is to measure empirically the remaining opportunities for exploiting loop-level parallelism that are missed by state-of-the-art parallelizing compiler technology. We perform run-time testing of data accessed within all candidate loops not parallelized by the compiler to identify which of these loops could safely execute in parallel for the given program input. This system extends the Lazy Privatizing Doall (LPD) test to simultaneously instrument multiple loops in a nest. Using the results of interprocedural array dataflow analysis, we avoid unnecessary instrumentation of arrays with compile-time provable dependences or loops nested inside outer parallelized loops. We have implemented the system in the Stanford SUIF compiler and have measured programs in three benchmark suites.
BibTeX Citation
@inproceedings{so_measuring_1998,
series = {{ICS} '98},
title = {Measuring the {Effectiveness} of {Automatic} {Parallelization} in {SUIF}},
url = {https://dl.acm.org/doi/10.1145/277830.277876},
doi = {10.1145/277830.277876},
booktitle = {The 12th International Conference on Supercomputing ({ICS'98})},
publisher = {Association for Computing Machinery},
author = {So, Byoungro and Moon, Sungdo and Hall, Mary W.},
month = jul,
year = {1998},
pages = {212--219}
}
This paper demonstrates that significant improvements to automatic parallelization technology require that existing systems be extended in two ways: (1) they must combine high-quality compile-time analysis with low-cost run-time testing; and, (2) they must take control flow into account during analysis. We support this claim with the results of an experiment that measures the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF compiler’s automatic parallelization system. We present results of measurements on programs from two benchmark suites — Specfp95 and Nas sample benchmarks — which identify inherently parallel loops in these programs that are missed by the compiler. We characterize remaining parallelization opportunities, and find that most of the loops require run-time testing, analysis of control flow, or some combination of the two.
BibTeX Citation
@inproceedings{moon_case_1998,
title = {A {Case} for {Combining} {Compile}-{Time} and {Run}-{Time} {Parallelization}},
doi = {10.1007/3-540-49530-4_7},
booktitle = {The 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers ({LCR'98})},
publisher = {Springer},
author = {Moon, Sungdo and So, Byoungro and Hall, Mary W. and Murphy, Brian R.},
month = may,
year = {1998},
pages = {91--106}
}
This paper presents hyperblocking, or hypertiling, a novel optimization technique that makes it possible to drastically eliminate the self and cross interference misses of tiled loop nests, while significantly reducing the overhead involved in copying data blocks. In hyperblocking, all arrays used in a tiled loop nest are reorganized at the beginning of the computation such that all data blocks are guaranteed to map into disjoint and contiguous cache regions. Doing this effectively eliminates the occurrence of interference misses in many dense-matrix computations. When data prefetching is used in combination with hyperblocking, it is possible to completely hide the latency of capacity misses, and given that no cache conflicts can occur, it makes it possible to increase the prefetch distance to cover larger latencies without causing any amount of cache pollution.
BibTeX Citation
@techreport{moon_hyperblocking_1998,
title = {Hyperblocking: {A} {Data} {Reorganization} {Method} to {Eliminate} {Cache} {Conflicts} in {Tiled} {Loop} {Nests}},
url = {https://digitallibrary.usc.edu/asset-management/2A3BF1S4H2US0},
number = {USC–CSTR–98–671},
institution = {USC},
author = {Moon, Sungdo and Saavedra, Rafael H.},
month = feb,
year = {1998}
}
The granularity of shared data is one of the key factors affecting the performance of distributed shared memory machines (DSM). Given that programs exhibit quite different sharing patterns, providing only one or two fixed granularities cannot result in an efficient use of resources. On the other hand, supporting arbitrarily granularity sizes significantly increases not only hardware complexity but software overhead as well. In this paper, we present a new communication scheme, called Adaptive Granularity (AG). Adaptive Granularity makes it possible to transparently integrate bulk transfer into the shared memory model by supporting variable-size granularity and memory replication. Simulation results show that AG improves performance up to 43% over the hardware implementation of DSM (e.g., DASH, Alewife).
BibTeX Citation
@article{park_adaptive_1997,
title = {Adaptive {Granularity}: {Transparent} {Integration} of {Fine}- and {Coarse}-{Grain} {Communication}},
volume = {25},
number = {5},
url = {https://doi.org/10.1007/BF02699885},
doi = {10.1007/BF02699885},
journal = {International Journal of Parallel Programming},
author = {Park, Daeyeon and Saavedra, Rafael H. and Moon, Sungdo},
month = oct,
year = {1997},
pages = {419--446}
}
Unimodular transformations, tiling, and software prefetching are loop optimizations known to be effective in increasing parallelism, reducing cache miss rates, and eliminating processor stall time. Although these optimizations individually are quite effective, there is the expectation that even better improvements can be obtained by combining them together. In this paper we show that indeed this is the case when unimodular transformations are combined with either tiling or software prefetching. However, our results also show that although combining tiling with prefetching tends to improve the performance of tiling alone, it is also the case that in some situations tiling can degrade the cache performance of software prefetching.
BibTeX Citation
@inproceedings{saavedra_combined_1996,
title = {The {Combined} {Effectiveness} of {Unimodular} {Transformations}, {Tiling}, and {Software} {Prefetching}},
url = {https://ieeexplore.ieee.org/abstract/document/508037},
doi = {10.1109/IPPS.1996.508037},
booktitle = {The 1996 International Conference on Parallel Processing ({ICPP'96})},
author = {Saavedra, Rafael H. and Mao, Weihua and Park, Daeyeon and Chame, Jacqueline and Moon, Sungdo},
month = aug,
year = {1996},
pages = {39--45}
}