Browse Prior Art Database

A Data Restructuring Methodology for Reducing Allocated Cache Lines

IP.com Disclosure Number: IPCOM000012685D
Original Publication Date: 2003-May-20
Included in the Prior Art Database: 2003-May-20
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Abstract

Presented is a methodology for reducing the number of cache lines, used by the fields composing a structure, that are accessed during application execution. This would in turn reduce the number of cache lines, and therefore the amount of data, transferred between processors when a process migrates. It also improves cache efficiency within the processor, which results in the performance improvement.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

A Data Restructuring Methodology for Reducing Allocated Cache Lines

Presented is a methodology for reducing the number of cache lines, used by the fields composing a structure, that are accessed during application execution. This would in turn reduce the number of cache lines, and therefore the amount of data, transferred between processors when a process migrates. It also improves cache efficiency within the processor, which results in the performance improvement.

This methodology takes as input, data structure field access information collected by using a tool to profile this access information. (The tool used is orthogonal to this proposal and is not discussed further). The access information contains the address of the data structure, the name of the data structure field, the field offset within the structure, the size of the field, and the routine accessing the structure. The input information is then used to determine the number of cache lines used by the executing application when accessing the data structure. This methodology also includes the rearrangement of fields within a data structure.

Franke, et. al. [1], invented a process that monitors the cache footprint of threads on a processor and associated cache, facilitating a cache sensitive threading methodology or thread affinity. Bryant and Hartner [2] describe a process where the fields within a specific data structure are reorganized to be adjacent to each other for better performance. Sears [3] describes a process for aligning fields in data structures. The presented proposal differs in that focus is on packing fields within a cacheline. However, the methodology presented in [2] , [3] can be used in conjunction with this proposal for better performance. For example, if a field within a structure is aligned according to a cache line, and there is still additional space in the cache line for another candidate field in the structure, then the candidate field can be added to the cache line.

Described are two alternative methods for this proposal; one which takes advantage of information regarding the application routine that accesses the fields in the structure, and another which does not. Each method is described below.

1) Cache Line Reduction using Application Routines: The trace data collected from the access profile tool is grouped according to the execution paths - send, receive, and send and receive routines of a networking application for example. For each of these paths, the elements accessed during the execution are grouped on a per structure basis. Each execution path may access elements in one or more structures. For each of those structures, the cacheline access patterns are tabulated giving the number of cachelines that are accessed by the send path and the receive path. Cachelines that are common to both paths can be easily determined from the tabulation. Any element of a structure that is accessed and is on a cacheline by itself is a prime candidate for re...