Evaluation of Neural and Genetic Algorithms For Synthesizing Parallel Storage Schemes

Exploiting compile time knowledge to improve memory band-width can produce noticeable improvements at run-time [13, 1]. Allocating the data structure [13] to separate memories whenever the data may be accessed in parallel allowed im-provements in memory access time of 13 % to 40%. We are concerned with dynamic storage schemes for which the com-piler can predict some of the access patterns of parallelized programs. A storage scheme provides a mapping from array addresses into storages. However, ¯nding a con°ict-free stor-age scheme for a set of data patterns is NP-complete. This problem is reduceable to weighted graph coloring. Optimiz-ing the address transformation is investigated by using: (1) constructive heuristics, (2) neural methods, and (3) genetic algorithms. The details of implementation of these di®er-ent approaches are presented. Using realistic data patterns, simulation shows that memory utilization of 80 % or higher can be achieved in the case of 20 data patterns over up to 256 unbu®ered parallel memories. The neural approach was relatively very fast in producing reasonably good solutions even in the case of large problem sizes. Convergence of pro-posed neural algorithm seems to be only slightly dependent on problem size. Genetic algorithms outperformed all others and are recommended for advanced compiler optimization especially for: (1) large problem sizes, and (2) applications which are compiled once and run many times over di®erent data sets.