An Efficient Implementation of Nested Data Parallelism for Irregular Divide-and-Conquer Algorithms

50k compressed postscript

Abstract: This paper presents work in progress on a new method of implementing irregular divide-and-conquer algorithms in a nested data-parallel language model on distributed-memory multiprocessors. The main features discussed are the recursive subdivision of asynchronous processor groups to match the change from data-parallel to control-parallel behavior over the lifetime of an algorithm, switching from parallel code to serial code when the group size is one (with the opportunity to use a more efficient serial algorithm) , and a simple manager-based run-time load-balancing system. Sample algorithms translated from the high-level nested data-parallel language NESL into C and MPI using this method are significantly faster than the current NESL system, and show the potential for further speedup.

@inproceedings{ hardwick96efficient,
    author = "Jonathan C. Hardwick",
    title = "An Efficient Implementation of Nested Data Parallelism for Irregular Divide-and-Conquer Algorithms",
    booktitle = "Proceedings of the First International Workshop on High-Level Programming Models and Supportive Environments",
    pages = "105--114",
    month = "April",
    year = "1996",
    url = "citeseer.nj.nec.com/hardwick96efficient.html" }