Browse Prior Art Database

Scatter Index Table Expansion Entry Initialization

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

Publishing Venue

IBM

Related People

Clark, BD: AUTHOR [+3]

Abstract

Current 3990 Model 3 microcode uses the concept of a Scatter Index Table (SIT) to maintain control over the data in the cache. An algorithm that uses device number and physical address (cylinder and head number) controls access into the SIT. However, this algorithm yields the same result for several different device/physical address combinations given the constraints of the SIT size. This result is known as a hashing collision. To address these collisions, record caching 3990s use an additional cache block referred to as the SIT Expansion area. This SIT Expansion area ranges in size from 16K bytes for the smallest cache to 1M bytes for the largest machine. The cache block is logically divided into 32-byte SIT Expansion entry and links it to the original SIT entry.

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

Scatter Index Table Expansion Entry Initialization

      Current 3990 Model 3 microcode uses the concept of a
Scatter Index Table (SIT) to maintain control over the data in the
cache.  An algorithm that uses device number and physical address
(cylinder and head number) controls access into the SIT.  However,
this algorithm yields the same result for several different
device/physical address combinations given the constraints of the SIT
size.  This result is known as a hashing collision.  To address these
collisions, record caching 3990s use an additional cache block
referred to as the SIT Expansion area.  This SIT Expansion area
ranges in size from 16K bytes for the smallest cache to 1M bytes for
the largest machine.  The cache block is logically divided into
32-byte SIT Expansion entry and links it to the original SIT entry.
Subsequent collisions to the same SIT will use the same process by
linking a new SIT Expansion entry to the last SIT Expansions entry on
the chain.

      A problem arises with the time needed to initialize these
32-byte entries to the correct format.  Each 32-byte write to cache
takes approximately 20 microseconds.  With up to 32,768 entries
allocated for the largest cache, the time needed to initialize all
these entries would be approximately 655 milliseconds.

      The solution to this time problem is to not initialize the SIT
Expansion entries in cache but in extended control store only on an
"as needed" basis (see psuedocode of process on the next page).  Two
separate singly linked "lists" control the availability of the SIT
Expansion entries; one a physically linked list, the other a
logically linked list.  The first list is one of previously used and
returned SIT Expansion entries.  The other is a pointer to the
beginning of the remaining unused portion of the SIT Expansion area
in cache.  This second pointer originally starts at the beginning of
the S...