Assignment of files to storage device using macro and micro programming model which optimized performance of input/output subsystem

• US 5,014,197 A
• Filed: 09/02/1988
• Issued: 05/07/1991
• Est. Priority Date: 09/02/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wolf, Joel L.
• Primary Examiner(s): Eng, David Y.
• Assistant Examiner(s): Lim, Krisna
• Application Number:
  US07/240,029
• Time in Patent Office: 977 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 710/38
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

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.

Claims

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

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

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

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

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

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