US5313611A — Method and apparatus for maintaining a lookup tab…

Claim 1

Independent Claim 205 words

An apparatus for building and accessing a table storing an evaluated function value for each of a plurality of points in a domain of a function, comprising: (1) means for generating an input address which identifies a selected domain point, (2) a memory device for providing a lookup table entry value in response to said input address, said memory device comprising: a page table storage means for mapping the input address to a storage location, wherein the input address is initially unallocated and mapped to a first default storage location shared with other input addresses and containing a default value, and wherein the input address is subsequently allocated and mapped to a corresponding second storage location allocated to said input address, (3) means for determining whether said input address is allocated based on the entry table value provided in response to the input address, (4) means for determining the value of said function at said selected domain point when the input address is unallocated, and (5) means for storing said determined function value in a storage location allocated to said input address, said means for storing comprising: means for modifying said page table storage means to map said input address to said allocated storage location.

Claim 2

Independent Claim 205 words

An apparatus for building and accessing a table storing an evaluated function value for each of a plurality of points in a domain of a function, comprising: (1) means for generating an input address which identifies a selected domain point, (2) a memory device for providing a lookup table entry value in response to said input address, said memory device comprising: a page table storage means for mapping the input address to a storage location, wherein the input address is initially unallocated and mapped to a first default storage location shared with other input addresses and containing a default value, and wherein the input address is subsequently allocated and mapped to a corresponding second storage location allocated to said input address, (3) means for determining whether said input address is allocated based on the entry table value provided in response to the input address, (4) means for determining the value of said function at said selected domain point when the input address is unallocated, and (5) means for storing said determined function value in a storage location allocated to said input address, said means for storing comprising: means for modifying said page table storage means to map said input address to said allocated storage location.

Claim 3

Dependent Claim 74 words

The apparatus of claim 1 wherein said page table storage means comprises a page pointer storage location for storing a page pointer for a page of input addresses, wherein a page pointer is initially a default pointer which identifies a first page of storage locations shared by multiple input addresses, and wherein said page pointer subsequently identifies a second allocated page of storage locations allocated to input addresses within said page of input addresses.

Claim 4

Dependent Claim 39 words

The apparatus of claim 2 wherein said means for modifying said page table comprises means for replacing a default page pointer with a new page pointer identifying a set of storage locations allocated to input addresses with said page.

Claim 5

Dependent Claim 22 words

The apparatus of claim 3 further comprising initializing means for initializing each storage location within said allocated page to said default value.

Claim 6

Dependent Claim 22 words

The apparatus of claim 4 wherein said initializing means comprises means for copying a default page identified by said default page pointer.

Claim 7

Dependent Claim 44 words

The apparatus of claim 3 wherein said page pointer storage location comprises a page number storage portion for storing a page number identifying a set of storage locations and an attribute storage portion for storing an attribute identifier which specifies storage location access attributes.

Claim 8

Dependent Claim 68 words

The apparatus of claim 1 wherein said input address includes a sequence of dimensional pointers which identify said input point in a multidimensional domain, and wherein said memory device further comprises: means for deriving a first pointer which identifies a multidimensional sub-array of domain points which includes said input point, and means for deriving a second pointer which identifies said input point in said multidimensional sub-array of points.

Claim 9

Independent Claim 160 words

A method for building and accessing a table storing an evaluated function value for each of a plurality of points in a domain of a function comprising the steps of: generating an input address which identifies a selected domain point, mapping the input address to a corresponding storage location in a memory device, wherein the input address is initially unallocated and mapped to a default storage location shared with other input addresses and containing a default lookup table value, and wherein the input address is subsequently allocated and mapped to a corresponding storage location allocated to said input address, determining whether said input address is allocated based on the entry table value provided in response to the input address, determining the value of said function at said selected domain point when the input address is unallocated, storing said determined function value in a storage location allocated to said input address, and remapping said input address to said allocated storage location.

Claim 10

Independent Claim 160 words

A method for building and accessing a table storing an evaluated function value for each of a plurality of points in a domain of a function comprising the steps of: generating an input address which identifies a selected domain point, mapping the input address to a corresponding storage location in a memory device, wherein the input address is initially unallocated and mapped to a default storage location shared with other input addresses and containing a default lookup table value, and wherein the input address is subsequently allocated and mapped to a corresponding storage location allocated to said input address, determining whether said input address is allocated based on the entry table value provided in response to the input address, determining the value of said function at said selected domain point when the input address is unallocated, storing said determined function value in a storage location allocated to said input address, and remapping said input address to said allocated storage location.

Claim 11

Dependent Claim 64 words

The method of claim 8 wherein said mapping step comprises the step of: storing a page pointer for a page of input addresses, wherein said page pointer is initially a default pointer which identifies a page of storage locations shared by multiple input addresses and wherein said page pointer subsequently identifies a set of storage locations allocated to said input addresses within said page.

Claim 12

Dependent Claim 34 words

The method of claim 9 wherein said remapping step comprises the step of replacing the default page pointer with a new page pointer identifying a set of storage locations allocated to said input addresses.

Claim 13

Dependent Claim 24 words

The method of claim 10 further comprising the step of initializing each storage location of said set of storage locations to said default value.

Claim 14

Dependent Claim 23 words

The method of claim 11 wherein said initializing step comprises the step of copying a default page identified by said default page pointer.

