Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Patent
1996-06-28
1999-05-04
Chan, Eddie P.
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
711217, 711219, 364765, G06F 1200
Patent
active
059000236
ABSTRACT:
An efficient integer-division-by-an-constant method and apparatus. This integer-division-by-an-constant is useful in calculations which must be performed often and/or quickly, and where the denominator is fixed for the calculations, such as address calculations in massively parallel, distributed memory processor systems. Also described is a method and apparatus using the integer-division-by-an-constant method and apparatus, which facilitates removing power-of two restrictions on the reorganization and redistribution of data between remote and local memory blocks in a massively parallel, distributed-memory processing system. The flexible addressing scheme provided supports data organizations which vary widely depending on the processing task. In particular, a plurality of processing elements (PEs) operating in parallel within a subset of all the PEs in a massively parallel processor system, may simultaneously operate on an array data structure, the array data structure having an arbitrary size and shape. Different data organizations in memory are supported by a processing element (PE) internal array address having certain index ranges designated as the target PE number and the areas within those index ranges designating the offset within that PE's local memory. The index ranges and areas are distributed throughout the PE internal array address to achieve various data distributions throughout memory.
REFERENCES:
patent: 3777132 (1973-12-01), Bennett, Jr.
patent: 5434995 (1995-07-01), Oberlin et al.
patent: 5581705 (1996-12-01), Passint et al.
patent: 5586325 (1996-12-01), MacDonald et al.
patent: 5696922 (1997-12-01), Fromm
Robert Alverson, "Integer Division Using Reciprocals", Proceedings 10th Symposuim on Computer Arithmetic, pp. 186-190 (Jun. 1991).
Robert Alverson, "Integer Division Using Reciprocals", Proceedings 10th Symposium on Computer Arithmetic, pp. 186-190, (Jun., 1991).
Ehud Artzy, et al., "A Fast Division Technique for Constant Divisors", Communications of the ACM, pp. 98-101, (Feb., 1976).
Henry G. Baker, "Computing A*B (Mod N) Efficiently in Ansi C", ACM Sigplan Notices, pp. 95-98, (Jan., 1992).
Robert Bernstein, "Multiplication by Integer Constants", Software--Practice and Experience, pp. 641-652, (Jul., 1986).
Raymond T. Boute, "The Euclidean Definition of the Functions Div and Mod", ACM Transactions on Programming Languages and Systems, pp. 127-144, (Apr., 1992).
A.P. Chang, "A Note on the Modulo Operation", pp. 19-23, (Apr., 1995).
Torbjorn Granlund, et al., "Division by Invariant Intergers Using Multiplication", pp. 61-72, (1994).
David H. Jacobsohn, "A Combinatoric Division Algorithm for Fixed-Integer Divisors", IEEE Transactions on Computers, pp. 608-610, (Jun., 1973).
Shuo-Yen Robert Li, "Fast Constant Division Routines", IEEE Transactions on Computers, pp. 866-869, (Sep., 1985).
Daniel J. Magenheimer, "Integer Multiplication and Division on the HP Precision Architecture", In Proceedings Second International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 90-99, (Oct., 1978).
Chan Eddie P.
Cray Research Inc.
Nguyen T. V.
LandOfFree
Method and apparatus for removing power-of-two restrictions on d does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for removing power-of-two restrictions on d, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for removing power-of-two restrictions on d will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1867412