Browse Prior Art Database

Scatter Index Table Skewing

IP.com Disclosure Number: IPCOM000121080D
Original Publication Date: 1991-Jul-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 3 page(s) / 115K

Publishing Venue

IBM

Related People

Clark, BD: AUTHOR [+4]

Abstract

Directory management of cache storage in 3990 control units uses the basic premise of a Scatter Index Table (SIT) as the first point of access. Entries in this SIT are used to point to the data directory entries. Access to the SIT itself is controlled by an algorithm that hashes the device, cylinder and head values to obtain an address in the SIT. A hashing collision occurs when different combinations of device, cylinder and head values produce the same SIT address. When this happens, SIT entries must be chained together.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Scatter Index Table Skewing

      Directory management of cache storage in 3990 control
units uses the basic premise of a Scatter Index Table (SIT) as the
first point of access.  Entries in this SIT are used to point to the
data directory entries.  Access to the SIT itself is controlled by an
algorithm that hashes the device, cylinder and head values to obtain
an address in the SIT.  A hashing collision occurs when different
combinations of device, cylinder and head values produce the same SIT
address.  When this happens, SIT entries must be chained together.

      DASD users who only cache data from a small group of
sequentially addressed devices (e.g., devices 0 through 3) can
experience a greater hashing collision rate than users who cache data
from all of the devices in a string.  This is caused by the way the
SIT has been traditionally "divided" for each device.  Prior art
logically divided the SIT sequentially, starting at the beginning of
the SIT for device 0 and incrementally allocating an equal fraction
of the SIT to the rest of the devices attached.  This was done by
determining a "unit skew" value by dividing the size of the SIT by
the number of devices attached (either 32 or 64). This unit skew
value was then multiplied by the device number and the result became
the offset into the SIT for the device.  Given the number of
cylinder/head combinations for each device, the area that can be
accessed by one device is larger than the area logically assigned to
it, causing several device areas to overlap.  For the users only
caching a few sequentially addressed devices, this overlapping can
significantly increase the hashing collision rate, and thereby
increase the processing time to handle each collision.

      This current concept has addressed this problem by altering the
way the SIT is logically divided for each device.  Rather than
incrementally allocating the SIT, the new algorithm "scatters" the
devices throughout the SIT. The process starts by determining the
"unit skew" in the same manner as the programs before it.  It then
reads in a pre- established Skew Offset Table (Table 1) one control
store word at a time.  The format for each word is that the first
byte will contain a device number from 0 to 31 and the second byte
device numbers 32 through 63.  A looping algorithm given at the end
of this article then uses this table to build the Device Skew Table
(Table 2).  The fractional numbers in Table 2 represent the distance
from the start of the SIT in relationship to the size of the entire
SIT.  For example, the offset of 1/2 for device 1 means that SIT
entries for device 1 will start halfway through the SIT.  The
starting point for device 20 is 9/32nds from the beginning of the SIT
and so forth.  As can be seen from Table 2, the lower numbered
devices begin further apart in the SIT area with the gaps between
sequentially numbered devices getting smaller as the device number
increases.  It...