Browse Prior Art Database

Algorithm to Match a Storage Hierarchy to a Cache Memory of Given Access Time and of Yet Undetermined Capacity

IP.com Disclosure Number: IPCOM000084354D
Original Publication Date: 1975-Oct-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 4 page(s) / 43K

Publishing Venue

IBM

Related People

Chow, CK: AUTHOR

Abstract

The general trend in the development of large computer systems is toward increasing use of storage hierarchies. A storage hierarchy is an integrated system of two or more storage systems, usually of dissimilar technology and of widely different capacities, access times and per unit costs. The primary purpose of the hierarchical storage systems is to enhance performance at an effective cost.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 4

Algorithm to Match a Storage Hierarchy to a Cache Memory of Given Access Time and of Yet Undetermined Capacity

The general trend in the development of large computer systems is toward increasing use of storage hierarchies. A storage hierarchy is an integrated system of two or more storage systems, usually of dissimilar technology and of widely different capacities, access times and per unit costs. The primary purpose of the hierarchical storage systems is to enhance performance at an effective cost.

The storage hierarchy under consideration consists of n levels: M(1), M(2),....,M(n) in cascade. The first level M(1) is the cache memory. In practice, the cache is usually integrated into the processor unit and is generally implemented by the same technology as the processor, and consequently operates at the same speed as the processor. The access time of the cache t(1) is thus determined by the processor and is, therefore, considered as given. However, its capacity C(1) is a design parameter, not a priori determined.

The algorithm provides a means to determine the values of the design parameters in the storage hierarchy, namely, the capacities C(2), C(3),...., C(n-1) of levels M(2), M(3)....,M(n-1) and the access times, t(2), t(3) ,....,t(n) of M(2), M(3),....,M(n). The capacity C(n) of the archive store M(n) is given as a requirement.

The objective is to so determine these values as to minimize the effective storage hierarchy access time, subject to a constraint that the total hierarchy (including the cache) does not exceed a given cost S(0), taking into account the fact that the cache access time is given and to be matched by the hierarchy. The algorithm makes use of the miss ratio characteristic exponent alpha and technology cost characteristic exponent beta, and the given number of storage levels, n, in the hierarchy.

Input Parameters.

The input design parameters are:
1. The allowable cost of the memory hierarchy, including the cache, S(0),
2. The cache access time, t(1).
3. The number of memory levels in the hierarchy, including the cache, n.
4. Nonnegative parameter alpha, which is the characteristic exponent of the miss ratio F as a power function of the capacity in the form of F=F(0)C/- alpha/. 4b. The parameter F(0) in (4).
5. Nonnegative parameter beta, which is the characteristic exponent of memory cost b per byte as a power function of the access time in the form of b=b(0)/- beta/. 5b. The parameter b(0) on (5).

Output Parameters.

The desired output parameters are the capacities and access times of the storage levels M(2), M(3),....,M(n-1) and the access time of M(n).

1

Page 2 of 4

The following algorithm determines those parameters that minimize the effective hierarchy access time of a required hierarchy capacity and total a...