Aperiodic mapping system using power-of-two stride access to interleaved devices
Patent 5111389 Issued on May 5, 1992. Estimated Expiration Date: May 5, 2009. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
An aperiodic mapping procedure for the mapping of logical to physical addresses is defined as a permutation function for generating optimized stride accesses in an interleaved multiple device system such as a large, parallel processing shared memory system wherein the function comprises a bit-matrix multiplication of a presented first (logical) address with a predetermined matrix to produce a second (physical) address. The permutation function maps the address from a first to a second address space for improved memory performance in such an interleaved memory system. Assuming that the memory has n logical address bits and 2d separately accessible memory devices (where dࣘn) and a second address that utilizes n-d bits of the first address as the offset within the referenced device node. The procedure includes performing a bit matrix multiplication between successive roows of the said matrix and bits of the first address to produce successive d bits of the second address.
Other References
IBM Technical Disclosure Bulletin, vol. 24, No. 5, Oct. 1981, pp. 2335-2336, "Electronic Signature for Use with Data Encryption Standard" by Matyas et al
IBM Technical Disclosure Bulletin, vol. 28, No. 2, Jul. 1985, pp. 603-604, "Matrix Digital Signature for Use with the Data Encryption Algorithm" by Lubold et al
IBM Technical Disclosure Bulletin, vol. 16, No. 7, Dec. 1973, pp. 2223-2224, "Information Retrieval Technique" by Anglin et al
IBM Technical Disclosure Bulletin, vol. 24, No. 5, Oct. 1981, pp. 2332-2334, "Electronic Signature for Data Encryption Standard" by Matyas et al
IBM Technical Disclosure Bulletin, vol. 25, No. 8, Jan. 1983, pp. 4445-4449, "Versatile Programmable Logic Array" by Langmaid
Pfister et al., "`Hot Spot` Contention and Combining in Multistage Interconnection Networks," Proceedings of the 1985 International Conference on Parallel Processing, pp. 790-797
Budnik et al., "The Organization and Use of Parallel Memories," IEEE Trans. on Computers, Dec. 1971, pp. 1566-1569
Batcher et al., "The Multidimensional Access Memory in STARAN," IEEE Trans. on Computers, Feb. 1977, pp. 174-177
Lawrie et al., "The Prime Memory System for Array Access," IEEE Tran. on Computers, C-31, No. 5, May 1982, pp. 435-442
Kuck, "ILLIAC IV Software and Application Programming," IEEE Trans. on Computers, vol. C-17, No. 8, Aug. 1968, pp. 758-770
Lawrie, "Access and Alignment of Data in an Array Processor," IEEE Trans. on Computers, vol. c-24, No. 12, Dec. 1975, pp. 1145-1155
Frailong et al., "XOR-Schemes: A Flexible Data Organization in Parallel Memories," Proceedings, International Conf. on Parallel Processing, Aug. 1985, pp. 276-283
Wijshoff et al., "The Structure of Perodic Storage Schemes for Parallel Memories," IEEE Trans. on Computers, vol. C-34, No. 6, Jun. 1985, pp. 501-505
Shapiro, "Theoretical Limitations on the Efficient Use of Parallel Memories," IEEE Trans. on Computers, vol. C-27, No. 5, May 1978, pp. 421-428
Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. on Computers, vol. C-20, No. 2, Feb. 1971, pp. 153-161
Lenfant, "Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations," IEEE Trans. on Computers, vol. C-27, No. 7, Jul. 1978, pp. 637-647
Pfister et al., "The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture," Proceedings, International Conf. on Parallel Processing, 1985, pp. 764-771
Brooks, "Performance of the Butterfly Processor-Memory Interconnection in a Vector Environment," Proceedings, International Conf. on Parallel Processing, 1985, pp. 21-24
Mandelbrot, "The Fractal Geometry of Nature," W. H. Freeman and Company, New York, 198
May 5, 2009. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
