US5111389A — Aperiodic mapping system using power-of-two strid…

Claim 1

Independent Claim 190 words

An aperiodic mapping system for the mapping of logical addresses to physical addresses in a multi-user, multi-server system wherein there are 2 d server devices and n logical address bits (where d is <n) for generating optimized stride accesses among said multiple server system; said multiple-users and multiple servers being selectively connectable over an interconnection network wherein any user can communicate with any server in the system, each user having its own address transformation unit including a multiplier means and a matrix storage means, each said network having addressing means which examines any system address on the network to determine which server is being addressed, said mapping system comprising, an address transformation means operating in each address transformation unit for performing in the multiplier a bit-matrix multiplication of an n-bit first (logical) address (A) from its associated user with a predetermined matrix M' stored in the matrix storage means, said matrix having d, n-bit rows to produce a second (d-bit)+(n-d bit) (physical) address A', placing said second address A', on the interconnection network, and utilizing the d-bits of said second address A' to determine if that server is being addressed.

Claim 2

Dependent Claim 190 words

An aperiodic mapping system for the mapping of logical addresses to physical addresses in a multi-user, multi-server system wherein there are 2 d server devices and n logical address bits (where d is <n) for generating optimized stride accesses among said multiple server system; said multiple-users and multiple servers being selectively connectable over an interconnection network wherein any user can communicate with any server in the system, each user having its own address transformation unit including a multiplier means and a matrix storage means, each said network having addressing means which examines any system address on the network to determine which server is being addressed, said mapping system comprising, an address transformation means operating in each address transformation unit for performing in the multiplier a bit-matrix multiplication of an n-bit first (logical) address (A) from its associated user with a predetermined matrix M' stored in the matrix storage means, said matrix having d, n-bit rows to produce a second (d-bit)+(n-d bit) (physical) address A', placing said second address A', on the interconnection network, and utilizing the d-bits of said second address A' to determine if that server is being addressed.

Claim 3

Dependent Claim 39 words

Said aperiodic mapping system as set forth in claim 1 including each addressing means utilizing the n-d bits of the address A which were not altered by the mapping procedure as an address offset within the addressed server device.

Claim 4

Dependent Claim 68 words

Said aperiodic mapping system as set forth in claim 1 wherein said matrix M' comprises the first d rows and n columns of a square n×n matrix M, including configuring said matrix M' so that all d×d submatrices consisting of d consecutive columns of M' are nonsingular and wherein a matrix is defined as nonsingular if and only if its determinant is nonzero or the matrix is invertible.

Claim 5

Dependent Claim 74 words

Said aperiodic mapping system as set forth in claim 3 including configuring said matrix M as an n by n matrix so that either the top or bottom row of said matrix is all `1`s (unitary) and that either the right or left hand columns is all `1`s, the remainder of the matrix being configured so that all bits are the exclusive-OR at the two adjacent bits closest to the unitary column and row.

Claim 6

Independent Claim 228 words

A method for mapping addresses from a first to a second address for improved system performance in a multi-processor computer system having a plurality of memory modules wherein both the processors and memory modules are adapted for concurrent operation, said processor and memory modules being selectively connectable over an interconnection network each processor having an address transformation unit including a multiplier and a matrix storage means, said system including address responsive means for accessing a desired memory module and further address responsive means for accessing a selected offset with a selected memory module, said system further having a physical address architecture comprising n address bits and 2 d separately accessible memory modules where d is <n) and an address format A=(a 0 , a 1 , . . . a n-2 , a n-1 ), said mapping method comprising: a) said processor transmitting a first n bit address to its address transformation unit b) accessing a predetermined permutation matrix M' having d rows and n columns from said matrix storage means c) said multiplier accessing d successive n bit rows of said matrix and performing d bit-matrix multiplications with the n bits of said first address to produce d successive second address bits, and d) said system address responsive means utilizing the generated d bits of the second address as a memory module address in the system memory.

Claim 7

Independent Claim 228 words

A method for mapping addresses from a first to a second address for improved system performance in a multi-processor computer system having a plurality of memory modules wherein both the processors and memory modules are adapted for concurrent operation, said processor and memory modules being selectively connectable over an interconnection network each processor having an address transformation unit including a multiplier and a matrix storage means, said system including address responsive means for accessing a desired memory module and further address responsive means for accessing a selected offset with a selected memory module, said system further having a physical address architecture comprising n address bits and 2 d separately accessible memory modules where d is <n) and an address format A=(a 0 , a 1 , . . . a n-2 , a n-1 ), said mapping method comprising: a) said processor transmitting a first n bit address to its address transformation unit b) accessing a predetermined permutation matrix M' having d rows and n columns from said matrix storage means c) said multiplier accessing d successive n bit rows of said matrix and performing d bit-matrix multiplications with the n bits of said first address to produce d successive second address bits, and d) said system address responsive means utilizing the generated d bits of the second address as a memory module address in the system memory.

Claim 8

Dependent Claim 58 words

Said aperiodic mapping method as set forth in claim 5 wherein there are d memory modules and n logical address bits where (where d is <n), addressing means within an addressed memory module utilizing the n-d bits of the first address which are not altered by the mapping procedure as an address offset within the addressed memory module.

Claim 9

Dependent Claim 68 words

Said aperiodic mapping method as set forth in claim 5 wherein said matrix M' comprises the first d rows and n columns of a square n×n matrix M including said matrix M' being configured so that all d×d submatrices consisting of d consecutive columns of M' are nonsingular, wherein said matrix is defined as nonsingular if and only if its determinant is nonzero or the matrix is invertible.

Claim 10

Dependent Claim 72 words

Said aperiodic mapping method as set forth in claim 7 wherein said n by n matrix M is so configured that either the top or bottom row of said matrix is all `1`s (unitary) and that either the right or left hand columns is all `1`s, the remainder of the matrix being configured so that all bits are the exclusive-OR of the two adjacent bits closest to the unitary column and row.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1995-05-05	1995-11-04	1996-05-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1999-05-05	1999-11-04	2000-05-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2003-05-05	2003-11-04	2004-05-05	$7700.00	Window Closed / Lapsed

Aperiodic mapping system using power-of-two stride access to interleaved devices

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag