Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Finite State Machine DEAT/TREAT Algorithm

IP.com Disclosure Number: IPCOM000019241D
Publication Date: 2003-Sep-08
Document File: 7 page(s) / 111K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disk drive rotational position optimization (RPO) algorithms use DEAT or TREAT tables to determine expected access times for commands. With DEAT the expected access time (EAT) calculation requires one divide and one multiply for each command in the queue. With TREAT the updating of table elements requires a fraction part to table elements if previous algorithms are used. The new algorithm presented here cuts the DEAT table space by 50% and eliminates both the divide and the multiply. No additional table space is required for EAT calculations or DEAT updates. With TREAT the new algorithm provides for an efficient update without the requirement of a fractional part to the table elements.

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 34% of the total text.

Page 1 of 7

Finite State Machine DEAT/TREAT Algorithm

  A summary of articles on disk drive rotational position optimization (RPO) algorithms is given by Burkhard and Palmer in "Rotational Position Optimization (RPO) Disk Scheduling", available at the following internet address:

http://www.cs.ucsd.edu/Dienst/UI/2.0/Describe/ncstrl.ucsd_cse/CS2001-0679

Also, the following US patents are directed to this subject: 6496877; 6418510; and 6272565.

Disk drive RPO algorithms use DEAT or TREAT tables to determine expected access times for commands. These tables typically have 30 rows and 8 or more columns. With DEAT the expected access time (EAT) calculation requires one divide and one multiply for each command in the queue. With TREAT the updating of table elements requires a fraction part to table elements if previous algorithms are used.

The new algorithm presented here cuts the DEAT table space by 50% and eliminates both the divide and the multiply. No additional table space is required for EAT calculations or DEAT updates. With TREAT the new algorithm provides for an efficient update without the requirement of a fractional part to the table elements.

New DEAT Algorithm

The new DEAT algorithm also uses a read and a write table, each with 30 rows and 8 columns, however, each element consists of a single byte, Dr,c . This eliminates half the table space. Furthermore, Dr,c is the delta to the EAT directly, hence the multiply and divide are eliminated. The EAT calculation is the following

EAT = SeekTime + RotationTime + Dr,c

The DEAT update consists of adding or subtracting one, conditioned on some probability. For the time being

If miss then sometimes Dr,c = Dr,c + 1

If hit


then sometimes Dr,c = Dr,c - 1

What is meant by "sometimes" must be defined. But in any case the EAT calculation and DEAT update are done without the need for any additional tables.

DEAT Update to Arrive at Equilibrium

1

Page 2 of 7

It is desired to have Dr,c equal to the probability of a miss (p) times the number of SIDs (N). This will be accomplished if the following probabilistic updates occur.

If miss (probability p) then add 1 to Dr,c with probability 1-p else don't change Dr,c If hit (probability 1-p) then subtract 1 from Dr,c with probability p else don't change Dr,c

Misses occur with probability p, and when a miss occurs Dr,c is incremented with probability 1-p. Hits occur with probability 1-p, and when a hit occurs Dr,c is decremented with probability p. Otherwise the DEAT remains unchanged. Increments and decrements occur with the same probability, p(1-p). In effect, p is not known directly during updating. Instead we are attempting to get a best guess at its value.

DEAT Update Using Dr,c/N

The estimate that is used for p during update is Dr,c/N. This produces

If Miss (probability p) then add 1 to Dr,c with probability 1-Dr,c/N else don't change Dr,c If Hit (probability 1-p) then subtract 1 from Dr,c with probability Dr,c/N else don't change Dr,c

When Dr,c is at the equili...