Hash index table hash generator apparatus

• US 4,215,402 A
• Filed: 10/23/1978
• Issued: 07/29/1980
• Est. Priority Date: 10/23/1978
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Houdek, Merle E., Mitchell, Glen R.
• Primary Examiner(s): Smith, Jerry
• Application Number:
  US05/953,675
• Time in Patent Office: 645 Days
• Field of Search: 364/200, 364/900
• US Class Current: 711/216
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

The present invention discloses an apparatus for the efficient translation of virtual addresses to main storage addresses by means of a hash index table which contains main storage addresses. Hash generator apparatus is provided for generating a uniform distribution of hash index table entry addresses from a non-uniform distribution of virtual addresses in a data processing system, where the size of the hash index table is variable and is based on the size of main storage. A field of bits within the virtual address corresponding to the page identification bits are reversed in order and aligned with two groups of bits from a field of bits within the virtual address corresponding to object identification bits, and the three groups of bits are applied to an EXCLUSIVE-OR circuit. The alignment of the three groups of bits and the size of the hash index table entry addresses generated by the present invention are based on the size of the hash index table.

Claims

1. Apparatus for generating an entry address into a table from a virtual address in a data processing system, the data processing system having a main store, the virtual address having (1) a first group of bits for addressing within an object and (2) a second group of bits for addressing a particular object, where the size of the table is variable and is dependent upon the size of the main store, the main store having a plurality of objects, comprising:

first register means for storing a virtual address;

indicating means for indicating the number of entries in the table;

alignment means for aligning the first group of bits relative to the second group of bits based upon the number of entries in the table as indicated by said indicating means;

EXCLUSIVE-OR means connected to receive the first and second groups of bits after they have been aligned by said alignment means and operable to generate a result having a number of bits sufficient to represent the maximum number of entries in the table; and

bit eliminating means for eliminating bits from the result produced by said EXCLUSIVE-OR means based upon the number of entries in the table indicated by said indicating means.

2. Apparatus for generating a hash index table entry address from a virtual address in a data processing system, the data processing system having a main store, the virtual address having a first group of bits for addressing within an object and a second group of bits for addressing a particular object, where the hash index table size is variable and is based upon the size of the main store, the main store having a plurality of objects, comprising:

a virtual address register containing a virtual address for addressing the main store;

indicating means for indicating the number of entries in said hash index table;

alignment means for aligning the first group of bits relative to the second group of bits based upon the number of entries in said hash index table as indicated by said indicating means;

EXCLUSIVE-OR means for EXCLUSIVE-OR'"'"'ing the first group of bits with the second group of bits after the first and second group of bits have been aligned by said alignment means to produce a result having a number of bits encodable to represent the maximum number of entries in said hash index table; and

bit eliminating means for eliminating bits from the result produced by said EXCLUSIVE-OR means based upon the number of entries in said hash index table indicated by said indicating means.

3. The apparatus as set forth in claim 2 further comprising:

means for reversing the order of the first group of bits before applying that group of bits to said alignment means.

4. The apparatus as set forth in claim 2 further comprising:

means for shifting to the left one position the result produced by said EXCLUSIVE-OR means, whereby the implementation of the hash index table in main storage which is addressed on a byte basis is facilitated.

5. The apparatus as set forth in claim 2 further comprising:

adding means for adding the main store address of the beginning of the hash index table to the result obtained from said bit eliminating means whereby the hash index table entry address is produced.

6. The apparatus as claimed in claim 2 wherein said indicating means is comprised of size register means for storing a fixed number of bits, the right-most consecutive bits being set to a first state and the left most consecutive bits being set to a second state, the number of bits in the first state corresponding to the size of the hash index table.

7. The apparatus as claimed in claim 6 wherein said alignment means comprises:

first shift register means;

second shift register means for storing the first group of bits from the virtual address;

inverting means for inverting the bits contained in said size register means;

first connecting means for connecting the output of said inverting means to said first shift register means;

compare circuit means for comparing the bits contained in said first shift register means to the second state and for providing a noncompare signal if at least one bit contained in said first shift register means is not set to the second state;

second connecting means for connecting the noncompare signal provided by said compare circuit means to said first shift register means to cause said first shift register means to shift left and to set the right-most bit in said first shift register means to the second state and for connecting the noncompare signal to said second shift register means to cause said second shift register means to shift right, said first shift register means and said second shift register means thus being shifted left and right, respectively, until all the bits in said first shift register means are in the second state.

8. Apparatus for generating a hash index table entry address from a virtual address in a data processing system, the data processing system having a main store, the virtual address having first and second groups of bits for addressing a particular segment of virtual storage and a third group of bits for addressing within a segment of virtual storage, where the size of the hash index table is variable and is based upon the size of the main store, the main store having a plurality of segments, comprising:

a virtual address register for storing a virtual address;

indicating means for indicating the size of the hash index table;

reversing means for reversing the order of the third group of bits;

alignment means for aligning the first and second groups of bits relative to the group of bits produced by said reversing means based upon the size of the hash index table as indicated by said indicating means;

EXCLUSIVE-OR means connected to receive the first and second groups of bits and the group of bits produced by said alignment means and operable to generate a result having a number of bits encodable to represent the maximum number of entries in the table;

shift left means for shifting to the left one position the result produced by said EXCLUSIVE-OR means;

bit eliminating means for eliminating high order bits from the result produced by said EXCLUSIVE-OR means and said shift left means based upon the size of the hash index table indicated by said indicating means; and

adder means for adding the main store address of the beginning of the hash index table to the result obtained from said bit eliminating means, whereby the hash index table entry address corresponding to the virtual address stored in said virtual address register is obtained.