 Main
Minimization of memory and network contention for accessing arbitrary data patterns in SIMD systems
 Author(s): Seiden, Steven S.;
 AlMouhamed, Mayez A.
 et al.
Abstract
Nonuniform memory and network access is a major source of performance degradation in SIMD supercomputers. We investigate the problem oí finding general XORschemes to minimize memory conflicts and network contention for accessing arrays with arbitrary data templates, defined by template bases.
The XORmatrix is defined so that each column corresponds to a distinct vector in the union of all templates bases. A restriction of the XORmatrix 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 conflictfree and networkcontentionfree access for the Baseline network is that certain submatrices of every template's restricted matrix be nonsingular. A new characterization of the baseline network and XORmatrices is proposed. Finding an XORmatrix far accessing arbitrary templates is proved to be an NPcomplete problem.
To minimize memory and network contention, a heuristic algorithm is proposed for finding XORmatrices. 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 XORschemes significantly reduce memory and network contention compared to interleaving and XORschemes that are optimized for a set of static reference reference templates.
Main Content
Enter the password to open this PDF file:













