Programmable microprocessor cache index hashing function

#This invention relates generally to electronic circuits. More particularly, this invention relates to integrated electronic circuits and cache memory.

#Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing may be used to index and retrieve items in a database or a memory hierarchy because it is usually faster to find the item using the shorter hashed key than to find it using the original value. It may also be used in many encryption algorithms.

#The hashing algorithm is called a hash function. The hash function is used to index the original value or key and then used later each time the data associated with the value or key is to be retrieved. A good hash function also should not produce the same hash value from two different inputs. If it does, this is known as a “collision”. A hash function that offers an extremely low risk of collision may be considered acceptable.

#FIG. 1 is a schematic drawing of a generic index hashing function. Prior Art

#FIG. 2 is a schematic drawing of a programmable index hashing function.

#FIG. 1 is a schematic drawing of an example of a index hashing function. The lower half, B(N)-B(1), 118-104, of the memory address (2N+X bits), 102 is connected to an input of each XOR of N XORs, 150-136, respectively. The upper half, B(2N)-B(N+1), 134-120, of the memory address (2N+X bits), 102, is connected to the other input of each XOR of N XORs, 150-136, respectively. The outputs of the N XORs, 150-136, form a new N-bit memory index, ID(N)-ID1, 166-152. B1, 104, of memory address, 102 is connected to an input of XOR1, 136. B2, 106, of memory address, 102 is connected to an input of XOR2, 138. B3, 108, of memory address, 102 is connected to an input of XOR3, 140. B4, 110, of memory address, 102 is connected to an input of XOR4, 142. B(N−3), 112, of memory address, 102 is connected to an input of XOR(N−3), 144. B(N−2), 114, of memory address, 102 is connected to an input of XOR(N−2), 146. B(N−1), 116, of memory address, 102 is connected to an input of XOR(N−1), 148. B(N), 118, of memory address, 102 is connected to an input of XOR(N), 150. B(N+1), 120, of memory address, 102 is connected to an input of XOR1, 136. B(N+2), 122, of memory address, 102 is connected to an input of XOR2, 138. B(N+3), 124, of memory address, 102 is connected to an input of XOR3, 140. B(N+4), 126, of memory address, 102 is connected to an input of XOR4, 142. B(2N−3), 128, of memory address, 102 is connected to an input of XOR(N−3), 144. B(2N−2), 130, of memory address, 102 is connected to an input of XOR(N−2), 146. B(2N−1), 132, of memory address, 102 is connected to an input of XOR(N−1), 148. B(2N), 134, of memory address, 102 is connected to an input of XOR(N), 150. The outputs of XOR(N)-XOR1, 150-136, form the indexed memory address, ID(N)-ID1, 166-152, respectively.

#FIG. 2 is a schematic drawing of one example of a programmed hashing function. In this example, the bits of the upper half, B(2N)-B(N+1), of memory address, 202, (2N+X bits) are each connected to an input of AND gates, AND(2N)-AND(N+1) respectively. The other input of AND gates, AND(2N)-AND(N+1), are connected to programmable nodes, 278-268, 213, respectively. The programmable nodes, 278-268, 213 may be programmed after a microprocessor is fabricated to improve the performance of the hashing function. The outputs of AND gates, AND(2N)-AND(N+1), 296, 298, 201-211, are connected to an input of each XOR gate, XOR(N)-XOR1, 250-236 respectively. The memory address bits B(N)-B1, 218-204, are connected to a second input of each XOR gate, XOR(N)-XOR1, 250-236, respectively. The outputs, ID(N)-ID1, 266-252, of XOR gates, XOR(N)-XOR1, 250-236, form the N-bit indexed memory address.

#B1, 204, of memory address, 202 is connected to an input of XOR1, 236. B2, 206, of memory address, 202 is connected to an input of XOR2, 238. B3, 208, of memory address, 202 is connected to an input of XOR3, 240. B4, 210, of memory address, 202 is connected to an input of XOR4, 242. B(N−3), 212, of memory address, 202 is connected to an input of XOR(N−3), 244. B(N−2), 214, of memory address, 202 is connected to an input of XOR(N−2), 246. B(N−1), 216, of memory address, 202 is connected to an input of XOR(N−1), 248. B(N), 218, of memory address, 202 is connected to an input of XOR(N), 250. B(N+1), 220, of memory address, 202 is connected to an input of AND(N+1), 294. B(N+2), 222, of memory address, 202 is connected to an input of AND(N+2), 292. B(N+3), 224, of memory address, 202 is connected to an input of AND(N+3), 290. B(N+4), 226, of memory address, 202 is connected to an input of AND(N+4), 288. B(2N−3), 228, of memory address, 102 is connected to an input of AND(2N−3), 286. B(2N−2), 230, of memory address, 202 is connected to an input of AND(2N−2), 284. B(2N−1), 232, of memory address, 202 is connected to an input of AND(2N−1), 282. B(2N), 234, of memory address, 202 is connected to an input of AND(N), 280. Node 213 may be programmed to a logical “high” or “low” and is connected to a second input of AND(N+1), 294. Node 268 may be programmed to a logical “high” or “low” and is connected to a second input of AND(N+2), 292. Node 270 may be programmed to a logical “high” or “low” and is connected to a second input of AND(N+3), 290. Node 272 may be programmed to a logical “high” or “low” and is connected to a second input of AND(N+4), 288. Node 274 may be programmed to a logical “high” or “low” and is connected to a second input of AND(2N−3), 286. Node 276 may be programmed to a logical “high” or “low” and is connected to a second input of AND(2N−2), 284. Node 277 may be programmed to a logical “high” or “low” and is connected to a second input of AND(2N−1), 282. Node 278 may be programmed to a logical “high” or “low” and is connected to a second input of AND(2N), 280. The output, 211, of AND(N+1), 294, is electrically connected to a second input of XOR1, 236. The output, 209, of AND(N+2), 292, is electrically connected to a second input of XOR2, 238. The output, 207, of AND(N+3), 290, is electrically connected to a second input of XOR3, 240. The output, 205, of AND(N+4), 288, is electrically connected to a second input of XOR4, 242. The output, 203, of AND(2N−3), 286, is electrically connected to a second input of XOR(N−3), 244. The output, 201, of AND(2N−2), 284, is electrically connected to a second input of XOR(N−2), 246. The output, 298, of AND(2N−1), 282, is electrically connected to a second input of XOR(N−1), 248. The output, 296, of AND(2N), 280, is electrically connected to a second input of XOR(N), 250. The outputs of XOR(N)-XOR1, 250-236, form the indexed memory address, ID(N)-ID1, 266-252, respectively.