Loading...
Please wait, while we are loading the content...
Similar Documents
ICASE Report No . 91-55 ICASE RECTILINEAR PARTITIONING OF IRREGULAR DATA PARALLEL COMPUTATIONS
| Content Provider | Semantic Scholar |
|---|---|
| Author | Nicol, David M. |
| Abstract | This paper describes new mapping algorithms for domain-oriented data-parallel computations, where the workload is distributed irregularly throughout the domain, but exhibits localized communication patterns. We consider the problem of partitioning the domain for parallel processing in such a way that the workload on the most heavily loaded processor is minimized, subject to the constraint that the partition be perfectly rectilinear. Rectilinear partitions are useful on architectures that have a fast local mesh network and a relatively slower global network; these partitions heuristically attempt to maximize the fraction of communication carried by the local network. This paper provides an improved algorithm for finding the optimal partition in one dimension, new algorithms for partitioning in two dimensions, and shows that optimal partitioning in three dimensions is NP-complete. We discuss our application of these algorithms to real problems. *This research was supported in part by tlreArmy Avionics Research and Development Activity through NASA grant NAG-I-787, in part by NASA grant NAG-1-1132, and in part by NSF Grant ASC 8819373. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.dtic.mil/dtic/tr/fulltext/u2/a240681.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Report |
