Shift register storage unit with multi-dimensional dynamic ordering

Claim 2

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein bits of the word are accessible to a using unit; means for shifting pluralities of said groups in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting pluralities of said groups in said first dimension from position to position in said matrices in second shift loops each of which excludes said access position; row addressing means for providing manifestations of address bits for identifying a row which contains a word requested by said using unit; row detection means for detecting the presence in said access row of a requested word; means for shifting a plurality of said groups in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position; word addressing means for providing manifestations of address bits of a word requested by said using unit; means for enabling access to said requested word while its representations are in said access positions; and shift control means for controlling the shifting in said respective shift loops so that words recently accessed are maintained in positions for successive shifting into said access positions substantially in a sequence based upon recency of usage.

Claim 3

A storage unit according to claim 1 wherein: said shift control means is arranged to terminate shifting in said first loops and to initiate shifting in said third loops when a requested word is shifted into said access row.

Claim 4

A storage unit according to claim 2 wherein: one of said second loops comprises, in a column of said matrix which includes said access position, bit positions excluding said access position; and others of said second loops each comprises, in a column of said matrix which includes a bit position of said access row other than said access position, bit positions including one bit position of said access row.

Claim 5

A storage unit according to claim 2 wherein: said shift control means Is arranged to terminate shifting in said third loops and to initiate shifting simultaneously in said second and fourth loops when a requested word is shifted into said access position.

Claim 6

A storage unit according to claim 4 wherein said shift control means is arranged to: terminate shifting in said second loops when the number of shifts in said second loops is equal to the number of shifts that took place in said first loops, and terminate shifting in said fourth loops when the number of shifts in said fourth loops is equal to the number of shifts that took place in said third loops.

Claim 7

A storage unit according to claim 2 wherein: said shift control means is arranged to terminate shifting in said third loops and to initiate shifting in said fourth loops when a requested word is shifted into said access position.

Claim 8

A storage unit according to claim 6 wherein: said shift control means is arranged to terminate shifting in said fourth loops and to initiate shifting in said second loops when the number of shifts in said fourth loops is equal to the number of shifts that took place in said third loops.

Claim 9

A storage unit according to claim 7 wherein: said shift control means is arranged to terminate shifting in said second loops when the number of shifts in said second loops is equal to the number of shifts that took place in said first loops.

Claim 10

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein the bits of the word are accessible to a using unit; means for shifting sectors each comprising a plurality of words in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting said sectors in said first dimension from position to position in said matrices in said second shift loops each of which excludes positions in said access row; sector addressing means for providing manifestations of address bits for identifying a requested sector which contains a word requested by said using unit; sector detection means for detecting the presence in said access row of said requested sector; means for shifting words within said requested sector in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position; word addressing means for providing manifestations of address bits of a word requested by said using unit; word detection means for detecting the presence in said access position of a requested word; means for enabling access to said requested word while its representations are in said access positions; and shift control means for controlling the shifting in said respective shift loops so that sectors recently accessed are maintained in rows for successive shifting into said access rows on a priority based upon recency of usage and, within each accessed sector, words recently accessed are maintained in positions for successive shifting into said access positions on a priority based upon recency of usage when a given sector is in the access row.

Claim 11

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein the bits of the word are accessible to a using unit; means for shifting sectors each comprising a plurality of words in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting said sectors in said first dimension from position to position in said matrices in said second shift loops each of which excludes positions in said access row; sector addressing means for providing manifestations of address bits for identifying a requested sector which contains a word requested by said using unit; sector detection means for detecting the presence in said access row of said requested sector; means for shifting words within said requested sector in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position; word addressing means for providing manifestations of address bits of a word requested by said using unit; word detection means for detecting the presence in said access position of a requested word; means for enabling access to said requested word while its representations are in said access positions; and shift control means for controlling the shifting in said respective shift loops so that sectors recently accessed are maintained in rows for successive shifting into said access rows on a priority based upon recency of usage and, within each accessed sector, words recently accessed are maintained in positions for successive shifting into said access positions on a priority based upon recency of usage when a given sector is in the access row.

Claim 12

A storage unit according to claim 9 wherein: said shift control means is arranged to terminate shifting in said first loops and to initiate shifting in said third loops when a requested sector is shifted into said access row.

Claim 13

A storage unit according to claim 10 wherein: said shift control means is arranged to terminate shifting in said third loops and to initiate shifting simultaneously in said second and fourth loops when a requested word is shifted into said access position.

