Modeling a target system by interpolating

• US 7,039,897 B2
• Filed: 07/12/2002
• Issued: 05/02/2006
• Est. Priority Date: 07/12/2002
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Anderson, Eric, Wilkes, John
• Primary Examiner(s): DAS, CHAMELI
• Application Number:
  US10/193,163
• Publication Number:
  US 20040010501A1
• Time in Patent Office: 1,390 Days
• Field of Search: 717/104, 717/102, 717/117, 717/101, 717/106, 709/204, 719/321, 707/100, 707/200, 707/102, 707/103.Y
• US Class Current: 717/104
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

In a method of modeling a target system, a data structure is populated with points, where each point includes at least one target value associated with at least one system parameter value of the target system. The data structure is searched with at least one inquiry parameter value. A return value is interpolated for at least one inquiry parameter value based on the points.

Claims

1. A computer-implemented method of modeling a target system, said method comprising:

populating a data structure with points, each point comprising at least one target value associated with at least one system parameter value of said target system;

searching said data structure with at least one inquiry parameter value; and

interpolating a return value for said at least one inquiry parameter value based on said points in response to said searching of said data structure resulting in a failure to find a point in the data structure corresponding to the at least one inquiry parameter value.

2. The method according to claim 1, wherein said at least one target value is a performance value.

3. The method according to claim 1, wherein said at least one target value is a plurality of values.

4. The method according to claim 1, wherein said interpolating of said return value uses a closest neighbor algorithm.

5. The method according to claim 1, wherein said interpolating of said return value uses a Bezier sheet interpolation algorithm.

6. The method according to claim 1, wherein said interpolating of said return value uses a hyper-plane interpolation algorithm.

7. The method according to claim 1 wherein said searching of said data structure uses one of a table look-up, a linear scan, and a tree-index.

8. The method according to claim 1, wherein said target system is a storage system and said points are measurements of said storage system.

9. The method according to claim 8, wherein said storage system is a disk array.

10. The method according to claim 1, wherein said target system is a computer system and said points are measurements of said computer system.

11. The method according to claim 1, wherein said target system is a network and said points are measurements of said network.

12. The method according to claim 1, wherein said target system is a simulated system and said points are predictions of said target system.

13. The method according to claim 1, wherein said data structure is one of an array, a table, a linked-list, and a hash table.

14. A computer implemented method of adding points, said method comprising:

instantiating a data structure with zero or more initial points;

selecting at least one target inquiry value;

determining a point for said at least one target inquiry value;

inserting said point into said data structure;

returning a value in response to an inquiry into said data structure using at least one inquiry value;

monitoring an metric associated with said inquiry;

interpolating an additional target inquiry value in response to said metric not meeting a user-specified criterion;

determining a respective point for said additional target inquiry value; and

adding said respective point for said additional target inquiry value to said data structure.

15. The method according to claim 14, wherein said user-specified criterion comprises a density of points in the said data structure near the point that would be associated with said at least one inquiry value.

16. The method according to claim 14, wherein said selecting of said additional target inquiry value includes selecting a respective point in a region of low density of points stored in said data structure.

17. The method according to claim 14, wherein said user-specific criterion comprises a density of points stored in said data structure in regions where at least one target value is changing rapidly.

18. The method according to claim 14, further comprising:

selecting an additional target inquiry value to determine a point by applying a rule; and

populating said data structure with a respective point of said additional target inquiry value.

19. The method according to claim 18, further comprising:

repeating said step of selecting subsequent additional target inquiry value to determine by said rule until a predetermined number of said subsequent additional target inquiry values is reached; and

adding said respective point for each subsequent additional target inquiry value to said data structure.

20. The method according to claim 18, wherein said rule comprises selecting said additional target inquiry value randomly within a hypercube formed of said system parameter values of said initial points.

21. The method according to claim 18, wherein said rule comprises selecting said additional target inquiry value randomly until the point associated with said additional target inquiry value is not-near existing points.

22. The method according to claim 18, wherein said rule comprises selecting said additional target inquiry value by choosing a set of points that represent multiple target inquiry values, and selecting the point within said set that is farthest away from existing points.

23. The method according to claim 18, wherein said rule comprises selecting said additional target inquiry value that has an associated point close to an existing point having a high mis-prediction error.

