Patent US5014197A successfully refreshed from Google Patents.
US5014197A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Assignment of files to storage device using macro and micro programming model which optimized performance of input/output subsystem
Assignee: International Business Machines Corp
•
Filing: 1988-09-02
•
Granted: 1991-05-07
•
Expires: 2008-09-02
Abstract
Abstract A practical mathematical algorithm is used to solve the so-called "File Assignment Problem" (FAP). The FAP is partitioned into two sequential optimization problems, called the macro model and the micro model. The macro model is solved by a Non-Linear Programming Model (NLPM) and a Queuing Network Model (QNM). The NLPM takes as input detailed information on the computer system configuration and performance characteristics down through the DASD level, and, using the QNM as its objective function evaluator, determines the "optimal" DASD relative access rates as output. The micro model is solved by a Binary Linear Programming Model (BLPM), although the QNM is also involved to help determine the BLPM stopping criteria. The input to the micro model consists basically of the output from the macro model, together with statistics on the access rates of the various files in the computer system. The output from the optimization is an "optimal" assignment of files to DASDs. The micro model algorithm can be utilized in either an unlimited file movement mode or a limited file movement mode, the former being used when the computer system undergoes a major reconfiguration while the latter is used on a once per week basis. The BLPM is solved by a "neighborhood escape" type heuristic. The procedure provides a real-world, practical solution to the FAP resulting in significant increases in performance.
Inventors
- 👤 Joel L. Wolf
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 05:46
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F16/00; G06F16/10
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
337 words
In a data processing system having one or more central processing units and a plurality of direct access storage devices, said direct access storage devices being grouped in a plurality of collections with the direct access storage devices in each collection being connected serially to a respective one of a plurality of head of strings, said head of strings each being attached to one or more storage directors of a controller, said storage directors each being attached to one or more channels which are, in turn, connected to one of said central processing units, said channels, storage directors, head of strings and direct access storage devices constituting a computer input/output subsystem a method performed by said data processing system for improving the performance of said computer input/output subsystem, said method including a macro model and a micro model and comprising steps of: inputing to a non-linear programming model configuration and performance characteristics of said data processing system down through the direct access storage device level; based on the data processing system configuration and using the non-linear programming model, determining optimal relative access rates of said direct access storage devices, said optimal relative access rates being evaluated by using a queuing network model, said inputing and determining steps comprising said macro model; using said macro model only on initial configuration or reconfiguration of said data processing system; using a binary linear programming model, measuring for each direct access storage device the distance between the optimal relative access rates as determined by said macro model and the sum of individual file access rates for data files assigned to that direct access storage device, and then summing measured distances for each direct access storage device across all direct access storage devices in the data processing system, said measuring and summing steps comprising said micro model; using said micro model on a periodic basis to maintain optimal performance of said input/output subsystems; and assigning filed to the direct access storage devices based on the results of said measuring and summing steps.
Claim 2
Dependent Claim
337 words
In a data processing system having one or more central processing units and a plurality of direct access storage devices, said direct access storage devices being grouped in a plurality of collections with the direct access storage devices in each collection being connected serially to a respective one of a plurality of head of strings, said head of strings each being attached to one or more storage directors of a controller, said storage directors each being attached to one or more channels which are, in turn, connected to one of said central processing units, said channels, storage directors, head of strings and direct access storage devices constituting a computer input/output subsystem a method performed by said data processing system for improving the performance of said computer input/output subsystem, said method including a macro model and a micro model and comprising steps of: inputing to a non-linear programming model configuration and performance characteristics of said data processing system down through the direct access storage device level; based on the data processing system configuration and using the non-linear programming model, determining optimal relative access rates of said direct access storage devices, said optimal relative access rates being evaluated by using a queuing network model, said inputing and determining steps comprising said macro model; using said macro model only on initial configuration or reconfiguration of said data processing system; using a binary linear programming model, measuring for each direct access storage device the distance between the optimal relative access rates as determined by said macro model and the sum of individual file access rates for data files assigned to that direct access storage device, and then summing measured distances for each direct access storage device across all direct access storage devices in the data processing system, said measuring and summing steps comprising said micro model; using said micro model on a periodic basis to maintain optimal performance of said input/output subsystems; and assigning filed to the direct access storage devices based on the results of said measuring and summing steps.
Claim 3
Dependent Claim
91 words
The method recited in claim 1 wherein said binary linear programming model is solved by a "neighborhood escape" type heuristic and said micro model has unlimited and limited modes, further comprising the steps of: moving files stored on said direct access storage devices without restriction when using said micro model in the unlimited mode; and moving only a limited number of files stored on said direct access storage devices when using said micro model in the limited mode, said limited number being specified by a user of the data processing system.
Claim 4
Dependent Claim
59 words
The method recited in claim 2 wherein file movement in said unlimited mode is performed by the following steps: choosing a starting assignment of files to direct access storage devices; attempting to remove burstiness and capacity infeasibilities; and if all infeasibilities have been successfully removed, testing a resulting assignment to determine if it is improved over said starting assignment.
Claim 5
Dependent Claim
132 words
The method recited in claim 3 wherein in the steps of attempting to remove burstiness and capacity infeasibilities comprises the steps of: imposing a finite nested sequence of increasing neighborhoods about points in the space of file assignments; then, given an assignment, searching a first neighborhood in its sequence for an improved assignment which, for removing the burstiness infeasibility, is an assignment that satisfies performance and availability constraints of the DASDs, for removing the capacity infeasibility, is an assignment which satisfies the performance and availability constraints and burstiness constraints while having less capacity infeasibility; and if an improved assignment cannot be found, expanding the search to a second neighborhood in the sequence, and then a next neighborhood, until an improvement is found or until the neighborhoods of the nested sequence are exhausted.
Claim 6
Dependent Claim
80 words
The method recited in claim 2 wherein file movement in said limited mode is performed by the following steps: choosing as a starting assignment of files to direct access storage devices an existing file to direct access storage device assignment; attempting to remove burstiness and capacity infeasibilities, and if all infeasibilities have been successfully removed, using said queuing network model by limiting the search to a current neighborhood; and using the number of files reassigned as a stopping point criteria.
Claim 7
Dependent Claim
93 words
The method recited in claim 5 wherein the steps of attempting to remove burstiness and capacity infeasibilities comprises the steps of: imposing a finite nested sequence of increasing neighborhoods about points in the space file assignments; and the, given an assignment, searching a first neighborhood in its sequence for an improved assignment which, for removing the burstiness infeasibility, is an assignment that satisfies performance and availability constraints of the DASDs, for removing the capacity infeasibility, is an assignment which satisfies the performance and availability constraints and burstiness constraints while having less capacity infeasibility.
References Cited (Backward Citations)
US4542458A
Cited
US4885686A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-05-06 | 1994-11-05 | 1995-05-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-05-06 | 1998-11-05 | 1999-05-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-05-06 | 2002-11-05 | 2003-05-07 | $7700.00 | Window Closed / Lapsed |