Claim 14

A storage unit according to Claim 11 wherein said shift control means is arranged to: terminate shifting in said second loops when the number of shifts in said second loops is equal to the number of shifts that took place in said forst loops; and terminate shifting in said fourth loops when the number of shifts in said fourth loops is equal to the number of shifts that took place in said third loops.

Claim 15

A storage unit according to claim 10 wherein: said shift control means is arranged to terminate shifting in said third loops and to initiate shifting in said fourth loops when a requested word is shifted into said access position.

Claim 16

A storage unit according to claim 13 wherein: said shift control means is arranged to terminate shifting in said fourth loops when the shifts in said fourth loops have resulted in the word which was in said access positions, after shifting in said first loops and prior to shifting in said third loops, being shifted into the matrix positions adjacent to said access positions.

Claim 17

A storage unit according to claim 14 wherein: said shift control means is arranged to initiate shifting in said second loops when a requested word is shifted into said access positions and to terminate shifting in said second loops when the shifts in said second loops have resulted in the sector which was in said access rows, prior to shifting in said first loops, being shifted into the matrix rows adjacent to said access rows.

Claim 18

A storage unit according to claim 13 wherein: said shift control means is arranged to terminate shifting in said fourth loops when the number of shifts in said fourth loops is qual to the number of shifts that took place in said third loops.

Claim 19

A storage unit according to claim 16 wherein: said shift control means is arranged to initiate shifting in said second loops when shifting in said fourth loops is terminated and to terminate shifting in said second loops when the number of shifts in said second loops is equal to the number of shifts that took place in said first loops.

Claim 20

A storage unit according to claim 9 wherein said shift control means comprises: first and second counting means; means for incrementing said first counting means each time that a shift is accomplished in said first loops and for decrementing said first counting means each time that a shift is accomplished in second loops; means for incrementing said second cutting means each time that a shift is accomplished in said third loops and for decrementing said second counting means each time that a shift is accomplished in said fourth loops; means for terminating shifting in said second loops when said first counting means has been decremented to zero; and means for terminating shifting in said fourth loops when said second counting means has been decremented to zero.

Claim 21

A storage unit in accordance with claim 18 wherein each of said counting means comprises a bi-directional shift means.

Claim 22

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein the bits of the word are accessible to a using unit; means for shifting sectors, each sector comprising the words in related rows of the matrices, in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting pluralities of said groups in said first dimension from position to position in said matrices in second shift loops each of which excludes said access row, said second shift loops being in a direction opposite to that of said first shift loops; sector addressing means for providing manifestations of sector address bits for identifying a requested sector which contains a word requested by said using unit; sector detection means for detecting the presence in said access row of said requested sector; means for shifting words within said requested sector in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position, said fourth shift loops being opposite in direction to said third shift loops; word addressing means for providing manifestations of address bits of a word requested by said using unit; word detection means for detecting the presence in said access position of a requested word; means for enabling access to said requested word while its representations are in said access positions; and shift control means comprising means responsive to said sector detection means for causing shifting in said first loops when said requested sector is not in said access rows, and for terminating shifting in said first loops when said requested sector is in said access rows; means responsive to said sector detection means and to said word detection means for causing shifting in said third loops when said requested sector is in said access rows but said requested word is not in said access positions, and for terminating shifting in said third loops when said requested word is in said access positions; means for causing a number of shifts in said fourth loops that is equal to the number of shifts that were accomplished in said third loops; and means for causing a number of shifts in said second loops that is equal to the number of shifts that were accomplished in said first loops; said shift control means thereby controlling the shifting in said respective shift loops so that sectors most recently accessed are maintained in rows for successive shifting into said access rows in a sequence based upon recency of usage and, within each accessed sector, words most recently accessed are maintained in positions for successive shifting into said access positions in a sequence based upon recency of usage.

