High performance dynamic array structures.

Abstract

Simple arrays are often modified into more complex dynamic structures in order to increase the efficiency of applications. Two examples of these dynamic array structures are the telescoping wedge and adaptive blocks. Implementing high performance versions of these structures is often difficult because of their complexity. Challenges include efficiently locating data, maintaining cache use, and moving efficiently through the structure. Difficulties in implementation are especially acute when the program is created for a parallel computer. Challenges unique to parallel computers include communication and load balancing. This project addresses these challenges by investigating the implementation of high performance versions of the telescoping wedge and adaptive blocks. The above challenges were met for each data structure. For the telescoping wedge, efficient versions of two types of wedge were implemented. Both types of wedge allowed the solution of problems which were previously considered infeasible by reducing the amount of computational resources required. For example, the size of the problem solvable for the 3-arm bandit was expanded from <italic>n</italic> = 20 to <italic>n</italic> = 200. For adaptive blocks, a flexible and efficient general purpose tool was developed. The flexibility of the tool was demonstrated by the ease with which changes were made, such as switching between a large supercomputing platform and a home computer, and adding a new grid shape. The efficiency was demonstrated by the small percentage of time taken by the tool in an example application.