Abstract
Finding general XOR-schemes to minimize memory and network contention for accessing arrays with arbitrary sets of data templates is presented. A combined XOR-matrix is proposed together with a necessary and sufficient condition for conflict-free access. We present a new characterization of the baseline network. Finding an XOR-matrix for combined templates is shown to be an NP-complete problem. A heuristic is proposed for finding XOR-matrices by determining the constraints of each template-matrix and solving a set of simultaneous equations for each row. Evaluation shows significant reduction of memory and network contention compared to interleaving and to static row-column-diagonals storage.
| Original language | English |
|---|---|
| Pages (from-to) | 757-762 |
| Number of pages | 6 |
| Journal | IEEE Transactions on Computers |
| Volume | 45 |
| Issue number | 6 |
| DOIs | |
| State | Published - 1996 |
Bibliographical note
Funding Information:The authors appreciate the care with which the referees read this paper and their constructive and useful suggestions. This work was supported in part by the U.S. National Science Foundation under grant MIP-9208929.
Keywords
- Memory conflicts
- Multistage networks
- NP-completeness
- Parallel memories
- Storage schemes
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics