KeLP to the n-th
Scot Baden
University of California, San Diego
Hierarchically organized parallel multicomputers present opportunities for
delivering high performance, but also many obstacles. Historically, parallel
programming models assume a non-hierarchical view of system organization,
which is the basis for most general-purpose commercial multicomputers. As a
result, programmers are forced to navigate a cluttered terrain of processes,
threads, messages, shared memory, and so on. I propose a more orderly
programming model, KeLP^N, which supports hierarchical control flow, data
decomposition, and data motion. These mechanisms are parameterized according
to the level of the machine at which they are applied, and thus present a
uniform programmer interface. The run time system hides most of the details,
executing anonymous parameterized instruction sequences that carry out the
desired behavior at each level of the hierarchy. I present results for a
2-level prototype of KeLP^N running on a dedicated SMP cluster. A variety of
hierarchically organized computations have been implemented which generally
outperform their non-hierarchical counterparts. In particular, these
applications are able to effectively overlap communication on a system which
does not realize overlap with non-blocking communication. KeLP supports
overlap by ascribing communication at the node rather than the processor
level. Communication executes as a separate concurrent task, and how it is
implemented on the node cannot be exploited by the programmer. I conclude by
generalizing the 2-level model to the general case of N levels, and sketch the
details of an overlapped version of an iterative finite difference solver
running on a 3-level multicomputer with symmetric multiprocessor nodes.
Overlap in this computation is expressed at 2 distinct levels.
Further info and related paper(s):