Dynamic address mapping for conflict-free vector access
First Claim
1. A method of dynamic address mapping for conflict-free vector access in a vector processing system having a processor accessing a main memory having a multiplicity of N memory modules in which sequential memory addresses are mapped to different ones of the memory modules, said processor including means for referencing successive addresses differing by a constant access stride, said method comprising the steps of:
- (a) determining a stride S greater than 1 for which a vector is to be accessed;
(b) accessing said main memory to load data for said vector in said main memory using a storage scheme that is preselected for said vector and is a predetermined function of said stride S and permits conflict-free sequential access and conflict-free access with said stride S;
(c) accessing said main memory to access data for said vector by using the storage scheme preselected for said vector; and
(d) repeating steps (a), (b) and (c) for a multiplicity of different vectors, wherein different respective strides S are determined for the vectors, and said main memory is accessed using different respective storage schemes for said vectors, so that the storage scheme is selected dynamically for said multiplicity of vectors.
1 Assignment
0 Petitions
Accused Products
Abstract
Conflict-free vector access of any constant stride is made by preselecting a storage scheme for each vector based on the accessing patterns to be used with that vector. A respective storage scheme for each vector, for example, is selected to provide conflict-free access for a predetermined stride S. The respective storage scheme involves a rotation or permutation of an addressed row of corresponding memory locations in N parallel modules in main memory. The amount of rotation or permutation is a predetermined function of the predetermined stride S and the row address. The rotation is performed by modulo-N addition, or the permutation is performed by a set of exclusive-OR gates. For a system in which N is a power of 2 such that n=log2 N, the predetermined stride S is factored into an odd component and an even component that is a power of 2. The factorization is easily performed by a shift and count procedure, a shifter and counter, or a priority encoder. The amount of rotation or permutation is a predetermined function of the even component and the row address, and is preferably obtained by selecting a field of the row address in accordance with the maximum of s and n, and masking the selected field with a mask generated from the minimum of s and n.
73 Citations
20 Claims
-
1. A method of dynamic address mapping for conflict-free vector access in a vector processing system having a processor accessing a main memory having a multiplicity of N memory modules in which sequential memory addresses are mapped to different ones of the memory modules, said processor including means for referencing successive addresses differing by a constant access stride, said method comprising the steps of:
-
(a) determining a stride S greater than 1 for which a vector is to be accessed; (b) accessing said main memory to load data for said vector in said main memory using a storage scheme that is preselected for said vector and is a predetermined function of said stride S and permits conflict-free sequential access and conflict-free access with said stride S; (c) accessing said main memory to access data for said vector by using the storage scheme preselected for said vector; and (d) repeating steps (a), (b) and (c) for a multiplicity of different vectors, wherein different respective strides S are determined for the vectors, and said main memory is accessed using different respective storage schemes for said vectors, so that the storage scheme is selected dynamically for said multiplicity of vectors. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method of mapping addresses in a vector processing system of the kind having a processor and a main memory including a plurality of N memory modules;
- said processor supplying an address having a module address field, and a row address field selecting a respective storage location in each of said memory modules;
said processor also supplying a parameter for selecting storage schemes providing predetermined mappings of said address to said storage locations in said modules, said method comprising the steps of;(a) selecting a portion of said row address field in response to said parameter, and (b) determining a module address as a predetermined function of said module address field and the preselected portion of said row address field. - View Dependent Claims (11, 12, 13, 14)
- said processor supplying an address having a module address field, and a row address field selecting a respective storage location in each of said memory modules;
-
15. An address mapping circuit for mapping an address from an address bus to physical storage locations in a plurality of N memory modules connected to said address mapping circuit, said address including a row address field specifying a respective address in each of said modules, and a module address field, said address mapping circuit including
(a) selecting means, connected to said address bus, for selecting a portion of said row address field in response to a predetermined parameter, and (b) determining means, connected to said address bus, said selecting means and said plurality of N memory modules, for determining a module address as a predetermined function of said module address field and said portion of said row address field.
Specification