US4598361A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Allocator for a reduction processor evaluating programs stored as binary directed graphs employing variable-free applicative language codes
Assignee: Unisys Corp
•
Filing: 1985-01-11
•
Granted: 1986-07-01
•
Expires: 2005-01-11
Abstract
Abstract An allocator for a reduction processor which evaluates programs stored as binary graphs employing variable-free applicative language codes. These graphs are made up of nodes, each of which exists in memory and contains as its most significant bit a mark bit which when set indicates that the node is being used in a graph and when reset indicates that the node or storage location is available for future use by the processor. The allocator scans selected groups of storage locations in parallel to see if there are any unused storage locations and then places the addresses of those unused storage locations in a queue for use by the processor.
Inventors
- 👤 Gary L. Logsdon
- 👤 Mark R. Scheevel
- 👤 Frank A. Williams, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 08:48
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
120 words
In a processing system having a memory with a plurality of storage locations, each storage location having a mark bit position which when set indicates that the storage location has been allocated for use and when reset indicates that the storage location is available for use, allocation means comprising: mark bit addressing means coupled to said memory to fetch in parallel mark bits from a plurality of sequential storage locations, said fetched mark bits forming a mark bit vector; checking means coupled to said mark bit addressing means for checking said mark bit vector for reset marked bits; and address formation means for forming addresses for those storage locations represented by the reset mark bits in said mark bit vector.
Claim 2
Dependent Claim
120 words
In a processing system having a memory with a plurality of storage locations, each storage location having a mark bit position which when set indicates that the storage location has been allocated for use and when reset indicates that the storage location is available for use, allocation means comprising: mark bit addressing means coupled to said memory to fetch in parallel mark bits from a plurality of sequential storage locations, said fetched mark bits forming a mark bit vector; checking means coupled to said mark bit addressing means for checking said mark bit vector for reset marked bits; and address formation means for forming addresses for those storage locations represented by the reset mark bits in said mark bit vector.
Claim 3
Dependent Claim
23 words
Allocation means according to claim 1 further including: queuing means coupled to said address formation means for receiving said formed storage location addresses.
Claim 4
Dependent Claim
35 words
Allocation means according to claim 1 wherein: said mark bit addressing means includes reset means coupled to said mark bit positions in said storage locations to reset those mark bits that were fetched in parallel.
Claim 5
Dependent Claim
36 words
Allocation means according to claim 3 wherein: said mark bit addressing means includes scan count means to receive a count of the number of mark bit vectors that are to be fetched from said storage locations.
Claim 6
Dependent Claim
37 words
Allocation means according to claim 4 further including: means to increment said mark bit addressing means and to decrement said scan count means after the fetch of each plurality of mark bits forming a mark bit vector.
Claim 7
Dependent Claim
132 words
In a processing system having a memory which has a plurality of storage locations, each storage location having a mark bit position which when set indicates that the storage location has been allocated and which when reset indicates that the storage location is available for use, the combination comprising: mark bit setting means coupled to said storage locations to set selected mark bits so as to allocate those storage locations; mark bit addressing means to fetch in parallel mark bits from a plurality of sequential storage locations which selected mark bits form a mark bit vector; checking means coupled to said mark bit addressing means to check said mark bit vector for reset mark bits; and address generating means to generate addresses for those storage locations represented by said reset mark bits.
Claim 8
Dependent Claim
132 words
In a processing system having a memory which has a plurality of storage locations, each storage location having a mark bit position which when set indicates that the storage location has been allocated and which when reset indicates that the storage location is available for use, the combination comprising: mark bit setting means coupled to said storage locations to set selected mark bits so as to allocate those storage locations; mark bit addressing means to fetch in parallel mark bits from a plurality of sequential storage locations which selected mark bits form a mark bit vector; checking means coupled to said mark bit addressing means to check said mark bit vector for reset mark bits; and address generating means to generate addresses for those storage locations represented by said reset mark bits.
Claim 9
Dependent Claim
23 words
The combination according to claim 6 further including: queing means coupled to said address generating means for receiving said generated storage location addresses.
Claim 10
Dependent Claim
34 words
Combination according to claim 6 wherein: said mark bit addressing means includes reset means coupled to said mark bit positions in said storage locations to reset those mark bits that were fetched in parallel
Claim 11
Dependent Claim
35 words
Combination according to claim 8 wherein: said mark bit addressing means includes scan count means to receive a count of the number of mark bit vectors that are to be fetched from said storage locations.
Claim 12
Dependent Claim
36 words
Combination according to claim 9 further including: means to increment said mark bit addressing means and to decrement said scan count means after the fetch of each plurality of mark bits forming a mark bit vector.
References Cited (Backward Citations)
US4435752A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-06-30 | 1989-12-30 | 1990-07-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-06-30 | 1993-12-30 | 1994-07-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-06-30 | 1997-12-30 | 1998-07-01 | $7700.00 | Window Closed / Lapsed |