Claim 23

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein the bits of the word are accessible to a using unit; means for shifting sectors, each sector comprising the words in related rows of the matrices, in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting pluralities of said groups in said first dimension from position to position in said matrices in second shift loops each of which excludes said access row, said second shift loops being in a direction opposite to that of said first shift loops; sector addressing means for providing manifestations of sector address bits for identifying a requested sector which contains a word requested by said using unit; sector detection means for detecting the presence in said access row of said requested sector; means for shifting words within said requested sector in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position, said fourth shift loops being opposite in direction to said third shift loops; word addressing means for providing manifestations of address bits of a word requested by said using unit; word detection means for detecting the presence in said access position of a requested word; means for enabling access to said requested word while its representations are in said access positions; and shift control means comprising means responsive to said sector detection means for causing shifting in said first loops when said requested sector is not in said access rows, and for terminating shifting in said first loops when said requested sector is in said access rows; means responsive to said sector detection means and to said word detection means for causing shifting in said third loops when said requested sector is in said access rows but said requested word is not in said access positions, and for terminating shifting in said third loops when said requested word is in said access positions; means for causing a number of shifts in said fourth loops that is equal to the number of shifts that were accomplished in said third loops; and means for causing a number of shifts in said second loops that is equal to the number of shifts that were accomplished in said first loops; said shift control means thereby controlling the shifting in said respective shift loops so that sectors most recently accessed are maintained in rows for successive shifting into said access rows in a sequence based upon recency of usage and, within each accessed sector, words most recently accessed are maintained in positions for successive shifting into said access positions in a sequence based upon recency of usage.

Claim 24

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein the bits of the word are accessible to a using unit; means for shifting pluralities of said groups in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting pluralities of said groups in said first dimension from position to position in said matrices in second shift loops one of which comprises, in a column of said matrix which includes said access position, bit positions excluding said access position and others of which comprise, in columns of said matrix which do not include said access position, bit positions including one bit position of said access row; row addressing means for providing manifestations of address bits for identifying a row which contains a word requested by said using unit; row detection means for detecting the presence in said access row of a requested word; means for shifting a plurality of said groups in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position; word addressing means for providing manifestations of address bits of a word requested by said using unit; word detection means for detecting the presence in said access position of a requested word; means for enabling access to said requested word while its representations are in said access positions; and shift control means for controlliNg the shifting in said respective shift loops so that words recently accessed are maintained in positions for successive shifting into said access positions substantially on a priority based upon recency of usage.

Claim 25

A storage unit for storing representations of words of data which comprises: a plurality of shiftable memory matrices for storing said representations in related positions, a group of related positions containing the representations constituting a word, each matrix including an access position wherein the bits of the word are accessible to a using unit; means for shifting pluralities of said groups in a first dimension from position to position in each of said matrices in first shift loops which include positions in each of said matrices which comprise an access row which includes said access position, and for shifting pluralities of said groups in said first dimension from position to position in said matrices in second shift loops one of which comprises, in a column of said matrix which includes said access position, bit positions excluding said access position and others of which comprise, in columns of said matrix which do not include said access position, bit positions including one bit position of said access row; row addressing means for providing manifestations of address bits for identifying a row which contains a word requested by said using unit; row detection means for detecting the presence in said access row of a requested word; means for shifting a plurality of said groups in a second dimension from position to position in said access rows in third shift loops which include said access position and in fourth shift loops which exclude said access position; word addressing means for providing manifestations of address bits of a word requested by said using unit; word detection means for detecting the presence in said access position of a requested word; means for enabling access to said requested word while its representations are in said access positions; and shift control means for controlliNg the shifting in said respective shift loops so that words recently accessed are maintained in positions for successive shifting into said access positions substantially on a priority based upon recency of usage.

Claim 26

A storage unit according to claim 21 wherein: said shift control means is arranged to terminate shifting in said first loops and to initiate shifting in said third loops when a requested word is shifted into said access row.

Claim 27

A storage unit according to claim 22 wherein: said shift control means is arranged to terminate shifting in said third loops and to initiate shifting in said fourth loops when a requested word is shifted into said access position.

Claim 28

A storage unit according to claim 23 wherein said shift control unit is arranged to: terminate shifting in said fourth loops and initiate shifting in said second loops when the shifts in said fourth loops have resulted in the word that was in said access positions, after shifting in said first loops and prior to shifting in said third loops, being shifted into the matrix positions adjacent to said access positions; and terminate shifting in said second loops when the shifts in second loops have resulted in the word that was in said access positions, prior to shifting in said first loops, being shifted into the matrix row adjacent to said access row.

Claim 29

A storage unit according to claim 23 wherein said shift control means is arranged to: terminate shifting in said fourth loops and to initiate shifting in said second loops when the number of shifts in said fourth loops is equal to the number of shifts that took place in said third loops, and terminate shifting in said second loops when the number of shifts in said second loops is equal to the number of shifts that took place in said first loops.