24. The method according to claim 18 further comprising:

measuring a metric using one of a predetermined parameter and a user-specified parameter for said additional target inquiry value;

comparing said metric with a user-specified metric of quality; and

repeating said step of selecting subsequent additional target inquiry value to determine by said rule until said metric satisfies said user-specified metric of quality.

25. The method according to claim 24, wherein said repeating ceases after a user-specified number of points have been determined.

26. The method according to claim 24, wherein said metric is a number of additional target inquiry values wherein a mis-prediction error is less than a user-specified error-bound parameter, and the user-specified metric of quality is a minimum number.

27. The method according to claim 26, wherein said mis-prediction error is one of relative and absolute.

28. The method according to claim 24, wherein said metric is a number of consecutive additional system parameter values wherein a mis-prediction error is less than a user-specified error-bound parameter, and the user-specified metric of quality is a minimum number.

29. The method according to claim 24, wherein said metric is an exponentially moving average and said user-specified parameter is a factor for the exponentially moving average and the quality metric is a maximum exponentially moving average.

30. The method according to claim 24, wherein said metric is an average of a relative difference between each point and a next nearest point being less than a predetermined threshold and the quality metric is a maximum average difference.

31. The method according to claim 24, wherein said metric is an average of absolute differences between each point and a next nearest point being less than a predetermined threshold and the user-specified metric of quality is a maximum average difference.

32. The method according to claim 24, wherein said metric is elapsed time and said user-specified metric of quality is a timebound.

33. A computer apparatus for modeling a target system, said computer apparatus comprising:

means for populating a data structure with points, each point comprising at least one system parameter value and at least one target value;

means for searching said data structure with at least one inquiry parameter value; and

means for interpolating a return value for said at least one inquiry parameter value based on said points, wherein the means for interpolating is configured to interpolate the return value in response to a determination by the means for searching that a point in the data structure corresponding to the at least one inquiry parameter value has not been found.

34. The apparatus according to claim 33, wherein said means for interpolating said return value uses one of a closest neighbor algorithm, a nearest neighbor averaging algorithm, a Bezier sheet interpolation algorithm, and a hyper-plane interpolation algorithm.

35. The apparatus according to claim 33, Wherein said target system is one of a storage system, a computer system, a network, a web service, and a radar system.

36. The apparatus according to claim 35, wherein said points are measured on one of said storage system, said computer system, said network, said web service, and said radar system.

37. The apparatus according to claim 35, wherein said storage system is one of a disk drive, a tape drive, and a disk array.

38. The apparatus according to claim 33, wherein said data structure is one of a table, a linked-list, and a hash table.

39. A computer apparatus for modeling a target system, said computer apparatus comprising:

means for instantiating a data structure with points associated with said target system;

means far selecting one or more target inquiry values based on a rule;

means for determining a respective point using said one or more system parameter values;

means for adding said respective point to said data structure;

means for returning a value in response to an inquiry into said data structure using at least one inquiry value;

means for monitoring a metric associated with said inquiry;

means for interpolating an additional target inquiry value, wherein the means for interpolating is configured to interpolate the additional target inquiry value in response to said metric not meeting a user-specified criterion; and

means for determining a respective point for said additional target inquiry value, and wherein the means for adding is configured to add the respective point for said additional target inquiry value to said data structure.

40. The apparatus according to claim 39, wherein said means for selecting one or more target inquiry values based on said rule further comprises means for stopping said selecting one or more inquiry values when a stopping condition is reached.

41. The apparatus according to claim 40, further comprising:

means for measuring a metric;

means for comparing said metric with a user-specified metric of quality as a stopping condition.

42. The apparatus according to claim 39, wherein said means for selecting one or more target inquiry values based on a rule further comprises means for selecting said one or more target inquiry values randomly within a hypercube formed by ranges of said system parameter values.

43. The apparatus according to claim 39, further comprising:

means for selecting said one or more target inquiry values randomly until said one or more target inquiry values is not-near existing points.

44. The apparatus according to claim 39, further comprising:

means for selecting two or more sets of said system parameter values and means for selecting a set of said system parameter values from said two or more sets of said system parameter values that is farther way from existing points.

