US5563987A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pagemap memory representation in RISC processor printers
Assignee: International Business Machines Corp
•
Filing: 1994-10-28
•
Granted: 1996-10-08
•
Expires: 2014-10-28
Abstract
Abstract Disclosed is a process and apparatus for pagemap memory representation in RISC controlled printers. The technique disclosed optimizes pagemaps in memory to minimize losses in processor efficiency of processors having data caches, TLB's and virtual memory, due to unavailability of desired data in first the data cache, then the random access memory. The technique is particularly applicable to RISC processors having a plurality of table lookaside buffers, each containing the address of a frame or page of memory, each frame comprising a finite number of bytes of data. This is accomplished by dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order. Each of said swaths having a height measured in scans which is a function of frame size, data cache line size and set associativity of the data cache, but which is an integral multiple of the number of words in a data cache line. The optimization of set associativity of data cache line utilization is accomplished by determining that the swath height divided by the number of words in a data cache line are not evenly divided by two.
Inventors
- 👤 Steven M. Scott
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 22:04
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06K; G06K15/00; G06F12/1027; G06K2215/00; G06K2215/0002; G06K2215/0062; G06K2215/0065
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
147 words
A method of optimizing pagemaps in computer memory to minimize losses in efficiency of processing with processors having data caches, TLB's and virtual memory, the loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; comprising the steps of: (1) dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; (2) each of said swaths having a height measured in scans which is an integral multiple of the number of words in a data cache line; and (3) printing the pagemap by providing the output of the processor to a print head.
Claim 2
Independent Claim
147 words
A method of optimizing pagemaps in computer memory to minimize losses in efficiency of processing with processors having data caches, TLB's and virtual memory, the loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; comprising the steps of: (1) dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; (2) each of said swaths having a height measured in scans which is an integral multiple of the number of words in a data cache line; and (3) printing the pagemap by providing the output of the processor to a print head.
Claim 3
Dependent Claim
53 words
A method of optimizing pagemaps in memory to minimize losses in processor efficiency in accordance with claim 1 including the step of optimizing set associativity of data cache line utilization by determining that the swath height divided by the number of words in a data cache line are not evenly divided by two.
Claim 4
Independent Claim
36 words
A method of optimizing pagemaps in memory to minimize losses in processor efficiency in accordance with claims 1 or 2 including the step of transforming the output of said pagemap from memory into row major order.
Claim 5
Dependent Claim
41 words
A method of optimizing pagemaps in memory to minimize losses in processor efficiency wherein said processor comprises a reduced instruction set processor and in accordance with claim 1, including the step of rasterizing into scans information received from a host processor.
Claim 6
Independent Claim
150 words
A method of optimizing pagemaps in computer memory to minimize losses in efficiency of processing with processors having data caches, TLB's and virtual memory, the loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; comprising the steps of: (1) dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; (2) each of said swaths having a height measured in scans which is a function of frame size, data cache line size and set associativity of said data cache; and (3) printing the pagemap by providing the output of the processor to a print head.
Claim 7
Independent Claim
150 words
A method of optimizing pagemaps in computer memory to minimize losses in efficiency of processing with processors having data caches, TLB's and virtual memory, the loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; comprising the steps of: (1) dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; (2) each of said swaths having a height measured in scans which is a function of frame size, data cache line size and set associativity of said data cache; and (3) printing the pagemap by providing the output of the processor to a print head.
Claim 8
Dependent Claim
49 words
A method of optimizing pagemaps in computer memory to minimize losses in efficiency of processing in accordance with claim 5, including the step of providing the number of scans in each of said swaths equal to an integral multiple of the number of words in a data cache line.
Claim 9
Dependent Claim
44 words
A method of optimizing pagemaps in memory to minimize losses in processor efficiency wherein said processor comprises a reduced instruction set processor, and in accordance with claim 6, including the step of rasterizing into scans information received from a host processor desired for printing.
Claim 10
Dependent Claim
33 words
A method of optimizing pagemaps in memory to minimize losses in processor efficiency in accordance with claim 7 including the step of transforming the output of said rasterizing step into row major order.
Claim 11
Dependent Claim
53 words
A method of optimizing pagemaps in memory to minimize losses in processor efficiency in accordance with claim 5 including the step of optimizing set associativity of data cache line utilization by determining that the swath height divided by the number of words in a data cache line are not evenly divided by two.
Claim 12
Dependent Claim
157 words
A printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing, said processor including random access main memory, at least a data cache, virtual memory and a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; said loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; means for dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; each of said swaths having a height measured in scans which is an integral multiple of the number of words in a data cache line, and print head means for printing the pagemap.
Claim 13
Dependent Claim
157 words
A printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing, said processor including random access main memory, at least a data cache, virtual memory and a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; said loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; means for dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; each of said swaths having a height measured in scans which is an integral multiple of the number of words in a data cache line, and print head means for printing the pagemap.
Claim 14
Dependent Claim
72 words
A printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing when printing in accordance with claim 10 including means for optimizing set associativity of data cache line utilization by determining that the swath height divided by the number of words in a data cache line are not evenly divided by two.
Claim 15
Dependent Claim
55 words
A printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing when printing, in accordance with claim 10, including pagemap transformer means for transforming the output of said pagemap from memory into row major order.
Claim 16
Dependent Claim
55 words
A printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing when printing, in accordance with claim 11, including pagemap transformer means for transforming the output of said pagemap from memory into row major order.
Claim 17
Dependent Claim
51 words
A printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing when printing, in accordance with claim 10 or 11 or 12, wherein said processor comprises a reduced instruction set processor.
Claim 18
Dependent Claim
143 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing with processors having data caches and virtual memory, the loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data: (1) means for dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; (2) each of said swaths having a height measured in scans which is an integral multiple of the number of words in a data cache line; and (3) print head means for receiving the output of the processor for printing the pagemap.
Claim 19
Dependent Claim
143 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing with processors having data caches and virtual memory, the loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data: (1) means for dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; (2) each of said swaths having a height measured in scans which is an integral multiple of the number of words in a data cache line; and (3) print head means for receiving the output of the processor for printing the pagemap.
Claim 20
Dependent Claim
54 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing in accordance with claim 15 including means for determining that the swath height divided by the number of words in a data cache line are not evenly divided by two and thereby optimizing set associativity of data cache line utilization.
Claim 21
Dependent Claim
36 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing in accordance with claim 16 including pagemap transformer means for transforming the output of said pagemap from memory into row major order.
Claim 22
Dependent Claim
28 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing in accordance with claim 17 wherein said processor comprises a reduced instruction set processor.
Claim 23
Dependent Claim
47 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing in accordance with claim 17 including means for providing the number of scans in each of said swaths equal to an integral multiple of the number of words in a data cache line.
Claim 24
Dependent Claim
43 words
Apparatus for optimizing pagemaps in computer memory to minimize losses in efficiency of processing in accordance with claim 15 wherein said processor comprises a reduced instruction set processor; a host computer and means for rasterizing into scans information received from said host computer.
Claim 25
Dependent Claim
190 words
A printing system comprising a host computer for sending commands and data in a predetermined format as specified by at least the operating system of the computer, to a printer; said printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing, said processor including random access main memory, at least a data cache, virtual memory and a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; said loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; means for dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; each of said swaths having a height measured in scans which is a function of frame size, data cache line size and set associativity of said data cache; and print head means for printing the pagemap.
Claim 26
Dependent Claim
190 words
A printing system comprising a host computer for sending commands and data in a predetermined format as specified by at least the operating system of the computer, to a printer; said printer including a processor for receiving, and operating upon a stream of data and reforming the data to be printed into a pagemap to minimize losses in efficiency of processing, said processor including random access main memory, at least a data cache, virtual memory and a plurality of table lookaside buffers associated with the processor, each table lookaside buffer containing the address of a frame of memory, each frame comprising a finite number of bytes of data; said loss in efficiency due to unavailability of desired data in first the data cache, then the random access memory; means for dividing the pagemap into one dimensional array of swaths of scans, each swath containing a two dimensional array of words in column major order; each of said swaths having a height measured in scans which is a function of frame size, data cache line size and set associativity of said data cache; and print head means for printing the pagemap.
Claim 27
Dependent Claim
34 words
A printing system in accordance with claim 21 wherein each of said swaths has a height measured in scans which is an integral multiple of the number of words in a data cache line.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-08 | 2000-04-08 | 2000-10-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-08 | 2004-04-08 | 2004-10-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-08 | 2008-04-08 | 2008-10-08 | $7700.00 | Window Closed / Lapsed |