Storage Utilization in a Memory Hierarchy When Storage Assignment Is Performed by a Hashing Algorithm.

Saved in:

Bibliographic Details
Title:	Storage Utilization in a Memory Hierarchy When Storage Assignment Is Performed by a Hashing Algorithm.
Authors:	Williams, John G.¹, Ashenhurst, R. L.
Source:	Communications of the ACM. Mar1971, Vol. 14 Issue 3, p172-175. 4p. 1 Diagram, 3 Graphs.
Subjects:	Memory hierarchy (Computer science), Hashing, Algorithms, Computer storage devices, Electronic file management, Computer storage device industry
Abstract:	The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store. [ABSTRACT FROM AUTHOR]
	Copyright of Communications of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store. [ABSTRACT FROM AUTHOR]
ISSN:	00010782
DOI:	10.1145/362566.362570