Interleaved addressing was implemented to support cache line fills tarting at a non-aligned address or if your cache line takes 4 words and your processor askes for word 2, the cache would start filling with word 2, then 3, then complete the line by filling words 0 and then 1. This reduces latency (e.g., intel processors).
For most FPGA applications it is better to stay away from interleaved addressing because it complicates design and restricts the maximum burst size of an access.(1)
Interleaving in disk storage
Low-level format utility performing interleave speed tests on a 10-megabyte IBM PC XT hard drive.
Interleaving was used in ordering block storage on disk-based storage devices (e.g., floppy disk and the hard disk). The primary purpose of interleaving was to adjust the timing differences between ready to transfer data, and data arriving at the drive head to be read. Interleaving was very common prior to the 1990s; but modern disk storage is not interleaved because processing speeds increased.
Interleaving was used for sector efficiency; after reading a sector, time would be permitted for processing, and then the next sector in sequence is ready to be read. Matching the sector interleave to the processing speed accelerates the data transfer, but incorrect interleave slows the system.
Example
Information is stored on disk storage (very small pieces) referred to as sectors or blocks. These are arranged in concentric rings (tracks) across the surface of each disk. Ordering these blocks in direct serial order in each track, such as 1 2 3 4 5 6 7 8 9, for early computing devices was not practical.
Data to be written or read is put into a special region/reusable memory or buffer. When data needed to be written, it was moved into the buffer, and then written from buffer to disk and reading was the reverse. Early computers were not fast enough to read a sector, move the data from the buffer to somewhere else, and be ready to read the next sector by the time that next sector was appearing under the read head.
In direct serial order, after the first sector was read the computer waits for three sectors to pass by before it is ready to receive data again; in direct order, sector two, three, and four have already passed by. The computer doesn't need sectors 4, 5, 6, 7, 8, 9, or 1, and must wait for these to pass by, before reading sector two waiting slows the data transfer rate.
To correct delays, the ideal interleave for this system would be 1:4, ordering the sectors like this: 1 8 6 4 2 9 7 5 3. It reads sector 1, processes for three sectors whereby 8 6 and 4 pass by, and just as the computer becomes ready again, sector two is arriving just as it is needed. Sometimes the interleave is expressed as a "skip factor", the number of physical sectors between consecutive logical sectors. A skip factor of 0 places the sectors sequentially—1 2 3 4 5 6 ... .
Modern disk storage does not use interleaving because buffer space is now so much larger. Data is now stored as clusters which are groups of sectors, and the data buffer is sufficiently large to allow all sectors in a block to be read at once without any delay.
Interleaving in error-correction coding
Interleaving is used in digital communication and storage systems to improve the performance of forward error correcting codes. Many communication channels are not memoryless: errors typically occur in bursts. If the number of errors within a code word exceeds the error-correcting code's capability, it fails to recover the original code word. Interleaving solves this problem with movement of source symbols across several code words, and more uniform distribution of errors.(2)
(1)<http://www.embeddedrelated.com/usenet/embedded/show/60826-1.php>. Web. 6 Nov. 2011.
(2)<http://en.wikipedia.org/wiki/Interleaving>. Web. 6 Nov. 2011.
a b B. Vucetic, J. Yuan (2000). Turbo codes: principles and applications. Springer Verlag. ISBN 978-0792378686.
No comments:
Post a Comment