Cyclic Permutation Access Method – CPAM

STB Suite | The Industry Standard in Peripheral Testing.

Cyclic Permutation Access Method – CPAM

Engineering innovations from STB have always lead the storage test industry. That tradition of technical leadership continues with the introduction of the powerful new access algorithm, Cyclic Permutation Access Method or CPAM for short. CPAM produces an evenly distributed random LBA access pattern while guaranteeing that each LBA will be accessed once and only once.  Other random access methods miss entire block ranges, repeat some LBAs while never hitting others, no matter how long they are run. CPAM overcomes all of those shortcomings.

CPAM’s evenly distributed yet random access pattern will hit every LBA once and only once in a single full-drive pass.

CPAM produces the physical and queue system stress of true random access, while guaranteeing that every LBA is tested in the shortest amount of time.

CPAM is available in version 8.4 of the STB Suite Disk Manufacturing Module (DMM) and the Developers Toolbox (DTB) API.

 

Introduction to CPAM

Cyclic Permutation Access Method (CPAM) is a significantly improved algorithm for generating random
logical block addresses( LBAs). It is superior to the random number generator contained in the Standard C-Runtime Library in several critical areas, including

  • It is uniformly distributed (CPAM hits each LBA with equal probability)
  • It has total coverage (CPAM guarantees hitting every LBA)
  • Pictorial diagrams of the CPAM generator show the generator is indistinguishable from a true
    random number generator
  • It passes the “Autocorrelation Test”

We will address each of the above items in the remainder of this article

Uniform Distribution

Tests on the Standard C-Runtime Library random number generator “rand” have shown that it will hit some LBAs with different probabilities than others. In fact, on many intervals, it may only hit as few as 48% of the LBAs!! On certain intervals, rand will hit some LBAs multiple times, while skipping others. CPAM guarantees that every LBA on your disk drive will be hit with the exact same probability as any other LBA, even for large drives that are over 2TeraBytes.

Total Coverage

As mentioned above, rand will not necessarily hit every LBA. So, for example, if you have a 2TB drive and you execute 2 trillion (2TB) random I/Os to the drive, you are NOT guaranteed that each block on the drive has been hit. With CPAM, this is not the case. You are absolutely guaranteed that CPAM will hit every block on the drive.

Pictorial Diagrams

The rand function shows certain “striping”, which can be seen from the following picture of the rand function:
C RAND Runtime Generated IO Pattern

As you can see from the above picture, the rand function hardly looks random, with the very visible vertical bars in the picture of rand.

 

Compare the above picture to the one generated for CPAM:

STB Suite CPAM Generated IO Pattern

An incredible difference.  CPAM is non-distinguishable from a true random number generator!

Autocorrelation Test

The purpose of the autocorrelation test is to verify that any two bits in the numbers generated are independent of each other.  For example, if one bit is 0 then the probability any other bit is 1 should be 50% (similarly, the probability any other bit is 0 should be 50%).  The rand function exhibited a probability of 49.976%.  However, CPAM has a probability of exactly 50%.