An algebraic memory model

ABSTRACT

Memory in the von Neumann computer is usually viewed as a linear array. We prove that this view does not follow from the consecutive nature of this memory, but from the group structure of the law performed in the address arithmetic unit. By changing that law, we can get a memory with a non commutative access. As an example we describe the metacyclic memory.

REFERENCES

• 1: S. B. Akers and B. Krishnamurthy, Group graphs as interconnection networks, proc. 14th IEEE symposium on Fault-Tolerant Computing, pp. 422--427, june 1984.
• 2: A. Asthana , H. V. Jagadish , J. A. Chandross , D. Lin , S. C. Knauer, An intelligent memory system, ACM SIGARCH Computer Architecture News, v.16 n.4, p.12-20, Sept. 1988 [doi>10.1145/54331.54332]
• 3: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 4: S. Bhatt, F. Chung, T. Leighton and A. Rosenberg, Optlmal simulations of tree machines, proc. 27th IEEE symposium on Foundations of Computer Science, pp. 274--282, october 1986.
• 5: F. Chung, A. L. Rosenberg and L. Snyder, Perfect storage representations for families of data structures, SIAM J. Alg. Disc. Meth., vol. 4, no. 4, pp. 548--565, december 1983.
• 6: H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, Springer-Verlag, 1957.
• 7: P. M. Fenwick, Addressing operations for automatic data structure accessing, ACM SIGARCH Computer Architecture News, v.12 n.1, p.44-57, March 1984 [doi>10.1145/641602.641607]
• 8: M. Garzon, Cyclic automata, Theoretical Computer Science, v.53 n.2-3, p.307-317, Aug. 1987 [doi>10.1016/0304-3975(87)90071-5]
• 9: D. L. Johnson, Topics in the theory of group presentations, Cambridge University Press, 1980.
• 10: C. Jousselin, Nouvelle arithmétique d'accès mémoire, Revue Annuelle LEP 1987.
• 11: C. Jousselin and J-P. Moskowitz, More efficient retrieval of data in a computer memory, to be published in Philips Research Newsletter.
• 12: C. Jousselin and J-P. Moskowitz, Procédé et unité de gestion de mots d'adresse, French Patent 88 04809, april 12, 1988.
• 13: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 14: W. Magnus, A. Karrass and D. Solitar, Combinatorial group theory, Interscience, 1966.
• 15: A. L. Rosenberg, Data graphs and addressing schemes, J. Comp. Syst. Sci., vol. 5, pp. 193--238, 1971.