Method and system for determining optimal data layout using blind justice

• US 7,805,580 B2
• Filed: 01/08/2007
• Issued: 09/28/2010
• Est. Priority Date: 01/08/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhang, Chengliang, Hirzel, Martin
• Primary Examiner(s): Song; Jasmine
• Application Number:
  US11/620,818
• Publication Number:
  US 20080168249A1
• Time in Patent Office: 1,359 Days
• Field of Search: 711/154, 711/170, 717/151, 717/158, 707/206
• US Class Current: 711/154
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

Disclosed are a method and system for finding an optimal data layout. The approach of the present invention is to try one of several data layouts in the memory, measure the impact of said one data layout on a performance of a program, and decide which of said several data layouts to try next. The trying and measuring steps are repeated, and one of said several data layouts is selected as best or optimal based on the measurings. The preferred embodiment of the invention provides layout auditing, a framework for picking the best data layout online without requiring any user input. Layout auditing optimizes data layouts with a try-measure-decide feedback loop: use a data reorganizer to try one of several data layouts, use a profiler to measure the impact of the data layout on performance, and use a controller to decide which data layout to try next.

Claims

1. A system for improving data locality in a memory, comprising:

a data reorganizer to copy data objects in different data layouts in the memory;

a profiler for evaluating the performances of the different data layouts; and

a controller to choose one of the data layouts as optimal based on said evaluating, wherein;

said profiler outputs information describing said different performances;

the controller uses said output information to choose the optimal data layout;

the profiler outputs counts of simulated data accesses, cache misses and TLB misses for each of the data layouts; and

the controller is an instrumentation-based controller, calculates costs separately for each of the different data layouts using said output costs from the profiler, and calculates probabilities for each of the data layouts from said costs.

2. A system for improving data locality in a memory accessed by a given program, comprising:

a data reorganizer to copy data objects in a plurality of different data layouts in the memory, wherein the given program accesses each of the data layouts while the given program is running;

a profiler for evaluating the performance of the program while the program is running and accessing each of the different data layouts; and

a controller to choose one of the plurality of data layouts as optimal based on said evaluating; and

, wherein;

said profiler outputs information describing said different performances;

the controller uses said output information to choose the optimal data layout;

the profiler outputs counts of simulated data accesses, cache misses and TLB misses for each of the data layouts;

the system further comprises a hardware performance counter that outputs total counts of simulated data accesses, cache misses and TLB misses for all of the data layouts; and

the controller is a hardware-based controller, calculates costs separately for each of the different data layouts using said output counts from the profiler and said output total counts from the hardware performance counter, and calculates probabilities for each of the data layouts from said costs.

3. A method of operating a profiler to measure the performance of different layouts in memory, comprising the steps of dividing memory into areas that can have a plurality of different data layouts, wherein a running program accesses each of the data layouts;

and measuring the locality for each memory area by using the profiler, while the program is running, for evaluating the performance of the program when accessing each of the data layouts, and wherein;

one of the plurality of data layouts is chosen as optimal based on said evaluating, wherein the measuring step includes the steps of;

collecting data reference traces;

using the collected traces to drive a cache and TLB simulation;

mapping simulated accesses and misses to the data layouts; and

keeping a count of each simulated miss mapped to each of the data layouts.

4. A method according to claim 3, wherein the using step is performed at the beginning of a garbage collection process.

5. A method according to claim 3, wherein:

the measuring step includes the further step of filtering some of the accesses, including the steps of filtering access with a reuse distance below a given value, and filtering accesses to objects that are less than a given age; and

the performances of said different data layouts are measured simultaneously.