Modeling a target system by interpolating

• US 20040010501A1
• Filed: 07/12/2002
• Published: 01/15/2004
• Est. Priority Date: 07/12/2002
• Status: Active Grant

• 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
• Granted Patent: US 7,039,897 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 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.

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 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; and

inserting said point into said data structure.

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

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

monitoring a metric associated with said inquiry;

selecting 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.

16. The method according to claim 15, 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.

17. The method according to claim 15, 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.

18. The method according to claim 15, 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.

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

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

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

20. The method according to claim 19, 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.

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

22. The method according to claim 19, 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.

23. The method according to claim 19, 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.

24. The method according to claim 19, 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.

25. The method according to claim 19, 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.

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

27. The method according to claim 25, 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.

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

29. The method according to claim 25, 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.

30. The method according to claim 25, 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.

31. The method according to claim 25, 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.

32. The method according to claim 25, 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.

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

34. An apparatus for modeling a target system, said 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.

35. The apparatus according to claim 34, 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.

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

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

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

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

40. An apparatus for modeling a target system, said apparatus comprising:

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

means for 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; and

means for adding said respective point to said data structure.

41. The apparatus according to claim 40, 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.

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

means for measuring a metric;

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

43. The apparatus according to claim 40, 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.

44. The apparatus according to claim 40, 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.

45. The apparatus according to claim 40, 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.

46. The apparatus according to claim 40, 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.

47. 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 populate 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.

48. The system according to claim 47, wherein said interpolation module is configured to interpolate said return value for said target system in response to said search not finding a point in said data structure corresponding to said inquiry parameter values.

49. The system according to claim 47, 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.

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

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

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

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

54. 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.

55. The apparatus according to claim 54, 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.

57. The apparatus according to claim 54, 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.

58. The apparatus according to claim 54, 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.

59. The apparatus according to claim 54, 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.

60. The apparatus according to claim 54, 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.

61. The apparatus according to claim 54, 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.

62. The apparatus according to claim 61, 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.

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

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

65. The apparatus according to claim 61, 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.

66. The apparatus according to claim 61, 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.

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

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