Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1998-06-30
2001-04-03
Powell, Mark R. (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S520000
Reexamination Certificate
active
06211889
ABSTRACT:
BACKGROUND
This application relates to computers and computer systems and further relates to a method and apparatus for visually displaying various aspects of memory.
As computer systems become more complex, it is becoming more difficult for human beings to easily understand and grasp all the intricacies involved in any given computer system.
During execution, a computer system may move units of memory, such as pages or cache lines, between units of hardware. As more complex caching systems are designed and as caching systems begin to have more and more levels, it is becoming more and more difficult for human beings to understand whether a given caching system is operating efficiently for the software executing on the computer system.
Software currently exists to aid a human being in visualizing certain aspects of a computer's memory, such as the performance impact of caching. These conventional software programs, however, display memory using a line-by-line display on a display device. For example, in such a line-by-line display, a pixel representing information about a first unit of memory is displayed on a first line in a first column of a display screen. A pixel representing information about a second unit of memory is displayed on a first line in a second column of the display screen. A pixel representing information about a last unit of memory may be displayed on a last line in a last column of a display screen, and so on. Pixels representing information about intermediate units of memory are displayed, one after the other, on consecutive rows and in consecutive columns within each row (or vice versa in consecutive columns and rows).
The term “locality of memory” refers to the location of data (e.g., variables) within memory in time and space. Accessing a variable closely in time is called “temporal locality.” Accessing variables stored physically close together is called “spatial locality.” Physical locations in a memory that are close together have a high spatial locality. For example, a variable that is read from close together in time has a high temporal locality. For example, a 49
th
memory unit and a 50
th
memory unit (such as bits, bytes, words, pages, etc.) that are physically close to each other in a computer memory have a high spatial locality. As another example, if a variable is read twice in quick succession, the variable has a high temporal locality. On modern computer systems, temporal and spatial locality impact performance.
Unfortunately, in conventional line-by-line visualization software, even though a 49
th
memory unit is physically contiguous to a 50
th
memory unit in the actual memory of the computer, it is entirely possible that the display pixels corresponding to the memory units will be on opposite sides of the display screen. For example, the pixel corresponding to the 49
th
memory unit might be the last column in row n, while the pixel corresponding to the 50
th
memory unit might be displayed in the first column of row n+1. Because conventional visualization tools do not necessarily show memory units having a high locality as being physically near each other on the display, conventional visualization tools are not ideal for aiding a human being in visualizing how various memory units relate to each other or for visualizing locality.
Another example of conventional visualization software displays memory accesses by address on one axis of a graph and time on the other axis. This method also fails to present data in a way that effectively aids human understanding of the relationships between the data.
SUMMARY OF THE INVENTION
The described embodiments of the present invention provide a method and apparatus that display certain aspects of a computer memory on a display screen in accordance with a fractal curve instead of a line-by-line display. In at least one embodiment, the fractal curve is a Hilbert curve. The fractal curve display can be used as an aid in visualizing various types of information about a computer memory. Certain embodiments have a display that remains static, while other embodiments have a display that is dynamic and changes in real-time to reflect changes in memory.
For example, the display can be used as an aid to visualize memory access patterns, such as when and/or where read or write operations occur in a computer memory. As a second example, the display can be used as an aid to visualize which pages are currently being swapped in or out of various levels of memory in a virtual memory system. As a third example, the display can be used as an aid to visualize which cache lines are active in a caching system. As a fourth example, the display can be used as an aid to visualize which pages are being swapped into memory. As a fifth example, the display can be used as an aid to visualize the read/write permissions of various pages of memory. As a sixth example, the display can be used as an aid to visualize the shared/modified exclusive states of cache lines.
Use of a Hilbert curve as an aid in visualizing memory has the advantage that it allows memory groups equal to powers of two to be displayed near each other. For example, display bits of the fractal curve corresponding to memory addresses 00xxxxxx, where xx is any value, are grouped in a same quadrant of the memory display. Similarly, display bits of the fractal curve corresponding to memory address 0000xxxx are grouped within a sub-quadrant of the quadrant holding display bits for the addresses 00xxxxxx. Display bits of the fractal curve corresponding to memory address 000000xx are grouped within a sub-sub-quadrant of the quadrant holding display bits for the addresses 0000xxxx, and so on.
Certain embodiments use color on the display to indicate types of memory access, while other use display color to indicate a type of memory being represented in the display. In addition, certain embodiments of the present invention also use a 3-D version of a fractal curve, either drawn in 2D or rendered in 3D to aid in visualization of various aspects of memory. In accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of displaying information, performed by a data processing system, comprising the steps of: receiving notification of a memory event, including a memory location; determining a portion of a fractal curve that corresponds to the memory location at which the memory event has occurred; and highlighting a portion of a display screen in accordance with the determined portion of the fractal curve.
A fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4843468 (1989-06-01), Drewery
patent: 5602943 (1997-02-01), Velho et al.
patent: 5852443 (1998-12-01), Kenworthy
Web Page entitled, “PatchWrx—A Dynamic Execution Tracing Tool”, Oct. 1995, By: Richard L. Sites and Sharon E. Perl, Digital Equipment Corp, Systems Research Center, Palo Alto, CA, pp. 1-17, Additional Pages: Figures 7 & 8, Figures 9 & 9a, Figures 10 & 11, URL=http://www.research.digital.com/SRC/personal/DickSites/patchwrx/PatchWrx.html.
Article: “Studies of Windows NT Performance Using Dynamic Execution Traces”, Usenix 2d Symposium on OS Design and Implementation (OSDI '96), Oct. 28-31, 1996, Seattle, Washington, Co-Sponsored by ACM SIGOPS and IEEE TCOS, By: Richard L. Sites and Sharon E. Perl, Digital Systems Research Center, Palo Alto, CA, pp. 1-15, Additional Pages: Frame 211, Frame 295.
Web Page entitled, “Notes on A Cube-filling Hilbert Curve”, By: William J. Gilbert, Printed: Jun. 30, 1998, p. 1 of 1, URL=http://math.uwaterloo.ca/~wgilbert/Research/HilbertCurve/HilbertCurveNotes.html.
Web Page entitled, “An Introduction to Chaos Theory and Fractals”, Printed: Mar. 6, 1998, pp. 1-13, URL=http://www.geocities.com/CapeCanaveral/9753/AmChaosIntro.html.
Web Page entitled, “Fractal Frequently Asked Questions and Answers,” Printed: Mar. 6, 1998, Last Updated: Feb. 5,
Beyer Weaver & Thomas LLP
Cunningham G. F.
Powell Mark R.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for visualizing locality within an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for visualizing locality within an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for visualizing locality within an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2552021