Temporal Affinity Analysis Optimization for Software Performance

Brief Description:
This concept applies to the optimization of hardware and the effectiveness of cache allocation for given applications and software. The goal is not cache analysis, but program analysis.  It provides a general method for improving software performance by providing a hierarchical partition of program data.

The most straightforward way of implementing the technology is in a compiler, such that the advantage is applied to all software run on the system. Since the compiler is fundamental to the computer system performance, this improvement flows directly to the overall performance of the computer system, and can be applied immediately to compilers used for the major operating systems, such as Unix and Windows. Alternatively the technology could be used in individual software packages to improve the performance of their compiled run code.  It is expected that the method can be applied to improving Internet search engines, such as Google. It could be used in a system integration tool for applications involving a high level of data memory, in, for example, an embedded processor in a machine vision robot or a highly featured cell phone. An alternative application for the "reuse distance" may be in pattern recognition.  The algorithms are not limited to a defined data set, but can be used in an open-ended flow of data. 

The technology provides a general method for improving software performance by providing a hierarchical partition of program data, based on algorithms for “reference affinity”. This affinity analysis improves cache utilization, and has been shown to improve systems performance in benchmark testing in the scale of 6 to 12%. Earlier methods of optimizing data structures include (1) access frequency, (2) compiler analysis, and (3) statistical clustering. Our method is better than the one using access frequency because it measures distance between data blocks by volume, not time, and accounts for the possible “togetherness” of data.  Earlier methods of compiler analysis, which depend on identifying regular loops and array access patterns, are not useful for complex control flow and indirect data access, but our method does apply for these complex programs. Statistical clustering, which has been used in attempts to optimize data blocks, draws upon unwieldy statistical tools, while our approach is much easier to implement.

URV Reference Number: 1-11114-03016
Patent Information:
Title Country Patent No. Issued Date
Temporal Affinity Analysis Using Reuse Signatures United States 7,356,805 4/8/2008
Computer Software
For Information, Contact:
Curtis Broadbent
Licensing Manager
University of Rochester
Chen Ding
Yutao Zhong