45. The apparatus according to claim 39, further comprising:

means for selecting two or more sets of said target inquiry values and means for selecting a set of said target inquiry values from said two or more sets of said target inquiry values that is closest to a point having a highest mis-prediction error.

46. A system for modeling characteristics of a target system, said system comprising:

a memory;

at least one processor;

an interpolation module configured to be stored in said memory and executed by said at least one processor; and

a data structure configured to be stored in said memory and searched by inquiry parameter values related to said target system, wherein said interpolation module is configured to populace said data structure with points, each point comprising of at least one system parameter value and at least one target value and said interpolation module is also configured to search said data structure with said inquiry parameter values, and to interpolate a return value based on said points in response said search of said data structure resulting in a failure to find a point in the data structure corresponding to the at least one inquiry parameter value.

47. The system according to claim 46, wherein said interpolation module uses one of a closest neighbor algorithm, a nearest neighbor averaging algorithm, a Bezier sheet interpolation algorithm, and a hyper-plane interpolation algorithm to estimate said return value.

48. The system according to claim 46, wherein said target system is one of a storage system, a computer system, a network, a web service, and a radar system.

49. The system according to claim 48, wherein said points are measurements on one of said storage system, said computer system, said network, said web service, and said radar system.

50. The system according to claim 48, wherein said storage system is one of a disk drive, a tape drive, end a disk array.

51. The system according to claim 46, wherein said data structure is one of a table, a linked-list and a hash table.

52. An apparatus for populating a data structure adapted to model a target system, said apparatus comprising:

a memory;

at least one processor;

an interpolation module configured to be stored in said memory and executed by said at least one processor, wherein said interpolation module is configured to instantiate a data structure; and

a populator module configured to add points associated with said target system to said data structure, each point comprising at least one system parameter value and at least one associated target value, wherein said populator module is configured to select at Least one target inquiry value to determine a point based on said at least one target inquiry value set, and to add said point to said data structure, and wherein the populator module is further configured to add a respective point corresponding to an additional target inquiry value that is not found in the data structure, wherein the additional target inquiry comprises a value interpolated by the interpolation module based upon a metric.

53. The apparatus according to claim 52, wherein said populator module is configured to apply a rule, to select an additional target inquiry value based on said rule, to determine a respective point for said additional target inquiry value, and to add said respective point to said data Structure.

54. The apparatus according to claim 52, wherein said populator module is configured to select said at least one target inquiry value randomly within a hypercube formed of a range of said system parameter values.

55. The apparatus according to claim 52, wherein said populator module is configured to select said at least one target inquiry value randomly until said at least one target inquiry value is not-near existing points.

56. The apparatus according to claim 52, wherein said populator module is configured to select said target inquiry value by choosing at least two target inquiry value sets and selecting one that is farthest away from existing points.

57. The apparatus according to claim 52, wherein said populator module is configured to select said target inquiry value by choosing at least two target inquiry value sets and selecting one that is closest to an existing point having a highest mis-prediction error.

58. The apparatus according to claim 52, wherein said populator module is configured to measure a metric using at least one of a predetermined parameter and a user-specified parameter, to compare said metric with a user-specified metric of quality, and to cease selection of said additional target inquiry values in response to said metric satisfying said user-specified metric of quality.

59. The apparatus according to claim 58, wherein said metric is a number of points wherein the mis-prediction error is less than a user-specified error parameter and the user-specified metric of quality is a minimum number.

60. The apparatus according to claim 59, wherein said metric resets to zero when to the mis-prediction error exceeds the user-specified parameter.

61. The apparatus according to claim 59, wherein said mis-prediction error is either relative or absolute.

62. The apparatus according to claim 58, wherein said metric is an exponentially moving average, the optional user-specified parameter is a factor for the exponentially moving average and the quality metric is a maximum exponentially moving average.

63. The apparatus according to claim 58, wherein said metric is a mean relative difference between a target value of each point and a target value of a next nearest point-and the quality metric is a maximum average error.

64. The apparatus according to claim 58, wherein said metric is a mean absolute difference between a target value of each point and a target value of a next nearest point.

65. The apparatus according to claim 58, wherein said metric is elapsed time and said user-specified metric of quality is time-bound.