Experimental analysis of data management for distibuted data structures

Distributed memory multiprocessor architectures offer enormous computational power, by exploiting the concurrent execution of many loosely connected processors. Because of the low interconnection degree, and partitioned memories, the architectures can scale to arbitrary num­bers of processors. We pay a price for this seal.ability. Interface delays and low interconnection bandwidth to the distributed memories make remote memory access inefficient. In order to achieve good performance, we must carefully manage data to reduce the frequency of remote memory accesses. While attempting to increase locality, we cannot allow data management to become such a burden to prevent the creation of sophisticated programs. This thesis investigates issues pertaining to data management for "distributed data struc­tures". A distributed data structure logically extends traditional data structures by incorpo­rating data management mechanisms within the abstraction boundary. The data management policies can be tuned to the particular algorithmic behavior, while hiding the particular details from the end user. This approach has the advantages of performance, flezibility, abstraction, and system independence. To evaluate the success of data-structure-specific data management we performed an ex­perimental, trace-driven analysis of various management policies on a set of scientific parallel benchmarks. An object-based, data management formulation provided mechanisms for data organization, partition, placement, and access. The organization, partition, and placement poli­cies are similar to the domain decomposition facilities described in the current literature. The access policies are variants of remote access, migration, and coherent caching schemes. The ex­perimental analysis evaluates the success of the data management configurations on individual data structures. The conclusions indicate that data-structure-specific access policies can lead to substantial performance improvement over a single, system-imposed, data management policy. The encapsulation of data management within a· data structure appears to be an appropriate compromise between programming simplicity and practical performance.U of I OnlyRestricted to the U of I community indenfinitely during batch ingest of legacy ETDs