Claim 15

Dependent Claim 34 words

The method of claim 12 wherein storing said page pointer comprises the steps of: storing a page number identifying a set of storage locations and storing an attribute identifier which specifies storage location attributes.

Claim 16

Independent Claim 123 words

A method for dynamically allocating storage memory for storing a plurality of function values, each stored function value representing a value of a function evaluated at a selected domain point of the function's domain, the method comprising the steps of: generating an input address representative of a selected domain point, selecting, from a page table storage means, a page pointer which indicated whether said input address is allocated, selecting, if said input address is unallocated, a new portion of said memory, said new portion comprising a new storage location allocated to said input address, evaluating the function at the selected domain point, and storing in said new storage location, the function value evaluated at the selected domain point identified by said input address.

Claim 17

Independent Claim 123 words

A method for dynamically allocating storage memory for storing a plurality of function values, each stored function value representing a value of a function evaluated at a selected domain point of the function's domain, the method comprising the steps of: generating an input address representative of a selected domain point, selecting, from a page table storage means, a page pointer which indicated whether said input address is allocated, selecting, if said input address is unallocated, a new portion of said memory, said new portion comprising a new storage location allocated to said input address, evaluating the function at the selected domain point, and storing in said new storage location, the function value evaluated at the selected domain point identified by said input address.

Claim 18

Dependent Claim 32 words

The method of claim 14 further comprising the step of: determining if said selected page pointer includes a default page number identifying a default physical page of storage locations in said memory.

Claim 19

Dependent Claim 56 words

The method of claim 15 wherein said step of determining if said selected page pointer includes a default page number comprises the step of determining whether said default physical page contains at least one storage location containing a default value which indicates that the function value is unknown for all points whose input addresses are unallocated.

Claim 20

Dependent Claim 44 words

The method of claim 15 wherein said step of selecting a new portion of memory comprises the step of replacing said default page number of said page pointer with a physical page number identifying a new physical page of storage locations in said memory.

Claim 21

Dependent Claim 98 words

The method of claim 14 wherein said input address includes a sequence of dimensional pointers which identify said input point in a multidimensional domain, and wherein said step of determining if said memory contains a storage location allocated to said input address comprises the steps of: deriving from a higher order portion of each said dimensional pointer, a first pointer which identifies a multidimensional sub-array of domain points which includes said input point, and deriving from a lower portion of each said dimensional pointer, a second pointer which identifies said input point in said multidimensional sub-array of points.

Claim 22

Dependent Claim 51 words

The method of claim 18 wherein deriving said first pointer comprises the step of: concatenating said higher order portions of each dimensional pointer to form said first pointer; and wherein deriving said second pointer comprises the steps of: concatenating said lower portions of said dimensional pointer to form said second pointer.

Claim 23

Dependent Claim 38 words

The method of claim 19 further comprising the steps of: selecting dimensionality indicia defining demarcations, within a input address, between the respective dimensional pointers and using the dimensionality indicia to identify the dimensional pointers within the input address.

Claim 24

Independent Claim 99 words

A method for evaluating a function comprising the steps of: generating an input address representation of the function input value, searching a stored lookup table, based on the address representation, for the corresponding function value, determining the function value explicitly if a default value is stored in the lookup table, storing the determined function value at the corresponding address representation, said storing step comprising: determining if said input address is allocated, selecting, if said input address is unallocated, a newly allocated storage location allocated to said input address, and remapping said input address to said newly allocated storage location.

Claim 25

Independent Claim 99 words

A method for evaluating a function comprising the steps of: generating an input address representation of the function input value, searching a stored lookup table, based on the address representation, for the corresponding function value, determining the function value explicitly if a default value is stored in the lookup table, storing the determined function value at the corresponding address representation, said storing step comprising: determining if said input address is allocated, selecting, if said input address is unallocated, a newly allocated storage location allocated to said input address, and remapping said input address to said newly allocated storage location.

Claim 26

Independent Claim 140 words

A method for building and accessing a function table which stores function values in function table addresses that correspond to points in the function's input domain, the method comprising steps of: initializing a page table to map input domain points to a shared region of the function table where a default value is stored as a function value; selecting a domain point in the function's input domain; mapping the domain point to a function table address; reading a function value stored in the function table address; if the function value is the default value then (1) evaluating the function for the input domain point, (2) storing the evaluated function value in a non-shared function table address, and (3) modifying the page table to map the domain point to the non-shared function table address in which the output value is stored.

Claim 27

Independent Claim 140 words

A method for building and accessing a function table which stores function values in function table addresses that correspond to points in the function's input domain, the method comprising steps of: initializing a page table to map input domain points to a shared region of the function table where a default value is stored as a function value; selecting a domain point in the function's input domain; mapping the domain point to a function table address; reading a function value stored in the function table address; if the function value is the default value then (1) evaluating the function for the input domain point, (2) storing the evaluated function value in a non-shared function table address, and (3) modifying the page table to map the domain point to the non-shared function table address in which the output value is stored.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1997-05-16	1997-11-15	1998-05-17	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2001-05-16	2001-11-15	2002-05-17	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2005-05-16	2005-11-15	2006-05-17	$7700.00	Window Closed / Lapsed

Method and apparatus for maintaining a lookup table for storing function values

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag