# US 8,572,315 B2 · Smart optimization of tracks for cloud computing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,572,315 B2
- Document ID: US8572315B2
- Status: Granted
- Kind: B2
- Application number: 12/941,016
- Filed: 2010-11-05
- Published: 2012-05-10
- Granted: 2013-10-29
- Earliest claimed: 2010-11-05
- Assignees: International Business Machines Corporation
- Applicants: Bhooshan P. Kelkar; Abhinay R. Nagpal; Sandeep R. Patil
- Inventors: Bhooshan P. Kelkar; Abhinay R. Nagpal; Sandeep R. Patil
- Web page: https://patentgrep.com/patent/US8572315B2

## CPC

- G06F 3/061: {Improving I/O performance}
- G06F 3/0614: {Improving the reliability of storage systems}
- G06F 3/0625: {Power saving in storage systems}
- G06F 3/064: {Management of blocks}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G11B 20/1217: {on discs}
- G11B 27/36: Monitoring, i.e. supervising the progress of recording or reproducing {(for digital recording G11B20/00 and s.gr.; for monitoring, testing or measuring of TV recorders of the type covered by H04N5/76 and subgroups, see H04N17/06)}
- G11B 2220/2516: Hard disks
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Optimization of tracks on a hard disk includes: determining I/O characteristics for data clusters to be stored on the hard disk; generating a set of solutions for each possible placement configuration; for each solution, calculating a plurality of cost functions using the I/O characteristics for the plurality of data clusters; for each solution, calculating a membership value using the cost function values; for each solution, calculating a fitness value using the membership value; retaining the solutions with the fitness value greater than a predetermined threshold; determining whether at least one stopping condition has been met; if not, adding new solutions to the retained solutions to generate the next set of solutions; and repeating the calculating the membership value, the calculating the fitness value, and the retaining the solutions with the fitness value greater than the predetermined threshold until at least one stopping condition has been met.

## Claims

### Claim 1

A method for optimization of tracks on a hard disk, comprising:
determining, by a processor, I/O characteristics for a plurality of data clusters to be stored on the hard disk;
determining, by the processor, a plurality of costs of operation of the hard disk for a plurality of possible placement configurations of the plurality of data clusters, wherein the determining uses the I/O characteristics for the plurality of data clusters; and
determining, by the processor, an optimal placement map for the plurality of data clusters from the plurality of costs of operation,
wherein the determining the plurality of costs of the operation of the hard disk for the plurality of possible placement configurations of the plurality of data clusters comprises:
generating a set of solutions for a possible placement configuration, and
for each solution, calculating a cost function value for a plurality of cost functions,
wherein the determining the optimum placement map for the plurality of data clusters from the plurality of costs of operation comprises:
for each solution, calculating a membership value using the cost function values, wherein the membership value represents how good the solution is as part of the optimal placement map;
for each solution, calculating a fitness value using the membership value, wherein the fitness value serves as an indication of how fit the solution is as part of the optimal placement map;
retaining the solutions with the fitness value greater than a predetermined threshold;
determining whether at least one stopping condition has been met;
in response to determining that none of the stopping conditions have been met, adding new solutions to the retained solutions to generate the next set of solutions; and
repeating the calculating of the membership value using the cost function values, the calculating of the fitness value using the membership value, and the retaining of the solutions with the fitness value greater than the predetermined threshold until at least one stopping condition has been met.

### Claim 2 (depends on 1)

The method of claim 1, wherein for each solution, the calculating the membership value using the cost function values comprises:
for each cost function, calculating a base cost for the cost function as a current iteration cost divided by an optimum cost for the cost function;
for each cost function, comparing the base cost with the optimum cost and a worst cost for the cost function; and
for each cost function, setting the membership value for the cost function in response to the comparing of the base cost with the optimum cost and the worst cost for the cost function.

### Claim 3 (depends on 2)

The method of claim 2, wherein the setting the membership value for the cost function in response to the comparing of the base cost with the optimum cost and the worst cost for the cost function comprises:
in response determining that the base cost is better than or equal to the optimum cost, setting the membership value to 1.0;
in response to determining that the base cost is worse than the worst cost, setting the membership value to 0.0; and
in response to determining that the base cost is between the optimum cost and the worst cost, setting the membership value=(base cost−worst cost)/(1−worst cost).

### Claim 4 (depends on 2)

The method of claim 2, wherein for each solution, the calculating the fitness value using the membership value comprises:
selecting a lowest membership value among the membership values of the cost functions; and
calculating the fitness value=(β*(lowest membership value)+(1+β)*(sum of the membership values)/(count of the membership values).

### Claim 5

A method for optimization of tracks on a hard disk, comprising:
determining, by a processor, I/O characteristics for a plurality of data clusters to be stored on the hard disk;
determining, by the processor, a plurality of costs of operation of the hard disk for a plurality of possible placement configurations of the plurality of data clusters, wherein the determining uses the I/O characteristics for the plurality of data clusters; and
determining, by the processor, an optimal placement map for the plurality of data clusters from the plurality of costs of operation, wherein the determining the plurality of costs of operation of the hard disk for the plurality of possible placement configurations of the plurality of data clusters comprises:
determining an objective function with a plurality of cost function values as variables;
determining one or more constraints in terms of the variables;
graphing the constraints; and
shading a feasibility region on the graph.

### Claim 6 (depends on 5)

The method of claim 5, wherein the determining the optimum placement map for the plurality of data clusters from the plurality of costs of operation comprises:
finding corner points of the feasibility region;
determining the corner point that gives minimum values for the variables; and
setting the placement configuration associated with the cost function values with the minimum values as the optimal placement map.

### Claim 7

A computer program product for optimization of tracks on a hard disk, the computer program product comprising:
a computer readable storage device having computer readable program code embodied therewith, the computer readable program code configured to:
determine I/O characteristics for a plurality of data clusters to be stored on the hard disk;
determine a plurality of costs of operation of the hard disk for a plurality of possible placement configurations of the plurality of data clusters, wherein the determining uses the I/O characteristics for the plurality of data clusters; and
determine an optimal placement map for the plurality of data clusters from the plurality of costs of operation,
wherein the computer readable program code configured to determine the plurality of costs of the operation of the hard disk for the plurality of possible placement configurations of the plurality of data clusters is further configured to:
generate a set of solutions for a possible placement configuration; and
for each solution, calculate a cost function value for a plurality of cost functions,
wherein the computer readable program code configured to determine the optimal placement map for the plurality of data clusters from the plurality of costs of operation is further configured to:
for each solution, calculate a membership value using the cost function values, wherein the membership value represents how good the solution is as part of the optimal placement map;
for each solution, calculate a fitness value using the membership value, wherein the fitness value serves as an indication of how fit the solution is as part of the optimal placement map;
retain the solutions with the fitness value greater than a predetermined threshold;
determine whether at least one stopping condition has been met;
in response to determining that none of the stopping conditions have been met, add new solutions to the retained solutions to generate the next set of solutions; and
repeat the calculating of the membership value using the cost function values, the calculating of the fitness value using the membership value, and the retaining of the solutions with the fitness value greater than the predetermined threshold until at least one stopping condition has been met.

### Claim 8 (depends on 7)

The computer program product of claim 7, wherein the computer readable program code configured to calculate the membership value using the cost function values is further configured to:
for each cost function, calculate a base cost for the cost function as a current iteration cost divided by an optimum cost for the cost function;
for each cost function, compare the base cost with the optimum cost and a worst cost for the cost function; and
for each cost function, set the membership value for the cost function in response to the comparing of the base cost with the optimum cost and the worst cost for the cost function.

### Claim 9 (depends on 8)

The computer program product of claim 8, wherein the computer readable program code configured to set the membership value for the cost function in response to the comparing of the base cost with the optimum cost and the worst cost for the cost function is further configured to:
in response determining that the base cost is better than or equal to the optimum cost, set the membership value to 1.0;
in response to determining that the base cost is worse than the worst cost, set the membership value to 0.0; and
in response to determining that the base cost is between the optimum cost and the worst cost, set the membership value=(base cost−worst cost)/(1−worst cost).

### Claim 10 (depends on 8)

The computer program product of claim 8, wherein the computer readable program code configured to calculate the fitness value using the membership value is further configured to:
select a lowest membership value among the membership values of the cost functions; and
calculate the fitness value=(β*(lowest membership value)+(1+β)*(sum of the membership values)/(count of the membership values).

### Claim 11

A computer program product for optimization of tracks on a hard disk, the computer program product comprising:
a computer readable storage device having computer readable program code embodied therewith, the computer readable program code configured to:
determine I/O characteristics for a plurality of data clusters to be stored on the hard disk;
determine a plurality of costs of operation of the hard disk for a plurality of possible placement configurations of the plurality of data clusters, wherein the determining uses the I/O characteristics for the plurality of data clusters; and
determine an optimal placement map for the plurality of data clusters from the plurality of costs of operation,
wherein the computer readable program code configured to determine the plurality of costs of operation of the hard disk for the plurality of possible placement configurations of the plurality of data clusters is further configured to:
determine an objective function with a plurality of cost function values as variables;
determine one or more constraints in terms of the variables;
graph the constraints; and
shade a feasibility region on the graph.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the computer readable program code configured to determine the optimum placement map for the plurality of data clusters from the plurality of costs of operation is further configured to:
find corner points of the feasibility region;
determine the corner point that gives minimum values for the variables; and
set the placement configuration associated with the cost function values with the minimum values as the optimal placement map.

### Claim 13

A system, comprising:
at least one hard disk comprising a plurality of tracks;
a processor; and
a computer readable storage medium operationally coupled to the processor, the computer readable storage medium having computer readable program code embodied therewith to be executed by the processor, the computer readable program code configured to:
determine I/O characteristics for a plurality of data clusters to be stored on the hard disk;
determine a plurality of costs of operation of the hard disk for a plurality of possible placement configurations of the plurality of data clusters, wherein the determining uses the I/O characteristics for the plurality of data clusters; and
determine an optimal placement map for the plurality of data clusters from the plurality of costs of operation,
wherein the computer readable program code configured to determine the plurality of costs of the operation of the hard disk for the plurality of possible placement configurations of the plurality of data clusters is further configured to:
generate a set of solutions for a possible placement configuration; and
for each solution, calculate a cost function value for a plurality of cost functions,
wherein the computer readable program code configured to determine the optimal placement map for the plurality of data clusters from the plurality of costs of operation is further configured to:
for each solution, calculate a membership value using the cost function values, wherein the membership value represents how good the solution is as part of the optimal placement map;
for each solution, calculate a fitness value using the membership value, wherein the fitness value serves as an indication of how fit the solution is as part of the optimal placement map;
retain the solutions with the fitness value greater than a predetermined threshold;
determine whether at least one stopping condition has been met;
in response to determining that none of the stopping conditions have been met, add new solutions to the retained solutions to generate the next set of solutions; and
repeat the calculating of the membership value using the cost function values, the calculating of the fitness value using the membership value, and the retaining of the solutions with the fitness value greater than the predetermined threshold until at least one stopping condition has been met.

### Claim 14 (depends on 13)

The system of claim 13, wherein the computer readable program code configured to calculate the membership value using the cost function values is further configured to:
for each cost function, calculate a base cost for the cost function as a current iteration cost divided by an optimum cost for the cost function;
for each cost function, compare the base cost with the optimum cost and a worst cost for the cost function; and
for each cost function, set the membership value for the cost function in response to the comparing of the base cost with the optimum cost and the worst cost for the cost function.

### Claim 15 (depends on 14)

The system of claim 14, wherein the computer readable program code configured to set the membership value for the cost function in response to the comparing of the base cost with the optimum cost and the worst cost for the cost function is further configured to:
in response determining that the base cost is better than or equal to the optimum cost, set the membership value to 1.0;
in response to determining that the base cost is worse than the worst cost, set the membership value to 0.0; and
in response to determining that the base cost is between the optimum cost and the worst cost, set the membership value=(base cost−worst cost)/(1−worst cost).

### Claim 16 (depends on 14)

The system of claim 14, wherein the computer readable program code configured to calculate the fitness value using the membership value is further configured to:
select a lowest membership value among the membership values of the cost functions; and
calculate the fitness value=(β*(lowest membership value)+(1+β)*(sum of the membership values)/(count of the membership values).

### Claim 17

A system, comprising:
at least one hard disk comprising a plurality of tracks;
a processor; and
a computer readable storage medium operationally coupled to the processor, the computer readable storage medium having computer readable program code embodied therewith to be executed by the processor, the computer readable program code configured to:
determine I/O characteristics for a plurality of data clusters to be stored on the hard disk;
determine a plurality of costs of operation of the hard disk for a plurality of possible placement configurations of the plurality of data clusters, wherein the determining uses the I/O characteristics for the plurality of data clusters; and
determine an optimal placement map for the plurality of data clusters from the plurality of costs of operation,
wherein the computer readable program code configured to determine the plurality of costs of operation of the hard disk for the plurality of possible placement configurations of the plurality of data clusters is further configured to:
determine an objective function with a plurality of cost function values as variables;
determine one or more constraints in terms of the variables;
graph the constraints; and
shade a feasibility region on the graph.

### Claim 18 (depends on 17)

The system of claim 17, wherein the computer readable program code configured to determine the optimum placement map for the plurality of data clusters from the plurality of costs of operation is further configured to:
find corner points of the feasibility region;
determine the corner point that gives minimum values for the variables; and
set the placement configuration associated with the cost function values with the minimum values as the optimal placement map.