Donald Bren School of Information and Computer Sciences

Non-uniform memory and network access is a major source of performance degradation in SIMD supercomputers. We investigate the problem oí finding general XOR-schemes to minimize memory conflicts and network contention for accessing arrays with arbitrary data templates, defined by template bases.

The XOR-matrix is defined so that each column corresponds to a distinct vector in the union of all templates bases. A restriction of the XOR-matrix to a given template is formed by concatenation oí the columns corresponding to the template basis. We prove that a necessary and sufficient condition for conflict-free and network-contention-free access for the Baseline network is that certain sub-matrices of every template's restricted matrix be non-singular. A new characterization of the baseline network and XOR-matrices is proposed. Finding an XOR-matrix far accessing arbitrary templates is proved to be an NP-complete problem.

To minimize memory and network contention, a heuristic algorithm is proposed for finding XOR-matrices. The algorithm determines successive rows, from the bottom up. Given the previous row, the algorithm determines: 1) the constraints required by each template's restricted matrix 2) and the row solution by solving a set of simultaneous equations. To avoid backtracking, a randomized approach is used. The time complexity of the heuristic is O(tpn^2), where t, 2^P, and n, are the number of templates, the number of processors, and the number of distinct vectors of template bases, respectively. Evaluation shows that the proposed XOR-schemes significantly reduce memory and network contention compared to interleaving and XOR-schemes that are optimized for a set of static reference reference templates.