IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0392035
(1999-09-08)
|
발명자
/ 주소 |
- Davis, Charlotte Elizabeth
- Fisher, Bradford Austin
- Greenfield, Jonathan Scott
|
출원인 / 주소 |
- International Business Machines Corporation
|
대리인 / 주소 |
Ray-Yarletts, Jeanine S.Doubet, Marcia L.
|
인용정보 |
피인용 횟수 :
7 인용 특허 :
6 |
초록
▼
A method, system, and computer program product code using a two-tiered cache for hierarchically structured data. The present invention significantly reduces the frequency of computationally intense processing used to retrieve hierarchically structured data and reduces the system cache storage requir
A method, system, and computer program product code using a two-tiered cache for hierarchically structured data. The present invention significantly reduces the frequency of computationally intense processing used to retrieve hierarchically structured data and reduces the system cache storage requirements for maintaining coalesced images.
대표청구항
▼
A method, system, and computer program product code using a two-tiered cache for hierarchically structured data. The present invention significantly reduces the frequency of computationally intense processing used to retrieve hierarchically structured data and reduces the system cache storage requir
A method, system, and computer program product code using a two-tiered cache for hierarchically structured data. The present invention significantly reduces the frequency of computationally intense processing used to retrieve hierarchically structured data and reduces the system cache storage requirements for maintaining coalesced images. cond level hash index structure; building a third-level hash index structure; building a fourth-level hash index structure; establishing a link between an entry in the first-level index structure and a unique entry in the second-level index structure; establishing a link between an entry in the second-level index structure and a unique entry in the third-level index structure; and establishing a link between an entry in the third-level index structure and a unique entry in the fourth-level index structure. 18. The method of claim 17, wherein the act of building a first level hash index structure comprises building a link-list hash structure. 19. The method of claim 17, wherein the act of building a second-level hash index structure comprises building a variable-length hash structure. 20. The method of claim 19 wherein the act of building a second-level hash index structure comprises building a link-list hash structure. 21. The method of claim 17, further comprising establishing a link between an entry in the fourth-level hash index structure and a data object. 22. The method of claim 21, further comprising: receiving an object identifier; identifying an entry in said first-level hash index structure based on the object identifier; identifying an entry in said second-level hash index structure based on the identified entry in said first-level hash index structure; identifying an entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; and identifying an entry in said fourth-level hash index structure based on the identified entry in said second-level hash index structure. 23. The method of claim 22, further comprising retrieving a data object indicated by the identified entry in said fourth-level hash index structure. 24. The method of claim 23, wherein the act of retrieving a data object comprises using a location component, where a first portion of said location component indicates a file, and a second portion of said location component indicates an offset into the file. 25. The method of claim 24, wherein the first portion of said location component comprises a 1-byte field, and the second portion of said location component comprises a 4-byte field. 26. The method of claim 22, wherein the act of receiving an object identifier comprises receiving a numeric identifier. 27. The method of claim 22, wherein the act of receiving an object identifier comprises receiving an alphanumeric identifier. 28. The method of claim 22, wherein the act of identifying an entry in said second-level hash index structure comprises traversing a link between the identified first-level hash index structure entry and an entry in said second-level hash index structure. 29. The method of claim 22, wherein the act of identifying an entry in said second-level hash index structure comprises: identifying a first entry in said second-level hash index structure based on the identified entry in said first-level hash index structure; and traversing said second-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said second-level hash index structure. 30. The method of claim 22, further comprising building an overflow structure; and establishing a link between the overflow structure and an entry in the second-level hash index structure. 31. The method of claim 30, wherein the act of identifying an entry in said second-level hash index structure uses the overflow structure. 32. The method of claim 17, wherein the act of building a third-level hash index structure comprises building a link-list hash structure. 33. The method of claim 17, wherein the act of identifying an entry in said third-level hash index structure comprises traversing a link between the identified second-level hash index structure entry and an entry in said third-level index structure. 34 . The method of claim 17, wherein the act of identifying an entry in said third-level hash index structure comprises: identifying a first entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; and traversing said third-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said third-level hash index structure. 35. The method of claim 17, further comprising: building an overflow structure; and establishing a link between the overflow structure and an entry in the second-level hash index structure and an entry in the third-level hash index structure. 36. The method of claim 35, wherein the act of building said overflow structure comprises building an ordered hash structure. 37. The method of claim 35, wherein the act of identifying an entry in said third-level hash index structure uses the overflow structure. 38. A program storage device, readable by a programmable control device, comprising instructions stored on the program storage device for causing the programmable control device to build a tiered hash index structure, including instructions to: build a first-level hash index structure having a predetermined number of entries; build a second-level hash index structure; a build a third-level hash index structure; a build a fourth-level hash index structure; to establish a link between an entry in the first-level hash index structure and a unique entry in the second-level hash index structure; establish a link between an entry in the second-level hash index structure and a unique entry in the third-level hash index structure; and establish a link between an entry in the third-level hash index structure and a unique entry in the fourth-level hash index structure. 39. The program storage device of claim 38, wherein the instructions to build a second-level hash index structure comprise instructions to build a variable-length hash structure. 40. The program storage device of claim 38, further comprising instructions to: receive an object identifier; identify an entry in said first-level hash index structure based on the object identifier; identify an entry in said second-level hash index structure based on the identified entry in said first-level hash index structure; identify an entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; and identify an entry in said fourth-level hash index structure based on the identified entry in said second-level hash index structure. 41. The program storage device of claim 40, further comprising instructions to retrieve a data object indicated by the identified entry in said fourth-level hash index structure. 42. The program storage device of claim 40, wherein the instructions to receive an object identifier comprise instructions to receive a numeric identifier. 43. The program storage device of claim 40, wherein the instructions to receive an object identifier comprise instructions to receive an alphanumeric identifier. 44. The program storage device of claim 40, wherein the instructions to identify an entry in said second-level hash index structure comprise instructions to: identify a first entry in said second-level hash index structure based on the identified entry in said first-level hash index structure; traverse said second-level hash index structure beginning at the identified first entry; and identify a second entry in said second-level hash index structure based on the object identifier. 45. The program storage device of claim 44, wherein the instructions to identify the second entry in said second-level hash index structure comprise instructions to compare the object identifier with a portion of each entry traversed during the act of traversing said second-level hash index structure. 46. The program stora ge device of claim 40, wherein the instructions to identify an entry in said third-level hash index structure comprise instructions to: identify a first entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; traverse said third-level hash index structure beginning at the identified first entry; and identify a second entry in said third-level hash index structure based on the object identifier. 47. The program storage device of claim 46, wherein the instructions to identify the first entry in said third-level hash index structure comprise instructions to traverse a link between the identified second-level hash index structure entry and an entry in said third-level hash index structure. 48. The program storage device of claim 47, wherein the instructions to identify the second entry in said third-level hash index structure comprise instructions to compare the object identifier with a portion of each entry traversed during the act of traversing said third-level hash index structure. 49. The program storage device of claim 46, further comprising instructions to: build an overflow structure; and establish a link between the overflow structure and an entry in the second-level hash index structure and an entry in the third-level hash index structure. 50. The program storage device of claim 49, wherein the instructions to build said overflow structure comprise instructions to build an ordered hash structure. 51. The program storage device of claim 49, wherein the instructions to identify a first entry in said third-level hash index structure comprise instructions to use the overflow structure. 52. The method of claim 17, wherein the act of building said fourth-level hash index structure comprises building a link-list structure. 53. The program storage device of claim 17, wherein the instructions to build said fourth-level hash index structure comprise instructions to build a link-list structure. 54. The method of claim 22, wherein the act of identifying an entry in said fourth-level hash index structure comprises: identifying a first entry in said fourth-level hash index structure based on the identified entry in said third-level hash index structure; and traversing said fourth-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said fourth-level hash index structure. 55. The method of claim 54, further comprising building an overflow structure; and establishing a link between the overflow structure and an entry in the third-level hash index structure and an entry in the fourth-level hash index structure. 56. The method of claim 55, wherein the act of building said overflow structure comprises building an ordered hash structure. 57. The method of claim 55, wherein the act of identifying the first entry in said fourth-level hash index structure uses the overflow structure. 58. The program storage device of claim 40, wherein the instructions to identify an entry in said fourth-level hash index structure comprise instructions to: identify a first entry in said fourth-level hash index structure based on the identified entry in said third-level hash index structure; and traverse said fourth-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said fourth-level hash index structure. and said first and second addend and augend bits, said first threshold logic gate generates a first intermediate bit based on a comparison between a concatenation of said second addend and augend bits and zero, and combinatorial boolean logic that employs said intermediate bits to generate said carry out bit. 2. The microprocessor as recited in claim 1 wherein said second threshold logic gate generates a second intermediate bit based on a comparison between a concatenation of said second addend and augend bits and two. 3. The microprocessor as recited in claim 1 wherein said third threshold logic gate generates a third intermediate bit based on a comparison between a concatenation of said first addend and augend bits and said carry in bit and four. 4. The microprocessor as recited in Claim 1 wherein said at least one further includes a plurality of said circuits coupled together to form at least a part of a multiplier circuit. 5. A microprocessor, comprising: a cache memory; and an arithmetic and logic unit containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: first, second and third threshold logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, and combinatorial boolean logic that employs said intermediate bits to generate said carry out bit, said combinatorial boolean logic having first, second and third AND gates and first and second OR gates, wherein said second OR gate is coupled to outputs of said first, second and third AND gates, and an output of said first OR gate is coupled to an input of said second AND gate. 6. The microprocessor as recited in claim 5 wherein said combinatorial boolean logic generates said carry out bit from said first augend bit and said carry in bit. 7. A microprocessor, comprising: a cache memory; and an arithmetic and logic unit containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: first, second and third threshold logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, each of said first, second and third threshold logic gates having: a summer, having at least two binary inputs with corresponding discrete weights, that generates a weighted sum of input binary digits presented at said at least two binary inputs, and a quantizer, coupled to said summer, that generates an output binary digit at a binary output thereof that is a function of said weighted sum; and combinatorial boolean logic that employs said intermediate bits to generate said carry out bit. 8. The microprocessor as recited in claim 7 wherein said discrete weights are integer multiples of a predetermined number. 9. The microprocessor as recited in claim 7 wherein each of said at least two binary inputs comprises: a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight; and a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular input binary digit. 10. The microprocessor as recited in claim 7 wherein said circuit further includes a threshold input that provides a current that represents a threshold number to said quantizer, said output binary digit being a function of a relationship between said weighted sum and said threshold number. 11. A digital signal processor, comprising: a signal input; a signal output; and a signal transformation unit employing said signal input to generate said signal output and containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: first, second and third threshold logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, said first threshold logic gate generates a first intermediate bit based on a comparison between a concatenation of said second addend and augend bits and zero, and combinatorial boolean logic that employs said intermediate bits to generate said carry out bit. 12. The DSP as recited in claim 11 wherein said second threshold logic gate generates a second intermediate bit based on a comparison between a concatenation of said second addend and augend bits and two. 13. The DSP as recited in claim 11 wherein said third threshold logic gate generates a third intermediate bit based on a comparison between a concatenation of said first addend and augend bits and said carry in bit and four. 14. A digital signal processor, comprising: a signal input; a signal output; and a signal transformation unit employing said signal input to generate said signal output and containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: first, second and third threshold logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, and combinatorial boolean logic that employs said intermediate bits to generate said carry out bit, said combinatorial boolean logic comprises first, second and third AND gates and first and second OR gates, wherein said second OR gate is coupled to outputs of said first, second and third AND gates, and an output of said first OR gate is coupled to an input of said second AND gate. 15. The DSP as recited in claim 14 wherein said combinatorial boolean logic generates said carry out bit from said first augend bit and said carry in bit. 16. A digital signal processor, comprising: a signal input; a signal output; and a signal transformation unit employing said signal input to generate said signal output and containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: first, second and third threshold logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, each of said first, second and third threshold logic gates having: a summer, having at least two binary inputs with corresponding discrete weights, that generates a weighted sum of input binary digits presented at said at least two binary inputs, and a quantizer, coupled to said summer, that generates an output binary digit at a binary output thereof that is a function of said weighted sum; and combinatorial boolean logic that employs said intermediate bits to generate said carry out bit. 17. The DSP as recited in claim 16 wherein said discrete weights are integer multiples of a predetermined number. 18. The DSP as recited in claim 16 wherein each of said at least two binary inputs comprises: a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight; and a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular input binary digit. 19. The DSP as recited in claim 16 wherein said circuit further includes a threshold input that provides a current that represents a threshold number to said quantizer, said output binary digit being a function of a relationship between said weighted sum and said threshold numbe r. 20. The DSP as recited in claim 16 wherein said at least one further includes a plurality of said circuits coupled together to form at least a part of a multiplier circuit.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.