Memory - peregrineshahin/ChessProgrammingWiki GitHub Wiki

title: Memory

[ RNA, biological data storage [1] Memory is the ability to store, retain, and recall information and experiences as researched in cognitive science. Computer memory refers to physical devices used to store data and sequences of instructions (programs) on a temporary or permanent basis, typically distinguished as fast random-access memory and relatively slow data storage.

N-Bit Latches

N-Bit latches are arrays of one-bit latches or flip-flops typically as wide as a connected parallel data-bus. They may be used as a registers or scratchpad RAM inside a central processing unit.

RAM

Random access memory is a fast form of computer memory and refers to the idea that any piece of data can be stored and retrieved in a constant time, regardless of its physical location and whether or not it is related to the previous piece of data.

Static RAM

Static RAM (SRAM) is an array of latches, where each latch has a unique address, which connects the addressed latch to its data-bus, often used as CPU cache.

Static random access memory from Wikipedia

Dynamic RAM

Dynamic random access memory (DRAM) is a type of random access memory that stores each bit of data in a separate capacitor within an electronic circuit. Since capacitors leak charge, the information eventually fades unless the capacitor charge is refreshed periodically, which is the reason to call that memory dynamic. Since DRAM takes only one transistor and capacitor per bit, it is therefor used as cheap main memory part of recent computer data storage, despite its worse latency compared to SRAM.

[ DRAM write at a 4 by 4 array [7]

ROM

Read-only memory (ROM) is a class of storage programmed once and mainly used to distribute firmware. EPROMs have a small quartz window which admits UV light for erasure [8] . ROM or EPROM were often embedded inside a microcontroller in conjunction with some RAM. They were often used in dedicated chess computers.

[ National Semiconductor EPROMs 2764 and 2716 [9]

Since each data-bit stored in a ROM is a boolean function of its inputs or address, a ROM is also used to implement combinatorial logic.

Read-only memory from Wikipedia

Persistence

Auxiliary Storage

Beside the computer's random access main memory, auxiliary storage refer to mass storage like optical discs, and magnetic storage hard disk drives. Those devices are usually connected via a serial bus, and accessed via streams.

Compact Cassette as Auxiliary Storage in Intelligent Chess [10]

USB 3.0

Historical Data Storage

[ Plated wire memory from Wikipedia

[

Memory Hierarchy

Memory hierarchy from Wikipedia

Memory organisation from Wikipedia

Memory Management

Todays processors utilize all the above types of memory from small and fast to large but slow within the concepts of virtual memory, paging, protection and various caches.

Virtual Memory


Page table actions.svg	Virtual address space and physical address space relationship.svg
Physical address translation [12]	Virtual and physical address space [13]

Paging

Page (computer memory) from Wikipedia

Page table Page replacement algorithm Paging Demand Paging Page fault Copy-on-write

TLB

Translation lookaside buffer (TLB)

Huge Pages

Note that what Windows calls "large pages," Linux and Unix call "huge pages" or "huge TLB pages (x86 and x86-64)

Page Size Extension from Wikipedia
MSDN - Large-Page Support » Windows
Huge pages part 1 Introduction by Mel Gorman, LWN.net, February 16, 2010 » Linux
Huge pages part 2: Interfaces by Mel Gorman, LWN.net, February 24, 2010
Huge pages part 3: Administration by Mel Gorman, LWN.net, March 3, 2010
Huge pages part 4: benchmarking with huge pages by Mel Gorman, LWN.net, March 17, 2010
Huge pages part 5: A deeper look at TLBs and costs by Mel Gorman, LWN.net, March 23, 2010
Transparent huge pages in 2.6.38 by Jonathan Corbet, LWN.net, January 19, 2011

Memory Model

Memory Footprint

Beside their individual memory footprint, chess programs have to deal with huge memory areas of transposition table and possibly caches for endgame table- or bitbases and their relative huge random access latencies.

Miles Davis, Wayne Shorter, Herbie Hancock, Ron Carter, Tony Williams

Monika Malczak Quartet - Footprints, Witold Lutosławski Concert Studio of Polish Radio, Warsaw, May 20, 2016, YouTube Video

Monika Malczak, Mateusz Gramburg, Paweł Zwierzyński-Pióro, Michał Szeligowski

Multiprocessing

SMP
NUMA

Memory versus Search

Publications

Computer Memory

1960 ...

Kenneth C. Knowlton (1965). A Fast storage allocator. Communications of the ACM, Vol. 8, No. 10 : 623-625

1970 ...

Paul W. Purdom, Stephen M. Stigler (1970). Statistical Properties of the Buddy System. Journal of the ACM, Vol. 17, No. 4 [14]
Donald Eastlake (1977). Tertiary Memory Access and Performance in the Datacomputer. VLDB 1977

1980 ...

Paul W. Purdom, Cynthia A. Brown (1980). Exact formulas for the buddy system. Information Sciences, Vol. 22, No. 1
Ozalp Babaoglu, William Joy (1981). Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits. Proceedings of the 8th SOSP, Operating Systems Review, Vol. 15, No. 5, pp. 78-86
Bruce W. Leverett, Peter G. Hibbard (1982). An Adaptive System for Dynamic Storage Allocation. Software: Practice and Experience, Vol. 12, No. 6, pp. 543-555
Subir Bhattacharya, Amitava Bagchi (1986). Making Best Use of Available Memory when Searching Game Trees. Proceedings of the 5th International Conference on Artificial Intelligence (AAAI-86), pp. 163-167. AAAI/MIT Press, Boston, MA.

1990 ...

Peter W. Frey (1991). Memory-Based Expertise: Computer Chess vs. AI. ICCA Journal, Vol. 14, No. 4
Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
Wim Pijls, Arie de Bruin (1993). SSS*-like Algorithms in Constrained Memory. ICCA Journal, Vol. 16, No. 1
Hermann Kaindl, Gerhard Kainz, Angelika Leeb, Harald Smetana (1995). How to use limited memory in heuristic search. IJCAI 1995
Matteo Frigo (1997). The weakest reasonable memory model. Masters Thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, pdf
Dennis Breuker (1998). Memory versus Search in Games. Ph.D. thesis, Maastricht University, pdf available via Dennis Breuker's page
Harald Prokop (1999). Cache-Oblivious Algorithms. Masters thesis, Department of Electrical Engineering and Computer Science, MIT, pdf [15]
Erik D. Demaine, J. Ian Munro (1999). Fast Allocation and Deallocation with an Improved Buddy System. FSTTCS 1999, Lecture Notes in Computer Science, Vol. 1738, Springer [16]

2000 ...

Yue Yang, Ganesh Gopalakrishnan, Gary Lindstrom (2002). Specifying Java Thread Semantics Using a Uniform Memory Model. Java Grande 2002, pdf
F. Warren Burton, David J. Simpson (2000). Memory requirements for parallel programs. Parallel Computing, Vol. 26, Nos. 13-14
Qiang Wu, Artem Pyatakov, Alexey Spiridonov, Easwaran Raman, Douglas W. Clark, David I. August (2004). Exposing Memory Access Regularities Using Object-Relative Memory Profiling. CGO 2004, pdf
Ulrich Drepper (2007). What Every Programmer Should Know About Memory. pdf, also hosted by LWN.net

Memory part 1 Memory part 2: CPU caches Memory part 3: Virtual Memory Memory part 4: NUMA support Memory part 5: What programmers can do

David Gay, Robert Ennals, Eric Brewer (2007). Safe manual memory management. ISMM 2007
David Silver, Richard Sutton, Martin Müller (2008). Sample-Based Learning and Search with Permanent and Transient Memories. In Proceedings of the 25th International Conference on Machine Learning, pdf

2010 ...

Aaron Becker, Gengbin Zheng, Laxmikant Kale (2011). Distributed Memory Load Balancing. Encyclopedia of Parallel Computing, Springer
George Church, Yuan Gao, Sriram Kosuri (2012). Next-Generation Digital Information Storage in DNA. Science [17] [18]
Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran (2012). Cache-Oblivious Algorithms. ACM Transactions on Algorithms, Vol. 8, No. 1, pdf
Aravinthan Athmanathan, Milos Stanisavljevic, Junho Cheon, Seokjoon Kang, Changyong Ahn, Junghyuk Yoon, Min-Chul Shin, Taekseung Kim, Nikolaos Papandreou, Haralampos Pozidis, Evangelos Eleftheriou (2014). A 6-bit drift-resilient readout scheme for multi-level Phase-Change Memory. A-SSCC 2014
Milos Stanisavljevic, Aravinthan Athmanathan, Nikolaos Papandreou, Haralampos Pozidis, Evangelos Eleftheriou (2015). Phase-change memory: Feasibility of reliable multilevel-cell storage and retention at elevated temperatures. IRPS 2015
Aravinthan Athmanathan, Milos Stanisavljevic, Nikolaos Papandreou, Haralampos Pozidis, Evangelos Eleftheriou (2016). Multilevel-Cell Phase-Change Memory: A Viable Technology. IEEE Journal of Emerging and Selected Topics in Circuits and Systems, Vol. 6, No. 1
Sylvain Gelly, Karol Kurach, Marcin Michalski, Xiaohua Zhai (2018). MemGEN: Memory is All You Need. arXiv:1803.11203 [19]
Milos Stanisavljevic, Thomas Mittelholzer, Nikolaos Papandreou, Thomas P. Parnell, Haralampos Pozidis (2018). Drift-Invariant Detection for Multilevel Phase-Change Memory. ISCAS 2018

Cognition

1960 ...

Adriaan de Groot (1966). Perception and Memory versus Thought: Some Old Ideas and Recent Findings. Problem Solving: Research, Method, and Theory (ed. B. Kleinmuntz), pp. 19-50. John Wiley, New York.

1970 ...

Herbert Simon, Kevin J. Gilmartin (1973). A Simulation of Memory for Chess Positions. Cognitive Psychology, Vol. 5, pp. 29-46. pdf » MAPP
Peter W. Frey, Peter Adesman (1976). Recall Memory for Visually Presented Chess Positions. Memory & Cognition, Vol. 4, No. 5, 541-547
Neil Charness (1976). Memory for Chess Positions: Resistance to Interference. Journal of Experimental Psychology: Human Learning and Memory, Vol. 2, No. 6, pp. 641-653 » MAPP
Judith S. Reitman (1976). Mechanisms of Forgetting in Short-term Memory. Cognitive Psychology, Vol. 2, No. 2
Judith S. Reitman (1976). Skilled Perception in Go: Deducing Memory Structures from Inter-Response Times. Cognitive Psychology, Vol. 8, No, 3
Sarah E. Goldin (1978). Memory for the ordinary: Typicality effects in chess memory. Journal of Experimental Psychology: Human Learning and Memory, Vol. 4, No. 6, pp. 605-616
Sarah E. Goldin (1979). Recognition memory for chess positions: Some preliminary research. American Journal of Psychology, Vol 92, No. 1, pp. 19-32

1980 ...

Marvin Minsky (1980). K-Lines: A Theory of Memory. Cognitive Science 4, 117-133, pdf [20]
Dennis H. Holding, Robert I. Reynolds (1982). Recall or Evaluation of Chess Positions as Determinants of Chess Skill. Memory & Cognition, Vol. 10, No. 3
A. Harry Klopf (1982). The Hedonistic Neuron: A Theory of Memory, Learning, and Intelligence. Hemisphere Publishing Corporation, University of Michigan

1990 ...

Fernand Gobet (1993). A Computer Model of Chess Memory. Proceedings of the 15th Annual Meeting of the Cognitive Science Society, pp. 463-468.
Fernand Gobet, Peter Jansen (1994). Towards a chess program based on a model of human memory. Advances in Computer Chess 7. abstract
Robert W. Howard (1995). Learning and Memory: Major Ideas, Principles, Issues and Applications. Praeger, amazon.com
Adriaan de Groot, Fernand Gobet (1996). Perception and memory in chess. Heuristics of the professional eye. Assen: Van Gorcum, The Netherlands. ISBN 90-232-2949-5. Chapter 9; A discussion: Two authors, two different views? word reprint
Fernand Gobet, Herbert Simon (1996). Templates in Chess Memory: A Mechanism for Recalling Several Boards. Cognitive Psychology, Vol. 31, pp. 1-40.
Fernand Gobet, Herbert Simon (1996). Recall of random and distorted positions: Implications for the theory of expertise. Memory & Cognition, 24, 493-503.
Fernand Gobet, Herbert Simon (1996). Recall of rapidly presented random chess positions is a function of skill. Psychonomic Bulletin & Review, 3, 159-163, word reprint
Fernand Gobet, Herbert Simon (1998). Expert chess memory: Revisiting the chunking hypothesis. Memory, 6, 225-255
Richard S. Schultetus, Neil Charness (1999). Recall vs. position evaluation revisited: The importance of position-specific memory in chess skill. American Journal of Psychology, Vol. 112, No. 4, 555-569.

2000 ...

Pertti Saariluoma, Tei Laine (2001). Novice construction of chess memory. Scandinavian Journal of Psychology, Vol. 42, No. 2 [21]
Dharshan Kumaran, Eleanor A. Maguire (2005). The Human Hippocampus: Cognitive Maps or Relational Memory? Journal of Neuroscience, Vol. 25, No. 31
Guillermo Campitelli, Fernand Gobet, Amanda Parker (2005). Structure and Stimulus Familiarity: A Study of Memory in Chess-Players with Functional Magnetic Resonance Imaging. The Spanish Journal of Psychology Vol. 8, No. 2, 238-245. pdf
Alan H. Bond (2005). Representing episodic memory in a system-level model of the brain. Neurocomputing, vol 65-66, pp. 261-273, pdf
Guillermo Campitelli, Fernand Gobet, Kay Head, Mark Buckley, Amanda Parker (2007). Brain localisation of memory chunks in chessplayers. International Journal of Neuroscience, 117
Dharshan Kumaran (2008). Short-Term Memory and The Human Hippocampus. Journal of Neuroscience, Vol. 28, No. 15, pdf
Demis Hassabis (2009). The Neural Processes Underpinning Episodic Memory. Ph.D. thesis, University College London, Supervisor Eleanor A. Maguire, pdf