Abstract
While software support for array-based, data-parallel algorithms has been studied extensively, less attention has been devoted to irregular parallel applications. The majority of these applications are unstructured, that is, they possess asynchronous components that do not fit the data-parallel model. Examples of unstructured applications include sparse matrix and n-body problems. Previous research, such as Parti[11] and CHAOS[13], has concentrated on extending the array-based data-parallel model to handle structured irregular algorithms. For unstructured irregular applications, however, the appropriate language abstractions, compiler technology, and runtime techniques have yet to be discovered.
In this paper, we analyze, under a systematic framework, implementations of a representative set of algorithms— Blocked Sparse Cholesky (BSC)[20], Barnes-Hut[3], and EM3D[10]— on Tempest/Blizzard[18], a platform that supports both shared memory and message passing. Using our framework and corroborating experiments, we isolate a set of abstractions that allows easy and efficient expression of our benchmarks. The philosophy behind this set is to provide, for each component of a parallel language, mechanisms that support user control, along with good default behavior. Our contributions are the following: a framework for the evaluation of abstractions, a set of recommendations for language support for irregular applications, and an analysis of the ability of current languages to support them.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Agarwal et al. The MIT Alewife machine. In Proceedings of Workshop on Scalable Shared Memory Multiprocessors, 1991.
H. Bal and F. Kaashoek. Object distribution in Orca using compile-time and runtime techniques. In OOPSLA, Sept. 1993.
J. Barnes and P. Hut. A hierarchical O(N log N) force calculation algorithm. Nature, pages 446–449, Dec. 1986.
C. Leiserson et al. The network architecture of the connection machine CM-5. In Symposium on Parallel and Distributed Algorithms, pages 272–285, June 1992.
M. Carlisle and A. Rogers. Software caching and computation migration in olden. Principles and Practice of Parallel Programming, July 1995.
R. Chandra, A. Gupta, and J. Hennessy. Data locality and load balancing in COOL. In Principles and Practice of parallel programming, May 1993.
S. Chandra, B. Richards, and J. Larus. Teapot: Language support for writing memory coherence protocls. Technical Report TR 1291, Computer Science Department, University of Wisconsin, Madison, WI, Oct. 1995.
M. Chandy and C. Kesselman. A declarative, concurrent object oriented programming notation. Technical Report CS-92-01, California Institute of Technology, Pasadena, Ca, 1992.
A. Chien, V. Karamcheti, and J. Pleyvak. The concert system — compiler and runtime support for efficient, fine-grained concurrent object-oriented programs. Technical Report UIUCDCS-R-93-1815, Dept of Computer Science, University of Illinois(UC), 1993.
D. Culler et al. Parallel programming in Split-C. In Proceedings of Supercomputing '93, pages 262–273, Nov. 1993.
R. Das, M. Uysal, J. Saltz, and Y.-S. Hwang. Communication optimizations for irregular scientific computations on distributed memory architectures. Technical Report CS-TR-3163, University of Maryland, Oct. 1993.
B. Falsafi, A. Lebeck, S. Reinhardt, I. Schoinas, M. Hill, J. Larus, A. Rogers, and D. Wood. Application-specific protocols for user-level shared memory. In Proceedings of Supercomputing '94, pages 380–389, Nov. 1994.
Y.-S. Hwang, B. Moon, S. Sharma, R. Ponnuswamy, R. Das, and J. Saltz. Runtime and language support for compiling adaptive irregular programs on distributed memory machines. Software — Practice and Experience, 25, June 1995.
J. Kuskin et al. The Stanford FLASH multiprocessor. In Proceedings of the 21st Annual International Symposium on Computer Architecture, pages 302–313, Apr. 1994.
M. Blumrich et al. Virtual memory mapped network interface for the SHRIMP multicomputer. In Proceedings of the 21st Annual International Symposium on Computer Architecture, pages 142–153, Apr. 1994.
J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9(1):21–65, Feb. 1991.
R. S. Nikhil. Cid: A parallel, shared-memory C for distributed-memory machines. In Languages and Compilers for Parallel Computing, pages 376–390, Aug. 1994.
S. Reinhardt, J. Larus, and D. Wood. Tempest and Typhoon: user-level shared memory. In Proceedings of the 21st Annual International Symposium on Computer Architecture, Apr. 1994.
M. Rinard. The design, implementation and evaluation of Jade: a portable, implicitly parallel programming language. PhD thesis, Stanford University, Aug. 1994.
E. Rothberg. Exploiting the memory hierarchy in sequential and sparse Cholesky factorization. PhD thesis, Stanford University Department of Computer Science, Jan. 1993.
I. Schoinas, B. Falsafi, A. Lebeck, S. Reinhardt, J. Larus, and D. Wood. Fine-grain access control for distributed shared memory. In Conference on Architectural Support for Programming Languages and Operating Systems, pages 297–307, Nov. 1994.
J. P. Singh, J. L. Hennessy, and A. Gupta. Implications of hierarchical n-body methods for multiprocessor architecture. ACM Transactions on Computer Systems, May 1995.
J. P. Singh, C. Holt, T. Totsuka, A. Gupta, and J. L. Hennessy. Load balancing and data locality in adaptive hierarchical n-body methods: Barnes-hut, fast multipole, and radiosity. Journal of Parallel and Distributed Computing, June 1995.
T. von Eicken, D. Culler, S. Goldstein, and K. Schauser. Active messages: a mechanism for integrated commmunication and computing. In Proceedings of the International Symposium on Computer Architecture, pages 256–266, May 1992.
K. Yelick, S. Chakrabarti, E. Deprit, J. Jones, A. Krishnamurthy, and C.-P. Wen. Parallel data structures for symbolic computation. In Workshop on Parallel Symbolic Languages and Systems, Oct. 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Raghavachari, M., Rogers, A. (1996). Understanding language support for irregular parallelism. In: Ito, T., Halstead, R.H., Queinnec, C. (eds) Parallel Symbolic Languages and Systems. PSLS 1995. Lecture Notes in Computer Science, vol 1068. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0023061
Download citation
DOI: https://doi.org/10.1007/BFb0023061
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61143-1
Online ISBN: 978-3-540-68332-2
eBook Packages: Springer Book Archive