Heuristic Guided Pre-Optimized Algorithm Substitution for Parallel Computers
Ko‐Yang Wang · Purdue e-Pubs (Purdue University System) · 1990
In this paper, we study the integration of pre-optimized algorithm substitution with the feature-directed program transformation techniques. In the algorithm substitution approach, a pre-optimized algorithm replaces a user program when the pattern of the user program matches that of the pre-optimized algorithm. Parallel program optimization is a highly machine dependent process. However, it is impossible or cost-inefficient to have one pre-optimized algorithm for every architecture. When there is no pre-optimized algorithm for the target machine exists, the feature-directed program optimization process is involved for two purposes: to choose among applicable pre-optimized algorithms or to fine tune the selected preoptimized algorithm to match the particular architecture that the algorithm is not designed for. Our solution to the problem of fine-tuning pre-optimized algorithms for different parallel architectures is to record the machine features that the optimization of the algorithm is based upon and use a knowledge base system and a set of program transformations to further restructure the substituted algorithm to fit the target machine.